多目标跟踪数据关联方法综述

第１３卷，第１期　中国传媒大学学报自然科学版　Ｖｏ１．１３，Ｎｏ・１　２００６年３月ＪＯＵＲ．ＮＡＬ　ＯＦ　ＣＯＭＭＵＮＩＣＡＴＩＯＮ　ＵＮＩＶＥＲＳＩＴＹ　ＯＦ　ＣＨＩＮＡ　ＳＣＩＥＮＣＥ　ＡＮＤ　ＴＥＣＨＮｏ　ＧＹ　Ｊ—ａｎ　２００６　

数据关联综述　马杰，田立峰，陈远知　（中国传媒大学数字化工程中心，北京１０００２４）　摘要：数据关联是目前一种新的重要的研究领域。它是多目标跟踪的一个核心问题。本文介绍了数据关联的概　念、目的、以及常用数据关联方法的基本原理及特点。对数据关联领域面临的问题做了介绍和展望。　关键词：多目标跟踪（Ｍ，丌）；贝叶斯定律；神经网络（ＮＮ）；跟踪门　中图分类号：ＴＮ９１１．７文献标识码：Ａ文章编号：１６７３－４７９３（２００６）０１—００９０—３　近三十多年来，人们对数据关联的问题进行了　大量的研究，提出了许多数据关联的方法，其中具有　代表性的方法有：“最近邻”法、“航迹分裂”法、“高　斯和”法、“０—１整数规划”法、“极大似然（ＭＬ）”　法、“多元假设（ＭＨＴ）”法、“概率数据关联（ＰＤＡ）”　法、“联合概率数据关联（ＪＰＤＡ）”法、“神经网络概　率数据关联（ＮＰＤＡ）”法、多特征数据关联法等等。　这些方法主要可分为两大类：　（ａ）贝叶斯估计法：指的是该方法依靠贝叶斯　定律计算概率。由先验概率计算个可能情况下的后　验（条件）概率。　（ｂ）非贝叶斯估计方法：指的是该方法不计算　概率，仅依靠一些简单的规则做出决策；或需要计　算概率，但不依靠贝叶斯定律计算，做出决策。　下面从上述方法中提取几个具有代表性的数据　关联方法，进行详细讲解。　１　“最近邻＂法：　它是最早的一种方法。它最大的特点是简单，　易于工程实现。美国早期的ＴＷＳ雷达（ＡＷＧ一９）　就是使用这种方法。首先，设置跟踪门以限制潜在　的决策数目，由跟踪门初步筛选所得到的回波成为　候选回波。跟踪门是跟踪空间中的一块子空间，中　心位于被跟踪目标的预测状态，其大小应设计的能　保证具有一定的接收正确回波的概率。“最近邻”　法仅选落人跟踪门内与航迹统计最近的点迹。“最　近邻”法中离目标预测状态最近的回波并非一定是　目标回波，特别是当滤波器工作在密集多回波环境　中时，发生误跟、丢失目标的情况会常常发生，这点　也说明“最近邻”法的相关性能不高。　２“０—１整数规划＂法：　这是一种采用批处理的最大似然法。其原理　如下：　当空中存在多个目标，雷达经多次扫描后，获得　一个录取点迹集。从每次扫描得到的点迹中挑选一　个点迹来构成可能的航迹。这样产生的航迹数目会　很大，例如假定Ｋ个目标扫描ｎ次，不加任何限制　会产生　条航迹，因此“０—１整数规划”法提出初　选条件（例如简单的波们取舍）来选出“可能”的航　迹，再在这些航迹集合的基础上，计算每条航迹的似　然函数。在全部航迹的集合中选取满足一定约束条　件的最大似然函数子集，此约束条件是：选出的航迹　子集必须满足；１．每个点迹最多被录取一次；２．子　集合含有的航迹应包容所有点迹。则选出的子集就　是真实的航迹集。　由于选此子集相当于变量只取０或ｌ（表示舍　去和选中），故此得名。“０—１整数规划”法具有航　迹起始能力，但批处理要求计算存储量大，处理后输　出数据有相对较大的时间延迟，抗于扰能力不强，密　集目标环境下计算量会急剧加大的缺点。　

多目标跟踪中ＧＮＮ数据关联算法　

及其跟踪性能评估　

任建芳　刘俊义　

内　容提要　在多目标跟踪的数据处理中，最重要的是观测数据与目标航迹同的数据关　

联问题。将ＧＮＮ（全局域最近邻）数据关联算法与卡尔曼滤波算法结合可以快　

速、成功地处理上百批次目标的跟踪问题。基于Ｍａｔａｌａｂ的仿真程序说明了该　

方法适用于观测噪声较大场景中的多目标跟踪。　

关键词：多目标跟踪；ＧＮＮ数据关联；卡尔曼滤波；数据关联　

１　引　言　

在多目标跟踪的数据处理问题中，每次所接收到的来自不同目标的有效数据可能有　多个，如何判断某个观测数据是来自某一特定目标的，即为数据关联问题。数据能否正　

确关联，其结果将直接影响目标跟踪算法的性能。通常情况下，由于杂波干扰、目标密　

集、目标机动以及来自传感器如雷达扫描时观测噪声等因素的影响，使得成功解决数据　

关联问题变得较为困难。　

近年来，已提出的数据关联算法［Ｉ。　’　有：最近邻（ＮＮ）算法、全局域最近邻（ＧＮＮ）　算法、联合数据关联（Ｊｏｉｎｔ　ｐｒｏｂａｂｉｌｉｔｙ　Ｄａｔａ　Ａｓｓｏｃｉａｔｉｏｎ）算法、多假设跟踪算法（Ｍｕｌｔｉ—　

ｐｉｅ　Ｈｙｐｏｔｈｅｓｉｓ　Ｔｒａｃｋｉｎｇ）等。在杂波干扰环境下跟踪多目标，多假设跟踪算法被公认为　是跟踪效果最好的算法，但是该算法过多依赖于目标和杂波的先验假设，其计算量随被　

跟踪目标的总数增加而呈指数式增长，进而导致计算量严重影响跟踪的效果。　

文献［５］中对真实雷达数据进行了试验。该雷达数据描述了６架飞机按指定的路线　和编队进行飞行的场景。该试验表明ＧＮＮ算法是最好的和最强大的，其性能甚至超过　

联合数据关联算法。另外，ＧＮＮ算法能够同时处理多个（几百批次）目标的跟踪，这一点　

在实际应用中是非常重要的。　

本文主要是介绍ＧＮＮ数据关联算法。并对其跟踪性能进行Ｍａｔａｌａｂ仿真。本文的　第二部分介绍ＧＮＮ算法中数据关联问题的数学描述；第三部分是ＧＮＮ算法跟踪多个　

联合概率数据关联算法

联合概率数据关联算法( Joint probability data association，JPDA)是一种常用于多目标跟踪的算法，其主要思想是根据物体的特征进行跟踪，通过将观测数据与可能的跟踪假设进行比较，选择最优的假设来进行目标跟踪。

联合概率数据关联算法主要分为两个步骤，首先是预测，其次是数据关联。

在预测阶段，算法根据物体的历史数据和运动模型进行预测。这些预测通常以卡尔曼滤波等方式进行，从而得到一个跟踪假设集合，其中包括各个物体的预测位置、速度和方向等信息。

在数据关联阶段，算法将得到的观测数据与跟踪假设进行比对，计算它们之间的匹配程度，并根据匹配程度来更新跟踪假设的置信度。这里的匹配程度一般采用基于概率的方法，如贝叶斯法则等。

在JPDA算法中，广泛采用了概率数据关联（PDA）和扩展数据关联（E-PDA）等改进算法，以提高目标跟踪的准确性和鲁棒性。

需要注意的是，联合概率数据关联算法并不是普适于所有多目标跟踪问题，在一些场景下可能会存在一些局限性，例如在强干扰或高目标密度的环境下，其跟踪性能可能会受到限制。

总之，联合概率数据关联算法是一种常用于多目标跟踪场景的算法，其能够根据物体的特征进行跟踪，从而实现精确、鲁棒的目标跟踪。

第33卷󰀁第4期系统工程与电子技术Vol.33󰀁No.42011年4月SystemsEngineeringandElectronicsApril2011文章编号:1001󰀁506X(2011)04󰀁0734󰀁04

收稿日期:2010󰀁05󰀁02;修回日期:2010󰀁12󰀁09。基金项目:国家自然科学基金(60972159,61032001);航空科学基金(20085184003)资助课题作者简介:谭顺成(1985󰀁),男,博士研究生,主要研究方向为雷达数据处理。E󰀁mail:tanshuncheng@基于PHD滤波和数据关联的多目标跟踪谭顺成1,王国宏1,王󰀁娜1,2,贾舒宜1(1.海军航空工程学院信息融合技术研究所,山东烟台264001;2.中国人民解放军92941部队93分队,辽宁葫芦岛125001)󰀁󰀁摘󰀁要:针对杂波环境下的多目标跟踪,概率假设密度(probabilityhypothesisdensity,PHD)滤波不能提供目标航迹信息的问题,提出一种基于PHD滤波和数据关联的多目标跟踪方法。利用PHD滤波消除杂波并得到各个时刻的目标个数和目标状态估计。将PHD滤波的结果重新定义为量测数据,通过数据关联进一步消除虚警和漏警并给出目标航迹。仿真结果表明,该算法可以在有效地提高杂波环境下多目标跟踪精度的同时提供各目标航迹信息。关键词:概率假设密度;数据关联;多目标跟踪;随机有限集;最近邻域标准滤波器中图分类号:TN953.6󰀁󰀁󰀁󰀁文献标志码:A󰀁󰀁󰀁󰀁DOI:10.3969/j.issn.1001󰀁506X.2011.04.04Multi󰀁targettrackingbasedonPHDfilteranddataassociationTANShun󰀁cheng1,WANGGuo󰀁hong1,WANGNa1,2,JIAShu󰀁yi1(1.InstituteofInformationFusionTechnology,NavalAeronauticalandAstronauticalUniversity,Yantai264001,China;2.93Element,Unit92941ofthePLA,Huludao125001,China)󰀁󰀁Abstract:Formulti󰀁targettrackinginclutter,theprobabilityhypothesisdensity(PHD)filtercannotpro󰀁videthetrackinformationofeachtarget,thus,anovelmethodbasedonPHDfilteranddataassociationispro󰀁posed.Firstly,thePHDfilterisutilizedtoremovethecluttersandgettheestimatedtargetnumberandstatesateachtimestep.Then,theresultsofPHDfilterareredefinedasthemeasurements,whicharemanagedbydataassociationsothatthefalsealarmsandmissdetectionsarefurthereliminatedandthetracksoftargetsareprovided.Simulationresultsdemonstratethattheproposedmethodcanimprovetheaccuracyofmulti󰀁targettrackingeffectivelyaswellasprovidetrackinformationofeachtarget.Keywords:probabilityhypothesisdensity(PHD);dataassociation;multi󰀁targettracking;randomfiniteset(RFS);nearestneighborstandardfilter(NNSF)0󰀁引󰀁言󰀁󰀁噪声、杂波以及数据关联和检测等的不确定性使得杂波环境下的多目标跟踪尤其困难。一方面,目标的出现及消失具有随机性,监测区域内的目标个数是变化且未知的;另一方面,传感器得到的量测有可能来源于目标,也有可能来源于杂波,所以量测个数也是时变的。因此,对多目标跟踪往往需要从个数时变的量测中估计出目标个数不确定的各目标状态,这就要求算法能够在各个时刻联合估计目标的个数和各目标的状态。传统的多目标跟踪算法主要有联合概率数据互联[1󰀁2](jointprobabilisticdataassociation,JPDA)和多假设跟踪[3󰀁4](multiplehypothesistrack,MHT)等。JPDA通过对每一条航迹波门内的所有量测进行加权求和得到一个等效量测来更新该航迹,以解决数据互联的不确定性,而MHT则通过对所有可能的互联假设进行递推,并利用新量测减小数据互联的不确定性。但是,JPDA仅能处理目标个数固定的情况,而对于MHT,其可能的互联假设个数随时间的递推成指数增长,其计算量也随之急剧增长。因此,这两种算法均受到实际应用的限制。Mahler提出的随机有限集(randomfiniteset,RFS)理论提供了一种最优的Bayes多目标滤波方法[5]。但是,即使是在目标数目中等情况,基于RFS的最优Bayes多目标滤波也要解决大量高维积分的组合问题,其计算非常复杂[6󰀁7]。为了避免这个问题,Mahler又提出了概率假设密度(probabilityhypothesisdensity,PHD)滤波的思想。PHD滤波仅对多目标RFS后验密度的第一阶矩进行递推,从而极大的减小了计算复杂度。然而,PHD滤波方程的递推要求对高维积分进行求解,而这些积分通常没有闭合解。序惯蒙特卡罗(sequentialMonteCarlo,SMC)提供了一种近似求解高维积分的方法,文献[6󰀁8]等将其应用到PHD滤波当中,提出了一种基于SMC󰀁PHD(或粒子PHD)滤波,真正意义上实󰀁第4期谭顺成等:基于PHD滤波和数据关联的多目标跟踪󰀁735󰀁󰀂󰀁现了PHD滤波的工程应用。文献[9]对粒子PHD滤波的收敛性进行了证明。由于具备粒子滤波的优点,基于粒子的PHD滤波能够较好的适应强非线性非高斯系统[10]。PHD滤波可以有效消除杂波并给出目标的个数和状态估计,但由于避免了数据关联问题,PHD滤波并不能提供各目标的航迹信息。另外,PHD滤波不可能在任何时刻都完全准确的估计出监测区域内的目标个数,即存在一定的虚警或漏警。文献[6]研究了基于聚类索引的粒子PHD滤波算法,但该算法并不能消除PHD滤波的虚警或漏警,也不能进一步提高目标跟踪精度。文献[11󰀁12]研究了在PHD滤波的同时结合MHT进行数据关联的算法,但由于引进了MHT,其算法的复杂度和计算量大大增加。本文针对以上情况,提出一种基于PHD滤波和数据关联的多目标跟踪算法。其基本思想是:先利用PHD滤波消除杂波,得到各目标的状态估计,再将PHD滤波得到的结果当作新的量测值进行多目标数据关联,以消除PHD滤波估计目标个数和目标状态不准确的问题,并给出各目标的航迹信息。仿真结果表明了该算法的有效性。1󰀁RFS框架下的多目标跟踪1.1󰀁多目标跟踪的RFS模型让Es和Eo分别表示状态空间和观测空间,定义两个随机集的随机过程X={Xk|k󰀁N}和Z={Zk|k󰀁N+},其中,过程X和过程Z分别称为状态过程和量测过程,Xk={xk,1,󰀁,xk,Mk}󰀁Es和Zk={zk,1,󰀁,zk,Nk}󰀁Eo分别表示k时刻的多目标状态RFS和多目标量测RFS,而xk,i(i=1,󰀁,Mk)和zk,j(j=1,󰀁,Nk)分别表示单目标状态和单目标量测或杂波,Mk和Nk分别为k时刻的目标个数和量测个数。给定k-1时刻的多目标状态RFSXk-1,将任意xk-1󰀁Xk-1在k时刻的状态建模为RFSSk|k-1(xk-1),当目标持续存在时其取值为{xk},目标消失时为󰀁。则k时刻的多目标状态RFSXk由持续存在目标、衍生目标以及新生目标联合给出,即Xk=󰀁xk-1󰀁Xk-1Sk|k-1(xk-1)󰀁󰀁xk-1󰀁Xk-1Bk|k-1(xk-1)󰀁󰀁k(1)式中,Bk|k-1(xk-1)为从xk-1󰀁Xk-1衍生新目标的RFS;󰀁k为新目标出现的RFS。任意xk󰀁Xk产生一个RFS󰀁k(xk),当目标被检测到其取值为{zk},目标未被检测到时为󰀁,则多目标量测RFSZk=Kk󰀁󰀁xk󰀁Xk󰀁k(xk)(2)式中,Kk表示虚警或杂波的RFS。多目标跟踪滤波的问题就是利用观测集Z1:k={Z1,󰀁,Zk}对不可观测集X0:k={X0,󰀁,Xk}进行估计,得到X^k={x^k,1,󰀁,x^k,N^k},其中N^k表示k时刻估计的目标个数。1.2󰀁PHD滤波定义在󰀁上的RFSX,其第一阶矩(或称之为PHD和密度函数)是󰀁上的一个非负函数v,满足对任意闭子集S󰀁󰀁有E[|X󰀁S|]=󰀁Sv(x)dx(3)式中,|X|表示集X中元素的个数。根据定义,多目标后验概率密度分布的第一阶矩实际上就是其PHD。给定单目标状态向量x和直到k时刻所有量测的集合Z1:k,PHD滤波的预测和更新方程分别如式(4)和式(5)所示[5]vk|k-1(x|Z1:k-1)=󰀁k(x)+󰀁󰀁k|k-1(x|xk-1)󰀁vk-1|k-1(xk-1|Z1:k-1)dxk-1(4)vk|k(x|Z1:k)=v(x)+󰀁z󰀁Zkk,z(x)󰀁k(z)+Dk|k-1,k,z󰀁vk|k-1(x|Z1:k)(5)式中,v(x)=1-PD(x);󰀁k(z)=󰀁kck(z);󰀁k|k-1(x|xk-1)=ek|k-1(xk-1)󰀁fk|k-1(x|xk-1)+bk|k-1(x|xk-1);k,z(x)=PD(x)gk(z|x)。在PHD滤波的预测和更新方程中,󰀁k(󰀁)和bk|k-1(󰀁|xk-1)分别表示k时刻RFS󰀁k和Bk|k-1(xk-1)的PHD;ek|k-1(xk-1)表示k-1时刻状态为xk-1的目标持续存在到k时刻的概率;PD(x)为k时刻状态为x的目标被检测到的概率;fk|k-1(󰀁|󰀁)和gk(󰀁|󰀁)分别为单目标的状态转移函数和量测似然函数;󰀁k为杂波个数服从泊松分布的期望值;而ck(󰀁)为杂波点在整个观测空间上的概率密度分布;符号󰀁,󰀁为内积,定义为vk|k,󰀁=󰀁vk|k(x|Z1:k)󰀁(x)dx(6)2󰀁数据关联算法描述数据关联算法有NNSF、JPDA、最优Bayes算法以及多假设法等[13]。由于PHD滤波可以有效的滤除杂波并得到粗略的目标个数和目标状态估计,因此本文采用算法复杂度较低NNSF进行数据关联。NNSF是一种利用先验统计特性估计相关性能的滤波器。设k-1时刻的目标航迹数为Tr(k-1),其原理是先设置跟踪门,如果目标量测yi(k)(i=1,󰀁,N^k)满足[yi(k)-y^j(k|k-1)]TS-1j(k)󰀁[yi(k)-y^j(k|k-1)]󰀁󰀁(7)则认为该量测落入航迹j(j=1,󰀁,Tr(k-1))的跟踪门内,成为该航迹的候选回波。若落入跟踪门内的测量只有1个,则该测量可被直接用于该航迹的更新;但当有两个或两个以上的量测落在该航迹的跟踪门内时,取统计距离最小的候选回波,也就是使新息加权范数d2(y)=[y-y^j(k|k-1)]TS-1j(k)󰀁[y-y^j(k|k-1)](8)达到极小的量测用于该航迹的更新。3󰀁基于粒子PHD滤波和数据关联的算法实现󰀁󰀁以Rk={󰀁iki,k|i=1,󰀁,Tr(k)}表示k时刻所有目标的航迹集,其中,󰀁iki,k表示第i条航迹;ki为该航迹的起始时刻。给定k-1时刻的航迹集Rk-1和粒子集{xik-1,wik-1}Lk-1i=1,基于粒子PHD滤波和数据关联算法的步骤如下:步骤1󰀁预测:根据建议分布qk(󰀁|xik-1,Zk)和pk(󰀁|Zk)进行粒子采样xik|k-1~qk(󰀁|xik-1,Zk),i=1,󰀁,Lk-1pk(󰀁|Zk),i=Lk-1+1,󰀁,Lk-1+Jk(9)