基于模糊聚類的群分離與合并跟蹤算法

杜明洋，畢大平，王樹亮，潘繼飛

(國防科技大學電子對抗學院，安徽 合肥 230037)

0 引言

雜波環(huán)境下的密集多目標跟蹤是目標跟蹤領域的難點問題，尤其是當目標空間位置很近、互相遮擋現(xiàn)象嚴重，如遷徙的鳥群、監(jiān)控錄像中的行人、低空飛行的飛機編隊等[1-2]。Blackman于1977年對群問題進行了分類，他將問題分為中心群跟蹤(Centroid Group Tracking, CGT)和編隊群跟蹤(Formation Group Tracking, FGT)[3]。這兩種算法也是目前群目標跟蹤中比較實用的方法[4]，其中，CGT算法在20世紀70年代由Frazier和Scott提出。該算法直接利用群的中心對群進行跟蹤，最為直接，計算復雜度也相對較小；但當目標處于較強的背景噪聲中時，群中的虛假量測會破壞群的分布矩陣，使量測的互聯(lián)出現(xiàn)較大誤差，造成跟蹤效果惡化，在實際的軍事應用中將帶來很大的威脅[5]。文獻[6]采用群內聚類的方法，將群內的波動考慮到群中心的計算中，相比于傳統(tǒng)算法，能夠更加適應雜波的影響，航跡更加穩(wěn)定。

從20世紀70年代開始，信息融合逐漸被廣泛應用于軍事和非軍事的各個領域[7-8]。在多目標跟蹤領域，傳統(tǒng)的數(shù)據關聯(lián)算法例如最近鄰(NN)、概率數(shù)據關聯(lián)(PDA)、聯(lián)合概率數(shù)據關聯(lián)(JPDA)等都只利用了目標的運動狀態(tài)(距離、速度、方位)信息[9]。信息融合可以利用有關目標的屬性信息，如特征信息(空間分布特征、外形尺寸特征、電磁輻射特征等)、身份信息(敵我識別應答)等。以跟蹤飛機編隊為例，在海灣戰(zhàn)爭中，美軍首次突襲巴格達時，攻擊機群編隊由32架轟炸機、16架護航機、12架電子戰(zhàn)飛機、15架加油機組成。不同型號的飛機特征信息不同，但相對固定，而雜波的特征信息隨機性較強。基于此，可以利用多特征信息融合的方法對雜波進行篩選，提高對飛機編隊的跟蹤精度。

在飛機編隊的運動過程中，基于特定的戰(zhàn)術要求，會出現(xiàn)分離、合并等機動模式[10]，這種成員的合并與分離對于群目標跟蹤來說，都會引起群規(guī)模和質心的變化，造成跟蹤誤差變大，甚至丟失目標。現(xiàn)有的群目標分離、合并跟蹤算法大體可以分為兩類：一類從位置、方向、航跡歷史等方面檢測群分離與合并，基于PDA、模式空間、MCMC粒子濾波、SMC-PHDF、等方法進行群機動的處理[11-14]，文獻[15]通過區(qū)分彈道導彈與誘餌的微動多普勒特征，基于時頻圖的周期相關性進行群目標的分離檢測；另一類從群的結構模型出發(fā)，通過演化圖網絡模型估計群的結構及狀態(tài)，描述群的分離與合并運動[16]。基于此，本文通過多特征信息融合理論對回波進行篩選，提出了基于模糊聚類的群合并與分離算法。

1 多特征信息融合

關聯(lián)度定義為根據某個特征信息判定跟蹤門內的各個有效量測與真實目標的關聯(lián)程度。多特征信息融合，是基于目標多種特征信息的量測值，計算與真實目標的關聯(lián)度[17]。本文融合目標的運動狀態(tài)信息和電磁輻射信息，應用于CGT算法中的數(shù)據關聯(lián)，計算確認量測與真實目標之間的關聯(lián)度，一定程度上克服了雜波的干擾，使得量測值與預測值可以準確互聯(lián)。

假設航跡已經起始，則系統(tǒng)的動態(tài)方程可表示為：

X(k+1)=F(k)X(k)+G(k)u(k)+V(k)

(1)

量測方程為：

z(k)=H(k)X(k)+W(k)

(2)

式(2)中，H(k)為量測矩陣，z(k)表示k時刻群的量測值，W(k)表示零均值高斯白噪聲，設Z(k)為k時刻的量測集合，

(3)

式(3)中，mk為k時刻的量測個數(shù)。

1) 目標運動狀態(tài)關聯(lián)度

將目標運動狀態(tài)量測的關聯(lián)度記為ms，群中第i個有效量測的ms(i)定義為

(4)

式(4)中，di(k)為確認波門內有效狀態(tài)量測與預測值的距離。可以看出，ms(i)∈(0,1]，di(k)越小，ms(i)越大，則關聯(lián)度越大。

2) 目標載頻關聯(lián)度

基于目標載頻的關聯(lián)度記為mf，在第k次采樣中，群中各個確認量測對應的目標載頻分別用f1(k)，f2(k)，…，fM(k)表示。設第k-1次采樣時群跟蹤門所對應目標載頻的觀測值用f(k-1)表示，記觀測頻差Δfi(k)=|fi(k)-f(k-1)|。觀測頻差越大，則該量測與真實目標的關聯(lián)度就越小。此外，頻率關聯(lián)度的定義還與目標的頻率類型有關。基于此，對固定頻率(FIX)的目標，群中第i個有效量測的mf定義為：

(5)

對頻率捷變(FA)的目標，群中第i個有效量測的mf定義為：

(6)

式(6)中，fA是頻率捷變范圍，fε是門限值。mf(i)∈(0,1]，mf(i)越大，則關聯(lián)程度越高。

3) 目標脈寬關聯(lián)度

將脈寬(Pulse Width, PW)的關聯(lián)度記為mPW，mPW的定義也與目標的脈寬類型有關。定義原則與頻率關聯(lián)度相同。mPW(i)∈(0,1]，mPW(i)越大，說明關聯(lián)程度越高。

4) 目標脈沖重復間隔關聯(lián)度

第k次采樣時，各個有效量測的脈沖重復周期(Pulse Repetition Interval, PRI)分別用Tr1(k)，Tr2(k)，…，TrM(k)表示。假設第k-1次采樣時該確認波門所對應目標的PRI為Tr(k-1)，PRI的觀測差記為ΔTri(k)=|Tri(k)-Tr(k-1)|，簡記為ΔTri。

將PRI的關聯(lián)度記為mTr，表示脈沖重復間隔的觀測差對關聯(lián)程度的影響，mTr的定義與目標PRI的類型有關。若目標為重頻固定(PRIFIX)，則關聯(lián)度mTr的定義與固定頻率類型的mf的定義類似。若目標為重頻參差(PRIST)，以二參差為例，設二參差重頻的差值記為DTr，則確認波門中第i個有效量測的關聯(lián)度mTr的定義為：

(7)

式(7)中，Trε是由系統(tǒng)噪聲與量測噪聲導致的PRI測量誤差。mTr(i)∈(0,1]，mTr(i)越大，說明關聯(lián)程度越高。

完成上述各項特征信息的關聯(lián)度計算后，還需考慮各關聯(lián)度的權值分配。以a1，a2，a3，a4分別表示在運動狀態(tài)、目標載頻、脈寬、重頻等方面確認量測與真實目標的關聯(lián)度的權值，則群中第i個有效量測在多特征信息共同作用下的關聯(lián)度可以記為：

m(i)=a1ms(i)+a2mf(i)+a3mPW(i)+a4mTr(i)

(8)

權值滿足歸一化條件，即a1+a2+a3+a4=1。

權值的選擇在不同環(huán)境中需要視具體情況而定。以飛機編隊為例，如引言中所述，在實際應用中，作戰(zhàn)方式不同，飛機的力量編成也會不同。在合成空襲作戰(zhàn)中，常常將各種飛機統(tǒng)一編組，形成執(zhí)行不同任務的群體，在統(tǒng)一指揮下協(xié)同作戰(zhàn)，共同完成攻擊任務。因此目標的載頻、脈寬、重頻等電磁輻射信息也會不盡相同。本文以融合目標的運動狀態(tài)信息和載頻信息為例，由于在密集雜波背景下，位置的量測信息會受到雜波的干擾，因此運動狀態(tài)關聯(lián)度ms的權值a1應當相對較小；另一方面，與雜波頻率的隨機性相比，目標載頻更具有確定性，因此通過載頻信息可以更加準確地區(qū)分雜波和真實量測，所以目標載頻關聯(lián)度mf的權值a2應當相對較大。在本文中，運動狀態(tài)關聯(lián)度ms權值a1取0.3，目標載頻關聯(lián)度mf權值a2取0.7。

根據相關指標信息，設定關聯(lián)度門限值η，對候選回波進行篩選，

(9)

在遍歷每一時刻確認波門內量測之后，即完成了對群內目標數(shù)量的估計。在本文中，η取0.5。

2 基于聚類的群跟蹤算法

按照所采用的基本策略不同，可將聚類算法分為兩類。一是層次(hierarchical)或凝聚式(agglomerative)算法，這類算法一開始將每個點都看成是一個簇，簇與簇之間按照接近度(closeness)來組合，而接近度可以基于“接近”的不同含義采用不同的定義。當進一步的組合導致多個原因之一的非期望結果時，上述組合過程結束。例如，當達到預先給定的簇數(shù)目時可以停止聚類。二是點分配算法，即按照某個順序依次考慮每個點，并將它分配到最適合的簇中，點分配算法中最經典的是k均值(k-means)算法。該算法假定環(huán)境為歐式空間，且最終簇的數(shù)目已知。本文基于k-means算法，結合中心群跟蹤算法，將密集的群內目標分成若干個聚類小群，通過對小群運動狀態(tài)的估計實現(xiàn)對大群整體的跟蹤。具體算法步驟如下：

1) 針對群中心的一步預測建立跟蹤波門

設X(k|k-1)為k時刻群狀態(tài)的一步預測值，定義落入其確認波門內的量測必須滿足以下條件，

(10)

(11)

RG=BRmB′

(12)

式(12)中，B為量測坐標系到跟蹤坐標系中的轉換矩陣，Rm是量測坐標系下的群量測的誤差協(xié)方差矩陣。從滿足上述判決條件的點跡中，選擇歸一化距離D2最小的量測作為一個群t的種子量測(Seed Measurement)。

2) 選擇聚類中心

假設群內聚類數(shù)目為T，定義群內第t個聚類中心(Cluster Centroid)在k時刻的狀態(tài)向量為：

(13)

考慮到聚類中心將參與小群幾何中心的計算，因此最好選擇群內的目標點，這樣可以避免引入新的點跡，影響群內目標的分布。此外，想要選出極有可能不在同一簇的點，一種簡單的方法是選擇彼此距離盡量遠的點跡，即“最遠”原則。基于此，聚類中心的選取按照以下步驟進行：

①選擇種子量測作為第1個聚類中心；

②計算剩余點到種子量測的距離，從中選擇最大距離對應的點作為第2個聚類中心；

③分別計算剩余點到前兩個聚類中心的距離，兩個距離中的較小值作為該點到前兩個聚類中心的“得分”，選擇“得分”最高對應的點作為第3個聚類中心；

④以此類推，完成聚類中心的初始化。

3) 形成小群

計算群內量測與聚類中心的距離，將量測歸于最近的聚類中心，形成t個小群。計算各小群的幾何中心、分布矩陣及權重，

(14)

(15)

(16)

k時刻群t所占的權重γk,t可用下式表示，

(17)

4) 航跡維持

群目標在運動過程中可能存在整體機動(加速、減速或轉彎等運動)或分離、合并的情形。以遂行轟炸任務為例，飛機以編隊形式到達任務區(qū)域，之后編隊分離，對不同位置的目標進行轟炸，任務完成后以編隊形式返航。文獻[6]中利用速度的一步預測值對聚類中心進行外推，然而當飛機編隊運動狀態(tài)發(fā)生變化時，外推法得到的聚類中心不能準確反映群中目標的分布，從而使聚類效果受到影響。因此，本文根據每一時刻篩選的量測實時地選取聚類中心。將大群通過聚類分為T個小群后，需要與上一時刻進行數(shù)據互聯(lián)以維持航跡。本文基于最近鄰算法的思想，通過下式計算k時刻第j個聚類中心的真實值與各聚類中心的一步預測的歸一化距離，選擇最小歸一化距離所對應的值與k-1時刻進行互聯(lián)，完成航跡的維持。

(18)

算法的流程圖如圖1所示。

圖1 算法流程圖Fig. 1 Algorithm flow chart

3 仿真實驗

相比文獻[6]，本文提出算法做出兩點改進，第一，采用多特征信息融合的方法進行量測的篩選；第二，采用實時選取聚類中心的方法代替了外推法。本節(jié)通過Monte Carlo仿真實驗對上述兩點改進的有效性分別進行驗證。實驗結果的評價指標采用跟蹤估計的均方根誤差(RMSE)，定義為：

(19)

3.1 仿真條件

跟蹤由8個目標組成的群目標，各目標的間距在150～300 m之間，目標在x-y平面內運動，模擬實際飛機編隊飛行。檢測概率Pd=0.98，門概率PG=0.999 7，采樣間隔為1 s，仿真運動時間為60 s，Monte Carlo仿真次數(shù)為50次。在濾波過程中產生隨機的雜波，雜波的空間位置服從高斯分布，個數(shù)服從泊松分布，初始雜波密度λ=4×10-6/m2。目標初始狀態(tài)數(shù)據如表1，表2所示。本文選取目標載頻與運動狀態(tài)作為特征信息進行融合，具體數(shù)據如表3所示，將大群劃分為4個聚類小群，即T=4。

在群分離場景中，t=1～34 s，群整體做勻速直線運動；t=35 s時，群發(fā)生分離，分群1中有4個目標，做左轉彎運動，分群2中剩余4個目標繼續(xù)做勻速直線運動。

表1 群分離場景目標初始狀態(tài)數(shù)據

表2 群合并場景目標初始狀態(tài)數(shù)據

表3 目標的輻射特征數(shù)據

在群合并場景中，t=1～34 s，分群1做左轉彎運動，t=35～60 s，做勻速直線運動；分群2一直做勻速直線運動。當t=35 s時，群發(fā)生合并。

3.2 仿真結果及分析

1) 仿真實驗1

從仿真步數(shù)中任選時刻k，觀察本文算法各步驟對接收量測處理的效果，以驗證算法的有效性，具體如圖2所示。

圖2 算法效果圖Fig.2 Performance of the proposed algorithm

由圖2可以看出，首先，多特征信息融合的方法較好地完成了對量測的篩選；其次，采用k-means聚類的方法，設置初始聚類數(shù)目為4，并以種子量測作為第1個聚類中心，依次完成聚類中心的選取，而后根據各點間距離，將大群分成4個小群，計算各小群權值，得出各小群的中心。下一時刻，重復上述步驟，并與k時刻進行航跡關聯(lián)，以此類推，通過估計4個聚類小群的運動狀態(tài)，完成對大群態(tài)勢的檢測。

2) 仿真實驗2

驗證多特征信息融合數(shù)據關聯(lián)的準確性。場景為雜波背景下勻速運動的群目標，將文獻[6]中算法改進為實時選取聚類中心，僅驗證信息融合對算法的優(yōu)化效果。

圖3(a)為本文算法對群目標的跟蹤效果圖。由圖3(b)可以看出，相比于文獻[6]中基于聚類的CGT算法，本文提出算法通過融合目標多個特征的信息，能夠更好地對雜波進行篩選，提高了對群中心的估計精度。

圖3 多特征信息融合算法性能圖Fig.3 Performance of multi-characteristic information fusion algorithm

3) 仿真實驗3

驗證本文算法對群機動的檢測能力。圖4、圖5分別為運動場景及跟蹤效果模擬。圖6為群分離前后傳統(tǒng)算法、文獻[6]算法與本文算法對群中心的估計誤差對比。

圖4 群機動的真實運動軌跡及雜波分布圖Fig.4 Motion trajectory of group maneuvering and clutter map

圖5 群機動跟蹤效果圖Fig.5 Performance of tracking group target maneuvering

圖6 群分離跟蹤誤差Fig.6 RMSE of tracking group target splitting

由圖5可以看出，通過群內聚類的方式可以較好地檢測出群的分離與合并。特別的，在群合并的跟蹤中，起始時刻相當于多群的跟蹤問題，按照本文提出算法，第一個聚類中心的初始化選擇有效量測的幾何中心，由于與真實量測距離較遠，小群中僅有一個點(聚類中心)，即形成了起始時刻的孤立點。但在下一個循環(huán)中，以種子量測作為第一個聚類中心，通過聚類以及航跡互聯(lián)，較好地實現(xiàn)了對兩個分群的跟蹤，在群合并之后跟蹤效果較好。由此說明本文提出算法對群分離和合并都具有較好的跟蹤效果，證明了算法的普適性。

通過比較可以看出，三種算法中本文算法精度最高。特別的，由圖6(a)可以看出，文獻[6]采取聚類的方法，相比于傳統(tǒng)算法，提高了雜波背景下群中心的估計精度；但是由于速度的估計存在誤差，隨著算法的循環(huán)，采用速度估計值對聚類中心進行外推會使得誤差積累，聚類中心將無法準確反映群內目標的分布，因此分離前文獻[6]中算法的估計誤差逐漸增大。從圖6(b)和(c)中可看出，當群分離之后，此時大群中心的速度與兩分群的實際速度相差較大，仍然利用其進行外推，將導致跟蹤發(fā)散甚至丟失目標，因此，文獻[6]的算法不具有檢測群機動的能力；而傳統(tǒng)算法只對大群中心進行估計，估計結果可能更接近其中一個分群，即對一個分群估計誤差較小，對另一分群估計誤差較大，所以傳統(tǒng)算法同樣無法檢測群的機動。

4) 仿真實驗4

比較文獻[6]中算法與本文算法的實時性。改變雜波密度，跟蹤群目標機動，兩種算法的耗時對比如圖7所示。

圖7 群分離算法耗時對比圖Fig.7 Comparison of calculate time of tracking group target splitting

從圖7中可以看出，本文采用實時選取聚類中心的方法，相比文獻[6]中的外推法運算量有所增加。通過計算，本文算法平均單次Monte Carlo仿真耗時增加了4%，即本文算法在不影響跟蹤實時性的前提下，減小了對群目標的跟蹤誤差，并實現(xiàn)了群機動的檢測，相比于文獻[6]中算法性能有所提升。

4 結論

本文提出了基于模糊聚類的群分離與合并跟蹤算法。該算法首先通過結合目標的運動狀態(tài)信息及電磁輻射信息，計算候選回波與真實目標的關聯(lián)度，對量測進行篩選；其次，基于k-means聚類將群目標分為若干個小群，并結合中心群跟蹤算法，選取種子量測作為第一個聚類中心，根據“最遠”原則，依次完成各聚類中心的初始化，在每一個算法循環(huán)中實時選取聚類中心，采用最近鄰方法以維持航跡。仿真結果表明，本文算法提高了對群目標的跟蹤精度，并且能夠有效檢測群的分離與機動，具備工程實用性。