基于联合概率数据互联的多假设跟踪算法

闫 龙，王曙曜，黄 磊，姚 远

(中国船舶集团有限公司第八研究院，南京 211153)

0 引 言

多假设跟踪(Multiple Hypothesis Tracking，MHT)算法采用延迟决策逻辑，通过不断产生多种可能的假设，利用未来接收到的量测来帮助解决当前量测与航迹之间的关联问题。该算法提供了一个将航迹起始、航迹维持以及航迹终结等功能统一的多目标跟踪框架。在检测概率比较低、杂波和目标密集的跟踪环境下，MHT算法被认为是目前具有最优关联性能的数据关联算法。[1]Reid首先提出了面向假设的多假设跟踪(Hypothesis-Oriented MHT，HOMHT)算法，Cox等给出了面向假设的MHT的一种高效率实现方案，并提出了一种面向航迹的多假设跟踪(Track-Oriented MHT，TOMHT)方法[2]。目前，国外针对MHT算法的理论研究较为成熟，提出了许多改进的算法及快速实现的方法。国内高校也开展了针对MHT算法的研究，形成了一些著作和论文，并形成了相关的软件产品。

随着软硬件技术的发展和电磁环境的复杂化，应用MHT算法提高杂波环境中多目标跟踪性能的呼声越来越高。据此，本文提出了基于JPDA的TOMHT算法，采用预测波门连通分组的方法对多目标进行航迹分簇处理，采用序贯概率比检验(SPRT)、N-Scan剪枝法和K-Best全局最优法进行假设管理，对于簇内可能存在的不相容航迹树进行JPDA联合概率分配来保证不相容航迹树的互斥性，对杂波环境下的多目标稳定跟踪具有较大改善。目前，该算法已应用于舰载某三坐标预警雷达系统中，取得了较好的效果。

1 TOMHT算法

1.1 TOMHT算法处理框架

MHT算法的具体实现方案可分为HOMHT算法和TOMHT算法两种。HOMHT算法是一种自顶向下的方法，其在接收到量测时先产生多个全局假设，并计算出这些假设的概率，然后据此计算每条航迹的概率。而TOMHT算法是一种自下向上的方法，其在接收到量测时首先对现有航迹树进行更新，之后再根据更新后的航迹树形成全局假设。虽然两者在原理上十分接近，但由于目前TOMHT算法的实现更为简单、高效，所以TOMHT算法应用更为广泛。图 1给出了TOMHT算法的流程图。

图1 TOMHT算法流程图

1.2 航迹形成与维持

当接收到新的量测时，TOMHT算法对现有的航迹进行各种可能的量测-航迹关联，增长现有的航迹树，起始新的航迹树。针对每一个落入已有假设航迹关联门内的量测，将对应假设航迹分叉形成一棵具有相同量测根结点的航迹树，同时为每一个假设航迹赋予一个确认概率，其描述了当前假设航迹为真实目标航迹的概率。TOMHT中的假设航迹数量会随时间指数增长。因此，为限制TOMHT算法的计算复杂度，需要对假设航迹进行管理，及时删除虚假航迹。

1.3 基于得分的航迹剪枝

采用序贯概率比检验法(Sequential Probability Ratio Test，SPRT)对航迹进行管理。SPRT将最新时刻所有航迹的航迹得分与两个阈值比较，如果航迹得分大于确认阈值则确认该航迹，如果小于删除阈值则删除该航迹。

(1)

ηd=ln(β/(1-α))

(2)

ηc=ln((1-β)/α)

(3)

其中，ηd为删除门限；ηc为确认门限；α为虚假航迹的确认概率，也被成为第1类错误概率；β为正确航迹的删除概率，也被成为第2类错误概率。

1.4 分 簇

簇是指包含所有直接或间接共享相同量测的假设航迹的集合。从簇的定义可以看出，不同簇内的航迹总是相容的。因此，所有航迹的全局假设可以通过对不同簇中得到的全局假设进行组合而得到。这样相当于将整个航迹集分成了若干个子集，以使全局假设的生成能够在每个子集中独立完成，从而降低算法的计算量。以n个航迹为例，由于全局假设生成算法的计算量约为n3，如果能够把所有航迹分为10个等量簇，即每个簇中包含n/10个航迹，那么整个算法的计算量约为10×(n/10)3=n3/100，计算量为不分簇时计算量的1/100。

1.5 假设形成与剪枝

剪枝是一种有效限制假设航迹数量的方法，具体操作是根据之前得到的最优全局假设，确定航迹树根结点的关联情况，同时删除航迹树根结点的其他分支。航迹树剪枝过程如图 2所示。

图2 航迹树剪枝

图2中TOMHT算法的延迟深度N为3，假定全局最优假设为包含航迹树叶子结点11的航迹。由于航迹树T深度超出延迟深度3，所以航迹树T将只保留右边包含存在于最优全局假设的航迹分支，由此确认结点3所代表的量测将与假设航迹相关联。由于该操作将确认延迟深度N时刻之前航迹与量测的关联关系，因此通常也被称为N回扫剪枝。

1.6 基于全局假设的航迹剪枝

完成N回扫剪枝之后，为进一步减少假设航迹的数量，基于假设形成与剪枝中求出的前k个最优全局假设对航迹进行进一步地删除，基本思想是几乎没有出现在前k个最优全局假设中的航迹很大可能不是真实的目标航迹。

1.7 航迹更新

若在N时刻航迹与量测关联，则使用交互多模型(Interacting Multiple Model，IMM)滤波算法对航迹的状态进行滤波更新，若不存在关联量测则对航迹的状态进行外推更新。

1.8 航迹输出

最后，根据航迹得分实时输出处于已确认状态的最佳航迹信息。

2 基于JPDA的点航迹关联方法

2.1 传统JPDA算法

杂波环境下的多目标数据互联技术是多目标跟踪中最重要又是最难处理的问题。联合概率数据互联(Joint Probabilistic Data Association，JPDA)是解决这一问题的一种良好的算法。JPDA的目的就是计算每一个量测与其可能的各种源目标相互关联的概率，回波落入不同目标相关波门的重叠区域内时则必须综合考虑各个目标量测的目标来源情况。为了表示有效回波和各航迹跟踪波门的复杂关系，JPDA引入了确认矩阵的概念。[3]

(4)

其中，ωjt是二进制变量，ωjt=1表示量测j落入航迹t的确认门内，而ωjt=0表示量测j没有落入航迹t的确认内。t=0表示没有航迹，此时对应的列元素ωj0全都是1，因为每一个量测都可能源于杂波或者是虚警。

对于一个给定的多目标航迹跟踪问题，在建立了有效回波与航迹或杂波互联关系的确认矩阵后，就可以通过对确认矩阵的拆分得到所有表示互联事件的互联矩阵，在对确认矩阵进行拆分时必须依据以下的两个基本假设：

(1) 每一个量测有唯一的源，即任一量测不源于某一个目标则必源于杂波，即该量测为虚警；

(2) 对于一个给定目标，最多有一个量测以其为源。如果一个目标有可能与多个量测相匹配，将取一个为真，其他为假。

依据上述的两个假设来实现由确认矩阵到互联矩阵的拆分：

(1) 在确认矩阵的每一行，选出一个且仅选出一个1作为互联矩阵在该行唯一非零的元素；

(2) 在可行矩阵中，除第一行外，每列最多只能有一个非零元素，即满足第2个假设。

双目标航迹不存在虚假点迹时点航迹JPDA算法关联过程如图 3所示。落入目标航迹1关联波门内的有2个点迹，落入目标航迹2关联波门内的有1个点迹。JPDA算法建立一个航迹和点迹的确认矩阵。该矩阵维数为2×3，2表示量测的个数，3表示的是航迹数目加1。由建立的确认矩阵可以拆分为5个互联事件，每一个互联事件代表了一种点迹航迹的分配关系，经过计算选择其中概率最大的作为点迹航迹的分配依据。

图3 JPDA点航迹关联过程示意图

2.2 基于JPDA的TOMHT算法

传统TOMHT算法在航迹形成与维持的过程中簇内航迹与检测波门内量测点迹均产生航迹分支。这样会导致航迹树过于庞大，后期处理中滤波、剪枝及管理会造成计算量指数倍增，同时会产生航迹树间分支合并的问题。

针对传统TOMHT算法的上述问题，结合JPDA算法的优点，本文提出基于JPDA的TOMHT算法，主要进行以下改进：

(1) 在TOMHT跟踪框架的基础上引入JPDA算法参与点航迹分配。通过遍历各航迹分支的预测波门，将预测波门存在重叠区域的航迹分为同一簇，同时将簇内所有预测波门区域的并集作为该簇的检测波门。这样，对簇内不相容航迹分支和簇检测波门内量测点迹进行联合概率数据互联分配，达到保证不相容航迹树的互斥性的目的，降低航迹树分簇时对叶节点的搜索工作量，提高量测点迹和簇内航迹树间假设航迹的关联正确率和实时性，避免出现树间分支合并的问题。

(2) 在航迹维持的基础上计算航迹得分，若航迹得分处于下降通道则对该航迹分支进行扩大波门检测相关点迹，若检测到相关点迹则根据相关点迹进行滤波产生航迹分支，若未检测到相关点迹则进行航迹外推产生航迹分支。

3 仿真与试验

3.1 杂波背景下密集目标的跟踪效果

仿真场景中有3个运动的目标，目标运动状态为匀速直线，起始距离35 km，速度280 m/s，航向225°，高度50 m，目标间隔约750 m。目标量测点迹误差为距离误差30 m，方位误差0.2°，仰角误差0.2°，扫描周期2 s，探测概率为0.9。杂波点迹分布为5 km×5 km×1 km的空间里3个杂波点迹。仿真目标运动轨迹如图 4所示。

图4 3批密集目标运动轨迹

对同一仿真数据，分别采用本文提出的基于JPDA的TOMHT算法和JPDA算法进行跟踪，滤波方法采用IMM算法。两种方法在关联波门的设置，滤波器参数方面完全一致，跟踪结果分别如图 5和图 6所示。

图5 基于JPDA的TOMHT算法对3批密集目标的跟踪效果

图6 JPDA算法对3批密集目标的跟踪效果

针对密集目标的跟踪效果对比表明，在无杂波仿真条件下，本文提出的基于JPDA的TOMHT算法和JPDA算法相差无几。在杂波仿真条件下，本文提出的基于JPDA的TOMHT算法相比于JPDA算法具有明显的优势。

3.2 杂波背景下随机多批目标的跟踪效果

仿真场景中有20个运动的目标，目标运动状态分为非机动和机动。

非机动目标方位在0°～360°随机产生，距离在10～100 km随机产生，速度在50～280 m/s随机产生，航向在0°～360°随机产生，高度在100 ～15 000 m随机产生。非机动样式分为匀速直线、匀速切向、匀速径向。

机动目标方位在0°～360°随机产生，距离在10～100 km随机产生，速度在50 ～280 m/s随机产生，航向在0°～360°随机产生，高度在100～15 000 m随机产生。机动样式分为转弯、加减速，机动程度在1、3、5、10 g随机产生。

目标量测点迹误差为距离误差30 m，方位误差0.2°，仰角误差0.2°，扫描周期2 s，探测概率为0.9。杂波点迹分布为5 km×5 km×1 km的空间里3个杂波点迹。

本文提出的基于JPDA的TOMHT算法和JPDA算法对杂波环境下对20批随机目标的跟踪效果分别如图7和图8所示。

图7 基于JPDA的TOMHT算法对20批随机

图8 JPDA算法对20批随机目标的跟踪效果

跟踪效果对比表明，在杂波较复杂的场景下，针对不同机动程度、不同机动方式、不同速度的典型机动目标以及非机动目标，本文提出的基于JPDA的TOMHT算法比JPDA算法对目标的跟踪航迹更完整连贯平滑，穿杂波能力更强，具有明显优势。另外，由于保证不相容航迹树的互斥性，避免了同一簇内互斥航迹分支关联同一量测点迹，导致航迹树分支数量倍增及后期合并等问题，降低航迹树分簇时对叶节点的搜索工作量，基于JPDA的TOMHT算法比传统MHT算法的实时性更强，更适合复杂杂波环境下密集目标的跟踪。

3.3 基于仿真目标的跟踪性能定量评估

本文设计了下列4种指标用于算法性能定量评估。一般来说，在进行算法比较时总是从指标集中选择若干作为评估准绳。

(1) 漏情率

对于一个真实目标，如果在某一扫描时刻没有真航迹对应于该真实目标，则称该真实目标在该时刻的信息被漏掉，否则该真实目标在该时刻的信息没有被漏掉。一个真实目标的漏情率为其被漏掉的扫描时刻数和总扫描时刻数的比值。规定一个算法的漏情率为仿真场景中所有真实目标的漏情率的平均值。

(2) 真航迹的平均误关联率

所有真航迹中误关联的量测点数目与真航迹寿命之和的比值。在理想的数据关联无差错的情况下，误关联率等于0。误关联率反映了数据关联的质量，显然误关联率越小越好。

(3) 目标量测的正确关联率

正确关联到相应真航迹的量测占所有来自真实目标的量测的比率。这个变量反映出跟踪算法对真实目标量测的利用率，也是评价数据关联质量的指标之一。

(4) 位置估计的均方根误差

对所有算法给出的真航迹，计算它们与对应的目标航迹真值的位置RMSE。

对杂波背景下随机20批目标的跟踪性能进行定量评估，通过50次蒙特卡罗仿真试验，统计对20批目标跟踪的各项指标均值，结果见表1。

表1 跟踪性能指标计算结果

4 结束语

基于MHT算法的杂波环境下多目标跟踪是当前研究的热点。本文在研究传统JPDA算法和MHT算法的基础上提出一种基于JPDA的TOMHT算法，将JPDA模型引入TOMHT跟踪框架作为杂波环境密集目标场景下航迹跟踪树间关联互斥的方法，采用预测波门连通分组的方法进行航迹分簇处理。对于簇内可能存在的不相容航迹树进行JPDA联合概率分配来保证不相容航迹树的互斥性。通过仿真试验，定性定量比较了基于JPDA的TOMHT算法和JPDA算法对杂波环境下多目标的跟踪性能。结果表明，基于JPDA的TOMHT算法在正确关联率和滤波精度上均存在明显优势，对杂波环境下对多目标跟踪具有一定适应性和有效性。