基于聯(lián)合概率數(shù)據(jù)互聯(lián)的多假設(shè)跟蹤算法

閆 龍，王曙曜，黃 磊，姚 遠(yuǎn)

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

0 引 言

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

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

1 TOMHT算法

1.1 TOMHT算法處理框架

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

圖1 TOMHT算法流程圖

1.2 航跡形成與維持

當(dāng)接收到新的量測(cè)時(shí)，TOMHT算法對(duì)現(xiàn)有的航跡進(jìn)行各種可能的量測(cè)-航跡關(guān)聯(lián)，增長(zhǎng)現(xiàn)有的航跡樹，起始新的航跡樹。針對(duì)每一個(gè)落入已有假設(shè)航跡關(guān)聯(lián)門內(nèi)的量測(cè)，將對(duì)應(yīng)假設(shè)航跡分叉形成一棵具有相同量測(cè)根結(jié)點(diǎn)的航跡樹，同時(shí)為每一個(gè)假設(shè)航跡賦予一個(gè)確認(rèn)概率，其描述了當(dāng)前假設(shè)航跡為真實(shí)目標(biāo)航跡的概率。TOMHT中的假設(shè)航跡數(shù)量會(huì)隨時(shí)間指數(shù)增長(zhǎng)。因此，為限制TOMHT算法的計(jì)算復(fù)雜度，需要對(duì)假設(shè)航跡進(jìn)行管理，及時(shí)刪除虛假航跡。

1.3 基于得分的航跡剪枝

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

(1)

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

(2)

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

(3)

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

1.4 分 簇

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

1.5 假設(shè)形成與剪枝

剪枝是一種有效限制假設(shè)航跡數(shù)量的方法，具體操作是根據(jù)之前得到的最優(yōu)全局假設(shè)，確定航跡樹根結(jié)點(diǎn)的關(guān)聯(lián)情況，同時(shí)刪除航跡樹根結(jié)點(diǎn)的其他分支。航跡樹剪枝過程如圖 2所示。

圖2 航跡樹剪枝

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

1.6 基于全局假設(shè)的航跡剪枝

完成N回掃剪枝之后，為進(jìn)一步減少假設(shè)航跡的數(shù)量，基于假設(shè)形成與剪枝中求出的前k個(gè)最優(yōu)全局假設(shè)對(duì)航跡進(jìn)行進(jìn)一步地刪除，基本思想是幾乎沒有出現(xiàn)在前k個(gè)最優(yōu)全局假設(shè)中的航跡很大可能不是真實(shí)的目標(biāo)航跡。

1.7 航跡更新

若在N時(shí)刻航跡與量測(cè)關(guān)聯(lián)，則使用交互多模型(Interacting Multiple Model，IMM)濾波算法對(duì)航跡的狀態(tài)進(jìn)行濾波更新，若不存在關(guān)聯(lián)量測(cè)則對(duì)航跡的狀態(tài)進(jìn)行外推更新。

1.8 航跡輸出

最后，根據(jù)航跡得分實(shí)時(shí)輸出處于已確認(rèn)狀態(tài)的最佳航跡信息。

2 基于JPDA的點(diǎn)航跡關(guān)聯(lián)方法

2.1 傳統(tǒng)JPDA算法

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

(4)

其中，ωjt是二進(jìn)制變量，ωjt=1表示量測(cè)j落入航跡t的確認(rèn)門內(nèi)，而ωjt=0表示量測(cè)j沒有落入航跡t的確認(rèn)內(nèi)。t=0表示沒有航跡，此時(shí)對(duì)應(yīng)的列元素ωj0全都是1，因?yàn)槊恳粋€(gè)量測(cè)都可能源于雜波或者是虛警。

對(duì)于一個(gè)給定的多目標(biāo)航跡跟蹤問題，在建立了有效回波與航跡或雜波互聯(lián)關(guān)系的確認(rèn)矩陣后，就可以通過對(duì)確認(rèn)矩陣的拆分得到所有表示互聯(lián)事件的互聯(lián)矩陣，在對(duì)確認(rèn)矩陣進(jìn)行拆分時(shí)必須依據(jù)以下的兩個(gè)基本假設(shè)：

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

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

依據(jù)上述的兩個(gè)假設(shè)來(lái)實(shí)現(xiàn)由確認(rèn)矩陣到互聯(lián)矩陣的拆分：

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

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

雙目標(biāo)航跡不存在虛假點(diǎn)跡時(shí)點(diǎn)航跡JPDA算法關(guān)聯(lián)過程如圖 3所示。落入目標(biāo)航跡1關(guān)聯(lián)波門內(nèi)的有2個(gè)點(diǎn)跡，落入目標(biāo)航跡2關(guān)聯(lián)波門內(nèi)的有1個(gè)點(diǎn)跡。JPDA算法建立一個(gè)航跡和點(diǎn)跡的確認(rèn)矩陣。該矩陣維數(shù)為2×3，2表示量測(cè)的個(gè)數(shù)，3表示的是航跡數(shù)目加1。由建立的確認(rèn)矩陣可以拆分為5個(gè)互聯(lián)事件，每一個(gè)互聯(lián)事件代表了一種點(diǎn)跡航跡的分配關(guān)系，經(jīng)過計(jì)算選擇其中概率最大的作為點(diǎn)跡航跡的分配依據(jù)。

圖3 JPDA點(diǎn)航跡關(guān)聯(lián)過程示意圖

2.2 基于JPDA的TOMHT算法

傳統(tǒng)TOMHT算法在航跡形成與維持的過程中簇內(nèi)航跡與檢測(cè)波門內(nèi)量測(cè)點(diǎn)跡均產(chǎn)生航跡分支。這樣會(huì)導(dǎo)致航跡樹過于龐大，后期處理中濾波、剪枝及管理會(huì)造成計(jì)算量指數(shù)倍增，同時(shí)會(huì)產(chǎn)生航跡樹間分支合并的問題。

針對(duì)傳統(tǒng)TOMHT算法的上述問題，結(jié)合JPDA算法的優(yōu)點(diǎn)，本文提出基于JPDA的TOMHT算法，主要進(jìn)行以下改進(jìn)：

(1) 在TOMHT跟蹤框架的基礎(chǔ)上引入JPDA算法參與點(diǎn)航跡分配。通過遍歷各航跡分支的預(yù)測(cè)波門，將預(yù)測(cè)波門存在重疊區(qū)域的航跡分為同一簇，同時(shí)將簇內(nèi)所有預(yù)測(cè)波門區(qū)域的并集作為該簇的檢測(cè)波門。這樣，對(duì)簇內(nèi)不相容航跡分支和簇檢測(cè)波門內(nèi)量測(cè)點(diǎn)跡進(jìn)行聯(lián)合概率數(shù)據(jù)互聯(lián)分配，達(dá)到保證不相容航跡樹的互斥性的目的，降低航跡樹分簇時(shí)對(duì)葉節(jié)點(diǎn)的搜索工作量，提高量測(cè)點(diǎn)跡和簇內(nèi)航跡樹間假設(shè)航跡的關(guān)聯(lián)正確率和實(shí)時(shí)性，避免出現(xiàn)樹間分支合并的問題。

(2) 在航跡維持的基礎(chǔ)上計(jì)算航跡得分，若航跡得分處于下降通道則對(duì)該航跡分支進(jìn)行擴(kuò)大波門檢測(cè)相關(guān)點(diǎn)跡，若檢測(cè)到相關(guān)點(diǎn)跡則根據(jù)相關(guān)點(diǎn)跡進(jìn)行濾波產(chǎn)生航跡分支，若未檢測(cè)到相關(guān)點(diǎn)跡則進(jìn)行航跡外推產(chǎn)生航跡分支。

3 仿真與試驗(yàn)

3.1 雜波背景下密集目標(biāo)的跟蹤效果

仿真場(chǎng)景中有3個(gè)運(yùn)動(dòng)的目標(biāo)，目標(biāo)運(yùn)動(dòng)狀態(tài)為勻速直線，起始距離35 km，速度280 m/s，航向225°，高度50 m，目標(biāo)間隔約750 m。目標(biāo)量測(cè)點(diǎn)跡誤差為距離誤差30 m，方位誤差0.2°，仰角誤差0.2°，掃描周期2 s，探測(cè)概率為0.9。雜波點(diǎn)跡分布為5 km×5 km×1 km的空間里3個(gè)雜波點(diǎn)跡。仿真目標(biāo)運(yùn)動(dòng)軌跡如圖 4所示。

圖4 3批密集目標(biāo)運(yùn)動(dòng)軌跡

對(duì)同一仿真數(shù)據(jù)，分別采用本文提出的基于JPDA的TOMHT算法和JPDA算法進(jìn)行跟蹤，濾波方法采用IMM算法。兩種方法在關(guān)聯(lián)波門的設(shè)置，濾波器參數(shù)方面完全一致，跟蹤結(jié)果分別如圖 5和圖 6所示。

圖5 基于JPDA的TOMHT算法對(duì)3批密集目標(biāo)的跟蹤效果

圖6 JPDA算法對(duì)3批密集目標(biāo)的跟蹤效果

針對(duì)密集目標(biāo)的跟蹤效果對(duì)比表明，在無(wú)雜波仿真條件下，本文提出的基于JPDA的TOMHT算法和JPDA算法相差無(wú)幾。在雜波仿真條件下，本文提出的基于JPDA的TOMHT算法相比于JPDA算法具有明顯的優(yōu)勢(shì)。

3.2 雜波背景下隨機(jī)多批目標(biāo)的跟蹤效果

仿真場(chǎng)景中有20個(gè)運(yùn)動(dòng)的目標(biāo)，目標(biāo)運(yùn)動(dòng)狀態(tài)分為非機(jī)動(dòng)和機(jī)動(dòng)。

非機(jī)動(dòng)目標(biāo)方位在0°～360°隨機(jī)產(chǎn)生，距離在10～100 km隨機(jī)產(chǎn)生，速度在50～280 m/s隨機(jī)產(chǎn)生，航向在0°～360°隨機(jī)產(chǎn)生，高度在100 ～15 000 m隨機(jī)產(chǎn)生。非機(jī)動(dòng)樣式分為勻速直線、勻速切向、勻速?gòu)较颉?/p>

機(jī)動(dòng)目標(biāo)方位在0°～360°隨機(jī)產(chǎn)生，距離在10～100 km隨機(jī)產(chǎn)生，速度在50 ～280 m/s隨機(jī)產(chǎn)生，航向在0°～360°隨機(jī)產(chǎn)生，高度在100～15 000 m隨機(jī)產(chǎn)生。機(jī)動(dòng)樣式分為轉(zhuǎn)彎、加減速，機(jī)動(dòng)程度在1、3、5、10 g隨機(jī)產(chǎn)生。

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

本文提出的基于JPDA的TOMHT算法和JPDA算法對(duì)雜波環(huán)境下對(duì)20批隨機(jī)目標(biāo)的跟蹤效果分別如圖7和圖8所示。

圖7 基于JPDA的TOMHT算法對(duì)20批隨機(jī)

圖8 JPDA算法對(duì)20批隨機(jī)目標(biāo)的跟蹤效果

跟蹤效果對(duì)比表明，在雜波較復(fù)雜的場(chǎng)景下，針對(duì)不同機(jī)動(dòng)程度、不同機(jī)動(dòng)方式、不同速度的典型機(jī)動(dòng)目標(biāo)以及非機(jī)動(dòng)目標(biāo)，本文提出的基于JPDA的TOMHT算法比JPDA算法對(duì)目標(biāo)的跟蹤航跡更完整連貫平滑，穿雜波能力更強(qiáng)，具有明顯優(yōu)勢(shì)。另外，由于保證不相容航跡樹的互斥性，避免了同一簇內(nèi)互斥航跡分支關(guān)聯(lián)同一量測(cè)點(diǎn)跡，導(dǎo)致航跡樹分支數(shù)量倍增及后期合并等問題，降低航跡樹分簇時(shí)對(duì)葉節(jié)點(diǎn)的搜索工作量，基于JPDA的TOMHT算法比傳統(tǒng)MHT算法的實(shí)時(shí)性更強(qiáng)，更適合復(fù)雜雜波環(huán)境下密集目標(biāo)的跟蹤。

3.3 基于仿真目標(biāo)的跟蹤性能定量評(píng)估

本文設(shè)計(jì)了下列4種指標(biāo)用于算法性能定量評(píng)估。一般來(lái)說(shuō)，在進(jìn)行算法比較時(shí)總是從指標(biāo)集中選擇若干作為評(píng)估準(zhǔn)繩。

(1) 漏情率

對(duì)于一個(gè)真實(shí)目標(biāo)，如果在某一掃描時(shí)刻沒有真航跡對(duì)應(yīng)于該真實(shí)目標(biāo)，則稱該真實(shí)目標(biāo)在該時(shí)刻的信息被漏掉，否則該真實(shí)目標(biāo)在該時(shí)刻的信息沒有被漏掉。一個(gè)真實(shí)目標(biāo)的漏情率為其被漏掉的掃描時(shí)刻數(shù)和總掃描時(shí)刻數(shù)的比值。規(guī)定一個(gè)算法的漏情率為仿真場(chǎng)景中所有真實(shí)目標(biāo)的漏情率的平均值。

(2) 真航跡的平均誤關(guān)聯(lián)率

所有真航跡中誤關(guān)聯(lián)的量測(cè)點(diǎn)數(shù)目與真航跡壽命之和的比值。在理想的數(shù)據(jù)關(guān)聯(lián)無(wú)差錯(cuò)的情況下，誤關(guān)聯(lián)率等于0。誤關(guān)聯(lián)率反映了數(shù)據(jù)關(guān)聯(lián)的質(zhì)量，顯然誤關(guān)聯(lián)率越小越好。

(3) 目標(biāo)量測(cè)的正確關(guān)聯(lián)率

正確關(guān)聯(lián)到相應(yīng)真航跡的量測(cè)占所有來(lái)自真實(shí)目標(biāo)的量測(cè)的比率。這個(gè)變量反映出跟蹤算法對(duì)真實(shí)目標(biāo)量測(cè)的利用率，也是評(píng)價(jià)數(shù)據(jù)關(guān)聯(lián)質(zhì)量的指標(biāo)之一。

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

對(duì)所有算法給出的真航跡，計(jì)算它們與對(duì)應(yīng)的目標(biāo)航跡真值的位置RMSE。

對(duì)雜波背景下隨機(jī)20批目標(biāo)的跟蹤性能進(jìn)行定量評(píng)估，通過50次蒙特卡羅仿真試驗(yàn)，統(tǒng)計(jì)對(duì)20批目標(biāo)跟蹤的各項(xiàng)指標(biāo)均值，結(jié)果見表1。

表1 跟蹤性能指標(biāo)計(jì)算結(jié)果

4 結(jié)束語(yǔ)

基于MHT算法的雜波環(huán)境下多目標(biāo)跟蹤是當(dāng)前研究的熱點(diǎn)。本文在研究傳統(tǒng)JPDA算法和MHT算法的基礎(chǔ)上提出一種基于JPDA的TOMHT算法，將JPDA模型引入TOMHT跟蹤框架作為雜波環(huán)境密集目標(biāo)場(chǎng)景下航跡跟蹤樹間關(guān)聯(lián)互斥的方法，采用預(yù)測(cè)波門連通分組的方法進(jìn)行航跡分簇處理。對(duì)于簇內(nèi)可能存在的不相容航跡樹進(jìn)行JPDA聯(lián)合概率分配來(lái)保證不相容航跡樹的互斥性。通過仿真試驗(yàn)，定性定量比較了基于JPDA的TOMHT算法和JPDA算法對(duì)雜波環(huán)境下多目標(biāo)的跟蹤性能。結(jié)果表明，基于JPDA的TOMHT算法在正確關(guān)聯(lián)率和濾波精度上均存在明顯優(yōu)勢(shì)，對(duì)雜波環(huán)境下對(duì)多目標(biāo)跟蹤具有一定適應(yīng)性和有效性。