陳　杭, 張伯彥, 陳　映

(北京無(wú)線電測(cè)量研究所, 北京 100854)

?

關(guān)聯(lián)深度自適應(yīng)的多假設(shè)跟蹤研究

陳杭, 張伯彥, 陳映

(北京無(wú)線電測(cè)量研究所, 北京 100854)

多假設(shè)跟蹤(multiple hypothesis tracking, MHT)方法是一種在多個(gè)掃描上評(píng)價(jià)關(guān)聯(lián)假設(shè)并由此做出決策的貝葉斯型關(guān)聯(lián)跟蹤方法,此方法能夠在信噪比低10～100倍的狀況下獲得與單掃描方法相當(dāng)?shù)男阅?但同時(shí)會(huì)帶來(lái)相當(dāng)大的計(jì)算量。本文研究了面向航跡MHT中的關(guān)鍵算法,包括航跡得分計(jì)算與航跡樹(shù)的生成、將航跡聚類(lèi)和假設(shè)生成建模為圖論問(wèn)題并求解、N掃描回溯剪枝等,特別關(guān)注了這些算法過(guò)程的實(shí)現(xiàn);提出了一種關(guān)聯(lián)深度自適應(yīng)(adaptive association depth, AAD)方法,使關(guān)聯(lián)深度隨關(guān)聯(lián)場(chǎng)景的復(fù)雜程度自適應(yīng)變化;仿真研究了本文提出的AAD-MHT跟蹤密集目標(biāo)的性能,結(jié)果和分析表明,與深度值固定為6的MHT相比,最大深度為6的AAD-MHT既能保證性能又有效降低了計(jì)算量。

多目標(biāo)跟蹤; 多假設(shè)跟蹤; 數(shù)據(jù)關(guān)聯(lián); 關(guān)聯(lián)深度自適應(yīng)

0　引　言

多目標(biāo)跟蹤(multi-target tracking, MTT)技術(shù)在軍事和民用領(lǐng)域應(yīng)用非常廣泛。在MTT中,航跡狀態(tài)估計(jì)和數(shù)據(jù)關(guān)聯(lián)常耦合在一起,前者基于后者給定的同源量測(cè)序列估計(jì)和預(yù)測(cè)目標(biāo)狀態(tài),后者基于前者確定的狀態(tài)預(yù)測(cè)及量測(cè)數(shù)據(jù)再根據(jù)某種準(zhǔn)則判斷量測(cè)的來(lái)源。就航跡狀態(tài)估計(jì)而言,由于目標(biāo)運(yùn)動(dòng)或觀測(cè)模型的非線性,一般采用非線性濾波方法,如擴(kuò)展卡爾曼濾波(extended Kalman filter, EKF)、無(wú)敏卡爾曼濾波(unscented Kalman filter, UKF)等;針對(duì)目標(biāo)運(yùn)動(dòng)方式的不確定性,可以采用交互式多模型(interactive multiple model, IMM)方法以及變結(jié)構(gòu)多模型(variable structure multiple model, VSMM)方法等。數(shù)據(jù)關(guān)聯(lián)問(wèn)題,由于量測(cè)的多種不確定性,相比濾波估計(jì)問(wèn)題更加困難。量測(cè)的不確定性包括:①量測(cè)來(lái)源不確定,即傳感器量測(cè)可能源于虛警、雜波、干擾或者目標(biāo)、相鄰目標(biāo)等,同時(shí)目標(biāo)也有可能未被檢測(cè)到;②量測(cè)誤差存在并且非線性。早期發(fā)展起來(lái)的數(shù)據(jù)關(guān)聯(lián)方法適用于目標(biāo)不密集環(huán)境下的單目標(biāo)場(chǎng)景,包括最近鄰(nearest neighbor, NN)方法以及概率數(shù)據(jù)關(guān)聯(lián)(probabilistic data association, PDA)方法,將上述方法分別擴(kuò)展到MTT中,即為全局最近鄰(global NN, GNN)方法和聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)(joint PDA, JPDA)方法。還有一些數(shù)據(jù)關(guān)聯(lián)方法實(shí)際上是上述兩種方法的改進(jìn),如最強(qiáng)鄰(strongest NN, SNN)方法和Cheap JPDA等。GNN和JPDA是單掃描型方法,均基于上一次掃描已做出的關(guān)聯(lián)決策和當(dāng)前掃描的量測(cè)數(shù)據(jù),來(lái)給出當(dāng)前的關(guān)聯(lián)決策。由于量測(cè)噪聲、虛警雜波、目標(biāo)機(jī)動(dòng)的存在,在較困難的情景下僅利用單掃描的數(shù)據(jù)并不足以給出正確關(guān)聯(lián),因此需要聯(lián)合多次掃描周期內(nèi)的量測(cè)進(jìn)行關(guān)聯(lián)的多掃描型數(shù)據(jù)關(guān)聯(lián)方法。

文獻(xiàn)[1]中首次提出了一種完整的利用多掃描數(shù)據(jù)的數(shù)據(jù)關(guān)聯(lián)方法。此方法在難以做出關(guān)聯(lián)決策時(shí)維持各個(gè)可能關(guān)聯(lián)情形作為關(guān)聯(lián)假設(shè),這些假設(shè)隨著后續(xù)量測(cè)數(shù)據(jù)的接收不斷生成子假設(shè),即假設(shè)在掃描間傳遞,最后評(píng)估假設(shè)并做出決策。因此它是一種面向假設(shè)的多假設(shè)跟蹤(hypothesisa-oriented multiple hypothesis tracking, HOMHT)方法[2]。

多假設(shè)跟蹤(multiple hypothesis tracking, MHT)能夠在信噪比低10～100倍的情況下獲取與單掃描方法相當(dāng)?shù)男阅躘3]。Bar-Shalom 1989年在一篇關(guān)于MHT的綜述文章中寫(xiě)道[4]:MHT在所有方法中考慮最全面,它能處理航跡起始、多目標(biāo)及機(jī)動(dòng)目標(biāo),它的劣勢(shì)在于巨大的計(jì)算量和存儲(chǔ)空間要求(高于PDA數(shù)個(gè)量級(jí))、非常復(fù)雜的數(shù)據(jù)管理和巨量的輸出航跡。因此在80年代,MHT的研究和應(yīng)用進(jìn)展緩慢。

在1990年到1993年間,文獻(xiàn)[5-8]提出了面向航跡的MHT(track-oriented MHT,TOMHT)實(shí)現(xiàn)方案。在TOMHT中,不再維持全局假設(shè)集,而是維持假設(shè)航跡集,并由假設(shè)航跡集生成全局假設(shè),利用全局假設(shè)概率計(jì)算航跡的概率,并據(jù)此刪除低概率航跡以限制航跡數(shù)目。相比HOMHT,TOMHT方案的優(yōu)勢(shì)在于:①航跡綜合輸出容易,而在HOMHT中綜合多個(gè)假設(shè)給出具有一致性的輸出較為困難;②在表述同樣多種關(guān)聯(lián)可能時(shí),維持假設(shè)航跡所需存儲(chǔ)空間遠(yuǎn)較維持全局假設(shè)之所需低;③假設(shè)航跡生成簡(jiǎn)單,但全局假設(shè)的生成較為困難。針對(duì)TOMHT的最優(yōu)全局假設(shè)生成問(wèn)題,從1991年起,文獻(xiàn)[9]將此問(wèn)題建模為多維分配(multiple dimension assignment, MDA)問(wèn)題,并利用遞歸拉格朗日松弛方法求解此問(wèn)題[10],之后對(duì)此方法又做了改進(jìn)[11],拉格朗日松弛方法的應(yīng)用使得實(shí)時(shí)求解多傳感器下多掃描、密集目標(biāo)、密集雜波場(chǎng)景下的數(shù)據(jù)關(guān)聯(lián)問(wèn)題成為可能。文獻(xiàn)[12]將假設(shè)航跡映射為圖論中的頂點(diǎn),將假設(shè)生成過(guò)程等價(jià)于求解最大加權(quán)獨(dú)立集問(wèn)題(maximum weighted independent set problem, MWISP),而MWISP是圖論中的經(jīng)典問(wèn)題,在離散優(yōu)化領(lǐng)域已被深入研究,因此結(jié)合已有的高效的MWISP求解算法,可以高效地生成全局假設(shè)。多種最優(yōu)全局假設(shè)生成方法的研究成果、航跡分枝控制技術(shù)[13]以及計(jì)算能力的提高使TOMHT在國(guó)外獲得廣泛應(yīng)用和深入研究。代表性的應(yīng)用研究有:結(jié)合IMM的MHT以跟蹤多機(jī)動(dòng)目標(biāo)[14];改進(jìn)MHT并應(yīng)用于群目標(biāo)跟蹤[15]、分離目標(biāo)跟蹤[16]、擴(kuò)展目標(biāo)跟蹤[17]等特定場(chǎng)景;在視覺(jué)跟蹤應(yīng)用中將深度學(xué)習(xí)所得外觀特征與MHT結(jié)合等[18]。

從2002年起國(guó)內(nèi)有很多論文涉及到MHT的研究。代表性的研究及應(yīng)用有機(jī)載雷達(dá)網(wǎng)系統(tǒng)的MHT框架設(shè)計(jì)和工程實(shí)現(xiàn)問(wèn)題[19];分布式多傳感器網(wǎng)絡(luò)系統(tǒng)中IMM 結(jié)合MHT的算法[20];角度信息輔助的集中式多傳感器MHT[21]以及基于因子圖的地面密集目標(biāo)MHT[22]等。

目前幾乎普遍認(rèn)為MHT是現(xiàn)代跟蹤系統(tǒng)數(shù)據(jù)關(guān)聯(lián)的首選方法[3],但是由于MHT算法的復(fù)雜度以及研究成本、研制周期、計(jì)算量的限制,國(guó)內(nèi)在MHT領(lǐng)域起步較晚,且鮮有人對(duì)MHT在多傳感器信息融合方面的應(yīng)用進(jìn)行研究和驗(yàn)證[20]。

本文著重研究了TOMHT算法在工程實(shí)現(xiàn)中的問(wèn)題:給出了航跡得分計(jì)算方法及用途;結(jié)合跟蹤門(mén)的使用闡述航跡樹(shù)的生成;將航跡聚類(lèi)和假設(shè)生成建模為圖論問(wèn)題,以便采用成熟高效的MWISP生成全局假設(shè);提出了一種關(guān)聯(lián)深度自適應(yīng)(adaptive association depth, AAD)方法,使關(guān)聯(lián)深度隨關(guān)聯(lián)場(chǎng)景的復(fù)雜程度自適應(yīng)變化;仿真研究了本文提出的AAD-MHT跟蹤密集目標(biāo)的性能,仿真驗(yàn)證表明,本文所給出的算法具有良好的關(guān)聯(lián)跟蹤效果,同時(shí)又有效降低了計(jì)算量。

1　面向航跡的多假設(shè)跟蹤算法

一個(gè)完整的TOMHT的邏輯框架如圖1所示,由6個(gè)部分構(gòu)成[23]:①對(duì)現(xiàn)有的航跡進(jìn)行預(yù)測(cè)(即卡爾曼預(yù)測(cè));②進(jìn)行基于航跡得分的航跡刪除和確認(rèn);③對(duì)在航跡刪除后幸存的航跡進(jìn)行分簇;④在每個(gè)簇中獨(dú)立地進(jìn)行全局假設(shè)的生成、航跡全局概率的計(jì)算;⑤基于最優(yōu)全局假設(shè)的N掃描回溯剪枝及基于全局概率的航跡刪除;⑥用當(dāng)前時(shí)刻量測(cè)對(duì)幸存航跡進(jìn)行更新,即卡爾曼濾波,同時(shí)綜合剩余假設(shè)航跡向用戶提供輸出。研究表明上述6個(gè)階段主要涉及航跡得分、航跡樹(shù)的生成、航跡聚類(lèi)、全局假設(shè)生成、N掃描回溯剪枝等5項(xiàng)關(guān)鍵算法,下面在理論和應(yīng)用結(jié)合層面上對(duì)這些關(guān)鍵算法進(jìn)行論述。

圖1　TOMHT的邏輯框架Fig.1　Logic overview of TOMHT

1.1航跡樹(shù)的生成

TOMHT一般會(huì)引入航跡樹(shù)結(jié)構(gòu)。一株航跡樹(shù)對(duì)應(yīng)一個(gè)目標(biāo),樹(shù)上每一條從根到葉的路徑構(gòu)成該目標(biāo)的一組量測(cè)歷史記錄,其中至多只有一條路徑反映了真實(shí)目標(biāo)的航跡。圖2可說(shuō)明航跡樹(shù)形成過(guò)程:在k-1掃描,將航跡量測(cè)預(yù)測(cè)值附近區(qū)域設(shè)為相關(guān)門(mén),只有位于相關(guān)門(mén)內(nèi)的量測(cè)(如圖2中的zk-1,1和zk-1,2)才可與航跡關(guān)聯(lián),由于目標(biāo)可能不被探測(cè)到,這時(shí)航跡可不關(guān)聯(lián)任何量測(cè),即關(guān)聯(lián)zk-1,0(空量測(cè),以深色節(jié)點(diǎn)表示)。接著根據(jù)關(guān)聯(lián)結(jié)果獲得各個(gè)航跡分支在k掃描的量測(cè)預(yù)測(cè),并可設(shè)置相應(yīng)的相關(guān)門(mén),再根據(jù)相關(guān)門(mén)內(nèi)的量測(cè),將航跡樹(shù)伸展到k掃描。

圖2　航跡樹(shù)的形成Fig.2　Tree structure formation in TOMHT

顯然,隨著時(shí)間的推移,航跡樹(shù)的數(shù)量會(huì)越來(lái)越多,樹(shù)的結(jié)點(diǎn)數(shù)也會(huì)急劇增大。除了采用相關(guān)門(mén)技術(shù)控制假設(shè)航跡數(shù)目,還需要根據(jù)航跡得分對(duì)航跡進(jìn)行剪枝操作,以及根據(jù)假設(shè)航跡的后驗(yàn)概率進(jìn)行N-掃描回溯剪枝和全局剪枝。

1.2航跡得分

在MHT中必須對(duì)假設(shè)進(jìn)行評(píng)估,其評(píng)估準(zhǔn)則是假設(shè)后驗(yàn)概率。分析假設(shè)后驗(yàn)概率的計(jì)算式,可將此概率的對(duì)數(shù)值分解到可遞推計(jì)算的航跡概率似然值(即航跡得分)。記P{Θk,s|Z1∶k}為1到k掃描所有量測(cè)Z1∶k條件下假設(shè)Θk,s(k掃描第s個(gè)全局假設(shè))的概率,設(shè)Θk,s在k+1掃描的某個(gè)子假設(shè)為Θk+1,l,則假設(shè)后驗(yàn)概率[24]的對(duì)數(shù)形式為

(1)

式中,ci為第i掃描中不隨假設(shè)變化的常數(shù);δt指示Θk,s中航跡Tt是否關(guān)聯(lián)k+1時(shí)刻的量測(cè);v為k+1掃描新出現(xiàn)目標(biāo)的數(shù)目;λfa和λnew分別表示虛警雜波密度和新雜波密度;PDt(k+1)表示航跡Tt所代表目標(biāo)在k+1掃描被傳感器觀測(cè)到且其量測(cè)落入相關(guān)門(mén)的概率;ft[zk+1,jt]表示在量測(cè)取為zk+1,jt(即航跡Tt關(guān)聯(lián)量測(cè)zk+1,jt)時(shí)的概率密度函數(shù)值(pdf),在利用卡爾曼濾波預(yù)測(cè)下一掃描量測(cè)時(shí)此pdf是容易計(jì)算的。

式(1)等式左側(cè)設(shè)為Θk+1,l的假設(shè)得分,分析可知:假設(shè)得分可遞推計(jì)算,假設(shè)得分增量可分解到每條航跡上;新目標(biāo)對(duì)假設(shè)得分的貢獻(xiàn)為ln(λnew/λfa);航跡Tt不關(guān)聯(lián)任何量測(cè)時(shí)貢獻(xiàn)為ln(1-PDt);航跡Tt關(guān)聯(lián)量測(cè)zk+1,jt時(shí)的貢獻(xiàn)為ln[PDtft[zk+1,jt]/λfa]。分解得分增量實(shí)際上是將假設(shè)得分分解到每條航跡上,即每條航跡都有得分。航跡Tt在k掃描的得分sk可定義為

(2)

根據(jù)航跡得分的定義,假設(shè)得分為構(gòu)成假設(shè)的所有航跡的航跡得分之和,從而可用于計(jì)算航跡后驗(yàn)概率。航跡得分[25]還可用于確定航跡的狀態(tài),一般根據(jù)航跡得分將航跡分為起始航跡(單點(diǎn)航跡)、暫時(shí)航跡(得分較低的多點(diǎn)航跡)、確認(rèn)航跡(得分超過(guò)某門(mén)限的多點(diǎn)航跡)、刪除航跡(航跡得分過(guò)低或與歷史最高得分之差超過(guò)一定門(mén)限)。

1.3航跡聚類(lèi)

由于某些目標(biāo)在時(shí)空中的可區(qū)分性很高,因此可將所有的假設(shè)航跡劃分成子集,在每個(gè)子集中獨(dú)立地進(jìn)行假設(shè)生成、全局級(jí)航跡刪減和航跡更新等操作,以免因假設(shè)組合導(dǎo)致復(fù)雜度過(guò)大。假設(shè)航跡子集即為航跡類(lèi)或航跡簇(若干共享量測(cè)的航跡樹(shù)組成的集合)。

MTT算法一般假設(shè):任何量測(cè)最多源于單個(gè)目標(biāo);任何目標(biāo)在單個(gè)掃描中最多產(chǎn)生一個(gè)量測(cè)。因此,不同航跡類(lèi)中的假設(shè)航跡必定不能共享量測(cè)。將假設(shè)航跡映射為圖論中圖的頂點(diǎn),航跡共享量測(cè)則對(duì)應(yīng)頂點(diǎn)是相鄰的(即頂點(diǎn)間存在邊)。聚類(lèi)即為頂點(diǎn)集的劃分操作,根據(jù)聚類(lèi)原則,相鄰頂點(diǎn)必在同一集合中,根據(jù)此性質(zhì),聚類(lèi)對(duì)應(yīng)將所有頂點(diǎn)劃分為若干個(gè)極大連通子集的操作,此過(guò)程可由深度優(yōu)先搜索算法實(shí)現(xiàn)。

由于航跡間是否共享量測(cè)在航跡聚類(lèi)和全局假設(shè)生成中都是必需的,故在實(shí)現(xiàn)時(shí)需要維持航跡相容性矩陣M:若航跡i與航跡j共享量測(cè),則Mij=1,否則Mij=0(相容即不共享量測(cè))。可通過(guò)2個(gè)步驟確定M:①如果兩航跡在前一個(gè)掃描(即父航跡)是不相容的,則這兩個(gè)航跡也是不相容的;②如果在當(dāng)前掃描兩航跡關(guān)聯(lián)同一個(gè)量測(cè),則這兩個(gè)航跡也是不相容的。

1.4全局假設(shè)生成

航跡得分只能反映航跡本身的量測(cè)歷史與運(yùn)動(dòng)模型、觀測(cè)模型的符合程度,它沒(méi)有考慮其他航跡、量測(cè)對(duì)航跡的影響。在MTT中必須通過(guò)假定了全部量測(cè)來(lái)源的全局假設(shè)來(lái)進(jìn)行整體的數(shù)據(jù)關(guān)聯(lián)。全局假設(shè)是互不共享量測(cè)的假設(shè)航跡集合,不在任何假設(shè)航跡中出現(xiàn)的量測(cè)認(rèn)為是虛假量測(cè),因此它實(shí)質(zhì)上假定了所有量測(cè)的來(lái)源。全局假設(shè)可在每一個(gè)簇中獨(dú)立地形成,故假設(shè)生成很容易并行處理。由于航跡樹(shù)內(nèi)航跡共享一個(gè)根結(jié)點(diǎn),所以一株航跡樹(shù)內(nèi)的所有航跡是互不相容的,因此一個(gè)全局假設(shè)中至多包含某個(gè)航跡樹(shù)中的一條航跡。

當(dāng)前掃描下的最優(yōu)假設(shè)(得分最高的假設(shè))給出了在目前數(shù)據(jù)下具有最大概率的數(shù)據(jù)關(guān)聯(lián)結(jié)果,它可用于關(guān)聯(lián)決策。如果生成所有較優(yōu)假設(shè)并使未生成假設(shè)的概率和很小,則能夠較準(zhǔn)確計(jì)算假設(shè)航跡的后驗(yàn)概率。因此應(yīng)盡可能生成所有的較優(yōu)假設(shè)[23]。具體來(lái)說(shuō),如果最優(yōu)假設(shè)的得分為smax,設(shè)其概率為Pmax,則應(yīng)該生成得分在smax-Δsthr的假設(shè),相應(yīng)的假設(shè)概率為e-ΔsthrPmax,一般設(shè)Δsthr=10。

考慮到MWISP與基于MDA的MHT實(shí)現(xiàn)比較起來(lái)更加簡(jiǎn)明,且可以利用圖論中成熟的算法,因而本文采用MWISP獲得全局假設(shè)。圖3給出了將假設(shè)航跡映射到圖的例子,左邊的航跡樹(shù)表示到k次掃描時(shí)的4個(gè)航跡,樹(shù)的每個(gè)節(jié)點(diǎn)中的數(shù)字為航跡在對(duì)應(yīng)掃描中所關(guān)聯(lián)量測(cè)的標(biāo)號(hào),因此航跡T1、T2、T3互不相容(共享根節(jié)點(diǎn)量測(cè)),T2和T4在k次掃描時(shí)共享量測(cè)2,故不相容,假定每個(gè)航跡的得分為其航跡標(biāo)號(hào)數(shù)值,故可得右邊的航跡圖,圖的頂點(diǎn)數(shù)字對(duì)應(yīng)假設(shè)航跡的得分。顯然加權(quán)獨(dú)立集按照航跡得分加權(quán)和從大到小排序有{T3,T4},{T1,T4},{T4},{T3},{T2}和{T1},即這4個(gè)航跡可生成6個(gè)全局假設(shè),其中最優(yōu)全局假設(shè)為{T3,T4}。

圖3　假設(shè)航跡到圖的映射Fig.3　Mapping from hypothesis tracks to track graph

通過(guò)求解MWISP獲得較優(yōu)假設(shè)是TOMHT算法的關(guān)鍵步驟,因?yàn)镸WISP是圖論中的NP問(wèn)題,在問(wèn)題規(guī)模較大時(shí),主要指目標(biāo)密集或虛警很高情況下,假設(shè)生成是TOMHT算法計(jì)算量的主要來(lái)源。一種啟發(fā)式方法貪心隨機(jī)自適應(yīng)搜索方法(greedyrandomizedadaptivesearchingprocedure,GRASP)可用于求解此問(wèn)題[26]。

TOMHT的假設(shè)生成和一般的MWISP不同之處是MWISP中所有頂點(diǎn)的權(quán)值必定均為非負(fù)數(shù),而TOMHT假設(shè)生成中允許部分航跡得分為負(fù)值,只要假設(shè)得分滿足條件即可。因此假設(shè)生成過(guò)程可分為以下3步:

步驟 1考慮所有的正得分航跡,利用MWISP算法獲得大量較優(yōu)全局假設(shè);

步驟 2從負(fù)得分航跡集構(gòu)成的圖中生成大量獨(dú)立集,保證獨(dú)立集的權(quán)值和不超過(guò)Δsthr(這種獨(dú)立集中元素個(gè)數(shù)一般不大,在10以下),并將獨(dú)立集按權(quán)值和降序排列;

步驟 3進(jìn)行合并,若最大假設(shè)得分為smax,對(duì)步驟1所獲得分為si的較優(yōu)假設(shè)選取步驟2中的權(quán)值和在smax-si-Δsthr以上的獨(dú)立集進(jìn)行合并,如果合并后還是獨(dú)立集,則將合并后的獨(dú)立集作為一個(gè)較優(yōu)全局假設(shè)(步驟1所有較優(yōu)假設(shè)都在最后的較優(yōu)全局假設(shè)集內(nèi))。

1.5N掃描回溯剪枝和全局級(jí)航跡刪減

N掃描回溯剪枝,利用了k-N+1,…,k-1,k這N次掃描的數(shù)據(jù)確定第k-N+1次掃描數(shù)據(jù)的關(guān)聯(lián)決策。圖4表示N=3時(shí)的N掃描回溯剪枝,涂灰的節(jié)點(diǎn)表示對(duì)應(yīng)航跡出現(xiàn)在最優(yōu)假設(shè)中(稱為最優(yōu)節(jié)點(diǎn)),當(dāng)前掃描為第k次掃描,對(duì)于tree1,從最優(yōu)節(jié)點(diǎn)開(kāi)始,按樹(shù)的分支路徑往前回溯,回溯到k-2次掃描,在k-2次掃描中有根節(jié)點(diǎn),但又不是最優(yōu)假設(shè)中航跡的根節(jié)點(diǎn)的所有假設(shè)航跡分支都被刪除。由于tree2在k-2次掃描不存在關(guān)聯(lián)不確定性,因此不做3-掃描回溯剪枝;tree3必定沒(méi)有航跡出現(xiàn)在最優(yōu)假設(shè)中,因?yàn)樗ctree1最優(yōu)節(jié)點(diǎn)對(duì)應(yīng)航跡共享量測(cè),由于k-2的量測(cè)來(lái)源已確定,因此tree3被刪除。

圖4　3-掃描回溯剪枝Fig.4　3-scan pruning

全局級(jí)航跡刪減是對(duì)N掃描回溯剪枝幸存的假設(shè)航跡,再依據(jù)假設(shè)航跡的后驗(yàn)概率式(3)進(jìn)行刪除。

(3)

式中,Hi(i=1,2,…,NH)為全局假設(shè),其對(duì)應(yīng)得分為si。全局級(jí)航跡刪減過(guò)程分兩個(gè)步驟進(jìn)行:①根據(jù)概率門(mén)限法,刪除后驗(yàn)概率低于門(mén)限的假設(shè)航跡;②對(duì)每個(gè)航跡樹(shù),刪除若干個(gè)低后驗(yàn)概率的航跡,以保證每個(gè)航跡樹(shù)內(nèi)假設(shè)航跡數(shù)不超過(guò)定值。

由上述可見(jiàn)全局假設(shè)在N掃描回溯剪枝和全局級(jí)航跡刪減中起非常重要的作用。

本節(jié)對(duì)TOMHT過(guò)程所涉及的關(guān)鍵算法進(jìn)行了詳細(xì)描述:航跡得分是航跡生命期管理和對(duì)數(shù)據(jù)關(guān)聯(lián)假設(shè)進(jìn)行評(píng)估的基礎(chǔ);航跡樹(shù)是一種有效的航跡組織結(jié)構(gòu),據(jù)此可方便地做回溯剪枝以給出具有一致性的關(guān)聯(lián)決策;聚類(lèi)即為求解極大連通子圖問(wèn)題;假設(shè)形成歸結(jié)為獲得較優(yōu)加權(quán)獨(dú)立集問(wèn)題;全局級(jí)航跡刪除則依賴航跡后驗(yàn)概率。

TOMHT算法實(shí)用性取決于能否有效控制假設(shè)航跡數(shù)目以減少計(jì)算量,一般有基于航跡本身的航跡級(jí)刪減、掃描回溯剪枝、全局級(jí)航跡刪減和航跡合并技術(shù)。

2　關(guān)聯(lián)深度自適應(yīng)方法

MHT方法利用若干個(gè)掃描的后繼量測(cè)解決當(dāng)前掃描的關(guān)聯(lián)不確定性,隨著后繼掃描數(shù)目的增加所需要保留的假設(shè)航跡數(shù)目呈指數(shù)增加,所以后繼掃描數(shù)目N不宜過(guò)大,但N值過(guò)小可能導(dǎo)致所利用的后續(xù)量測(cè)信息不足以解決當(dāng)前關(guān)聯(lián)不確定性。目前很多跟蹤系統(tǒng)中關(guān)聯(lián)深度N一般是事先設(shè)定的,文獻(xiàn)[3]給出了經(jīng)驗(yàn)性建議N≥5。當(dāng)關(guān)聯(lián)深度N=1時(shí),MHT算法退化為具有航跡起始與終結(jié)等功能的GNN算法。

實(shí)際上,關(guān)聯(lián)深度N應(yīng)該依賴于跟蹤場(chǎng)景:對(duì)目標(biāo)和雜波密集的困難情景,需要更多量測(cè)信息來(lái)共同做出關(guān)聯(lián)決策,N值應(yīng)較大;在目標(biāo)的時(shí)空區(qū)分性好、雜波和干擾少的簡(jiǎn)單情景,N值應(yīng)較小,甚至N=1,即GNN方法足以給出正確關(guān)聯(lián)決策。在同一監(jiān)視空間,有些區(qū)域的目標(biāo)需要較大的關(guān)聯(lián)深度,某些區(qū)域所需關(guān)聯(lián)深度很小。對(duì)同一個(gè)目標(biāo),某段時(shí)間需要的關(guān)聯(lián)深度較大,另一段時(shí)間所需深度可能很小。因此,事先設(shè)定統(tǒng)一關(guān)聯(lián)深度,對(duì)簡(jiǎn)單情景增加了不必要的計(jì)算量而不能改善關(guān)聯(lián)結(jié)果,甚至延遲了關(guān)聯(lián)決策;對(duì)極為復(fù)雜情景的目標(biāo),預(yù)先設(shè)定的關(guān)聯(lián)深度可能還不夠。因此,設(shè)定關(guān)聯(lián)深度,使其與跟蹤場(chǎng)景相適應(yīng),有利于高效利用計(jì)算資源和提高復(fù)雜場(chǎng)景下算法性能。

下面描述TOMHT框架下AAD方法,此方法依賴于最優(yōu)假設(shè)和航跡后驗(yàn)概率,對(duì)每個(gè)航跡樹(shù)設(shè)定自適應(yīng)變化的關(guān)聯(lián)深度,并且該變化過(guò)程分兩步進(jìn)行,即關(guān)聯(lián)深度擴(kuò)大和縮減。關(guān)聯(lián)深度擴(kuò)大用于替代掃描回溯剪枝過(guò)程,而關(guān)聯(lián)深度減小則在全局級(jí)航跡刪減后的航跡更新與合并步驟中執(zhí)行。

關(guān)聯(lián)深度擴(kuò)大過(guò)程可描述如下:

步驟 1將航跡樹(shù)按樹(shù)中分支航跡的最大得分作降序排列,排序后的航跡樹(shù)為T(mén)ri(i=1:NTree),樹(shù)中分支航跡的最大得分有s1≥s2≥…≥sNTree。設(shè)最小深度Nmin=1,設(shè)最大深度Nmax=8。令i=1,s=1,轉(zhuǎn)入步驟2。

步驟 2當(dāng)Tri中某假設(shè)航跡Tij隸屬于最優(yōu)假設(shè),則轉(zhuǎn)入步驟3,否則轉(zhuǎn)入步驟7。

步驟 3設(shè)Tri對(duì)應(yīng)的關(guān)聯(lián)深度為di,當(dāng)di=Nmax則執(zhí)行步驟4后轉(zhuǎn)入步驟6,否則di

步驟 4在Tri中對(duì)Tij從當(dāng)前的第k掃描回溯到k-di+1掃描,將Tri中在k-di+1掃描異于Tij的所有航跡分支刪除,同時(shí)將其他航跡樹(shù)中在k-di+1掃描與Tij共享量測(cè)的所有航跡刪除。

步驟 5設(shè)pij為T(mén)ij的后驗(yàn)概率,Tri中在k-di+1掃描與Tij關(guān)聯(lián)相同量測(cè)的所有航跡(包括Tij)的后驗(yàn)概率之和為pi,如果pij≥ps_thr且pi≥pb_thr,則執(zhí)行步驟4,再轉(zhuǎn)步驟6,否則認(rèn)為di掃描量測(cè)不足以支持決策,故di:=di+1,轉(zhuǎn)入步驟6。

步驟 6令i:=i+1,如果i≤NTree,轉(zhuǎn)入步驟2,否則s:=s-1,令l=1并轉(zhuǎn)入步驟8。

步驟 7令is=i,然后s:=s+1,轉(zhuǎn)入步驟6。

步驟 8如果s

步驟 9設(shè)航跡樹(shù)Tril在k-dil+1掃描中以j量測(cè)為根的航跡分支的后驗(yàn)概率之和為pj,其中后驗(yàn)概率和最大的量測(cè)為jl。若dil=Nmax則執(zhí)行步驟10后轉(zhuǎn)入步驟12,否則dil

步驟 10保留jl量測(cè)為根的航跡分支而刪除其他分支,刪除其他航跡樹(shù)Trij(1≤j≠l≤s)中關(guān)聯(lián)jl量測(cè)的航跡。

步驟 11如果pjl≥pb_thr,執(zhí)行步驟10后轉(zhuǎn)入步驟12,否則dil:=dil+1,轉(zhuǎn)入步驟12。

步驟 12令l:=l+1,轉(zhuǎn)入步驟8。

關(guān)聯(lián)深度縮減過(guò)程:對(duì)于航跡樹(shù)Tri,其關(guān)聯(lián)深度為di,如果航跡樹(shù)中所有航跡從k-di+1到k-di+ni次掃描的量測(cè)歷史序列一致,則取di:=max(di-ni+1,Nmin)。

圖5示例說(shuō)明關(guān)聯(lián)深度自適應(yīng)過(guò)程,其中粗線表示此航跡分支在最優(yōu)假設(shè)中。設(shè)計(jì)兩個(gè)關(guān)聯(lián)決策參數(shù)Pb-thr=0.4和Pb-thr=0.8分別為單航跡顯著概率和分支顯著概率。在Tree1中,當(dāng)前深度為3,由于最優(yōu)假設(shè)所含航跡所在子樹(shù)所有航跡后驗(yàn)概率之和為0.7,小于Pb-thr,因此認(rèn)為3個(gè)掃描的數(shù)據(jù)不足以給出可信的關(guān)聯(lián)決策;在Tree2中,最優(yōu)假設(shè)所含航跡的后驗(yàn)概率0.4不低于Ps-thr,此航跡所在子樹(shù)所有航跡分支的后驗(yàn)概率和為0.85,高于Pb-thr,因此可進(jìn)行3-掃描回溯剪枝,在關(guān)聯(lián)深度擴(kuò)大階段保持深度為3,到了關(guān)聯(lián)深度縮減階段,關(guān)聯(lián)深度減小為2;Tree3的關(guān)聯(lián)深度為2,不滿足關(guān)聯(lián)決策條件,關(guān)聯(lián)深度擴(kuò)大為3。

圖5　關(guān)聯(lián)深度自適應(yīng)過(guò)程示例Fig.5　Example of an AAD process

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

本節(jié)給出兩個(gè)仿真實(shí)驗(yàn),以說(shuō)明本文關(guān)AAD-MHT方法的有效性。

3.1幾乎交叉目標(biāo)跟蹤實(shí)驗(yàn)

兩個(gè)目標(biāo)具有相同速度,先相互靠近,再逐漸遠(yuǎn)離,目標(biāo)間最近距離為150m, 掃描周期T=2s,設(shè)目標(biāo)最大速度Vmax=300m/s,檢測(cè)概率PD=0.75,虛警雜波密度λfa=10-9m-2,新目標(biāo)密度為λnew=10-10m-2。在x,y方向上的量測(cè)噪聲均方差為100m。實(shí)驗(yàn)結(jié)果如表1和圖6所示。

表1　算法結(jié)果對(duì)比

表1給出N=1、N=6和AAD下的多個(gè)性能指標(biāo)比較,NT為真實(shí)航跡(指至少有一半量測(cè)源于真實(shí)目標(biāo)的航跡)數(shù)目;RMC為誤關(guān)聯(lián)率; RCC為真實(shí)航跡正確關(guān)聯(lián)率;OSPA為最優(yōu)子模式分配(optimalsub-patternassignment)[27]距離,用于度量關(guān)聯(lián)結(jié)果與真實(shí)航跡之間的差異性。由表1和圖6(b)可見(jiàn),N=1時(shí)發(fā)生了航跡交叉和航跡多次起批;表1和圖6(c)均說(shuō)明,AAD獲得了與N=6相同的結(jié)果,均與真實(shí)航跡一致,但是其運(yùn)行時(shí)間僅為固定N的48%。

圖7給出了兩個(gè)航跡對(duì)應(yīng)航跡樹(shù)的關(guān)聯(lián)深度隨掃描的變化情況。前20次掃描中,目標(biāo)間距較大,此時(shí)關(guān)聯(lián)深度N=1;第20個(gè)掃描后,目標(biāo)間距減小,單掃描量測(cè)不足以支持關(guān)聯(lián)決策,故N值逐漸增大,直到Nmax;第40個(gè)掃描后兩目標(biāo)逐漸遠(yuǎn)離,故N值逐漸減小直到Nmin。

圖6　幾乎交叉目標(biāo)跟蹤實(shí)驗(yàn)結(jié)果Fig.6　Results of tracking nearly crossed targets

圖7　關(guān)聯(lián)深度N的自適應(yīng)變化Fig.7　Adaptive change of association depth N

3.2編隊(duì)飛機(jī)跟蹤實(shí)驗(yàn)

本實(shí)驗(yàn)將AAD-MHT算法用于跟蹤編隊(duì)飛機(jī)目標(biāo)。飛機(jī)的相對(duì)位置定義為(a,b,c),分別表示某飛機(jī)在領(lǐng)頭機(jī)的后方a處、右邊b處、上方c處。共有4架飛機(jī)編隊(duì)飛行,除領(lǐng)頭機(jī)外,其余3架的相對(duì)位置為(2,-0.8,0.1)、(4.5,0.8,0.2)和(6.5,1.6,0.2)(單位為km)。雷達(dá)觀測(cè)坐標(biāo)系為極坐標(biāo)系,距離誤差標(biāo)準(zhǔn)差為200m,方位角和俯仰角誤差標(biāo)準(zhǔn)差均為0.2°。λfa=10-2m-1·rad-2,λnew=10-6m-1·rad-2,掃描間隔為4s,檢測(cè)概率為0.3,假定目標(biāo)運(yùn)動(dòng)符合常加速度模型,目標(biāo)最大速度為1 000m/s。

圖8給出了編隊(duì)飛機(jī)跟蹤結(jié)果的平面顯示,由圖可見(jiàn),航跡均開(kāi)始于第(9)區(qū)域,結(jié)束于第(1)區(qū)域。由圖8(a)可以看出,GNN所輸出航跡多次交換、航跡起始較晚且其中有些航跡在后期發(fā)生了嚴(yán)重的關(guān)聯(lián)錯(cuò)誤,而圖8(b)說(shuō)明,AAD-MHT幾乎沒(méi)有航跡互換且所有航跡均較快地起始。

圖8　編隊(duì)飛機(jī)目標(biāo)跟蹤結(jié)果Fig.8　Results of tracking target in formation

表2給出了幾項(xiàng)指標(biāo)比較,說(shuō)明在平均意義下,AAD-MHT的起始時(shí)刻比GNN早28.5個(gè)掃描,并且航跡持續(xù)時(shí)間較長(zhǎng),真實(shí)航跡正確關(guān)聯(lián)率高于后者。

兩個(gè)仿真實(shí)驗(yàn)結(jié)果表明,AAD方法確實(shí)能夠根據(jù)關(guān)聯(lián)情景的難易程度自適應(yīng)地調(diào)整N值,能夠在兼顧性能的同時(shí)減小計(jì)算量,說(shuō)明了AAD-MHT算法的有效性。

表2　不同算法性能比較

4　結(jié)　論

MHT的基本思想是對(duì)每種關(guān)聯(lián)情況多掃描考察,而非根據(jù)現(xiàn)有數(shù)據(jù)立即給出不可逆轉(zhuǎn)的關(guān)聯(lián)決策。由于關(guān)聯(lián)情況的多樣性,MHT算法的計(jì)算量必然很大,這給工程上實(shí)時(shí)應(yīng)用提出了挑戰(zhàn)?？紤]到很多假設(shè)是極低可能的假設(shè),因此必須對(duì)MHT算法的各個(gè)步驟做精心設(shè)計(jì),盡可能保留高可能假設(shè),同時(shí)盡可能降低假設(shè)航跡數(shù)目。本文重點(diǎn)描述了TOMHT的關(guān)鍵算法及具體實(shí)現(xiàn),包括航跡樹(shù)生成、航跡得分計(jì)算、航跡聚類(lèi)、假設(shè)生成、航跡刪除等?；陉P(guān)聯(lián)深度應(yīng)與跟蹤場(chǎng)景相匹配的思想,提出了一種利用航跡后驗(yàn)概率的AAD方法,每個(gè)航跡樹(shù)的關(guān)聯(lián)深度可隨著關(guān)聯(lián)情況自適應(yīng)的變化。此方法在復(fù)雜情況下使用較大的關(guān)聯(lián)深度保證了跟蹤性能,在簡(jiǎn)單情況下使用較小的關(guān)聯(lián)深度降低了計(jì)算量。本文的兩個(gè)仿真實(shí)驗(yàn)驗(yàn)證了本文基于AAD-MHT的有效性。

[1]ReidDB.Analgorithmfortrackingmultipletargets[J].IEEE Trans. on Automatic Control, 1979, 24(6):843-854.

[2]AntunesDM,MatosD,GasparJ.Alibraryforimplementingthemultiplehypothesistrackingalgorithm[EB/OL].[2015-11-03].http:∥arxiv.org/abs/1106.2263.

[3]BlackmanSS.Multiplehypothesistrackingformultipletargettracking[J].IEEE Aerospace and Electronic Systems Magazine, 2004, 19(1):5-18.

[4]Bar-ShalomY.Recursivetrackingalgorithms:fromtheKalmanfiltertointelligenttrackersforclutteredenvironment[C]∥Proc.of the IEEE International Conference on Control and Applications, 1989:675-680.

[5]KurienT. Issues in the design of practical multitarget tracking algorithms[M]∥Bar-ShalomYed. Multitarget-multisensor tarcking: advanced and applications.Norwood:ArtechHouse, 1990.

[6]DemosGC,RibasRA,BroidaTJ,etal.ApplicationsofMHTtodimmovingtargets[C]∥Proc.of the Signal and Data Processing of Small Targets, 1990:287-309.

[7]WerthmannJR.Step-by-stepdescriptionofacomputationallyefficientversionofmultiplehypothesistracking[C]∥Proc.of the Signal and Data Processing of Small Targets, 1992:288-300.

[8]ChanDS,HarrisonDD,LanganDA.Trackinginahighclutterenvironment:simulationresultscharacterizingaBi-levelMHTalgorithm[C]∥Proc.of the Signal and Data Processing of Small Targets, 1993:540-551.

[9]PooreAB,RijavecN.Multi-targettrackingandmulti-dimensionalassignmentproblems[C]∥Proc.of the Signal and Data Processing of Small Targets, 1991:345-356.

[10]RogerDW.Parametricandcombinatorialproblemsinconstrainedoptimization,ADA264229[R].California:CaliforniaUniversifyDavisDepartmentofMathematics, 1993:1-25.

[11]PooreAB,RobertsonAJIII.Anewlagrangianrelaxationbasedalgorithmforaclassofmultidimensionalassignmentproblems[J].Computational Optimization and Applications, 1997,8(2): 129-150.

[12]PapageorgiouDJ,SalpukasMR.Themaximumweightindependentsetproblemfordataassociationinmultiplehypothesistracking[C]∥Proc.of the 8th International Conference on Cooperative Control and Optimization, 2009: 235-255.

[13]WilliamsJL.Gaussianmixturereductionfortrackingmultiplemaneuveringtargetsinclutter,ADA415317[D].Ohio:AirForceInstituteofTechnology, 2003.

[14]BlackmanSS,DempsterRJ,RoszkowskiSH.IMM/MHTapplicationstoradarandIRmultitargettracking[C]∥Proc.of the Signal and Data Processing of Small Targets, 1997: 429-439.

[15]CoraluppiS,CarthelC.Aggregatesurveillance:acardinalitytrackingapproach[C]∥Proc.of the 14th International Conference on Information Fusion, 2001:1-6.

[16]ObataY,MaekawaR,ItoM,etalTrackingalgorithminheritingsmoothingvectorinsplittingtargettracking[C]∥Porc. of the ICROS-SICE International Joint Conference, 2009: 3020-3025.

[17]ZhaiG,MengHD,ZhongZW,etal.Amultiplehypothesistrackingmethodforextendedtargettarcking[C]∥Porc. of the International Conference on Electrical and Control Engineering, 2010: 109-112.

[18]KimC,LiFX,CiptadiA,etal.Multiplehypothesistrackingrevisited[EB/OL].[2015-12-10].http:∥web.engr.oregonstate.edu/～lif/MHT_ICCV15.pdf.

[19]WangZ.Airbornemulti-sensordatafusiontechnology[D].Nanjing:NanjingUniversityofScienceandTechnology,2010. (王智.機(jī)載多傳感器數(shù)據(jù)融合技術(shù)研究[D].南京:南京理工大學(xué),2010.)

[20]LuYB,SunW.Amulti-sensordatafusionalgorithmbasedMHT[J].Journal of China Academy of Electronics and Information Technology,2008,3(1):24-28. (陸耀賓,孫偉. 基于MHT的多傳感器數(shù)據(jù)融合算法[J].中國(guó)電子科學(xué)研究院學(xué)報(bào), 2008, 3(1): 24-28.)

[21]WangH,SunJP,FuJT,etal.Angle-aidedcentralizedmulti-sensormultiplehypothesistrackingmethod[J].Journal of Electronics & Information Technology,2015,37(1):56-62. (王歡,孫進(jìn)平,付錦斌,等.角度信息輔助的集中式多傳感器多假設(shè)跟蹤算法[J].電子與信息學(xué)報(bào), 2015, 37(1):56-62.)[22]WangH,SunJP,LuST.Factorgraphaidedmultiplehypothesistracking[J].Science China Iinformation Science, 2013, 56(10):1-6.[23]BlackmanSS,PopoliRF. Design and analysis of modern tracking systems[M].Boston:ArtechHouse, 1999:1069-1075.

[24]Bar-ShalomY,LiXR. Multitarget-multisensor tracking: principles and techniques[M].StorrsCT:YBSPublishing, 1995: 337-338.

[25]Bar-ShalomY,BlackmanSS,FitzgeraldRJ.Dimensionlessscorefunctionformultiplehypothesistracking[J].IEEE Trans. on Aerospace and Electronic Systems, 2007,43(1):392-400.

[26]RenXY,HuangZP,SunSY,etal.AnefficientMHTimplementationusingGRASP[J].IEEE Trans. on Aerospace and Electronic Systems, 2014, 50(1):86-100.

[27]Ba-NguV,Ba-TuongV,SchuhmacherD.Aconsistentmetricforperformanceevaluationofmulti-objectfilters[J].IEEE Trans. on Signal Processing, 2008, 56(8):3447-3467.

Multiple hypothesis tracking with adaptive association depth

CHEN Hang, ZHANG Bo-yan, CHEN Ying

(BeijingInstituteofRadioMeasurement,Beijing100854,China)

Multiple hypothesis tracking(MHT) is a Bayesian association method that evaluates association hypotheses among multiple scans and makes evaluation-based decisions. Comparing with the single hypothesis method, MHT can work reasonably under 10～100 times lower signal-noise ratio (SNR) but it needs much more computational load. The implementation of track-oriented MHT (TOMHT) is studied and some key points are investigated, include calculating the track score, generating the track tree, modeling track clustering, hypotheses generating as problems in graph theory andN-scan pruning, etc. In the TOMHT framework, an adaptive association depth (AAD) method is proposed. This method makes the association depth change adaptively with the complexity of scenarios. Its performance is investigated by several simulation experiments on tracking closely targets. The results and analysis show that the performance of AAD-MHT is nearly the same as MHT but the computational load is much lower.

multi-target tracking(MTT); multiple hypothesis tracking(MHT); data association; adaptive association depth(AAD)

2015-12-24；

2016-06-08；網(wǎng)絡(luò)優(yōu)先出版日期：2016-07-03。

TN 953

A

10.3969/j.issn.1001-506X.2016.09.06

陳杭(1990-),男,碩士研究生,主要研究方向?yàn)槔走_(dá)信號(hào)處理與數(shù)據(jù)處理。

E-mail:chenhanghb@126.com

張伯彥(1957-),女,研究員,博士,主要研究方向?yàn)楝F(xiàn)代雷達(dá)控制與數(shù)據(jù)處理、機(jī)動(dòng)多目標(biāo)跟蹤、數(shù)據(jù)融合。

E-mail:zhbyhktk@163.com

陳映(1984-),女,高級(jí)工程師,博士,主要研究方向?yàn)槔走_(dá)數(shù)據(jù)處理、彈道目標(biāo)跟蹤。

E-mail:michelle_cv@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160703.1240.004.html