基于時間滑窗的混合Hausdorff距離航跡關(guān)聯(lián)算法?

李寅龍 張?zhí)焓?/p>

（海軍航空大學(xué) 煙臺 264001）

1 引言

在分布式多傳感器目標(biāo)跟蹤系統(tǒng)中，每個傳感器負(fù)責(zé)各區(qū)域的目標(biāo)檢測與跟蹤，若收集不同目標(biāo)的航跡序列信息，對采集到的航跡序列信息是否屬于同一目標(biāo)進(jìn)行判斷是態(tài)勢統(tǒng)一的關(guān)鍵，影響著指揮員的最終決策，因此眾多學(xué)者對航跡關(guān)聯(lián)問題開展研究［1～2］。航跡關(guān)聯(lián)算法在實際中有很多應(yīng)用，例如多目標(biāo)跟蹤空中交通管制系統(tǒng)等。自20世紀(jì)70年代Singer等提出這一課題以來，學(xué)術(shù)界涌現(xiàn)出大批優(yōu)秀的航跡關(guān)聯(lián)算法，國內(nèi)外學(xué)者對各類航跡關(guān)聯(lián)的理論和方法進(jìn)行了大量的研究［3～4］。

Hausdorff距離可用于衡量兩個集合的相似程度，是集合距離的一種度量方式，文獻(xiàn)［5］利用單向Hausdorff距離比較建筑物輪廓與最佳擬合外接矩形的相似程度，使高分辨率遙感圖像下的建筑物輪廓精度得到有效提升。文獻(xiàn)［6］利用Hausdorff距離建立配電網(wǎng)饋線區(qū)域兩端零序電流暫態(tài)分量幅值特征匹配度，能夠在不同環(huán)境下有效定位故障區(qū)段。文獻(xiàn)［7］融合K-means思想和Hausdorff距離，解決了點云數(shù)據(jù)的空洞問題。文獻(xiàn)［8］利用Haus?dorff距離對車輛交叉區(qū)域軌跡進(jìn)行聚類，建立識別模型彌補(bǔ)交叉路口軌跡遺漏的問題。文獻(xiàn)［9］提出加權(quán)的Hausdorff距離以解決邊界區(qū)域的像素點分類問題。文獻(xiàn)［10］提出適當(dāng)排序的廣義Hausdorff距離評價點云數(shù)據(jù)的幾何質(zhì)量。文獻(xiàn)［11］研究了基于K-means聚類算法的胸腰椎三維圖，利用Hausdorff距離比較各類脊髓三維圖像自動分割方法。文獻(xiàn)［12］利用Hausdorff距離，構(gòu)建參考模型約束活動輪廓模型的收斂，提高了分割圖像輪廓在噪聲、雜波、遮擋情況下的魯棒性。

以上文獻(xiàn)將Hausdorff距離應(yīng)用于電力故障排除、點云數(shù)據(jù)、醫(yī)學(xué)測量、圖像分割、車輛軌跡識別等各個方向，皆取得了良好的效果。本文將Haus?dorff距離應(yīng)用于多傳感器航跡關(guān)聯(lián)問題，利用Hausdorff距離比較不同航跡集合間的相似程度判決航跡是否關(guān)聯(lián)。由于Hausdorff距離對野值較敏感，數(shù)據(jù)波動會大幅降低航跡關(guān)聯(lián)正確率，因此本文改進(jìn)傳統(tǒng)的Hausdorff距離，且引入位置、速度、方位角等信息提出了混合Hausdorff距離判決航跡關(guān)聯(lián)。針對各地傳感器開機(jī)時間不一致、采樣頻率不一致造成的時間異步問題，提出基于時間滑窗的Hausdorff距離，將傳統(tǒng)的一對一點跡距離變?yōu)橐粚θc跡距離，并且加入時間滑窗以提高時間異步情況下航跡關(guān)聯(lián)的精度。

2 算法原理

2.1 傳統(tǒng)Hausdorff距離的定義

其中，ai∈A，bi∈B。

h(A，B)稱為集合A到B的正向Hausdorff距離，即集合A中數(shù)據(jù)距離集合B中數(shù)據(jù)的最小距離中的最大值，同理可得，h(B，A)稱為反向Hausdorff距離，h(A，B)與h(B，A)中的較大者稱為兩個集合間的Hausdorff距離。

2.2 基于位置的Hausdorff距離

以雷達(dá)A為例，利用單向Hausdorff距離定義航跡集合間距離相似度如下：

2.3 基于速度的Hausdorff距離

在目標(biāo)批數(shù)較少，航跡簡單等情況下實現(xiàn)航跡關(guān)聯(lián)較為輕松，但是在目標(biāo)密集、航跡交叉、分岔、合并等情況下，易產(chǎn)生錯關(guān)聯(lián)、漏關(guān)聯(lián)等情況。因此僅考慮位置因素作為判決航跡關(guān)聯(lián)的標(biāo)準(zhǔn)不夠全面，將航跡集合各時刻速度、方位角引入Haus?dorff距離，共同作為判決航跡關(guān)聯(lián)的標(biāo)準(zhǔn)。

其中，t為雷達(dá)探測時間間隔。

定義基于速度的Hausdorff距離如下

定義航跡集合間速度相似度如下

2.4 基于方位角的Hausdorff距離

當(dāng)目標(biāo)運動模型為勻速直線運動時，實現(xiàn)航跡關(guān)聯(lián)較為簡單，但實際情況中目標(biāo)大多數(shù)做變速非直線運動，因此提出基于方位角的Hausdorff距離作為衡量航跡關(guān)聯(lián)的指標(biāo)之一，可提升在復(fù)雜運動狀態(tài)下航跡關(guān)聯(lián)的正確率。

定義基于方位角的Hausdorff距離如下：

定義航跡集合間方位角相似度如下

2.5 基于時間滑窗的混合Hausdorff距離

綜上所述，結(jié)合基于位置、速度、方位角的Hausdorff距離，定義混合Hausdorff距離如下：

其中W1、W2、W3為加權(quán)系數(shù)因子，W1+W2+W3=1，設(shè)置W1=0.5，W2=0.25，W3=0.25。

定義航跡集合間混合相似度如下：

其中R1、R2、R3為加權(quán)系數(shù)因子，R1+R2+R3=1，設(shè)置 R1=0.5，R2=0.25，R3=0.25。

各地雷達(dá)開機(jī)時間不一致、采樣頻率不同會造成時間異步，導(dǎo)致航跡數(shù)據(jù)錯位，降低航跡關(guān)聯(lián)精度。為解決此問題提出基于時間滑窗的混合Haus?dorrff距離，從原有的一對一Hausdorff距離變?yōu)橐粚θ鼿ausdorff距離，提高時間異步情況下航跡關(guān)聯(lián)的精度。

圖1 時間滑窗示意圖

綜上所述，定義基于時間滑窗的混合Hausdorff距離如下

其中，dist[a，(b，c，d)]代表a與b、c、d的Haus?dorff距離之和。

定義航跡集合間綜合相似度如下

建立基于時間滑窗的混合Hausdorff距離航跡關(guān)聯(lián)算法流程如圖2所示。

圖2 基于時間滑窗的Hausdorff航跡關(guān)聯(lián)算法流程

3 仿真分析

3.1 仿真環(huán)境

假設(shè)兩部異地配置的2D雷達(dá)對公共區(qū)域目標(biāo)進(jìn)行航跡關(guān)聯(lián)，公共探測區(qū)域為邊長10km*10km的矩形。雷達(dá)A的坐標(biāo)為（0，0），雷達(dá)B的坐標(biāo)為（15km，0）。雷達(dá)A的隨機(jī)誤差服從均值為0，方差為2500m2的高斯分布。雷達(dá)B的隨機(jī)誤差服從均值為0，方差為3600m2的高斯分布。雷達(dá)A、B每1s探測一次數(shù)據(jù)，隨機(jī)生成不同批數(shù)航跡數(shù)據(jù)，進(jìn)行500次Monte Carlo仿真實驗。

仿真環(huán)境1：目標(biāo)做勻速直線運動，初始運動速度在300m/s～700m/s之間，初始角度在0～2π之間。雷達(dá)A、B無時間異步，且數(shù)據(jù)野值已被剔除。

仿真環(huán)境2：目標(biāo)做變速非直線運動，速度隨機(jī)在300m/s～700m/s之間，每秒方位角隨機(jī)在0～2π之間。雷達(dá)A、B無時間異步，且數(shù)據(jù)野值已被剔除。

仿真環(huán)境3：在10個目標(biāo)航跡數(shù)據(jù)中隨機(jī)加入3個野值，野值大小隨機(jī)在原數(shù)據(jù)的0.8倍～1.5倍，其余條件與仿真環(huán)境2相同。

仿真環(huán)境4：雷達(dá)A比雷達(dá)B晚開機(jī)0.2s，其余條件與仿真環(huán)境3相同。

3.2 仿真結(jié)果

在仿真環(huán)境2的條件下，圖3為正確關(guān)聯(lián)率隨時間、目標(biāo)批數(shù)變化的曲面。隨著時間、目標(biāo)批數(shù)的增加，正確關(guān)聯(lián)率不斷下降。在時間超過7s、目標(biāo)批數(shù)超過60批后正確關(guān)聯(lián)率下降嚴(yán)重，航跡正確關(guān)聯(lián)率開始低于90%。傳統(tǒng)的航跡關(guān)聯(lián)算法需要大量數(shù)據(jù)支撐，隨著時間增加往往正確關(guān)聯(lián)率越來越高，但本文算法對數(shù)據(jù)量沒有要求，在前期數(shù)據(jù)點較少時，相比其他算法能以極高正確率完成關(guān)聯(lián)，但數(shù)據(jù)點增多后航跡集合易發(fā)生交集，因此正確關(guān)聯(lián)率下降。

圖3 正確關(guān)聯(lián)率與時間及目標(biāo)批數(shù)的關(guān)系

在仿真環(huán)境1、2的條件下，圖4為不同范數(shù)形式下正確關(guān)聯(lián)率與目標(biāo)批數(shù)的變化曲線。傳統(tǒng)的Hausdorff距離利用2范數(shù)進(jìn)行計算，仿真不同范數(shù)形式對本文算法的影響，結(jié)果表明在兩種仿真環(huán)境中2范數(shù)的正確關(guān)聯(lián)率最高，優(yōu)于1范數(shù)和3范數(shù)。從仿真結(jié)果分析本文算法對目標(biāo)機(jī)動運動狀態(tài)下的航跡關(guān)聯(lián)具有較強(qiáng)的魯棒性，在兩種仿真環(huán)境下的正確關(guān)聯(lián)率相差無幾。

圖4 不同范數(shù)形式下本文算法的正確關(guān)聯(lián)率

在仿真環(huán)境1、2、3的條件下，圖5為正確關(guān)聯(lián)率與目標(biāo)批數(shù)的變化曲線。由于仿真環(huán)境3中加入野值，本文算法的正確關(guān)聯(lián)率有所下降，但仍優(yōu)于最近鄰域法，正確關(guān)聯(lián)率能夠保持在80%以上，表明本文算法在野值環(huán)境中有較強(qiáng)的魯棒性。

圖5 不同仿真環(huán)境下各算法的正確關(guān)聯(lián)率曲線

在仿真環(huán)境4的條件下，圖6為各類算法在不同目標(biāo)批數(shù)情況下的正確關(guān)聯(lián)率曲線。仿真環(huán)境4中雷達(dá)開機(jī)時間不一致，造成航跡數(shù)據(jù)錯位。隨著目標(biāo)批數(shù)的增加，各類算法的正確關(guān)聯(lián)率不斷下降，但本文算法在時間異步情況下仍能保持較高的航跡正確關(guān)聯(lián)率，當(dāng)目標(biāo)批數(shù)達(dá)到100批時正確關(guān)聯(lián)率能夠保持在80%以上，仿真結(jié)果表明在時間異步、野值較多的情況下，本文算法性能優(yōu)于傳統(tǒng)的最近鄰域法和灰關(guān)聯(lián)法。

圖6 仿真環(huán)境4下各類算法的正確關(guān)聯(lián)率

在仿真環(huán)境4的基礎(chǔ)上，改變雷達(dá)A、B的采樣率之比，圖7為各類算法在不同采樣比情況下的正確關(guān)聯(lián)率曲線。最近鄰域法根據(jù)各時刻航跡點的距離判決航跡是否關(guān)聯(lián)，因此對采樣比較敏感，當(dāng)采樣比差距懸殊時精度大幅降低。本文算法及灰關(guān)聯(lián)法在不同采樣比的情況下仍能保持高精度關(guān)聯(lián)，且本文算法的性能優(yōu)于灰關(guān)聯(lián)法，航跡正確關(guān)聯(lián)率可穩(wěn)定保持在95%以上。

圖7 不同采樣比下各類算法的正確關(guān)聯(lián)率

4 結(jié)語

本文將Hausdorff距離應(yīng)用于航跡關(guān)聯(lián)問題中，改進(jìn)傳統(tǒng)的Hausdorff距離，定義了基于位置、速度、方位角的混合Hausdorff距離，在此基礎(chǔ)上加入時間滑窗，提出了基于時間滑窗的混合Hausdorff距離航跡關(guān)聯(lián)算法。仿真結(jié)果表明本文算法在目標(biāo)機(jī)動、野值較多、時間異步、雷達(dá)采樣頻率不一致等情況下能夠保持較高的精度與魯棒性，優(yōu)于傳統(tǒng)的最近鄰域法、灰關(guān)聯(lián)法。