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

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

?

探測跟蹤技術

紅外點目標跟蹤方法綜述*

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

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

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

關鍵詞：紅外點目標；檢測；跟蹤；先跟蹤后檢測；貝葉斯估計；多目標

0引言

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

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

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

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

1目標跟蹤方法

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

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

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

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

(1)

(2)

(3)

這樣，式(1)可以化成

(4)

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

(5)

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

(6)

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

(7)

則

(8)

式中：

β=PFA/M，

(9)

1.2全局最近鄰(GNN)算法

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

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

(10)

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

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

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

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

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

(11)

式中：權值wj為

(12)

(13)

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

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

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

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

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

(14)

(15)

(16)

).　(17)

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

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

1.5多假設跟蹤(MHT)算法

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

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

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

(18)

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

圖2　MHT假設示意圖Fig.2　Hypothesis for MHT

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

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

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

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

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

(19)

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

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

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

(20)

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

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

(21)

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

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

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

(22)

(23)

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

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

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

(24)

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

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

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

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

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

(25)

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

DPA算法存在一些不足。

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

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

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

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

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

(26)

若k時刻各目標的測量值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)，建立各目標軌跡的單步關聯(lián)，并以此類推得到t個目標的軌跡。

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

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

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

在此小結一下上述目標跟蹤方法。實際上，它們都基于貝葉斯估計。對單目標情況，先利用Bayes預測和更新方程計算各時刻潛在目標θ(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))為目標的狀態(tài)轉移概率。

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

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

(30)

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

(31)

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

對多目標情況，式(28)，(29)中的單目標后驗密度p(θ(k)|zk)及狀態(tài)轉移概率p(θ(k+1)|θ(k))變?yōu)槎嗄繕撕篁灻芏萷(Θ(k)|zk)及狀態(tài)轉移概率p(Θ(k+1)|Θ(k))。由此，后驗密度的預測和更新方程相應變?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ù)學上，由于后驗密度p(Θ(k)|zk)是高維的，式(32)，(33)很難直接計算。為此，一般假設各目標的狀態(tài)及觀測相獨立，這樣p(Θ(k)|zk)就可近似為各目標i(i=1,…,T)的后驗密度p(θi(k)|zk)的乘積，即

(34)

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

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

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

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

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

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

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

(35)

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

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

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

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

2各算法的分析比較

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

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

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

表3　算法的分析比較

3結束語

本文綜述了紅外點目標的跟蹤算法，介紹了算法之間的聯(lián)系以及各自的特點，并從多個角度對它們加以了分析和對比。目前，多目標跟蹤性能較好的算法對低信噪比目標的跟蹤性能普遍較弱。反之，對低信噪比目標跟蹤性能較好的算法對多目標的跟蹤能力或者偏弱，或者計算量很大以致難以應用。本文綜述的各算法中，DPA和PHD相對其他算法分別在暗目標和多目標跟蹤問題上更具優(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]楊峰, 王永齊, 梁彥，等. 基于概率假設濾波方法的多目標跟蹤技術綜述[J]. 自動化學報, 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-)，男，遼寧丹東人。博士生，主要研究方向為目標識別與信息融合。

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

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

中圖分類號：TN911.73

文獻標志碼：A

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