基于聚類和Hough變換的多編隊航跡起始算法

邢鳳勇，熊 偉，王海鵬

（海軍航空工程學院 電子信息工程系，山東 煙臺 264001）

雜波環境下的密集多目標跟蹤[1]是多傳感器多目標跟蹤領域的難點，特別是所跟蹤目標的空間位置距離很近、運動方式大致相同時，不僅回波眾多，而且關聯門交叉嚴重，要對其進行精確跟蹤十分困難[2]。當所跟蹤目標由多個個體組成時，它們所展現出的主要特點是一種群運動[3]，因而在目標跟蹤領域形成了一種新的跟蹤問題，即編隊目標跟蹤。

編隊被定義為方向、距離和速度滿足以下3個條件的多個目標：① 運動方向一致；② 編隊中各成員之間的距離遠遠小于各編隊之間的距離；③ 速度基本相同。[4]

航跡起始是航跡處理中的首要問題，但同跟蹤維持的研究相比，航跡起始課題方面的研究成果非常少。由于航跡起始時，目標一般距偵察站很遠，傳感器探測分辨力低、測量精度差[5]，加之真假目標的出現無真正的統計規律。因此，在多目標航跡處理中，航跡起始問題是難以處理的問題。

由定義可知，編隊目標的運動中各個成員之間都是基于固定相對位置，即它們有固定幾何結構。在雷達分辨力高或編隊目標分布稀疏的情況下，可以區分辨出編隊的幾何結構[6]，此時的編隊目標航跡起始可以通過判別這種具體的結構來達到剔除編隊中雜波的目的。但在現代戰爭中，編隊目標的密集度有增無減，群中各目標空間距離很小，當雷達的分辨力較低時，容易造成量測的丟失。測量噪聲和過程噪聲的存在使得普通雷達很難分辨編隊中的各個成員，而編隊結構也就不得而知，以上提到的編隊跟蹤的結構優勢就不能作為編隊目標跟蹤和航跡起始的判斷依據。在這種情況下，本文提出并改進了一種易于實現的、計算量較少的基于K均值聚類[7]和Hough變換的編隊目標航跡起始算法。

1 傳感器回波的循環閾值聚合

通過比較兩個量測的空間距離[8]與一個常數之間的大小關系可以完成傳感器回波的分割，假定Z (k)為傳感器在k時刻所獲得的量測集，且

式中，mk為k時刻的量測個數。

定義1：Z(k)中第i個量測 zi(k)=[xik,yik]'與第j個量測 zj(k)的距離為：

若

則量測 zi(k)和zj(k)屬于同一個子群。其中，d0反映了編隊內目標的稠密程度，其取值與傳感器系統編隊目標跟蹤的目的有關。對機械掃描雷達而言，采用編隊目標跟蹤的目的是解決錯誤互聯所引起的濾波誤差協方差增大的問題，故 d0為最近鄰域法剛好不能區分的兩個目標之間的空間距離。

編隊目標分割可分為以下4步[9]：

1）選取 zi(k)為中心，以 d0為閾值建立波門；

2）對落入波門中的每個量測重新以 d0為閾值建立波門，尋找落入最新波門中的量測；

3）重復第2）步，直到所建的波門中沒有量測為止，在此過程中所涉及到的量測定義為一個子群；

4）從不屬于已確定子群的量測中任意選取一個量測，重復以上3步直到最后一個量測，最終完成對雷達回波的分割。

2 K均值聚類的子群中心點算法

定義2：設X是數據集，即

定義X的m 聚類?，將X 分割成m個集合（聚類）C1,…,Cm，使其滿足下面3個條件：

而且，在聚類中包含的向量彼此“更相似”，與其他類中的向量“不相似”。

K-均值聚類[10]是一種迭代的聚類算法，迭代過程中不斷地移動簇集中的成員直至得到理想的簇集為止。K-means算法工作過程如下：

首先，從n個數據對象任意選擇k個對象作為初始聚類中心，而對于所剩下的其他對象，則根據它們與這些聚類中心的相似度（距離），分別將它們與其最相似的（聚類中心所代表的）聚類；其次，再計算每個所獲新聚類的中心（該聚類中所在對象的均值），不斷重復這一過程，直到標準測度函數開始收斂為止。相似度通過距離公式進行計算，常用的距離有Minkoski距離、Euclid距離、Chebyshev距離、Mahalanois距離等。在此以歐氏距離作為距離計算公式如下：

式(5)中：xij是第i類第j個樣本；im是第i類的聚類中心或稱質心；in是第i類樣本個數。

K-均值聚類算法實質就是通過反復迭代尋找k個最佳的聚類中心，將全體n個樣本點分配到離它最近的聚類中心，使聚類誤差平方和E最小。

K-均值聚類法實施流程圖如下[11]：

圖1 K-均值聚類法流程圖

3 編隊目標互聯的雜波群去除

設量測集Z(k)最終分割為m個編隊，記為{U1,U2,…,Um}。在通過K-均值聚類法獲得相鄰時刻各個編隊的中心之后，定義k=m時刻第i個編隊的中心與k=n時刻第j個編隊的中心的距離為

若這兩個編隊互聯，則必須滿足下式

式(8)中：T為采樣間隔；n=m+1；Vmax為編隊的最大速度，其取值視具體編隊類型而定。

如果k=m時刻第i個編隊與k=n時刻的多個編隊互聯，選取距離最近的編隊為互聯編隊。

4 Hough變換的編隊目標航跡起始

將極坐標引入Hough變換，得到其變換函數：

如圖2所示，數據空間中的—條直線可以通過從原點到這條直線的距離ρ和ρ與x軸的夾角θ 來定義。

圖2 數據空間上的4個點

如圖3所示，P1、P2、P3、P4 經公式(9)變換到參數空間并在參數空間相交于一點。

圖3 數據空間變換到參數空間后的點跡

在參數空間中交于公共點的曲線所對應的直角坐標系中的坐標點一定在一條直線上。Hough變換基本算法采用參考文獻[12]。

5 仿真驗證與分析

為驗證本文所提出的K均值聚類和Hough變換的密集多編隊航跡起始算法的有效性，本文對兩個編隊共10個目標的航跡起始進行了仿真驗證。

5.1 仿真環境與結果

本節假定編隊目標的起始在如下環境中進行：過程噪聲分量q=0.01；測距誤差rσ=90 m；測角誤差 θσ=0.03 rad；檢測概率 DP=0.997；門概率GP=0.97；采樣間隔T=1 s；仿真中每個周期的雜波個數按照泊松分布確定的，取λ=50；每次仿真步數40步。在該環境下對10個目標進行航跡起始，前5個目標組成第一個編隊，編隊中每個目標的初始位置均在（1 500 m，2 000 m）與（0 m，500 m）中隨機產生，初始速度為（270 m/s，270 m/s）；后5個目標組成第二個編隊，編隊中每個目標的初始位置均在（0 m，500 m）與（1 500 m，2 000 m）中隨機產生，初始速度為（270 m/s，270 m/s）。

圖4～6為量測空間的目標點跡以及聚類后的群中心點，圖7為變換到參數空間Hough變換圖，圖8為量測航跡和編隊航跡對比圖。

圖4 前3個時刻傳感器回波

圖5 聚合后的前3個時刻傳感器回波

圖6 K-均值聚類的各子群中心

圖7 互聯上的兩條航跡的Hough變換

圖8 航跡起始圖

5.2 仿真分析

圖4為低分辨率傳感器對兩個密集編隊共10個目標的量測點跡圖，可以明顯看出前3個時刻目標明顯分成兩個編隊，編隊內部各目標間沒有固定的幾何結構。目標回波較為密集，而雜波分布較為分散，所以在循環閾值聚合中去除了大量在觀測空間內均勻分布的雜波，這同時也是編隊目標跟蹤中可以用來去除雜波的重要特征。

圖5前3個時刻傳感器回波通過循環閾值聚合后形成的空間子群分布態勢圖。這里設同一子群中兩個量測點判為一個子群的最大距離為230 m，不但目標點聚合成為子群，而且距離較近的雜波點也聚合成了子群，分布分散的雜波點跡得到了消除。

圖6對聚合后的子群代入K-均值聚類法，形成各個子群的中心。圖中前3個時刻形成的航跡已經比較清晰，雜波子群中心間的距離都遠遠大于目標以最大速度在采樣間隔間的運行距離，所以通過中心外推法又進一步去除了雜波子群。

圖7對互聯上的前3時刻子群中心點變換到參數空間中去，6條曲線相交于兩個點，每個交點的3條曲線分別代表3個時刻的互聯中心點在參數空間的分布，很明顯兩個編隊航跡起始成功。

圖8所示為兩個編隊的航跡起始圖，從圖中可以看出，同一編隊中的目標量測點跡相互交叉，沒有固定的相對位置。該航跡起始過程可以滿足編隊起始的需要，能夠較精確的完成編隊目標的起始。

由以上分析，K-均值聚類算法與Hough變換的相互結合給編隊目標航跡起始和目標跟蹤提出了新的思想。前者通過聚類更加準確的求出了子群的中心，為后者Hough變換準確判斷子群中心點是否在一條直線上提供了更好的條件。總的來說，該方法思路清晰，計算量較小，去除雜波能力強，航跡起始率高。

6 結束語

本文提出了一種編隊目標航跡起始算法,用于密集雜波環境下編隊目標航跡起始分析。

該算法將聚類算法和Hough變換思想引入到編隊目標航跡起始模型中，本文算法不僅能在密集雜波環境下對目標有效航跡起始，而且航跡起始時間短，航跡起始成功率高，節省了雷達資源，滿足了現代戰場環境下的戰爭需要。

但同時，當一個編隊中目標成員個數較少時，特別是在雜波特別密集時，雜波和目標形成的聚類就會對子群中心的求取產生較大的影響，Hough變換的效果和正確率還有待于進一步提高。因此，如何降低雜波對稀疏編隊航跡起始的影響，是下一步工作的重點。

[1]潘泉,梁彥,楊峰,等.現代目標跟蹤與信息融合[M].北京∶國防工業出版社,2009∶89-92.

[2]SOFIKNE AFFES,SAEED GAZOR,YVES GRENIER.An algorithm for multisource beamforming and multitarget tracking[J].IEEE,1995,98(12)∶57-61.

[3]SALMOND D J,GORDON N J.Group tracking with limited sensor resolution and finite field of view[J].Signal and Data Processing of Small Traget,2000,57(45)∶45-48

[4]何友,修建娟,張晶煒.雷達數據處理及應用[M].2版.北京∶電子工業出版社,2009∶184-185.

[5]金術玲,梁彥,王曾福,等.兩級Hough變換航跡起始算法[J].電子學報,2008,26(3)∶234-237.

[6]KEVIN GILHOLM,SIMON GODSILL,SIMON MASKELL,et al.Poisson models for extended target and group tracking[J].Signal and Data Processing of Small Traget,2005,34(78)∶67-71.

[7]時銀水,姬紅兵,湯金平.對斷續點跡的速度模糊聚類航跡起始研究[J].儀器儀表學報,2009,10(30)∶38-42.

[8]耿文東.編隊目標跟蹤綜述[C]//第十屆全國雷達學術年會.北京∶國防工業出版社,2008∶367-371.

[9]YANG CHEN-YANG,QU JIAN-MING,MAO SHI-YI,et al.An initialization method for group tracking[J].IEEE,Signal and Data Processing of Small Traget,1995,45(60)∶303-306.

[10]SERGIOS THEODORIDIS,KONSTANTINOS KOUTROUMBAS.Pattern Recognition[M].李晶皎,王愛俠,張廣淵,譯.北京∶電子工業出版社,2006∶317-318,410-412.

[11]蔡慧,劉洪波,韓國棟.基于K均值聚類的隨機網絡拓撲模型[J].計算機工程與設計,2009,30(5)∶1089-1090.

[12]王峰.基于Hough變換的航跡起始算法[J].杭州電子科技大學學報,2008,28(6)∶87-90.