基于點對局部拓撲和加權二分圖的地面目標關聯

夏 濤，吉琳娜，劉 哲，楊風暴

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

0 引言

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

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

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

1 形狀描述算子與加權二分圖

1.1 形狀描述算子

1.1.1 點對全局拓撲

(1)

(2)

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

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

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

1.1.2 點對局部拓撲

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

1.2 加權二分圖

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

2 基于PPLT-WBGM的地面目標關聯方法

為了提升算法的抗噪性能和魯棒性，本文提出基于PPLT-WBGM的地面目標關聯方法，首先構建點對局部拓撲特征，使用特定的點代替全局拓撲特征中的質心，并采用歐式距離代替對數距離進行均勻量化，降低了對噪聲的敏感性和算法復雜度；其次計算不同點集中點對之間的相似度，得到相似度矩陣；最后建立加權二分圖，將該點模式匹配問題轉化為在加權二分圖中尋找最大權完備匹配的問題，并使用Kuhn-Munkres算法進行最佳匹配求解，實現地面目標關聯。具體流程如圖3所示。

圖3 基于PPLT-WBGM的地面目標關聯方法流程圖Fig.3 Flow chart of ground target association method based on PPLT-WBGM

2.1 點對局部拓撲特征構建

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

(3)

(4)

(5)

(6)

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

2.2 實現最佳匹配

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

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

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

3 實驗與分析

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

圖5 目標位置示意圖Fig.5 Diagram of target positions

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

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

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

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

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

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

表4 Eg=1 km且漏檢一個目標時的正確匹配率比較Tab.4 Comparison of matching accuracy with Eg=1 km and missed one target

圖6 關聯正確率比較Fig.6 Correlation accuracy comparison

4 結論

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