胡 敏，邱金鳳，許 紅，李榮鋒

(1 航天南湖電子信息技術(shù)股份有限公司， 湖北 荊州 434000；2.海軍工程大學(xué)電子工程學(xué)院， 武漢 430033)

多假設(shè)跟蹤(Multiple Hypothesis Tracking，MHT)[1-3]采用一種延遲判決邏輯，通過(guò)建立和傳播多個(gè)候選假設(shè)，由后續(xù)的量測(cè)數(shù)據(jù)來(lái)解決當(dāng)前時(shí)刻的數(shù)據(jù)關(guān)聯(lián)問(wèn)題。由于利用了多個(gè)時(shí)刻的量測(cè)信息，理論上MHT的性能優(yōu)于傳統(tǒng)的全局最近鄰(Global Nearest Neighbor，GNN)[4]、概率數(shù)據(jù)關(guān)聯(lián)(Probability Data Association，PDA)[5]和聯(lián)合數(shù)據(jù)關(guān)聯(lián)(Joint Probability Data Association，JPDA)[6]，因而被廣泛應(yīng)用于各種多目標(biāo)跟蹤(Multiple Target Tracking，MTT)場(chǎng)景[7-9]。

MHT方法最早由Reid[3]于1979年提出，該方法面向量測(cè)構(gòu)造關(guān)聯(lián)假設(shè)，通過(guò)枚舉可行的全局假設(shè)，并計(jì)算假設(shè)的概率來(lái)給出最優(yōu)的量測(cè)關(guān)聯(lián)結(jié)果。因此，該方法實(shí)質(zhì)上是基于假設(shè)的MHT方法(Hypothesis-oriented MHT，HOMHT)。然而，在復(fù)雜跟蹤場(chǎng)景中，枚舉可行的全局假設(shè)是一個(gè)NP-難問(wèn)題，因此文獻(xiàn)[3]中HOMHT方法難以實(shí)際應(yīng)用。文獻(xiàn)[10]通過(guò)利用Murty 算法來(lái)生成假設(shè)，避免了枚舉操作，減低了HOMHT的計(jì)算復(fù)雜度。文獻(xiàn)[11]提出了面向航跡的MHT方法(Track-oriented MHT，TOMHT)，該方法是一種“自上而下”的方法，其通過(guò)更新的航跡節(jié)點(diǎn)來(lái)生成全局假設(shè)，避免了維持和傳播假設(shè)。相比于HOMHT，TOMHT的計(jì)算復(fù)雜度和實(shí)現(xiàn)難度更低，因而，在MTT領(lǐng)域多采用TOMHT方法[1]。

本文基于TOMHT方法開(kāi)展研究，TOMHT的難點(diǎn)在于最優(yōu)全局假設(shè)的生成。針對(duì)該問(wèn)題，基于圖論的TOMHT方法近年來(lái)倍受關(guān)注。文獻(xiàn)[12]指出最優(yōu)假設(shè)生成問(wèn)題等價(jià)于最大權(quán)重獨(dú)立集(Maximum Weighted IndependentSet，MWIS)問(wèn)題。為了引用方便，本文將傳統(tǒng)的基于(Multi-dimensional Assignment，MDA)和基于MWIS的MHT方法分別簡(jiǎn)記為MDA-MHT和MWIS-MHT。與MDA-MHT相比，MWIS-MHT具備如下優(yōu)勢(shì)[12-14]：MWIS-MHT在概念上更加簡(jiǎn)潔明了；MWIS是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題已被廣泛研究，因此利用現(xiàn)有的MWIS求解算法可更加高效的求解全局假設(shè)。需要說(shuō)明的是，現(xiàn)有的MWIS-MHT方法的運(yùn)動(dòng)模型均為單一模型，在目標(biāo)機(jī)動(dòng)場(chǎng)景下，會(huì)存在性能損失，并不適合于多機(jī)動(dòng)目標(biāo)場(chǎng)景。

針對(duì)現(xiàn)有的MWIS-MHT方法并不適用于多機(jī)動(dòng)目標(biāo)跟蹤的問(wèn)題，本文將交互式多模型(IMM)算法應(yīng)用于MWIS-MHT，提出了基于交互式多模型的MWIS-MHT方法。所提方法采用多種運(yùn)動(dòng)模型對(duì)機(jī)動(dòng)目標(biāo)進(jìn)行跟蹤，因而更適用于多機(jī)動(dòng)目標(biāo)跟蹤場(chǎng)景。此外，相比于MDA-MHT，所提方法基于MWIS生成最優(yōu)假設(shè)，具有更低的計(jì)算復(fù)雜度。仿真實(shí)驗(yàn)驗(yàn)證了所提算法的有效性。

1 MHT問(wèn)題描述

MHT通過(guò)建立多個(gè)候選假設(shè)并通過(guò)假設(shè)評(píng)估及管理技術(shù)來(lái)實(shí)現(xiàn)多目標(biāo)跟蹤。為了便于后文描述算法原理，本文將MHT中常用的術(shù)語(yǔ)總結(jié)于表1，其中部分術(shù)語(yǔ)定義借鑒于文獻(xiàn)[15]。

表1 MHT常用術(shù)語(yǔ)定義

MHT考慮量測(cè)數(shù)據(jù)可能源于新生目標(biāo)、虛警或已有航跡。為了便于描述算法，MHT方法有如下假設(shè)：傳感器的檢測(cè)概率為PD；虛警和新目標(biāo)分別服從空間密度為λF和λN的泊松分布；一個(gè)目標(biāo)在不漏檢條件下僅能產(chǎn)生一個(gè)量測(cè)。

此外，為了便于后文描述算法，本節(jié)給出量測(cè)數(shù)據(jù)和航跡的定義。假設(shè)第k時(shí)刻傳感器接收的量測(cè)數(shù)據(jù)定義為

(1)

(2)

2 所提方法原理與實(shí)現(xiàn)

本節(jié)將IMM算法引入到MWIS-MHT框架中，提出了適用于機(jī)動(dòng)目標(biāo)的多假設(shè)跟蹤方法。為了行文方便，本文將所提方法簡(jiǎn)記MWIS-IMM-MHT，其原理框圖如圖1。

圖1 MWIS-IMM-MHT方法原理框圖

下面對(duì)MWIS-IMM-MHT的關(guān)鍵實(shí)現(xiàn)步驟進(jìn)行詳細(xì)論述。

2.1 IMM算法原理

機(jī)動(dòng)目標(biāo)跟蹤一直是目標(biāo)跟蹤領(lǐng)域的研究熱點(diǎn)，其難點(diǎn)在于目標(biāo)運(yùn)動(dòng)的不確定性[16]。IMM算法[17]通過(guò)引入模型交互步驟，具有1 階廣義偽貝葉斯(Generalized Pseudo Bayesian，GPB)算法的計(jì)算復(fù)雜度優(yōu)勢(shì)，同時(shí)兼?zhèn)? 階GPB 算法的跟蹤性能，實(shí)現(xiàn)了跟蹤精度與算法復(fù)雜度的折中。因此，IMM算法被廣泛應(yīng)用于各類機(jī)動(dòng)目標(biāo)跟蹤問(wèn)題。在給定的跳變線性馬爾科夫狀態(tài)空間模型[17]的基礎(chǔ)上，IMM算法包含如下步驟：

1) 模型交互：

(3)

2) 模型預(yù)測(cè)：

(4)

3) 模型更新：

(5)

需要說(shuō)明的是，模型的詳細(xì)實(shí)現(xiàn)過(guò)程見(jiàn)文獻(xiàn)[18]。

2.2 航跡得分

(6)

(7)

(8)

(9)

其中，λN表示新生目標(biāo)的空間密度。航跡的狀態(tài)通過(guò)概率序列比檢驗(yàn)(Sequential Probability Ratio Test，SPRT)[2]確定。具體來(lái)所，SPRT通過(guò)將航跡得分與預(yù)先設(shè)置的刪除門(mén)限Tl和確認(rèn)門(mén)限Tu進(jìn)行對(duì)比進(jìn)而判斷航跡的狀態(tài)。門(mén)限參數(shù)Tl和Tu的設(shè)置見(jiàn)文獻(xiàn)[2]。

(10)

其中，J表示全局假設(shè)的數(shù)目。

2.3 全局假設(shè)生成

(11)

圖2給出了MWIS生成最優(yōu)全局假設(shè)。

圖2 MWIS生成最優(yōu)全局假設(shè)示意圖

圖2(a)給出了從t=k-2時(shí)刻至t=k時(shí)刻的3株航跡樹(shù)的示意圖，圖中的圓代表了航跡節(jié)點(diǎn)，圓中的數(shù)字表示量測(cè)數(shù)據(jù)序列號(hào)，定義見(jiàn)式。一株航跡樹(shù)由根節(jié)點(diǎn)、分支和葉節(jié)點(diǎn)構(gòu)成，圖2(a)中在第k時(shí)刻總共包含了8條航跡，其航跡標(biāo)簽為{T1，…，T8}。圖2(b)給出了3株航跡樹(shù)在第k時(shí)刻對(duì)應(yīng)的加權(quán)無(wú)向圖的示意圖，圖中的圓代表了第k時(shí)刻航跡節(jié)點(diǎn)，圓中的數(shù)字表示航跡標(biāo)簽，圓外的數(shù)字表示航跡得分，連接邊由航跡的相容關(guān)系確定。圖2(b)中的藍(lán)色航跡節(jié)點(diǎn){T2，T5，T8}為MWIS生成最優(yōu)全局假設(shè)。

2.4 方法實(shí)現(xiàn)的幾個(gè)技巧

為了確保MWIS-IMM-MHT方法的性能及執(zhí)行效率，本文考慮如下技巧：

1) 運(yùn)動(dòng)模型集設(shè)置。運(yùn)動(dòng)模型集直接影響了IMM算法的性能。運(yùn)動(dòng)模型集設(shè)置可以根據(jù)跟蹤場(chǎng)景中的機(jī)動(dòng)目標(biāo)運(yùn)動(dòng)特點(diǎn)的先驗(yàn)知識(shí)[21]進(jìn)行設(shè)計(jì)，也可通過(guò)更為精細(xì)的方法如最小模型距離法、矩匹配法和基于優(yōu)化的方法等。

2) 航跡聚類。航跡聚類將所有的航跡節(jié)點(diǎn)分解為多個(gè)無(wú)共享量測(cè)的子簇，進(jìn)而將復(fù)雜關(guān)聯(lián)問(wèn)題分解為諸多小規(guī)模的關(guān)聯(lián)問(wèn)題。由于子簇間并無(wú)共享量測(cè)，因此子簇的關(guān)聯(lián)問(wèn)題可并行求解。圖2(a)中的3株航跡樹(shù)可分為兩個(gè)子簇，其中航跡樹(shù)1和航跡樹(shù)2為一個(gè)子簇，航跡樹(shù)3為第二個(gè)子簇。一種高效的航跡聚類方法可參考文獻(xiàn)[11]。

(12)

圖3 N-幀剪枝示意圖(N=2)

3 仿真實(shí)驗(yàn)

本節(jié)通過(guò)仿真實(shí)驗(yàn)驗(yàn)證MWIS-IMM-MHT方法對(duì)機(jī)動(dòng)多目標(biāo)的跟蹤性能，并與現(xiàn)有的MWIS-MHT[12]方法進(jìn)行對(duì)比。

3.1 仿真場(chǎng)景設(shè)置

仿真實(shí)驗(yàn)考慮2維空間中的多機(jī)動(dòng)目標(biāo)，目標(biāo)的加速度矢量a(t)=a(t)∠θ(t)滿足半-馬爾科夫過(guò)程[22]。簡(jiǎn)而言之，在隨機(jī)駐留一段時(shí)間后，加速度的大小a(t)和相位θ(t)由某一狀態(tài)跳變至另一狀態(tài)。半-馬爾科夫過(guò)程的完整數(shù)學(xué)模型參考文獻(xiàn)[22]中的式(8)至式(14)。仿真試驗(yàn)中，目標(biāo)的初始加速度大小設(shè)置為0，初始相位在區(qū)間[-π，π]內(nèi)隨機(jī)分布，加速度的參數(shù)設(shè)置與文獻(xiàn)[22]一致。仿真實(shí)驗(yàn)的其他參數(shù)設(shè)置如下：目標(biāo)數(shù)目N=15，目標(biāo)檢測(cè)概率PD=0.95，虛警空間密度λF=1×10-8，采樣時(shí)間T=2 s，觀測(cè)時(shí)間TK=200 s，X軸與Y軸的量測(cè)誤差標(biāo)準(zhǔn)差相同，其標(biāo)準(zhǔn)差σX=σY=50 m。圖4給出了一組隨機(jī)生成的真實(shí)目標(biāo)軌跡的仿真場(chǎng)景。為了能夠生成具有挑戰(zhàn)性的多目標(biāo)航跡，仿真實(shí)驗(yàn)將目標(biāo)航跡的起始和終點(diǎn)中心點(diǎn)均設(shè)置為原點(diǎn)。

圖4 仿真場(chǎng)景示意圖

MWIS-IMM-MHT方法的運(yùn)動(dòng)模型集設(shè)置為：勻速(Constant Velocity，CV)模型、勻加速(Constant Acceleration，CA)模型和Singer模型，模型的先驗(yàn)概率為[1/3 1/3 1/3]，馬爾科夫模型轉(zhuǎn)移概率矩陣為

(13)

模型參數(shù)設(shè)置如下：CV模型的過(guò)程噪聲方差設(shè)置為δCV=10；CA模型的過(guò)程噪聲方差設(shè)置為δCA=1；Singer模型的機(jī)動(dòng)時(shí)間常數(shù)τ=10 s，最大加速度aM=40 m/s2。航跡樹(shù)的最大深度設(shè)置為N=5；MWIS問(wèn)題采用Tabu搜索法求解，其中最大搜索深度設(shè)置為L(zhǎng)=10，最大迭代次數(shù)設(shè)置為nmax=50；新生目標(biāo)空間密度λN=1×10-8。SPRT的參數(shù)設(shè)置為：虛假航跡確認(rèn)概率α=10-6；真實(shí)航跡檢測(cè)概率β=10-3。本文將采用CV模型、CA模型和Singer模型的MWIS-MHT分別簡(jiǎn)記為MWIS-CV-MHT、MWIS-CA-MHT和MWIS-Singer-MHT，其過(guò)程噪聲方差參數(shù)設(shè)置如下：MWIS-CV-MHT中的過(guò)程噪聲方差設(shè)置為δCV=400，MWIS-CA-MHT的過(guò)程噪聲方差設(shè)置為δCA=10，MWIS-Singer-MHT中的最大加速度設(shè)置為aM=80 m/s2。需要說(shuō)明的是，單模型MWIS-MHT的過(guò)程噪聲取值更大的目的是為了擴(kuò)大跟蹤器的適用范圍。

為了能夠評(píng)估算法的關(guān)聯(lián)性能、估計(jì)精度和運(yùn)行效率，本文借鑒文獻(xiàn)[13-14]中的評(píng)估指標(biāo)，采用如下指標(biāo)：

1) 真實(shí)航跡數(shù)目NT。真航跡定義為由跟蹤算法給出的航跡中至少有50% 的量測(cè)來(lái)自同一個(gè)目標(biāo)。該指標(biāo)主要評(píng)估關(guān)聯(lián)的正確性及航跡的連續(xù)性。

2) 虛假航跡數(shù)目Nf。不滿足真航跡定義的航跡。該指標(biāo)主要評(píng)估關(guān)聯(lián)的正確性。

3) 航跡的誤關(guān)聯(lián)率RMC。所有真航跡中誤關(guān)聯(lián)的量測(cè)點(diǎn)數(shù)目與真航跡長(zhǎng)度之和的比值。顯然RMC越小越好，理想條件下RMC=0。該指標(biāo)主要評(píng)估關(guān)聯(lián)的正確性。

4) 位置均方根誤差Rp。根據(jù)算法估計(jì)的目標(biāo)位置與真實(shí)航跡的目標(biāo)位置計(jì)算位置的均方根誤差。該指標(biāo)主要評(píng)估算法的位置估計(jì)精度。

5) 速度均方根誤差Rv。根據(jù)算法估計(jì)的目標(biāo)速度和真實(shí)航跡的目標(biāo)速度計(jì)算速度均方根誤差。

6) (Optimal Subparrern Assignment，OSPA)距離。OSPA距離是用來(lái)衡量集合之間差異程度的距離度量，可綜合評(píng)估目標(biāo)的狀態(tài)估計(jì)精度及目標(biāo)數(shù)目估計(jì)的準(zhǔn)確性。

7) 運(yùn)行時(shí)間TE。TE定義為算法處理一幀數(shù)據(jù)的機(jī)器運(yùn)行平均時(shí)間。該指標(biāo)主要評(píng)估算法的執(zhí)行效率。

3.2 實(shí)驗(yàn)結(jié)果與分析

圖5給出了圖4場(chǎng)景中MWIS-CV-MHT和MWIS-IMM-MHT方法的跟蹤軌跡和OSPA曲線。由于現(xiàn)有的MWIS-MHT軌跡均是基于CV模型的，因此圖5僅僅給出了MWIS-CV-MHT軌跡。圖5(a)和圖5(b)中的綠色點(diǎn)表示量測(cè)點(diǎn)跡(包含虛警和真實(shí)目標(biāo))，藍(lán)色軌跡為目標(biāo)真實(shí)軌跡，紅色軌跡為跟蹤算法輸出的軌跡。由圖5(a)和圖5(b)可知：MWIS-CV-MHT軌跡出現(xiàn)了航跡中斷問(wèn)題，而MWIS-IMM-MHT跟蹤航跡連續(xù)穩(wěn)定。由圖5(c)可知：初始時(shí)刻MWIS-CV-MHT軌跡和MWIS-IMM-MHT軌跡的OSPA曲線相當(dāng)，這是由于仿真實(shí)驗(yàn)的初始運(yùn)動(dòng)均為勻速運(yùn)動(dòng)，而當(dāng)目標(biāo)機(jī)動(dòng)后，MWIS-CV-MHT的OSPA曲線顯著高于MWIS-IMM-MHT軌跡。這是由于MWIS-CV-MHT曲線采用了較大方差的過(guò)程噪聲，因此濾波器的去噪能力顯著下降，同時(shí)航跡中斷也會(huì)引起OSPA曲線抬升。

表2給出了100次蒙特卡羅仿真實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果。由表可知，MWIS-IMM-MHT的NT與真實(shí)目標(biāo)數(shù)目15最為接近，這表明了所提方法在跟蹤連續(xù)性方面具備最優(yōu)性能。從跟蹤精度來(lái)看，MWIS-IMM-MHT的位置均方根誤差和速度均方根誤差最小，因而具有最優(yōu)的狀態(tài)估計(jì)精度。從關(guān)聯(lián)性能來(lái)看，MWIS-IMM-MHT并非最優(yōu)，但其性能也優(yōu)于MWIS-CA-MHT和MWIS-Singer-MHT。從運(yùn)行效率來(lái)看，MWIS-IMM-MHT的單幀處理時(shí)間約為現(xiàn)有方法的兩倍，計(jì)算復(fù)雜度并沒(méi)有顯著增加。

圖5 跟蹤軌跡和OSPA曲線

表2 100次蒙特卡羅仿真結(jié)果

4 結(jié)論

提出了一種多假設(shè)跟蹤方法。將交互式多模型算法引入，采用多種運(yùn)動(dòng)模型對(duì)機(jī)動(dòng)目標(biāo)進(jìn)行跟蹤，該方法能兼顧計(jì)算效率上的優(yōu)勢(shì)。仿真結(jié)果表明：相比于單模型方法，多假設(shè)跟蹤方法能提升跟蹤的連續(xù)性和狀態(tài)估計(jì)的精度，更適用于多機(jī)動(dòng)目標(biāo)跟蹤問(wèn)題。