目标跟踪与数据关联

1、第四章目标跟踪与数据关联概论4. 1 多目标跟踪的基本思想4. 2 数据关联的概念与方法 补记本 章阐述多目标数据关联与跟踪的基本概念及主要思想。所涉及的内容在许多文献中已有不同程度的报导。读者或者可以跳过本章，或者可以通过本章快速了解目标跟踪与数据关联的基本思想与方法 4. 1 多目标跟踪的基本思想多目标跟踪的基本概念是由 Wax在 1955 年首先提出的 。1964 年，Sittler对多目标跟踪理论以及数据关联问题进行了深入的研究，并取得了开创性的进展 。然而，直到 20 世纪 70年代初期，机动多目标跟踪理论才真正引起人们的普遍关注和极大兴趣 。在这一期间，由 Bar-Shalom和

2、Singer 开创的以数据关联技术和卡尔曼滤波技术有机结合为标志的多目标跟踪技术取得了突破性的进展。所谓多目标跟踪，就是为了维持对多个目标当前状态的估计而对所接收到的量测信息进行处理的过程。图 4.1 表示多目标跟踪的基本原理。由图 4.1 可以看出多目标跟踪过程是一个递推过程，并且在开始扫描期间各目标的航迹已经形成。来自传感器的量测信息首先被用于更新已经建立的目标航迹；如果来自传感器的量测数据(回波)落入目标的跟踪门中，则称此回波为有效量测(或有效回波) 。即使目标只有一个，由于杂波的干扰，有效量测也可能为多个。跟踪门被用来粗略确定量测/航迹配对是否合理 。继承继承是指这样一种能力：它可以使

3、用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展。通过继承创建的新类称为“子类”或“派生类”。被继承的类称为“基类”、“父类”或“超类”。继承的过程，就是从一般到特殊的过程。继承概念的实现方式有三类：实现继承、接口继承和可视继承。实现继承是指使用基类的属性和方法而无需额外编码的能力；接口继承是指仅使用属性和方法的名称、但是子类必须提供实现的能力；可视继承是指子窗体（类）使用基窗体（类）的外观和实现代码的能力。封装封装，也就是把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。对象间的相互联系和相互作用过程主要通过消息机制

4、得以实现。对象之间并不需要过多的了解对方内部的具体状态或运动规律。面向对象的类是封装良好的模块，类定义将其说明（用户可见的外部接口）与实现（用户不可见的内部实现）显式地分开，其内部实现按其具体定义的作用域提供保护。类是封装的最基本单位。封装防止了程序相互依赖性而带来的变动影响。在类中定义的接收对方消息的方法称为类的接口。多态多态性（polymorphism）是指同名的方法可在不同的类中具有不同的运动规律。在父类演绎为子类时，类的运动规律也同样可以演绎，演绎使子类的同名运动规律或运动形式更具体，甚至子类可以有不同于父类的运动规律或运动形式。不同的子类可以演绎出不同的运动规律。实现多态，有两种方式

5、：覆盖、重载。覆盖，是指子类重新定义父类的虚函数的做法。重载，是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同）。类和对象类是一个对一组像是对象的一般性描述（如，模板、模式或蓝图）。通过定义，存在于类中的所有对象继承其属性和用于操纵属性的操作。父类是类的集合，子类是类的实例。这些定义蕴含了类层次的存在，父类的属性和操作被子类继承，而子类也可以加入自己“私有的”属性和方法。属性属性依附于类和对象，并且以某种方式描述类或对象。Champeaux及其同事给出了如下的关于属性的讨论：现实的实体经常用指明其稳定特性的词来描述。大多数物理对象具有形状、重

6、量、颜色和材料类型等特性；人具有生日、父母、名字、肤色等特性，特性可被视为在类和某确定域之间的二元关系。面向对象的开发方法传统的面向过程的开发方法是以过程为中心，以算法为驱动，因此，面向过程的编程语言是程序=算法+数据面向对象的开发方法是以对象为中心，以消息为驱动，因此，面向对象的编程语言是程序=对象+消息。传统开发方法开发软件存在的问题软件重用性差软件可维护性差软件稳定性差面向对象的分析面向对象的分析（Object Oriented Analysis, OOA），是在一个系统的开发过程中进行了系统业务调查以后，按照面向对象的思想来分析问题。四个基本步骤：第一步，获取功能需求。第二步，根据功能

7、和参与者确定系统的对象和类。第三步，确定类的结构、主题、属性和方法。第四步，建造对象模型。面向对象的设计面向对象的设计（Object Oriented Design，OOD），是根据OOA中确定的类和对象，设计软件系统，以作为面向对象的编程的基础。整个设计过程分为系统设计和对象设计。系统设计过程包括：系统分解确定并发性设计人机交互子系统设计任务管理子系统设计数据管理子系统面向对象的模型模型是对实体的特征和变化规律的一种表示或抽象，即把对象实体通过适当的过滤，用适当的表现规则描绘出的模仿品。该模型主要关心系统中对象的结构、属性和操作，它是分析阶段三个模型的核心，是其他两个模型的框架。在面向对象的

8、开发中，有对象模型、动态模型和功能模型这三种常用模型。对象模型对象模型使表示了静态的、结构化的系统数据性质，描绘了系统的静态结构，它是从客观世界实体的对象关系角度来描绘的，表现了对象的相互关系。在该模型中包括以下几方面的元素。对象和类关联和链层次结构动态模型动态模型是与时间和变化有关的系统性质。该模型描述了系统的控制结构，它表示了瞬间的、行为化的系统控制。它关心的是系统的控制、操作的执行顺序，它从对象的事件和状态的角度出发，表现了对象的相互行为。事件状态状态图图 4.1 多目标跟踪的基本原理示意图图 4.2 是一个两目标情形下跟踪门和有效回波的关系示意图。跟踪维持包括机动识别和自适应滤波与预测

9、，用以估计各目标航迹的真实状态。在跟踪空间中，数据关联的输入是有效量测，与已建立的目标航迹不相关的量测或回波可能来自潜在的新目标或杂波，由跟踪起始方法可以鉴别其真伪，并相应地建立新的目标航迹。当目标逃离跟踪空间或被摧毁时，由跟踪终结方法可删除航迹，以减轻不必要的计算开销 。最后，在新的量测到达之前，由目标预测状态和接收正确回波的概率可以确定下一时刻跟踪门的中心和大小，以便重新开始下一时刻的递推循环。多目标跟踪问题包括许多方，主要包括机动目标模型与自适应跟踪算法 、跟踪门的形成、数据关联、跟踪维持、跟踪起始与终结等 。图 4.2 跟踪门和有效回波示意图4. 2 数据关联的概念与方法多目标跟踪过程

10、的关键问题是如何进行有效的数据关联 。数据关联问题首先产生于传感器观测过程和多目标跟踪环境的不确定性。实际的传感器系统总是不可避免地存在着测量误差，缺乏跟踪环境的先验知识；我们往往不能确知目标的个数，无法判定观测数据是由真实目标还是由其它虚假目标产生的。这些不确定因素破坏了回波观测与其目标源之间的对应关系，是导致多传感器多目标数据关联关系模糊的基本原因在实时的多目标跟踪过程中，同一个目标在多传感器上建立的量测必定因其物理来源相同而具有某种相似特征，在此同时，也必定因为杂波的干扰和传感器自身性能的不稳定而导致这些量测的特征不完全相同。数据关联的目的就是利用这种量测的相似特征，来判定这些特征不完全

11、相同的量测是否源于同一个目标数据关联问题广泛地存在于多传感器多目标跟踪的各个过程。跟踪过程中的新目标检测，需要在多个采样周期之间进行“观测观测”的数据关联，以便为新目标建立起始航迹提供充分的初始化信息；而观测数据的直接融合也需要进行“观测观测”关联，以稳定航迹生存周期。为了更新航迹，维持跟踪的持续性，还需要进行“观测航迹”关联以确定用于航迹修正的新观测数据。另外，在分布式多传感器系统中，一个由本地跟踪输出的多目标航迹数据融合，首先需要进行“航迹航迹”的数据关联，以确定哪些本地数据来源于共同的跟踪目标。单传感器跟踪过程中冗余航迹合并也要进行“航迹航迹”的数据关联。近 20 年来，关于多目标数据关

12、联方法的研究取得了丰硕的成果。下面介绍其中有代表性的几种方法。4. 2. 1 “最近邻”方法 1971 年 Singer 等提出了一种具有固定记忆要求并且能在多回波环境下工作的跟踪滤波器。这种滤波器仅将在统计意义上与被跟踪目标预测位置（跟踪门中心）最近的有效回波作为候选回波。其中，表示新息， S ( k )表示 v ( k )的协方差， d ( z ( k )表示目标预测位置与有效回波 z ( k )之间的距离。“最近邻”方法的思想如图 4. 3 所示。图 4.3 最近邻数据关联方法示意图“最近邻”方法的基本含义是，“唯一性”地选择落在相关跟踪门之内且与被跟踪目标预测位置最近的观测作为目标关联

13、对象，所谓“最近”表示或者统计距离最小或者残差概率密度最大。基本的最近邻方法实质上是一种局部最优的“贪心”算法，并不能在全局意义上保持最优。在目标回波密度较大的情况下，多目标相关波门相关交叉，最近的回波未必由目标所产生。最近邻方法便于实现，计算量小，适应于信噪比高 ，目标密度小的条件。最近邻方法的抗干扰能力差，在目标密度较大时容易产生关联错误。最近邻方法的实际应用往往还需要附加其它限制。4. 2. 2 “全邻”最优滤波器 1974 年， Singer、 Sea 和 Housewright提出了全邻滤波器：其中表示最佳修正值。P i (k )为 k 时刻航迹 i 正确的概率， b i( k |

14、k -1 )为 k -1 时刻对 k 时刻航迹 i的状态预测偏差的均值， L (k ) = ( 1+ k ) L ( k -1 )为 k 时刻全部可能的航迹总数， k 为第 k 次扫描期间的候选回波数。这种滤波器不仅考虑了所有候选回波(空间累积量测)，而且考虑了跟踪历史，即多扫描相关(时间累积信息)。 4. 2. 3 概率数据关联滤波器 1972 年， Bar-Shalom 和 Jaffer在关于数据关联的研究中，首先试图应用位于跟踪门中的所有回波以获得可能的后验概率。在此基础上， Bar-Shalom和 Jaffer在1975年提出了概率数据互联滤波器。 4. 2. 4 多模型方法 Blom

15、1984 年提出了多模型滤波器(基于Kalman 滤波器)：其中 j ( k )表示模型 M j 在时刻 k 正确的概率 。在这种算法中，每一个模型对应一个不同的机动输入水平，可以以较大的计算资源来换取机动性能的提高，其主要问题是如何选择保持最佳跟踪性能的离散机动水平近 10 年来，受到 Blom 和 Bar-Shalom 思想的激励，概率数据互联和多模型算法的研究变得十分活跃，这些算法正在被应用于多传感器情形。我们将在第五章对概率数据关联算法 ，多模型算法和相互作用多模型概率数据互联算法进行深入讨论。4. 2. 6 联合概率数据关联滤波器在多目标跟踪问题中，如果被跟踪的多个目标的跟踪门互不相

16、交（如图4.4（a）所示），或虽然跟踪门相交，但没有量测落入相交的区域（如图4.4（b）所示 ），则多目标跟踪问题总可以简化为多目标环境中的但目标跟踪问题。实际的情形是，跟踪门相互交错，并且有许多量测落入这些相交区域中（如图4.5所示 ）。如图4.4图 4.5多目标跟踪问题量 测确认的一般情形1974年， Bar-Shalom在多目标数据关联研究中，推广了他的概率数据互联滤波方法，引入了“聚”的概念，提出了联合概率数据互联滤波器，以便对多个目标进行处理。这种方法不需要关于目标和杂波的任何先验信息。聚定义为彼此相交的跟踪门的最大集合，总有一个二元聚矩阵与其关联。从聚矩阵中得到有效回波和杂波的全排

17、列和所有的联合事件，进而通过联合似然函数来求解关联概率。联合概率数据关联方法以其优良的相关性能而引起研究者的高度重视。然而，由于在这种法中，联合事件数是所有候选回波数的指数函数，并随回波密度的增大二迅速增大，致使计算负荷出现组合爆炸现象。为了解决这一问题，1986年，Fitzgeraled提出了一种简化的联合概率数据关联方法，其中关联概率用一个基于经验的特殊规则来计算。1993年，Zhou和Bose提出了基于深度优先搜索的数据关联快速算法。这些算法在降低计算量的同时，也降低了算法的有效性、可靠性和应用范围。 关于联合概率数据关联算法的身体讨论将在第六章进行。4. 2. 7 多假设方法 1977

18、 年， Reid 15 针对多目标跟踪问题，基于“全邻”最优滤波器和 Bar-Shalom的聚概念，提出了多假设跟踪方法。这种方法的主要过程包括：假设生成、假设估计、假设管理（删除、合并、聚类等）。关于这种方法的深入讨论将在第六章进行。 4. 2. 8航迹分裂方法Sittler1974 年提出了航迹分裂方法：其中， k ， l 表示 k 时刻第 l 个航迹正确的事件，c k 是常数。 这种方法基于每一个可能航迹的似然函数。当接收到更多的回波时，将原有的航迹分裂为相应数目的新航迹，然后计算每一航迹的似然函数，把低于指定门限的摒弃，其余保留。 4. 2. 9 分布式多传感器多目标跟踪与数据关联的一

19、般理论Chong，Mori，Chang等一直专注于多传感器多目标跟踪一半和理论的研究。他们以各种排名次序发表了许多很有影响的研究论文，在多传感器目标跟踪研究中引入了信息图（Information Graph）和信息集（Information Set）的概念，并以此为基础，建立了没有先验识别的分布式多传感器多目标跟踪与数据关联的一般理论。他们应用贝叶斯方法道出了两个一般算法，一个处理集合中的航迹起始和航迹延续；另一个是第一个特殊形式，可以证明它包含典型的现有算法作为子集。他们在其研究中还引入了多假设技术，并给出了递推假设估计和成批假设估计的算法。我们将在第七章专门讨论分布式多传感器多目标跟踪与数据关联的一般理论。 4. 2. 10 基于神经网络的多目标数据关联