数据关联算法综述

魏 祥，李 颖，骆荣剑

（重庆通信学院，重庆 400035）

数据关联算法综述

魏 祥，李 颖，骆荣剑

（重庆通信学院，重庆 400035）

数据关联是多目标跟踪里面的核心问题，文章系统地介绍了几种基本数据关联算法，通过总结国内外的文献，分析指出了传统数据关联算法的一些问题。

多目标跟踪；数据关联；算法

多目标跟踪由多个部分构成，分别为点迹预处理、航迹起始和终结、数据关联、波门、跟踪等方面。简单地说，数据关联就是将多个雷达量测得到的数据进行正确分类，打个比方，在某一时刻，N个雷达在对N个感兴趣的目标进行观测，得到了N个量测数据，数据关联要完成的事情就是将量测数据1，2，3...N正确的分配给相对应的目标1，2，3…N，如果数据关联不正确，将目标1的量测数据1（如速度）配给了目标2，那么后续的跟踪结果可以预想，将是不可信的。上面这个例子还没有考虑到噪声、虚假目标等的影响，所以实际应用环境中的数据关联问题更为复杂，因此若接收的数据不进行正确的数据关联，后续工作也就变得毫无意义，故而在多目标跟踪里，数据关联一直是十分重要的一个部分。

1　数据关联算法

由于战场环境的日益复杂，如各种电子干扰及自然环境等因素影响，量测有可能是敌目标的正确测量值，但也有可能是来自于噪声、虚假目标、杂波等的错误测量值。数据关联，有时也被称作点迹相关，它是雷达数据处理的关键问题之一，如果数据关联不正确，那么错误的数据关联就会给目标配上一个错误的速度，对于空中交通管制雷达来说，错误的目标速度可能会导致飞机碰撞；对于军用雷达来说，可能会导致错过目标拦截。数据关联是通过建立某时刻雷达量测数据和其他时刻量测数据的关系，来确定量测数据是否来自同一个目标的处理过程［1］。

就多目标跟踪的基本方法而言，概括来讲可分为以下2类：极大似然类数据关联算法和Bayes数据关联算法。

1.1极大似然类数据关联算法

极大似然类数据关联算法的基础是观测数据的似然比，这类算法中比较常见有航迹分岔法［3］、联合大似然算法［3］、0-1整数规划法［1］、广义相关法［1］等。

航迹分叉法最早是在20世纪60年代被提出的，之后Smith和Buechler对其进行进一步研究，其基本原理是假设航迹已起始，此时把目标波门内全部的回波都作为目标回波，原有的目标航迹则以不同的目标回波为基础，分裂为同等数目的新目标航迹，然后通过计算每条航迹的似然函数，设置一个门限进行甄别。联合极大似然算法实质上是对航迹分叉法的一个推广，航迹分叉法的使用条件为单目标或者波门无相交区域的多目标环境，当不同目标的波门相交而且相交区域内有回波时，该公共回波属于哪个目标是不确定的，此时就需要借助联合极大似然算法。联合极大似然算法充分考虑了所有量测的可行组合与划分，计算所有可行划分对应的联合似然函数，取使联合似然函数最大的可行划分为有效划分，进而完成多目标的数据关联。1974年，Morefield在论文中将多目标跟踪问题看作0-1整数规划问题中集合的分解和组合问题，提出了适于多目标跟踪的0-1整数规划法。1975年Steinhe和Blackman提出了广义相关法，给出了计算量测数据和航迹最优关联和交接（称为广义相关）的一般表达式，基本思想是定义了一个得分函数，通过得分函数可完成对航迹起始、确认和撤销的操作。

1.2Bayes类数据关联算法

Bayes类数据关联算法的基础是贝叶斯准则，主要包括最近邻域（Nearest Neighbor，NN）算法［1，4］、概率数据关联（Probabilistic Data Association，PDA ） 算法［1，4］、联合概率数据关联算法（Joint Probabilistic Data Association，JPDA ）［1，4］、和多假设法［1，4］等。按照确认量测集合的不同，Bayes类算法又可以分为两大类：第一类只对最新的确认量测集合进行研究，是一种次优的Bayes算法，前3种算法即为此类；第二类是包括对当前时刻之前所有的确认量测集合进行研究，是一种最优的Bayes算法，最后一种属于此类算法。

Singer等人在20世纪70年代初提出了NN算法，1973年，Singer和Sea在此基础上提出了最近邻域标准滤波器（NNSF）［5］。NNSF的基本思想：先设置相关波门，通过相关波门的设置，尽可能达到真实量测以一个较高的接收概率落入相关波门内，并且里面干扰因素（如其它目标的量测等）尽可能少。在相关波门里的若干候选回波中，从里面选取离被跟踪目标的预测位置最近的回波作为目标回波，进而用于目标状态更新。NN算法结构简单，实现起来比较容易，但是当被跟踪目标附近有其他目标时，得到的目标回波可能并不是属于真正被跟踪的目标，这也是NN算法不够完善的一个方面。

PDA算法［6］认为所有落入相关波门内的回波都有可能源于目标，只是每个有效回波源于目标的概率不同，应首先根据不同情况计算出各回波来自目标的概率，然后利用这些概率值对相关波门内的不同回波进行加权，将各个候选回波的加权和作为等效回波，并利用等效回波对目标的状态进行更新。

PDA算法是一种次优滤波方法，它只对最新的量测进行分解，由于其推导是在假设关联区域内仅存在一个目标的假设下进行的，因而主要用于解决杂波环境下的单雷达单目标跟踪问题，在杂波密集的多目标环境下，容易出现丢失目标或跟错目标的问题。

JPDA算法［7］是在仅适用于单目标跟踪的PDA算法的基础上提出来的，该方法是杂波环境下对多目标进行数据互联的一种良好的算法。然而，JPDA的困难在于难以确定得到联合事件与关联事件的概率，因为在这种方法中联合事件数是所有候选波门数的指数函数， 并且随回波密度的增加出现计算上的组合爆炸现象。

西北工业大学潘泉教授在文献［8］中提出了一种广义概率数据关联算法（GPDA），新算法利用了更多的关联事件信息，使新算法的性能得到了改善，其计算量随目标数增加仅成线性变化，具有很好的实时性能，并且在一一对应、一多对应和多多对应这些典型的仿真环境下，详细和全面地对新算法进行了分析比较，结果表明，GPDA算法的性能全面优于JPDA算法。

多假设算法［9］（MHT）是基于全邻最优滤波器和JPDA中聚概念的一种算法， 该方法考虑每个新接收到的量测可能来自新目标、虚警或已有目标，它通过一个有限长度的时间滑窗，建立多个候选假设，并通过假设评估、假设管理技术实现多目标跟踪。近年来，MHT的研究热点主要是假设管理技术的有效实现。

2　结语

众所周知，点迹-航迹数据互联问题是雷达及其组网跟踪系统的基本与核心问题，特别是当有交叉目标、机动目标、密集多目标等情况时，数据互联的难度增加。然而，在多目标数据关联技术的进步的情况下，前面提到的极大似然类数据关联算法未得到更进一步的发展和改进。贝叶斯类的数据关联算法，相对于极大似然类算法等批处理算法来说，在工程应用中更为普遍，目前基于该类数据关联算法的研究工作也更为深入。

［1］何友，修建娟.雷达数据处理及应用［M］.北京：电子工业出版社，2009.

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

［3］张兰秀，赵连芳译.跟踪和数据互联［M］.连云港：中船总七一六所，1991.

［4］李弼程，黄洁.信息融合技术及其应用［M］.北京：国防工业出版社，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，FORMANN 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］潘泉，叶西宁，张洪才.广义概率数据关联算法［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-），男，湖北监利，硕士研究生；研究方向：数据关联。