一种机动目标多假设跟踪方法

胡 敏，邱金凤，许 红，李荣锋

(1 航天南湖电子信息技术股份有限公司， 湖北 荆州 434000；2.海军工程大学电子工程学院， 武汉 430033)

多假设跟踪(Multiple Hypothesis Tracking，MHT)[1-3]采用一种延迟判决逻辑，通过建立和传播多个候选假设，由后续的量测数据来解决当前时刻的数据关联问题。由于利用了多个时刻的量测信息，理论上MHT的性能优于传统的全局最近邻(Global Nearest Neighbor，GNN)[4]、概率数据关联(Probability Data Association，PDA)[5]和联合数据关联(Joint Probability Data Association，JPDA)[6]，因而被广泛应用于各种多目标跟踪(Multiple Target Tracking，MTT)场景[7-9]。

MHT方法最早由Reid[3]于1979年提出，该方法面向量测构造关联假设，通过枚举可行的全局假设，并计算假设的概率来给出最优的量测关联结果。因此，该方法实质上是基于假设的MHT方法(Hypothesis-oriented MHT，HOMHT)。然而，在复杂跟踪场景中，枚举可行的全局假设是一个NP-难问题，因此文献[3]中HOMHT方法难以实际应用。文献[10]通过利用Murty 算法来生成假设，避免了枚举操作，减低了HOMHT的计算复杂度。文献[11]提出了面向航迹的MHT方法(Track-oriented MHT，TOMHT)，该方法是一种“自上而下”的方法，其通过更新的航迹节点来生成全局假设，避免了维持和传播假设。相比于HOMHT，TOMHT的计算复杂度和实现难度更低，因而，在MTT领域多采用TOMHT方法[1]。

本文基于TOMHT方法开展研究，TOMHT的难点在于最优全局假设的生成。针对该问题，基于图论的TOMHT方法近年来倍受关注。文献[12]指出最优假设生成问题等价于最大权重独立集(Maximum Weighted IndependentSet，MWIS)问题。为了引用方便，本文将传统的基于(Multi-dimensional Assignment，MDA)和基于MWIS的MHT方法分别简记为MDA-MHT和MWIS-MHT。与MDA-MHT相比，MWIS-MHT具备如下优势[12-14]：MWIS-MHT在概念上更加简洁明了；MWIS是一个经典的组合优化问题已被广泛研究，因此利用现有的MWIS求解算法可更加高效的求解全局假设。需要说明的是，现有的MWIS-MHT方法的运动模型均为单一模型，在目标机动场景下，会存在性能损失，并不适合于多机动目标场景。

针对现有的MWIS-MHT方法并不适用于多机动目标跟踪的问题，本文将交互式多模型(IMM)算法应用于MWIS-MHT，提出了基于交互式多模型的MWIS-MHT方法。所提方法采用多种运动模型对机动目标进行跟踪，因而更适用于多机动目标跟踪场景。此外，相比于MDA-MHT，所提方法基于MWIS生成最优假设，具有更低的计算复杂度。仿真实验验证了所提算法的有效性。

1 MHT问题描述

MHT通过建立多个候选假设并通过假设评估及管理技术来实现多目标跟踪。为了便于后文描述算法原理，本文将MHT中常用的术语总结于表1，其中部分术语定义借鉴于文献[15]。

表1 MHT常用术语定义

MHT考虑量测数据可能源于新生目标、虚警或已有航迹。为了便于描述算法，MHT方法有如下假设：传感器的检测概率为PD；虚警和新目标分别服从空间密度为λF和λN的泊松分布；一个目标在不漏检条件下仅能产生一个量测。

此外，为了便于后文描述算法，本节给出量测数据和航迹的定义。假设第k时刻传感器接收的量测数据定义为

(1)

(2)

2 所提方法原理与实现

本节将IMM算法引入到MWIS-MHT框架中，提出了适用于机动目标的多假设跟踪方法。为了行文方便，本文将所提方法简记MWIS-IMM-MHT，其原理框图如图1。

图1 MWIS-IMM-MHT方法原理框图

下面对MWIS-IMM-MHT的关键实现步骤进行详细论述。

2.1 IMM算法原理

机动目标跟踪一直是目标跟踪领域的研究热点，其难点在于目标运动的不确定性[16]。IMM算法[17]通过引入模型交互步骤，具有1 阶广义伪贝叶斯(Generalized Pseudo Bayesian，GPB)算法的计算复杂度优势，同时兼备2 阶GPB 算法的跟踪性能，实现了跟踪精度与算法复杂度的折中。因此，IMM算法被广泛应用于各类机动目标跟踪问题。在给定的跳变线性马尔科夫状态空间模型[17]的基础上，IMM算法包含如下步骤：

1) 模型交互：

(3)

2) 模型预测：

(4)

3) 模型更新：

(5)

需要说明的是，模型的详细实现过程见文献[18]。

2.2 航迹得分

(6)

(7)

(8)

(9)

其中，λN表示新生目标的空间密度。航迹的状态通过概率序列比检验(Sequential Probability Ratio Test，SPRT)[2]确定。具体来所，SPRT通过将航迹得分与预先设置的删除门限Tl和确认门限Tu进行对比进而判断航迹的状态。门限参数Tl和Tu的设置见文献[2]。

(10)

其中，J表示全局假设的数目。

2.3 全局假设生成

(11)

图2给出了MWIS生成最优全局假设。

图2 MWIS生成最优全局假设示意图

图2(a)给出了从t=k-2时刻至t=k时刻的3株航迹树的示意图，图中的圆代表了航迹节点，圆中的数字表示量测数据序列号，定义见式。一株航迹树由根节点、分支和叶节点构成，图2(a)中在第k时刻总共包含了8条航迹，其航迹标签为{T1，…，T8}。图2(b)给出了3株航迹树在第k时刻对应的加权无向图的示意图，图中的圆代表了第k时刻航迹节点，圆中的数字表示航迹标签，圆外的数字表示航迹得分，连接边由航迹的相容关系确定。图2(b)中的蓝色航迹节点{T2，T5，T8}为MWIS生成最优全局假设。

2.4 方法实现的几个技巧

为了确保MWIS-IMM-MHT方法的性能及执行效率，本文考虑如下技巧：

1) 运动模型集设置。运动模型集直接影响了IMM算法的性能。运动模型集设置可以根据跟踪场景中的机动目标运动特点的先验知识[21]进行设计，也可通过更为精细的方法如最小模型距离法、矩匹配法和基于优化的方法等。

2) 航迹聚类。航迹聚类将所有的航迹节点分解为多个无共享量测的子簇，进而将复杂关联问题分解为诸多小规模的关联问题。由于子簇间并无共享量测，因此子簇的关联问题可并行求解。图2(a)中的3株航迹树可分为两个子簇，其中航迹树1和航迹树2为一个子簇，航迹树3为第二个子簇。一种高效的航迹聚类方法可参考文献[11]。

(12)

图3 N-帧剪枝示意图(N=2)

3 仿真实验

本节通过仿真实验验证MWIS-IMM-MHT方法对机动多目标的跟踪性能，并与现有的MWIS-MHT[12]方法进行对比。

3.1 仿真场景设置

仿真实验考虑2维空间中的多机动目标，目标的加速度矢量a(t)=a(t)∠θ(t)满足半-马尔科夫过程[22]。简而言之，在随机驻留一段时间后，加速度的大小a(t)和相位θ(t)由某一状态跳变至另一状态。半-马尔科夫过程的完整数学模型参考文献[22]中的式(8)至式(14)。仿真试验中，目标的初始加速度大小设置为0，初始相位在区间[-π，π]内随机分布，加速度的参数设置与文献[22]一致。仿真实验的其他参数设置如下：目标数目N=15，目标检测概率PD=0.95，虚警空间密度λF=1×10-8，采样时间T=2 s，观测时间TK=200 s，X轴与Y轴的量测误差标准差相同，其标准差σX=σY=50 m。图4给出了一组随机生成的真实目标轨迹的仿真场景。为了能够生成具有挑战性的多目标航迹，仿真实验将目标航迹的起始和终点中心点均设置为原点。

图4 仿真场景示意图

MWIS-IMM-MHT方法的运动模型集设置为：匀速(Constant Velocity，CV)模型、匀加速(Constant Acceleration，CA)模型和Singer模型，模型的先验概率为[1/3 1/3 1/3]，马尔科夫模型转移概率矩阵为

(13)

模型参数设置如下：CV模型的过程噪声方差设置为δCV=10；CA模型的过程噪声方差设置为δCA=1；Singer模型的机动时间常数τ=10 s，最大加速度aM=40 m/s2。航迹树的最大深度设置为N=5；MWIS问题采用Tabu搜索法求解，其中最大搜索深度设置为L=10，最大迭代次数设置为nmax=50；新生目标空间密度λN=1×10-8。SPRT的参数设置为：虚假航迹确认概率α=10-6；真实航迹检测概率β=10-3。本文将采用CV模型、CA模型和Singer模型的MWIS-MHT分别简记为MWIS-CV-MHT、MWIS-CA-MHT和MWIS-Singer-MHT，其过程噪声方差参数设置如下：MWIS-CV-MHT中的过程噪声方差设置为δCV=400，MWIS-CA-MHT的过程噪声方差设置为δCA=10，MWIS-Singer-MHT中的最大加速度设置为aM=80 m/s2。需要说明的是，单模型MWIS-MHT的过程噪声取值更大的目的是为了扩大跟踪器的适用范围。

为了能够评估算法的关联性能、估计精度和运行效率，本文借鉴文献[13-14]中的评估指标，采用如下指标：

1) 真实航迹数目NT。真航迹定义为由跟踪算法给出的航迹中至少有50% 的量测来自同一个目标。该指标主要评估关联的正确性及航迹的连续性。

2) 虚假航迹数目Nf。不满足真航迹定义的航迹。该指标主要评估关联的正确性。

3) 航迹的误关联率RMC。所有真航迹中误关联的量测点数目与真航迹长度之和的比值。显然RMC越小越好，理想条件下RMC=0。该指标主要评估关联的正确性。

4) 位置均方根误差Rp。根据算法估计的目标位置与真实航迹的目标位置计算位置的均方根误差。该指标主要评估算法的位置估计精度。

5) 速度均方根误差Rv。根据算法估计的目标速度和真实航迹的目标速度计算速度均方根误差。

6) (Optimal Subparrern Assignment，OSPA)距离。OSPA距离是用来衡量集合之间差异程度的距离度量，可综合评估目标的状态估计精度及目标数目估计的准确性。

7) 运行时间TE。TE定义为算法处理一帧数据的机器运行平均时间。该指标主要评估算法的执行效率。

3.2 实验结果与分析

图5给出了图4场景中MWIS-CV-MHT和MWIS-IMM-MHT方法的跟踪轨迹和OSPA曲线。由于现有的MWIS-MHT轨迹均是基于CV模型的，因此图5仅仅给出了MWIS-CV-MHT轨迹。图5(a)和图5(b)中的绿色点表示量测点迹(包含虚警和真实目标)，蓝色轨迹为目标真实轨迹，红色轨迹为跟踪算法输出的轨迹。由图5(a)和图5(b)可知：MWIS-CV-MHT轨迹出现了航迹中断问题，而MWIS-IMM-MHT跟踪航迹连续稳定。由图5(c)可知：初始时刻MWIS-CV-MHT轨迹和MWIS-IMM-MHT轨迹的OSPA曲线相当，这是由于仿真实验的初始运动均为匀速运动，而当目标机动后，MWIS-CV-MHT的OSPA曲线显著高于MWIS-IMM-MHT轨迹。这是由于MWIS-CV-MHT曲线采用了较大方差的过程噪声，因此滤波器的去噪能力显著下降，同时航迹中断也会引起OSPA曲线抬升。

表2给出了100次蒙特卡罗仿真实验的统计结果。由表可知，MWIS-IMM-MHT的NT与真实目标数目15最为接近，这表明了所提方法在跟踪连续性方面具备最优性能。从跟踪精度来看，MWIS-IMM-MHT的位置均方根误差和速度均方根误差最小，因而具有最优的状态估计精度。从关联性能来看，MWIS-IMM-MHT并非最优，但其性能也优于MWIS-CA-MHT和MWIS-Singer-MHT。从运行效率来看，MWIS-IMM-MHT的单帧处理时间约为现有方法的两倍，计算复杂度并没有显著增加。

图5 跟踪轨迹和OSPA曲线

表2 100次蒙特卡罗仿真结果

4 结论

提出了一种多假设跟踪方法。将交互式多模型算法引入，采用多种运动模型对机动目标进行跟踪，该方法能兼顾计算效率上的优势。仿真结果表明：相比于单模型方法，多假设跟踪方法能提升跟踪的连续性和状态估计的精度，更适用于多机动目标跟踪问题。