基于k近鄰平均距離的異步航跡關聯算法

衣 曉, 曾 睿,2,*

(1. 海軍航空大學, 山東 煙臺 264001; 2. 中國人民解放軍92325部隊, 山西 大同 037001)

0 引 言

對于分布式多傳感器多目標跟蹤系統,由于各局部節點獨立工作,每個局部節點一般都有多條目標航跡信息,如何判斷來自不同局部節點的航跡是否對應同一個目標,即航跡關聯,是融合中心需要解決的關鍵問題之一。而各局部節點配置傳感器的采樣周期不一致或者開機時機不同,使得融合中心收到的局部航跡往往是異步不等速率的,增加了航跡關聯的難度。

對異步航跡關聯問題,傳統的解決思路是進行時間配準,將異步航跡轉換為同步航跡進行處理。常用的時間配準方法有最小二乘法和內插外推法。文獻[8]通過偽測量技術,將來自不同傳感器的測量值和濾波值重建到一個合適的時間點,再利用經典分配算法實現異步關聯。文獻[9]利用勻角速度變換率插值法,將多傳感器的時間對齊,再用局部尋優方法進行關聯。文獻[10]基于灰色關聯的思想,以先整體后局部的次序分兩級關聯修正灰色關聯矩陣,并利用灰色關聯度最大值方法實現關聯。文獻[12]針對分叉軌跡、交叉軌跡和組合軌跡在關聯中正確率不高的問題,基于加權思想獲取關聯質量,引入信息散度構造加權關聯圖進行關聯。文獻[13]基于模糊理論,選取部分關聯影響因素進行加權處理,計算得到綜合模糊隸屬度曲線,利用雙門限檢測確定關聯對實現關聯。但文獻[8-13]算法均需以時間配準為前提,導致航跡數據的誤差累加,影響航跡關聯算法的性能。文獻[14]把不等長實數序列轉換為等長區間數序列,再運用灰關聯模型和最大關聯準則進行關聯,算法無需時域配準,但航跡點被區間數取代,引入了一定的誤差,影響關聯的正確率。

針對上述問題,本文提出一種基于近鄰平均距離的航跡關聯算法,定義一種新的序列距離度量,通過計算航跡序列與單一航跡點相距最近的個平均距離作為航跡序列與單一航跡點的距離,進而得到不等長航跡序列之間的灰色關聯度,利用多維分配實現航跡關聯。該方法無需時域配準,可對異步不等長航跡序列進行直接關聯,并且很大程度保證了航跡信息的原始性與完整性,可顯著提高正確關聯率。

1 序列相似度度量

坐標序列與坐標點間的近鄰平均距離

設非空坐標序列={(1),(2),…,()},其中坐標點()=((),(),())∈,=1,2,…,,若對任意坐標點=(,,)∈,有距離

設≤≤…≤≤…≤按非減次序排列,則稱

(1)

為坐標序列與坐標點間的近鄰平均距離。

不等長坐標序列間的相似度

設坐標序列集合={,,…,,…,}和坐標序列={(1),(2),…,()},其中坐標點()=((),(),())∈,且序列與長度不等,則坐標序列與坐標序列的相似度定義為

(2)

式中:

(3)

表示坐標序列與坐標序列的灰關聯系數。其中,=1,2,…,;=1,2,…,;實數∈[0,1]表示分辨系數;()=-()=(,())。

定義1與定義2中坐標變量均為三維坐標,因此適用于三維空間;若定義1與定義2中坐標變量用二維坐標表示,則可適用于二維平面。

2 基于k近鄰平均距離的航跡關聯算法

2.1 基本思想

假設兩局部節點、對公共觀測區域內的多批目標實施跟蹤,輸出的航跡號集合分別為

2.2 異步航跡相似度的計算

假設各局部節點異步且采樣速率不同,為融合中心固定的一個時間處理周期,以融合中心第個處理周期[(-1),]為例,局部節點、跟蹤上報的航跡批數分別為,,則上報的目標航跡集合()可記為

圖1 局部節點對目標的測距和測角示意圖Fig.1 Diagram of cocalnode ranging and angle measurement of target

(4)

利用式(4),可將局部節點的第條航跡序列記為

則來自局部節點的第條航跡可記為

以局部節點的全部航跡作為比較序列,局部節點的第條航跡作為參考序列,利用坐標序列定義航跡點坐標關聯列向量為

(5)

式中:前行表示比較序列的航跡數據;第+1行表示參考序列的航跡數據。

根據航跡異步不等速率的不同情況討論的取值問題。

(1) 局部節點采樣速率一致、開機時機不一致

如圖2所示,可以看出,局部節點、的航跡點交叉分布,因此,可用局部節點的航跡點與局部節點航跡中對應時刻前后的臨近兩個航跡點的平均距離作為局部節點航跡點與局部節點航跡序列的距離,故取2時關聯效果最佳。

圖2 局部節點時延示意圖Fig.2 Diagram of local node delay

(2) 局部節點開機時機一致、采樣速率不一致

圖3 不等長航跡示意圖Fig.3 Diagram of unequal length track

(3) 局部節點采樣速率和開機時機都不一致

(6)

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

根據定義1中對坐標點與坐標序列間距離的定義,計算比較序列與參考序列間的近鄰平均距離矩陣為

(7)

式中:

(8)

進一步利用定義2可以求得局部節點的第條航跡與局部節點的第條航跡間的灰色關聯度為

(9)

式中:

(10)

2.3 異步航跡關聯判決

利用經典分配法對灰色關聯度進行航跡關聯判決,先分別對局部節點上報的條航跡和局部節點上報的條航跡計算灰色關聯度,將其組成×維灰色關聯度矩陣,通過對分配問題的求解找出全局最優航跡關聯對即可。

令變量

(11)

將目標函數記為

(12)

構成以下二維分配問題

(13)

圖4給出了基于近鄰平均距離的異步航跡關聯算法流程圖。

圖4 異步航跡關聯算法流程圖Fig.4 Flow chart of asynchronous track-to-track association algorithm

3 仿真分析與驗證

3.1 仿真環境

假設分布式系統中有兩個2局部節點對公共區域內的20批目標持續跟蹤觀測35 s,若局部節點1、2異地配置,坐標分別為(0,0)km、(100,0)km,局部節點1的采樣周期為=02 s,局部節點2的采樣周期為=05 s,局部節點2開機時機比局部節點1延遲02 s。

假設所有觀測目標都處于二維平面勻速直線運動狀態,且起始運動方向和初速度隨機分布在0～2π rad、200～400 m/s內。局部節點1的測距和測角誤差分別為1=150 m、1=003 rad;局部節點2的測距和測角誤差分別為2=180 m、2=002 rad。

采用正確關聯率作為航跡關聯結果的評價指標:

(14)

式中:()為融合中心在第個處理周期內正確關聯的航跡批數;為仿真實驗的蒙特卡羅次數;為局部節點觀測目標航跡的總批數。

3.2 k的取值分析

對取值做出簡要理論分析:如若取值為1,相當于未對異步航跡情況做出處理。

表1給出了≥2時的正確關聯率和耗時對比?？梢钥吹?隨著取值由2增加到7,耗時增加明顯,這是因為取值增大會導致計算量明顯增加。

表1 k取值不同的耗時變化Table 1 Change in time for different values of k

表2給出了不同取值和采樣周期的正確關聯率?？梢钥吹?若局部節點1、2采樣周期比值小于等于1,則正確關聯率在取值為2時最大;若局部節點1、2采樣周期比值大于1小于等于2,則正確關聯率在取值為3時最大;若局部節點1、2采樣周期比值大于2,則正確關聯率固定在取值為4時最大。這是由于若采樣周期比值較小,則說明獲得的航跡序列數目相差甚微,此時若取值過大,則與參考航跡序列點距離較遠的比較航跡序列點也會參與航跡距離的計算,使關聯正確率降低;若采樣周期比值較大,則表示航跡序列數目相差甚多,此時若取值過小,則相當于用較少的航跡點間距離代替整條航跡間距離進行計算,易因數據不夠充分而導致正確率降低。

表2 不同k取值和采樣周期比的正確關聯率變化Table 2 Comparison of correct associating rates for different values on k and the ratio of sampling periods

3.3 算法性能比較與分析

為驗證本文算法的可行性和優越性,實施120次蒙特卡羅仿真實驗,改變實驗條件,對不同算法之間的性能進行比較分析。

圖5給出了不同算法的航跡正確關聯率對比?？梢钥吹?由于文獻[16]算法中的離散度屬于統計學度量,需要一定的數據量作為前提,因此正確關聯率受采樣時間長短的影響較大;文獻[17]算法利用最小二乘法實現異步航跡同步化,估計誤差傳播會導致正確關聯率較低;文獻[14]算法由于采用虛實混合變換方法對異步航跡進行同步,沒有誤差傳播,因此正確關聯率較高,但將實數序列變換為區間數和實數的混合序列會使航跡計算精度降低;本文算法利用序列距離度量,對異步航跡直接關聯,沒有誤差的傳播和引入,因此從采樣初期起就一直保持很高的正確關聯率。

圖5 不同算法的正確關聯率對比Fig.5 Comparison of correct associating rates for different algorithms

圖6給出了不同目標航跡數目下4種算法的耗時對比?？梢钥闯?隨著目標數目從10增加到40,各算法的耗時也在逐步增大,其中文獻[14]算法耗時最長,這是由于該算法需要對航跡序列的大部分航跡實數點做區間數變換處理,過程較為繁瑣;文獻[16]算法耗時較高,因為算法中的離散度求取包含標準差計算,因此計算量較大;文獻[17]算法作為早期經典算法,較為簡單,因此耗時最短;而本文算法沒有對異步航跡序列做變換處理,只需對不等長航跡序列直接計算出航跡點距離的最短平均值即可,因此耗時也較短。

圖6 不同目標航跡數目的耗時Fig.6 Time consum for different target track numbers

3.4 異步航跡關聯有效性分析

圖7比較了兩局部節點采樣率不同情況下4種算法的正確關聯率。隨著采樣率相差越來越明顯,即異步航跡序列點的數目相差變大,可以看出,文獻[16]算法主要比較兩條航跡的空間位置相似性,當航跡點數目不滿足一定的統計學數據量時,正確關聯率會有一定波動;文獻[17]算法的正確關聯率下降最為明顯,這是因為通過最小二乘法對異步航跡序列同步化,需要對兩條不等長航跡序列進行插值補齊,異步航跡點數目相差越大,需要補齊的航跡點越多,估計傳播越大;而本文算法和文獻[14]算法的正確關聯率受其影響不大,穩定性較佳,因為兩個算法都是利用距離度量來判斷兩條航跡的相似性,對航跡點數目差異不敏感。

圖7 正確關聯率隨采樣率之比的變化Fig.7 Change of the correct correlation rate with the ratio of the sampling rate

由表3可知,無論是開機時間還是采樣周期,對本文算法的正確關聯率都無明顯影響。這是因為采樣周期不同只是導致航跡點數目不一致,但本文算法核心是計算單一航跡點與其他航跡序列的近鄰平均距離,并不要求航跡等長;局部節點開機存在時間差異會導致上傳的航跡點時間不一致,但本文算法中對航跡序列間距離的求解并未利用時間信息,所以不需要航跡點的時刻一一對應。

表3 不同采樣周期和開機時機的正確關聯率對比Table 3 Comparison of correct associating rates for different sampling periods and startup times

3.5 算法其他性能分析

改變仿真環境中目標航跡總數,目標密集程度對算法正確關聯率的影響如圖8所示?？梢钥闯?在目標數目增多時,文獻[14]算法的正確關聯率下降最為明顯,這是因為異步航跡區實變換后,區間重合度較高,以航跡全部數據點求解的傳統距離容易在數值上接近,難以辨別;文獻[17]算法雖然比較穩定,但正確關聯率較低;文獻[16]算法正確關聯率較穩定,這是因為該算法基于離散度,涉及均值與方差的求解,單一數據對其影響較大,故即便航跡數目增加,只要航跡非同源,離散度對其辨別能力一直較高;本文算法僅取距離最近的個點計算近鄰平均距離,可有效增加非同源航跡間距離的差異度,故正確關聯率受目標數目影響較小。

圖8 不同目標數目的正確關聯率Fig.8 Correct associating rates of different targets number

改變仿真環境中的噪聲分布形式,算法正確關聯率的變化如表4所示。由表4中數據可知,本文算法在高斯、瑞利、指數和均勻4種噪聲分布形式下均能保持較高的正確關聯率,基本不受噪聲分布形式的影響。

表4 不同噪聲分布形式的正確關聯率Table 4 Correct associating rates of different noise distributions forms

4 結 論

為解決異步不等速率航跡關聯問題,本文給出不等長航跡序列間的距離計算規則,用航跡序列與航跡點的距離取代傳統兩航跡點間距離,可對目標航跡序列直接計算距離,最大程度保證了航跡信息的完整性和原始性,避免了誤差的引入,具有很高的關聯正確率。

算法無需時域配準,可對異步航跡直接關聯,能有效克服來自局部節點采樣周期不一致和開機時間不同造成的影響,且不受目標數目密集程度影響,不受噪聲分布影響,具有良好的抗噪能力。