基于三角形拓撲相似性的航跡關聯算法

毛藝帆，　張多林，　王　路

(空軍工程大學 防空反導學院， 陜西 西安 710051)

?

基于三角形拓撲相似性的航跡關聯算法

毛藝帆，張多林，王路

(空軍工程大學 防空反導學院， 陜西 西安 710051)

針對多個傳感器量測航跡在系統誤差下關聯融合困難的問題，提出基于拓撲4交差模型和三角形拓撲相似度的航跡關聯方法，將傳感器探測目標分成若干個拓撲三角形結構，使用4交差模型排除不同傳感器探測中相關可能性小的三角形；然后定義三角形相似度，對歸屬于不同探測源的拓撲三角形相似程度進行度量，從而得出目標之間的相關程度，獲取航跡關聯結果。仿真結果表明，在目標密集編隊時，該算法具有有效性。

航跡融合；航跡關聯；拓撲4交差模型；三角形相似度

航跡關聯是航跡融合中的關鍵問題，解決了不同航跡是否屬于同一目標的問題，是后續信息能夠進行可靠融合的基礎，是跟蹤成功的關鍵。在分布式信息處理系統中，信息處理子節點提供目標的狀態估計航跡；在信息處理中心，對不同節點的航跡信息關聯對準，對關聯成功的航跡對再進行航跡融合，得到最終的融合結果。現階段，已有大量的關于航跡融合及航跡關聯的研究成果，主要分為基于統計的方法[1-2]、基于模糊理論的方法[3-6]和基于灰色理論的方法[7-8]。這些方法大多只考慮探測的隨機誤差，未考慮系統誤差，且在目標密集編隊時，無法在短時間內獲取良好的關聯效果。因此，需要在現有研究的基礎上，發掘新的方法，解決上述問題。

本文首先推導存在系統誤差的目標粗相關波門，再將航跡目標進行分割，劃分成最簡單的拓撲目標——三角形目標進行研究，并通過基于空間拓撲模型進行篩選，通過篩選的目標進行基于三角形相似度比較的精相關，最后結合雙門限準則和多義性處理，得到最終的航跡關聯結果。

1　目標粗相關波門計算

目標粗相關的思想是根據關聯波門，對待關聯的目標進行篩選，以便在進一步的關聯操作中，摒棄關聯波門以外的目標。粗關聯可有效減小計算量，提高計算效率[9]。在粗關聯中，關聯波門的選擇是尤為重要的，因此，本文對存在系統誤差時的關聯波門計算方法進行闡述。

假設有傳感器S1、S2對規定區域進行目標探測和跟蹤，探測到的目標分別為m和n個；探測到的航跡信息傳遞到信息融合中心，以融合中心為坐標原點，建立笛卡爾坐標系，取其中兩維進行研究，設S1和S2在該坐標系下的坐標為(xs1,ys1)和(xs2,ys2)；將傳感器S1所在位置設為融合中心，則其與傳感器及任一目標位置關系如圖1所示。圖中，S1和S2分別表示2個傳感器，Target表示目標真實位置，TS1和TS2分別表示傳感器的測量值。考慮傳感器的系統誤差，其測距以及測角系統誤差為(Δrs1,Δθs1)和(Δrs2,Δθs2)。

圖1　融合中心、傳感器及任一目標位置關系示意圖

(1)

(2)

(3)

(4)

(5)

(6)

2　基于三角形相似性的航跡相關

2.1目標三角形分割

由于三角形是形狀比較簡單的拓撲結構，可以很好地反映局部的拓撲結構，而且對大規模的運算而言，運算負擔不會很重，其在模式識別方面已經得到廣泛應用[10]，因此，本文選擇將三角形結構作為拓撲結構元，研究基于目標之間拓撲信息的航跡關聯方法。

a) 傳感器1中選中的三角形示意圖

b) 傳感器2中目標點跡三角形組合

a) 傳感器2中目標點跡三角形組合

b) 傳感器2中目標點跡三角形組合

2.2目標三角形篩選

(7)

式中，Aο表示集合A的內部；Bο表示集合B的內部；?A表示集合A的邊界；?B表示集合B的邊界。該模型可描述多種點/點、點/線、點/面、線/線、線/面、面/面關系。

相對于其他模型(如9交模型等)，4交模型只需計算4個元素，且可表征比較完備的空間目標拓撲關系，其應用比較廣；然而要進行4個交運算，運算復雜性比較高。因此，鄧敏等[11]46-49提出了一種混合模型——4交差模型，如式(8)所示。較之4交模型，其只需進行2個交運算和2個差運算，顯然，差運算比交運算的計算復雜性低；而且，該模型同樣可以很好地表征空間目標的拓撲關系。

(8)

若2個拓撲目標相關，則其在空間中的距離不應相距太遠，而彼此之間的距離衡量需要定義另外的函數。假設有一個映射函數σ(Δ),其定義如式(9)。進而，定義距離函數，如式(10)所示。

(9)

(10)

例如目標相等和目標相離之間拓撲距離計算過程為

已知

可以看出，目標相等和目標相交、包含、包含于、覆蓋、覆蓋于這幾種關系的距離較近，由于傳感器探測到的目標都不是百分百準確的目標信息，所以具有不同程度的模糊性。因此本文認定，當空間目標處于相等、相交、包含、包含于、覆蓋、覆蓋于這幾種拓撲關系時，目標是有相關的可能性的，只是可能性大小不同；反之，當處于相接和相離關系時，認定其是不相關的。根據此方法，排除相關可能性較低的拓撲三角形目標，使用Arcview軟件即可實現，并可與Matlab進行數據互通。

2.3三角形相似度度量

已經經過相關篩選的三角形目標，需要進行進一步的處理，才能獲取目標關聯結果。本文根據目標之間的拓撲相似性來判斷目標相關程度。具體來說，當拓撲目標之間的結構相似度越大，則可知構成三角形拓撲結構的目標點之間的關聯程度就越高，繼而問題轉化為如何判斷三角形目標相似度。參考文獻[14]中對三角形相似度的闡述，定義三角形拓撲相似度為

(11)

2.4雙門限準則和多義性處理

某一時刻的目標關聯結果并不能作為整體的航跡關聯結果，需要經過多次的關聯檢驗，才有可能形成固定的航跡關聯對，因此，需要引入雙門限準則和多義性處理幫助進行航跡關聯判定。

雙門限準則[9,15]：選擇整數I和R(一般根據經驗選值)，?k=1,…,R時刻，若關聯成功，則計數器mij(k)=mij(k-1)+1，mij(0)置0；若經過R次關聯檢測，計數器值大于門限值I,即mij(R)≥I,則判定目標i和目標j為同一目標，否則，需進入下一檢驗周期進行關聯檢測。已經判定為關聯的目標對則不需要進行進一步的關聯檢測。

3　算法流程

5) 對目標進行基于I/R規則的航跡相關檢驗，并在必要的時候進行多義性處理，得到最終航跡關聯對。對已關聯航跡對，使用基本加權融合法，得到航跡融合結果。

4　仿真分析

為說明本文方法的有效性，設置如下的基本仿真環境：假設在以融合中心為原點的坐標系中有2個傳感器，坐標分別為(0,0)和(0,50)。在2個傳感器的重疊觀測區域內，有30批目標。傳感器的重疊觀測區域一般是不規則圖形，為了方便對關聯方法進行討論，設置該區域為矩形，目標初始位置隨機分布在30km×30km的矩形區域內，目標的初速和初始方位角分別位于20～200 m/s和0～2π rad范圍內，目標進行勻速直線運動。隨機測量距離誤差為50 m，隨機測量角度誤差為0.5°。假設共同觀測概率為1，進行50次蒙特卡羅仿真，每次20步，使用本文的方法和傳統的最近鄰(Nearest Neighbor,NN)算法進行仿真。為對航跡關聯的效果進行度量，定義航跡正確關聯概率Pr，Pr=Cr/(Cr+Cw),其中Cr表示正確關聯航跡對數目，Cw表示錯誤關聯航跡對數目。I/R邏輯選擇3/5規則。設置不同的仿真條件，進行仿真實驗。

1) 系統誤差范圍固定。假設傳感器1的系統測量距離和角度偏差最大值分別為100 m和1°，傳感器2的系統測量距離和角度偏差最大值分別為100 m和1°。使用本文方法和基本NN關聯法以及文獻[5]1694-1697中所提的模糊關聯法進行仿真實驗。在起始時刻，目標真實位置及2個傳感器的測量值如圖4所示，使用本文的方法，其最終航跡關聯結果的局部如圖5所示。

圖4　初始時刻目標示意圖

圖5　航跡關聯結果局部圖

根據本文算法和NN算法，得到正確關聯概率如圖6。在經過20步的關聯檢驗之后，3種方法的關聯正確率均可達到0.9以上，說明在檢驗步數一定的情況下，3種方法均有效。

2) 系統測角誤差不固定。假設傳感器1的系統測量距離和角度偏差最大值分別為100m和1°，傳感器2的系統測量距離最大值為100 m，其系統測量角度偏差最大值為1°～5°，分別為1°、1.5°、2°、2.5°、3°、3.5°、4°、4.5°和5°。使用本文方法和基本NN關聯法以及文獻[5]1694-1697中的模糊關聯法進行仿真實驗，得到正確關聯概率如圖7。由圖可得，隨著測角誤差增大，NN算法性能下降嚴重，文獻[5]1694-1697的方法也有所下降，且在誤差達到5°時關聯正確率已經降至0.7，本文方法性能比較穩定，關聯正確率仍舊在0.8以上。

3) 系統測距誤差不固定。假設傳感器1的系統測量距離和角度偏差最大值分別為100 m和1°，傳感器2的系統測量角度偏差最大值1°，其系統測量距離偏差最大值為100～500 m，分別為100 m、150 m、200 m、250 m、300 m、350 m、400 m、450 m和500 m。使用本文方法和基本NN關聯法以及文獻[5]1694-1697中的模糊關聯法進行仿真實驗，得到正確關聯概率如圖8。隨著測距誤差增大，NN算法和文獻[5]1694-1697的方法性能均下降嚴重，說明以上算法對距離誤差是比較敏感的，本文算法性能也有所下降，但正確關聯概率穩定在0.8以上。

圖6　系統誤差固定時的關聯正確率

圖7　系統測角誤差變化時的關聯正確率

圖8　系統測距誤差變化時的關聯正確率

由以上不同條件的仿真結果可知，首先，在系統誤差相差比較大的情況下，能夠獲取較好的關聯效果；進而，在系統誤差產生變化時，算法性能穩定，在系統測量誤差逐漸增大時，算法的正確關聯概率雖然也會逐漸減小，但比較平穩，變化不大，在可接收的范圍內。

5　結 束 語

針對現有航跡關聯算法對編隊飛行及密集目標關聯效果較差的問題，提出基于三角形拓撲相似性的航跡關聯方法，該方法有別于傳統的方法，是解決航跡關聯問題的一個有益的嘗試，仿真結果也表明本文方法的有效性。然而，本文算法雖然可以解決目標密集的問題，但運算量是一個不得不考慮的問題。在今后的研究中，應著重提升算法的效率，以便在實時性要求比較高的場合能夠得到應用。

References)

[1]盧大威, 高彥釗, 晏行偉, 等.基于角度觀測關聯對的NN-EKF紅外/毫米波融合跟蹤算法[J]. 彈箭與制導學報, 2011,31(5):4-8.

[2]耿利祥,陳錢,錢惟賢.改進的聯合概率數據關聯算法(JPDA)對紅外目標與誘餌的辨別[J].紅外與激光工程,2013,42(2):305-310.

[3]劉德浩,王國宏,陳中華.系統誤差下的模糊航跡關聯方法[J].現代防御技術, 2012,40(3):128-131；143.

[4]郭徽東,章新華.基于模糊綜合函數的航跡關聯算法及其應用[J].系統工程與電子技術,2003,25(11):1401-1403.

[5]丁鋒,薛磊.基于模糊理論的證據航跡關聯算法分析[J].計算機應用研究,2015,32(6):1694-1697.

[6]毛藝帆,王睿,張金成.基于空天信息的異類傳感器模糊航跡關聯算法[J].空軍工程大學學報(自然科學版),2012,13(5):35-39.

[7]閆子豪.基于灰關聯分析-模糊推理的目標關聯技術[J].華東理工大學學報(自然科學版),2007,33(5):712-715.

[8]李鵬,劉思峰.基于灰色關聯分析和D-S證據理論的區間直覺模糊決策方法[J].自動化學報,2011,37(8):993-998.

[9]宋強,熊偉,何友.基于復數域拓撲描述的航跡對準關聯算法[J]. 宇航學報, 2011, 32(3):560-566.

[10]趙鳳,劉漢強.不同形狀鄰域空間信息的模糊聚類圖像分割[J].計算機工程與應用, 2015,51(10):12-15；35.

[11]鄧敏,李志林,吳靜.空間關系理論與方法[M].北京:科學出版社,2013.

[12]鄧敏.矢量GIS中拓撲關系的擴展模型、理論和方法[D].武漢:武漢大學,2003：85-90.

[13]鄧敏,劉文寶,馮學智.GIS面目標間拓撲關系描述的形式化模型[J].測繪學報, 2005,34(1):85-91.

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

[15]宋強,熊偉,馬強.基于目標不變信息量的模糊航跡對準關聯算法[J]. 系統工程與電子技術,2011, 33(1):190-195.

(編輯：李江濤)

A Track Association Approach Based on Topological Triangle Similarity Degree

MAO Yifan，ZHANG Duolin，WANG Lu

(Air and Missile Defense College, Air Force Engineering University, Xi’an Shaanxi 710051, China)

To solve out the challenges over the track association and fusion with system error when measuring track with multiple sensors, the paper proposes a track association method based on topological 4-intersection-and-difference model and triangle similarity degree. By dividing the detected target of multiple sensors into several topological triangle similarity structures, using 4-intersection-and-difference model, the paper excludes those triangles with small possibility of association , then the paper defines the triangle similarity degree and measures the topological triangle similarity degree so as to draw the relevance among targets and the result of track association. The simulation result shows, the algorithm is effective in case of intensive formation targets.

track fusion; track association; topological 4-intersection-and-difference model; triangle similarity degree

2016-01-25

毛藝帆(1988—)，女，博士研究生，主要研究方向為作戰建模與仿真。myf1210@126.com

TP212

2095-3828(2016)04-0069-06

A

10.3783/j.issn.2095-3828.2016.04.015

張多林，男，教授，博士生導師。