吴健康 (中国北京市石景山区玉泉路19号甲, Beijing 8, 100048, CN)
SUN, Shuyan (19 Yuquan Rd, Shijingshan District, Beijing 8, 100048, CN)
孙树岩 (中国北京市石景山区玉泉路19号甲, Beijing 8, 100048, CN)
JIANG, Sheng (19 Yuquan Rd, Shijingshan District, Beijing 8, 100048, CN)
中国科学院研究生院 (中国北京市石景山区玉泉路19号甲, Beijing 8, 100048, CN)
WU, Jiankang (19 Yuquan Rd, Shijingshan District, Beijing 8, 100048, CN)
吴健康 (中国北京市石景山区玉泉路19号甲, Beijing 8, 100048, CN)
SUN, Shuyan (19 Yuquan Rd, Shijingshan District, Beijing 8, 100048, CN)
孙树岩 (中国北京市石景山区玉泉路19号甲, Beijing 8, 100048, CN)
| 权利 要求 1、 一种特征迹驱动的多目标跟踪装置， 其特征在于包括观测数据模块、 特征迹 生成、 管理、 确认和删除模块、 滤波模块； 观测数据模块是一个或多个传感器系统， 通过传感器系统得到目标的观测数据的 数值表示；传感器系统把目标的物理特性和运动特性转换成谱、空间和时间域的数据； 特征迹生成、 管理、 确认和删除模块的输入端与观测数据模块的输出端连接， 用 于接收观测数据模块所产生的目标观测数据， 形成跟踪门并确定邻域数据， 形成特征 迹， 并对特征迹进行管理、 确认和删除处理， 最后由特征迹生成、 管理、 确认和删除 模块输出特征迹信息； 滤波模块的输入端与特征迹生成、 管理、 确认和删除模块的输出端连接， 用于接 收特征迹生成、 管理、 确认和删除模块的特征迹数据， 并预测输出目标状态和位置。 2、 如权利要求 1 所述的特征迹驱动的多目标跟踪装置， 其特征在于， 所述特征 迹生成、 管理、 确认和删除模块需要在谱、 空间和时间域里， 使用目标的物理模型和 动态模型、 以及噪声模型， 运用数据融合的方法， 将目标较高层次的特征从目标的观 测数据中提取出来并形成特征迹。 3、 如权利要求 1 所述的特征迹驱动的多目标跟踪装置， 其特征在于， 所述特征 迹由六元组结构组成表示如下： Signature(a, t) = {Dt， Lt, Ft, Kt, Ct,v,} 式中： Dt表示为测量数据； Lt表示为等效状态序列； Ft表示为特征序列； Kt表示 为运动连续性； Ct表示为特征连续性； vt表示为目标整体可信度， t为当前时刻， a为 起始时刻。 4、 一种使用权利要求 1 所述特征迹驱动的多目标跟踪装置的特征迹驱动的多目 标跟踪方法， 其特征在于， 该方法包括： 步骤 S1 : 将目标 O的特征迹设定为目标在时间区间 [a,t]内的数据结构， 其中起 始时刻 a=max(t-N+l,s)， 时间区间长度为 N， s为目标出现时刻， t为当前时刻； 目标 在时刻 t的特征迹 Signature(a,t)由六元组结构组成表示如下： Signature (a, t) = {Dt, Lt, Ft, Kt, Ct, v,} 式中： Dt表示为测量数据； Lt表示为等效状态序列； Ft表示为特征序列； Kt表示 为运动连续性； Ct表示为特征连续性； V,表示为目标整体可信度； 步骤 S2: 根据每一帧的目标均具有特征特性和运动特性， 利用同一目标 >在前 后帧之间特征特性和运动特性的马尔科夫性， 生成邻域， 形成跟踪门； 步骤 S3 : 确定邻域后， 将没有落入现有特征迹的邻域内的观测信息设定为新目标 起点，生成新的特征迹；将落入现有特征迹的邻域内的观测信息与现有特征迹做关联， 生成更新的特征迹； 将所述特征迹以树结构保存； 将树中自根节点的每一条路径对应于一个可能的特 征迹数据关联序列； 如果所述特征迹时间达到 N个采样间隔， 则将目标整体可信度比 较低的特征迹删除， 再将等效状态序列之差小于某个门限的特征迹合并； 最后， 从该树中抽取目标整体可信度最高的特征迹， 并输出目标整体可信度最高 的特征迹； 步骤 S4: 在前后帧之间， 设定马尔科夫性如下： 定义运动马尔科夫可信度： c , 其中， cs (ξκί )为前一时刻等效状态 ^到当前时刻等效状态 ^的转移特性， cM (ξ |Zr_, ) 表征当前时刻等效状态 与整个特征迹等效状态序列 L,_i的相容性， j=0,l,...， m; 定义特征马尔科夫可信度： = P{ l )其中， cF d l^ )为前一时刻特征迹 到当前时刻特征迹 ,，,的转移特性， cK ( l J 表征 当前时刻特征迹;^与整个特征迹 一 ,的相容性； 步骤 S5 : 给定特征迹， 使用特征迹整体可信度、应用航迹起始原则和终结原则对 之进行确认和删除判断； 在一棵树中， 如果全部特征迹被删除， 则目标航迹到此终止； 如果有多于一个的 特征迹被确认， 则保留整体可信度最大的特征迹； 重复执行步骤 S1-S5实现多目标跟 踪。 5、 如权利要求 3或 4所述的特征迹驱动的多目标跟踪装置或方法， 其特征在于， 所述测量数据， 表示为 Dt = 其中， 是起始时刻 a由 n个传感器所获得的 数据矢量， 是当前时刻 t由 n个传感器所获得的数据矢量。 6、 如权利要求 3或 4所述的特征迹驱动的多目标跟踪装置或方法， 其特征在于， 所述等效状态序列， 表示为 Lt = ¾,..., ; ^是起始时刻 a的等效状态， 是当前时刻 t的等效状态， 包含目标的位置、 速度和加速度， 由测量数据 Dt导出。 7、 如权利要求 3或 4所述的特征迹驱动的多目标跟踪装置或方法， 其特征在于， 所述特征序列， 表示为 Ft = ia,...,Tit); ;/。是起始时刻 a的特征迹， 是当前时刻 t的特 征迹， 即从特征测量数据中所提取的目标的谱和空间特征序列； 对于视频数据而言， 其特征可选取为颜色信息、 轮廓信息和几何形状信息。 8、 如权利要求 3或 4所述的特征迹驱动的多目标跟踪装置或方法， 其特征在于， 所述运动连续性， 表示为 ={ζ^,} ; 其中， 是当前时刻 t运动马尔科夫可信度， 包 括了位置、 速度和加速度的连续性描述； 是当前时刻 t基于运动信息为目标 0的概 率。 9、 如权利要求 3或 4所述的特征迹驱动的多目标跟踪装置或方法， 其特征在于， 所述特征连续性， 表示为 ; 其中 是当前时刻 t特征马尔科夫可信度， 也即 当前特征在整个特征迹中的相容性， Tt是当前时刻 t基于特征信息为目标 0的概率。 10、如权利要求 3或 4所述的特征迹驱动的多目标跟踪装置或方法，其特征在于， 所述目标整体可信度， 表示为 ν,; 它给出了特征迹在此时此地表征某一目标的概率。 |
技术领域
本发明属于多目标跟踪技术领域， 涉及一种特征迹驱动的多目标跟踪方法及装 置。 背景技术
在强干扰情况下检测和跟踪大量动态目标在国 防和国民经济中有重要应用， 也 是科学研究的一大难题。 目前传统目标跟踪邻域和视频跟踪邻域的多目 标跟踪方法 有各自的优势， 也有各自的局限性， 但都达到了进一步提高性能的瓶颈。
多目标跟踪无论在军事还是在民用都有着十分 广泛的应用。 如在大干扰环境下 检测和跟踪大量且高度机动的来犯飞行器， 各种交通车辆和人员的监测等。 多目标 跟踪 (Multiple Target Tracking, MTT)的难点在于： 1 ) 观测数据含有大量的噪声和杂 波干扰， 有时真实目标信号的检测概率甚至低到 50% ; 2) 随着目标的新生、 消亡和 裂变， 目标的数目本身也是随机变化的； 3 ) 目标的高度机动， 对跟踪方法的动态性 能提出更高的要求。 这些难点使得多目标跟踪方法的核心算法， 即数据关联， 变得 更加复杂： 在上百个目标和上千个测量数据中， 究竟哪个数据是哪个目标产生的， 它又该对应于下一时刻的哪个数据呢？
1978年， Reid( Donald B. Reid. "An Algorithm for Tracking Multiple Targets". IEEE Transactions on Automatic Control, Vol. 24, No. 6, December 1979. )提出了多假设 £艮踪 (MHT)方法， 此后， 很多学者提出改进算法（如： Blackman, S.S.; Dempster, RJ.; Broida, T.J. "Multiple hypothesis track confirmation for infrared surveillance systems". Aerospace and Electronic Systems, IEEE Transactions on, Volume 29, Issue 3, July 1993 Page(s):810 - 824； Lancaster, J.; Blackman, S. "Joint IMM/MHT Tracking and Identification for Multi-Sensor Ground Target Tracking". Information Fusion, 2006. ICIF '06. 9th International Conference on July 2006 Page(s):l ― 7； Muthumanikandan, P.; Vasuhi, S.; Vaidehi, V. . "Multiple Maneuvering Target Tracking Using MHT and Nonlinear Non-Gaussian Kalman Filter". Signal Processing, Communications and Networking, 2008. ICSCN '08. International Conference on 4-6 Jan. 2008 Page(s):52一 565 )。 MHT方法在每一时刻根据每一目标估计状态在观 测空间生成跟踪门， 确定 落入跟踪门内的观测， 以一个目标只能产生一个观测、 一个观测只能来源于一个目 标为约束， 针对每一目标估计状态和相应跟踪门内的每一 观测生成全局关联假设。
MHT考虑了观测来源于新目标的可能性， 以及目标没有被观测到的可能性， 将每一 次递推中的数据关联假设积累 N个时间点后， 进行 N-scan回溯决策。 原理上， 多假设 跟踪能求得理想的数据关联。 在实际中， 这却是一个 NP的难题， 算法的计算复杂性 指数增长， 无法对所有可能的假设进行回溯。
上述方法代表了当前多目标跟踪邻域的水平， 目前的研究和发展大多是对这类 方法的改进。 然而， 这类方法针对的都是雷达观测数据， 其特点是随机点目标。 视 频跟踪基于图像和视频处理方法， 主要依赖于对目标视频特征的分析和前后帧目 标 特征的相似性。 由于视频特征非常有效， 在很长的时间内并没有把多目标的数据关 联作为研究重点。 Jiang等 ( H. Jiang, S. Fels, and J. J. Little. A linear programming approach for multiple object tracking. Int Conf. on Computer Vision and Pattern Recognition, 2007. ) 针对人群中个人跟踪问题， 提出了使用线性规划来求全局最优 目标轨迹的方法。 他们用网络来表示可能的数据关联， 网络中的每一个连接表示每 一个可能的关联。 连接的代价函数由三个分量组成： 一是上下两个观测的特征相似 性（或称似然率）， 二是上下两个观测的位置之距离， 三是遮挡所引起的损失。 有了 代价函数， 使用线性规划或 Vitabi算法求取最优路径就理所当然了。 Li等 （Yuan Li, Chang Huang and Ram Nevatia, Learning to Associate: Hybrid Boosted Multi-Target Tracker for Crowded Scene, Int Conf. on Computer Vision and Pattern Recognition, 2009. )在以上数据关联方法中进一步加入运动模型 他们将可能的运动模型表示成 训练数据， 通过学习嵌入相似度量中， 进一步改善数据关联的质量。
传统的跟踪邻域和视频跟踪分别有着自己的研 究传统和技术特点。 例如， 传统 跟踪邻域方法都属于广义的贝叶斯网滤波， 是概率和统计方法， 没有目标特征的概 念； 而视频跟踪有相当一部分工作是确定的数字方 法， 如目标特征和相似度量， 线 性规划等。对于这类方法， 充分吸取传统跟踪邻域的完整的数据关联方法 很有必要。 这两个邻域都局限在各自的数据和传统方法中 ， 然而， 随着探测技术的发展， 我们 获得的目标数据不仅是点， 有时是象； 不仅是单一观测手段， 有时是多种或安装在 多个地点的传感器和成象装置。 应用邻域也在不断扩展， 双方的传统应用邻域也有 很多交叉。 例如使用实时成象系统对地面目标的跟踪。 为了适应新型传感器技术的 发展， 为了满足不断出现的新的应用的需求， 必须从基本方法的层面， 研究新的多 目标跟踪方法。 新的多目标跟踪方法必须面对的是大量数目变 化的目标， 目标高度 机动， 并伴随强干扰和虚警。
从根本上说， 对多目标的检测和跟踪的基础， 是融合各种探测手段测得的关于 目标的谱、 空间和时间域的数据， 充分利用目标和干扰的运动知识， 充分利用目标 和干扰对传感器的反射特性，构建目标的"特 迹 "（Signature), 是跟踪方法的基础。 由此我们发明了"特征迹驱动的多目标跟踪方 " （ Signature-Driven multi-target Tracking, SDT)。
目标的谱、 空间和时间域的信息的融合， 即"特征迹"， 是一目标区别于另一目 标、 区别于干扰和背景的根本。 目标的谱信息是目标对于探测器的反射特征， 它的 空间分布就是目标的形状和表面特征， 对于时间的分布就是目标的运动特性。 在进 行数据关联的时候， 使用"特征迹 "的概念， 我们可以系统地利用目标谱及其空间分 布的连续性， 目标运动特性 （位置、 速度、 加速度、 运动模型） 的连续性。 传统的 跟踪方法， 如多假设跟踪， 只是通过位置连续性的时间积累， 完成对假设的取舍。 视频跟踪方法更多地强调了视频特征， 没有信息融合的概念， 也没有形成利用时间 域连续性的机制。
特征迹驱动的多目标跟踪方法对于可能的目标 ， 在一定的时间间隔内生成该候 选目标的"特征迹"， 计算其运动模型、 特征度量， 以及运动和特征的马尔可夫可信 度， 并由此导出该特征迹的整体可信度。 这一特征迹生成过程使用了目标的动态模 型和物理性质， 实现在谱、 空间和时间域的信息融合。 例如， 物体有 6个自由度 （3 个位置、 3个方位）， 它们的运动都涉及 6个自由度的变化， 产生相对于传感器的位置 和朝向的变化。 反映到测量数据上， 便是运动和特征以及马尔可夫性。 这是目标有 别于干扰， 以及目标之间相互区别的物理基础。 另一方面， 雷达数据的检测概率主 要取决于雷达等效切面积（RCS)， 而加入谱、 空间和时间域信息后， 可以实现目标 的自适应检测， 大大提高目标的检测概率。 目标的特征、 马尔可夫性和检测概率构 成了目标特征迹的整体可信度。 使用整体可信度来确定该特征迹的真伪和去留 ， 从 而在第一时刻去除虚假关联， 可以大大降低计算复杂度。 经过确认的特征迹所代表 的数据将送往滤波器。 这样， 进入滤波器的干扰很少， 滤波出的航迹的准确性也大 大提高。
1. 问题描述
为便于下文阐述， 我们首先给出单目标跟踪和多目标跟踪的贝叶 斯滤波估值方 法的基本框架。
1.1 单目标跟踪
在单个点目标动态跟踪中， 假定目标状态在状态空间 里是一阶马尔科夫 过程， 它的状态转移概率为 PCCIJCM), 也即给定目标在时刻 t-1的状态 JC ， 它在时刻 t状态为 X,的概率密度。在观测空间 ze/ ， 目标在时刻 t的状态 X,可以被观测到的 似然函数为 7( C,)。 我们所要求的是在时刻 t， 在给定该时刻和该时刻以前的所有观 测值 Z ,...^)的条件下， 目标具有状态 X,的后验概率密度 ^' Ι^ ) , 这可以通过 如下的迭代方法求得：
求得后验概率后， 可以用其最大后验概率状态作为估值， 称 MAP方法。 然而， 这仅 是理论解。 在实现中， 我们必须知道初始概率、 求得转移概率的动态方程、 求得似 然率的测量方程， 以及它们的分布函数。 为实现的方便， 人们常假定目标状态和观 测服从线性高斯动态模型， 或多个高斯模型的叠加。 这里， 我们在滤波时也采用高 斯分布的假定和 kalman滤波（ Kalman, R. E. 1960. "A New Approach to Linear Filtering and Prediction Problems," Transaction of the ASME― Journal of Basic Engineering, pp. 35-45 (March 1960)。
1.2 多目标跟踪
图 1给出了存在噪声和杂波干扰条件下，大机动 数目变化的多目标运动与观测。 在状态空间中， 假定在时刻 t-7目标个数为 m(t-7)， 并假设这些目标的状态为
JC,_, = {.χ)_„χΙ„...,^- ]) Υ。进一步假设目标以检测概率 ?产生观测 I X )。 在时刻 t-1,我们获得观测数据 ^，^,...,^—")。 这些观测中， 部分观测是由 目标产生的， 其他观测则是杂波或干扰。 也有部分目标所产生得观测并没有被检测 到。 因此， 如何在获得的观测中， 找到属于目标所产生的观测数据 ^ 1 ,， 实属不易。 再者， 到时刻 t， 一些目标可能会消失， 而继续存在的目标的状态可能会改变， 或切 换运动模型， 并可能有新的目标产生， 此时获得的观测为 ...， W )， 此 时又如何找到与目标 /所产生的观测呢？ 因此， 多目标跟踪的任务就是在干扰、 目标 机动和数目变化的复杂情况下， 对每一个目标 /， 找到它在每一个时刻的观测数据序 列 z L J = (z;— Κ，...，^)。
图 2 给出了传统多目标跟踪的基本原理框图。 它以滤波为中心， 在寻找目标 所对应的观测 时，它使用目标的动态特性产生跟踪门，只对 门内的观测进行关联。 这时， 仍存在的问题有： 门内的观测可能有多个， 哪个最有可能？此时， 也存在目 标产生的观测没有被检测到的情况。 再者， 两个或多个目标的跟踪门可能重合。 这 些问题使得多目标跟踪中的数据关联方法难以 应付。 为了更好地解决这些问题，
MHT在 N个时间点寻求最优解。 然而， 目标动态特性极大地挑战目前跟踪门的产 生方法， 在目标的先验知识不够或使用不充分的情况下 ， 求最优很难奏效。 发明内容
为了解决现有技术存在的问题， 本发明的主要目的在于提供一种特征迹驱动的 多目标跟踪方法及装置。
为达成上述目的， 本发明提供的一种特征迹驱动的多目标跟踪装 置， 该装置包 括- 观测数据模块是一个或多个传感器系统， 通过传感器系统得到目标的观测数据 的数值表示； 传感器系统把目标的物理特性和运动特性转换 成谱、 空间和时间域的 数据；
特征迹生成、管理、确认和删除模块， 其输入端与观测数据模块的输出端连接， 用于接收观测数据模块所产生的目标观测数据 ， 形成跟踪门并确定邻域数据， 形成 特征迹， 并对特征迹进行管理、 确认和删除处理， 最后输出特征迹信息；
滤波模块， 其输入端与特征迹生成、 管理、 确认和删除模块的输出端连接， 用 于接收特征迹生成、 管理、 确认和删除模块的特征迹数据， 并预测输出目标状态和 位置。
为达成上述目的， 本发明提供的一种使用特征迹驱动的多目标跟 踪装置的特征 迹驱动的多目标跟踪方法， 该方法包括步骤如下：
步骤 S1 : 将目标 O的特征迹设定为目标在时间区间 [a，t]内的数据结构， 其中起 始时刻 a=max(t-N+l,s)， 时间区间长度为 N， s为目标出现时刻， t为当前时刻； 目 标在时刻 t的特征迹 Signature(a，t)由六元组结构组成表示如下：
Signature(a, t) = {D t ， L t ， F t , K t ， C t , ¼}
式中： D t 表示为测量数据； L t 表示为等效状态序列； F t 表示为特征序列； K t 表 示为运动连续性； C t 表示为特征连续性； V,表示为目标整体可信度；
步骤 S2: 根据每一帧的目标均具有特征特性和运动特性 ， 利用同一目标 O在前 后帧之间特征特性和运动特性的马尔科夫性， 生成邻域， 形成跟踪门；
步骤 S3: 确定邻域后， 将没有落入现有特征迹的邻域内的观测信息设 定为新目 标起点， 生成新的特征迹； 将落入现有特征迹的邻域内的观测信息与现有 特征迹做 关联， 生成更新的特征迹；
将所述特征迹以树结构保存； 将树中自根节点的每一条路径对应于一个可能 的 特征迹数据关联序列； 如果所述特征迹时间达到 N个采样间隔， 则将目标整体可信 度比较低的特征迹删除， 再将等效状态序列之差小于某个门限的特征迹 合并； 最后， 从该树中抽取目标整体可信度最高的特征迹， 并输出目标整体可信度最 高的特征迹；
步骤 S4: 在前后帧之间， 设定马尔科夫性如下：
定义运动马尔科夫可信度： c^n ^m ^^n 其中，
^ (^^M )为前一时刻等效状态 ,到当前时刻等效状态^的转移特性， 表征当前时刻等效状态 与整个特征迹等效状态序列 的相容性， j=0,l,..., m ;
其中， c F 表 征当前时刻特征迹 与整个特征迹 _,的相容性；
步骤 S5 : 给定特征迹， 使用特征迹整体可信度、 应用航迹起始原则和终结原则 对之进行确认和删除判断；
在一棵树中， 如果全部特征迹被删除， 则目标航迹到此终止； 如果有多于一个 的特征迹被确认， 则保留整体可信度最大的特征迹； 重复执行步骤 S1-S5实现多目 不艮 。
本发明的有益效果： 本发明提出了一种崭新的特征迹驱动的多目标 跟踪方法
( SDT)。它从多目标检测和跟踪的物理基础出发 从根本上提出一动态目标有别于 干扰和其它目标的度量 一 "特征迹"， 并给出了在谱、 空间和时间域使用目标的物 理特性和运动特性融合测量数据生成特征迹， 计算基于运动马尔可夫可信度、 特征 马尔可夫可信度以及检测概率和虚警密度的特 征迹整体可信度的方法。 使用特征迹 及其可信度， SDT在第一时间去除噪声， 大大提高了数据关联的可靠性， 使得跟踪 结果中真航迹概率增加、 寿命加长。 由于进入滤波器的是确认后的特征迹数据， 使 得跟踪结果的精度大大提高。 实验结果表明， 特征迹驱动的多目标跟踪方法在性能 上远优于目前公认为最佳的多假设跟踪 （MHT) 方法。
SDT方法一开始就利用特征迹去除噪声和干扰， 大大简化了算法的复杂度。 由 于 MHT算法有很多简化算法， 需要进行认真调査才能确定其最新的计算复杂 度。 附图说明
图 1给出了现有技术存在噪声和杂波干扰条件下 大机动、数目变化的多目标运 动与观测。
图 2 给出了传统多目标跟踪的基本原理框图。
图 3是本发明 SDT方框图。
图 4是本发明特征迹树的生成示意图。
图 5是本发明目标轨迹和虚警数据示意图。
图 6 (a) 是现有技术 MHT跟踪结果。
图 6 (b) 是本发明 SDT跟踪结果示意图。
图 7 (a)、 图 7 (b) 是为了复杂化跟踪场景， 向鱼缸中加入了与鱼形态相似的 纸片， 作为杂波和干扰。
图 8是相交目标跟踪效果示意图。 具体实施方式
为使本发明的目的、 技术方案和优点更加清楚明白， 以下结合具体实施例， 并 参照附图， 对本发明进一歩详细说明。
一、 下面介绍本发明特征迹驱动的多目标跟踪方法
如图 3示出本发明的 SDT方框图与图 2中的传统跟踪方法的流程不同，本发明 的 SDT的数据关联发生在滤波之前， 由特征迹扮演中心角色。 由于特征迹是谱、 空 间和时间特征数据的融合， 它是目标能区别于其它目标和噪声的最完全的 信息， 由 它形成的跟踪门更合理， 也更能去除噪声； 由它进行航迹的确认和删除也更为有效。 确认后的特征迹所关联的数据送往滤波器， 使加入滤波器的噪声远少于信号， 大大 提高了跟踪精度。
如图 3示出 SDT方框图， 包括： 观测数据模块是一个传感器系统， 通过传感器系统得到目标的观测数据的数值 表示； 传感器系统把目标的物理特性和运动特性转换 成谱、 空间和时间域的数据； 特征迹生成、 管理、 确认和删除模块， 其输入端与观测数据模块的输出端连接， 用 于接收观测数据模块所产生的目标观测数据， 使用跟踪门产生邻域数据， 形成特征 迹， 并对特征迹进行管理、 确认和删除处理， 最后输出特征迹信息； 跟踪门形成模 块， 其输入端与特征迹生成、 管理、 确认和删除模块的输出端连接； 其输出端与特 征迹生成、管理、确认和删除模块的输入端连 接； 跟踪门形成模块接收特征迹数据， 由特征迹定义邻域， 生成并输出邻域数据； 滤波模块， 其输入端与特征迹生成、 管 理、 确认和删除模块的输出端连接， 用于接收特征迹生成、 管理、 确认和删除模块 的特征迹数据， 并预测输出目标状态和位置。
目标特征迹是传感器系统所得到的目标观测数 据的数值表示。 传感器系统把目 标的物理特性 （如反射系数， 辐射率， 形状）和运动特性（如位置， 速度， 加速度， 转弯） 转换成谱、 空间和时间域的数据。 未经处理的数据所包含的目标特征层次较 低， 需要在谱、 空间和时间域里， 使用目标的物理模型和动态模型， 以及噪声模型， 运用数据融合的方法，将目标较高层次的特征 从这些数据中提取出来并形成特征迹。
背景和杂波可视为特殊类型的目标， 对目标和杂波的数学建模是分析方法和跟 踪算法的基础。 已知关于目标、 杂波和监控区域的先验信息， 在提出跟踪算法之前， 有必要对目标和杂波进行数学建模。 在建模时， 要考虑传感器系统的特性、 目标反 射回波的特性、 目标运动学特性、 杂波的特性等等。 在对目标和杂波建模之后， 需 要建立目标模型数据库， 数据库中每种目标数据项中的变量包括： 目标类型、特征， 可能的运动学模型， 目标的出现概率； 杂波类型、 特征， 以及杂波的出现概率等。
1 目标特征迹定义
我们将目标 O的特征迹 （Signature) 定义为目标在时间区间 [aJ]内的数据结构， 其中起始时刻 a=max(t-N+l^)， 时间区间长度为 N, s为目标出现时刻， t为当前时刻。
Signature(a,t)是一六元组结构：
Signature^, t) = {D„ L„ F„ K„ C" v,}
其中六元组结构组成包括：
♦ 测量数据： Α= (ζ α ，... ,ζ,) ; 其中 是起始时刻 a传感器所获得的数据矢量， 当前时刻 1由《个传感器所获得的数据矢量。
♦ 等效状态序列： ξ,) ; 是起始时刻 a的等效状态， ξ,是当前时刻 t 的等效状态， 包含目标的位置、 速度和加速度， 由测量数据 A导出。 特征序列： F t = (η α ,... ,η,^ /。是起始时刻 a的特征迹, 是当前时刻 t的特征迹， 即从特征测量数据中所 提取的目标的谱和空间特征序列； 对于视频数据而言， 其特征选取为颜色信息、 轮 廓信息、 几何形状信息；
♦ 运动连续性： ={ζ,, } ; 其中， ζ,是当前时刻 t运动马尔科夫可信度， 包括 了位置、 速度和加速度的连续性描述； 是当前时刻 t基于运动信息为目标 O的概率。
♦ 特征连续性： G={^ r,} ; 其中/ ^是当前时刻 t特征马尔科夫可信度， 也即当 前特征在整个特征迹中的相容性， 例如， 人走动的视频序列， 由于人相应于摄像机 的方位变化， 其图像特征也会变化， 但其变化是连续的， 满足马尔可夫特性。 是当 前时刻 t基于特征信息为目标 O的概率。
♦ 目标整体可信度 ν,; 它给出了特征迹在此时此地表征某一目标的概 率。 特征迹 Signature^, t)中的等效状态序列的产生使用的是对位置、 速度和加速度 的曲线拟合方法。 拟合可以是高阶非线性， 原则上可以适合任意运动模型。 因此， 我们没有在 SDT中引入多模型。
2 由特征迹定义邻域
准确地定义邻域是降低跟踪方法中假设数目的 关键。 在设置门限确定邻域时， 我们将目标运动的马尔可夫性表述到运动模式 中： 1)加速度的马尔可夫性对应于当 前加速度运动模式或匀加速度 （CA)运动模式； 2)速度的马尔可夫性对应于当前速 度运动模式或匀速（CV )模式。应用特征迹中运动特性设定邻域， 同时考虑了位置、 速度和加速度的马尔可夫性。
目标在运动时， 其特征迹具有马尔科夫特性。 前后帧之间， 同一目标的特征相 同或相似， 其运动变化趋势相同或相近。 例如， 对于人群的视频跟踪而言， 人在走 动时， 由于人相应于摄像机的方位不断变化， 其图像特征也会变化， 但其变化是连 续的， 满足马尔可夫特性。 我们设定邻域， 既考虑运动的连续性， 也考虑特征的连 续性。
假设从谱域、 空域和时域提取出的较高层次的某时刻的特征 数据为 ， 位置数 据为 。 此时， 不妨将数据写为 2 ' = {^,； 。
给定 O在时刻 t-1的等效状态 ξΜ， 对传感器系统时刻 t的观测数据， 其运动连续性 邻域 (^设定为： G, = (3)
S由系统模型 MOC^CM)和观测模型 g,( c,)导出，运动的马尔科夫特性也体现在系 统动态模型/的选取中， 为与 Gk相应的阔值。
对于特征; /， 可以选取与之对应的相似度函数 ί ， 使之取值在 0-1之间。 取值越 大， 两特征越相似。 又以 表示特征变化趋势评估函数， 取值也在 0-1之间。 取值越 大， 表明从特征序列 E,到；/变化趋势的相容度越高。 对时刻 t的观测数据， 首先应用 目标和杂波特征的不同， 将杂波从观测数据中分离出去。 对于剩下的观测数据， 将 之与已有特征迹进行关联。 给定特征迹 0 ， 相应的特征连续性邻域记为 <¾·。
G F = { z ' = { ∑P ^} - c F {η |^-, ) · κ (η |^_！ )≥s F ] (4) 最终的邻域 G为运动连续性邻域 和特征连续性邻域 (^之交：
3 特征迹的生成和管理
如图 4示出特征迹树的生成示意图， 确定特征迹邻域之后， 假定在时刻 t， 存在 一个观测 z 没有落入任何现有特征迹的邻域之内， 那么， 它有可能是一个新目标的 起点。 将之设定为起点， 生成一个 t时刻的特征迹， 不妨记之为 o， 其对应目标的出 现时刻为 s=t。
在 +l时刻， 确定 t时刻的特征迹 0 的邻域， 求得落入 t时刻的特征迹 0 邻域内的观 测集为 {^, +1 ，…， β , +1 }， 那么将 t时刻的特征迹 0分别与这/ w。个观测及漏检做关联， 生 成 。+l个新的特征迹， 记之为 ，产 0,l,... , m。， 其中 (^由 t时刻特征迹 0 与漏检相关联 所生成， o/ =l，...， W )由 t时刻的特征迹 0 与^ +1 观测相关联所生成； 它们与 t时刻特征迹 o对应同一个目标； 由此， t时刻特征迹 0 生成了新的/ «。+1个特征迹。 在 t+2时刻进行 同样操作。
这样， 我们就生成了一个特征迹树结构， 如图 4。 按照定义， 树中自根节点的每 一条路经， 对应于一个可能的数据关联序列， 也即可能的特征迹。 但为了航迹起始 与终结操作的方便， 如果特征迹时间达到了 N个采样间隔， 即 t-s+l=N， 进行剪枝与 合并操作： 删除整体可信度 V,比较低特征迹； 如果几个特征迹等效状态序列之差小 于某个门限， 那么将之合并。 在剪枝合并操作后， 如果该树己有特征迹得到确认， 那么从该树中抽取整体可信度最高的特征迹作 为该树的输出： 将根节点送入滤波器 估计目标的状态， 并将滤波结果送入航迹集中， 以便航迹维持和管理。 树的新根节 点下移一个时间点， 保持特征迹时间长度为1^。
为表述方便， 下文一律采用以下表述方式： 给定 t-1时刻生成的特征迹树结构 Θ， V,./}, 在当前时刻， 即/时 刻， 落入 0邻域内的观测集合为 ζ ={ /=ι，...，/«。}， 这 。个观测和漏检分别与 0 相关联 后， -0, l,...,m 0 ,而落入树 Θ的观测集合为：
Z, e =|JZ ( 0 ={z;,/ = l,---,m} (6)
4特征迹马尔科夫可信度
对于特征¾0， 我们首先确定其运动马尔科夫可信度 ς和特征马尔科夫可信度/,。 目标的运动具有其连续性， 也即马尔科夫性。 当前时刻的目标位置、 速度和加 速度都与前一时刻或相当长时间的相关。 在考虑马尔可夫可信度时， 不仅要考虑前 一时刻状态对当前时刻的影响， 也要考虑特征迹内整个等效状态序列的影响。 由此， 我们定义运动马尔可夫可信度
= Ρ{ξ,, | -> ) ) (7) 其中， ^(m)为前一时刻等效状态 ,到当前时刻等效状态^的转移特性， 其取值越大， 表明两状态相关性越高； ^ ^")表征当前时刻等效状态 与整 个特征迹等效状态序列 z M 的相容性，这涉及到状态转移变化趋势的 一致性、运动模 型转换的协调性等， 其取值越大， 表明^ ,与等效状态序列 /^的相容度越高。
相邻时间点特征之间的变化可能因运动、环境 等而起，这一变化也具有连续性。 也就是说， 同一个目标的前后点的特征是相似的， 特征的变化趋势也是相近的。 同 样， 我们将特征马尔可夫可信度 定义为目标特征;^在该特征迹的特征序列 - /内 的整体相容性， 这涉及到 ^与 的相似度， 以及其与 . /的变化趋势的相容性：
t ) ( 8 ) 其中， ^(/^Ι;^,)为前一时刻特征迹; 7,—,到当前时刻特征迹 的转移特性， c K ( lt j )表征当前时刻特征迹 77, 与整个特征迹 的相容性。
5 特征迹的整体可信度和特征迹的确认和删除
给定一个特征迹，我们使用特征迹整体可信度 v,，应用航迹起始与终结原则对之 进行确认和删除判断， 应用航迹起始与终结原则为公知技术在此不再 赘述。
给定前一时刻即 t- 其中 ,( -j为 t-1时刻的权重系数， ω .Λ+α^,^^
那么， 当前时刻即 t时亥 ijo的整体可信度 -c^Ay+co/^, ,其中 (¾,,,o ^为 t时刻的 权重系数，
通过如下方式计算。
给定运动马尔科夫可信度
(9) 那么 0的运动信息关联似然比 PlJ 为
P,
(10) l-P Dr_
,7 = 0
1―
其中 P D 是目标检测概率， 9为虚警密度。 从而有
给定特征连续性刻画函数
(12) 那么 的特征信息关联似 比为
从而有 整合以上各式可以求得 o/的整体可信度
给定特征迹确认门限 / c和删除门限 Ρττ， 贝叶斯确认和删除决策逻辑为
Delete
Ρ ΊΤ <ν, . < Ρ π , Further Investigation (15)
TC .Confirm 式中， P^ = (16)
p
Ρττ - τ^- (17)
\ -a p 其中， 《 为假航迹接受概率 (false acceptance probability), ^为真航迹拒绝概率 (t e rejection probability)。
在一棵树中， 如果全部特征迹被删除， 则目标航迹到此终止。 如果有多于一个 的特征迹被确认， 则保留整体可信度最大的特征迹。
二、 实验与性能评估
为了验证 SDT有效性， 我们分别使用仿真方法和视频跟踪试验将它与 MHT方法 进行对比实验。 MHT方法采取了 Cox的程序 （ I. J. Cox and S. L. An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1996)2, 138-150. ) 和改进算法实现的。
1 点目标跟踪仿真实验
近年来有影响的仿真和性能评估方案在文献中 并不多见。 我们提出了一个对自 动检测跟踪 (Automatic Detection and Tracking, ADT)系统进行仿真和性能评估的方 案。 仿真测试框架包括两个部分， 即密集高机动性目标仿真和监测雷达 (surveillance radar)的观测仿真， 以及在此仿真环境下多目标跟踪算法的性能评 价准绳。
1.1 目标轨迹仿真
对于仿真评估而言， 跟踪场景的真实与合理性至关重要。 美国海军表面作战中 心 Dahlgren分部 (Naval Surface Warfare Center Dahlgren Division)的 W. D. Blair与 Connecticut大学的 Y. Bar-Shalom ( W.D. Blair, G. A. Watson, T. Kirubarajan, and Y. Bar-Shalom. Benchmark for radar allocation and tracking in ecm. IEEE. TRANS. AES, 34(4): 1097-1114, 1998. ) 等人提出了一个雷达调度与跟踪的评估基准 (benchmark), 用于评价和比较不同算法对机动目标的跟踪性 能。 然而这一基准给出的六组仿真场 景都只包括一个轨迹指定的三维点目标。 为了对多目标跟踪算法进行评估， 需要设 计合理的多目标场景， 每个场景中应包括多至上百个机动目标， 每个目标的轨迹可 以相当复杂。 为此， 我们参考了 Florida大学 Anil V. Rao等的工作 （ Anil V. Rao, David Benson, Geoffrey T. Huntington, Camila Francolin, and Michael Patterson. Users Manual for GPOPS Version 2.2: A MATLAB Package for Dynamic Optimization Using the Gauss Pseudospectral Method. University of Florida, et al.， Gainesville, FL.， February 2009. ), 应用"航迹优化"方法生成目标轨迹， 其主要思想是： 目标动力学方程已知时， 若给 出一对初始和终止目标状态， 则唯一的最短时间航迹可以通过数值计算得出 。 这一 追求最短时间路径的思想与多数实际情况是相 符的。 飞行器可以用三维空间中的点 目标建模表示， 其初始与终止状态对可以在一定限制区域内随 机产生， 这样就可以 用上述方法生成任意多个目标轨迹。 由于目标起止状态的随机性， 其航迹具有较强 的机动性； 又因为目标运动受到动力学方程组约束， 数值计算给出的航迹具有物理 上的合理性。
1.2 雷达仿真
对目标检测的仿真采用航空监测雷达 (air-surveillance radar) (Merrill I. Skolnik. Introduction to Radar Systems. McGraw-Hill, third edition, 2001. The de-facto radar introduction bible. )模型。 雷达检测数据仿真的流程是： 对于每一个在探测范围的目 标， 首先计算其雷达截面 （RCS ) 的一个样值， 进而求出信噪比 （SNR) 和检测概 率 P D ， 以此决定该目标在此时刻是否被检测到。 如果被检测到， 则计算测量的标准 偏差， 并根据高斯分布模型给出有噪测量值。 雷达测量过程在球面坐标系中完成， 后将测量值和测量方差矩阵转换到直角坐标系 中。 雷达测量场景中的杂波 (clutter)建 模为均匀分布于监测区域内的无起伏的离散点 杂波，其 RCS在 10 2 到 10 6 平方米之间随 机取值。 每次扫描中杂波的出现被视作泊松过程。
1.3 算法性能评价指标
多目标跟踪算法的评估应综合考虑其航迹初始 化、 数据关联以及滤波等方面的 性能。 对于监测雷达构成的自动检测跟踪系统的算法 评价方面， 加拿大和美国曾合 作建立一个雷达数据库， 记录了对六架 F-18战斗机 30分钟内的雷达观测数据， 用来 支持多目标跟踪的研究。加拿大 Calgary大学的 Henry Leung(H. Leung, Zhijian Hu, and M. Blanchette. Evaluation of multiple radar target trackers in stressful environments. IEEE. TRANS. AES, 35(2):663-^74, 1999. )等人基于这个数据库做过具有启发性的工 作， 并制订了一系列跟踪性能指标， 我们取其中关键的 6个指标：
N r -. 跟踪算法给出的目标航迹中， 真航迹的数目。 所谓的 "真航迹"中至少应有
50%的观测值与目标间实现了正确关联。
跟踪算法给出的目标航迹中， 假航迹的数目。 所有非真航迹均为假航迹。 真航迹的平均持续时间。 目标的一条真实轨迹可能由于中间的某些观测 点 丢失而被跟踪算法拆分为两条或多条航迹， 出现 ^大于目标个数的情况。 因此， 在 同样的跟踪场景下， 真航迹的持续时间应该越长越好。
假航迹的平均持续时间。
平均每一条真航迹关联的目标个数。 由于难以避免的数据关联错误， 跟踪 算法给出的一条航迹可能由来自多个不同目标 的观测值组成。 理想情况下一条真航 迹关联的目标个数为 1。 实际上在复杂的场景中 往往会大于 1。
平均每一条真航迹的误关联率。误关联率是指 跟踪算法给出的一条航迹中 错误关联的测量值数目与本航迹包含的所有测 量值数目之比。 在理想的无差错数据 关联情况下， ， 等于 \， ^等于 0。
1.4 仿真实验 1
在本实验中， 假定雷达位于直角坐标系的原点， 监视区域 X坐标范围是 [35km, 55km], y坐标范围是〖35km, 55km]。 目标飞行高度范围是 1000~5000m， 速度变化范 围是 100-500m/s， 加速度变化范围是 0~9g。 本次试验， 对 10个仿真目标进行跟踪。 图 5是目标轨迹和虚警数据。 图 5中的实线为真实航迹， 点为雷达观测。
图 6 (a) 是现有技术 MHT跟踪结果； 虚线为真实航迹， 实线为估计航迹， 图 6 (b) 是本发明 SDT跟踪结果， 虚线为真实航迹， 实线为估计航迹； 实验结果表明， 图 6 (b) 中有更多的实现与虚线重合， 说明 SDT方法在本次试验中取得了更好的跟 踪效果。
我们对这 10个目标进行了 100次蒙特卡洛仿真实验，并根据上文中提出的 性能指 标， 对 SDT算法和 MHT方法做评估， 得到结果如表 1。
表 1 : 在同一场景下对 10个目标进行 100次仿真的平均结果
从真假航迹数目的角度来看，这两种算法的输 出航迹，真航迹数目都达到了 50% 的数量要求。 SDT给出的真实航迹数目比 MHT输出高出 14.16%。 从真实航迹的平均 持续时间来看， SDT输出的真实航迹时间， 要比 MHT的高 51.6%。虽然 SDT假航迹数 略高 （0.11对 0.08 )， 但从虚假航迹的平均持续时间来看， SDT输出的虚假航迹时间 要比 MHT的输出结果少 44.44%。 因此， SDT算法对同一目标的持续跟踪能力远好于 MHT算法 (好 51.6%)， SDT的数据关联能力也要优于 MHT。
从跟踪准确性来看， SDT算法输出位置估计的均方根误差（RMSE ) , 要比 MHT 算法低 71.41 %, SDT的速度估计 RMSE, 要比 MHT算法的低 48.13%。 SDT算法对位 置和速度估计的准确性要远高于 MHT算法。
综合上述实验结果， 在发现目标、 持续跟踪目标、 数据关联和估计准确性等方 面， SDT算法都要优于 MHT算法。
2 视频跟踪实验
图 7 ( a)、 图 7 (b)示出为了进行视频跟踪的试验， 我们利用摄像机视频对鱼缸 中的热带鱼进行跟踪。 鱼缸大小为 (90cmx60cmx50cm)， 摄像机分辨率为 1280x720 像素， 釆样率为 30Fps。 被跟踪的是身长为 2-3cm的热带鱼， 其运动活跃、 动作迅速。 鱼的颜色为黄色和橙色。 为了复杂化跟踪场景， 我们向鱼缸中加入了与鱼形态相似 的纸片， 作为杂波和干扰。
我们使用目标颜色直方图建立无参密度估计， 并加入边缘检测量来建立目标的 特征度量。 原始图像的颜色为 256位色的 RGB颜色空间。 为了表达目标模型， 我们将 目标区域内的颜色进行统计建模。将每个子空 间 R、 G、 B分成 16个相等区域， 每个 区间称为一个 bin, 构成特征空间， 因此共有 m=16 3 个特征数。 在本此研究中， 我们 取 8x8的像素框作为样本， 这刚好是鱼头部的大小。设目标区域中心为 ， 假设其中 有 n个象素， 用 "表示， 特征值 bin的个数为 m。 则目标模型特征值 u=l ...m估计 的概率密度为 ( Francesc Moreno, Adri、a Tarrida, Juan Andrade-Cetto and Alberto Sanfeliu, 3D Real-Time Head Tracking Fusing Color Histograms and Stereovision, Int Conf. on Computer Vision and Pattern Recognition, 2002. )： , = C^ (|| ^HI 2 顺 在本次试验中， 我们选取 系数为目标特征相似性函数， 其定义为： 对于每一帧图像， 我们采用基于边缘检测的图像分割方法来检测 可能的目标， 也称前景分割。 由于光照的明暗变化、 水面的扰动等因素均会很大地影响目标的颜 色特征， 我们设计了一种自适应门限算法， 将不断变化的杂波和目标区分开来。
整个视频跟踪的流程共分成新目标检测和原有 目标跟踪两个部分。 对新目标进 行检测时， 先对当前帧图像进行前景分割， 得到可能是目标的区域。 然后根据上一 帧得到的目标位置预测， 得到该帧新增加目标的位置。 最后利用预先得到的目标特 征模板对新目标候选区域进行搜索， 得到新目标检测位置， 同时初始化目标门限等 参数。 在对原有目标进行跟踪时， 我们在上一帧预测得到的位置附近进行搜索， 并 对每个目标检测门限作自适应更新。 最后将所有检测到的目标结果合并， 输入后端 的数据关联和跟踪模块进行处理。 图 7 (a) MHT热带鱼跟踪之第 69帧， 图 7 (b) SDT 热带鱼跟踪之第 69帧；
表 2、 SDT和 MHT对热带鱼进行视频跟踪的统计结果
13 100 100 100.00% 91 91.00%
14 100 88 88.00% 80 80.00%
15 64 30 46.88% 29 45.31%
16 59 59 100.00% 50 84.75%
17 83 83 100.00% 83 100.00%
18 39 39 100.00% 38 97.44%
19 21 21 100.00% 20 95.24% 合计 1566 1484 94.76% 1380 88.12% 图 7 (a)、 图 7 (b)示出 MHT和 SDT对热带鱼视频跟踪结果之第 69帧。 每个目标 都标有航迹。 由图可见， MHT有不少误判， 将纸片当作鱼。 真航迹寿命也短。 为了 统计跟踪结果， 对 100帧（581— 680) 图像进行人工核对， 两种方法的跟踪结果如表 2。 SDT的正确跟踪概率为 94.76%, MHT的正确跟踪概率为 88.12%。
图 8示出相交目标跟踪效果， SDT方法在相交目标的跟踪上， 体现了其融合时间 域、 频率域和空间域信息的优越性。 如图 8所示（左)， 两条鱼正相向游动； （中)一段 时间后， 两条鱼相遇； （右)两鱼分开后， SDT跟踪算法仍然能有效地跟踪各自的游动 轨迹。
三、 结论
本文提出了一种崭新的"特征迹驱动的多目标 踪方法"（SDT)。 它从多目标检 测和跟踪的物理基础出发， 从根本上提出一动态目标有别于干扰和其它目 标的度量 - "特征迹"， 并给出了在谱、 空间和时间域使用目标的物理特性和运动特性 融合测 量数据生成特征迹， 计算基于运动马尔可夫可信度、 特征马尔可夫可信度以及检测 概率和虚警密度的特征迹整体可信度的方法。 使用特征迹及其可信度， SDT在第一 时间去除噪声， 大大提高了数据关联的可靠性， 使得跟踪结果中真航迹概率增加、 寿命加长。 由于进入滤波器的是确认后的特征迹数据， 使得跟踪结果的精度大大提 高。 实验结果表明， 特征迹驱动的多目标跟踪方法在性能上远优于 目前公认为最佳 的多假设跟踪 （MHT) 方法。
SDT方法一开始就利用特征迹去除噪声和干扰， 大大简化了算法的复杂度。 由 于 MHT算法有很多简化算法， 需要进行认真调査才能确定其最新的计算复杂 度。 因 此， 本文没有对两种方法的复杂度进行定量比较。
以上所述， 仅为本发明中的具体实施方式， 但本发明的保护范围并不局限于此， 任何熟悉该技术的人在本发明所揭露的技术范 围内， 可理解想到的变换或替换， 都 应涵盖在本发明的包含范围之内， 因此， 本发明的保护范围应该以权利要求书的保 护范围为准。
Next Patent: HYDRAULIC ROCK DRILLING MACHINE FOR EXCAVATOR