一種改進(jìn)的多假設(shè)跟蹤算法

蔣富勤 朱鯤 祝獻(xiàn)

（第七一五研究所 聲納技術(shù)重點(diǎn)實(shí)驗(yàn)室，杭州，310012）

在目標(biāo)檢測(cè)中，提高門(mén)限，可以降低虛警，但同時(shí)也降低了檢測(cè)概率，影響目標(biāo)檢測(cè)，尤其是弱目標(biāo)檢測(cè)。事實(shí)上，對(duì)于虛警，可以通過(guò)后續(xù)觀察予以剔除。因此，在目標(biāo)檢測(cè)過(guò)程中，適當(dāng)降低門(mén)限，提高檢測(cè)概率，允許一定的虛警概率，通過(guò)后續(xù)觀察數(shù)據(jù)來(lái)辨識(shí)哪些是目標(biāo)，哪些是虛警，哪些出現(xiàn)漏報(bào)。

在檢測(cè)概率小于1和存在虛警或雜波情況下的目標(biāo)跟蹤，其主要難點(diǎn)在于數(shù)據(jù)關(guān)聯(lián)。目前，已發(fā)展了許多方法試圖解決這一問(wèn)題。兩種簡(jiǎn)單的方法是強(qiáng)近鄰方法（SN）[1]和最近鄰方法（NN）[2]。SN 關(guān)聯(lián)跟蹤門(mén)內(nèi)最強(qiáng)的測(cè)量。NN則關(guān)聯(lián)跟蹤門(mén)內(nèi)與預(yù)測(cè)值最接近的測(cè)量。隨著虛警概率的增加，這兩種方法無(wú)法實(shí)現(xiàn)目標(biāo)跟蹤。概率數(shù)據(jù)關(guān)聯(lián)（PDA）[3]則選用跟蹤門(mén)內(nèi)所有測(cè)量，而不是其中一個(gè)，賦予它們不同的概率。在多目標(biāo)情況下，除了測(cè)量與測(cè)量之間存在競(jìng)爭(zhēng)外，測(cè)量還可能位于多個(gè)目標(biāo)的跟蹤門(mén)內(nèi)，數(shù)據(jù)關(guān)聯(lián)與跟蹤變得更為困難。其它方法還有全局最近鄰方法（GNN）、聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)（JPDA）[4]、多假設(shè)跟蹤（MHT）[5]、概率多假設(shè)跟蹤（PMHT）[6]，維特比數(shù)據(jù)關(guān)聯(lián)（VDA）[7]等。

1979年，Reid在0-1整數(shù)規(guī)劃方法基礎(chǔ)上，結(jié)合全鄰最優(yōu)濾波器和Bar-Shalom的聚概念，提出了多假設(shè)跟蹤方法。MHT建立多個(gè)候選假設(shè)，通過(guò)后續(xù)觀察數(shù)據(jù)進(jìn)行延遲關(guān)聯(lián)判決，但假設(shè)數(shù)目隨目標(biāo)個(gè)數(shù)和虛警個(gè)數(shù)的增加呈指數(shù)級(jí)增加，需要對(duì)假設(shè)進(jìn)行修剪，刪除低概率的假設(shè)，維持適度規(guī)模的假設(shè)數(shù)目。這也是MHT實(shí)現(xiàn)工程化應(yīng)用的關(guān)鍵步驟。

維特比算法在通信和語(yǔ)音識(shí)別中廣泛使用，它在離散馬爾科夫系統(tǒng)中是最佳的。在數(shù)據(jù)關(guān)聯(lián)中，維特比算法同樣得到應(yīng)用。VDA的關(guān)鍵思想是基于測(cè)量而不是離散狀態(tài)集創(chuàng)建網(wǎng)格圖。網(wǎng)格上的路徑對(duì)應(yīng)一個(gè)數(shù)據(jù)關(guān)聯(lián)序列。維特比算法可確定網(wǎng)格上的最小代價(jià)路徑。本文結(jié)合MHT和VDA的思想，提出了一種改進(jìn)的多假設(shè)跟蹤算法。降低計(jì)算復(fù)雜度，實(shí)現(xiàn)快速目標(biāo)關(guān)聯(lián)與跟蹤。

1 狀態(tài)-空間模型

對(duì)于單陣多目標(biāo)數(shù)據(jù)關(guān)聯(lián)和跟蹤問(wèn)題，為簡(jiǎn)單起見(jiàn)，這里假設(shè)目標(biāo)個(gè)數(shù)為T(mén)，且目標(biāo)相互獨(dú)立，不機(jī)動(dòng)。那么多目標(biāo)跟蹤系統(tǒng)模型可用狀態(tài)-空間模型表示：

其中i= 1,2,… ,T，xi(k)是k時(shí)刻第i個(gè)目標(biāo)的狀態(tài)向量，F(xiàn)(k)是已知的狀態(tài)轉(zhuǎn)移矩陣，vi(k)和wi(k)是獨(dú)立同分布的零均值白高斯噪聲，yj(k)是目標(biāo)測(cè)量，H(k)是測(cè)量矩陣。目標(biāo)和測(cè)量之間的對(duì)應(yīng)關(guān)系i?j未知。在測(cè)量過(guò)程中，目標(biāo)可能存在漏報(bào)和虛警。虛警采用PDA均勻/泊松模型，即虛警測(cè)量值在測(cè)量空間內(nèi)服從均勻分布，虛警個(gè)數(shù)服從泊松分布，其參數(shù)為λ。

2 算法原理

2.1 多假設(shè)跟蹤算法

NN是最簡(jiǎn)單的關(guān)聯(lián)算法，它關(guān)聯(lián)跟蹤門(mén)內(nèi)與預(yù)測(cè)值最接近的測(cè)量，其計(jì)算公式如下：

MHT正是基于延遲判決的思想發(fā)展而來(lái)的。它認(rèn)為每個(gè)新接收到的測(cè)量可能源于新目標(biāo)、虛警或已知目標(biāo)，它通過(guò)一個(gè)有限長(zhǎng)度的時(shí)間滑窗，建立多個(gè)候選假設(shè)，通過(guò)數(shù)據(jù)聚類(lèi)、假設(shè)生成、假設(shè)刪除、假設(shè)矩陣管理等步驟實(shí)現(xiàn)數(shù)據(jù)關(guān)聯(lián)和目標(biāo)跟蹤。由于假設(shè)數(shù)目隨目標(biāo)個(gè)數(shù)和虛警個(gè)數(shù)的增加呈指數(shù)級(jí)增加，需要對(duì)假設(shè)進(jìn)行修剪，刪除低概率的假設(shè)，如 m-最優(yōu)MHT算法。

m-最優(yōu)MHT算法的核心思想是通過(guò)Murty算法搜索前m個(gè)最優(yōu)解，即刪除各時(shí)刻低概率假設(shè)，保留前m個(gè)最優(yōu)假設(shè)，抑制假設(shè)個(gè)數(shù)的急劇增加。這種算法雖然可以緩解計(jì)算量的指數(shù)級(jí)增長(zhǎng)，但當(dāng)目標(biāo)個(gè)數(shù)和虛警數(shù)目較多時(shí)，Murty算法搜索最優(yōu)m個(gè)解依然需要較長(zhǎng)時(shí)間，需要進(jìn)一步優(yōu)化。

2.2 維特比數(shù)據(jù)關(guān)聯(lián)算法

VDA 算法[7]是在網(wǎng)格圖中搜索數(shù)據(jù)關(guān)聯(lián)kΘ中最有可能的序列：

其中，Xk、Yk分別是1～k時(shí)刻的狀態(tài)序列和測(cè)量序列。

關(guān)于測(cè)量序列和關(guān)聯(lián)事件序列的聯(lián)合概率密度可分解為

其中j= 0 ,… ,nk，nk是k時(shí)刻時(shí)網(wǎng)格圖的節(jié)點(diǎn)個(gè)數(shù)，其與測(cè)量個(gè)數(shù)有關(guān)。對(duì)代價(jià)取負(fù)對(duì)數(shù)，問(wèn)題可轉(zhuǎn)化為搜索最小代價(jià)路徑問(wèn)題：

2.3 改進(jìn)的多假設(shè)跟蹤算法

為減少M(fèi)HT計(jì)算量，需要對(duì)假設(shè)生成和假設(shè)刪除等進(jìn)行優(yōu)化。這里，通過(guò)網(wǎng)格圖減少假設(shè)數(shù)目，刪除低概率假設(shè)，實(shí)現(xiàn)快速目標(biāo)關(guān)聯(lián)跟蹤。每個(gè)新接收到的測(cè)量可能源于新目標(biāo)、虛警或已知目標(biāo)，同時(shí)考慮這3種情況計(jì)算復(fù)雜。這里對(duì)于目標(biāo)的關(guān)聯(lián)跟蹤分成兩步。

2.3.1 關(guān)聯(lián)跟蹤已知目標(biāo)。

對(duì)于已知目標(biāo)而言，新目標(biāo)和虛警測(cè)量都是錯(cuò)誤關(guān)聯(lián)的測(cè)量，均可視為虛警。因此，測(cè)量假設(shè)分為兩種情況：源于已知目標(biāo)、源于虛警和新目標(biāo)。

圖1表示k-1時(shí)刻到k時(shí)刻的網(wǎng)格圖。每個(gè)節(jié)點(diǎn)包含目標(biāo)編號(hào)、當(dāng)前時(shí)刻目標(biāo)狀態(tài)和協(xié)方差矩陣、路徑代價(jià)，以及指向前一時(shí)刻的節(jié)點(diǎn)位置。圖1(a)表示位于門(mén)限范圍以?xún)?nèi)的路徑；通過(guò)比較節(jié)點(diǎn)上各路徑的代價(jià)，圖1(b)給出了各節(jié)點(diǎn)選擇的幸存路徑。從圖中可以看出，k時(shí)刻節(jié)點(diǎn)3沒(méi)有與k-1時(shí)刻的節(jié)點(diǎn)關(guān)聯(lián)，認(rèn)為其為虛警。k時(shí)刻節(jié)點(diǎn)1和節(jié)點(diǎn)2均與k-1時(shí)刻節(jié)點(diǎn)1關(guān)聯(lián)，路徑出現(xiàn)分支，需要通過(guò)后續(xù)觀察數(shù)據(jù)確定哪一條是真實(shí)路徑。k-1時(shí)刻節(jié)點(diǎn)2沒(méi)有與后續(xù)節(jié)點(diǎn)關(guān)聯(lián)，該路徑終止，停止跟蹤。如果它是分支路徑之一，認(rèn)為其不是真實(shí)路徑。但實(shí)際上檢測(cè)概率不為1，會(huì)出現(xiàn)漏報(bào)，為此k時(shí)刻設(shè)置新的節(jié)點(diǎn)，關(guān)聯(lián)k-1時(shí)刻未被關(guān)聯(lián)的路徑節(jié)點(diǎn)2，節(jié)點(diǎn)狀態(tài)采用預(yù)測(cè)值。若這條路徑不是真實(shí)路徑，其后續(xù)路徑多采用預(yù)測(cè)值，而不是測(cè)量值與之關(guān)聯(lián)。在一定長(zhǎng)度時(shí)間窗內(nèi)，當(dāng)采用預(yù)測(cè)值次數(shù)或代價(jià)大于某個(gè)門(mén)限時(shí)，停止跟蹤，修剪這條分支路徑，釋放分支期間關(guān)聯(lián)的測(cè)量數(shù)據(jù)。

圖1 網(wǎng)格圖

2.3.2 新目標(biāo)初始化

測(cè)量假設(shè)分為兩種情況：潛在的新目標(biāo)和虛警。在k-p時(shí)刻，若存在m個(gè)未關(guān)聯(lián)的測(cè)量數(shù)據(jù)（即認(rèn)為是虛警的測(cè)量和被修剪的分支測(cè)量），假定其為潛在的新目標(biāo)Newi,i= 1 ,… ,m，重復(fù)第一步的過(guò)程，其中關(guān)聯(lián)的數(shù)據(jù)為k-p～k時(shí)刻未關(guān)聯(lián)的測(cè)量數(shù)據(jù)。到k時(shí)刻時(shí)，若某個(gè)潛在目標(biāo)路徑上關(guān)聯(lián)的測(cè)量數(shù)據(jù)個(gè)數(shù)大于某個(gè)門(mén)限（如Pd*（p+1）,其中Pd為檢測(cè)概率），則認(rèn)為該目標(biāo)為新目標(biāo)，否則認(rèn)為是虛警。

在目標(biāo)跟蹤過(guò)程中，設(shè)置計(jì)數(shù)器q，q

若目標(biāo)1和目標(biāo)2在跟蹤過(guò)程中出現(xiàn)交叉，有時(shí)會(huì)出現(xiàn)交叉之后，1）交叉后目標(biāo)1路徑分配給目標(biāo)2，目標(biāo)2路徑分配給目標(biāo)1，稱(chēng)之為交叉交換；2）交叉之后的兩條路徑均分配給同一個(gè)目標(biāo)，造成另一個(gè)目標(biāo)失跟。為此，若目標(biāo)間距離小于某個(gè)門(mén)限值，認(rèn)為其可能會(huì)出現(xiàn)交叉，對(duì)其進(jìn)行數(shù)據(jù)關(guān)聯(lián)時(shí)應(yīng)考慮：1）門(mén)限內(nèi)存在多個(gè)測(cè)量時(shí)，每個(gè)目標(biāo)至少分配一個(gè)節(jié)點(diǎn)，避免目標(biāo)失跟；2）根據(jù)一段時(shí)間的目標(biāo)路徑數(shù)據(jù)進(jìn)行曲線擬合，預(yù)測(cè)當(dāng)前時(shí)刻測(cè)量值，而不是采用一步預(yù)測(cè)值。在這兩個(gè)原則基礎(chǔ)上選擇使代價(jià)最小的數(shù)據(jù)關(guān)聯(lián)方案。

3 仿真結(jié)果

仿真中，共有6個(gè)目標(biāo)，測(cè)量數(shù)據(jù)為目標(biāo)方位，其方位標(biāo)準(zhǔn)差σ為0.5o，檢測(cè)概率Pd為0.8，虛警值服從均勻分布，其個(gè)數(shù)服從泊松分布，參數(shù)λ取4和8。改進(jìn)的MHT算法結(jié)果見(jiàn)圖2。

圖2 多目標(biāo)關(guān)聯(lián)跟蹤結(jié)果

圖2（a）和（c）是λ取4和8時(shí)的測(cè)量數(shù)據(jù)，圖 2（b）和（d）為相應(yīng)的關(guān)聯(lián)跟蹤結(jié)果，不同顏色代表不同目標(biāo)的關(guān)聯(lián)跟蹤結(jié)果。從圖中可以看出，改進(jìn)的MHT算法可以實(shí)現(xiàn)虛警環(huán)境下的多目標(biāo)關(guān)聯(lián)與跟蹤。

在個(gè)人計(jì)算機(jī)上，采用 m-最優(yōu) MHT算法（m=2，延遲判決長(zhǎng)度N=5）時(shí)，完成上述6個(gè)目標(biāo)的跟蹤（λ=4）需要845 s，不使用新目標(biāo)初始化功能時(shí)需要31.5 s；而相同情況下，采用改進(jìn)的MHT算法前者只需2.9 s，后者只需1.5 s，運(yùn)算速度得到大幅提高。

假定跟蹤后得到的方位值與真實(shí)值相差 1°以?xún)?nèi)，則認(rèn)為該時(shí)刻檢測(cè)到目標(biāo)，那么跟蹤前后參數(shù)λ取不同值時(shí)的檢測(cè)概率Pd如圖3所示（跟蹤前檢測(cè)概率恒定，50次蒙特卡洛仿真，6個(gè)目標(biāo)結(jié)果取平均值），檢測(cè)性能得到提高。

圖3 跟蹤前后檢測(cè)性能變化曲線

圖4給出目標(biāo)起始時(shí)刻不同時(shí)的關(guān)聯(lián)跟蹤結(jié)果，驗(yàn)證了本算法新目標(biāo)初始化的有效性。

圖4 新目標(biāo)初始化關(guān)聯(lián)跟蹤結(jié)果

對(duì)于交叉目標(biāo)，考慮方位上較遠(yuǎn)目標(biāo)和相近目標(biāo)交叉兩種情況，如圖5所示。

圖5 交叉目標(biāo)關(guān)聯(lián)跟蹤結(jié)果

改進(jìn)的MHT算法對(duì)交叉目標(biāo)進(jìn)行跟蹤時(shí)，雖沒(méi)有交叉后兩條路徑分配給同一個(gè)目標(biāo)，但交叉交換現(xiàn)象依然存在，表1給出不同檢測(cè)概率和虛警個(gè)數(shù)時(shí)的交叉交換次數(shù)（表中前一個(gè)數(shù)字表示較遠(yuǎn)目標(biāo)的交叉交換次數(shù)，后一個(gè)數(shù)字表示相近目標(biāo)的交叉交換次數(shù)）。從表中可以看出，檢測(cè)概率越高、虛警個(gè)數(shù)越少，完成交叉過(guò)程越短，出現(xiàn)交叉交換的可能性越低。

表1 出現(xiàn)交叉交換的次數(shù)（50次蒙特卡洛仿真）

4 總結(jié)

在檢測(cè)概率小于1和存在虛警或雜波情況下的目標(biāo)跟蹤，其主要難點(diǎn)在于數(shù)據(jù)關(guān)聯(lián)。理想情況下，MHT算法是數(shù)據(jù)關(guān)聯(lián)問(wèn)題的最優(yōu)解，但計(jì)算量大。本文結(jié)合VDA和MHT，提出了一種改進(jìn)的MHT算法，它通過(guò)對(duì)假設(shè)生成和假設(shè)刪除過(guò)程進(jìn)行優(yōu)化，分步進(jìn)行已知目標(biāo)的關(guān)聯(lián)跟蹤和新目標(biāo)的初始化，降低計(jì)算復(fù)雜度，實(shí)現(xiàn)快速目標(biāo)關(guān)聯(lián)跟蹤，并且提高了檢測(cè)性能。對(duì)于交叉目標(biāo)，采用曲線擬合方式預(yù)測(cè)當(dāng)前時(shí)刻的測(cè)量值，降低交叉交換出現(xiàn)的可能。通過(guò)仿真分析，驗(yàn)證了該方法的有效性。

[1] RONG LI X, ZHI XIAORONG. A refined strongest neighbor filter for tracking in clutter[C]. Proceedings of the 35thconference on Decision and control, Kobe, 1996:2557-2562.

[2] RONG LI X, BAR-SHAALOM Y. Tracking in clutter with nearest neighbor filters: analysis and performance[J]. IEEE transactions on aerospace and electronic systems, 1996, 32(3):995-1010.

[3] BAR-SHALOM Y, KIRUBARAJAN T, LIN X.Probabilistic data association techniques for target tracking with applications to sonar,radar and EO sensors[J]. IEEE A&E systems magazine, 2005, 20(8): 37-56.

[4] BAR-SHALOM Y, BLAIR W D. Multitarget-multisensor tracking: applications and advances Volume III[M]. Norwood,MA: Artech House, 2002: 175-184.

[5] WILLETT PETER, LUGINBUHL TOD, EVANGELOS GIANNOPOULOS. MHT tracking for crossing targets[C]. SPIE conference on Signal and Data Processing of Small Targets, 2007:66991C:1-12.

[6] WILLETT PETER, RUAN YANHUA, STREIT ROY.PMHT: problems and some solutions[J]. IEEE transactions on aerospace and electronic systems, 2002, 38(3): 738-754.

[7] PULFORD G W. Multi-target viterbi data association,information fusion[C]. The 9th International Conference of ICIF, 2006.