基于時(shí)空距離度量的航跡發(fā)現(xiàn)關(guān)聯(lián)算法

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

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

0 引言

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

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

考慮目標(biāo)航跡數(shù)據(jù)的空間特性以及時(shí)間特性，同時(shí)結(jié)合數(shù)據(jù)分類思想，本文設(shè)計(jì)提出基于時(shí)空距離度量的航跡發(fā)現(xiàn)關(guān)聯(lián)算法。

1 基于時(shí)空距離度量的航跡發(fā)現(xiàn)關(guān)聯(lián)算法設(shè)計(jì)

K-近鄰方法（K-Nearest Neighbor，KNN）在機(jī)器學(xué)習(xí)分類問題方面有著較多應(yīng)用[15-17]。對(duì)于待分類數(shù)據(jù)，KNN 通過在訓(xùn)練數(shù)據(jù)中尋找出歐氏距離最近的K 條數(shù)據(jù)，其中最多的類別數(shù)據(jù)作為分類結(jié)果。針對(duì)目標(biāo)運(yùn)動(dòng)點(diǎn)跡數(shù)據(jù)的時(shí)空特性，本文在傳統(tǒng)KNN 算法的基礎(chǔ)上，提出基于時(shí)空距離度量的無監(jiān)督KNN 航跡發(fā)現(xiàn)關(guān)聯(lián)算法。

1.1 時(shí)空距離度量模型（TSMM）

對(duì)點(diǎn)跡進(jìn)行航跡關(guān)聯(lián)，如果僅考慮單個(gè)數(shù)據(jù)點(diǎn)之間的空間距離，由于存在目標(biāo)運(yùn)動(dòng)軌跡交叉的情況，會(huì)存在較大錯(cuò)誤率[18-19]，如圖1 所示。

圖1 目標(biāo)飛行示意圖Figure 1 Schematic diagram of target flight

此外，當(dāng)兩個(gè)目標(biāo)在不同時(shí)間以相同或近似航跡飛行時(shí)，航跡在空間上高度重合，僅基于空間位置的度量方法會(huì)得出誤差較大的結(jié)果[20-21]?；谝陨峡紤]，結(jié)合目標(biāo)運(yùn)動(dòng)點(diǎn)跡數(shù)據(jù)實(shí)際場景，提出基于時(shí)空距離的度量模型（Time-Space Metric Model，TSMM）。

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

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

1.2 基于時(shí)空距離度量的改進(jìn)型KNN 點(diǎn)跡建航算法（TSMM-KNN）

基于時(shí)空距離度量的改進(jìn)型KNN 點(diǎn)跡建航算法（TSMM-KNN）主要分為四個(gè)階段：點(diǎn)集數(shù)據(jù)預(yù)處理階段、已識(shí)別航跡關(guān)聯(lián)匹配階段、K-近鄰數(shù)據(jù)集相同點(diǎn)集識(shí)別匹配階段和計(jì)算結(jié)果輸出階段。算法整體流程如圖2 所示。

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

點(diǎn)集數(shù)據(jù)預(yù)處理階段作為處理流程的起始，負(fù)責(zé)處理流程控制功能以及對(duì)目標(biāo)數(shù)據(jù)格式化處理。由于點(diǎn)跡數(shù)據(jù)不存在航跡編號(hào)批號(hào)，所以對(duì)點(diǎn)跡數(shù)據(jù)預(yù)生成標(biāo)識(shí)，使用前文提出的TSMM 模型在目標(biāo)點(diǎn)集中尋找距離量度結(jié)果最小的K 個(gè)鄰居點(diǎn)。

在航跡關(guān)聯(lián)匹配階段，如果兩個(gè)點(diǎn)的共同鄰居數(shù)大于MIN_NUM_SAME_NEIGHBOR值，則將兩個(gè)目標(biāo)點(diǎn)以及它們的共同鄰居點(diǎn)編入同一航跡。

K-近鄰數(shù)據(jù)集相同點(diǎn)集識(shí)別匹配階段是在前序階段未成功關(guān)聯(lián)到已有航跡的情況下，與所有未關(guān)聯(lián)航跡的數(shù)據(jù)進(jìn)行鄰居關(guān)聯(lián)匹配。

2 實(shí)驗(yàn)及分析

2.1 實(shí)驗(yàn)數(shù)據(jù)集情況

航跡數(shù)據(jù)基于對(duì)大疆MAGIC3、大疆MINI2、大疆FPV 機(jī)型的測試飛行數(shù)據(jù)進(jìn)行預(yù)處理得到47條航跡數(shù)據(jù)，其中真實(shí)目標(biāo)數(shù)量30 個(gè)。實(shí)驗(yàn)基本內(nèi)容是對(duì)K 值與MIN_NUM_SAME_NEIGHBOR 參數(shù)進(jìn)行碰撞優(yōu)化，實(shí)驗(yàn)K 參數(shù)從8 到20，每個(gè)K 參數(shù)對(duì)應(yīng)MIN_NUM_SAME_NEIGHBOR 從3 到K 進(jìn)行實(shí)驗(yàn)。此章節(jié)中圖表橫坐標(biāo)表示MIN_NUM_SAME_NEIGHBOR 參數(shù)取值?？v坐標(biāo)表示對(duì)應(yīng)指標(biāo)結(jié)果值。

2.2 指標(biāo)定義和結(jié)果分析

同航跡數(shù)據(jù)聚類識(shí)別正確率F1：

式中：n 表示識(shí)別結(jié)果中航跡總數(shù)；N 表示真實(shí)航跡數(shù)；ACi表示第i 條航跡識(shí)別結(jié)果正確率，對(duì)于第i 條識(shí)別航跡，記其中識(shí)別出總點(diǎn)數(shù)量為m，其中同屬于一個(gè)目標(biāo)運(yùn)動(dòng)航跡的最大點(diǎn)集中點(diǎn)的數(shù)量為p，則表示識(shí)別出的航跡數(shù)與實(shí)際航跡數(shù)之間的差距情況。如果F1值越小，則說明識(shí)別結(jié)果中同航跡中數(shù)據(jù)混雜情況越嚴(yán)重。F1值越大，航跡點(diǎn)集識(shí)別越可靠。

從如圖3 所示F1指標(biāo)曲線可以看到，算法在兩個(gè)參數(shù)變化時(shí)有明顯的效果優(yōu)化過程。在MIN_NUM_ SAME_NEIGHBOR/K 值達(dá)到0.6 左右以后開始呈現(xiàn)較好效果。其意義在于，對(duì)于同一航跡上的數(shù)據(jù)點(diǎn)，其共同鄰居數(shù)大都能達(dá)到設(shè)定K值的0.6 以上水平，如果MIN_NUM_SAME_NEIGHBOR 設(shè)定較低，會(huì)導(dǎo)致不同航跡上的點(diǎn)被歸入同一航跡的情況增加。

圖3 F1 指標(biāo)曲線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

航跡分割評(píng)價(jià)指標(biāo)F2：

式中：predTi表示在預(yù)測結(jié)果中，有原航跡數(shù)據(jù)集中的Ti航跡中的數(shù)據(jù)點(diǎn)分布的不同航跡的數(shù)量；N 表示原航跡數(shù)據(jù)集中真實(shí)航跡數(shù)量。F2指標(biāo)度量算法對(duì)航跡的持續(xù)識(shí)別能力：F2值越小，則表明航跡被識(shí)別得更完整；如果F2值較大，表明航跡被識(shí)別成多段暫時(shí)航跡的情況較多。

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

圖4 F2 指標(biāo)曲線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

識(shí)別結(jié)果綜合評(píng)估指標(biāo)G：

當(dāng)同航跡數(shù)據(jù)聚類識(shí)別正確率F1指標(biāo)與航跡分割評(píng)價(jià)指標(biāo)F2都取得較好結(jié)果的情況下，綜合指標(biāo)G 才更加優(yōu)秀。

由圖5 所示的指標(biāo)G 的對(duì)照結(jié)果可以看出，TSMM-KNN 方法的綜合結(jié)果相對(duì)于只基于空間距離度量的傳統(tǒng)方法有顯著優(yōu)化效果。

圖5 G指標(biāo)曲線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 結(jié)語

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