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

多目标跟踪数据关联方法综述摘要：多目标跟踪问题在军事和民用方面都有着十分广泛的应用,如在军事方面的空中预警、空中攻击(多目标攻击)等,民用方面包括空中交通管制等。多目标跟踪在军事上的应用受到了各国广泛重视。本文对目前国内外部分文献上发表的有关多目标跟踪方法进行了综述。并对各种方法的优缺点进行了比较。关键字：多目标跟踪数据关联方法综述1概述多目标跟踪（MTT)是当前计算机视觉领域的一个研究热点。多目标跟踪是指利用计算机，在频序列中确定感兴趣的、具有某种显著视觉特征的各个独立运动目标的位置，大小和各个目标完整的运动轨迹。视频目标跟踪问题之所以引起广泛关注是由于它能够应用于民用和军事等许多领域。例如基于视频目标跟踪的视频监视系统常用于民宅、停车场、公共场合、银行等的监视，以防止偷盗、破坏行为的发生，保障社会的安全。在交通系统中，多目标跟踪研究也具有非常广泛的应用，主要包括交通流量控制、车辆异常行为监测等很多方面。在军事领域对视频监视系统的要求比民用领域要高得多，这主要是由于战场环境远比普通民用环境更加复杂和苛刻。恶劣的战场环境要求视频监视系统具有很强的适应性并能够对快速变化的运动目标实施稳定靠的跟踪。图1.1是一个典型多目标跟踪系统，包括视频采集处理、运动目标检测、多目标跟踪、目标行为分析等主要模块。运动目标检测与多目标跟踪模块处于整个视频跟踪系统的核心模块，是各种后续高级处理的基础。运动目标检测是指从视频中实时提取目标，而运动目标跟踪是通过建立目标关联实现多目标的持续跟踪，并确定多目标运动轨迹。视频采集设备为多目标跟踪系统提供输入视频流，视频监控窗口实时输出多目标跟踪结果，监控场景。目标行为分析理解属于高层次的视觉问题。2几种经典的数据关联算法多目标跟踪实现的关键问题在于如何进行有效的数据关联。而数据关联的目的就是把来源于单个或多个传感器的量测数据Zi(i=1,2,...,N)与j个已知或已经确定的航迹进行相互配对的过程,简单来说，就是使所有的量测数据分为j个集合，并且保证每个集合中所包含的量测数据以接近于1的概率都来自同一个目标。目标跟踪系统中数据关联是必不可少的关键步骤，原因在于传感器所获得的量测数据不确定性以及多目标跟踪环境的复杂性。实际中的传感器系统总是不可避免的存在着测量的误差，以及缺乏跟踪环境的先验知识，目标的个数往往是不能先验知道的，量测数据是来自真实目标还是由来自虚假目标这些也都是不能先验知道的。上述众多的不确定因素使得量测数据与真实目标之间的对应配对关系很难确定，是导致数据关联是多目标跟踪系统中最关键的一步的原因。概括来说，数据关联算法的分类有多种：分为贝叶斯框架和非贝叶斯框架；单帧数据关联和多帧数据关联；量测与航迹的关联和量测与量测的关联等等。其中第三种分类中的量测与航迹的关联，主要的目的是确定量测是否成为新航迹的起始，或者是否为已有航迹的最新一帧的量测，或者为虚假量测；量测与量测的关联主要是解决多源数据的不确定性，这种数据关联算法主要是应用于被动多传感器的目标跟踪系统中。图2.1给出了多目标跟踪的基本原理。多目标跟踪主要包含以下几个基本要素：跟踪起始与终结、跟踪门的形成、数据关联、跟踪维持等。多目标跟踪的关键在于如何有效地进行数据关联。数据关联大致可分为三个步骤：（1）将传感器得到的量测数据进行门限限制，充分利用先验知识粗略过滤那些门限以外的量测，主要包括其他目标形成的真实的量测数据、虚假目标的量测数据，减少一些不可能的量测与航迹的配对关系，得到可行的量测—航迹配对；（2）形成关联矩阵，用以衡量每个点迹与相应航迹匹配的程度；（3）把最有可能的点迹按照赋值策略分别赋予相应的航迹。2.1最近邻域法（NN）至今为止，许多数据关联算法都已经可以实现较好的关联，其中最近邻数据关联(NearNeighborDataAssociation)算法是提出最早，也是最简单的一种方法，但是在一定情况下却是最有效的。它是在1971年由Singer等人提出来的。这种方法首先设置关联门以限制潜在的决策数目，由关联门初步筛选所得到的回波成为候选回波。关联门是跟踪空间中的一块子空间，中心位于被跟踪目标的预测状态，其大小的设计应保证在一定概率程度上能够接收到正确回波。最近邻法所选择的一般是落入关联门内并且离被跟踪目标预测位置最近的点迹,通常根据统计距离进行判定。统计距离的定义：假设在第k次扫描之前，已经建立了N条航迹。第k次新观测为Zj(k)，j=1,2,…,N。在第i条航迹的关联门内，观测j和航迹i的差矢量定义为测量值和预测值之间的差，即滤波器残差，其中H为观测矩阵，设S(k)是eij(k)的协方差矩阵。则统计距离(平方)为它就是判断最近邻点的度量标准。最近邻数据关联算法的优点是运算量小，易于硬件的实现，但是只能适用于稀疏目标和杂波环境的目标跟踪系统。当在目标或者杂波密度较大时，很容易出现误跟和漏跟现象，同时算法跟踪性能不高。2.2概率数据关联（PDA）概率数据关联(ProbabilityDataAssociation)是由Bar-Shalom和Jaffer于1972年提出的。由于通过关联门过滤后，可能还有很多回波，即有效回波。概率数据关联认为，只要是有效回波，就都有可能是源于目标，只是每个回波源于目标的概率有所不同。PDA方法利用了跟踪门内的所有回波以获得可能的后验信息，并根据大量的相关计算得出各概率加权系数及其加权和，然后更新目标状态。在第1次到第k次扫描所获得的全部有效回波已知的情况下，第k次扫描时，第i个回波(i=1,2,3,…,mk)均为正确回波的概率，称之为正确关联概率，用Pi(k)来表示，式中：θi(k)为第k次扫描第i个回波为正确回波的事件；Zk为第1次到第k次扫描所获得的全部有效回波的集合；mk为第k次测量所获得的回波数目。根据全概率公式，目标在k时刻的状态估计，即均方意义下的最优估计为：其中，，i=1,2,…,mk,是有效回波皆来自目标的条件下的目标状态估计值；是回波来自干扰或杂波情况下的目标状态估计值。PDA的最大优点是它所需要的存储量与标准卡尔曼滤波算法几乎相等，因此很容易应用于实际环境中，也有学者将该算法用于跟踪多目标，但必须多目标处于稀疏杂波环境，跟踪效果才能勉强让人接受。如果处于密集杂波或者目标环境中，就会容易产生误跟。2.3联合概率数据关联（JPDA)联合概率数据关联(JointProbabilityDataAssociation)是Bar-shalom和他的学生在PDA的基础上提出的，它是对PDA的一种推广，它不需要任何关于目标和杂波的先验信息。是在杂波环境中对多目标进行跟踪较好的方法之一。基本思想：测量落入跟踪门相交区域的情形，对应某些观测可能源于多个目标，JPDA的目的就是计算每一个观测与其可能的所有目标的关联概率，且认为所有的有效回波都可能源于每个特定目标，只是它们源于不同目标的概率不同。建立线性状态方程和测量方程描述的混合系统：其中X(k)和Z(k)分别表示k时刻的状态和观测向量；F,H分别表示k时刻的状态转移矩阵和观测矩阵；V(k)和W(k)是零均值相互独立的白色高斯噪声。其中：mk表示在k时刻确认的测量个数；βjt(k)为第j个测量与目标t关联的概率，；为在k时刻第j个测量对目标t进行滤波所得到的状态估计。联合概率数据关联算法有着优秀的性能，但是该算法中，联合事件数是所有候选回波的指数函数，并随着回波密度的增大而迅速增大，致使出现组合爆炸现象。为了解决这个问题，Bar-shalom于80年代后期，又进一步提出最优联合概率数据关联算法。此后，B.Zhou，J.A.Roecke和D.Musicki等人又分别提出快速联合概率数据关联算法、次优(Suboptimal)联合概率数据关联算法和综合(integrated)概率数据关联算法。2.4多假设跟踪（MHT）多假设跟踪同时也是一种多帧的数据关联技术，在算法中，量测数据与目标的关联不仅取决于当前时刻的量测数据而且还取决于前面几帧的历史量测。如果在理想条件下，MHT是公认的处理数据关联的最优算法。MHT算法主要有四个处理步骤：（1）量测数据的聚簇：分别将新接收到的量测数据与前一时刻形成的假设进行关联，形成新簇，即新的假设。值得注意的是，如果步骤（1）中处理的两个独立的簇同时与同一个量测关联，那么这两个簇必须要组合成一个超簇；同时，不与任何簇相关联的量测可以暂时形成初始簇，作为假设航迹的起始。（2）假设生成：这是MHT算法中核心的一步，对每个簇中关联的各个量测进行处理生成新的假设，同时更新簇中每个假设的关联概率以及更新目标的状态。（3）假设剪枝与合并：主要是消除不可行假设，同时对关联概率相近的假设进行合并。（4）假设矩阵管理：根据各假设概率的大小和与量测的关联概率的情况，将假设航迹提升为确认航迹，同时删除不可能存在的假设航迹。MHT算法有两个假设条件：（1）每个量测数据最多只可能与一个目标航迹进行关联；（2）每个目标在某一时刻也最多只能生成一个量测数据。在此基础上对每个时刻得到的每个量测数据与各个目标航迹进行关联，同时考虑多种可能出现关联情况，生成多种关联假设，该算法的关键在于假设概率的计算。计算式如下：式中，Pki表示k时刻第i种假设的概率，PD表示检测概率，βFT表示杂波密度，βNT表示新生目标密度，c是归一化常数，NFT表示杂波数目，NNT表示新生目标数目，NDT表示检测到的目标数目，NTGT为前一帧的目标数，N为高斯型似然函数，NDT+NFT+NNT是当前时刻量测总数。MHT算法优秀之处是能够检测出目标数随时间推移而变化的情况，比如出现新生目标或者有目标终结，但是其缺点在于运算量过于巨大，由于各种可能假设的都需要考虑，使得假设的数量随着目标数和杂波数的增加而成爆炸性的增长，因此带来计算量难以接受，因此很多学者都提出一些假设剪枝方法从而提高运算速度和实时性。假设剪枝通常可以由以下两种方式进行：（1）保留最可能的假设或加权联合考虑几种情况并形成一种假设；（2）保留几种可能性较大的假设，并合并关联概率相似的假设；（3）化简假设矩阵。2.5其它关联方法随着数据关联技术的发展，衍生出了许多的算法，如：全局最邻近数据关联、简易联合概率数据关联(CJPDA)、模糊数据关联(FDA)、最近邻联合概率数据关联(NNJPDA)、最大似然数据关联(MLDA)等。2.6几种数据关联方法的比较方法优点缺点难易适用范围NN计算量小，方法简单抗干扰能力弱，在目标密度较大时易发生关联错误，使用时需加入许多的限制容易适用于信噪比较高，目标密度较小的场合，适用范围较小PDA适用于杂波环境下的目标跟踪需要计算所有可能的量测概率，很难满足实时性的需要较难适用于杂波环境下的目标跟踪JPDA避免了NN方法唯一性可能造成的关联错误，能较好适应密集环境下的目标跟踪联合事件数是所有候选回波的指数函数，并随回波密度的增大迅速增大，致使计算负荷出现组合爆炸的现象较容易适用于杂波环境下密集机动目标的跟踪MHT综合了NN方法和JPDA方法的优点过多依赖于目标和杂波的先验的知识较难适用于杂波环境下密集机动目标的跟踪3多目标跟踪技术的未来发展方向多目标跟踪技术是计算机科学、机器视觉、图像处理、人工智能、模式识别等多学科的结合，是一个尚在发展中的研究方向，还有很多技术难点有待解决。通过对多目标跟踪的难点及其相关方法的分析，多目标跟踪技术研究未来的发展方向为：一是目标建模。目标建模一直是MTT技术的一个关键问题，将是MTT技术的一个主要研究方向。其中使得目标模型随着目标的运动具有自适应能力的研究是一个方面；二是数据关联。多目标跟踪系统的复杂度使得数据关联问题成为MTT技术研究的另一个关键问题，仍是以后研究的一个主要方向；三是多传感器多目标跟踪技术。多传感器的使用可以扩大监视的有效范围，进行三维姿势跟踪和恢复，多个不同的方向视角可用于解决遮挡问题；四是目标行为识别。对所跟踪的目标进行进一步的行为分析。