基于聯合概率數據互聯的多假設跟蹤算法

閆 龍，王曙曜，黃 磊，姚 遠

(中國船舶集團有限公司第八研究院，南京 211153)

0 引 言

多假設跟蹤(Multiple Hypothesis Tracking，MHT)算法采用延遲決策邏輯，通過不斷產生多種可能的假設，利用未來接收到的量測來幫助解決當前量測與航跡之間的關聯問題。該算法提供了一個將航跡起始、航跡維持以及航跡終結等功能統一的多目標跟蹤框架。在檢測概率比較低、雜波和目標密集的跟蹤環境下，MHT算法被認為是目前具有最優關聯性能的數據關聯算法。[1]Reid首先提出了面向假設的多假設跟蹤(Hypothesis-Oriented MHT，HOMHT)算法，Cox等給出了面向假設的MHT的一種高效率實現方案，并提出了一種面向航跡的多假設跟蹤(Track-Oriented MHT，TOMHT)方法[2]。目前，國外針對MHT算法的理論研究較為成熟，提出了許多改進的算法及快速實現的方法。國內高校也開展了針對MHT算法的研究，形成了一些著作和論文，并形成了相關的軟件產品。

隨著軟硬件技術的發展和電磁環境的復雜化，應用MHT算法提高雜波環境中多目標跟蹤性能的呼聲越來越高。據此，本文提出了基于JPDA的TOMHT算法，采用預測波門連通分組的方法對多目標進行航跡分簇處理，采用序貫概率比檢驗(SPRT)、N-Scan剪枝法和K-Best全局最優法進行假設管理，對于簇內可能存在的不相容航跡樹進行JPDA聯合概率分配來保證不相容航跡樹的互斥性，對雜波環境下的多目標穩定跟蹤具有較大改善。目前，該算法已應用于艦載某三坐標預警雷達系統中，取得了較好的效果。

1 TOMHT算法

1.1 TOMHT算法處理框架

MHT算法的具體實現方案可分為HOMHT算法和TOMHT算法兩種。HOMHT算法是一種自頂向下的方法，其在接收到量測時先產生多個全局假設，并計算出這些假設的概率，然后據此計算每條航跡的概率。而TOMHT算法是一種自下向上的方法，其在接收到量測時首先對現有航跡樹進行更新，之后再根據更新后的航跡樹形成全局假設。雖然兩者在原理上十分接近，但由于目前TOMHT算法的實現更為簡單、高效，所以TOMHT算法應用更為廣泛。圖 1給出了TOMHT算法的流程圖。

圖1 TOMHT算法流程圖

1.2 航跡形成與維持

當接收到新的量測時，TOMHT算法對現有的航跡進行各種可能的量測-航跡關聯，增長現有的航跡樹，起始新的航跡樹。針對每一個落入已有假設航跡關聯門內的量測，將對應假設航跡分叉形成一棵具有相同量測根結點的航跡樹，同時為每一個假設航跡賦予一個確認概率，其描述了當前假設航跡為真實目標航跡的概率。TOMHT中的假設航跡數量會隨時間指數增長。因此，為限制TOMHT算法的計算復雜度，需要對假設航跡進行管理，及時刪除虛假航跡。

1.3 基于得分的航跡剪枝

采用序貫概率比檢驗法(Sequential Probability Ratio Test，SPRT)對航跡進行管理。SPRT將最新時刻所有航跡的航跡得分與兩個閾值比較，如果航跡得分大于確認閾值則確認該航跡，如果小于刪除閾值則刪除該航跡。

(1)

ηd=ln(β/(1-α))

(2)

ηc=ln((1-β)/α)

(3)

其中，ηd為刪除門限；ηc為確認門限；α為虛假航跡的確認概率，也被成為第1類錯誤概率；β為正確航跡的刪除概率，也被成為第2類錯誤概率。

1.4 分 簇

簇是指包含所有直接或間接共享相同量測的假設航跡的集合。從簇的定義可以看出，不同簇內的航跡總是相容的。因此，所有航跡的全局假設可以通過對不同簇中得到的全局假設進行組合而得到。這樣相當于將整個航跡集分成了若干個子集，以使全局假設的生成能夠在每個子集中獨立完成，從而降低算法的計算量。以n個航跡為例，由于全局假設生成算法的計算量約為n3，如果能夠把所有航跡分為10個等量簇，即每個簇中包含n/10個航跡，那么整個算法的計算量約為10×(n/10)3=n3/100，計算量為不分簇時計算量的1/100。

1.5 假設形成與剪枝

剪枝是一種有效限制假設航跡數量的方法，具體操作是根據之前得到的最優全局假設，確定航跡樹根結點的關聯情況，同時刪除航跡樹根結點的其他分支。航跡樹剪枝過程如圖 2所示。

圖2 航跡樹剪枝

圖2中TOMHT算法的延遲深度N為3，假定全局最優假設為包含航跡樹葉子結點11的航跡。由于航跡樹T深度超出延遲深度3，所以航跡樹T將只保留右邊包含存在于最優全局假設的航跡分支，由此確認結點3所代表的量測將與假設航跡相關聯。由于該操作將確認延遲深度N時刻之前航跡與量測的關聯關系，因此通常也被稱為N回掃剪枝。

1.6 基于全局假設的航跡剪枝

完成N回掃剪枝之后，為進一步減少假設航跡的數量，基于假設形成與剪枝中求出的前k個最優全局假設對航跡進行進一步地刪除，基本思想是幾乎沒有出現在前k個最優全局假設中的航跡很大可能不是真實的目標航跡。

1.7 航跡更新

若在N時刻航跡與量測關聯，則使用交互多模型(Interacting Multiple Model，IMM)濾波算法對航跡的狀態進行濾波更新，若不存在關聯量測則對航跡的狀態進行外推更新。

1.8 航跡輸出

最后，根據航跡得分實時輸出處于已確認狀態的最佳航跡信息。

2 基于JPDA的點航跡關聯方法

2.1 傳統JPDA算法

雜波環境下的多目標數據互聯技術是多目標跟蹤中最重要又是最難處理的問題。聯合概率數據互聯(Joint Probabilistic Data Association，JPDA)是解決這一問題的一種良好的算法。JPDA的目的就是計算每一個量測與其可能的各種源目標相互關聯的概率，回波落入不同目標相關波門的重疊區域內時則必須綜合考慮各個目標量測的目標來源情況。為了表示有效回波和各航跡跟蹤波門的復雜關系，JPDA引入了確認矩陣的概念。[3]

(4)

其中，ωjt是二進制變量，ωjt=1表示量測j落入航跡t的確認門內，而ωjt=0表示量測j沒有落入航跡t的確認內。t=0表示沒有航跡，此時對應的列元素ωj0全都是1，因為每一個量測都可能源于雜波或者是虛警。

對于一個給定的多目標航跡跟蹤問題，在建立了有效回波與航跡或雜波互聯關系的確認矩陣后，就可以通過對確認矩陣的拆分得到所有表示互聯事件的互聯矩陣，在對確認矩陣進行拆分時必須依據以下的兩個基本假設：

(1) 每一個量測有唯一的源，即任一量測不源于某一個目標則必源于雜波，即該量測為虛警；

(2) 對于一個給定目標，最多有一個量測以其為源。如果一個目標有可能與多個量測相匹配，將取一個為真，其他為假。

依據上述的兩個假設來實現由確認矩陣到互聯矩陣的拆分：

(1) 在確認矩陣的每一行，選出一個且僅選出一個1作為互聯矩陣在該行唯一非零的元素；

(2) 在可行矩陣中，除第一行外，每列最多只能有一個非零元素，即滿足第2個假設。

雙目標航跡不存在虛假點跡時點航跡JPDA算法關聯過程如圖 3所示。落入目標航跡1關聯波門內的有2個點跡，落入目標航跡2關聯波門內的有1個點跡。JPDA算法建立一個航跡和點跡的確認矩陣。該矩陣維數為2×3，2表示量測的個數，3表示的是航跡數目加1。由建立的確認矩陣可以拆分為5個互聯事件，每一個互聯事件代表了一種點跡航跡的分配關系，經過計算選擇其中概率最大的作為點跡航跡的分配依據。

圖3 JPDA點航跡關聯過程示意圖

2.2 基于JPDA的TOMHT算法

傳統TOMHT算法在航跡形成與維持的過程中簇內航跡與檢測波門內量測點跡均產生航跡分支。這樣會導致航跡樹過于龐大，后期處理中濾波、剪枝及管理會造成計算量指數倍增，同時會產生航跡樹間分支合并的問題。

針對傳統TOMHT算法的上述問題，結合JPDA算法的優點，本文提出基于JPDA的TOMHT算法，主要進行以下改進：

(1) 在TOMHT跟蹤框架的基礎上引入JPDA算法參與點航跡分配。通過遍歷各航跡分支的預測波門，將預測波門存在重疊區域的航跡分為同一簇，同時將簇內所有預測波門區域的并集作為該簇的檢測波門。這樣，對簇內不相容航跡分支和簇檢測波門內量測點跡進行聯合概率數據互聯分配，達到保證不相容航跡樹的互斥性的目的，降低航跡樹分簇時對葉節點的搜索工作量，提高量測點跡和簇內航跡樹間假設航跡的關聯正確率和實時性，避免出現樹間分支合并的問題。

(2) 在航跡維持的基礎上計算航跡得分，若航跡得分處于下降通道則對該航跡分支進行擴大波門檢測相關點跡，若檢測到相關點跡則根據相關點跡進行濾波產生航跡分支，若未檢測到相關點跡則進行航跡外推產生航跡分支。

3 仿真與試驗

3.1 雜波背景下密集目標的跟蹤效果

仿真場景中有3個運動的目標，目標運動狀態為勻速直線，起始距離35 km，速度280 m/s，航向225°，高度50 m，目標間隔約750 m。目標量測點跡誤差為距離誤差30 m，方位誤差0.2°，仰角誤差0.2°，掃描周期2 s，探測概率為0.9。雜波點跡分布為5 km×5 km×1 km的空間里3個雜波點跡。仿真目標運動軌跡如圖 4所示。

圖4 3批密集目標運動軌跡

對同一仿真數據，分別采用本文提出的基于JPDA的TOMHT算法和JPDA算法進行跟蹤，濾波方法采用IMM算法。兩種方法在關聯波門的設置，濾波器參數方面完全一致，跟蹤結果分別如圖 5和圖 6所示。

圖5 基于JPDA的TOMHT算法對3批密集目標的跟蹤效果

圖6 JPDA算法對3批密集目標的跟蹤效果

針對密集目標的跟蹤效果對比表明，在無雜波仿真條件下，本文提出的基于JPDA的TOMHT算法和JPDA算法相差無幾。在雜波仿真條件下，本文提出的基于JPDA的TOMHT算法相比于JPDA算法具有明顯的優勢。

3.2 雜波背景下隨機多批目標的跟蹤效果

仿真場景中有20個運動的目標，目標運動狀態分為非機動和機動。

非機動目標方位在0°～360°隨機產生，距離在10～100 km隨機產生，速度在50～280 m/s隨機產生，航向在0°～360°隨機產生，高度在100 ～15 000 m隨機產生。非機動樣式分為勻速直線、勻速切向、勻速徑向。

機動目標方位在0°～360°隨機產生，距離在10～100 km隨機產生，速度在50 ～280 m/s隨機產生，航向在0°～360°隨機產生，高度在100～15 000 m隨機產生。機動樣式分為轉彎、加減速，機動程度在1、3、5、10 g隨機產生。

目標量測點跡誤差為距離誤差30 m，方位誤差0.2°，仰角誤差0.2°，掃描周期2 s，探測概率為0.9。雜波點跡分布為5 km×5 km×1 km的空間里3個雜波點跡。

本文提出的基于JPDA的TOMHT算法和JPDA算法對雜波環境下對20批隨機目標的跟蹤效果分別如圖7和圖8所示。

圖7 基于JPDA的TOMHT算法對20批隨機

圖8 JPDA算法對20批隨機目標的跟蹤效果

跟蹤效果對比表明，在雜波較復雜的場景下，針對不同機動程度、不同機動方式、不同速度的典型機動目標以及非機動目標，本文提出的基于JPDA的TOMHT算法比JPDA算法對目標的跟蹤航跡更完整連貫平滑，穿雜波能力更強，具有明顯優勢。另外，由于保證不相容航跡樹的互斥性，避免了同一簇內互斥航跡分支關聯同一量測點跡，導致航跡樹分支數量倍增及后期合并等問題，降低航跡樹分簇時對葉節點的搜索工作量，基于JPDA的TOMHT算法比傳統MHT算法的實時性更強，更適合復雜雜波環境下密集目標的跟蹤。

3.3 基于仿真目標的跟蹤性能定量評估

本文設計了下列4種指標用于算法性能定量評估。一般來說，在進行算法比較時總是從指標集中選擇若干作為評估準繩。

(1) 漏情率

對于一個真實目標，如果在某一掃描時刻沒有真航跡對應于該真實目標，則稱該真實目標在該時刻的信息被漏掉，否則該真實目標在該時刻的信息沒有被漏掉。一個真實目標的漏情率為其被漏掉的掃描時刻數和總掃描時刻數的比值。規定一個算法的漏情率為仿真場景中所有真實目標的漏情率的平均值。

(2) 真航跡的平均誤關聯率

所有真航跡中誤關聯的量測點數目與真航跡壽命之和的比值。在理想的數據關聯無差錯的情況下，誤關聯率等于0。誤關聯率反映了數據關聯的質量，顯然誤關聯率越小越好。

(3) 目標量測的正確關聯率

正確關聯到相應真航跡的量測占所有來自真實目標的量測的比率。這個變量反映出跟蹤算法對真實目標量測的利用率，也是評價數據關聯質量的指標之一。

(4) 位置估計的均方根誤差

對所有算法給出的真航跡，計算它們與對應的目標航跡真值的位置RMSE。

對雜波背景下隨機20批目標的跟蹤性能進行定量評估，通過50次蒙特卡羅仿真試驗，統計對20批目標跟蹤的各項指標均值，結果見表1。

表1 跟蹤性能指標計算結果

4 結束語

基于MHT算法的雜波環境下多目標跟蹤是當前研究的熱點。本文在研究傳統JPDA算法和MHT算法的基礎上提出一種基于JPDA的TOMHT算法，將JPDA模型引入TOMHT跟蹤框架作為雜波環境密集目標場景下航跡跟蹤樹間關聯互斥的方法，采用預測波門連通分組的方法進行航跡分簇處理。對于簇內可能存在的不相容航跡樹進行JPDA聯合概率分配來保證不相容航跡樹的互斥性。通過仿真試驗，定性定量比較了基于JPDA的TOMHT算法和JPDA算法對雜波環境下多目標的跟蹤性能。結果表明，基于JPDA的TOMHT算法在正確關聯率和濾波精度上均存在明顯優勢，對雜波環境下對多目標跟蹤具有一定適應性和有效性。