多假设跟踪(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)
其中， mk表示接收量测数据数目；
表示第i个量测数据;
表示漏检的伪量测。航迹定义为如下的量测序列：
(2)
其中，
表示第i条航迹在第j(j∈{1，2，…，k})时刻的量测数据。
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)
其中， xk表示第k时刻的目标状态向量; z1∶k表示直到第k时刻的量测数据；
表示第k时刻第j个模型； M表示模型总数。
2) 模型预测：
(4)
其中，
表示第k时刻第j个模型的模型概率。
3) 模型更新：
(5)
需要说明的是，模型的详细实现过程见文献[18]。
2.2 航迹得分
TOMHT根据当前的航迹节点生成关联假设，并通过评分来判别航迹和假设的可信度。航迹得分定义为真实目标假设和虚警假设的对数似然比[2，19]。航迹
在第k时刻的航迹得分可递归求解如下：
(6)
其中，得分增量
定义为：
(7)
式中： PG表示波门判决概率;
表示量测
源于航迹
的似然密度函数，对于IMM算法来说，满足如下的高斯混合形式：
(8)
其中，
表示航迹第m个模型的预测概率；
表示量测源于航迹的第m个模型的似然分布，服从高斯分布：
其中，
和
分别表示航迹的第m个模型的预测量测及其协方差矩阵。对于新生航迹，其初始化得分为[19]
(9)
其中，λN表示新生目标的空间密度。航迹的状态通过概率序列比检验(Sequential Probability Ratio Test，SPRT)[2]确定。具体来所，SPRT通过将航迹得分与预先设置的删除门限Tl和确认门限Tu进行对比进而判断航迹的状态。门限参数Tl和Tu的设置见文献[2]。
全局假设的分值定义为其包含的相容航迹的得分之和：
因此，第k时刻第i个全局假设
的概率求解如下：
(10)
其中， J表示全局假设的数目。
2.3 全局假设生成
本节介绍如何利用MWIS生成最优全局假设。一个加权无向图G=(V,E,W)的MWIS定义为具有最大权重和的独立集，其中独立集定义为任意两个顶点均无边连接的顶点子集。由文献[12]可知，在第k时刻，若将G中的顶点vi∈V定义为航迹节点
顶点vi的权重wi∈W定义为航迹得分
同时对于不相容的航迹与
对应的顶点vi与vj用边(i， j)∈E相连，那么最优假设生成问题转化为MWIS问题，表述为
(11)
其中，
是一个二值变量表示第i条航迹是否包含于最优解中。需要说明的是： 式(11)中的优化问题是NP-难问题，学术界通常采用近似方法求解，如GRASP法[13]、Tabu搜索法[14]和信息传递法[20]等； MWIS问题等价于其补图上的最大加权团(Maximum Weighted Clique，MWC)问题，因此MWC问题的求解方法亦可应用于本方法中。
图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]。
3) 航迹剪枝。航迹剪枝也是一项降低计算复杂度的技巧。在TOMHT中，航迹剪枝包含两类：全局级航迹剪枝和N-帧剪枝。全局级航迹剪枝(亦称航迹级剪枝)通过利用航迹的全局概率进行航迹删除[7]。航迹的全局概率定义为
(12)
其中，
表示全局假设的概率，由式(10)给出。此外，目标的运动信息，如目标运动的速度范围亦可用于航迹剪枝。N-帧剪枝应用于限制航迹树的规模。假设航迹树的最大深度为N，N-帧剪枝对航迹树分枝深度超过N的航迹树进行剪枝处理，以确定k-N+1时刻的数据关联问题。N-帧剪枝仅保留最优的全局关联假设所在的分枝。以图2为例，假设航迹树的最大深度为N=2，则根据图2(b)中的最优假设结果可以确定k时刻的剪枝结果见图3。由图3可知，航迹树1的T3和T4以及航迹树2的T7被删除，k-2时刻的关联决策已确定。
图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次蒙特卡罗仿真结果
跟踪方法NTNfRMCRpRvOSPATEMWIS-CV-MHT17.220.060.05878.2039.30186.080.25MWIS-CA-MHT16.800.260.06560.7328.9497.860.21MWIS-Singer-MHT18.200.240.07661.5531.70113.390.22MWIS-IMM-MHT16.240.160.06055.9425.7585.630.39
4 结论
提出了一种多假设跟踪方法。将交互式多模型算法引入，采用多种运动模型对机动目标进行跟踪，该方法能兼顾计算效率上的优势。仿真结果表明：相比于单模型方法，多假设跟踪方法能提升跟踪的连续性和状态估计的精度，更适用于多机动目标跟踪问题。
[1] BLACKMAN S.Multiple Hypothesis Tracking for Multiple Target Tracking[J].IEEE Aerospace and Electronic Systems Magazine，2004，19(1)：5-18.
[2] BLACKMAN S，POPOLI R.Design and Analysis of Modern Tracking Systems[M].Artech House，1999.
[3] REID D.An Algorithm for Tracking Multiple Targets[J].IEEE Transactions on Automatic Control，1979，24(6)：843-854.
[4] SINHA A，DING Z，KIRUBARAJAN T，et al.Track Quality Based Multitarget Tracking Approach for Global Nearest-Neighbor Association[J].IEEE Transactions on Aerospace and Electronic Systems，2012，48(2)：1179-1191.
[5] BAR-SHALOM Y，TSE E.Tracking in a Cluttered Environment with Probabilistic Data Association[J].Automatica，1975(11)：451-460.
[6] CHANG K C，BAR-SHALOM Y.Joint Probabilistic Data Association for Multitarget Tracking with Possibly Unresolved Measurements and Maneuvers[J].IEEE Transactions on Automatic Control，1984，29(7)：584-594.
[7] BLACKMAN S S.Multiple-Target Tracking with Radar Applications[M].Dedham MA USA：Artech House，1986.
[8] KIM C，LI F，CIPTADI A，et al.Multiple Hypothesis Tracking Revisited[C]//Proceedings of the IEEE International Conference on Computer Vision，2015：4696-4704.
[9] SHENG H，CHEN J，ZHANG Y，et al.Iterative Multiple Hypothesis Tracking with Tracklet-Level Association[J].IEEE Transactions on Circuits and Systems for Video Technology，2019，29(12)：3660-3662.
[10] COX I J，HINGORANI S L.An Efficient Implementation of Reid’s Multiple Hypotheses Tracking Algorithm and Its Evaluation for the Purposes of Visual Tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1996，18(2)：138-150.
[11] KURIEN T.Issues in the Design of Practical Multitarget Tracking Algorithms，In Y.Bar-Shalom (Ed)，Multitarget-Multisensor Tracking：Advanced Applications，Ch.3，Norwood：MA：Artech House，1990.
[12] PAPAGEORGIOU D，MICHAEL S：The Maximum Weight Independent Set Problem for Data Association in Multiple Hypothesis Tracking[M].Inoptimization and Cooperative Control Strategies Berlin，Germany：Springer，2009：235-255.
[13] REN X，LUO T，HUANG Z，et al.An Efficient Mht Implementation Using Grasp[J].IEEE Transactions on Aerospace and Electronic Systems，2014，50(1)：86-102.
[14] HE S，SHIN H S，TSOURDOS A.Track-Oriented Multiple Hypothesis Tracking Based on Tabu Search and Gibbs Sampling[J].IEEE Sensors Journal，2018，18(1)：328-340.
[15] VO B N，MALLICK M，BAR-SHALOM Y，et al.：Multitarget Tracking[M].In Wiley Encyclopedia of Electrical and Electronics Engineering：Wiley，2015：1-23.
[16] 李洋，杜立夫，禹春梅.一种基于复合模型的机动目标跟踪算法[J].四川兵工学报，2015，36(5)：127-132.
[17] BLOM H，BAR-SHALOM Y.The Interacting Multiple Model Algorithm for Systems with Markovian Switching Coefficients[J].IEEE Transactions on Automatic Control，1988，33(8)：780-783.
[18] LOPEZ R，DANES P.Low-Complexity Imm Smoothing for Jump Markov Nonlinear Systems[J].IEEE Transactions on Aerospace and Electronic Systems，2017，53(3)：1261-1272.
[19] BAR-SHALOM Y，BLACKMAN S S，FITZGERALD R J.Dimensionless Score Function for Multiple Hypothesis Tracking[J].IEEE Transactions on Aerospace and Electronic Systems，2007，43(1)：392-400.
[20] SANGHAVI S，SHAH D，WILLSKY A S.Message Passing for Maximum Weight Independent Set[J].IEEE Transactions on Information Theory，2009，55(11)：4822-4834.
[21] LI X R，JILKOV V P.Survey of Maneuveringtarget Tracking.Part I：Dynamic Models[J].IEEE Transactions on Aerospace and Electronic Systems，2003，39(4)：1333-1364.
[22] LI X R，ZHANG Y，ZHI X.Multiple-Model Estimation with Variable Structure Part Iv：Design and Evaluation of Model-Croup Switching Algorithm[J].IEEE Transactions on Aerospace and Electronic Systems，1999，35(1)：242-254.