關聯深度自適應的多假設跟蹤研究

陳　杭, 張伯彥, 陳　映

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

?

關聯深度自適應的多假設跟蹤研究

陳杭, 張伯彥, 陳映

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

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

多目標跟蹤; 多假設跟蹤; 數據關聯; 關聯深度自適應

0　引　言

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

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

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

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

從2002年起國內有很多論文涉及到MHT的研究。代表性的研究及應用有機載雷達網系統的MHT框架設計和工程實現問題[19];分布式多傳感器網絡系統中IMM 結合MHT的算法[20];角度信息輔助的集中式多傳感器MHT[21]以及基于因子圖的地面密集目標MHT[22]等。

目前幾乎普遍認為MHT是現代跟蹤系統數據關聯的首選方法[3],但是由于MHT算法的復雜度以及研究成本、研制周期、計算量的限制,國內在MHT領域起步較晚,且鮮有人對MHT在多傳感器信息融合方面的應用進行研究和驗證[20]。

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

1　面向航跡的多假設跟蹤算法

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

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

1.1航跡樹的生成

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

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

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

1.2航跡得分

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

(1)

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

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

(2)

根據航跡得分的定義,假設得分為構成假設的所有航跡的航跡得分之和,從而可用于計算航跡后驗概率。航跡得分[25]還可用于確定航跡的狀態,一般根據航跡得分將航跡分為起始航跡(單點航跡)、暫時航跡(得分較低的多點航跡)、確認航跡(得分超過某門限的多點航跡)、刪除航跡(航跡得分過低或與歷史最高得分之差超過一定門限)。

1.3航跡聚類

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

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

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

1.4全局假設生成

航跡得分只能反映航跡本身的量測歷史與運動模型、觀測模型的符合程度,它沒有考慮其他航跡、量測對航跡的影響。在MTT中必須通過假定了全部量測來源的全局假設來進行整體的數據關聯。全局假設是互不共享量測的假設航跡集合,不在任何假設航跡中出現的量測認為是虛假量測,因此它實質上假定了所有量測的來源。全局假設可在每一個簇中獨立地形成,故假設生成很容易并行處理。由于航跡樹內航跡共享一個根結點,所以一株航跡樹內的所有航跡是互不相容的,因此一個全局假設中至多包含某個航跡樹中的一條航跡。

當前掃描下的最優假設(得分最高的假設)給出了在目前數據下具有最大概率的數據關聯結果,它可用于關聯決策。如果生成所有較優假設并使未生成假設的概率和很小,則能夠較準確計算假設航跡的后驗概率。因此應盡可能生成所有的較優假設[23]。具體來說,如果最優假設的得分為smax,設其概率為Pmax,則應該生成得分在smax-Δsthr的假設,相應的假設概率為e-ΔsthrPmax,一般設Δsthr=10。

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

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

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

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

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

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

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

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

N掃描回溯剪枝,利用了k-N+1,…,k-1,k這N次掃描的數據確定第k-N+1次掃描數據的關聯決策。圖4表示N=3時的N掃描回溯剪枝,涂灰的節點表示對應航跡出現在最優假設中(稱為最優節點),當前掃描為第k次掃描,對于tree1,從最優節點開始,按樹的分支路徑往前回溯,回溯到k-2次掃描,在k-2次掃描中有根節點,但又不是最優假設中航跡的根節點的所有假設航跡分支都被刪除。由于tree2在k-2次掃描不存在關聯不確定性,因此不做3-掃描回溯剪枝;tree3必定沒有航跡出現在最優假設中,因為它與tree1最優節點對應航跡共享量測,由于k-2的量測來源已確定,因此tree3被刪除。

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

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

(3)

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

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

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

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

2　關聯深度自適應方法

MHT方法利用若干個掃描的后繼量測解決當前掃描的關聯不確定性,隨著后繼掃描數目的增加所需要保留的假設航跡數目呈指數增加,所以后繼掃描數目N不宜過大,但N值過小可能導致所利用的后續量測信息不足以解決當前關聯不確定性。目前很多跟蹤系統中關聯深度N一般是事先設定的,文獻[3]給出了經驗性建議N≥5。當關聯深度N=1時,MHT算法退化為具有航跡起始與終結等功能的GNN算法。

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

下面描述TOMHT框架下AAD方法,此方法依賴于最優假設和航跡后驗概率,對每個航跡樹設定自適應變化的關聯深度,并且該變化過程分兩步進行,即關聯深度擴大和縮減。關聯深度擴大用于替代掃描回溯剪枝過程,而關聯深度減小則在全局級航跡刪減后的航跡更新與合并步驟中執行。

關聯深度擴大過程可描述如下:

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

步驟 2當Tri中某假設航跡Tij隸屬于最優假設,則轉入步驟3,否則轉入步驟7。

步驟 3設Tri對應的關聯深度為di,當di=Nmax則執行步驟4后轉入步驟6,否則di

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

步驟 5設pij為Tij的后驗概率,Tri中在k-di+1掃描與Tij關聯相同量測的所有航跡(包括Tij)的后驗概率之和為pi,如果pij≥ps_thr且pi≥pb_thr,則執行步驟4,再轉步驟6,否則認為di掃描量測不足以支持決策,故di:=di+1,轉入步驟6。

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

步驟 7令is=i,然后s:=s+1,轉入步驟6。

步驟 8如果s

步驟 9設航跡樹Tril在k-dil+1掃描中以j量測為根的航跡分支的后驗概率之和為pj,其中后驗概率和最大的量測為jl。若dil=Nmax則執行步驟10后轉入步驟12,否則dil

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

步驟 11如果pjl≥pb_thr,執行步驟10后轉入步驟12,否則dil:=dil+1,轉入步驟12。

步驟 12令l:=l+1,轉入步驟8。

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

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

圖5　關聯深度自適應過程示例Fig.5　Example of an AAD process

3　仿真實驗與分析

本節給出兩個仿真實驗,以說明本文關AAD-MHT方法的有效性。

3.1幾乎交叉目標跟蹤實驗

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

表1　算法結果對比

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

圖7給出了兩個航跡對應航跡樹的關聯深度隨掃描的變化情況。前20次掃描中,目標間距較大,此時關聯深度N=1;第20個掃描后,目標間距減小,單掃描量測不足以支持關聯決策,故N值逐漸增大,直到Nmax;第40個掃描后兩目標逐漸遠離,故N值逐漸減小直到Nmin。

圖6　幾乎交叉目標跟蹤實驗結果Fig.6　Results of tracking nearly crossed targets

圖7　關聯深度N的自適應變化Fig.7　Adaptive change of association depth N

3.2編隊飛機跟蹤實驗

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

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

圖8　編隊飛機目標跟蹤結果Fig.8　Results of tracking target in formation

表2給出了幾項指標比較,說明在平均意義下,AAD-MHT的起始時刻比GNN早28.5個掃描,并且航跡持續時間較長,真實航跡正確關聯率高于后者。

兩個仿真實驗結果表明,AAD方法確實能夠根據關聯情景的難易程度自適應地調整N值,能夠在兼顧性能的同時減小計算量,說明了AAD-MHT算法的有效性。

表2　不同算法性能比較

4　結　論

MHT的基本思想是對每種關聯情況多掃描考察,而非根據現有數據立即給出不可逆轉的關聯決策。由于關聯情況的多樣性,MHT算法的計算量必然很大,這給工程上實時應用提出了挑戰?？紤]到很多假設是極低可能的假設,因此必須對MHT算法的各個步驟做精心設計,盡可能保留高可能假設,同時盡可能降低假設航跡數目。本文重點描述了TOMHT的關鍵算法及具體實現,包括航跡樹生成、航跡得分計算、航跡聚類、假設生成、航跡刪除等。基于關聯深度應與跟蹤場景相匹配的思想,提出了一種利用航跡后驗概率的AAD方法,每個航跡樹的關聯深度可隨著關聯情況自適應的變化。此方法在復雜情況下使用較大的關聯深度保證了跟蹤性能,在簡單情況下使用較小的關聯深度降低了計算量。本文的兩個仿真實驗驗證了本文基于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. (王智.機載多傳感器數據融合技術研究[D].南京:南京理工大學,2010.)

[20]LuYB,SunW.Amulti-sensordatafusionalgorithmbasedMHT[J].Journal of China Academy of Electronics and Information Technology,2008,3(1):24-28. (陸耀賓,孫偉. 基于MHT的多傳感器數據融合算法[J].中國電子科學研究院學報, 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].電子與信息學報, 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；網絡優先出版日期：2016-07-03。

TN 953

A

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

陳杭(1990-),男,碩士研究生,主要研究方向為雷達信號處理與數據處理。

E-mail:chenhanghb@126.com

張伯彥(1957-),女,研究員,博士,主要研究方向為現代雷達控制與數據處理、機動多目標跟蹤、數據融合。

E-mail:zhbyhktk@163.com

陳映(1984-),女,高級工程師,博士,主要研究方向為雷達數據處理、彈道目標跟蹤。

E-mail:michelle_cv@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160703.1240.004.html