基于時空距離度量的航跡發現關聯算法

楊邦，江婷，丁亞坤，郭蕊，吳泳，孫祥

（中國電子科技集團公司第五十二研究所，浙江 杭州 311121）

0 引言

隨著無線傳感器技術、無線電探測技術的發展[1]，越來越多的設備能夠探測、發現并持續跟蹤特定區域內的活動目標[2]。在實際應用中，為了保證防控系統的可靠性，避免監控死角，會部署眾多的目標探測和跟蹤設備，這些設備獨立或者協同進行目標探測和持續跟蹤[3-4]，并實時上報所發現的目標的航跡數據。在這種場景下，系統往往面臨如下幾個問題：一是多設備交替覆蓋布控導致對目標的跟蹤數據增多，每個設備都會對發現的目標航跡進行上報，如果不做合理計算，系統會認為環境中出現了大量目標，導致與真實情況嚴重不符，將極大影響決策者對區域安全狀態的正確研判，也可能導致大量的虛警[5]；二是某些探測設備不具備目標建航跟蹤能力，只能持續探測發現運動目標實時位置，即僅上報時間序列上的散點。本文主要解決目標點跡建航以及航跡關聯等問題。

對于航跡關聯問題，衣曉和曾睿等[6]提出一種基于K 近鄰平均距離的異步航跡直接關聯算法，通過對不等長航跡序列間的灰色關聯度進行計算，并利用經典分配法進行航跡關聯判定。王號等[7]引入Hausdorff 距離，對兩個航跡集的相似程度進行指標衡量并將其作為航跡同一性關聯依據。李恒璐等[8]提出基于信息熵權的最近鄰域數據關聯算法，按照熵權法分配各個測量指標的權值，再對計算出的權值應用最近鄰域算法進行統計計算，從而改善原算法在單目標跟蹤中存在的問題。高峰等[9]提出了廣義絕對灰關聯、一般灰色關聯、B型灰關聯、C 型灰關聯、T 型灰關聯等理論用于航跡融合領域。Tokta等[10]在馬氏距離理論基礎上對時間序列做協方差計算實現了航跡關聯。周堯等[11]針對某些測試環境下或設備工作狀態下目標試驗數據原始數據差異較大的問題，提出基于支持度的多傳感器融合方法。李捷等[12]針對多周期數據融合問題，基于改進DS（Dempster-Shafer）理論，結合貝葉斯改進方案擬合多源數據的分布情況，建立基于疊合度的融合模型。李素等[13]采用K-means聚類的方法將來自各傳感器的局部航跡與系統航跡進行關聯，并將系統航跡作為初始聚類中心，避免了K-means 算法本身依賴初始值的缺陷。另一類基于深度學習的方法也有相關應用，黃虹瑋等[14]將長短期記憶網絡引入CNN（Convolutional Neural Networks）模型提升了航跡關聯的精度。

考慮目標航跡數據的空間特性以及時間特性，同時結合數據分類思想，本文設計提出基于時空距離度量的航跡發現關聯算法。

1 基于時空距離度量的航跡發現關聯算法設計

K-近鄰方法（K-Nearest Neighbor，KNN）在機器學習分類問題方面有著較多應用[15-17]。對于待分類數據，KNN 通過在訓練數據中尋找出歐氏距離最近的K 條數據，其中最多的類別數據作為分類結果。針對目標運動點跡數據的時空特性，本文在傳統KNN 算法的基礎上，提出基于時空距離度量的無監督KNN 航跡發現關聯算法。

1.1 時空距離度量模型（TSMM）

對點跡進行航跡關聯，如果僅考慮單個數據點之間的空間距離，由于存在目標運動軌跡交叉的情況，會存在較大錯誤率[18-19]，如圖1 所示。

圖1 目標飛行示意圖Figure 1 Schematic diagram of target flight

此外，當兩個目標在不同時間以相同或近似航跡飛行時，航跡在空間上高度重合，僅基于空間位置的度量方法會得出誤差較大的結果[20-21]?；谝陨峡紤]，結合目標運動點跡數據實際場景，提出基于時空距離的度量模型（Time-Space Metric Model，TSMM）。

TSMM 主要考慮空間距離、向量距離、時間距離因素，如式（1）所示。

其中，Ta為顯著因子，用來對計算結果做顯著性縮放處理，避免軟件實現過程中因精度丟失問題導致結果異常；TS為數據時間段分布參數，時間差大于此值的數據，需要考慮時間因素對計算結果的影響；t1，t2分別表示兩個數據點的時間戳，如果數據時間差小于此值，空間距離和向量距離對最終計算結果影響更加顯著；dV表示數據向量的歐氏距離；dS表示數據向量表示的目標點的空間距離。

1.2 基于時空距離度量的改進型KNN 點跡建航算法（TSMM-KNN）

基于時空距離度量的改進型KNN 點跡建航算法（TSMM-KNN）主要分為四個階段：點集數據預處理階段、已識別航跡關聯匹配階段、K-近鄰數據集相同點集識別匹配階段和計算結果輸出階段。算法整體流程如圖2 所示。

圖2 TSMM-KNN 流程圖Figure 2 TSMM-KNN flow chart

點集數據預處理階段作為處理流程的起始，負責處理流程控制功能以及對目標數據格式化處理。由于點跡數據不存在航跡編號批號，所以對點跡數據預生成標識，使用前文提出的TSMM 模型在目標點集中尋找距離量度結果最小的K 個鄰居點。

在航跡關聯匹配階段，如果兩個點的共同鄰居數大于MIN_NUM_SAME_NEIGHBOR值，則將兩個目標點以及它們的共同鄰居點編入同一航跡。

K-近鄰數據集相同點集識別匹配階段是在前序階段未成功關聯到已有航跡的情況下，與所有未關聯航跡的數據進行鄰居關聯匹配。

2 實驗及分析

2.1 實驗數據集情況

航跡數據基于對大疆MAGIC3、大疆MINI2、大疆FPV 機型的測試飛行數據進行預處理得到47條航跡數據，其中真實目標數量30 個。實驗基本內容是對K 值與MIN_NUM_SAME_NEIGHBOR 參數進行碰撞優化，實驗K 參數從8 到20，每個K 參數對應MIN_NUM_SAME_NEIGHBOR 從3 到K 進行實驗。此章節中圖表橫坐標表示MIN_NUM_SAME_NEIGHBOR 參數取值?？v坐標表示對應指標結果值。

2.2 指標定義和結果分析

同航跡數據聚類識別正確率F1：

式中：n 表示識別結果中航跡總數；N 表示真實航跡數；ACi表示第i 條航跡識別結果正確率，對于第i 條識別航跡，記其中識別出總點數量為m，其中同屬于一個目標運動航跡的最大點集中點的數量為p，則表示識別出的航跡數與實際航跡數之間的差距情況。如果F1值越小，則說明識別結果中同航跡中數據混雜情況越嚴重。F1值越大，航跡點集識別越可靠。

從如圖3 所示F1指標曲線可以看到，算法在兩個參數變化時有明顯的效果優化過程。在MIN_NUM_ SAME_NEIGHBOR/K 值達到0.6 左右以后開始呈現較好效果。其意義在于，對于同一航跡上的數據點，其共同鄰居數大都能達到設定K值的0.6 以上水平，如果MIN_NUM_SAME_NEIGHBOR 設定較低，會導致不同航跡上的點被歸入同一航跡的情況增加。

圖3 F1 指標曲線a）K=3 b）K=12 c）K=16 d）K=20Figure 3 Index F1 Curve a）K=3 b）K=12 c）K=16 d）K=20

航跡分割評價指標F2：

式中：predTi表示在預測結果中，有原航跡數據集中的Ti航跡中的數據點分布的不同航跡的數量；N 表示原航跡數據集中真實航跡數量。F2指標度量算法對航跡的持續識別能力：F2值越小，則表明航跡被識別得更完整；如果F2值較大，表明航跡被識別成多段暫時航跡的情況較多。

由圖4 所示的F2指標對照情況可以看出，TSMM-KNN 相對傳統只基于空間距離的KNN 方法擁有更好的航跡分割控制性能，TSMM-KNN 能夠更好地讓原航跡中的點聚集在同一結果航跡中，降低原航跡被過分識別成大量暫時航跡點的情況。

圖4 F2 指標曲線a）K=8 b）K=12 c）K=16 d）K=20Figure 4 Index F2 Curve a）K=8 b）K=12 c）K=16 d）K=20

識別結果綜合評估指標G：

當同航跡數據聚類識別正確率F1指標與航跡分割評價指標F2都取得較好結果的情況下，綜合指標G 才更加優秀。

由圖5 所示的指標G 的對照結果可以看出，TSMM-KNN 方法的綜合結果相對于只基于空間距離度量的傳統方法有顯著優化效果。

圖5 G指標曲線a）K=8 b）K=12 c）K=16 d）K=20Figure 5 Index G curve a）K=8 b）K=12 c）K=16 d）K=20

3 結語

本文利用目標點跡數據的時空特性，充分考量點跡數據之間的時空距離，結合KNN 數據分類理論，實現對大量點跡進行快速準確的航跡發現和關聯。相對于只采用空間距離信息的方法，本方法在同航跡數據聚類識別正確率、航跡分割評價指標以及綜合評價指標上都獲得了更加優秀的表現。算法在數據融合系統中已有相關實踐應用。實踐證明，該方法具備與數據融合系統快速集成的能力，特別是航跡數據融合系統，此算法的應用能夠有效彌補傳統航跡融合系統對未建航跡的目標點跡數據無法有效處理的問題。未來，本文將在時間分布不均勻的數據處理方面以及設備異常數據有效過濾等方面做進一步研究，提高算法對異常數據以及時間稀疏性不均勻數據的適應性和容忍度。