利用k近鄰區(qū)間距離的異步抗差航跡關(guān)聯(lián)算法

衣 曉, 曾 睿,2,*, 曹昕瑩

(1. 海軍航空大學(xué)航空作戰(zhàn)勤務(wù)學(xué)院, 山東 煙臺 264001; 2. 中國人民解放軍92325部隊, 山西 大同 037001)

0 引 言

在分布式多目標(biāo)跟蹤融合系統(tǒng)中,一個重要問題是如何判斷來自于不同局部節(jié)點的航跡是否源自同一目標(biāo),即航跡關(guān)聯(lián)問題。然而傳感器系統(tǒng)誤差的存在增大了航跡關(guān)聯(lián)的難度,使得系統(tǒng)誤差下的航跡關(guān)聯(lián)問題與誤差配準(zhǔn)問題互為前提。

為克服系統(tǒng)誤差的影響,文獻(xiàn)[8]通過牛頓算法優(yōu)化標(biāo)準(zhǔn)函數(shù),提出一種最小二乘配準(zhǔn)算法;文獻(xiàn)[9]根據(jù)同源航跡距離向量相似特征,提出基于最小平均距離的粗關(guān)聯(lián)和基于分布的精關(guān)聯(lián)算法;文獻(xiàn)[10]通過推導(dǎo)等價量測方程,基于距離分級聚類實現(xiàn)航跡關(guān)聯(lián),在目標(biāo)密集等復(fù)雜環(huán)境下能保持很低的錯誤關(guān)聯(lián)率,穩(wěn)定性較強(qiáng)。以圖像匹配原理為基礎(chǔ),將系統(tǒng)誤差的影響轉(zhuǎn)化為旋轉(zhuǎn)量和平移量,利用Fourier變換或Radon變換,文獻(xiàn)[17]和文獻(xiàn)[18]提出了一種不依賴于準(zhǔn)確誤差配準(zhǔn)的航跡關(guān)聯(lián)技術(shù)。文獻(xiàn)[19]利用模糊綜合決策思想,建立模糊因素集,依據(jù)航跡緊密度建立矩陣得到有效航跡關(guān)聯(lián)對來實現(xiàn)系統(tǒng)誤差下的航跡關(guān)聯(lián)。文獻(xiàn)[21]以目標(biāo)的拓?fù)浣y(tǒng)計距離信息為基礎(chǔ),進(jìn)行全局最優(yōu)關(guān)聯(lián),根據(jù)雙門限準(zhǔn)則完成關(guān)聯(lián)判決。上述算法的前提均是航跡同步,若航跡異步則需要時域配準(zhǔn),將異步航跡轉(zhuǎn)換為同步航跡進(jìn)行處理,但時域配準(zhǔn)會導(dǎo)致航跡數(shù)據(jù)的誤差傳播積累,影響航跡關(guān)聯(lián)算法的性能。

針對系統(tǒng)誤差難以描述的問題,提出兩種系統(tǒng)誤差區(qū)間化方法,把帶有系統(tǒng)誤差的航跡數(shù)據(jù)轉(zhuǎn)換成區(qū)間數(shù)進(jìn)行處理。給出區(qū)間序列到區(qū)間點的近鄰區(qū)間距離計算規(guī)則,通過不等長航跡區(qū)間序列間的相似度,實現(xiàn)了航跡異步和系統(tǒng)誤差下的同時關(guān)聯(lián)。本文算法可有效降低系統(tǒng)誤差對關(guān)聯(lián)結(jié)果的影響,并且無需時域配準(zhǔn),可對異步不等速率航跡直接關(guān)聯(lián)。

1 區(qū)間序列的相似度度量

區(qū)間坐標(biāo)序列與區(qū)間坐標(biāo)點的近鄰區(qū)間距離

設(shè)非空區(qū)間坐標(biāo)序列為

(1)

不等長區(qū)間坐標(biāo)序列間的相似度

(2)

式中:

(3)

定義1、定義2中坐標(biāo)變量均為三維坐標(biāo),適用于三維空間;對于二維情況,只需相應(yīng)變更坐標(biāo)變量維數(shù)即可。

2 利用k近鄰區(qū)間距離的航跡關(guān)聯(lián)算法

2.1 問題描述

單側(cè)區(qū)間化:假設(shè)局部節(jié)點傳感器的系統(tǒng)誤差偏差方向已知,即Δ∈(0,Δ),Δ∈(0,Δ),則在不考慮量測隨機(jī)誤差的條件下,觀測值與真值滿足:

(4)

圖1 系統(tǒng)誤差雙側(cè)區(qū)間化示意圖Fig.1 Diagram of bilateral interval of system bias

(5)

越大說明航跡和航跡越有可能對應(yīng)同一目標(biāo),根據(jù)區(qū)間相似度,可利用多維分配法進(jìn)行航跡關(guān)聯(lián)判定。

2.2 航跡序列相似度的計算

(6)

式中:

=[,,,]=[,,,]

將系統(tǒng)誤差區(qū)間化處理后的區(qū)間坐標(biāo)記為

(7)

利用式(7),可將局部節(jié)點的第條航跡區(qū)間序列記為

同理,可將局部節(jié)點的第條航跡區(qū)間坐標(biāo)序列記為

航跡區(qū)間坐標(biāo)序列關(guān)聯(lián)列向量可表示為

(8)

航跡區(qū)間坐標(biāo)序列關(guān)聯(lián)列向量的維數(shù)為+1,每行表示各航跡區(qū)間坐標(biāo)序列,由于各航跡長度不同,每行元素集合的長度也有差異。其中前行表示來自局部節(jié)點的比較航跡,第+1行表示來自局部節(jié)點的參考航跡。

(9)

式中:INT[]表示不小于的最小整數(shù)。

根據(jù)定義1中對區(qū)間坐標(biāo)序列與區(qū)間坐標(biāo)點間距離的定義,計算比較序列與參考序列間的近鄰區(qū)間距離矩陣為

(10)

式中:

(11)

進(jìn)一步利用定義2可以求得局部節(jié)點的第條航跡區(qū)間序列與局部節(jié)點的第條航跡區(qū)間序列的灰色關(guān)聯(lián)度為

(12)

式中:

(13)

2.3 航跡關(guān)聯(lián)判決

對局部節(jié)點,上報的,條航跡一一計算灰色關(guān)聯(lián)度,組成×維灰色關(guān)聯(lián)度矩陣,利用經(jīng)典分配法進(jìn)行航跡關(guān)聯(lián)判決。

令變量

(14)

將目標(biāo)函數(shù)記為

(15)

構(gòu)成以下二維分配問題:

(16)

圖2給出了利用近鄰區(qū)間距離的異步抗差航跡關(guān)聯(lián)算法的流程圖。

圖2 算法流程圖Fig.2 Flowchart of algorithm

3 仿真驗證與分析

3.1 仿真環(huán)境

假設(shè)多目標(biāo)跟蹤系統(tǒng)由2個異地配置的局部節(jié)點構(gòu)成,對20批目標(biāo)實施不間斷跟蹤觀測35 s。局部節(jié)點1位置坐標(biāo)為(0,0),局部節(jié)點2位置坐標(biāo)為(100 km,0 km),局部節(jié)點1,2的傳感器采樣周期均為0.2 s。

假設(shè)機(jī)動目標(biāo)在二維平面中一直處于勻速直線運動狀態(tài),目標(biāo)初始航向區(qū)間為[0,2πrad],初始航速區(qū)間為[200 m/s, 400 m/s]。局部節(jié)點1和局部節(jié)點2的傳感器測距和測角的隨機(jī)測量誤差均為=50 m、=0.02 rad。進(jìn)行100次蒙特卡羅仿真實驗。

3.2 k的取值分析

對取值做出簡要理論分析:如若取值為1,相當(dāng)于未對異步航跡情況做出處理,且易受個例影響導(dǎo)致關(guān)聯(lián)結(jié)果波動較大;若的取值等于局部節(jié)點的航跡點數(shù)目,意味著所有航跡點都將參與距離的計算,最終關(guān)聯(lián)效果將顯著降低。

圖3給出了不同取值時的耗時對比。可以看出,隨著取值增大,耗時也逐漸加大。這是因為的取值越大意味著要納入計算點跡距離的航跡區(qū)間點越多,因此耗時也越高。

圖3 不同k取值的耗時對比Fig.3 Time comparison of different values on k

表1 不同k取值和局部節(jié)點1,2航跡區(qū)間點數(shù)目比的正確關(guān)聯(lián)率

3.3 區(qū)間化方式比較與分析

在仿真環(huán)境中,固定兩個局部節(jié)點傳感器最大測角系統(tǒng)誤差分別為05°和1°,假設(shè)單側(cè)區(qū)間化的測距系統(tǒng)誤差滿足Δ∈(0,Δ),改變兩個局部節(jié)點傳感器的最大測距系統(tǒng)誤差,對兩種區(qū)間化方式進(jìn)行比較。

圖4給出不同區(qū)間化方式關(guān)聯(lián)結(jié)果的比較。對觀測數(shù)據(jù)的區(qū)間化處理會增加不確定度,相較于單側(cè)區(qū)間化,雙側(cè)區(qū)間化處理后數(shù)據(jù)的不確定度更大。但從圖中可知,在兩個局部節(jié)點傳感器最大測距系統(tǒng)誤差不同時,兩種區(qū)間化方式的關(guān)聯(lián)效果相當(dāng)。由于雙側(cè)區(qū)間化對最大系統(tǒng)誤差的先驗信息要求低,故整體性能優(yōu)于單側(cè)區(qū)間化。若在實際應(yīng)用中采用雙側(cè)區(qū)間化處理,則只需知道最大系統(tǒng)誤差即可進(jìn)行準(zhǔn)確關(guān)聯(lián)。

圖4 區(qū)間化方式關(guān)聯(lián)結(jié)果比較Fig.4 Comparison of correlation results of interval modes

取定一組關(guān)聯(lián)航跡數(shù)據(jù),在不同的最大測距系統(tǒng)誤差下,比較近鄰區(qū)間距離相對于原始數(shù)據(jù)近鄰區(qū)間距離的增量。從圖5中可以看出,由于副對角線方向兩個局部節(jié)點傳感器的最大系統(tǒng)誤差差值不變,故近鄰區(qū)間距離增量保持一致。而主對角線方向系統(tǒng)誤差的差值對稱變化,故近鄰區(qū)間距離增量呈對稱變化。如圖4所示,雙側(cè)區(qū)間化處理后數(shù)據(jù)的不確定度較大,其近鄰區(qū)間距離增量大約是單側(cè)區(qū)間化的兩倍,但對于不同大小的系統(tǒng)誤差,兩種區(qū)間化方式導(dǎo)致的增量變化趨勢相同。在利用最小近鄰區(qū)間距離進(jìn)行關(guān)聯(lián)判別時,取決于距離的相對大小而非絕對大小,故兩種區(qū)間化方式下近鄰區(qū)間距離增量的變化趨勢相同決定了其關(guān)聯(lián)效果相當(dāng)。

圖5 k近鄰區(qū)間距離增量對比Fig.5 Comparison of increments of k-nearest neighbors interval dispersion

3.4 算法性能比較與分析

在仿真環(huán)境中,設(shè)置局部節(jié)點1傳感器測距和測角的最大系統(tǒng)誤差分別為1 000 m,1°,局部節(jié)點2傳感器取不同的最大系統(tǒng)誤差,比較算法的抗差性能,結(jié)果如表2所示。表中，為正確關(guān)聯(lián)率,為錯誤關(guān)聯(lián)率,為漏關(guān)聯(lián)率。選取文獻(xiàn)[26]算法與本文算法進(jìn)行性能對比。

表2 不同最大系統(tǒng)誤差下的正確關(guān)聯(lián)率

由表2可以看出,不論是最大距離誤差還是最大角度誤差,隨著最大系統(tǒng)誤差的逐漸增加,文獻(xiàn)[26]中算法的正確關(guān)聯(lián)率有所下降,因為文獻(xiàn)[26]算法通過對航跡序列中兩兩對應(yīng)的航跡點計算距離組成相離度矩陣進(jìn)行航跡關(guān)聯(lián)判斷,系統(tǒng)誤差的增大會使航跡點的區(qū)間灰數(shù)范圍擴(kuò)大,導(dǎo)致帶系統(tǒng)誤差的航跡距離與航跡實際距離產(chǎn)生較大偏差;而本文算法選取整段距離最近的個平均區(qū)間距離,具有良好的抗差性能,因此一直保持較高的正確關(guān)聯(lián)率。

另外,在判決關(guān)聯(lián)結(jié)果是否歸屬漏關(guān)聯(lián)時,本文算法通過反復(fù)試驗最終確定的漏關(guān)聯(lián)閾值門限是一個變化值,與航跡對具體關(guān)聯(lián)度有關(guān),而文獻(xiàn)[26]算法采取固定值作為閾值門限,相對于變化的閾值門限更加穩(wěn)定,因此本文算法的漏關(guān)聯(lián)率比文獻(xiàn)[26]算法高。

局部節(jié)點傳感器開始采樣時機(jī)或采樣頻率的不同易造成航跡的異步不等速率,而傳統(tǒng)關(guān)聯(lián)算法的假設(shè)前提中,航跡異步或系統(tǒng)誤差只存在其一。在仿真環(huán)境中,保持局部節(jié)點1,2傳感器測距和測角的最大系統(tǒng)誤差為1 000 m,1°,研究航跡異步的影響。

由于文獻(xiàn)[26]算法是以航跡同步為前提的抗差關(guān)聯(lián)算法,只能在所有航跡序列等長且時間戳一致情況下進(jìn)行關(guān)聯(lián),因此在實驗前先對文獻(xiàn)[26]算法進(jìn)行時域配準(zhǔn)預(yù)處理,使其適應(yīng)航跡異步環(huán)境。

從表3中可以看出,采樣周期以及開機(jī)時機(jī)不同對文獻(xiàn)[26]算法的正確關(guān)聯(lián)率影響較大,這是因為對文獻(xiàn)[26]算法進(jìn)行同步化處理會引入不必要的誤差,影響總體關(guān)聯(lián)質(zhì)量;而本文算法中度量指標(biāo)近鄰區(qū)間距離的求解是在航跡點與航跡序列間尋找相對較近的距離,并未利用時間信息,也不要求航跡序列等長,航跡異步并不會改變各航跡序列對的近鄰區(qū)間距離值,因此本文算法的關(guān)聯(lián)效果沒有受到影響。

表3 不同采樣頻率和開始采樣時機(jī)的正確關(guān)聯(lián)率

3.5 算法復(fù)雜度分析

以同等長度的航跡序列為前提,表4比較了文獻(xiàn)[26]算法和本文算法的乘法、加法運算量,表中為航跡批數(shù),為航跡點數(shù),為本文算法近鄰區(qū)間距離的變量。

表4 算法運算量對比

在實際運算中,乘法耗時會大于加法耗時,顯然,本文算法運算量要高于文獻(xiàn)[26]中算法。這是因為文獻(xiàn)[26]算法只解決了系統(tǒng)誤差下的航跡關(guān)聯(lián)問題,而本文算法可在異步和系統(tǒng)誤差并存情況下直接關(guān)聯(lián),在處理異步航跡時,利用區(qū)間距離信息需要一定的計算量。另外,本文算法的單側(cè)區(qū)間化與雙側(cè)區(qū)間化只是對數(shù)據(jù)的預(yù)處理方式不同,因而單、雙側(cè)區(qū)間化的運算量相同。

圖6比較了不同航跡數(shù)目下各算法的耗時?？梢钥闯?隨著航跡數(shù)目的增加,本文提出的兩種區(qū)間化處理方式耗時相當(dāng),但整體而言,本文算法耗時高于文獻(xiàn)[26]中算法,結(jié)果與表4中的理論分析吻合。

圖6 不同航跡數(shù)目下的耗時對比Fig.6 Time-consuming comparison under different track numbers

4 結(jié) 論

本文提出一種利用近鄰區(qū)間距離的異步抗差關(guān)聯(lián)算法,定義區(qū)間坐標(biāo)序列與區(qū)間坐標(biāo)點間的近鄰區(qū)間距離,并給出系統(tǒng)誤差區(qū)間化方法。對系統(tǒng)誤差先驗信息的要求低,具有良好的抗差性能,且算法可不做時域配準(zhǔn)直接處理航跡異步問題。