魏 祥，李 穎，駱榮劍

（重慶通信學院，重慶 400035）

數(shù)據(jù)關(guān)聯(lián)算法綜述

魏 祥，李 穎，駱榮劍

（重慶通信學院，重慶 400035）

數(shù)據(jù)關(guān)聯(lián)是多目標跟蹤里面的核心問題，文章系統(tǒng)地介紹了幾種基本數(shù)據(jù)關(guān)聯(lián)算法，通過總結(jié)國內(nèi)外的文獻，分析指出了傳統(tǒng)數(shù)據(jù)關(guān)聯(lián)算法的一些問題。

多目標跟蹤；數(shù)據(jù)關(guān)聯(lián)；算法

多目標跟蹤由多個部分構(gòu)成，分別為點跡預處理、航跡起始和終結(jié)、數(shù)據(jù)關(guān)聯(lián)、波門、跟蹤等方面。簡單地說，數(shù)據(jù)關(guān)聯(lián)就是將多個雷達量測得到的數(shù)據(jù)進行正確分類，打個比方，在某一時刻，N個雷達在對N個感興趣的目標進行觀測，得到了N個量測數(shù)據(jù)，數(shù)據(jù)關(guān)聯(lián)要完成的事情就是將量測數(shù)據(jù)1，2，3...N正確的分配給相對應(yīng)的目標1，2，3…N，如果數(shù)據(jù)關(guān)聯(lián)不正確，將目標1的量測數(shù)據(jù)1（如速度）配給了目標2，那么后續(xù)的跟蹤結(jié)果可以預想，將是不可信的。上面這個例子還沒有考慮到噪聲、虛假目標等的影響，所以實際應(yīng)用環(huán)境中的數(shù)據(jù)關(guān)聯(lián)問題更為復雜，因此若接收的數(shù)據(jù)不進行正確的數(shù)據(jù)關(guān)聯(lián)，后續(xù)工作也就變得毫無意義，故而在多目標跟蹤里，數(shù)據(jù)關(guān)聯(lián)一直是十分重要的一個部分。

1　數(shù)據(jù)關(guān)聯(lián)算法

由于戰(zhàn)場環(huán)境的日益復雜，如各種電子干擾及自然環(huán)境等因素影響，量測有可能是敵目標的正確測量值，但也有可能是來自于噪聲、虛假目標、雜波等的錯誤測量值。數(shù)據(jù)關(guān)聯(lián)，有時也被稱作點跡相關(guān)，它是雷達數(shù)據(jù)處理的關(guān)鍵問題之一，如果數(shù)據(jù)關(guān)聯(lián)不正確，那么錯誤的數(shù)據(jù)關(guān)聯(lián)就會給目標配上一個錯誤的速度，對于空中交通管制雷達來說，錯誤的目標速度可能會導致飛機碰撞；對于軍用雷達來說，可能會導致錯過目標攔截。數(shù)據(jù)關(guān)聯(lián)是通過建立某時刻雷達量測數(shù)據(jù)和其他時刻量測數(shù)據(jù)的關(guān)系，來確定量測數(shù)據(jù)是否來自同一個目標的處理過程［1］。

就多目標跟蹤的基本方法而言，概括來講可分為以下2類：極大似然類數(shù)據(jù)關(guān)聯(lián)算法和Bayes數(shù)據(jù)關(guān)聯(lián)算法。

1.1極大似然類數(shù)據(jù)關(guān)聯(lián)算法

極大似然類數(shù)據(jù)關(guān)聯(lián)算法的基礎(chǔ)是觀測數(shù)據(jù)的似然比，這類算法中比較常見有航跡分岔法［3］、聯(lián)合大似然算法［3］、0-1整數(shù)規(guī)劃法［1］、廣義相關(guān)法［1］等。

航跡分叉法最早是在20世紀60年代被提出的，之后Smith和Buechler對其進行進一步研究，其基本原理是假設(shè)航跡已起始，此時把目標波門內(nèi)全部的回波都作為目標回波，原有的目標航跡則以不同的目標回波為基礎(chǔ)，分裂為同等數(shù)目的新目標航跡，然后通過計算每條航跡的似然函數(shù)，設(shè)置一個門限進行甄別。聯(lián)合極大似然算法實質(zhì)上是對航跡分叉法的一個推廣，航跡分叉法的使用條件為單目標或者波門無相交區(qū)域的多目標環(huán)境，當不同目標的波門相交而且相交區(qū)域內(nèi)有回波時，該公共回波屬于哪個目標是不確定的，此時就需要借助聯(lián)合極大似然算法。聯(lián)合極大似然算法充分考慮了所有量測的可行組合與劃分，計算所有可行劃分對應(yīng)的聯(lián)合似然函數(shù)，取使聯(lián)合似然函數(shù)最大的可行劃分為有效劃分，進而完成多目標的數(shù)據(jù)關(guān)聯(lián)。1974年，Morefield在論文中將多目標跟蹤問題看作0-1整數(shù)規(guī)劃問題中集合的分解和組合問題，提出了適于多目標跟蹤的0-1整數(shù)規(guī)劃法。1975年Steinhe和Blackman提出了廣義相關(guān)法，給出了計算量測數(shù)據(jù)和航跡最優(yōu)關(guān)聯(lián)和交接（稱為廣義相關(guān)）的一般表達式，基本思想是定義了一個得分函數(shù)，通過得分函數(shù)可完成對航跡起始、確認和撤銷的操作。

1.2Bayes類數(shù)據(jù)關(guān)聯(lián)算法

Bayes類數(shù)據(jù)關(guān)聯(lián)算法的基礎(chǔ)是貝葉斯準則，主要包括最近鄰域（Nearest Neighbor，NN）算法［1，4］、概率數(shù)據(jù)關(guān)聯(lián)（Probabilistic Data Association，PDA ） 算法［1，4］、聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)算法（Joint Probabilistic Data Association，JPDA ）［1，4］、和多假設(shè)法［1，4］等。按照確認量測集合的不同，Bayes類算法又可以分為兩大類：第一類只對最新的確認量測集合進行研究，是一種次優(yōu)的Bayes算法，前3種算法即為此類；第二類是包括對當前時刻之前所有的確認量測集合進行研究，是一種最優(yōu)的Bayes算法，最后一種屬于此類算法。

Singer等人在20世紀70年代初提出了NN算法，1973年，Singer和Sea在此基礎(chǔ)上提出了最近鄰域標準濾波器（NNSF）［5］。NNSF的基本思想：先設(shè)置相關(guān)波門，通過相關(guān)波門的設(shè)置，盡可能達到真實量測以一個較高的接收概率落入相關(guān)波門內(nèi)，并且里面干擾因素（如其它目標的量測等）盡可能少。在相關(guān)波門里的若干候選回波中，從里面選取離被跟蹤目標的預測位置最近的回波作為目標回波，進而用于目標狀態(tài)更新。NN算法結(jié)構(gòu)簡單，實現(xiàn)起來比較容易，但是當被跟蹤目標附近有其他目標時，得到的目標回波可能并不是屬于真正被跟蹤的目標，這也是NN算法不夠完善的一個方面。

PDA算法［6］認為所有落入相關(guān)波門內(nèi)的回波都有可能源于目標，只是每個有效回波源于目標的概率不同，應(yīng)首先根據(jù)不同情況計算出各回波來自目標的概率，然后利用這些概率值對相關(guān)波門內(nèi)的不同回波進行加權(quán)，將各個候選回波的加權(quán)和作為等效回波，并利用等效回波對目標的狀態(tài)進行更新。

PDA算法是一種次優(yōu)濾波方法，它只對最新的量測進行分解，由于其推導是在假設(shè)關(guān)聯(lián)區(qū)域內(nèi)僅存在一個目標的假設(shè)下進行的，因而主要用于解決雜波環(huán)境下的單雷達單目標跟蹤問題，在雜波密集的多目標環(huán)境下，容易出現(xiàn)丟失目標或跟錯目標的問題。

JPDA算法［7］是在僅適用于單目標跟蹤的PDA算法的基礎(chǔ)上提出來的，該方法是雜波環(huán)境下對多目標進行數(shù)據(jù)互聯(lián)的一種良好的算法。然而，JPDA的困難在于難以確定得到聯(lián)合事件與關(guān)聯(lián)事件的概率，因為在這種方法中聯(lián)合事件數(shù)是所有候選波門數(shù)的指數(shù)函數(shù)， 并且隨回波密度的增加出現(xiàn)計算上的組合爆炸現(xiàn)象。

西北工業(yè)大學潘泉教授在文獻［8］中提出了一種廣義概率數(shù)據(jù)關(guān)聯(lián)算法（GPDA），新算法利用了更多的關(guān)聯(lián)事件信息，使新算法的性能得到了改善，其計算量隨目標數(shù)增加僅成線性變化，具有很好的實時性能，并且在一一對應(yīng)、一多對應(yīng)和多多對應(yīng)這些典型的仿真環(huán)境下，詳細和全面地對新算法進行了分析比較，結(jié)果表明，GPDA算法的性能全面優(yōu)于JPDA算法。

多假設(shè)算法［9］（MHT）是基于全鄰最優(yōu)濾波器和JPDA中聚概念的一種算法， 該方法考慮每個新接收到的量測可能來自新目標、虛警或已有目標，它通過一個有限長度的時間滑窗，建立多個候選假設(shè)，并通過假設(shè)評估、假設(shè)管理技術(shù)實現(xiàn)多目標跟蹤。近年來，MHT的研究熱點主要是假設(shè)管理技術(shù)的有效實現(xiàn)。

2　結(jié)語

眾所周知，點跡-航跡數(shù)據(jù)互聯(lián)問題是雷達及其組網(wǎng)跟蹤系統(tǒng)的基本與核心問題，特別是當有交叉目標、機動目標、密集多目標等情況時，數(shù)據(jù)互聯(lián)的難度增加。然而，在多目標數(shù)據(jù)關(guān)聯(lián)技術(shù)的進步的情況下，前面提到的極大似然類數(shù)據(jù)關(guān)聯(lián)算法未得到更進一步的發(fā)展和改進。貝葉斯類的數(shù)據(jù)關(guān)聯(lián)算法，相對于極大似然類算法等批處理算法來說，在工程應(yīng)用中更為普遍，目前基于該類數(shù)據(jù)關(guān)聯(lián)算法的研究工作也更為深入。

［1］何友，修建娟.雷達數(shù)據(jù)處理及應(yīng)用［M］.北京：電子工業(yè)出版社，2009.

［2］FARINA A，STUDER F A.Radar Data Processing［M］.London：Research Studies Press LTD，1985.

［3］張?zhí)m秀，趙連芳譯.跟蹤和數(shù)據(jù)互聯(lián)［M］.連云港：中船總七一六所，1991.

［4］李弼程，黃潔.信息融合技術(shù)及其應(yīng)用［M］.北京：國防工業(yè)出版社，2010.

［5］SINGER R A，SEA R G.New results in optimizing surveillance system tracking and data correlation performance in dense multitarget environments［J］.Automatic Control Transactions，1973（6）：571-582.

［6］BAR-SHALOM Y，JAFFER A G.Adaptive Nonlinear Filtering for Tracking with Measurements of Uncertain Origin［J］. Conference on Decision and Control，1972（11）：243-247.

［7］BAR-SHALOM Y，F(xiàn)ORMANN T E，SCHEFFE M.Joint Probabilistic Data Association for Multiple Targets in Clutter［J］.Proc. Conf.Information Sciences and Systems，1980（1）：173-184.

［8］潘泉，葉西寧，張洪才.廣義概率數(shù)據(jù)關(guān)聯(lián)算法［J］.電子學報，2005（3）：467-472.

［9］REID D B.An Algorithm for Tracking Multiple Targets［J］.Transactions on Automatic Control，1979（6）：843-854.

Summary of Data Association Algorithms

Wei Xiang， Li Ying， Luo Rongjian
（Chongqing Institute of Communications， Chongqing 400035，China）

Data association is the core problem of multi target tracking.Several basic data association algorithms are introduced in this paper， by summarizing the literatures at home and abroad，then points out some problems of data association algorithm.

multi target tracking； data association； algorithm

魏祥（1990-），男，湖北監(jiān)利，碩士研究生；研究方向：數(shù)據(jù)關(guān)聯(lián)。