基于隱馬爾可夫模型的目標航跡匹配方法?

張宏宇 陶 智

（1.91001部隊 北京 100000）（2.海裝裝備項目管理中心 北京 100000）

1 引言

近年來，隨著我國國家實力的增強，海上目標的行為活動規律備受關注。在海上目標偵查監視過程中，目標經常在某個海域附近進行著相似的偵查活動，這使得目標的運動航跡具有較強的相似性。通過對目標動態航跡與目標歷史航跡進行關聯匹配分析、判斷目標的活動規律已經成為海上偵查監視工作的重要任務之一。

動態航跡指的是雷達對某個空中或者海上移動目標在運動過程中采集得到的位置、時間、方向及速度等數據按照時間先后順序構成的運動數據。依據動態航跡在歷史航跡大數據中匹配與目標航跡最為相似的航跡數據，從而識別出動態航跡的目標屬性。此類問題實際上可以歸類為軌跡匹配問題，通過一定的匹配算法計算多條軌跡之間的相似程度，從而為后續的軌跡聚類、目標識別、個性化推薦或其它相關應用提供相應的技術支持［1］。

現有的匹配方法根據使用的信息可以分為三類：1）幾何匹配方法，2）概率統計匹配方法以及3）其他高級匹配方法。幾何匹配方法可以歸納為三類，點到點的匹配方法［2］，點到線的匹配方法［3］以及線到線的匹配方法［4］。點到點的匹配方法計算探測點與候選軌跡中每個節點的距離，然后將探測點匹配到距離最近的節點上。點到線的匹配方法計算探測點到候選軌跡的投影距離，然后選擇最近的軌跡作為匹配軌跡，相應的投影點就是匹配節點。線到線的匹配方法將探測到的整條軌跡與候選軌跡進行相似性比較，最終選擇相似度最高的候選軌跡。幾何匹配方法的優點在于計算簡單，效率較高，但是適應性以及穩定性較差，精度較低，難以滿足實際的復雜應用需求。

基于概率信息，Ochieng等［5］提出了針對復雜道路網絡中的地圖匹配算法；文獻［6～7］提出了置信區間匹配方法，基于多假設思想，在置信區域內選出多條航跡加入到候選航跡中，然后對每條候選航跡都計算出一個得分，最終選擇得分最高的航跡作為匹配航跡。基于概率的匹配方法推導比較復雜，實現比較困難；并且算法計算開銷較大，匹配準確性較低，難以滿足實時性需求。

高級匹配方法往往使用綜合信息，使用機器學習或數據挖掘方法來完成匹配過程，具體包括卡爾曼濾波［8～9］，隱馬爾可夫模型［10～11］等。基于卡爾曼濾波中的白噪聲假設，通過分析卡爾曼濾波后的模型誤差特性是否滿足高斯白噪聲分布來完成匹配過程。隱馬爾可夫模型是一種全局匹配算法，可以綜合距離、方向等多個約束獲取最佳的軌跡序列。相對于前述的其他匹配方法，使用綜合信息的匹配算法準確率較高，算法的適應性也更好，算法本身也更加穩定。

現有的軌跡匹配工作主要集中于室外空間或路網空間中，而針對于航跡匹配的研究較少。其次，在現有的少量雷達航跡匹配的相關研究中，往往只考慮距離因素［12］，而忽略了航向、速度、方位、仰角以及高度等重要的運動特征信息，難以滿足復雜的應用需求。第三，現有研究往往關注離線、或者是靜態航跡的相似性，對于動態航跡、實時航跡的相似性關注較少。因此，針對現有研究狀況的不足，本文展開相應的研究工作，其主要內容包括以下幾點：1）由于隱馬爾可夫模型被廣泛應用于軌跡匹配中，并且匹配精度和穩定性明顯優于其他方法，因此，本文采用隱馬爾可夫模型來進行雷達航跡相似性匹配，以及相應的軟件設計；2）本文中對現有的隱馬爾可夫模型進行了相應的改進，加入了航向因素，使用綜合信息來完成匹配過程；3）基于現有的雷達航跡歷史數據，進行仿真實驗和測試，實時計算顯示航跡與歷史航跡的匹配結果，并且在界面上顯示相應的匹配概率；4）根據雷達航跡相似性匹配結果，完成基于活動規律的目標識別。

2 研究方法

隱馬爾可夫模型（Hidden Markov Model，HMM）最早是在20世紀60年代由Baum等在一系列統計學論文［13～15］中提出和描述的，主要應用在語音識別、行為分析、自然語言處理等領域。隱馬爾可夫模型可以解決三類問題：1）評價問題，將最可能的情況與觀測序列匹配，使用前向算法求解（Forward algorithm）；2）解碼問題，使用維比特算法（Viterbi algorithm）確定最可能產生觀察序列的隱藏序列；3）學習問題，使用前向-后向算法（Forward-backward algorithm）確定模型最可能產生的觀測序列。航跡匹配問題實際上可以歸類為一個解碼問題。基于HMM的航跡匹配是在給定序列前提下，尋找產生這一觀測序列的隱藏序列。其中，觀測序列表示雷達探測獲得的航跡點，而隱藏序列表示運動目標的歷史航跡構成的航跡網。

在基于HMM的航跡匹配算法中，對于每一個雷達探測點，存在多個候選航跡。當前雷達探測點在這些候選航跡上的投影視為候選航跡點，在隱馬爾可夫模型中作為頂點（如圖1所示），并且具有一個觀測狀態概率，表征探測航跡點是否與候選航跡匹配的可能性。探測點與候選航跡的距離越近，則觀測概率值越大。然后，計算馬爾可夫鏈中連接相鄰頂點的邊權重，稱為狀態轉移概率。最后，在馬爾可夫鏈中尋找使觀測概率和轉移概率的乘積最大化的最優路徑，一般使用維比特算法來進行求解。維比特算法實際上是一個動態規劃算法，在這里被用來解決隱馬爾可夫模型中的預測問題。

在隱馬爾可夫模型中，最關鍵的步驟是計算觀測概率和轉移概率。雷達探測航跡點的測量誤差可以被合理的描述為一個雷達探測點和歷史實際路段之間距離的高斯分布（式（1））。其中，高斯分布中的均值μ取0，標準差δ取10km，可根據具體實驗尺度進行調節。

ci表示馬爾可夫鏈中的候選點，‖‖pi-ci表示探測點與候選航跡點之間的空間距離。兩者之間的空間距離越近，則計算得到的觀察概率越大。

在Newson等［11］的算法中，觀測概率僅與距離因素相關。然而，在實際應用中，觀測概率也需要考慮方向權重［16］，因此，本研究中對觀測概率的計算進行了改進，加入了航向因素，具體計算方法如式（2）、（3）、（4）所示。式（2）為航向因素的觀察概率的計算公式，其中為速度方向與匹配航跡路段的夾角。以正北方向為基準，分別計算探測航跡以及歷史航跡與正北方向的夾角，標記為 βi和的計算方法如式（3）所示。綜合距離因素和航向因素，觀測概率的計算公式可以標記為二者的觀測概率積（見式（4））。

本研究中傳遞概率的計算基于如下假設：運動目標總是選擇空間距離最近的路線航行，前后航跡中的距離越小，其傳遞概率越大。轉移概率V的計算方法如式（5）所示，根據前后兩個時間點t和s之間的探測點 pi-1、pi及其候選點的信息，推測從 pi-1到 pi的真實路徑是到最短路徑的可能性。其中，di-1→i表示兩個探測航跡點之間的空間距離；w(i-1，t)→(i，s)表示兩個候選點之間的最短航跡距離。這樣匹配出的結果可以避免出現繞路航行或者航跡不連續的情況。

圖1 基于隱馬爾可夫模型的航跡匹配過程示例

基于HMM的航跡匹配過程可計算出各候選點的觀測概率及各候選點的轉移概率（如圖1所示）。具體計算過程如下：從c0開始，c0有3個候選點，它們的總概率分別為0.8×0.5=0.4，0.3×0.2=0.06，0.5×0.2=0.1。其中最大值為，于是c0成功匹配到。接下來對于，先計算路徑=0.6×0.8=0.48，同理計算路徑的得分等于max｛0.4+0.6×0.8，0.06+0.6×0.5，0.1+0.6×0.3｝，即為0.88。然后，針對每個候選點重復上述過程，算法最終得到的匹配結果為。

3 仿真驗證分析

3.1 實驗流程

仿真系統為多平臺多目標場景，模擬輸出目標的真實動態航跡，其具體的實驗驗證流程如圖2所示。首先，根據歷史航跡數據完成建庫和索引工作。在實際的驗證過程中，為了提高實時計算的效率，根據目標屬性建立了三個數據庫，分別為空客A320、波音737以及波音747等民航航班的歷史航跡數據庫。其次，為了提高歷史航跡搜索效率，本文中采用R樹［17～18］索引來查詢歷史航跡數據。R樹是一種與B樹相類似的高度平衡樹，它被廣泛應用到空間數據庫當中，用于解決傳統數據庫索引檢索空間對象效率低效的問題。

圖2 仿真試驗流程圖

然后，采用隱馬爾可夫模型進行航跡匹配。根據第二部分方法中介紹的觀測概率和傳遞概率的計算方法，分別計算得到各個候選航跡的觀測概率和傳遞概率。在觀測概率計算過程中，需要考慮距離和航向等多重運動特征因素，綜合衡量航跡間的相似性。最后使用維比特算法求解出相似路徑，同時輸出每條路徑的匹配概率。

在實際的計算過程中，對三個歷史航跡數據庫分別進行建模和索引，減輕索引負擔，同時并行計算以提高計算效率。此外，分別計算三個歷史航跡數據庫中的航跡匹配概率，取最大值分別標記為P1，P2，P3，并且以百分比的形式顯示在活動規律識別界面上。最后，根據上面計算得出的匹配概率，選擇最大值，標記目標屬性。例如，如果P1值最大，則該飛行目標為空客A320的可能性最大，因而被標記為空客A320。從而完成基于運動特征的目標識別，進一步輔助綜合識別等其他應用。

3.2 實驗結果分析

仿真驗證的具體實驗結果如圖3所示。基于空客A320、波音737和波音747歷史航跡數據，實驗使用隱馬爾可夫模型計算仿真動態航跡和歷史航跡的匹配概率，并且將匹配概率值以百分比的形式標記在界面上。目標運行過程中，基于隱馬爾可夫模型的匹配過程動態進行，界面上顯示的匹配概率動態更新，實時顯示運動目標的局部匹配結果。運動目標停止后，界面上顯示運動目標航跡的全局匹配結果。

圖3 動態航跡匹配結果圖

如結果所示的全局匹配結果，動態航跡與空客A320活動路線的匹配概率為75%，與波音737歷史航跡的匹配概率為15%，與波音747歷史航跡的匹配概率為4%。由此可以得到，該模擬航跡與空客A320活動路線的匹配概率最高。因此，從活動規律上判斷，該運動目標最有可能歸屬于空客A320。同時將該匹配概率結果發送給綜合識別模塊，輔助目標進一步識別。

4 結語

本文針對仿真系統多目標平臺時，雷達輸出目標航跡與歷史航跡的相似性問題，采用隱馬爾可夫模型來進行目標航跡與歷史航跡之間的關聯匹配。該算法突破了目標航跡與歷史航跡長度不一致限制、航跡不連續的限制，并且能夠有效地消除噪聲點的影響，對于航跡的關聯匹配具有較好的計算能力。基于隱馬爾可夫模型的雷達航跡關聯匹配方法已經應用在實際工程中，初步實現了基于活動規律的目標識別，為進一步的綜合目標識別奠定了基礎。

然而，本文實現的航跡匹配方法仍然存在一定的局限性，具體表現為僅僅考慮了航跡的空間距離和航向相似性，并未考慮時間因素［19］、其他多特征因素［20］以及位置語義特征［1］對航跡匹配的影響。其次，現有的方法適用于簡單場景，暫時未對復雜場景做匹配分析研究。因此，在后續的研究中，研究方向主要體現為以下兩點：1）繼續補充多特征以及多維度相似性度量因素，為綜合匹配識別提供更加有效的依據和證據；2）根據具體應用需要，因地制宜，提高算法對復雜場景的匹配效果和效率，實現航跡的精準化關聯匹配。