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

陳　杭, 張伯彥, 陳　映

(北京無線電測量研究所, 北京 100854)

?

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

陳杭, 張伯彥, 陳映

(北京無線電測量研究所, 北京 100854)

多假設(shè)跟蹤(multiple hypothesis tracking, MHT)方法是一種在多個掃描上評價關(guān)聯(lián)假設(shè)并由此做出決策的貝葉斯型關(guān)聯(lián)跟蹤方法,此方法能夠在信噪比低10～100倍的狀況下獲得與單掃描方法相當(dāng)?shù)男阅?但同時會帶來相當(dāng)大的計(jì)算量。本文研究了面向航跡MHT中的關(guān)鍵算法,包括航跡得分計(jì)算與航跡樹的生成、將航跡聚類和假設(shè)生成建模為圖論問題并求解、N掃描回溯剪枝等,特別關(guān)注了這些算法過程的實(shí)現(xiàn);提出了一種關(guān)聯(lián)深度自適應(yīng)(adaptive association depth, AAD)方法,使關(guān)聯(lián)深度隨關(guān)聯(lián)場景的復(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)常耦合在一起,前者基于后者給定的同源量測序列估計(jì)和預(yù)測目標(biāo)狀態(tài),后者基于前者確定的狀態(tài)預(yù)測及量測數(shù)據(jù)再根據(jù)某種準(zhǔn)則判斷量測的來源。就航跡狀態(tài)估計(jì)而言,由于目標(biāo)運(yùn)動或觀測模型的非線性,一般采用非線性濾波方法,如擴(kuò)展卡爾曼濾波(extended Kalman filter, EKF)、無敏卡爾曼濾波(unscented Kalman filter, UKF)等;針對目標(biāo)運(yùn)動方式的不確定性,可以采用交互式多模型(interactive multiple model, IMM)方法以及變結(jié)構(gòu)多模型(variable structure multiple model, VSMM)方法等。數(shù)據(jù)關(guān)聯(lián)問題,由于量測的多種不確定性,相比濾波估計(jì)問題更加困難。量測的不確定性包括:①量測來源不確定,即傳感器量測可能源于虛警、雜波、干擾或者目標(biāo)、相鄰目標(biāo)等,同時目標(biāo)也有可能未被檢測到;②量測誤差存在并且非線性。早期發(fā)展起來的數(shù)據(jù)關(guān)聯(lián)方法適用于目標(biāo)不密集環(huán)境下的單目標(biāo)場景,包括最近鄰(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)前掃描的量測數(shù)據(jù),來給出當(dāng)前的關(guān)聯(lián)決策。由于量測噪聲、虛警雜波、目標(biāo)機(jī)動的存在,在較困難的情景下僅利用單掃描的數(shù)據(jù)并不足以給出正確關(guān)聯(lián),因此需要聯(lián)合多次掃描周期內(nèi)的量測進(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)決策時維持各個可能關(guān)聯(lián)情形作為關(guān)聯(lián)假設(shè),這些假設(shè)隨著后續(xù)量測數(shù)據(jù)的接收不斷生成子假設(shè),即假設(shè)在掃描間傳遞,最后評估假設(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的綜述文章中寫道[4]:MHT在所有方法中考慮最全面,它能處理航跡起始、多目標(biāo)及機(jī)動目標(biāo),它的劣勢在于巨大的計(jì)算量和存儲空間要求(高于PDA數(shù)個量級)、非常復(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)勢在于:①航跡綜合輸出容易,而在HOMHT中綜合多個假設(shè)給出具有一致性的輸出較為困難;②在表述同樣多種關(guān)聯(lián)可能時,維持假設(shè)航跡所需存儲空間遠(yuǎn)較維持全局假設(shè)之所需低;③假設(shè)航跡生成簡單,但全局假設(shè)的生成較為困難。針對TOMHT的最優(yōu)全局假設(shè)生成問題,從1991年起,文獻(xiàn)[9]將此問題建模為多維分配(multiple dimension assignment, MDA)問題,并利用遞歸拉格朗日松弛方法求解此問題[10],之后對此方法又做了改進(jìn)[11],拉格朗日松弛方法的應(yīng)用使得實(shí)時求解多傳感器下多掃描、密集目標(biāo)、密集雜波場景下的數(shù)據(jù)關(guān)聯(lián)問題成為可能。文獻(xiàn)[12]將假設(shè)航跡映射為圖論中的頂點(diǎn),將假設(shè)生成過程等價于求解最大加權(quán)獨(dú)立集問題(maximum weighted independent set problem, MWISP),而MWISP是圖論中的經(jīng)典問題,在離散優(yōu)化領(lǐng)域已被深入研究,因此結(jié)合已有的高效的MWISP求解算法,可以高效地生成全局假設(shè)。多種最優(yōu)全局假設(shè)生成方法的研究成果、航跡分枝控制技術(shù)[13]以及計(jì)算能力的提高使TOMHT在國外獲得廣泛應(yīng)用和深入研究。代表性的應(yīng)用研究有:結(jié)合IMM的MHT以跟蹤多機(jī)動目標(biāo)[14];改進(jìn)MHT并應(yīng)用于群目標(biāo)跟蹤[15]、分離目標(biāo)跟蹤[16]、擴(kuò)展目標(biāo)跟蹤[17]等特定場景;在視覺跟蹤應(yīng)用中將深度學(xué)習(xí)所得外觀特征與MHT結(jié)合等[18]。

從2002年起國內(nèi)有很多論文涉及到MHT的研究。代表性的研究及應(yīng)用有機(jī)載雷達(dá)網(wǎng)系統(tǒng)的MHT框架設(shè)計(jì)和工程實(shí)現(xià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ì)算量的限制,國內(nèi)在MHT領(lǐng)域起步較晚,且鮮有人對MHT在多傳感器信息融合方面的應(yīng)用進(jìn)行研究和驗(yàn)證[20]。

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

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

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

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

1.1航跡樹的生成

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

圖2　航跡樹的形成Fig.2　Tree structure formation in TOMHT

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

1.2航跡得分

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

(1)

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

式(1)等式左側(cè)設(shè)為Θk+1,l的假設(shè)得分,分析可知:假設(shè)得分可遞推計(jì)算,假設(shè)得分增量可分解到每條航跡上;新目標(biāo)對假設(shè)得分的貢獻(xiàn)為ln(λnew/λfa);航跡Tt不關(guān)聯(lián)任何量測時貢獻(xiàn)為ln(1-PDt);航跡Tt關(guān)聯(lián)量測zk+1,jt時的貢獻(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)航跡)、暫時航跡(得分較低的多點(diǎn)航跡)、確認(rèn)航跡(得分超過某門限的多點(diǎn)航跡)、刪除航跡(航跡得分過低或與歷史最高得分之差超過一定門限)。

1.3航跡聚類

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

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

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

1.4全局假設(shè)生成

航跡得分只能反映航跡本身的量測歷史與運(yùn)動模型、觀測模型的符合程度,它沒有考慮其他航跡、量測對航跡的影響。在MTT中必須通過假定了全部量測來源的全局假設(shè)來進(jìn)行整體的數(shù)據(jù)關(guān)聯(lián)。全局假設(shè)是互不共享量測的假設(shè)航跡集合,不在任何假設(shè)航跡中出現(xiàn)的量測認(rèn)為是虛假量測,因此它實(shí)質(zhì)上假定了所有量測的來源。全局假設(shè)可在每一個簇中獨(dú)立地形成,故假設(shè)生成很容易并行處理。由于航跡樹內(nèi)航跡共享一個根結(jié)點(diǎn),所以一株航跡樹內(nèi)的所有航跡是互不相容的,因此一個全局假設(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]。具體來說,如果最優(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)比較起來更加簡明,且可以利用圖論中成熟的算法,因而本文采用MWISP獲得全局假設(shè)。圖3給出了將假設(shè)航跡映射到圖的例子,左邊的航跡樹表示到k次掃描時的4個航跡,樹的每個節(jié)點(diǎn)中的數(shù)字為航跡在對應(yīng)掃描中所關(guān)聯(lián)量測的標(biāo)號,因此航跡T1、T2、T3互不相容(共享根節(jié)點(diǎn)量測),T2和T4在k次掃描時共享量測2,故不相容,假定每個航跡的得分為其航跡標(biāo)號數(shù)值,故可得右邊的航跡圖,圖的頂點(diǎn)數(shù)字對應(yīng)假設(shè)航跡的得分。顯然加權(quán)獨(dú)立集按照航跡得分加權(quán)和從大到小排序有{T3,T4},{T1,T4},{T4},{T3},{T2}和{T1},即這4個航跡可生成6個全局假設(shè),其中最優(yōu)全局假設(shè)為{T3,T4}。

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

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

MHT方法利用若干個掃描的后繼量測解決當(dāng)前掃描的關(guān)聯(lián)不確定性,隨著后繼掃描數(shù)目的增加所需要保留的假設(shè)航跡數(shù)目呈指數(shù)增加,所以后繼掃描數(shù)目N不宜過大,但N值過小可能導(dǎo)致所利用的后續(xù)量測信息不足以解決當(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時,MHT算法退化為具有航跡起始與終結(jié)等功能的GNN算法。

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

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

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

步驟 1將航跡樹按樹中分支航跡的最大得分作降序排列,排序后的航跡樹為Tri(i=1:NTree),樹中分支航跡的最大得分有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對應(yīng)的關(guān)聯(lián)深度為di,當(dāng)di=Nmax則執(zhí)行步驟4后轉(zhuǎn)入步驟6,否則di

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

步驟 5設(shè)pij為Tij的后驗(yàn)概率,Tri中在k-di+1掃描與Tij關(guān)聯(lián)相同量測的所有航跡(包括Tij)的后驗(yàn)概率之和為pi,如果pij≥ps_thr且pi≥pb_thr,則執(zhí)行步驟4,再轉(zhuǎn)步驟6,否則認(rèn)為di掃描量測不足以支持決策,故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è)航跡樹Tril在k-dil+1掃描中以j量測為根的航跡分支的后驗(yàn)概率之和為pj,其中后驗(yàn)概率和最大的量測為jl。若dil=Nmax則執(zhí)行步驟10后轉(zhuǎn)入步驟12,否則dil

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

步驟 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)深度縮減過程:對于航跡樹Tri,其關(guān)聯(lián)深度為di,如果航跡樹中所有航跡從k-di+1到k-di+ni次掃描的量測歷史序列一致,則取di:=max(di-ni+1,Nmin)。

圖5示例說明關(guān)聯(lián)深度自適應(yīng)過程,其中粗線表示此航跡分支在最優(yōu)假設(shè)中。設(shè)計(jì)兩個關(guān)聯(lián)決策參數(shù)Pb-thr=0.4和Pb-thr=0.8分別為單航跡顯著概率和分支顯著概率。在Tree1中,當(dāng)前深度為3,由于最優(yōu)假設(shè)所含航跡所在子樹所有航跡后驗(yàn)概率之和為0.7,小于Pb-thr,因此認(rèn)為3個掃描的數(shù)據(jù)不足以給出可信的關(guān)聯(lián)決策;在Tree2中,最優(yōu)假設(shè)所含航跡的后驗(yàn)概率0.4不低于Ps-thr,此航跡所在子樹所有航跡分支的后驗(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)過程示例Fig.5　Example of an AAD process

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

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

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

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

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

表1給出N=1、N=6和AAD下的多個性能指標(biāo)比較,NT為真實(shí)航跡(指至少有一半量測源于真實(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)可見,N=1時發(fā)生了航跡交叉和航跡多次起批;表1和圖6(c)均說明,AAD獲得了與N=6相同的結(jié)果,均與真實(shí)航跡一致,但是其運(yùn)行時間僅為固定N的48%。

圖7給出了兩個航跡對應(yīng)航跡樹的關(guān)聯(lián)深度隨掃描的變化情況。前20次掃描中,目標(biāo)間距較大,此時關(guān)聯(lián)深度N=1;第20個掃描后,目標(biāo)間距減小,單掃描量測不足以支持關(guān)聯(lián)決策,故N值逐漸增大,直到Nmax;第40個掃描后兩目標(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ī)的相對位置定義為(a,b,c),分別表示某飛機(jī)在領(lǐng)頭機(jī)的后方a處、右邊b處、上方c處。共有4架飛機(jī)編隊(duì)飛行,除領(lǐng)頭機(jī)外,其余3架的相對位置為(2,-0.8,0.1)、(4.5,0.8,0.2)和(6.5,1.6,0.2)(單位為km)。雷達(dá)觀測坐標(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,檢測概率為0.3,假定目標(biāo)運(yùn)動符合常加速度模型,目標(biāo)最大速度為1 000m/s。

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

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

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

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

表2　不同算法性能比較

4　結(jié)　論

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

E-mail:chenhanghb@126.com

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

E-mail:zhbyhktk@163.com

陳映(1984-),女,高級工程師,博士,主要研究方向?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