袁定波*① 孟藏珍①② 許 稼① 彭應(yīng)寧①
?
基于最近鄰-拓?fù)鋱D的異類傳感器目標(biāo)關(guān)聯(lián)算法
袁定波孟藏珍許 稼彭應(yīng)寧
(清華大學(xué)電子工程系 北京 100084)(中國(guó)人民解放軍空軍預(yù)警學(xué)院 武漢 430019)
針對(duì)雷達(dá)和高動(dòng)態(tài)平臺(tái)上的紅外傳感器構(gòu)成的異類傳感器信息融合系統(tǒng)中的目標(biāo)關(guān)聯(lián)問題,該文提出了一種基于最近鄰-拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法。該算法避免了系統(tǒng)誤差補(bǔ)償環(huán)節(jié),有效地克服了最近鄰方法對(duì)系統(tǒng)偏差敏感和拓?fù)鋱D方法運(yùn)算量大的不足,顯著提高了存在系統(tǒng)誤差條件下的關(guān)聯(lián)成功率,且具有很強(qiáng)的穩(wěn)健性。數(shù)值實(shí)驗(yàn)結(jié)果表明了該方法的有效性,目標(biāo)關(guān)聯(lián)正確率在90%以上。
數(shù)據(jù)融合;目標(biāo)關(guān)聯(lián);拓?fù)湎嗨菩裕蛔罱徦惴?;拓?fù)鋱D法
隨著現(xiàn)代傳感器技術(shù)和信息處理技術(shù)等領(lǐng)域的日新月異的快速發(fā)展,異類傳感器之間的多源信息融合逐步體現(xiàn)出巨大的需求[1]。例如,目前常用的雷達(dá)和紅外異類傳感器組合[2]可為復(fù)雜電磁環(huán)境中目標(biāo)跟蹤提供解決思路。
目標(biāo)關(guān)聯(lián)問題是多源異類傳感器信息融合的關(guān)鍵步驟。在對(duì)紅外數(shù)據(jù)和雷達(dá)數(shù)據(jù)分別進(jìn)行濾波和時(shí)空配準(zhǔn)后,將雷達(dá)和紅外數(shù)據(jù)轉(zhuǎn)化到了同一個(gè)觀測(cè)坐標(biāo)系。由于隨機(jī)噪聲和傳感器系統(tǒng)偏差的影響,不同傳感器對(duì)同一個(gè)目標(biāo)觀測(cè)位置可發(fā)生較大的偏離。針對(duì)同類傳感器的系統(tǒng)偏差,目前已提出了基于誤差估計(jì)和補(bǔ)償?shù)姆椒āV饕袑?shí)施質(zhì)量控制法(Real Time Quality Control, RTQC)[3]、最小二乘法(Least Square, LS)[4]、極大似然法(Maximum Likelihood, ML)[5]、精確極大似然法(Exact Maximum Likelihood, EML)[6]等。但由于異類傳感器信息融合系統(tǒng)中傳感器觀測(cè)數(shù)據(jù)維度不同以及時(shí)空配準(zhǔn)引入的復(fù)雜的非線性變換等原因,難以建立方程進(jìn)行系統(tǒng)誤差估計(jì)和補(bǔ)償。圖1給出了時(shí)空配準(zhǔn)后的目標(biāo)的偏差示意圖??梢钥闯銎钍菚r(shí)變的,且同一時(shí)刻不同目標(biāo)的偏差也不一致。這為目標(biāo)關(guān)聯(lián)提出了很大的挑戰(zhàn)。傳統(tǒng)的目標(biāo)關(guān)聯(lián)算法如匈牙利算法[7、拍賣算法[9]、蟻群算法[10]、最近鄰算法[11]等由于沒有充分考慮系統(tǒng)誤差的影響,很難取得較好的關(guān)聯(lián)效果。例如,最近鄰(Nearest Neighbor, NN)算法計(jì)算量小,易于工程實(shí)現(xiàn)。但是在系統(tǒng)偏差存在的情況下,其關(guān)聯(lián)失配概率較大。其中,最近提出的基于多目標(biāo)拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法在系統(tǒng)偏差條件下實(shí)現(xiàn)數(shù)據(jù)關(guān)聯(lián)表現(xiàn)出了很好的特性。但是,拓?fù)鋱D方法在目標(biāo)拓?fù)浣Y(jié)構(gòu)發(fā)生嚴(yán)重畸變(如翻轉(zhuǎn))的情況下失配概率大,且算法復(fù)雜度高。
圖1 目標(biāo)偏差曲線
本文圍繞雷達(dá)-紅外傳感器信息融合系統(tǒng),針對(duì)系統(tǒng)誤差難以估計(jì)補(bǔ)償?shù)膯栴},提出了基于最近鄰-拓?fù)鋱D的異類傳感器目標(biāo)關(guān)聯(lián)算法。仿真表明,新算法巧妙地避開了系統(tǒng)誤差補(bǔ)償環(huán)節(jié),將系統(tǒng)誤差補(bǔ)償和目標(biāo)關(guān)聯(lián)耦合在了一起,關(guān)聯(lián)成功概率在90%以上。同時(shí),該算法具有較好的魯棒性,可適應(yīng)目標(biāo)結(jié)構(gòu)的較大變形,且大大降低了運(yùn)算復(fù)雜度。本文結(jié)構(gòu)組織如下:第2節(jié),第3節(jié)分別簡(jiǎn)單介紹了最近鄰算法和拓?fù)鋱D算法的原理;第4節(jié)重點(diǎn)介紹最近鄰-拓?fù)鋱D目標(biāo)關(guān)聯(lián)算法;第5節(jié)給出了算法的數(shù)值仿真和結(jié)果分析;第6節(jié)對(duì)本文做了一個(gè)總結(jié)和展望。
通常,雷達(dá)-紅外目標(biāo)關(guān)聯(lián)中的NN關(guān)聯(lián)算法
流程描述如下:
步驟1 隨機(jī)選擇一個(gè)雷達(dá)目標(biāo);
步驟2 從紅外目標(biāo)中選擇一個(gè)與其最近鄰的紅外目標(biāo);
步驟3 將關(guān)聯(lián)的雷達(dá)目標(biāo)和紅外目標(biāo)分別從數(shù)據(jù)集中移除;
步驟4 重復(fù)步驟1至步驟3,直至對(duì)每一個(gè)雷達(dá)目標(biāo)完成操作,直至結(jié)束。
通常,為了保證關(guān)聯(lián)成功率,步驟1中優(yōu)先選取威脅較大的目標(biāo)。NN關(guān)聯(lián)算法運(yùn)算量小,但其關(guān)聯(lián)成功率較低。在圖2所示的情況下,不難看出,最近鄰算法的結(jié)果是雷達(dá)目標(biāo)3和紅外目標(biāo)4關(guān)聯(lián),關(guān)聯(lián)錯(cuò)誤。
圖2 紅外-雷達(dá)目標(biāo)圖
基于拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法的基本思路是利用整體拓?fù)浣Y(jié)構(gòu)信息進(jìn)行關(guān)聯(lián)。其主要流程可描述如下:
步驟2 從個(gè)雷達(dá)目標(biāo)中任意選取3個(gè)構(gòu)成三角形;這樣的三角形構(gòu)成的集合共有個(gè)元素;
步驟3 從個(gè)紅外目標(biāo)中任意選取3個(gè)構(gòu)成三角形;這樣的三角形構(gòu)成的集合共有個(gè)元素;
步驟4 對(duì)于步驟2中的每一個(gè)三角形,按照式(1)中的定義,從步驟3中找出與其相似度最大的三角形并記下對(duì)應(yīng)的頂點(diǎn)和相似度;
步驟5 綜合步驟3、步驟4得出使得整體相似度最大的關(guān)聯(lián)序列。
該算法有一定的局限性和缺點(diǎn)。式(1)所描述的相似度公式并不能判斷三角形是否翻轉(zhuǎn),如圖3所示。
圖3 紅外-雷達(dá)拓?fù)鋱D
實(shí)際應(yīng)用中當(dāng)目標(biāo)相對(duì)位置翻轉(zhuǎn)時(shí),算法失效。同時(shí),算法中步驟2至步驟4要完成個(gè)相似度計(jì)算,算法復(fù)雜度高。
NN關(guān)聯(lián)算法運(yùn)算量小但是失配概率較大,而單純的基于拓?fù)鋱D的算法在拓?fù)浣Y(jié)構(gòu)畸變嚴(yán)重的情況下失配概率較大且運(yùn)算量較大。為此,基于以上兩點(diǎn),我們提出基于最近鄰-拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法。
4.1三角形拓?fù)湎嗨贫?/p>
該算法中拓?fù)湎嗨贫鹊呐卸ㄒ廊灰匀切螢橐劳?。為了判定拓?fù)浣Y(jié)構(gòu)是否翻轉(zhuǎn),定義如下規(guī)則:
(3)
(4)
4.2最近鄰-拓?fù)鋱D目標(biāo)關(guān)聯(lián)
基于最近鄰-拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法流程如圖4所示。
圖4 最近鄰-拓?fù)鋱D目標(biāo)關(guān)聯(lián)算法流程
對(duì)于雷達(dá)目標(biāo)集合中的每一個(gè)目標(biāo),都減去幾何形心偏差,得到新的雷達(dá)目標(biāo)集合為
(7)
(9)
(11)
步驟6 對(duì)于步驟5中得到的相似度矩陣,利用匈牙利指派算法或者JV最短路徑擴(kuò)張算法,求得使整體匹配度最高的匹配序列,完成雷達(dá)目標(biāo)和紅外目標(biāo)的匹配。
5.1仿真數(shù)據(jù)
仿真數(shù)據(jù)設(shè)置了兩個(gè)場(chǎng)景共計(jì)12個(gè)樣本。其中場(chǎng)景1中設(shè)置4個(gè)紅外目標(biāo),4個(gè)雷達(dá)目標(biāo),每個(gè)目標(biāo)包含52點(diǎn)數(shù)據(jù),方位角偏差在~之間緩變,俯仰角偏差在~之間緩變;場(chǎng)景2中設(shè)置4個(gè)紅外目標(biāo),8個(gè)雷達(dá)目標(biāo),每個(gè)目標(biāo)包含85點(diǎn)數(shù)據(jù),方位角偏差在~之間緩變,俯仰角偏差在~之間緩變。
5.2 仿真結(jié)果及分析
我們分別對(duì)兩個(gè)場(chǎng)景的6個(gè)樣本進(jìn)行仿真,得到兩個(gè)場(chǎng)景的關(guān)聯(lián)成功概率如表1和表2所示。
表1最近鄰-拓?fù)鋱D算法仿真結(jié)果(場(chǎng)景1)
場(chǎng)景-樣本主目標(biāo)關(guān)聯(lián)成功率(%)從目標(biāo)1關(guān)聯(lián)成功率(%)從目標(biāo)2關(guān)聯(lián)成功率(%)從目標(biāo)3關(guān)聯(lián)成功率(%) 1-1100100100100 1-2100100100100 1-3100100100100 1-4100100100100 1-510096.1510096.15 1-610098.0810098.08
場(chǎng)景-樣本紅外主目標(biāo)關(guān)聯(lián)成功率(%)紅外從目標(biāo)1關(guān)聯(lián)成功率(%)紅外從目標(biāo)2關(guān)聯(lián)成功率(%)紅外從目標(biāo)關(guān)聯(lián)成功率(%) 2-193909694 2-291908887 2-392767285 2-497858590 2-596859095 2-686717667
從表1,表2可以看出,本文算法將系統(tǒng)偏差補(bǔ)償和目標(biāo)關(guān)聯(lián)有機(jī)地耦合在一起,受系統(tǒng)偏差影響較小,關(guān)聯(lián)性能較高。
對(duì)于場(chǎng)景2的數(shù)據(jù)也利用最近鄰算法進(jìn)行了仿真,其結(jié)果如表3所示。通過表2、表3對(duì)比看出,由于系統(tǒng)偏差的影響,最近鄰算法性能極差。而新算法對(duì)系統(tǒng)偏差不敏感,性能較好。
表3最近鄰算法仿真結(jié)果(場(chǎng)景2)
場(chǎng)景-樣本紅外主目標(biāo)關(guān)聯(lián)成功率(%)紅外從目標(biāo)1關(guān)聯(lián)成功率(%)紅外從目標(biāo)2關(guān)聯(lián)成功率(%)紅外從目標(biāo)關(guān)聯(lián)成功率(%) 2-1484980 2-2431980 2-35621000 2-4672940 2-5514980 2-6596921
下面我們來分析雷達(dá)目標(biāo)數(shù)對(duì)主目標(biāo)關(guān)聯(lián)成功率的影響。設(shè)定紅外目標(biāo)數(shù)=4時(shí),得到主目標(biāo)關(guān)聯(lián)成功概率與雷達(dá)目標(biāo)數(shù)的關(guān)系曲線如圖5所示。從圖中我們可以看出,隨著雷達(dá)目標(biāo)數(shù)目增多,主目標(biāo)關(guān)聯(lián)成功概率下降。這是由于雷達(dá)數(shù)量越大,拓?fù)浣Y(jié)構(gòu)越復(fù)雜,出錯(cuò)概率越大。同時(shí)我們可以看出,當(dāng)雷達(dá)目標(biāo)數(shù)目小于9時(shí),關(guān)聯(lián)成功率在95%以上;當(dāng)雷達(dá)目標(biāo)數(shù)小于12時(shí),關(guān)聯(lián)成功率在91%以上。
同時(shí),由于在最近鄰-拓?fù)鋱D算法中涉及了鄰域半徑。我們分析鄰域半徑大小對(duì)主目標(biāo)關(guān)聯(lián)成功率和算法復(fù)雜度的影響得到曲線如圖6所示??梢钥闯?,鄰域半徑越小,算法復(fù)雜度越小,但同時(shí)會(huì)犧牲一定的算法精度。當(dāng)鄰域半徑超過一定范圍,關(guān)聯(lián)成功率不再隨鄰域半徑變換。鄰域半徑的大小選取反映了拓?fù)鋱D的畸變程度,綜合算法精度和時(shí)間的考慮,我們選取鄰域半徑為。
圖5 雷達(dá)目標(biāo)數(shù)對(duì)主目標(biāo)關(guān)聯(lián)成功率的影響
圖6 鄰域半徑對(duì)算法影響
最后,在此簡(jiǎn)要分析該算法的時(shí)間復(fù)雜度。假設(shè)雷達(dá)和紅外目標(biāo)個(gè)數(shù)分別為和,則步驟1共需要完成2次均值運(yùn)算和次減法運(yùn)算;步驟2~步驟4共需要進(jìn)行次拓?fù)湎嗨贫扔?jì)算;步驟6需要對(duì)的矩陣尋優(yōu)。故整體時(shí)間復(fù)雜度為量級(jí)。而拓?fù)鋱D法要完成次拓?fù)湎嗨贫鹊挠?jì)算,即次歐氏距離的計(jì)算,同時(shí)要完成的矩陣尋優(yōu)。故其時(shí)間復(fù)雜度為量級(jí)。當(dāng)取值較大時(shí),后者算法復(fù)雜度遠(yuǎn)遠(yuǎn)大于前者。
本文算法有一定的適用范圍。當(dāng)傳感器出現(xiàn)大量的虛警和漏報(bào)時(shí),整個(gè)拓?fù)浣Y(jié)構(gòu)發(fā)生嚴(yán)重的冗余或者缺失時(shí),基于最近鄰-拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法性能下降。
本文通過對(duì)異類傳感器目標(biāo)關(guān)聯(lián)算法的深入研究,針對(duì)同一時(shí)刻系統(tǒng)誤差對(duì)各目標(biāo)大小不一且系統(tǒng)誤差難以實(shí)時(shí)估計(jì)補(bǔ)償?shù)那闆r,提出了基于最近鄰-拓?fù)鋱D的目標(biāo)關(guān)聯(lián)算法。新算法巧妙地避免了系統(tǒng)誤差對(duì)目標(biāo)關(guān)聯(lián)的影響,很好地解決了異類傳感器目標(biāo)關(guān)聯(lián)成功概率較低的問題,且大大地降低了算法的復(fù)雜度。仿真實(shí)驗(yàn)表明新方法的目標(biāo)關(guān)聯(lián)成功概率在90%以上,有利于工程實(shí)現(xiàn)和軍事應(yīng)用。但同時(shí)本文算法還有待改進(jìn)的地方,比如算法中鄰域半徑的選擇如何做到自適應(yīng)是下一步值得研究的地方。
[1] 郜麗鵬, 葉方, 司錫才, 等. 基于雷達(dá)、紅外的數(shù)據(jù)融合算法研究[J]. 信息技術(shù), 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] 尹繼豪, 崔炳喆. 雷達(dá)/紅外數(shù)據(jù)融合的機(jī)動(dòng)目標(biāo)跟蹤算法綜述[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] 董云龍, 何友, 王國(guó)宏, 等. 一種改進(jìn)的系統(tǒng)偏差估計(jì)算法[J].宇航學(xué)報(bào), 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] 吳澤民, 任姝婕. 雷達(dá)時(shí)差和系統(tǒng)誤差的聯(lián)合估計(jì)方法[J]. 兵工學(xué)報(bào), 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] 宋強(qiáng), 何友, 熊偉, 等. 基于極大似然的單傳感器誤差配準(zhǔn)算法[J]. 宇航學(xué)報(bào), 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] 豐昌政, 薛強(qiáng). 雷達(dá)組網(wǎng)的精確極大似然誤差配準(zhǔn)算法[J]. 兵工自動(dòng)化, 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] 宋業(yè)新, 陳綿云, 張曙紅, 等. 兩類多目標(biāo)廣義指派問題的有效算法及其應(yīng)用[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 柳鵬, 高杰, 劉揚(yáng), 等. 基于拍賣算法的目標(biāo)分配問題優(yōu)化[J].兵工自動(dòng)化, 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] 黃樹采, 李為民, 李威, 等. 多傳感器管理的目標(biāo)分配問題蟻群算法研究[J]. 空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 田宏偉, 敬忠良, 胡士強(qiáng), 等. 基于多速率運(yùn)動(dòng)模型的多幀最近鄰數(shù)據(jù)關(guān)聯(lián)算法[J]. 上海交通大學(xué)學(xué)報(bào), 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] 楊哲, 韓崇昭, 李晨, 等. 基于目標(biāo)之間拓?fù)湫畔⒌臄?shù)據(jù)關(guān)聯(lián)方法[J]. 系統(tǒng)仿真學(xué)報(bào), 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的多傳感器融合多目標(biāo)跟蹤的數(shù)據(jù)關(guān)聯(lián)[J]. 系統(tǒng)仿真學(xué)報(bào), 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] 石玥, 王鉞, 王樹剛, 等. 基于目標(biāo)參照拓?fù)涞哪:桔E關(guān)聯(lián)方法[J]. 國(guó)防科技大學(xué)學(xué)報(bào), 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-),男,碩士研究生,清華大學(xué)電子工程系,主要從事衛(wèi)星導(dǎo)航等研究。 E-mail: ydb12@mails.tsinghua.edu.cn
孟藏珍(1978-),男,博士生,清華大學(xué)電子工程系。主要從事雷達(dá)信號(hào)與數(shù)據(jù)處理等方面的研究。 E-mail: mcz-zzhp@sina.com
許 稼(1974-),男,博士,教授,北京理工大學(xué)信息與電子學(xué)院。主要從事雷達(dá)信號(hào)檢測(cè)與處理、數(shù)據(jù)融合處理、SAR成像等方面研究。E-mail: xujia@tsinghua.edu.cn
彭應(yīng)寧,男,教授,清華大學(xué)電子工程系。E-mail: ynpeng@tsinghua.edu.cn
2012-11-16收到,2012-12-14改回;2012-12-19網(wǎng)絡(luò)優(yōu)先出版
國(guó)家自然科學(xué)基金(61102168)資助課題
袁定波 ydb12@mails.tsinghua.edu.cn