夏 濤，吉琳娜，劉 哲，楊風(fēng)暴

(中北大學(xué)信息與通信工程學(xué)院，山西 太原 030051)

0 引言

隨著各種探測(cè)技術(shù)的迅速發(fā)展，偵察設(shè)備所獲取的關(guān)于地面目標(biāo)的信息量急劇增加，信息來源也更加豐富。如何挖掘信息背后隱藏的關(guān)系，把相應(yīng)的觀測(cè)信息與同一目標(biāo)進(jìn)行匹配，是當(dāng)前偵察領(lǐng)域非常關(guān)心的一個(gè)問題。地面目標(biāo)關(guān)聯(lián)可以利用異類傳感器的觀測(cè)序列中獲取的地面目標(biāo)的量測(cè)信息，將不同傳感器獲取的同一目標(biāo)的信息進(jìn)行匹配，實(shí)際上解決的是一個(gè)異類傳感器目標(biāo)配對(duì)的問題[1]。

國(guó)內(nèi)外學(xué)者對(duì)關(guān)聯(lián)算法進(jìn)行了大量的研究，已發(fā)展為應(yīng)用于多領(lǐng)域的重要技術(shù)。文獻(xiàn)[2]在使用目標(biāo)位置信息進(jìn)行關(guān)聯(lián)匹配時(shí)，要引入目標(biāo)的屬性特征對(duì)基于位置信息的粗關(guān)聯(lián)結(jié)果進(jìn)行修正，但這類算法一般復(fù)雜度高，且通常難以建立相對(duì)完備的目標(biāo)特征數(shù)據(jù)庫。而基于位置信息的目標(biāo)關(guān)聯(lián)方法是目前比較成熟的關(guān)聯(lián)方法，其大致分為兩類：一是基于目標(biāo)運(yùn)動(dòng)狀態(tài)信息的方法；二是基于點(diǎn)模式匹配的方法。經(jīng)典的目標(biāo)關(guān)聯(lián)方法有最近鄰算法(NN)[3]、概率數(shù)據(jù)關(guān)聯(lián)算法(PDA)[4]、聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)算法(JPDA)[5]、多假設(shè)跟蹤方法(MHT)[6]等。這些算法一般都是利用目標(biāo)的運(yùn)動(dòng)狀態(tài)信息，通過傳感器不同時(shí)刻獲取的目標(biāo)狀態(tài)信息進(jìn)行關(guān)聯(lián)；但由于地面背景復(fù)雜、易受雜波干擾，地面目標(biāo)具有強(qiáng)機(jī)動(dòng)性，要求觀測(cè)信息時(shí)間分辨率高等因素，往往難以建立有效的運(yùn)動(dòng)模型估計(jì)和預(yù)測(cè)目標(biāo)的真實(shí)軌跡，極大地影響了關(guān)聯(lián)正確率。迭代最近點(diǎn)(ICP)[7]算法是應(yīng)用最廣泛的點(diǎn)模式匹配算法之一，因?yàn)樗鼘?shí)現(xiàn)簡(jiǎn)單，計(jì)算復(fù)雜度低；然而，ICP算法需要滿足一定的要求，即兩個(gè)點(diǎn)集的初始位置應(yīng)當(dāng)保持較小的距離，在實(shí)際中并非總是如此。文獻(xiàn)[8]使用了形狀上下文(SC)，該算法比ICP算法具有更強(qiáng)的魯棒性，但其也有明顯的局限性，即一個(gè)形狀中的鄰近點(diǎn)對(duì)可能與另一個(gè)形狀中相距較遠(yuǎn)的兩個(gè)點(diǎn)匹配。

綜上所述，大多基于位置信息的目標(biāo)關(guān)聯(lián)算法都存在局限性，制約了關(guān)聯(lián)正確率的提高?；谌滞?fù)涮卣鞯年P(guān)聯(lián)方法魯棒性好，但當(dāng)點(diǎn)集中點(diǎn)的位置包含較多噪聲時(shí)關(guān)聯(lián)正確率下降。為此，本文提出基于PPLT-WBGM的地面目標(biāo)關(guān)聯(lián)方法。

1 形狀描述算子與加權(quán)二分圖

1.1 形狀描述算子

1.1.1 點(diǎn)對(duì)全局拓?fù)?/p>

(1)

(2)

圖1(a)和圖1(b)分別為全局拓?fù)涮卣鞯臉?gòu)造方法和全局拓?fù)涮卣髅枋鏊阕印Ｔ摲椒ň唧w如下：計(jì)算點(diǎn)集S中任意兩點(diǎn)之間的歐氏距離，在所有的歐式距離中選出中值作為半徑，得到點(diǎn)si的鄰域，并計(jì)算該鄰域的質(zhì)心msi。以si為原點(diǎn)，畫出五個(gè)同心圓，向量simsi作為極徑，按照離原點(diǎn)的對(duì)數(shù)距離logρ依次量化為{1，2，3，4，5}五個(gè)整數(shù)值，角度按照逆時(shí)針方向依次均勻量化為{0，1，2，3，…，11}十二個(gè)整數(shù)值，整個(gè)鄰域空間按對(duì)數(shù)極坐標(biāo)劃分為60個(gè)部分。

圖1 全局拓?fù)涮卣髅枋鏊阕覨ig.1 Global topological characteristic descriptor

全局拓?fù)涮卣鞣椒▽?duì)于平移、旋轉(zhuǎn)等剛性變換甚至微小的非剛性變換具有較強(qiáng)的魯棒性[10]；但是，當(dāng)點(diǎn)集中點(diǎn)的位置包含較多噪聲時(shí)，此方法的魯棒性惡化比較明顯。第一，由于點(diǎn)si的鄰域在全局拓?fù)涮卣魃显谥苯亲鴺?biāo)系下是非均勻量化的，距離原點(diǎn)si越近的鄰近點(diǎn)對(duì)噪聲越敏感，尤其是角度量化時(shí)，靠近原點(diǎn)si的鄰近點(diǎn)更容易偏離到其他區(qū)域甚至是相反的區(qū)域；第二，因?yàn)猷徲虻馁|(zhì)心被選定為參考點(diǎn)，當(dāng)點(diǎn)集中出現(xiàn)較多異常值時(shí)，參考點(diǎn)的位置與真實(shí)位置相比誤差較大。

1.1.2 點(diǎn)對(duì)局部拓?fù)?/p>

圖2 點(diǎn)對(duì)局部拓?fù)涮卣髅枋鏊阕覨ig.2 Point pair local topological characteristic descriptor

1.2 加權(quán)二分圖

二分圖又稱為二部圖，是圖論中的一種特殊模型。設(shè)G=(V,E)是一個(gè)無向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集(A,B)，其中，兩點(diǎn)之間的連線表示G的邊，并且圖中的每條邊(i,j)所關(guān)聯(lián)的兩個(gè)頂點(diǎn)分別屬于這兩個(gè)不同的頂點(diǎn)集A和B，則稱圖G為一個(gè)二分圖。設(shè)ai,bj(i,j=1,2,…,n)分別是頂點(diǎn)集A、B中的點(diǎn)，給連接兩頂點(diǎn)的邊上賦予相應(yīng)的權(quán)值wij，其數(shù)值大小在0到1之間，且每個(gè)點(diǎn)只能選擇一次。由圖G中一些不相鄰的邊組成的集合M稱為G的一個(gè)匹配。圖G的含邊數(shù)最多的匹配稱為G的最大匹配。設(shè)l是賦權(quán)二部圖G的一個(gè)可行頂點(diǎn)標(biāo)號(hào)，若相等子圖Gl有完美匹配M′，則M′是G的最大權(quán)完美匹配。

2 基于PPLT-WBGM的地面目標(biāo)關(guān)聯(lián)方法

為了提升算法的抗噪性能和魯棒性，本文提出基于PPLT-WBGM的地面目標(biāo)關(guān)聯(lián)方法，首先構(gòu)建點(diǎn)對(duì)局部拓?fù)涮卣?，使用特定的點(diǎn)代替全局拓?fù)涮卣髦械馁|(zhì)心，并采用歐式距離代替對(duì)數(shù)距離進(jìn)行均勻量化，降低了對(duì)噪聲的敏感性和算法復(fù)雜度；其次計(jì)算不同點(diǎn)集中點(diǎn)對(duì)之間的相似度，得到相似度矩陣；最后建立加權(quán)二分圖，將該點(diǎn)模式匹配問題轉(zhuǎn)化為在加權(quán)二分圖中尋找最大權(quán)完備匹配的問題，并使用Kuhn-Munkres算法進(jìn)行最佳匹配求解，實(shí)現(xiàn)地面目標(biāo)關(guān)聯(lián)。具體流程如圖3所示。

圖3 基于PPLT-WBGM的地面目標(biāo)關(guān)聯(lián)方法流程圖Fig.3 Flow chart of ground target association method based on PPLT-WBGM

2.1 點(diǎn)對(duì)局部拓?fù)涮卣鳂?gòu)建

Smim,jn=(1-λ)SoDim,jn+λSoAim,jn

(3)

(4)

(5)

(6)

對(duì)得到的拓?fù)涮卣鞯南嗨贫染仃?為了使鄰域A和B中的點(diǎn)相互匹配，需要給出一定的規(guī)則尋找最佳匹配[12]，也即實(shí)現(xiàn)目標(biāo)關(guān)聯(lián)正確率最高。

2.2 實(shí)現(xiàn)最佳匹配

目標(biāo)關(guān)聯(lián)的本質(zhì)就是在目標(biāo)檢測(cè)的基礎(chǔ)上尋找最優(yōu)的關(guān)聯(lián)目標(biāo)對(duì)[13]。若不同的觀測(cè)信息都來源于同一個(gè)目標(biāo)，那么這些觀測(cè)信息之間的相似度必然較大。因此，結(jié)合二分圖定義，基于點(diǎn)模式匹配的目標(biāo)關(guān)聯(lián)過程就可以映射為加權(quán)二分圖匹配過程[14]，并通過某些算法實(shí)現(xiàn)最佳匹配。而完成最佳匹配，只需在相似度矩陣SM中尋找一組不在同一行或同一列的元素，使得該組元素和最大，即全局相似度最大。相似度矩陣SM可以用二分圖G來表示，傳感器a和b檢測(cè)到的目標(biāo)集A和B作為二分圖不同的頂點(diǎn)集，相似度矩陣中的元素Smim,jn可以用頂點(diǎn)之間被賦予權(quán)重的邊來表示，如圖4所示。尋找每個(gè)am與某個(gè)bn的匹配，使得權(quán)重和最大，則完成了最佳匹配，如圖4中實(shí)線所示。

圖4 相似度矩陣的加權(quán)二分圖Fig.4 Weighted bipartite graph of similarity matrix

常見的匹配算法有貪心算法、匈牙利算法等。貪心算法思想簡(jiǎn)單明了，但求解時(shí)不從整體最優(yōu)上加以考慮，所得到的僅是在某種意義上的局部最優(yōu)選擇，因此不適合二分圖最佳匹配。而Kuhn-Munkres算法不僅十分適合求解加權(quán)二分圖匹配問題，與枚舉法相比，其計(jì)算復(fù)雜度也大大下降。Kuhn-Munkres算法基本思想為首先給出加權(quán)二部圖G的任意一個(gè)可行頂點(diǎn)標(biāo)號(hào)，然后決定相等子圖G，在Gl中執(zhí)行匈牙利算法。根據(jù)最大權(quán)完美匹配定義可知，若在Gl中找到完美匹配，它就是G的最大權(quán)完美匹配。

3 實(shí)驗(yàn)與分析

假定地面某車輛群中有9個(gè)車輛目標(biāo)，其真實(shí)位置坐標(biāo)分別為[0,100]km內(nèi)隨機(jī)生成的數(shù)據(jù)，目標(biāo)分布如圖5中正方形所示。由于傳感器的定位誤差受到噪聲干擾等因素，傳感器a和傳感器b得到的位置信息均有一定的誤差，把兩者的總誤差分別記為Eg和Ee，并設(shè)定Eg和Ee分別服從零均值高斯分布N(0,σg)和N(0,σe)。在目標(biāo)點(diǎn)集的真實(shí)位置上添加均值為零和方差分別為Eg和Ee的噪聲，得到傳感器a和b的目標(biāo)點(diǎn)集，如圖5中“*”和“o”所示。

圖5 目標(biāo)位置示意圖Fig.5 Diagram of target positions

傳感器a總誤差中σg有兩種可能取值：{0.2，1} km，而傳感器b總誤差中σe有三種可能取值：{4，7，10} km。為了驗(yàn)證本文方法的有效性，針對(duì)無目標(biāo)漏檢和有目標(biāo)漏檢兩種情況下的場(chǎng)景分別進(jìn)行四組仿真實(shí)驗(yàn)，并與最近鄰方法(NN)和重心坐標(biāo)匹配算法(BCM)進(jìn)行了對(duì)比，每組實(shí)驗(yàn)進(jìn)行蒙特卡羅仿真1 000次，實(shí)驗(yàn)結(jié)果如表1—表4所示。

表1 Eg=0.2 km且無目標(biāo)漏檢時(shí)的正確匹配率比較Tab.1 Comparison of matching accuracy with Eg=0.2 km and no missed target

表1和表2分別展示了傳感器a誤差中σg分別取0.2 km和1 km，且不存在目標(biāo)漏檢時(shí)不同算法的正確匹配率比較。可以明顯地觀察到，本文方法和BCM算法的正確匹配率遠(yuǎn)高于NN方法。圖6為三種算法的關(guān)聯(lián)正確率比較曲線，實(shí)線、虛線分別表示Eg取值為0.2 km和1 km。隨著傳感器的誤差不斷增大，三種方法的正確匹配率都有不同程度的下降，但本文方法性能下降幅度相對(duì)較小，如圖6(a)所示，其性能仍然優(yōu)于NN方法和BCM算法。NN方法只是將落在關(guān)聯(lián)門內(nèi)且與目標(biāo)的預(yù)測(cè)位置最鄰近的觀測(cè)點(diǎn)作為相關(guān)聯(lián)的觀測(cè)，其抗干擾能力弱，所以傳感器誤差增加時(shí)易發(fā)生關(guān)聯(lián)錯(cuò)誤。而對(duì)于BCM算法來說，傳感器的誤差增加，目標(biāo)群的重心位置與實(shí)際位置偏差較大，導(dǎo)致其正確匹配率大幅下降。

表2 Eg=1 km且無目標(biāo)漏檢時(shí)的正確匹配率比較Tab.2 Comparison of matching accuracy with Eg=1 km and no missed target

為了模擬真實(shí)環(huán)境中的目標(biāo)漏檢情況，在傳感器b的目標(biāo)集中隨機(jī)刪除一個(gè)目標(biāo)，實(shí)驗(yàn)結(jié)果如表3、表4所示。結(jié)合表1—表4和圖6可以發(fā)現(xiàn)，與不存在目標(biāo)漏檢時(shí)相比，目標(biāo)漏檢情況下NN方法的正確匹配率下降約5%～8%，BCM算法的正確匹配率下降約15%，而本文方法仍可以保持較高的正確匹配率。綜合以上實(shí)驗(yàn)可以得出結(jié)論：面對(duì)傳感器誤差增大、存在目標(biāo)漏檢時(shí)，本文方法的正確匹配率較高。

表3 Eg=0.2 km且漏檢一個(gè)目標(biāo)時(shí)的正確匹配率比較Tab.3 Comparison of matching accuracy with Eg=0.2 km and missed one target

表4 Eg=1 km且漏檢一個(gè)目標(biāo)時(shí)的正確匹配率比較Tab.4 Comparison of matching accuracy with Eg=1 km and missed one target

圖6 關(guān)聯(lián)正確率比較Fig.6 Correlation accuracy comparison

4 結(jié)論

本文提出一種基于點(diǎn)對(duì)局部拓?fù)浜图訖?quán)二分圖匹配的地面目標(biāo)關(guān)聯(lián)方法。該方法采用點(diǎn)對(duì)局部拓?fù)涮卣骺坍嬆繕?biāo)群中各個(gè)成員目標(biāo)之間的相對(duì)位置關(guān)系，提高了形狀描述算子的抗噪能力。根據(jù)全局相似度最大的要求，基于點(diǎn)模式匹配的目標(biāo)關(guān)聯(lián)問題可以轉(zhuǎn)化為加權(quán)二分圖匹配問題。最后構(gòu)建了加權(quán)二分圖，并通過改進(jìn)的Kuhn-Munkres算法實(shí)現(xiàn)最佳匹配。仿真實(shí)驗(yàn)表明，在位置信息存在偏差和目標(biāo)漏檢的情況下，該算法與傳統(tǒng)方法相比具有較高的關(guān)聯(lián)正確率和較強(qiáng)的魯棒性。