紅外點目標(biāo)跟蹤方法綜述*

王碩，張奕群,2,孫冰巖

(1.北京電子工程總體研究所，北京　100854； 2.北京仿真中心航天系統(tǒng)仿真重點實驗室，北京　100854；3.中國人民解放軍駐航天科工集團第二研究院第二十三研究所軍事代表室，北京　100854)

?

探測跟蹤技術(shù)

紅外點目標(biāo)跟蹤方法綜述*

王碩1，張奕群1,2,孫冰巖3

(1.北京電子工程總體研究所，北京100854； 2.北京仿真中心航天系統(tǒng)仿真重點實驗室，北京100854；3.中國人民解放軍駐航天科工集團第二研究院第二十三研究所軍事代表室，北京100854)

摘要：綜述了常見的紅外點目標(biāo)跟蹤方法。介紹了全局最近鄰(GNN)、概率數(shù)據(jù)關(guān)聯(lián)(PDA)、聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)(JPDA)、多假設(shè)跟蹤(MHT)和動態(tài)規(guī)劃(DPA)等算法，討論了它們的區(qū)別、聯(lián)系。介紹了概率假設(shè)密度(PHD)濾波方法，指出它在跟蹤多目標(biāo)方面相比其他算法的優(yōu)勢。展望了紅外點目標(biāo)跟蹤方法的研究前景，提出對DPA和PHD兩算法的繼續(xù)研究是今后的重要研究方向。

關(guān)鍵詞：紅外點目標(biāo)；檢測；跟蹤；先跟蹤后檢測；貝葉斯估計；多目標(biāo)

0引言

傳統(tǒng)意義上，在點目標(biāo)跟蹤過程中，一般先利用閾值將目標(biāo)從含噪聲的圖像中分割出來，再將各幀分割出來的目標(biāo)關(guān)聯(lián)起來形成軌跡。由于噪聲的幅值也可能超過閾值，因此被分割出來的點可能是目標(biāo)，也可能是虛警，這些點在本文中統(tǒng)稱為“潛在目標(biāo)”。若目標(biāo)的信噪比高、同時目標(biāo)數(shù)目不多，那么很容易選擇合適的閾值將真目標(biāo)較“干凈”地分割出來，且跟蹤目標(biāo)也相對簡單。但實際上，常常需要同時跟蹤大量的目標(biāo)，另外也更希望跟蹤盡可能遠的目標(biāo)(即信噪比盡可能低的目標(biāo))，這使目標(biāo)的跟蹤問題變得相對復(fù)雜。若目標(biāo)的數(shù)目很多且分布相對密集，則跟蹤的難點在于如何處理潛在目標(biāo)與軌跡的分配，即后文提到的關(guān)聯(lián)沖突。而若目標(biāo)的信噪比很低、潛在目標(biāo)中虛警所占比例大，那么從潛在目標(biāo)中挑選真目標(biāo)會變得困難、也容易出錯，故跟蹤的難點在于如何從大量潛在目標(biāo)中準(zhǔn)確區(qū)分少數(shù)的真目標(biāo)。實際的跟蹤問題往往是以上兩方面的結(jié)合，依據(jù)側(cè)重點的不同，逐漸形成了不同的目標(biāo)跟蹤方法。

從20世紀(jì)六七十年代起，人們開始系統(tǒng)地研究點目標(biāo)跟蹤問題，將常見的目標(biāo)跟蹤算法暫且分為3個研究階段。早期的研究集中在實現(xiàn)基本的單步目標(biāo)跟蹤，其中全局最近鄰(GNN)算法[1]、概率數(shù)據(jù)關(guān)聯(lián)(PDA)算法[2]及聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)(JPDA)算法[3-4]是其中的代表。GNN算法是最基本的跟蹤方法，建立了包括目標(biāo)預(yù)報、目標(biāo)搜索及軌跡關(guān)聯(lián)在內(nèi)的整個目標(biāo)跟蹤過程。PDA算法首次將加權(quán)平均的概念引入目標(biāo)跟蹤過程中，減少了目標(biāo)軌跡被虛警“拉走”的可能性。JPDA算法則是最早提出利用剔除矛盾假設(shè)的辦法解決多目標(biāo)關(guān)聯(lián)沖突的跟蹤方法，其“多種可能就做多種假設(shè)”的想法為接下來的跟蹤算法研究提供了發(fā)展思路。

隨后的研究逐漸側(cè)重于利用多步策略解決較低信噪比的目標(biāo)的跟蹤問題。在眾多研究成果中，多假設(shè)跟蹤(MHT)算法[5-7]和動態(tài)規(guī)劃算法(DPA)[8]是其中的代表。MHT算法是應(yīng)用最為廣泛的利用多步跟蹤和延遲邏輯來確定真目標(biāo)的方法，它提供了非常優(yōu)秀的目標(biāo)跟蹤性能。DPA算法是一種重要的先跟蹤后檢測算法，也是目前最有效的低信噪比目標(biāo)跟蹤方法，它通過逆向分步尋優(yōu)實現(xiàn)在跟蹤過程中檢測目標(biāo)，取得了檢測效果和計算量上的平衡。

近年來，研究熱點側(cè)重于解決如何快速跟蹤大量目標(biāo)的問題。對這類問題，JPDA，MHT等傳統(tǒng)算法都是通過對潛在目標(biāo)的分配，將多目標(biāo)聯(lián)合跟蹤問題轉(zhuǎn)變?yōu)槎鄠€并行的單目標(biāo)跟蹤問題來處理。當(dāng)目標(biāo)數(shù)多，這種處理辦法會導(dǎo)致關(guān)聯(lián)假設(shè)過多，關(guān)聯(lián)組合爆炸。Markov鏈蒙特卡羅(MCMC)數(shù)據(jù)關(guān)聯(lián)方法[9]，利用有限的樣本數(shù)對潛在目標(biāo)的最優(yōu)分配進行估計，被證明有效減小了算法在多目標(biāo)跟蹤時的計算量。而基于有限集統(tǒng)計(FISST)理論的概率假設(shè)密度(PHD)濾波方法[10]，利用PHD實現(xiàn)了多目標(biāo)的聯(lián)合跟蹤，避免了對潛在目標(biāo)的分配，也就減小了跟蹤目標(biāo)的計算量，改善了跟蹤性能。PHD方法被普遍認為是目前最有發(fā)展前景的多目標(biāo)跟蹤方法。

1目標(biāo)跟蹤方法

1.1搜索區(qū)域的設(shè)置

引言提到，受噪聲影響，潛在目標(biāo)中存在虛警。在利用已有目標(biāo)軌跡預(yù)測出下一時刻的目標(biāo)位置后，若以預(yù)測位置為中心設(shè)置搜索范圍，在該區(qū)域中尋找目標(biāo)，則可大幅度降低虛警與目標(biāo)軌跡匹配的可能性，提高目標(biāo)的跟蹤性能。

區(qū)域的大小要考慮虛警和漏檢2方面的因素。區(qū)域太大則虛警增加，太小則漏檢增加。Sea先后提出了矩形和橢圓區(qū)域的設(shè)置方法，其中的橢圓區(qū)域得到了廣泛的應(yīng)用，其半徑的確定方法如下[1]。

首先定義對數(shù)似然比函數(shù)

(1)

(2)

(3)

這樣，式(1)可以化成

(4)

定義另外一個對數(shù)似然比函數(shù)LLRU，

(5)

由于PFA通常很小，則LLRU可簡化為

(6)

為使目標(biāo)能夠被分割出來，要求LLRD大于或等于LLRU，即

(7)

則

(8)

式中：

β=PFA/M，

(9)

1.2全局最近鄰(GNN)算法

GNN算法[1]是最基本的跟蹤方法，其實現(xiàn)方式如下。

在搜索區(qū)域內(nèi)，將潛在目標(biāo)j與真目標(biāo)i的相似程度用似然函數(shù)gij表示：

(10)

圖1　關(guān)聯(lián)沖突情況示例Fig.1　Illustration of association conflict

表1　關(guān)聯(lián)沖突的分配矩陣

若分配矩陣較大，計算量會很大。對這一分配問題，Kuhn最初利用Hungarian算法[12]尋找最優(yōu)解，但該算法只能求解正方形的分配陣。為此，Munkres等人提出了可求解一般矩形分配陣的Munkres算法[13-14]。隨后，Jonker和Bertsekas等人提出了J-V松弛算法[15]和拍賣算法[16]，進一步減小了分配耗時。

顯而易見，若目標(biāo)的信噪比很高、搜索區(qū)域內(nèi)不含虛警，GNN算法的目標(biāo)軌跡就是真目標(biāo)軌跡。但由于該方法將目標(biāo)預(yù)測位置附近的某個單點作為真目標(biāo)，則一旦區(qū)域內(nèi)存在虛警，目標(biāo)軌跡就可能被“拉走”，使接下來的目標(biāo)預(yù)測精度下降，從而可能導(dǎo)致連續(xù)地選擇假目標(biāo)進行軌跡關(guān)聯(lián)，甚至導(dǎo)致軌跡中斷。故只要搜索區(qū)域內(nèi)存在虛警，算法的跟蹤性能就會明顯下降。

1.3概率數(shù)據(jù)關(guān)聯(lián)(PDA)算法

(11)

式中：權(quán)值wj為

(12)

(13)

這樣，用潛在目標(biāo)的加權(quán)代替由GNN算法選出的單個潛在目標(biāo)，PDA算法能夠減小目標(biāo)軌跡被虛警“拉走”的機會。仿真結(jié)果顯示，采用PDA算法可以顯著減小門限內(nèi)偶爾存在虛警時，目標(biāo)跟蹤丟失的概率[2]。

應(yīng)該指出，采用PDA算法給目標(biāo)跟蹤帶來的改善是有限的。若某一幀門限內(nèi)虛警較多、或接連幾幀門限內(nèi)均存在虛警，目標(biāo)軌跡仍會被“拉走”，致使跟蹤性能下降。同時，由于PDA算法的目標(biāo)軌跡均由加權(quán)目標(biāo)構(gòu)成，只要存在虛警，其軌跡與真目標(biāo)軌跡之間就存在偏差。而相同條件下，GNN算法的軌跡若未被假目標(biāo)拉走，其軌跡與真目標(biāo)軌跡是相同的。

1.4聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)(JPDA)算法

為解決PDA算法在多目標(biāo)跟蹤時的關(guān)聯(lián)沖突，Bar-Shalom等人在PDA算法的基礎(chǔ)上又提出了JPDA算法[3-4]。仍以圖1的情況為例，JPDA算法先列出所有的軌跡關(guān)聯(lián)假設(shè)，再將其中存在關(guān)聯(lián)沖突的假設(shè)去掉，計算剩余的各關(guān)聯(lián)假設(shè)hi的概率p(hi)，見表2。以h2為例，p(h2)相當(dāng)于事件“P1與01關(guān)聯(lián)”及事件“P2軌跡中斷”同時發(fā)生的概率。因為01為P1的目標(biāo)的概率是PDg11，02，03是虛警的概率是β2，P2的目標(biāo)沒被分割出來的概率是(1-PD)，故

p(h2)=β2PD(1-PD)g11.

(14)

(15)

(16)

).　(17)

對JPDA算法來說，若想計算式(13)中的wij，必須列舉出全部的關(guān)聯(lián)假設(shè)。如果目標(biāo)的個數(shù)多，那么關(guān)聯(lián)假設(shè)的數(shù)量就會很多，出現(xiàn)NP-hard問題[17-20]，導(dǎo)致JPDA算法的計算量很大。為此，Oh等人提出了一種Markov鏈蒙特卡羅數(shù)據(jù)關(guān)聯(lián)(MCMCDA)算法[9]。該算法對表2的部分關(guān)聯(lián)假設(shè)采樣，再利用Markov鏈蒙特卡羅方法由樣本來估計wij。這樣，計算wij前無需再將全部假設(shè)列舉出來，僅需有限的關(guān)聯(lián)假設(shè)樣本就可以了。仿真結(jié)果表明，在跟蹤大量目標(biāo)時，MCMCDA算法比JPDA算法更有效率，而跟蹤性能相差不大。

上述方法只適用于信噪比高的目標(biāo)。如果目標(biāo)的信噪比低，受虛警的影響，這些方法就很難達到要求的跟蹤性能。為實現(xiàn)對低信噪比目標(biāo)的有效跟蹤，常采用多步跟蹤和延遲邏輯，將多幀數(shù)據(jù)結(jié)合在一起使用，以達到或增強目標(biāo)的信噪比、或更好的區(qū)分目標(biāo)與虛警的目的。

1.5多假設(shè)跟蹤(MHT)算法

單步跟蹤算法之所以不適用于低信噪比目標(biāo)，是因為只通過單幀圖像很難區(qū)別目標(biāo)和虛警。由于目標(biāo)在圖像中的運動是有規(guī)律的，若觀察連續(xù)多幀圖像中潛在目標(biāo)的位置的規(guī)律，則不難將真目標(biāo)甄別出來。多步跟蹤方法就是由這種思想發(fā)展而來。

Reid提出的MHT算法是一種典型的多步跟蹤算法[5-7,21]。還以圖1為例，k時刻各軌跡與潛在目標(biāo)的單步關(guān)聯(lián)有10種假設(shè)。在下一時刻，若在各軌跡的搜索區(qū)域內(nèi)仍存在多個潛在目標(biāo)，每一個關(guān)聯(lián)假設(shè)又會派生出多個新的關(guān)聯(lián)假設(shè)，例如圖2中由h6派生出的h6,1和h6,2等?？紤]k時刻某單步關(guān)聯(lián)假設(shè)hi及與其相關(guān)的所有歷史假設(shè)的集合，若將評價函數(shù)s(k)定義為該集合中各關(guān)聯(lián)假設(shè)的概率pk(hi)之和，即

s(k)=s(k-1)+pk(hi)，

(18)

利用SPRT[22]等方法對上述評價函數(shù)進行假設(shè)檢驗，即可得到真目標(biāo)軌跡。

圖2　MHT假設(shè)示意圖Fig.2　Hypothesis for MHT

關(guān)聯(lián)假設(shè)的數(shù)量由待跟蹤目標(biāo)個數(shù)及各搜索區(qū)域中潛在目標(biāo)數(shù)決定，每增加一步跟蹤，算法的計算量就會以指數(shù)增長。在虛警較多時，若不限制假設(shè)的規(guī)模，很容易出現(xiàn)組合爆炸。在實際使用中，MHT算法需不斷地剔除分數(shù)低的假設(shè)以減小計算量。Murty算法[23-26]，Deb和Popp等人提出的s-d分配算法[27-28]以及Kurien等人提出的面向軌跡的MHT[29-31]等均是有效的假設(shè)剔除算法。Blackman等人指出，MHT算法在剔除錯誤假設(shè)后是有可能做到實時計算的[32-33]。同時，de Feo等人在比較多種跟蹤方法后指出，若不考慮計算量，MHT算法具有在高虛警環(huán)境下跟蹤目標(biāo)的明顯優(yōu)勢[34-35]。

在低信噪比情況下，需要降低圖像分割閾值確保跟蹤過程中不漏掉目標(biāo)，但這會提高虛警概率。如對信噪比SNR=2的目標(biāo)，若要求檢測概率PD≥0.98，則虛警概率PFA≈0.52，即每幀由虛警產(chǎn)生的潛在目標(biāo)數(shù)超過圖像像素數(shù)的一半，關(guān)聯(lián)假設(shè)的數(shù)量很大。若虛警概率增大到一個極限值，比如PFA=1(即不對圖像進行閾值分割)，則MHT算法實際上成為一種對目標(biāo)軌跡窮舉式的搜索。以單目標(biāo)跟蹤為例，設(shè)圖像由M個像元構(gòu)成，若假定搜索區(qū)域為整幅圖像，各時刻目標(biāo)的位置均有M種可能(即存在M個關(guān)聯(lián)假設(shè))，各關(guān)聯(lián)假設(shè)在下一時刻又派生出M個新的關(guān)聯(lián)假設(shè)，即n幀后目標(biāo)軌跡的關(guān)聯(lián)假設(shè)數(shù)為Mn，致使MHT算法失去了工程實用價值。為此，我們需要一種減小窮舉式搜索的計算量、以實現(xiàn)低信噪比目標(biāo)跟蹤的方法，即下文介紹的DPA算法。

1.6動態(tài)規(guī)劃算法(DPA)

DPA算法是一種常見的檢測和跟蹤低信噪比目標(biāo)的方法。經(jīng)由Bellman，Larson，Viterbi等人對DPA的不斷完善[36-38]，Barniv首次將其用于低信噪比目標(biāo)的檢測，并對跟蹤性能進行了詳盡地分析[8,39]。

以跟蹤單個目標(biāo)為例，若將目標(biāo)軌跡記為(θ(n),θ(n-1),…,θ(1))，則對目標(biāo)的估計可由評價函數(shù)s(θ(n),θ(n-1),…,θ(1))的n維尋優(yōu)得到，即

(19)

如前文所述，該n維尋優(yōu)的計算量很大。若能將s(θ(n),θ(n-1),…,θ(1))拆分成多個相互獨立或僅部分相關(guān)的子評價函數(shù)之和，例如拆成如2個首尾相關(guān)的子評價函數(shù)

s(θ(n),…,θ(k+1),θ(k),…,θ(1))=

s(θ(n),…,θ(k))+s(θ(k),…,θ(1)).

(20)

則式(19)的尋優(yōu)過程便可大大簡化。但在一般情況下，評價函數(shù)均是不能拆分的，例如式(18)就無法寫成類似式(20)的形式，這一點借助式(10)，(15)及式(18)很容易證實。

Barniv找到了一種具有上述“可拆分”性質(zhì)的評價函數(shù)[8,39]，他將式(18)的pk(hi)定義為

(21)

式中：z為測量值；pk(hi)為θ(k)與θ(k-1)的關(guān)聯(lián)概率。由于按式(21)定義的pk只與pk-1相關(guān)，故s(θ(n),θ(n-1),…,θ(1))可拆分成n個只首尾相關(guān)的函數(shù)之和，即

s(θ(n),θ(n-1),…,θ(1))=

pn(θ(n),θ(n-1))+…+p2(θ(2),θ(1)).

(22)

(23)

DPA算法的這種分步尋優(yōu)，使算法的計算量由Mn減小為M2n，令其在檢測低信噪比目標(biāo)時，比MHT算法高效得多。

為進一步減小算法的計算量，可在各時刻k，將θ(k-1)的搜索范圍限制在以θ(k)為中心的某個區(qū)域內(nèi)。搜索區(qū)域的大小由目標(biāo)運動的快慢決定：目標(biāo)運動越快，θ(k-1)離θ(k)就會越遠，搜索區(qū)域就要越大。

和Barniv的工作類似，Arnold找到了另一種“可拆分”的評價函數(shù)，他將pk(hi)定義為[40]

(24)

該評價函數(shù)能夠比式(21)更有效地區(qū)分服從混合高斯分布的目標(biāo)及噪聲,如圖3所示。

圖3　Arnold評價函數(shù)特性Fig.3　Merit function for Arnold DPA

由式(21)，(24)，Barniv及Arnold的評價函數(shù)均利用了目標(biāo)及噪聲的先驗信息。在目標(biāo)信噪比很低時，先驗信息可以幫助我們將目標(biāo)從噪聲中更好地辨別出來。但先驗信息又是一把“雙刃劍”，即若先驗信息不準(zhǔn)，如對a(k)的估計與實際存在較大誤差，它反而會使檢測性能變差。

為此，Tonissen給出了一種不涉及先驗信息，而只與測量值z相關(guān)的評價函數(shù)[41]

pk(hi)=z(θ(k-1)).

(25)

利用Tonissen的評價函數(shù)，無論a(k)的估計是否準(zhǔn)確，算法的性能均不受影響。但也正是由于缺少先驗信息的修正，Tonissen方法對低信噪比目標(biāo)的檢測性能不如Barniv及Arnold方法。

DPA算法存在一些不足。

首先，跟蹤算法一般從2個方面綜合衡量某潛在目標(biāo)為真目標(biāo)的可能性：一是看各潛在目標(biāo)的幅值，即圖像中越“亮”的潛在目標(biāo)越可能是真目標(biāo)；二是看各潛在目標(biāo)與目標(biāo)預(yù)測位置的距離，即與目標(biāo)預(yù)測位置越接近的潛在目標(biāo)越可能是真目標(biāo)。由于DPA算法不具備預(yù)測目標(biāo)位置的能力，僅從“亮度”單方面評價尋優(yōu)結(jié)果的好壞，這樣目標(biāo)的信噪比越低，“亮度”這一判斷標(biāo)準(zhǔn)越不可靠，致使DPA算法在檢測運動目標(biāo)的過程中，目標(biāo)運動越快，搜索區(qū)域越大，DPA算法受噪聲干擾的機會越多，檢測性能越弱。

其次，為分辨由式(17)得到的最優(yōu)軌跡是否為目標(biāo)軌跡，需對評價函數(shù)值進行假設(shè)檢驗。在目前的研究中，目標(biāo)和噪聲軌跡的評價函數(shù)均視為服從高斯分布[39,41]，而事實上，評價函數(shù)近似服從極值分布[42]。統(tǒng)計特性的偏差會影響對檢驗門限的估計，進而影響辨別目標(biāo)軌跡的準(zhǔn)確性。

再次，由于目標(biāo)的評價函數(shù)值最大，其周圍的噪聲會關(guān)聯(lián)到目標(biāo)軌跡上，且離目標(biāo)越近，關(guān)聯(lián)越容易產(chǎn)生。噪聲與目標(biāo)軌跡關(guān)聯(lián)會使其評價函數(shù)值增大，反映到評價函數(shù)圖像上則表現(xiàn)為目標(biāo)周圍也被“點亮”，這種現(xiàn)象被稱為評價函數(shù)的擴散[43]，如圖4所示，其中A，B，C為目標(biāo)。由于評價函數(shù)的擴散，某目標(biāo)可能被其他目標(biāo)的擴散區(qū)域覆蓋，導(dǎo)致它在評價函數(shù)中無法“解析”(例如圖中目標(biāo)B，C的情況)，給多目標(biāo)的跟蹤帶來困難[44]。

事實上，擴散等同于圖1的關(guān)聯(lián)沖突。對這一問題，JPDA和MHT兩算法采用從所有的關(guān)聯(lián)假設(shè)中，剔除關(guān)聯(lián)沖突假設(shè)的解決辦法。與之類似，Pulford等人提出了下述多假設(shè)Viterbi數(shù)據(jù)關(guān)聯(lián)(MH-VDA)算法[45]。

圖4　評價函數(shù)的擴散Fig.4　Scattering of merit function for DPA

(26)

若k時刻各目標(biāo)的測量值z(θi(k))相互獨立，則

p(z(Θt(k-1))|Θt(k-1))=p(z(θ1(k-1))|θ1(k-1))p(z(θ2(k-1))|θ2(k-1))…

p(z(θt(k-1))|θt(k-1)).

(27)

由式(17)，算法在各時刻k對各Θt(k)尋找(k-1)時刻最優(yōu)的Θt(k-1)，建立各目標(biāo)軌跡的單步關(guān)聯(lián)，并以此類推得到t個目標(biāo)的軌跡。

由于在尋優(yōu)中，Pulford方法始終保持各假設(shè)的目標(biāo)數(shù)量一致，因此避免了將多個目標(biāo)與一個目標(biāo)關(guān)聯(lián)，也就避免了關(guān)聯(lián)沖突。這樣就防止了圖4中擴散的產(chǎn)生，使算法能夠準(zhǔn)確將多個目標(biāo)檢測出來。

顯然，Pulford方法要做的假設(shè)會更多，遠多于MHT算法。事實上，假設(shè)的數(shù)量為

其中：C為組合數(shù)。

在此小結(jié)一下上述目標(biāo)跟蹤方法。實際上，它們都基于貝葉斯估計。對單目標(biāo)情況，先利用Bayes預(yù)測和更新方程計算各時刻潛在目標(biāo)θ(k)的后驗密度，即

p(θ(k)|zk-1)=∫p(θ(k)|θ(k-1))p(θ(k-1)|

zk-1)dθ(k-1)，

(28)

p(θ(k)|zk)=K-1p(zk|θ(k))p(θ(k)|zk-1)，

(29)

式中：K-1為歸一化系數(shù)；p(θ(k)|θ(k-1))為目標(biāo)的狀態(tài)轉(zhuǎn)移概率。

式(28)對應(yīng)1.1節(jié)一開始所提到的由已有目標(biāo)軌跡預(yù)測接下來的目標(biāo)位置的過程。式(29)則實現(xiàn)了利用新的測量zk來修正預(yù)測結(jié)果，p(θ(k)|zk)對應(yīng)為式(10)潛在目標(biāo)θ(k)的似然函數(shù)gij。

隨后，利用上述后驗密度來估計真目標(biāo)位置。常用的估計方法包括極大后驗估計(MAP)和期望后驗估計(EAP)。對極大后驗估計，真目標(biāo)被視為后驗密度最大的那個潛在目標(biāo)，即

(30)

也就是GNN。對期望后驗估計，真目標(biāo)位置為各潛在目標(biāo)位置以各自的后驗密度為權(quán)值的加權(quán)平均，即

(31)

也就是PDA。而對MHT，DPA等多步方法，評價函數(shù)s(·)相當(dāng)于目標(biāo)軌跡上各狀態(tài)的后驗密度之和，由于真目標(biāo)被視為評價函數(shù)最大者，故它們同樣基于極大后驗估計。

對多目標(biāo)情況，式(28)，(29)中的單目標(biāo)后驗密度p(θ(k)|zk)及狀態(tài)轉(zhuǎn)移概率p(θ(k+1)|θ(k))變?yōu)槎嗄繕?biāo)后驗密度p(Θ(k)|zk)及狀態(tài)轉(zhuǎn)移概率p(Θ(k+1)|Θ(k))。由此，后驗密度的預(yù)測和更新方程相應(yīng)變?yōu)?/p>

p(Θ(k+1)|zk)=

(32)

p(Θ(k+1)|zk+1)=K-1p(zk+1|Θ(k+1))·

p(Θ(k+1)|zk).

(33)

數(shù)學(xué)上，由于后驗密度p(Θ(k)|zk)是高維的，式(32)，(33)很難直接計算。為此，一般假設(shè)各目標(biāo)的狀態(tài)及觀測相獨立，這樣p(Θ(k)|zk)就可近似為各目標(biāo)i(i=1,…,T)的后驗密度p(θi(k)|zk)的乘積，即

(34)

從而實現(xiàn)了對p(Θ(k)|zk)的降維計算，將多目標(biāo)跟蹤問題轉(zhuǎn)化為多個相獨立的單目標(biāo)跟蹤問題，簡化了計算難度。為滿足式(34)的假設(shè)，需在每一步跟蹤目標(biāo)之前剔除軌跡與潛在目標(biāo)的關(guān)聯(lián)沖突(如圖1所示)，這也就是JPDA，MHT等方法在跟蹤多目標(biāo)時需要列出表2的原因。

然而，式(32)的假設(shè)經(jīng)常是不成立的。比如，若目標(biāo)重合，在重合處就存在著關(guān)聯(lián)沖突。所以，若想從根本上解決多目標(biāo)跟蹤問題，必須要找到直接或者近似計算多目標(biāo)后驗密度p(Θ(k)|zk)的方法。

近年來，Mahler借助有限集統(tǒng)計理論(FISST)，提出用概率假設(shè)密度(PHD)來近似p(Θ(k)|zk)，并在此基礎(chǔ)上提出了PHD濾波方法，解決了近似計算多目標(biāo)后驗密度的問題[10,46]。

1.7概率假設(shè)密度(PHD)濾波方法

Mahler將高維的后驗密度p(Θ(k)|zk)用一個二維的“假設(shè)密度”PHD近似，實現(xiàn)了對p(Θ(k)|zk)的降維計算。

二維平面上某狀態(tài)θ(k)的PHD(記為D(θ(k)))被定義為各目標(biāo)i在θ(k)處的后驗密度p(θi(k)|zk)之和。這樣，PHD就有了明確的物理意義，即θ(k)的PHD越大，該θ(k)就越可能是目標(biāo)，且某區(qū)域內(nèi)各θ(k)的PHD的積分即為該區(qū)域內(nèi)目標(biāo)數(shù)的期望。

在此基礎(chǔ)上，Mahler用對PHD的預(yù)測和更新來近似式(32),(33)的對p(Θ(k)|zk)的預(yù)測和更新，即

(35)

式中：λ為與虛警有關(guān)的常數(shù)。

由于式(35)僅計算各狀態(tài)θ(k)處的后驗密度，并不用來估計目標(biāo)位置和它的軌跡，所以在得到二維平面上各θ(k)的PHD之后，需采用類似極大后驗估計或者期望后驗估計方法，由后驗密度估計目標(biāo)位置并形成軌跡[47-52]。

Erdinc等人指出，若目標(biāo)漏檢，PHD的計算會出錯[53-54]。為此，Mahler引入目標(biāo)數(shù)的高階項提出了勢概率假設(shè)密度(CPHD)濾波方法[54-56]。此外，Vo、Melzi等人提出了序貫蒙特卡羅PHD濾波、Gauss混合PHD濾波、快速傅里葉變換PHD濾波等快速計算PHD的方法[57-60]。其他有關(guān)PHD方法的發(fā)展及應(yīng)用請參見文獻[61]。

相比JPDA、MHT等傳統(tǒng)算法，PHD避免了在跟蹤多目標(biāo)時剔除關(guān)聯(lián)沖突、列舉關(guān)聯(lián)假設(shè)hi，這樣就減小了計算量，防止了在目標(biāo)數(shù)目多時遇到NP-hard問題。所以，PHD能更好完成對大量目標(biāo)的跟蹤任務(wù)。但Punithakumar等人發(fā)現(xiàn)，在跟蹤低信噪比目標(biāo)時，利用PHD會產(chǎn)生較大的軌跡偏差[62]，其目標(biāo)跟蹤性能與DPA算法相比還有一定差距。

2各算法的分析比較

前文介紹了一系列基于Bayes估計的目標(biāo)跟蹤算法。依照不同的后驗密度估計準(zhǔn)則，可以將它們大致分為基于極大后驗估計的方法，以及基于期望后驗估計(即“加權(quán)平均”)的方法2類?；凇凹訖?quán)平均”的方法一般采用單步跟蹤，利用平均思想減小因偶爾誤關(guān)聯(lián)導(dǎo)致目標(biāo)丟失的概率。然而，就像前面介紹PDA算法時所提到的，若目標(biāo)信噪比低、虛警接連出現(xiàn)在目標(biāo)周圍，目標(biāo)軌跡仍會被虛警“拉走”，導(dǎo)致目標(biāo)軌跡中斷。因此，這類方法在信噪比高的環(huán)境中更能發(fā)揮優(yōu)勢。

相對而言，基于極大后驗估計的跟蹤算法，特別是MHT、DPA這種多步算法，其優(yōu)勢體現(xiàn)在低信噪比目標(biāo)的跟蹤上。多步跟蹤算法可以利用多幀測量信息，結(jié)合目標(biāo)運動特可更準(zhǔn)確地判斷低信噪比目標(biāo)的真正位置。相比MHT，DPA在跟蹤性能和計算量上取得了較為理想的平衡，是目前跟蹤低信噪比目標(biāo)的首選。但正如前文所提到，它對運動目標(biāo)的跟蹤性能偏弱、無法準(zhǔn)確估計評價函數(shù)分布、難以跟蹤多個密集目標(biāo)。

在跟蹤多目標(biāo)方面，認為Pulford等人提出的結(jié)合多假設(shè)的DPA(即MH-VDA)是目前較好的解決方式。但該方法計算量很大，離工程實現(xiàn)還很遙遠。PHD濾波方法采用對多目標(biāo)聯(lián)合后驗密度的降維估計，克服了其它算法跟蹤多目標(biāo)計算量大的問題。然而，它在軌跡生成、低信噪比目標(biāo)跟蹤等方面還存在不足，進一步研究的空間很大。表3分別從對信噪比的要求、多目標(biāo)跟蹤能力、以及跟蹤單目標(biāo)和多目標(biāo)的計算量等角度對各算法的優(yōu)缺點進行了比較。為達到理想的跟蹤效果，選擇算法時應(yīng)依據(jù)實際需求，從對目標(biāo)的跟蹤要求、工程實現(xiàn)的復(fù)雜程度以及計算量等方面綜合衡量。

表3　算法的分析比較

3結(jié)束語

本文綜述了紅外點目標(biāo)的跟蹤算法，介紹了算法之間的聯(lián)系以及各自的特點，并從多個角度對它們加以了分析和對比。目前，多目標(biāo)跟蹤性能較好的算法對低信噪比目標(biāo)的跟蹤性能普遍較弱。反之，對低信噪比目標(biāo)跟蹤性能較好的算法對多目標(biāo)的跟蹤能力或者偏弱，或者計算量很大以致難以應(yīng)用。本文綜述的各算法中，DPA和PHD相對其他算法分別在暗目標(biāo)和多目標(biāo)跟蹤問題上更具優(yōu)勢。我們認為，對它們的完善和改進將是今后很長一段時間的研究重點。

參考文獻：

[1]BLACKMAN S, POPOLI R. Design and Analysis of Modern Tracking Systems[M].Norwood,MA: Artech House, 1999.

[2]BAR-SHALOM Y, KIRUBARAJAN T, LIN X.. Probabilistic Data Association Techniques for Target Tracking with Application to Sonar, Radar and EO Sensors[J]. IEEE Aerospace and Electronic Systems Magazine,2005, 20(8): 37-56.

[3]FORTMANN T.E, THOMAS E, BAR-SHALOM Y, et al. Sonar tracking of Multiple Targets Using Joint Probabilistic Data Association[J]. IEEE Journal of Oceanic Engineering, 1983, 8(3): 173-184.

[4]BAR-SHALOM Y, FORTMANN E T. Tracking and Data Association[M].New York: Academic Press, 1988.

[5]REID D B. An Algorithm for Tracking Multiple Targets[J]. IEEE Trans. on Automatic Control, 1979, 24(6): 843-854.

[6]REID D B. A Multiple Hypothesis Filter for Tracking Multiple Targets in a Cluttered Environment[R]. Lockheed Missiles and Space Company Report No. LMSC, D-560254, 1977.

[7]BLACKMAN S S. Multiple Hypothesis Tracking for Multiple Target Tracking[J]. IEEE Aerospace and Electronic Systems Magazine, 2004, 19(1): 5-18.

[8]BARNIV Y. Dynamic Programming Solution for Detecting Dim Moving Targets[J]. IEEE Trans. on Aerospace and Electronic Systems, 1985, 21(1): 144-156.

[9]OH S, RUSSELL S, SASTRY S. Markov Chain Monte Carlo Data Association for Multi-Target Tracking[J]. IEEE Trans to Automatic Control, 2009, 54(3):481-497.

[10]MAHLER R. Multi-Target Bayes Filtering Via First-Order Multi-Target Moment[J]. IEEE Trans. on Aerospace and Electronic Systems, 2003, 39(4): 1152-1178.

[11]TRUNK G V, WILSON J D. Track Initiation of Occasionally Unresolved Radar Targets[J]. IEEE Trans. on Aerospace and Electronic Systems, 1981, 17(3):122-130.

[12]KUHN H W. The Hungarian Method for The Assignment Problem[R]. Naval Research Logistics Quarterly No. 2, 1955: 83-97.

[13]MUNKRES J. Algorithm for The Assignment and Transportation Problems[J]. J. SIAM, 1957, 5(2): 32-38.

[14]BURGEOIS F, LASSALLE J C. An Extension of the Munkres Algorithm for the assignment Problem to Rectangular Matrices[J]. Communications of the ACM, 1971, 14(1):802-806.

[15]JONKER R, VOLGENANT A. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems[J]. Computing, 1987, 38(4): 325-340.

[16]BERTSEKAS D P. The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial[J]. Interfaces, 1990,20(2): 133-149.

[17]COLLINS J, UHLMANN J. Efficient Gating in Data Association with Multivariate Distributed States[J]. IEEE Trans. on Aerospace and Electronic Systems, 1992, 28(3): 909-916.

[18]OH S. A Distributed Deterministic Approximation Algorithm for Data Association[C]∥IEEE International Conference on Distributed Computing in Sensor Systems and Workshops, 2011.

[19]SCHULZ D, BURGARD W, FOX D, et al. Tracking Multiple Moving Targets with a Mobile Robot Using Particle Filters and Statistical Data Association[C]∥IEEE International Conference on Robotics and Automation, 2001:1665-1670.

[20]NEMETH C, FEARNHEAD P, MIHAYLOVA L. Sequential Monte Carlo Methods for State and Parameter Estimation in Abruptly Changing Environments[J]. IEEE Trans. on Signal Processing, 2014, 62(5): 1245-1255.

[21]BAR-SHALOM Y, BLACKMAN S, FITZGERALD R. The Dimensionless Score Function for Multiple Hypothesis Tracking[C]∥SPIE Signal and Data Processing of Small Targets, Vol. 5913, 2005.

[22]BLOSTEIN S D, HUANG T S. Detecting Small, Moving Objects in Image Sequences Using Sequential Hypothesis Testing[J]. IEEE Trans. on Signal Processing, 1991, 39(7): 1611-1629.

[23]COX I J, HINGORANI S L. An Efficient Implementation of Reid’s Multiple Hypotheses Tracking Algorithm and Its Evaluation for The Purpose of Visual Tracking[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1996, 18(2): 138-150.

[24]DING Z, VANDERVIES D. A Modified Murty Algorithm for Multiple Hypothesis Tracking[C]∥SPIE Signal and Data Processing of Small Targets, Vol. 6236, 2006.

[25]HE X, THARMARASA R, PELLETIER M, et al. Accurate Murty’s Algorithm for Multitarget Top Hypothesis Extraction[C]∥Proceedings of the 14th International Conference on Information Fusion, 2011.

[26]FORTUNATO E, KREAMER W, MORI S, et al. Generalized Murty’s Algorithm with Application to Multiple Hypothesis Tracking[C]∥10th International Conference on Information Fusion, 2007.

[27]DEB S, YEDDANAPUDI M, PATTIPATI K, et al. A Generalized s-d Assignment Algorithm for Multisensory-Multitarget State Estimation[J]. IEEE Trans. on Aerospace and Electronic Systems, 1997, 33(2): 523-538.

[28]POPP R, PATTIPATI K R, BAR-SHALOM Y. An M-best s-d Assignment Algorithm and Parallelization with Application to Multitarget Tracking[J]. IEEE Trans. on Aerospace and Electronic Systems, 2001, 37(1): 22-39.

[29]KURIEN T. Issues in The Design of Practical Multitarget Tracking Algorithms. Multitarget-Multisensor Tracking: Advanced Application[M].Norwood,MA: Artech House, 1990.

[30]CHAN D S K, LANGAN D.A. Performance Results of The Bi-Level MHT Tracking Algorithm for Two Crossing Targets in A High Clutter Environment[C]∥SPIE Signal and Data Processing of Small Targets, Vol. 2235, 1994: 406-416.

[31]BLOSTEIN S D, RICHARDSON H S. A Sequential Detection Approach to Target Tracking[J]. IEEE Trans. on Aerospace and Electronic Systems, 1994, 30(1): 197-211.

[32]BLACKMAN S S, DEMPSTER R, REED R. Demonstration of Multiple Hypothesis Tracking (MHT) Practical Real-Time Implementation Feasibility[C]∥SPIE Signal and Data Processing of Small Targets, Vol. 4473, 2001: 470-475.

[33]NORMAN B K, CRONIN B A, BLACKMAN S S, et al. Adaptive Processing to Ensure Practical Application of A Multiple Hypothesis Tracking System[C]∥ SPIE Sensor, and Command, Control, Communications, and Intelligence Technologies for Homeland Security and Homeland Defense, Vol. 6201, 2006.

[34]de Feo M, GRAZIANO A, MIGLIOLO R, et al. IMMJPDA Versus MHT and Kalman Filter with NN Correlation: Performance Comparison[J]. IEE Proceedings, Radar, Sonar, Navigation, 1997, 144(2),: 49-56.

[35]KENNEDY H. Comparison of MHT and PDA Tracking Initiation Performance[C]∥IEEE International Conference on Radar, 2008: 508-512.

[36]BELLMAN R. Dynamic Programming[M].Princeton,NS: Princeton University Press, 1957.

[37]LARSON R E, PESCHON J. A Dynamic Programming Approach to Trajectory Estimation[J]. IEEE Trans. on Automatic Control, 1966, 11(3): 537-540.

[38]VITERBI A J. Convolutional Codes and Their Performance in Communication Systems[J]. IEEE Trans. on Communication Technology, 1971 , 19(1): 751-772.

[39]BARNIV Y, KELLA O. Dynamic Programming Solution for Detecting Dim Moving Targets Part II: Analysis[J]. IEEE Trans. on Aerospace and Electronic Systems, 1987, 23(6): 776-788.

[40]ARNOLD J, SHAW S, PASTERNACK H. Efficient Target Tracking Using Dynamic Programming[J]. IEEE Trans. on Aerospace and Electronic Systems, 1993, 29(1): 44-56.

[41]TONISSEN S M, EVANS R J. Performance of Dynamic Programming Techniques for Track-Before-Detect[J]. IEEE Trans. on Aerospace and Electronic Systems, 1996, 32(4): 1440-1451.

[42]JOHNSTON L A, KRISHNAMURTHY V. Performance Analysis of A Dynamic Programming Track Before Detect Algorithm[J]. IEEE Trans. on Aerospace and Electronic Systems, 2002, 38(1): 228-242.

[43]YI W, KONG L, YANG J,et al. A Tracking Approach Based on Dynamic Programming Track-Before-Detect[C]∥IEEE Radar Conference, 2009.

[44]YI W, MORELANDE R, KONG L, et al. Multi-Target Tracking Via Dynamic-Programming Based Track-Before-Detect[C]∥IEEE Radar Conference, 2012:487-492.

[45]PULFORD G W, La Scala B F. Multihypothesis Viterbi Data Association: Algorithm Development and Assessment[J]. IEEE Trans. on Aerospace and Electronic Systems, 2010, 46(2): 583-609.

[46]MAHLER R. A Unified Foundation for Data Fusion[C]∥SPIE Selected Papers on Sensor and Data Fusion, 1996.

[47]LIN L, BAR-SHALOM Y, Kirubarajan T. Data Association Combined with The Probability Hypothesis Density Filter for Multitarget Tracking[C]∥SPIE Signal and Data Processing of Small Targets, 2004:464-475.

[48]PANTA K, VO B N, SINGH S, et al. Probability Hypothesis Density Filter Versus Multiple Hypothesis Tracking[C]∥SPIE Signal Processing, Sensor Fusion and Target Recognition, 2004: 284-295.

[49]LIN L, BAR-SHALOM Y, KIRUBARAJAN T. Track Labeling and PHD Filter for Multitarget Tracking[J]. IEEE Trans. on Aerospace and Electronic Systems, 2006, 42(3): 778-795.

[50]PANTA K, VO B.N, SINGH S. Novel Data Association Schemes for The Probability Hypothesis Density Filter[J]. IEEE Trans. on Aerospace and Electronic Systems, 2007, 43(2): 556-570.

[51]DUNNE D, RATNASINGHAM T, LANG T, et al. SMC-PHD Based Multi-Target Tracking with Reduced Peak Extraction[C]∥SPIE Signal and Data Processing of Small Targets, 2009.

[52]ERDINC O, WILLETT P, BAR-SHALOM Y. A Physical-Space Approach for The Probability Hypothesis Density and Cardinalized Probability Hypothesis Density Filters[C]∥SPIE Signal and Data Processing of Small Targets, 2006.

[53]ERDINC O, WILLETT P, BAR-SHALOM Y. Probability Hypothesis Density Filter for Multitarget Multisensor Tracking[C]∥IEEE International Conference on Information Fusion, 2005: 25-29.

[54]MAHLER R. PHD Filters of Higher Order in Target Number[J]. IEEE Trans. on Aerospace and Electronic Systems, 2007, 43(4): 1523-1543.

[55]MAHLER R, EAGAN M. Second-Generation PHD/CPHD Filters and Multitarget Calculus[C]∥SPIE Signal and Data Processing of Small Targets, 2009.

[56]VO B T, VO B N, CANTONI A. Performance of PHD Based Multi-Target Filters[C]∥IEEE International Conference on Information Fusion, 2006: 1-8.

[57]VO B N, SINGH S, DOUCET A. Sequential Monte Carlo Methods for Multi-Target Filtering with Random Finite Sets[J]. IEEE Trans. on Aerospace and Electronic Systems, 2005, 41(3): 1224-1244.

[58]VO B N, MA W. The Gaussian Mixture Probability Hypothesis Density Filter[J]. IEEE Trans. on Signal Processing, 2006, 54(11): 4091-4104.

[59]MELZI M, OULDALI A. Joint Multiple Target Tracking Abd Classification Using The Unscented Kalman Particle PHD Filter[C]∥ IEEE International New Circuits and Systems Conference, 2011: 534-537.

[60]PACE M, ZHANG H. Grid Based PHD Filtering by Fast Fourier Transform[C]∥IEEE International Conference on Information Fusion, 2011: 1-8.

[61]楊峰, 王永齊, 梁彥，等. 基于概率假設(shè)濾波方法的多目標(biāo)跟蹤技術(shù)綜述[J]. 自動化學(xué)報, 2013, 39(11): 1944-1956.

YANG Feng,WANG Yong-qi,LIANG Yan,et al.A Survey of PHD Filter Based Multi-target Tracking[J].Acta Automatica Sinica,2013,39(11):1944-1956.

[62]PUNITHAKUMAR K, KIRUBARAJAN T, SINHA A. A Sequential Monte Carlo Probability Hypothesis Density Algorithm for Multitarget Track-Before-Detect[C]∥SPIE Signal and Data Processing of Small Targets, 2005.

Review of Point Target Tracking Methods Based on Infrared Sensor

WANG Shuo1, ZHANG Yi-qun1，2，SUN Bing-yan3

(1.Beijing Inst. of Electronic System Engineering, Beijing 100854, China；2. Beijing Simulation Center,Seience and Technology on Special System Simulation Laboratory，Beijing 100854,China；3.Military Representitive office of the PLA in 23nd Research Institute of the 2nd Research Academy of CASIC,Beijing 100854,China)

Abstract:Common methods are reviewed to detect and track point targets. During the review of conventional tracking methods, such as global nearest neighbor (GNN), probabilistic data association (PDA), joint probabilistic data association (JPDA), multiple-hypothesis tracking (MHT), and dynamic programming algorithm (DPA), the differences and connections are discussed. The probabilistic hypothesis density (PHD) filter for multi-target tracking is also mentioned, and its superiority to other methods in performance is put forward. It is indicated that the improvements of DPA and PHD are possible research areas for further study.

Key words:Infrared point target; detecting; tracking; track-before-detect; Bayesian estimation; multi-target

*收稿日期：2015-05-26；修回日期：2015-05-28

基金項目：有

作者簡介：王碩(1987-)，男，遼寧丹東人。博士生，主要研究方向為目標(biāo)識別與信息融合。

通信地址：100854北京142信箱30分箱E-mail：13718854129@163.com

doi:10.3969/j.issn.1009-086x.2016.02.021

中圖分類號：TN911.73

文獻標(biāo)志碼：A

文章編號：1009-086X(2016)-02-0124-11