基于點對局部拓撲和加權(quán)二分圖的地面目標(biāo)關(guān)聯(lián)

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

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

0 引言

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

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

綜上所述，大多基于位置信息的目標(biāo)關(guān)聯(lián)算法都存在局限性，制約了關(guān)聯(lián)正確率的提高。基于全局拓撲特征的關(guān)聯(lián)方法魯棒性好，但當(dāng)點集中點的位置包含較多噪聲時關(guān)聯(lián)正確率下降。為此，本文提出基于PPLT-WBGM的地面目標(biāo)關(guān)聯(lián)方法。

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

1.1 形狀描述算子

1.1.1 點對全局拓撲

(1)

(2)

圖1(a)和圖1(b)分別為全局拓撲特征的構(gòu)造方法和全局拓撲特征描述算子。該方法具體如下：計算點集S中任意兩點之間的歐氏距離，在所有的歐式距離中選出中值作為半徑，得到點si的鄰域，并計算該鄰域的質(zhì)心msi。以si為原點，畫出五個同心圓，向量simsi作為極徑，按照離原點的對數(shù)距離logρ依次量化為{1，2，3，4，5}五個整數(shù)值，角度按照逆時針方向依次均勻量化為{0，1，2，3，…，11}十二個整數(shù)值，整個鄰域空間按對數(shù)極坐標(biāo)劃分為60個部分。

圖1 全局拓撲特征描述算子Fig.1 Global topological characteristic descriptor

全局拓撲特征方法對于平移、旋轉(zhuǎn)等剛性變換甚至微小的非剛性變換具有較強的魯棒性[10]；但是，當(dāng)點集中點的位置包含較多噪聲時，此方法的魯棒性惡化比較明顯。第一，由于點si的鄰域在全局拓撲特征上在直角坐標(biāo)系下是非均勻量化的，距離原點si越近的鄰近點對噪聲越敏感，尤其是角度量化時，靠近原點si的鄰近點更容易偏離到其他區(qū)域甚至是相反的區(qū)域；第二，因為鄰域的質(zhì)心被選定為參考點，當(dāng)點集中出現(xiàn)較多異常值時，參考點的位置與真實位置相比誤差較大。

1.1.2 點對局部拓撲

圖2 點對局部拓撲特征描述算子Fig.2 Point pair local topological characteristic descriptor

1.2 加權(quán)二分圖

二分圖又稱為二部圖，是圖論中的一種特殊模型。設(shè)G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，其中，兩點之間的連線表示G的邊，并且圖中的每條邊(i,j)所關(guān)聯(lián)的兩個頂點分別屬于這兩個不同的頂點集A和B，則稱圖G為一個二分圖。設(shè)ai,bj(i,j=1,2,…,n)分別是頂點集A、B中的點，給連接兩頂點的邊上賦予相應(yīng)的權(quán)值wij，其數(shù)值大小在0到1之間，且每個點只能選擇一次。由圖G中一些不相鄰的邊組成的集合M稱為G的一個匹配。圖G的含邊數(shù)最多的匹配稱為G的最大匹配。設(shè)l是賦權(quán)二部圖G的一個可行頂點標(biā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)建點對局部拓撲特征，使用特定的點代替全局拓撲特征中的質(zhì)心，并采用歐式距離代替對數(shù)距離進行均勻量化，降低了對噪聲的敏感性和算法復(fù)雜度；其次計算不同點集中點對之間的相似度，得到相似度矩陣；最后建立加權(quán)二分圖，將該點模式匹配問題轉(zhuǎn)化為在加權(quán)二分圖中尋找最大權(quán)完備匹配的問題，并使用Kuhn-Munkres算法進行最佳匹配求解，實現(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 點對局部拓撲特征構(gòu)建

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

(3)

(4)

(5)

(6)

對得到的拓撲特征的相似度矩陣,為了使鄰域A和B中的點相互匹配，需要給出一定的規(guī)則尋找最佳匹配[12]，也即實現(xiàn)目標(biāo)關(guān)聯(lián)正確率最高。

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

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

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

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

3 實驗與分析

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

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

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

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

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

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

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

表4 Eg=1 km且漏檢一個目標(biāo)時的正確匹配率比較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é)論

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