基于最近鄰-拓撲圖的異類傳感器目標關聯算法

袁定波*① 孟藏珍①② 許 稼① 彭應寧①

?

基于最近鄰-拓撲圖的異類傳感器目標關聯算法

袁定波孟藏珍許 稼彭應寧

(清華大學電子工程系 北京 100084)(中國人民解放軍空軍預警學院 武漢 430019)

針對雷達和高動態平臺上的紅外傳感器構成的異類傳感器信息融合系統中的目標關聯問題，該文提出了一種基于最近鄰-拓撲圖的目標關聯算法。該算法避免了系統誤差補償環節，有效地克服了最近鄰方法對系統偏差敏感和拓撲圖方法運算量大的不足，顯著提高了存在系統誤差條件下的關聯成功率，且具有很強的穩健性。數值實驗結果表明了該方法的有效性，目標關聯正確率在90%以上。

數據融合；目標關聯；拓撲相似性；最近鄰算法；拓撲圖法

1 引言

隨著現代傳感器技術和信息處理技術等領域的日新月異的快速發展，異類傳感器之間的多源信息融合逐步體現出巨大的需求[1]。例如，目前常用的雷達和紅外異類傳感器組合[2]可為復雜電磁環境中目標跟蹤提供解決思路。

目標關聯問題是多源異類傳感器信息融合的關鍵步驟。在對紅外數據和雷達數據分別進行濾波和時空配準后，將雷達和紅外數據轉化到了同一個觀測坐標系。由于隨機噪聲和傳感器系統偏差的影響，不同傳感器對同一個目標觀測位置可發生較大的偏離。針對同類傳感器的系統偏差，目前已提出了基于誤差估計和補償的方法。主要有實施質量控制法(Real Time Quality Control, RTQC)[3]、最小二乘法(Least Square, LS)[4]、極大似然法(Maximum Likelihood, ML)[5]、精確極大似然法(Exact Maximum Likelihood, EML)[6]等。但由于異類傳感器信息融合系統中傳感器觀測數據維度不同以及時空配準引入的復雜的非線性變換等原因，難以建立方程進行系統誤差估計和補償。圖1給出了時空配準后的目標的偏差示意圖?？梢钥闯銎钍菚r變的，且同一時刻不同目標的偏差也不一致。這為目標關聯提出了很大的挑戰。傳統的目標關聯算法如匈牙利算法[7、拍賣算法[9]、蟻群算法[10]、最近鄰算法[11]等由于沒有充分考慮系統誤差的影響，很難取得較好的關聯效果。例如，最近鄰(Nearest Neighbor, NN)算法計算量小，易于工程實現。但是在系統偏差存在的情況下，其關聯失配概率較大。其中，最近提出的基于多目標拓撲圖的目標關聯算法在系統偏差條件下實現數據關聯表現出了很好的特性。但是，拓撲圖方法在目標拓撲結構發生嚴重畸變(如翻轉)的情況下失配概率大，且算法復雜度高。

圖1 目標偏差曲線

本文圍繞雷達-紅外傳感器信息融合系統，針對系統誤差難以估計補償的問題，提出了基于最近鄰-拓撲圖的異類傳感器目標關聯算法。仿真表明，新算法巧妙地避開了系統誤差補償環節，將系統誤差補償和目標關聯耦合在了一起，關聯成功概率在90%以上。同時，該算法具有較好的魯棒性，可適應目標結構的較大變形，且大大降低了運算復雜度。本文結構組織如下：第2節，第3節分別簡單介紹了最近鄰算法和拓撲圖算法的原理；第4節重點介紹最近鄰-拓撲圖目標關聯算法；第5節給出了算法的數值仿真和結果分析；第6節對本文做了一個總結和展望。

2 最近鄰算法

通常，雷達-紅外目標關聯中的NN關聯算法

流程描述如下：

步驟1 隨機選擇一個雷達目標；

步驟2 從紅外目標中選擇一個與其最近鄰的紅外目標；

步驟3 將關聯的雷達目標和紅外目標分別從數據集中移除；

步驟4 重復步驟1至步驟3，直至對每一個雷達目標完成操作，直至結束。

通常，為了保證關聯成功率，步驟1中優先選取威脅較大的目標。NN關聯算法運算量小，但其關聯成功率較低。在圖2所示的情況下，不難看出，最近鄰算法的結果是雷達目標3和紅外目標4關聯，關聯錯誤。

圖2 紅外-雷達目標圖

3 拓撲圖法

基于拓撲圖的目標關聯算法的基本思路是利用整體拓撲結構信息進行關聯。其主要流程可描述如下：

步驟2 從個雷達目標中任意選取3個構成三角形；這樣的三角形構成的集合共有個元素；

步驟3 從個紅外目標中任意選取3個構成三角形；這樣的三角形構成的集合共有個元素；

步驟4 對于步驟2中的每一個三角形，按照式(1)中的定義，從步驟3中找出與其相似度最大的三角形并記下對應的頂點和相似度；

步驟5 綜合步驟3、步驟4得出使得整體相似度最大的關聯序列。

該算法有一定的局限性和缺點。式(1)所描述的相似度公式并不能判斷三角形是否翻轉，如圖3所示。

圖3 紅外-雷達拓撲圖

實際應用中當目標相對位置翻轉時，算法失效。同時，算法中步驟2至步驟4要完成個相似度計算，算法復雜度高。

4 基于最近鄰-拓撲圖的目標關聯算法

NN關聯算法運算量小但是失配概率較大，而單純的基于拓撲圖的算法在拓撲結構畸變嚴重的情況下失配概率較大且運算量較大。為此，基于以上兩點，我們提出基于最近鄰-拓撲圖的目標關聯算法。

4.1三角形拓撲相似度

該算法中拓撲相似度的判定依然以三角形為依托。為了判定拓撲結構是否翻轉，定義如下規則：

(3)

(4)

4.2最近鄰-拓撲圖目標關聯

基于最近鄰-拓撲圖的目標關聯算法流程如圖4所示。

圖4 最近鄰-拓撲圖目標關聯算法流程

對于雷達目標集合中的每一個目標，都減去幾何形心偏差，得到新的雷達目標集合為

(7)

(9)

(11)

步驟6 對于步驟5中得到的相似度矩陣，利用匈牙利指派算法或者JV最短路徑擴張算法，求得使整體匹配度最高的匹配序列，完成雷達目標和紅外目標的匹配。

5 算法仿真及結果分析

5.1仿真數據

仿真數據設置了兩個場景共計12個樣本。其中場景1中設置4個紅外目標，4個雷達目標，每個目標包含52點數據，方位角偏差在～之間緩變，俯仰角偏差在～之間緩變；場景2中設置4個紅外目標，8個雷達目標，每個目標包含85點數據，方位角偏差在～之間緩變，俯仰角偏差在～之間緩變。

5.2 仿真結果及分析

我們分別對兩個場景的6個樣本進行仿真，得到兩個場景的關聯成功概率如表1和表2所示。

表1最近鄰-拓撲圖算法仿真結果(場景1)

場景-樣本主目標關聯成功率(%)從目標1關聯成功率(%)從目標2關聯成功率(%)從目標3關聯成功率(%) 1-1100100100100 1-2100100100100 1-3100100100100 1-4100100100100 1-510096.1510096.15 1-610098.0810098.08

場景-樣本紅外主目標關聯成功率(%)紅外從目標1關聯成功率(%)紅外從目標2關聯成功率(%)紅外從目標關聯成功率(%) 2-193909694 2-291908887 2-392767285 2-497858590 2-596859095 2-686717667

從表1，表2可以看出，本文算法將系統偏差補償和目標關聯有機地耦合在一起，受系統偏差影響較小，關聯性能較高。

對于場景2的數據也利用最近鄰算法進行了仿真，其結果如表3所示。通過表2、表3對比看出，由于系統偏差的影響，最近鄰算法性能極差。而新算法對系統偏差不敏感，性能較好。

表3最近鄰算法仿真結果(場景2)

場景-樣本紅外主目標關聯成功率(%)紅外從目標1關聯成功率(%)紅外從目標2關聯成功率(%)紅外從目標關聯成功率(%) 2-1484980 2-2431980 2-35621000 2-4672940 2-5514980 2-6596921

下面我們來分析雷達目標數對主目標關聯成功率的影響。設定紅外目標數=4時，得到主目標關聯成功概率與雷達目標數的關系曲線如圖5所示。從圖中我們可以看出，隨著雷達目標數目增多，主目標關聯成功概率下降。這是由于雷達數量越大，拓撲結構越復雜，出錯概率越大。同時我們可以看出，當雷達目標數目小于9時，關聯成功率在95%以上；當雷達目標數小于12時，關聯成功率在91%以上。

同時，由于在最近鄰-拓撲圖算法中涉及了鄰域半徑。我們分析鄰域半徑大小對主目標關聯成功率和算法復雜度的影響得到曲線如圖6所示?？梢钥闯?，鄰域半徑越小，算法復雜度越小，但同時會犧牲一定的算法精度。當鄰域半徑超過一定范圍，關聯成功率不再隨鄰域半徑變換。鄰域半徑的大小選取反映了拓撲圖的畸變程度，綜合算法精度和時間的考慮，我們選取鄰域半徑為。

圖5 雷達目標數對主目標關聯成功率的影響

圖6 鄰域半徑對算法影響

最后，在此簡要分析該算法的時間復雜度。假設雷達和紅外目標個數分別為和，則步驟1共需要完成2次均值運算和次減法運算；步驟2～步驟4共需要進行次拓撲相似度計算；步驟6需要對的矩陣尋優。故整體時間復雜度為量級。而拓撲圖法要完成次拓撲相似度的計算，即次歐氏距離的計算，同時要完成的矩陣尋優。故其時間復雜度為量級。當取值較大時，后者算法復雜度遠遠大于前者。

本文算法有一定的適用范圍。當傳感器出現大量的虛警和漏報時，整個拓撲結構發生嚴重的冗余或者缺失時，基于最近鄰-拓撲圖的目標關聯算法性能下降。

6 結束語

本文通過對異類傳感器目標關聯算法的深入研究，針對同一時刻系統誤差對各目標大小不一且系統誤差難以實時估計補償的情況，提出了基于最近鄰-拓撲圖的目標關聯算法。新算法巧妙地避免了系統誤差對目標關聯的影響，很好地解決了異類傳感器目標關聯成功概率較低的問題，且大大地降低了算法的復雜度。仿真實驗表明新方法的目標關聯成功概率在90%以上，有利于工程實現和軍事應用。但同時本文算法還有待改進的地方，比如算法中鄰域半徑的選擇如何做到自適應是下一步值得研究的地方。

[1] 郜麗鵬, 葉方, 司錫才, 等. 基于雷達、紅外的數據融合算法研究[J]. 信息技術, 2005, 29(5): 8-10, 67.

Gao Li-peng, Ye Fang, Si Xi-cai,.. Study on data fusion algorithm of radar and IRI[J]., 2005, 29(5): 8-10, 67.

[2] 尹繼豪, 崔炳喆. 雷達/紅外數據融合的機動目標跟蹤算法綜述[J]. 航空兵器, 2009, (5): 39-43.

Yin Ji-hao and Cui Bing-zhe. Radar/IR data fusion algorithm for maneuvering target tracking[J]., 2009, (5): 39-43.

[3] 董云龍, 何友, 王國宏, 等. 一種改進的系統偏差估計算法[J].宇航學報, 2005, 26(6): 737-742.

Dong Yun-long, He You, Wang Guo-hong,.. One modified algorithms to estimate system errors[J]., 2005, 26(6): 737-742.

[4] 吳澤民, 任姝婕. 雷達時差和系統誤差的聯合估計方法[J]. 兵工學報, 2011, 32(7): 847-852.

Wu Ze-min and Ren Shu-jie. Joint estimation for time offset and radar system error[J]., 2011, 32(7): 847-852.

[5] 宋強, 何友, 熊偉, 等. 基于極大似然的單傳感器誤差配準算法[J]. 宇航學報, 2011, 32(8): 1826-1832.

Song Qiang, He You, Xiong Wei,.. A maximum likelihood-based single sensor bias registration algorithm[J]., 2011, 32(8): 1826-1832.

[6] 豐昌政, 薛強. 雷達組網的精確極大似然誤差配準算法[J]. 兵工自動化, 2012, 31(2): 5-8.

Feng Chang-zheng and Xue Qiang. An exact maximum likelihood error registration algorithm for radar network[J]., 2012, 31(2): 5-8.

[7] 宋業新, 陳綿云, 張曙紅, 等. 兩類多目標廣義指派問題的有效算法及其應用[J]. 華中科技大學學報(自然科學版), 2001, 29(1): 70-72.

Song Ye-xin, Chen Mian-yun, Zhang Shu-hong,.. An efficient algorithm for solving two multi-object generalized assignment problems and its application[J]., 2001, 29(1): 70-72.

[8] Gottschalk T D. Concurrent implementation of Munkres algorithm[C]. Proceedings of the Fifth Distributed Memory Computing Conference, 1990, Apr. 8-12, 1990: 52-57.

[9] 柳鵬, 高杰, 劉揚, 等. 基于拍賣算法的目標分配問題優化[J].兵工自動化, 2008, 27(9): 22-24.

Liu Peng, Gao Jie, and Liu Yang. Target distribution optimization based on auction algorithm[J]., 2008, 27(9): 22-24.

[10] 黃樹采, 李為民, 李威, 等. 多傳感器管理的目標分配問題蟻群算法研究[J]. 空軍工程大學學報(自然科學版), 2005, 6(2): 28-31.

Huang Shu-cai, Li Wei-min, Li Wei,.. Multisensor management with ant colony algorithm for solving target assignment problem[J].(), 2005, 6(2): 28-31.

[11] 田宏偉, 敬忠良, 胡士強, 等. 基于多速率運動模型的多幀最近鄰數據關聯算法[J]. 上海交通大學學報, 2005, 39(3): 413-416.

Tian Hong-wei, Jing Zhong-liang, Hu Shi-qiang,.. Multiple scan nearest-neighbor data association algorithm based on multirate kinematic model[J]., 2005, 39(3): 413-416.

[12] 楊哲, 韓崇昭, 李晨, 等. 基于目標之間拓撲信息的數據關聯方法[J]. 系統仿真學報, 2008, 20(9): 2357-2360.

Yang Zhe, Han Chong-zhao, Li Chen,.. Data association based on target topology[J]., 2008, 20(9): 2357-2360.

[13] Kadar I, Eadan E, and Gassner R. Comparison of robust assignment algorithms[C]. In: Kadar I, Signal Processing, Sensor Fusion, and Target Recognition VI, SPIE Conference Proceedings, Orlando, FL, USA, April 21, 1997, 3068: 240-249.

[14] 韓紅, 韓崇昭, 朱洪艷, 等. 基于FCM的多傳感器融合多目標跟蹤的數據關聯[J]. 系統仿真學報, 2004, 16(9): 2096-2099.

Han Hong, Han Chong-zhao, Zhu Hong-yan,.. Multi-sensor fusion multi-target tracking data association based on FCM[J]., 2004, 16(9): 2096-2099.

[15] 石玥, 王鉞, 王樹剛, 等. 基于目標參照拓撲的模糊航跡關聯方法[J]. 國防科技大學學報, 2006, 28(4): 105-109.

Shi Yue, Wang Yue, Wang Shu-gang,.. Fuzzy data association based on target topology of reference[J]. Journal of National University of Defense Technology, 2006, 28(4): 105-109.

[16] Jonker R and Volgenant A. A shortest augmenting path algorithm for dense and sparse linear assignment problems[J]., 1987, 38(4): 325–340.

Target Association of Heterogeneous Sensors Based on Nearest-neighbor and Topology

Yuan Ding-boMeng Cang-zhenXu JiaPeng Ying-ning

(Department of Electronic Engineering, Tsinghua University, Beijing 100084, China)(The Chinese People’s Liberation Army Air Force Warning Institute, Wuhan 430019, China)

A new data association algorithm is proposed in this paper for heterogeneous sensors information fusion system, which consists of Radar and high-dynamic-range IR, based on joint usage of the nearest-neighbor (NN) and the topology similarity. The proposed algorithm can avoid the complicated system biases compensation based on topology information. Because the NN method is sensitive to the system bias while the existing topology-based algorithms need a large amount of computation, the proposed algorithm shows a lot of advantages, like high estimation accuracy and robustness as well as the improvement of success association rate. Finally, some numerical experiments are provided to demonstrate the effectiveness of the proposed method. And the estimation accuracy can be as high as 90%.

Data fusion; Target association; Topology similarity; Nearest-Neighbor (NN) algorithm; Topology

TN957

A

2095-283X(2012)04-0393-06

10.3724/SP.J.1300.2012.20083

袁定波(1990-)，男，碩士研究生，清華大學電子工程系，主要從事衛星導航等研究。 E-mail: ydb12@mails.tsinghua.edu.cn

孟藏珍(1978-)，男，博士生，清華大學電子工程系。主要從事雷達信號與數據處理等方面的研究。 E-mail: mcz-zzhp@sina.com

許 稼(1974-)，男，博士，教授，北京理工大學信息與電子學院。主要從事雷達信號檢測與處理、數據融合處理、SAR成像等方面研究。E-mail: xujia@tsinghua.edu.cn

彭應寧，男，教授，清華大學電子工程系。E-mail: ynpeng@tsinghua.edu.cn

2012-11-16收到，2012-12-14改回；2012-12-19網絡優先出版

國家自然科學基金(61102168)資助課題

袁定波 ydb12@mails.tsinghua.edu.cn