一種機動目標多假設跟蹤方法

胡 敏，邱金鳳，許 紅，李榮鋒

(1 航天南湖電子信息技術股份有限公司， 湖北 荊州 434000；2.海軍工程大學電子工程學院， 武漢 430033)

多假設跟蹤(Multiple Hypothesis Tracking，MHT)[1-3]采用一種延遲判決邏輯，通過建立和傳播多個候選假設，由后續的量測數據來解決當前時刻的數據關聯問題。由于利用了多個時刻的量測信息，理論上MHT的性能優于傳統的全局最近鄰(Global Nearest Neighbor，GNN)[4]、概率數據關聯(Probability Data Association，PDA)[5]和聯合數據關聯(Joint Probability Data Association，JPDA)[6]，因而被廣泛應用于各種多目標跟蹤(Multiple Target Tracking，MTT)場景[7-9]。

MHT方法最早由Reid[3]于1979年提出，該方法面向量測構造關聯假設，通過枚舉可行的全局假設，并計算假設的概率來給出最優的量測關聯結果。因此，該方法實質上是基于假設的MHT方法(Hypothesis-oriented MHT，HOMHT)。然而，在復雜跟蹤場景中，枚舉可行的全局假設是一個NP-難問題，因此文獻[3]中HOMHT方法難以實際應用。文獻[10]通過利用Murty 算法來生成假設，避免了枚舉操作，減低了HOMHT的計算復雜度。文獻[11]提出了面向航跡的MHT方法(Track-oriented MHT，TOMHT)，該方法是一種“自上而下”的方法，其通過更新的航跡節點來生成全局假設，避免了維持和傳播假設。相比于HOMHT，TOMHT的計算復雜度和實現難度更低，因而，在MTT領域多采用TOMHT方法[1]。

本文基于TOMHT方法開展研究，TOMHT的難點在于最優全局假設的生成。針對該問題，基于圖論的TOMHT方法近年來倍受關注。文獻[12]指出最優假設生成問題等價于最大權重獨立集(Maximum Weighted IndependentSet，MWIS)問題。為了引用方便，本文將傳統的基于(Multi-dimensional Assignment，MDA)和基于MWIS的MHT方法分別簡記為MDA-MHT和MWIS-MHT。與MDA-MHT相比，MWIS-MHT具備如下優勢[12-14]：MWIS-MHT在概念上更加簡潔明了；MWIS是一個經典的組合優化問題已被廣泛研究，因此利用現有的MWIS求解算法可更加高效的求解全局假設。需要說明的是，現有的MWIS-MHT方法的運動模型均為單一模型，在目標機動場景下，會存在性能損失，并不適合于多機動目標場景。

針對現有的MWIS-MHT方法并不適用于多機動目標跟蹤的問題，本文將交互式多模型(IMM)算法應用于MWIS-MHT，提出了基于交互式多模型的MWIS-MHT方法。所提方法采用多種運動模型對機動目標進行跟蹤，因而更適用于多機動目標跟蹤場景。此外，相比于MDA-MHT，所提方法基于MWIS生成最優假設，具有更低的計算復雜度。仿真實驗驗證了所提算法的有效性。

1 MHT問題描述

MHT通過建立多個候選假設并通過假設評估及管理技術來實現多目標跟蹤。為了便于后文描述算法原理，本文將MHT中常用的術語總結于表1，其中部分術語定義借鑒于文獻[15]。

表1 MHT常用術語定義

MHT考慮量測數據可能源于新生目標、虛警或已有航跡。為了便于描述算法，MHT方法有如下假設：傳感器的檢測概率為PD；虛警和新目標分別服從空間密度為λF和λN的泊松分布；一個目標在不漏檢條件下僅能產生一個量測。

此外，為了便于后文描述算法，本節給出量測數據和航跡的定義。假設第k時刻傳感器接收的量測數據定義為

(1)

(2)

2 所提方法原理與實現

本節將IMM算法引入到MWIS-MHT框架中，提出了適用于機動目標的多假設跟蹤方法。為了行文方便，本文將所提方法簡記MWIS-IMM-MHT，其原理框圖如圖1。

圖1 MWIS-IMM-MHT方法原理框圖

下面對MWIS-IMM-MHT的關鍵實現步驟進行詳細論述。

2.1 IMM算法原理

機動目標跟蹤一直是目標跟蹤領域的研究熱點，其難點在于目標運動的不確定性[16]。IMM算法[17]通過引入模型交互步驟，具有1 階廣義偽貝葉斯(Generalized Pseudo Bayesian，GPB)算法的計算復雜度優勢，同時兼備2 階GPB 算法的跟蹤性能，實現了跟蹤精度與算法復雜度的折中。因此，IMM算法被廣泛應用于各類機動目標跟蹤問題。在給定的跳變線性馬爾科夫狀態空間模型[17]的基礎上，IMM算法包含如下步驟：

1) 模型交互：

(3)

2) 模型預測：

(4)

3) 模型更新：

(5)

需要說明的是，模型的詳細實現過程見文獻[18]。

2.2 航跡得分

(6)

(7)

(8)

(9)

其中，λN表示新生目標的空間密度。航跡的狀態通過概率序列比檢驗(Sequential Probability Ratio Test，SPRT)[2]確定。具體來所，SPRT通過將航跡得分與預先設置的刪除門限Tl和確認門限Tu進行對比進而判斷航跡的狀態。門限參數Tl和Tu的設置見文獻[2]。

(10)

其中，J表示全局假設的數目。

2.3 全局假設生成

(11)

圖2給出了MWIS生成最優全局假設。

圖2 MWIS生成最優全局假設示意圖

圖2(a)給出了從t=k-2時刻至t=k時刻的3株航跡樹的示意圖，圖中的圓代表了航跡節點，圓中的數字表示量測數據序列號，定義見式。一株航跡樹由根節點、分支和葉節點構成，圖2(a)中在第k時刻總共包含了8條航跡，其航跡標簽為{T1，…，T8}。圖2(b)給出了3株航跡樹在第k時刻對應的加權無向圖的示意圖，圖中的圓代表了第k時刻航跡節點，圓中的數字表示航跡標簽，圓外的數字表示航跡得分，連接邊由航跡的相容關系確定。圖2(b)中的藍色航跡節點{T2，T5，T8}為MWIS生成最優全局假設。

2.4 方法實現的幾個技巧

為了確保MWIS-IMM-MHT方法的性能及執行效率，本文考慮如下技巧：

1) 運動模型集設置。運動模型集直接影響了IMM算法的性能。運動模型集設置可以根據跟蹤場景中的機動目標運動特點的先驗知識[21]進行設計，也可通過更為精細的方法如最小模型距離法、矩匹配法和基于優化的方法等。

2) 航跡聚類。航跡聚類將所有的航跡節點分解為多個無共享量測的子簇，進而將復雜關聯問題分解為諸多小規模的關聯問題。由于子簇間并無共享量測，因此子簇的關聯問題可并行求解。圖2(a)中的3株航跡樹可分為兩個子簇，其中航跡樹1和航跡樹2為一個子簇，航跡樹3為第二個子簇。一種高效的航跡聚類方法可參考文獻[11]。

(12)

圖3 N-幀剪枝示意圖(N=2)

3 仿真實驗

本節通過仿真實驗驗證MWIS-IMM-MHT方法對機動多目標的跟蹤性能，并與現有的MWIS-MHT[12]方法進行對比。

3.1 仿真場景設置

仿真實驗考慮2維空間中的多機動目標，目標的加速度矢量a(t)=a(t)∠θ(t)滿足半-馬爾科夫過程[22]。簡而言之，在隨機駐留一段時間后，加速度的大小a(t)和相位θ(t)由某一狀態跳變至另一狀態。半-馬爾科夫過程的完整數學模型參考文獻[22]中的式(8)至式(14)。仿真試驗中，目標的初始加速度大小設置為0，初始相位在區間[-π，π]內隨機分布，加速度的參數設置與文獻[22]一致。仿真實驗的其他參數設置如下：目標數目N=15，目標檢測概率PD=0.95，虛警空間密度λF=1×10-8，采樣時間T=2 s，觀測時間TK=200 s，X軸與Y軸的量測誤差標準差相同，其標準差σX=σY=50 m。圖4給出了一組隨機生成的真實目標軌跡的仿真場景。為了能夠生成具有挑戰性的多目標航跡，仿真實驗將目標航跡的起始和終點中心點均設置為原點。

圖4 仿真場景示意圖

MWIS-IMM-MHT方法的運動模型集設置為：勻速(Constant Velocity，CV)模型、勻加速(Constant Acceleration，CA)模型和Singer模型，模型的先驗概率為[1/3 1/3 1/3]，馬爾科夫模型轉移概率矩陣為

(13)

模型參數設置如下：CV模型的過程噪聲方差設置為δCV=10；CA模型的過程噪聲方差設置為δCA=1；Singer模型的機動時間常數τ=10 s，最大加速度aM=40 m/s2。航跡樹的最大深度設置為N=5；MWIS問題采用Tabu搜索法求解，其中最大搜索深度設置為L=10，最大迭代次數設置為nmax=50；新生目標空間密度λN=1×10-8。SPRT的參數設置為：虛假航跡確認概率α=10-6；真實航跡檢測概率β=10-3。本文將采用CV模型、CA模型和Singer模型的MWIS-MHT分別簡記為MWIS-CV-MHT、MWIS-CA-MHT和MWIS-Singer-MHT，其過程噪聲方差參數設置如下：MWIS-CV-MHT中的過程噪聲方差設置為δCV=400，MWIS-CA-MHT的過程噪聲方差設置為δCA=10，MWIS-Singer-MHT中的最大加速度設置為aM=80 m/s2。需要說明的是，單模型MWIS-MHT的過程噪聲取值更大的目的是為了擴大跟蹤器的適用范圍。

為了能夠評估算法的關聯性能、估計精度和運行效率，本文借鑒文獻[13-14]中的評估指標，采用如下指標：

1) 真實航跡數目NT。真航跡定義為由跟蹤算法給出的航跡中至少有50% 的量測來自同一個目標。該指標主要評估關聯的正確性及航跡的連續性。

2) 虛假航跡數目Nf。不滿足真航跡定義的航跡。該指標主要評估關聯的正確性。

3) 航跡的誤關聯率RMC。所有真航跡中誤關聯的量測點數目與真航跡長度之和的比值。顯然RMC越小越好，理想條件下RMC=0。該指標主要評估關聯的正確性。

4) 位置均方根誤差Rp。根據算法估計的目標位置與真實航跡的目標位置計算位置的均方根誤差。該指標主要評估算法的位置估計精度。

5) 速度均方根誤差Rv。根據算法估計的目標速度和真實航跡的目標速度計算速度均方根誤差。

6) (Optimal Subparrern Assignment，OSPA)距離。OSPA距離是用來衡量集合之間差異程度的距離度量，可綜合評估目標的狀態估計精度及目標數目估計的準確性。

7) 運行時間TE。TE定義為算法處理一幀數據的機器運行平均時間。該指標主要評估算法的執行效率。

3.2 實驗結果與分析

圖5給出了圖4場景中MWIS-CV-MHT和MWIS-IMM-MHT方法的跟蹤軌跡和OSPA曲線。由于現有的MWIS-MHT軌跡均是基于CV模型的，因此圖5僅僅給出了MWIS-CV-MHT軌跡。圖5(a)和圖5(b)中的綠色點表示量測點跡(包含虛警和真實目標)，藍色軌跡為目標真實軌跡，紅色軌跡為跟蹤算法輸出的軌跡。由圖5(a)和圖5(b)可知：MWIS-CV-MHT軌跡出現了航跡中斷問題，而MWIS-IMM-MHT跟蹤航跡連續穩定。由圖5(c)可知：初始時刻MWIS-CV-MHT軌跡和MWIS-IMM-MHT軌跡的OSPA曲線相當，這是由于仿真實驗的初始運動均為勻速運動，而當目標機動后，MWIS-CV-MHT的OSPA曲線顯著高于MWIS-IMM-MHT軌跡。這是由于MWIS-CV-MHT曲線采用了較大方差的過程噪聲，因此濾波器的去噪能力顯著下降，同時航跡中斷也會引起OSPA曲線抬升。

表2給出了100次蒙特卡羅仿真實驗的統計結果。由表可知，MWIS-IMM-MHT的NT與真實目標數目15最為接近，這表明了所提方法在跟蹤連續性方面具備最優性能。從跟蹤精度來看，MWIS-IMM-MHT的位置均方根誤差和速度均方根誤差最小，因而具有最優的狀態估計精度。從關聯性能來看，MWIS-IMM-MHT并非最優，但其性能也優于MWIS-CA-MHT和MWIS-Singer-MHT。從運行效率來看，MWIS-IMM-MHT的單幀處理時間約為現有方法的兩倍，計算復雜度并沒有顯著增加。

圖5 跟蹤軌跡和OSPA曲線

表2 100次蒙特卡羅仿真結果

4 結論

提出了一種多假設跟蹤方法。將交互式多模型算法引入，采用多種運動模型對機動目標進行跟蹤，該方法能兼顧計算效率上的優勢。仿真結果表明：相比于單模型方法，多假設跟蹤方法能提升跟蹤的連續性和狀態估計的精度，更適用于多機動目標跟蹤問題。