邢鳳勇，熊 偉，王海鵬

（海軍航空工程學(xué)院 電子信息工程系，山東 煙臺(tái) 264001）

雜波環(huán)境下的密集多目標(biāo)跟蹤[1]是多傳感器多目標(biāo)跟蹤領(lǐng)域的難點(diǎn)，特別是所跟蹤目標(biāo)的空間位置距離很近、運(yùn)動(dòng)方式大致相同時(shí)，不僅回波眾多，而且關(guān)聯(lián)門交叉嚴(yán)重，要對(duì)其進(jìn)行精確跟蹤十分困難[2]。當(dāng)所跟蹤目標(biāo)由多個(gè)個(gè)體組成時(shí)，它們所展現(xiàn)出的主要特點(diǎn)是一種群運(yùn)動(dòng)[3]，因而在目標(biāo)跟蹤領(lǐng)域形成了一種新的跟蹤問(wèn)題，即編隊(duì)目標(biāo)跟蹤。

編隊(duì)被定義為方向、距離和速度滿足以下3個(gè)條件的多個(gè)目標(biāo)：① 運(yùn)動(dòng)方向一致；② 編隊(duì)中各成員之間的距離遠(yuǎn)遠(yuǎn)小于各編隊(duì)之間的距離；③ 速度基本相同。[4]

航跡起始是航跡處理中的首要問(wèn)題，但同跟蹤維持的研究相比，航跡起始課題方面的研究成果非常少。由于航跡起始時(shí)，目標(biāo)一般距偵察站很遠(yuǎn)，傳感器探測(cè)分辨力低、測(cè)量精度差[5]，加之真假目標(biāo)的出現(xiàn)無(wú)真正的統(tǒng)計(jì)規(guī)律。因此，在多目標(biāo)航跡處理中，航跡起始問(wèn)題是難以處理的問(wèn)題。

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

1 傳感器回波的循環(huán)閾值聚合

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

式中，mk為k時(shí)刻的量測(cè)個(gè)數(shù)。

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

若

則量測(cè) zi(k)和zj(k)屬于同一個(gè)子群。其中，d0反映了編隊(duì)內(nèi)目標(biāo)的稠密程度，其取值與傳感器系統(tǒng)編隊(duì)目標(biāo)跟蹤的目的有關(guān)。對(duì)機(jī)械掃描雷達(dá)而言，采用編隊(duì)目標(biāo)跟蹤的目的是解決錯(cuò)誤互聯(lián)所引起的濾波誤差協(xié)方差增大的問(wèn)題，故 d0為最近鄰域法剛好不能區(qū)分的兩個(gè)目標(biāo)之間的空間距離。

編隊(duì)目標(biāo)分割可分為以下4步[9]：

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

2）對(duì)落入波門中的每個(gè)量測(cè)重新以 d0為閾值建立波門，尋找落入最新波門中的量測(cè)；

3）重復(fù)第2）步，直到所建的波門中沒(méi)有量測(cè)為止，在此過(guò)程中所涉及到的量測(cè)定義為一個(gè)子群；

4）從不屬于已確定子群的量測(cè)中任意選取一個(gè)量測(cè)，重復(fù)以上3步直到最后一個(gè)量測(cè)，最終完成對(duì)雷達(dá)回波的分割。

2 K均值聚類的子群中心點(diǎn)算法

定義2：設(shè)X是數(shù)據(jù)集，即

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

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

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

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

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

K-均值聚類算法實(shí)質(zhì)就是通過(guò)反復(fù)迭代尋找k個(gè)最佳的聚類中心，將全體n個(gè)樣本點(diǎn)分配到離它最近的聚類中心，使聚類誤差平方和E最小。

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

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

3 編隊(duì)目標(biāo)互聯(lián)的雜波群去除

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

若這兩個(gè)編隊(duì)互聯(lián)，則必須滿足下式

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

如果k=m時(shí)刻第i個(gè)編隊(duì)與k=n時(shí)刻的多個(gè)編隊(duì)互聯(lián)，選取距離最近的編隊(duì)為互聯(lián)編隊(duì)。

4 Hough變換的編隊(duì)目標(biāo)航跡起始

將極坐標(biāo)引入Hough變換，得到其變換函數(shù)：

如圖2所示，數(shù)據(jù)空間中的—條直線可以通過(guò)從原點(diǎn)到這條直線的距離ρ和ρ與x軸的夾角θ 來(lái)定義。

圖2 數(shù)據(jù)空間上的4個(gè)點(diǎn)

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

圖3 數(shù)據(jù)空間變換到參數(shù)空間后的點(diǎn)跡

在參數(shù)空間中交于公共點(diǎn)的曲線所對(duì)應(yīng)的直角坐標(biāo)系中的坐標(biāo)點(diǎn)一定在一條直線上。Hough變換基本算法采用參考文獻(xiàn)[12]。

5 仿真驗(yàn)證與分析

為驗(yàn)證本文所提出的K均值聚類和Hough變換的密集多編隊(duì)航跡起始算法的有效性，本文對(duì)兩個(gè)編隊(duì)共10個(gè)目標(biāo)的航跡起始進(jìn)行了仿真驗(yàn)證。

5.1 仿真環(huán)境與結(jié)果

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

圖4～6為量測(cè)空間的目標(biāo)點(diǎn)跡以及聚類后的群中心點(diǎn)，圖7為變換到參數(shù)空間Hough變換圖，圖8為量測(cè)航跡和編隊(duì)航跡對(duì)比圖。

圖4 前3個(gè)時(shí)刻傳感器回波

圖5 聚合后的前3個(gè)時(shí)刻傳感器回波

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

圖7 互聯(lián)上的兩條航跡的Hough變換

圖8 航跡起始圖

5.2 仿真分析

圖4為低分辨率傳感器對(duì)兩個(gè)密集編隊(duì)共10個(gè)目標(biāo)的量測(cè)點(diǎn)跡圖，可以明顯看出前3個(gè)時(shí)刻目標(biāo)明顯分成兩個(gè)編隊(duì)，編隊(duì)內(nèi)部各目標(biāo)間沒(méi)有固定的幾何結(jié)構(gòu)。目標(biāo)回波較為密集，而雜波分布較為分散，所以在循環(huán)閾值聚合中去除了大量在觀測(cè)空間內(nèi)均勻分布的雜波，這同時(shí)也是編隊(duì)目標(biāo)跟蹤中可以用來(lái)去除雜波的重要特征。

圖5前3個(gè)時(shí)刻傳感器回波通過(guò)循環(huán)閾值聚合后形成的空間子群分布態(tài)勢(shì)圖。這里設(shè)同一子群中兩個(gè)量測(cè)點(diǎn)判為一個(gè)子群的最大距離為230 m，不但目標(biāo)點(diǎn)聚合成為子群，而且距離較近的雜波點(diǎn)也聚合成了子群，分布分散的雜波點(diǎn)跡得到了消除。

圖6對(duì)聚合后的子群代入K-均值聚類法，形成各個(gè)子群的中心。圖中前3個(gè)時(shí)刻形成的航跡已經(jīng)比較清晰，雜波子群中心間的距離都遠(yuǎn)遠(yuǎn)大于目標(biāo)以最大速度在采樣間隔間的運(yùn)行距離，所以通過(guò)中心外推法又進(jìn)一步去除了雜波子群。

圖7對(duì)互聯(lián)上的前3時(shí)刻子群中心點(diǎn)變換到參數(shù)空間中去，6條曲線相交于兩個(gè)點(diǎn)，每個(gè)交點(diǎn)的3條曲線分別代表3個(gè)時(shí)刻的互聯(lián)中心點(diǎn)在參數(shù)空間的分布，很明顯兩個(gè)編隊(duì)航跡起始成功。

圖8所示為兩個(gè)編隊(duì)的航跡起始圖，從圖中可以看出，同一編隊(duì)中的目標(biāo)量測(cè)點(diǎn)跡相互交叉，沒(méi)有固定的相對(duì)位置。該航跡起始過(guò)程可以滿足編隊(duì)起始的需要，能夠較精確的完成編隊(duì)目標(biāo)的起始。

由以上分析，K-均值聚類算法與Hough變換的相互結(jié)合給編隊(duì)目標(biāo)航跡起始和目標(biāo)跟蹤提出了新的思想。前者通過(guò)聚類更加準(zhǔn)確的求出了子群的中心，為后者Hough變換準(zhǔn)確判斷子群中心點(diǎn)是否在一條直線上提供了更好的條件?？偟膩?lái)說(shuō)，該方法思路清晰，計(jì)算量較小，去除雜波能力強(qiáng)，航跡起始率高。

6 結(jié)束語(yǔ)

本文提出了一種編隊(duì)目標(biāo)航跡起始算法,用于密集雜波環(huán)境下編隊(duì)目標(biāo)航跡起始分析。

該算法將聚類算法和Hough變換思想引入到編隊(duì)目標(biāo)航跡起始模型中，本文算法不僅能在密集雜波環(huán)境下對(duì)目標(biāo)有效航跡起始，而且航跡起始時(shí)間短，航跡起始成功率高，節(jié)省了雷達(dá)資源，滿足了現(xiàn)代戰(zhàn)場(chǎng)環(huán)境下的戰(zhàn)爭(zhēng)需要。

但同時(shí)，當(dāng)一個(gè)編隊(duì)中目標(biāo)成員個(gè)數(shù)較少時(shí)，特別是在雜波特別密集時(shí)，雜波和目標(biāo)形成的聚類就會(huì)對(duì)子群中心的求取產(chǎn)生較大的影響，Hough變換的效果和正確率還有待于進(jìn)一步提高。因此，如何降低雜波對(duì)稀疏編隊(duì)航跡起始的影響，是下一步工作的重點(diǎn)。

[1]潘泉,梁彥,楊峰,等.現(xiàn)代目標(biāo)跟蹤與信息融合[M].北京∶國(guó)防工業(yè)出版社,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]何友,修建娟,張晶煒.雷達(dá)數(shù)據(jù)處理及應(yīng)用[M].2版.北京∶電子工業(yè)出版社,2009∶184-185.

[5]金術(shù)玲,梁彥,王曾福,等.兩級(jí)Hough變換航跡起始算法[J].電子學(xué)報(bào),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]時(shí)銀水,姬紅兵,湯金平.對(duì)斷續(xù)點(diǎn)跡的速度模糊聚類航跡起始研究[J].儀器儀表學(xué)報(bào),2009,10(30)∶38-42.

[8]耿文東.編隊(duì)目標(biāo)跟蹤綜述[C]//第十屆全國(guó)雷達(dá)學(xué)術(shù)年會(huì).北京∶國(guó)防工業(yè)出版社,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].李晶皎,王愛(ài)俠,張廣淵,譯.北京∶電子工業(yè)出版社,2006∶317-318,410-412.

[11]蔡慧,劉洪波,韓國(guó)棟.基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(5)∶1089-1090.

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