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