多假设追踪Multiple Hypothesis Tracking这个名字我初次接触的时候第一反应是“这玩意是不是那种只在论文里活着、工程上根本没人敢碰的算法”。说实话这种印象不算全错——MHT在很长一段时间里确实被视为多目标追踪领域“理论上最优、实现上劝退”的典型代表。但后来我在实际项目里被SORT、DeepSORT这类“贪心策略”连续坑了几次才下定决心认真啃MHT。这篇文章就是想把MHT从论文语言翻译成工程语言用我自己的理解方式拆开讲清楚它的核心思想是什么、为什么它会被称为“最优”但又“难搞”以及你在实际落地时到底在哪些环节会真正感受到它和其他算法的区别。无论你是做自动驾驶感知、体育赛事分析、视频监控还是研究多智能体系统只要你的场景里存在“多个目标 相互遮挡 短暂消失 数据噪声”MHT就是你绕不开的一条技术路线。这篇讲解不会堆公式到让人放弃但该给的关键推导和数据结构我也会给到位重点放在“为什么这样设计”和“工程上怎么实现”这两块。1. 多目标追踪真正的难点不在“追踪”而在“认人”1.1 你以为是连续追踪其实是反复做“数据关联”很多人刚接触多目标追踪时会误以为这个问题是这样的我检测到目标了我给它做一个轨迹然后下一帧我继续在这个轨迹上更新位置就行。听起来很丝滑对吧但真实场景里这个“继续更新”的动作恰恰是整个问题的核心难点。因为你的传感器——无论是摄像头、毫米波雷达还是激光雷达——每一帧给到你的只是一堆“非连续的点观测值”。这些观测值本身没有身份它们只是一个个独立的量测比如目标的位置坐标、目标的置信度向量而你并不知道这一帧的点A和上一帧的点B到底是不是同一个目标。把每个观测值和它对应的历史轨迹正确配对起来这个环节就是“数据关联”。如果你只追踪一个目标这问题很简单全场景就一个点我直接关联就行。可是当画面里同时有十几个人、几辆车或者雷达回波里出现大量虚警点时“这一帧的哪个点属于哪条轨迹”就立刻变成组合爆炸级别的复杂问题。我打个比方你现在站在一个广场中央周围有成群的人在走动。每过一秒钟你闭一次眼睁开后你要判断——刚才站在你左边的那位现在是哪一位如果人少、运动慢你一眼就能认出来如果人多、衣着相似、相互穿插而过你可能瞬间就懵了。多目标追踪算法干的活就是替你做这个瞬间判断。1.2 贪心策略和最优策略的分水岭业界最常见的追踪框架比如SORT和DeepSORT一系它们在数据关联这一环采用的是“贪心匹配”的思路。什么叫贪心就是只看当前时刻做一个局部最优的决定我把这一帧的观测值和已有轨迹算一个代价矩阵然后用匈牙利算法或者直接最大二分匹配找到一个当前代价最小的匹配方案。一旦匹配上了就认为这件事“定了”不会再回头更改。这种方案的优点是显而易见的快、简单、稳定工程上非常好落地。但它有一个没有解决的问题——如果当前的匹配决策本身是错误的呢举个具体场景视频监控里一个人被另一个人遮挡了整整五秒。等他重新出现在画面中时你已有的轨迹和他现在的观测值之间的位置跳变非常大极有可能你会认为这是一个“新目标”于是新建了一条轨迹。而那个被他遮挡住的人他的轨迹因为在连续几帧里没有关联到任何观测值会被标记为“丢失”然后提前终止。与此同时你追踪到的“新目标”其实还是同一个人——但你已经在管理层上把它当成两个不同的ID了。这就是业界常说的“ID Switch”即同一目标被错误地分配了多个身份编号。贪心策略之所以在遮挡、交叉、密集场景中容易出现这类问题本质原因是它在每个时刻就只留一条被子——一旦这步选错后面所有帧都会基于错误前提继续更新。MHT要做的就是改变这个“定了就不回头”的假设。1.3 MHT给出的方案先不急着做决定MHT的全称是Multiple Hypothesis Tracking翻译过来是“多假设追踪”。它的核心思想如果用一句话总结就是既然我一时刻无法确定正确关联那我就把所有可能的关联方式都保留下来让数据在后续帧中慢慢“说话”最后才收敛出最具说服力的那一条轨迹。听起来很像是人在做选择时会用的办法。你去商场找人看到背影和同事很像但不确定。正常人不会立刻上去拍肩膀而是先跟着走两步近距离观察走姿、衣服细节、侧脸轮廓再最终确定“就是他”或者“不是他”。你不会在第一时间就做绝不回头的决定你会保留几种可能性观察一段再下结论。MHT正是这种“保留多种可能性”策略的机器实现。每一帧它对现有的每个轨迹结合当前观测数据构造若干条候选的关联假设。这些假设可能会让轨迹A关联到观测点1也可能让轨迹A关联到观测点2还可能让轨迹A认为观测点1是一个新目标的起始点。所有这些可能性都被保留下来各自形成一条新的轨迹假设分支。然后呢数据一帧帧累积有些假设的预测位置和真实观测越来越吻合得分持续升高有些假设则在连续几帧中都找不到支持它的观测值得分逐渐下滑最终被丢弃。打分制胜这就成了MHT最后的决策机制。2. 从直觉到实现MHT的四个核心模块2.1 假设生成把“所有可能性”枚举出来任何基于“多假设”的算法第一步一定是把一个“模糊的关联局面”拆解成若干“明确的关联候选”。这个拆解过程在MHT里叫做假设生成Hypothesis Generation。假设你现在有两帧数据。上一帧你已经有两条轨迹轨迹T1和轨迹T2。当前帧你检测到三个点观测值O1、O2、O3。那么这一帧的数据关联问题就变成了一个类似“每个轨迹要么关联一个观测值、要么暂时不关联每个观测值要么属于某个轨迹、要么属于新目标或虚警”的分配问题。我在实际做工程实现的时候第一步会用距离门限Gating把明显没戏的配对先排除掉。比如T1的预测位置在坐标(10,20)而O3出现在(300,200)两者之间距离远超过合理的运动范围那这组“T1-O3”关联就可以直接丢掉。这一步是纯粹的几何过滤可以帮助你把一个巨大的关联矩阵缩小成稀疏的候选集合。为什么需要这个步骤因为MHT最怕的就是把所有可能的组合全部枚举出来——那是指数爆炸级别的。如果当前帧有N条轨迹、M个观测值即便是简单的无约束分配组合数也会迅速膨胀到天文数字。如果在每一帧都做全量枚举算法根本无法实时运行。工程上MHT的可用性很大程度上取决于Gating的质量和灵活性。在我构建假设树的时候我用的框架是这样的每个节点代表一条轨迹在当前时刻的一个关联状态而一条完整轨迹的“历史”就是一棵从根节点到当前节点的路径。这个路径上记录的是这个假设在每一帧拿哪个观测值去更新轨迹的滤波器状态。树的规模就是所有可能的关联历史集合。这套结构的空间复杂度确实是MHT的软肋。我早期自己写代码时一段时间内没有控制假设树深度结果跑了不到两分钟内存直接爆炸到数十GB。后面才老老实实加上“最大假设树深度”这个限制参数比如只保留最近5帧的分支更早的历史认为已经定型不再分支。2.2 轨迹得分如何判断“这条假设活得对不对”多条假设都保留了但总不能一直让它们平行生长得有办法判断谁更“可信”。这个可信度在MHT里用“轨迹得分”Track Score来表达。我先说我的实现认知不一定和教科书上的公式完全一一对应但逻辑是一致的。每一条轨迹假设都有一个得分这个得分会随着每一帧的处理而更新。更新的规则是这样的当这条假设成功关联到一个观测值时它的得分会增加当这条假设没有任何观测值支持时它的得分则会被扣减。为什么这样设计因为你每拿到一个“支持证据”你对自己当前判断正确性的信心就应上升。这个思想其实和人类做决策的贝叶斯推断过程高度吻合。如果你把“观测值O出现了”看作对“轨迹是T1”这条假设的一个证据支持那么证据越多、越吻合假设的后验概率自然就越大。MHT的得分公式基础就来自这个朴素原理。具体操作上我常用的一套得分更新公式是这样的令当前轨迹假设的分数为Score_old当它关联到观测值z时更新分数为Score_old加上一个“关联收益”这个收益通常是该观测值对应目标的似然对数。如果这一帧没有任何观测值进入该轨迹那么Score_new等于Score_old减去一个“惩罚系数”。这个惩罚系数平时我会调成一个常数用于表征“目标暂时丢失”对假设可信度的削弱程度。这里有一个参数设计的微妙问题如果“关联收益”太大那算法会变得激进任何微弱证据都会让某条分支得分飙升最后可能过早收敛到错误的假设反过来如果“惩罚系数”过大那么轨迹只要在遮挡中断了一两帧得分就会被迅速扣到底导致正确轨迹被过早丢弃。实际调参下来我觉得这个“收益与惩罚的平衡”是整个MHT系统里最具艺术性的一部分我在后面调参章节会具体展开。这类比的感受是一条轨迹假设就像你养的一个手下的情绪账户你每派它完成一个任务关联到一个观测点情绪就涨每让它空等一轮没有找到观测点情绪就跌。但是你得小心别让情绪涨得太疯或跌得太狠否则判断就会失真。2.3 全局假设管理为什么需要“互斥条件”刚才说的是单条轨迹的得分但MHT还有一个关键机制——全局假设管理Global HypothesisManagement。这个设计的出发点很简单一条轨迹假设说“我是正确的因为我有高分”这还不够因为你还需要保证这些假设之间没有冲突。举个例子当前帧观测到3个点但不同轨迹的假设中可能存在“轨迹T1关联观测O1”和“轨迹T2关联观测O1”这样完全冲突的情形——同一个观测点不可能同时属于两条轨迹。如果放任这种冲突最终收敛出来的结果就是荒唐的。所以MHT维护的不是一棵假设树而是一整个“全局假设集合”。一个全局假设就是一组互不冲突的单条轨迹假设它们中间没有任何两条使用同一个观测值。这个全局假设的得分通常是它内部所有被采纳的轨迹假设得分的总和。那么每一帧要做的就是从当地所有可用的轨迹假设中挑出一组互不冲突的子集这个子集的得分总和最大。听上去是不是很耳熟对这本质上就是一个带权的最大独立集问题。当节点数是几百这个量级时你可以直接用经典的枚举加剪枝求解但一旦到了上千条假设就必须用近似解法。我在项目里实际尝试过几种逼近方式。一是把这个问题转换成整数线性规划ILP问题用现成的求解器去算精度高但慢。二是用贪心加局部搜索的办法先取一个效果还不错的可行解然后通过5到10轮局部扰动优化不求全局最优但只要结果足够好就行。三是我现在用得最顺手的做法给全局假设排序留一个“容忍窗口”——不要只保留得分最高的那个全局假设也保留排名第二、第三的候选假设把取舍延迟到更后续的帧里。这种“保留Top-K全局假设”的做法在工程上几乎是MHT实时化的核心手段。2.4 假设剪枝控制增长的生命线如果你完完整整把每个帧的“所有可能性”都保留下来那么假设树的规模会呈指数级增长。第五帧可能是十几个分支第十帧就可能到几百第二十帧直接爆掉。这时候就必须要执行“剪枝”Pruning。剪枝目标很简单把那些已经没有前途的假设分支去掉。怎么判断“没有前途”我主要会看这几个标准第一刚才提到的轨迹得分是否低于某个阈值。比如我常见的设置是把基线得分设为0只要一条假设的得分是严重负数它就是负资产直接丢弃。第二看这棵树的深度。如果某条分支连续若干帧都没有关联到观测值而且其得分在快速下降十有八九是目标真实丢失了这条分支留着只会干扰全局假设管理。第三也是我后期才悟到的限制每个父节点下的子节点数量。你不要天真地以为明确了Gating就能把候选分支控制在很小的范围内当你做的是密集人群扫描时目标数量多观测值也多候选对可能依然异常庞大。我会在代码里加一个“每父节点最大子分支数”的参数超过上限之后只保留得分最高的那部分。这种近似的代价是损失部分最优性但换来的可运行性可以说是天壤之别。还有一种是“协同剪枝”目的在于保持全局假设集合的一致性。你可能会遇到这样的情况某条轨迹假设单独看得分不错但它和当前最高分的全局假设产生了冲突比如它占用了那个全局假设里另一条轨迹必需的观测点。那为了保障最优全局假设的完整性我必须在剪枝阶段把它提前淘汰掉。这个步骤像打球时的战术配合——我不仅看你这名球员个人能力还要看你在这个阵型里能否和其他队友共存。3. 把MHT从理论放到代码我的一步步落地经验3.1 一帧一帧拆开MHT的完整处理流水线这里我想把MHT的完整计算流程用伪代码的形式写出来。因为只有把这套架构理顺了你后面写代码时才不会迷茫。输入当前帧观测值集合 Z {z1, z2, ..., zm} 输入现有轨迹假设集合 T {t1, t2, ..., tn} 输出最新全局假设 G_best # Step 1: 预测 for track in T: track_filter.predict() # 卡尔曼滤波先预测目标下一时刻位置 # Step 2: 门限过滤Gating candidate_pairs [] for track in T: for obs in Z: if gate_test(track, obs): # 计算欧氏距离/马氏距离是否小于门限 candidate_pairs.append((track, obs)) # Step 3: 生成新的轨迹假设集 new_hypotheses [] for pair in candidate_pairs: new_track deepcopy(track) new_track.update(obs) # 用当前观测值更新滤波器状态 new_track.score log_likelihood(pair) new_hypotheses.append(new_track) # 没配对到任何观测的目标标记为“丢失”进行惩罚 for track in T: if track not in candidate_pairs: lost_track deepcopy(track) lost_track.score - penalty new_hypotheses.append(lost_track) # 没配对到任何轨迹的观测生成新目标初始轨迹 for obs in Z: if obs not in candidate_pairs_observation: new_born create_track(obs) new_born.score birth_score new_hypotheses.append(new_born) # Step 4: 全局假设管理 G extract_global_hypotheses(new_hypotheses) # 通过“最大加权独立集”求解 G_best choose_best_global(G) # Step 5: 剪枝 prune_hypotheses(new_hypotheses)这个流程看着并不算特别复杂对吧但真正的复杂度藏在各个Step的实现细节里。就拿Step 3来说deepcopy一条轨迹假设——如果轨迹状态是卡尔曼滤波里的均值向量加协方差矩阵那拷贝还便宜但如果每条轨迹附带了一整棵特征历史队列例如ReID的外观特征序列那拷贝起来就是开销巨大的操作。我在第一版实现里天真地用了全量深拷贝结果发现每帧耗时随轨迹数量的增加呈指数级增长。后来优化成了“写时复制”Copy-on-Write即在新的假设生成时只保留和旧轨迹不同的部分公共历史部分用共享引用速度直接提升了一个量级。这个问题如果不做优化再好的算法也只是纸面文章。3.2 卡尔曼滤波之外观测模型与似然计算说完了流程框架我们来拆一个看起来很不起眼、但实际上对效果影响极大的点观测模型的似然计算。MHT里轨迹得分恰恰由这个似然数值来决定如果你的似然函数是拍脑袋写的那么所有假设分支的排序都是不准确的。最常见的做法是用卡尔曼滤波的预测结果来构造一个高斯似然函数。假设当前轨迹的状态分布是一个高斯分布有均值μ和协方差矩阵Σ那么一个观测值z对该轨迹的“似然”就是这个高斯分布在z点处的概率密度值。具体计算时因为会把分数映射到对数域进行所以最后得到的是一个负的二次型结果。数学化的表达是这样的假设观测值是z轨迹的预测位置是μ从状态空间到观测空间的观测矩阵是H那么z和μ之间的“残差”innovation为y z - Hμ其对应的协方差矩阵为S H P H^T R其中P是滤波器状态协方差R是观测噪声协方差。那么马氏距离d y^T S^{-1} y。这个d越小说明观测值和轨迹预测之间越吻合似然值越高。这里我踩过一个坑最开始我图省事直接用欧氏距离来做门限过滤和似然计算。在目标静止或者运动较为平缓的场景里结果差异不算大。但我一旦把算法迁移到车辆高速运动的数据集上目标移动速度飞快位置分布的真实不确定性已经拉成了一个细长的“椭圆”此时用各向同性的欧氏距离来衡量“是否匹配”结果就非常糟糕。后面我全线换成马氏距离预测协方差矩阵会在每一帧根据运动模型自动调整方向和大小整个系统的精度才稳定下来。所以这里我的建议是在你的框架里任何涉及“距离计算”的地方优先使用基于马氏距离的高斯似然而不要停留在欧氏距离。尤其当你的目标运动模型带明显的加速度或转向机动时这个差异会被无限放大。3.3 代码骨架与数据结构设计思路写MHT代码的时候数据分析结构设计比算法主逻辑更影响整体实现效率。我分享下我目前比较偏好的一套结构设计轨迹类至少要包含三个字段状态估计对象里面存放卡尔曼滤波器均值向量和协方差矩阵得分浮点数记录当前轨迹假设的累积得分生命状态标记轨迹当前是“活跃”、“暂时丢失”还是“已消亡”。此外为了支持后续的ReID或者通知外观信息一个可选的“观测历史队列”也值得预留着。这个队列不用太长保留最近10帧的特征向量就足够应对多数遮挡恢复的场景。全局假设类的设计同样重要。我会维护一个观测索引到轨迹索引的字典确保每一条全局假设内部的关联不冲突。全局假设还应包含一个成员得分总和方便在“选择最优全局假设”时直接排序。树的表示方式我用的是“虚拟树”的思路每个轨迹节点指向其父节点但父节点数据并不物理拷贝到子节点里。子节点只保存增量信息例如关联到的观测值索引、本帧得分增量。要回溯整条轨迹历史时从当前节点一路向父节点走即可。这种指针式结构会比节点物理拷贝的做法节省很多内存也方便后期剪枝——只要调整引用计数就能比较轻量地摘下无用分支。3.4 逐步反馈在代码里跑通“多假设”的第一步如果你现在准备自己动手实现一个最小的MHT系统我建议第一步千万别贪多求全。你可以先固定目标数量不超过5个简化运动模型去掉外观特征只依赖位置信息来做关联。这一步的核心目标是把“假设生成-假设管理-剪枝”这条主链路跑通。我当初的最低实现思路是这样的状态向量只包含位置和速度观测值只有位置坐标运动模型是恒定速度模型门限过滤用简化的马氏距离全局假设用最大加权二分匹配——先不考虑多目标的最优全局分配只做局部配对加剪枝。跑通这一版之后再逐步引入“观测值可以属于新目标”、引入“轨迹未关联观测则丢失”等机制让假设空间真正“多”起来。这一过程让我意识到一个规律MHT的复杂度上涨并不是线性的而是呈跳变的。当你允许的假设空间到达某个阈值时时间复杂度突然高到算法卡顿。这种时候不要急于调大剪枝力度先检查代码里是否有无谓的对象拷贝和索引重复计算。很多时候时间复杂度的爆炸是“低效的数据结构 过深的拷贝链”叠加出来的而不是MHT本身的复杂度造成的。4. 别把MHT玩成传说也别忘了它的“边界”4.1 为什么说MHT“在实际场景里并不总是最优”MHT在理论上被视为多目标追踪的“金标准”几乎所有其他追踪算法在对比精度时都会拿它作为参照。但“理论上最优”和“实际中必须用”之间还隔着几座大山。第一个大山是实时性。MHT的假设空间在高密度场景下增长极快即使加了种种剪枝策略你依然要面临“为了让系统实时跑最优性打了折扣”的处境。这种「理论最优性衰减」是所有在真实系统里用过MHT的工程师必然面对的妥协。第二个大山是参数敏感性。这个算法的效果极大依赖于门限阈值、惩罚系数、生成新目标的置信度、剪枝频率等一系列参数。我曾在同一个算法架构下换了一个数据集原先调好的参数就必须重新标定否则追踪的ID Switch会飙升到无法接受的程度。MHT不是一把“一键调好”的利器它更像一把需要你经常保养的瑞士军刀。第三个大山是在线学习能力不足。MHT基于的是“先有模型再关联数据”的思路——它假设你对目标的运动模型、观测噪声方差有一定的先验了解。但如果你遇到的是一类全新场景目标运动特征和你预设模型严重不符MHT的滤波器预测就会系统性地偏离真实位置导致门限过滤把正确的关联对提前丢掉了。而类似基于学习的关联算法如基于图神经网络的数据关联方法能够在大量标注数据中自动提取关联模式抗模型失配的能力更强。4.2 对比其他关联算法为什么JPDA没有MHT“翻盘”能力在讲MHT时有一个经常被放在一起对比的算法叫做JPDA——联合概率数据关联Joint Probabilistic Data Association。JPDA的核心思路是对每个轨迹把该帧所有观测值按“属于某轨迹”的概率进行加权融合最终用加权平均来更新轨迹状态。它不等同于选择某个单一关联对而是做一个概率上的“软分配”。JPDA和MHT的核心差异在于对“不确定性”解决方案的不同JPDA把不确定性直接“平均化”了用加权的方式顺滑地消化掉关联模糊MHT则把不确定性“保留”了她同时维护多个可能的关联历史最后用新证据逐步消歧。这意味着当出现严重的轨迹交叉或者遮挡时JPDA的模糊处理常常会把目标位置拉向“中间地带”——本来两条轨迹应该一个走左边、一个走右边但JPDA在模糊期间会把两轨迹都推向画面中央等模糊解除后你会发现它们的估计位置已经明显偏移了。MHT因为保留了“轨迹A走左边、轨迹B走右边”的多种假设后期可以随着观测值的出现让正确的假设胜出从而把位置误差控制得更小。这是我的切身体会如果你的场景目标密度不高目标运动稳定JPDA那套“平均化”的做法非常管用简单、快、稳但如果目标常常遮挡、轨迹互相交叉JPDA的位置偏移会积累成为硬伤而MHT虽然实时性差些但至少不会严重“跑偏”。所以我的项目里通常是这样取舍的低密度场景优先JPDA或SORT系高密度、强互扰的场景就直接上MHT密度再高就考虑分层、分块来缓解MHT的复杂度。4.3 用MHT要注意的三个“暗坑”我想share几个我在用MHT时踩得非常深的坑既然讲到这里希望后来的朋友能提前避开。第一个坑是“出生分数设置不当”。很多MHT相关文献里都会提到“新目标观测值生成出生轨迹时给定一个起始分数”。如果这个开始分数太高你几乎每看到一个界外点就立刻判定为新目标场景里的虚警率会被无限放大。随之而来的是大量无意义的轨迹假设内存爆炸且耗散掉了对真实轨迹的注意力。如果起点分数太低目标短暂被遮挡几帧后观测重新出现时系统不会把它看作一个“恢复的新目标”而会直接舍弃。经过多次试验我习惯把出生分数设为略低于“正常轨迹关联一帧后的得分”这样既能对虚警保持敏感也不至于完全错过新目标。第二个坑是“门限阈值的手动标定”。我之前遇到一个有趣的问题门限设太宽候选关联对会非常多假设空间爆炸设太窄正确的关联对往往被排除掉系统会出现“明明目标就在眼睛前却追踪不住”的废物状态。我后来找到的解决办法是不要只用一个固定的门限而是搞一个“自适应门限”——基于马氏距离的累积分布函数做一个百分比门限比如要求一个关联对的马氏距离必须小于某个置信区间比如95%置信度才被接受。这样门限会随着目标运动模型的状态不确定性自动伸缩鲁棒性大大增加。第三个坑是“全局假设树的维护代价失控”。这个问题前面提到过但你可能会低估它的严重性。在你上线第一个MHT版本时我强烈建议先在代码里打印出每条假设的数量、全局假设的数量以及整棵树的节点总数。如果运行一小时之内这些数字呈指数增长且很快失控就一定意味着你的某个剪枝规则失效了。我当时遇到这个情况查了整整两天才发现问题在于新目标生成分支没有计入“单帧最大新生轨迹数”的限制——同一帧里有上百个虚警点算法以为都是新目标全部留下了。后来限定每帧新生轨迹数的上限通常为2到5低频场景甚至为1假设树规模立刻回归理性区间。5. 三个典型场景下的MHT实战配置清单5.1 场景A停车场车辆追踪这类场景的特点是目标数量不多几十辆车但车辆外观相似、可能出现短时遮挡。你的核心困境往往是两辆同色系的车前后相随中间经过遮挡后ID是同一辆还是换了很多贪心算法在这里会出现频繁的ID切换。我在这类场景下的MHT配置思路是门限距离选得稍紧一些因为停车场里车辆运动相对缓慢一帧间移动距离不大过宽的门限只会引入过多杂乱的候选对。运动模型选择“恒定速度”就足够了不需要引入加速度项。出生分数要偏低一些防止检测器在阴影边缘、反光处产生的虚警被当成新目标。奖励系数适当拉高因为车辆在短时间遮挡后再次出现时位置连续性很强一旦关联成功应该给予较高的正反馈。我实测过这样的配置在30帧每秒的摄像头数据规模下追踪ID切换比SORT系方案下降了近50%。代价是单帧计算耗时增加但对比实用价值来说完全可以接受。5.2 场景B密集人群中的个体追踪密集人群是这个行业里公认的难点目标数量大、相互遮挡严重、外观一致性差——每个人都穿得差不多而且互相穿插。在这种极端场景下MHT不能单独完成所有任务。它需要搭配外观ReID特征和运动模型共同决策。我在这个场景里用的特征是每个目标在最近10帧中的平均外观特征向量把外观相似度作为代价矩阵中的一个加权项再把这个加权项送进MHT的轨道得分公式。这样一来位置信息负责“短期稳”外观信息负责“长期辨”。MHT在这里的核心价值并不在于每帧判得多准而在于它提供了一个“暂缓决策”的缓冲层。当两个目标交叉外观又相似时若采用贪心策略那个瞬间很多算法都会出错但MHT不会立刻判死它会维持两三个候选假设直到后续几帧的累积证据出现再决定谁是A谁是B。这个“延迟裁决”的特性简直就是密集人群场景的福音。5.3 场景C低信噪比雷达目标追踪雷达目标追踪是MHT的传统主场。在这个场景中雷达回波里往往充斥着大量的虚警点真实目标的信噪比很低。每个帧面里真实轨道和虚警点交织在一起人眼看数据都是一团混沌。我发现MHT相比其他算法的优势在这里被放大得更明显因为在虚警率高的场景下任意一帧的“单次关联”都极不可靠你非常需要“多重假设延迟决策”来渡过短暂的不确定期。同时雷达运动模型的非线性特征明显我习惯用交互多模型IMM或者无迹卡尔曼滤波UKF作为底层滤波器MHT负责更高层的关联层。这两者搭配起来的整体效果比用过简单卡尔曼滤波的MHT系统在目标切换率上低一个数量级。在这个场景下必须重点调节的是“代价计算里的虚警惩罚项”。如果虚警惩罚设得过高所有虚警都会被判为新目标数量爆炸如果过低真实目标会被虚警带偏轨迹。我后期采用了一个动态策略根据最近10帧的虚警率动态调整惩罚系数虚警率越高新目标出生的门槛就越高。这个自适应机制在野外复杂环境下对我的系统稳定性帮助极大。5.4 参数速查建议表这里我整理了一张表供大家在最初配置MHT时快速参考基于的是我个人的多次实践不一定通用但可以作为初始值。参数项场景A停车场场景B密集人群场景C雷达低信噪比门限类型马氏距离95%置信度马氏距离外观特征距离加权马氏距离99%置信度偏宽运动模型恒定速度恒定加速度加强噪声协方差交互多模型IMM出生分数偏低如-2.0中等如0.0不超过平均轨迹分数单帧最大新生轨迹数3510轨迹丢失惩罚中-0.8/帧低-0.3/帧视信噪比而定低则高惩罚关联奖励高1.5中1.0低0.3假设树最大深度3帧5帧7帧这张表不是金科玉律它更像是我在不同场景下爬起来后留下的路标。你完全可以在这些初始值基础上按照你的传感器噪声、检测器质量、目标运动特征逐步调整。6. 稳住下限之后再看MHT的上限扩展6.1 把MHT和ReID融合让外观成为第二个维度前面讲过在密集人群场景里搭配ReID特征的重要性这里我可以把这个点展开来说得更细一点。为什么在MHT里要融合外观特征因为MHT的核心是数据关联而数据关联在数学上终究是“分配问题”。如果只依靠位置信息和运动预测当两个目标距离极为靠近时其位置似然函数会发生严重的混叠——此时无论你怎么调运动模型参数数据关联的不确定性都降不下来。而外观特征为这个分配问题提供了另一个正交的信息维度。实际操作时我会为每个轨迹维护一个外观特征队列。我会用一个轻量级的外观特征提取器例如小型卷积网络或直接使用检测器的特征头部获取每个检测框的外观嵌入向量。在门限过滤阶段我把“马氏距离”和“特征余弦距离”按一定的比例加权成一个综合代价。比如在某些实现里我会取total_cost alpha * mahalanobis_cost (1 - alpha) * appearance_costalpha可以在0到1之间调节。alpha这个参数很有意思——alpha过大会退化成纯运动MHTalpha过小则会严重依赖外观判别力。好的外观提取器能够显著提升MHT的长期追踪能力但如果外观提取器本身性能不稳例如在光照变化剧烈的环境中强行使用反而会拖垮系统。我一般会在多样环境下做一次校准观察目标外观特征在同ID和不同ID两种情况下的分布距离关系然后据此确定alpha。比如如果不同ID之间的特征距离离散度很大、判别力强alpha就能调小如果特征严重同质化那只能保守一点多用运动信息。6.2 优化求解器从“精确解”到“近似最优”的平衡前面提到MHT的全局最优解本质上是一个加权最大独立集问题在规模中等时可用精确方法但规模一大就必须求快。我对这个环节做过几轮迭代可以分享一下不同策略给我带来的体感差异。最初我用的是暴力递归枚举对全局假设集合做深度优先搜索加入剪枝。这种方案在小场景轨迹数小于10时候非常直观代码写起来也简洁。缺点是当轨迹数超过20候选配对一多DFS就会山穷水尽。后来我改成了整数线性规划ILP方案。它的建模很优雅将每个候选“观测-轨迹关联对”看作一个二进制变量取值为1表示采纳0表示不采纳然后加上两条硬性约束——每个观测值最多分配给一个轨迹每个轨迹最多关联一个观测值目标函数是所有被采纳关联对的得分加和最大化。这个版本在40条轨迹以内、30个观测值的场景下Intel CPU实时求解也稳得住。但到了雷达大规模场景求解耗时一下子就拉长了实时性不达标。最终我采用的是“贪心起始解局部搜索优化”的方式先按得分高低排序从最高分开始不断尝试加入关联对并检查是否与已选集合冲突得到一个可用的初始解然后做“交换邻域搜索”——就是尝试把所有当前未被选入的高分关联对和已选入的低分关联对做一个交换模拟如果总分上升则执行。这个近似解的质量通常在精确解平均损失的1%-5%以内但速度提升了十倍还多。我觉得在实际工程项目里这种“99%接近最优”的方案远比“理论最优但实时天方夜谭”的方案有价值得多。6.3 MHT与深度学习的交接让特征既做输入也做判别现在的多目标追踪领域纯靠手工特征做关联的MHT已经慢慢退出主流主流方案逐步走向深度学习LSTM/Transformer关联建模。但我想强调这不意味着MHT失去了存在的意义。恰恰相反MHT的框架为深度学习提供了一个非常优的“外壳”让网络来负责特征的提取与判别让MHT来负责结构化推理和全局假设管理。我在某个密集目标追踪系统里最后采用的架构是这样的检测器输出目标框和外观特征向量外观特征进入MHT的代价计算模块同时轨迹的得分函数中的似然项不再是用手工设定的高斯似然而是换成了一个可学习的打分函数——基于一个多层感知机输入是“运动特征外观特征历史轨迹信息”输出是“关联成立”的概率。这个概率作为轨迹得分的增量底层仍然由MHT的假设树来维护整个解空间。这种混合架构的好处非常明显既保留了MHT的“暂缓决策、全局优化”结构优势又借助深度特征弥补了MHT在长期视觉特征上的短视。我比较推荐有充足标注数据集的小伙伴试试这条路。它是把经典理论和现代工具结合起来相当有效的一条路径。7. 自己的实战心得三个让我“悟了”的时刻7.1 第一件别把所有模糊帧都交给MHT求解最初我上MHT的时候以为“既然是全假设搜索那我每一帧都把所有模糊关联都丢给它去枚举它总会给我最优解”。结果程序跑起来的直观感受就是电脑风扇狂转、内存逐步爬升、跑十分钟已经卡到不行。后来我仔细分析了耗时分布发现真正需要MHT“延迟决策”的帧其实非常有限。大多数时刻目标分布稀疏、运动轨迹清晰直接用简单的最近邻关联就能得出和MHT同样正确的结果。我干脆加了一个“模糊度检测”模块如果当前帧的总体关联模糊度低于某个阈值就直接走贪心匹配只有模糊度高的时候才切换到MHT的完整假设分支。这个两阶段策略让系统在大多数帧上的计算量减少了90%同时遇到关键遮挡场景时又能启动完整的MHT能力效果和全时MHT几乎没有差异。7.2 第二件追踪器的输出要留“退路”还有一次让我印象深刻的经历是我在MHT系统上线后发现它偶尔会“犯错”——它的错误不是目标跟丢而是它把一条错误假设维持得太久甚至到了后期才在下一条证据出现后修正。这个“修正”过程本身没问题但由于MHT高层输出只会发布每帧的最优全局假设底层修正会导致输出ID在小范围内反复跳跃。后来我调整了输出策略MHT的最终决策层不直接输出每帧最优全局假设而是输出“当前最优全局假设中所有活跃轨迹的置信度”再由下游模块决定何时把这条轨迹“确认”为最终跟踪目标。换句话说我让MHT在“内部”可以大胆保留多条假设但在“对外”则保守发布只有某条轨迹的置信度连续多帧稳定居首时才会将其正式提交给业务层。这种“内紧外松”的设计显著削弱了ID切换给下游造成的干扰。7.3 第三件评价指标不要只看MOTA在做多目标追踪算法对比实验时大家最常看的指标是MOTAMulti-Object Tracking Accuracy。这个指标综合了漏检、误检和ID切换三个方面的表现。如果你只盯着MOTA去调MHT的参数你会发现它的提升空间相对有限甚至在某些数据集上不如简单方法。但我后来认识到MHT的很多价值并不体现在这个单一指标上而是体现在“轨迹连续性和平滑性”这些二级隐性指标上。比如我做视频分析项目时业务方最关心的并非ID切换计数——他们关心的是“同一个目标有没有被打断成两条轨迹”“车辆轨迹是否平滑连贯”。在这个维度上MHT的优势就体现得非常明显它输出的轨迹通常具备更长的连续性、更低的轨迹碎片率。后来我会在调参时额外关注“平均轨迹长度”和“轨迹碎片率”这两个指标而不是被MOTA这一个指标绑架。我建议做工程评估的时候从业务场景反向推导追踪指标别让它变成纯粹的数字游戏。第一性原则、延迟决策、全局最优——这三个词怎么听都像是一套学生时代崇拜的华丽理论。但在真正上手实现MHT、跑通仿真、又杀进真实场景之后我反而觉得它更像一位老派的匠人它不肯帮你做临时的决定它宁可让所有假设在时间里自行沉淀最后把最扎实的那一条轨迹呈现给你。每次我在密集场景里遇到ID切换比分都用MHT的机制来救场时我都能重新理解一次“不急于求成才能等到真相浮出水面”这句话。希望你读完这篇文章以后也能在MHT的复杂表象下看到它那份朴素的智慧——并且有勇气在你的下一个项目里试试它。 
长河君 · 2026/10/22 18:15:12 · 阅读 1.2k 多假设追踪MHT实战：从核心思想到工程落地
多假设追踪Multiple Hypothesis Tracking这个名字我初次接触的时候第一反应是“这玩意是不是那种只在论文里活着、工程上根本没人敢碰的算法”。说实话这种印象不算全错——MHT在很长一段时间里确实被视为多目标追踪领域“理论上最优、实现上劝退”的典型代表。但后来我在实际项目里被SORT、DeepSORT这类“贪心策略”连续坑了几次才下定决心认真啃MHT。这篇文章就是想把MHT从论文语言翻译成工程语言用我自己的理解方式拆开讲清楚它的核心思想是什么、为什么它会被称为“最优”但又“难搞”以及你在实际落地时到底在哪些环节会真正感受到它和其他算法的区别。无论你是做自动驾驶感知、体育赛事分析、视频监控还是研究多智能体系统只要你的场景里存在“多个目标 相互遮挡 短暂消失 数据噪声”MHT就是你绕不开的一条技术路线。这篇讲解不会堆公式到让人放弃但该给的关键推导和数据结构我也会给到位重点放在“为什么这样设计”和“工程上怎么实现”这两块。1. 多目标追踪真正的难点不在“追踪”而在“认人”1.1 你以为是连续追踪其实是反复做“数据关联”很多人刚接触多目标追踪时会误以为这个问题是这样的我检测到目标了我给它做一个轨迹然后下一帧我继续在这个轨迹上更新位置就行。听起来很丝滑对吧但真实场景里这个“继续更新”的动作恰恰是整个问题的核心难点。因为你的传感器——无论是摄像头、毫米波雷达还是激光雷达——每一帧给到你的只是一堆“非连续的点观测值”。这些观测值本身没有身份它们只是一个个独立的量测比如目标的位置坐标、目标的置信度向量而你并不知道这一帧的点A和上一帧的点B到底是不是同一个目标。把每个观测值和它对应的历史轨迹正确配对起来这个环节就是“数据关联”。如果你只追踪一个目标这问题很简单全场景就一个点我直接关联就行。可是当画面里同时有十几个人、几辆车或者雷达回波里出现大量虚警点时“这一帧的哪个点属于哪条轨迹”就立刻变成组合爆炸级别的复杂问题。我打个比方你现在站在一个广场中央周围有成群的人在走动。每过一秒钟你闭一次眼睁开后你要判断——刚才站在你左边的那位现在是哪一位如果人少、运动慢你一眼就能认出来如果人多、衣着相似、相互穿插而过你可能瞬间就懵了。多目标追踪算法干的活就是替你做这个瞬间判断。1.2 贪心策略和最优策略的分水岭业界最常见的追踪框架比如SORT和DeepSORT一系它们在数据关联这一环采用的是“贪心匹配”的思路。什么叫贪心就是只看当前时刻做一个局部最优的决定我把这一帧的观测值和已有轨迹算一个代价矩阵然后用匈牙利算法或者直接最大二分匹配找到一个当前代价最小的匹配方案。一旦匹配上了就认为这件事“定了”不会再回头更改。这种方案的优点是显而易见的快、简单、稳定工程上非常好落地。但它有一个没有解决的问题——如果当前的匹配决策本身是错误的呢举个具体场景视频监控里一个人被另一个人遮挡了整整五秒。等他重新出现在画面中时你已有的轨迹和他现在的观测值之间的位置跳变非常大极有可能你会认为这是一个“新目标”于是新建了一条轨迹。而那个被他遮挡住的人他的轨迹因为在连续几帧里没有关联到任何观测值会被标记为“丢失”然后提前终止。与此同时你追踪到的“新目标”其实还是同一个人——但你已经在管理层上把它当成两个不同的ID了。这就是业界常说的“ID Switch”即同一目标被错误地分配了多个身份编号。贪心策略之所以在遮挡、交叉、密集场景中容易出现这类问题本质原因是它在每个时刻就只留一条被子——一旦这步选错后面所有帧都会基于错误前提继续更新。MHT要做的就是改变这个“定了就不回头”的假设。1.3 MHT给出的方案先不急着做决定MHT的全称是Multiple Hypothesis Tracking翻译过来是“多假设追踪”。它的核心思想如果用一句话总结就是既然我一时刻无法确定正确关联那我就把所有可能的关联方式都保留下来让数据在后续帧中慢慢“说话”最后才收敛出最具说服力的那一条轨迹。听起来很像是人在做选择时会用的办法。你去商场找人看到背影和同事很像但不确定。正常人不会立刻上去拍肩膀而是先跟着走两步近距离观察走姿、衣服细节、侧脸轮廓再最终确定“就是他”或者“不是他”。你不会在第一时间就做绝不回头的决定你会保留几种可能性观察一段再下结论。MHT正是这种“保留多种可能性”策略的机器实现。每一帧它对现有的每个轨迹结合当前观测数据构造若干条候选的关联假设。这些假设可能会让轨迹A关联到观测点1也可能让轨迹A关联到观测点2还可能让轨迹A认为观测点1是一个新目标的起始点。所有这些可能性都被保留下来各自形成一条新的轨迹假设分支。然后呢数据一帧帧累积有些假设的预测位置和真实观测越来越吻合得分持续升高有些假设则在连续几帧中都找不到支持它的观测值得分逐渐下滑最终被丢弃。打分制胜这就成了MHT最后的决策机制。2. 从直觉到实现MHT的四个核心模块2.1 假设生成把“所有可能性”枚举出来任何基于“多假设”的算法第一步一定是把一个“模糊的关联局面”拆解成若干“明确的关联候选”。这个拆解过程在MHT里叫做假设生成Hypothesis Generation。假设你现在有两帧数据。上一帧你已经有两条轨迹轨迹T1和轨迹T2。当前帧你检测到三个点观测值O1、O2、O3。那么这一帧的数据关联问题就变成了一个类似“每个轨迹要么关联一个观测值、要么暂时不关联每个观测值要么属于某个轨迹、要么属于新目标或虚警”的分配问题。我在实际做工程实现的时候第一步会用距离门限Gating把明显没戏的配对先排除掉。比如T1的预测位置在坐标(10,20)而O3出现在(300,200)两者之间距离远超过合理的运动范围那这组“T1-O3”关联就可以直接丢掉。这一步是纯粹的几何过滤可以帮助你把一个巨大的关联矩阵缩小成稀疏的候选集合。为什么需要这个步骤因为MHT最怕的就是把所有可能的组合全部枚举出来——那是指数爆炸级别的。如果当前帧有N条轨迹、M个观测值即便是简单的无约束分配组合数也会迅速膨胀到天文数字。如果在每一帧都做全量枚举算法根本无法实时运行。工程上MHT的可用性很大程度上取决于Gating的质量和灵活性。在我构建假设树的时候我用的框架是这样的每个节点代表一条轨迹在当前时刻的一个关联状态而一条完整轨迹的“历史”就是一棵从根节点到当前节点的路径。这个路径上记录的是这个假设在每一帧拿哪个观测值去更新轨迹的滤波器状态。树的规模就是所有可能的关联历史集合。这套结构的空间复杂度确实是MHT的软肋。我早期自己写代码时一段时间内没有控制假设树深度结果跑了不到两分钟内存直接爆炸到数十GB。后面才老老实实加上“最大假设树深度”这个限制参数比如只保留最近5帧的分支更早的历史认为已经定型不再分支。2.2 轨迹得分如何判断“这条假设活得对不对”多条假设都保留了但总不能一直让它们平行生长得有办法判断谁更“可信”。这个可信度在MHT里用“轨迹得分”Track Score来表达。我先说我的实现认知不一定和教科书上的公式完全一一对应但逻辑是一致的。每一条轨迹假设都有一个得分这个得分会随着每一帧的处理而更新。更新的规则是这样的当这条假设成功关联到一个观测值时它的得分会增加当这条假设没有任何观测值支持时它的得分则会被扣减。为什么这样设计因为你每拿到一个“支持证据”你对自己当前判断正确性的信心就应上升。这个思想其实和人类做决策的贝叶斯推断过程高度吻合。如果你把“观测值O出现了”看作对“轨迹是T1”这条假设的一个证据支持那么证据越多、越吻合假设的后验概率自然就越大。MHT的得分公式基础就来自这个朴素原理。具体操作上我常用的一套得分更新公式是这样的令当前轨迹假设的分数为Score_old当它关联到观测值z时更新分数为Score_old加上一个“关联收益”这个收益通常是该观测值对应目标的似然对数。如果这一帧没有任何观测值进入该轨迹那么Score_new等于Score_old减去一个“惩罚系数”。这个惩罚系数平时我会调成一个常数用于表征“目标暂时丢失”对假设可信度的削弱程度。这里有一个参数设计的微妙问题如果“关联收益”太大那算法会变得激进任何微弱证据都会让某条分支得分飙升最后可能过早收敛到错误的假设反过来如果“惩罚系数”过大那么轨迹只要在遮挡中断了一两帧得分就会被迅速扣到底导致正确轨迹被过早丢弃。实际调参下来我觉得这个“收益与惩罚的平衡”是整个MHT系统里最具艺术性的一部分我在后面调参章节会具体展开。这类比的感受是一条轨迹假设就像你养的一个手下的情绪账户你每派它完成一个任务关联到一个观测点情绪就涨每让它空等一轮没有找到观测点情绪就跌。但是你得小心别让情绪涨得太疯或跌得太狠否则判断就会失真。2.3 全局假设管理为什么需要“互斥条件”刚才说的是单条轨迹的得分但MHT还有一个关键机制——全局假设管理Global HypothesisManagement。这个设计的出发点很简单一条轨迹假设说“我是正确的因为我有高分”这还不够因为你还需要保证这些假设之间没有冲突。举个例子当前帧观测到3个点但不同轨迹的假设中可能存在“轨迹T1关联观测O1”和“轨迹T2关联观测O1”这样完全冲突的情形——同一个观测点不可能同时属于两条轨迹。如果放任这种冲突最终收敛出来的结果就是荒唐的。所以MHT维护的不是一棵假设树而是一整个“全局假设集合”。一个全局假设就是一组互不冲突的单条轨迹假设它们中间没有任何两条使用同一个观测值。这个全局假设的得分通常是它内部所有被采纳的轨迹假设得分的总和。那么每一帧要做的就是从当地所有可用的轨迹假设中挑出一组互不冲突的子集这个子集的得分总和最大。听上去是不是很耳熟对这本质上就是一个带权的最大独立集问题。当节点数是几百这个量级时你可以直接用经典的枚举加剪枝求解但一旦到了上千条假设就必须用近似解法。我在项目里实际尝试过几种逼近方式。一是把这个问题转换成整数线性规划ILP问题用现成的求解器去算精度高但慢。二是用贪心加局部搜索的办法先取一个效果还不错的可行解然后通过5到10轮局部扰动优化不求全局最优但只要结果足够好就行。三是我现在用得最顺手的做法给全局假设排序留一个“容忍窗口”——不要只保留得分最高的那个全局假设也保留排名第二、第三的候选假设把取舍延迟到更后续的帧里。这种“保留Top-K全局假设”的做法在工程上几乎是MHT实时化的核心手段。2.4 假设剪枝控制增长的生命线如果你完完整整把每个帧的“所有可能性”都保留下来那么假设树的规模会呈指数级增长。第五帧可能是十几个分支第十帧就可能到几百第二十帧直接爆掉。这时候就必须要执行“剪枝”Pruning。剪枝目标很简单把那些已经没有前途的假设分支去掉。怎么判断“没有前途”我主要会看这几个标准第一刚才提到的轨迹得分是否低于某个阈值。比如我常见的设置是把基线得分设为0只要一条假设的得分是严重负数它就是负资产直接丢弃。第二看这棵树的深度。如果某条分支连续若干帧都没有关联到观测值而且其得分在快速下降十有八九是目标真实丢失了这条分支留着只会干扰全局假设管理。第三也是我后期才悟到的限制每个父节点下的子节点数量。你不要天真地以为明确了Gating就能把候选分支控制在很小的范围内当你做的是密集人群扫描时目标数量多观测值也多候选对可能依然异常庞大。我会在代码里加一个“每父节点最大子分支数”的参数超过上限之后只保留得分最高的那部分。这种近似的代价是损失部分最优性但换来的可运行性可以说是天壤之别。还有一种是“协同剪枝”目的在于保持全局假设集合的一致性。你可能会遇到这样的情况某条轨迹假设单独看得分不错但它和当前最高分的全局假设产生了冲突比如它占用了那个全局假设里另一条轨迹必需的观测点。那为了保障最优全局假设的完整性我必须在剪枝阶段把它提前淘汰掉。这个步骤像打球时的战术配合——我不仅看你这名球员个人能力还要看你在这个阵型里能否和其他队友共存。3. 把MHT从理论放到代码我的一步步落地经验3.1 一帧一帧拆开MHT的完整处理流水线这里我想把MHT的完整计算流程用伪代码的形式写出来。因为只有把这套架构理顺了你后面写代码时才不会迷茫。输入当前帧观测值集合 Z {z1, z2, ..., zm} 输入现有轨迹假设集合 T {t1, t2, ..., tn} 输出最新全局假设 G_best # Step 1: 预测 for track in T: track_filter.predict() # 卡尔曼滤波先预测目标下一时刻位置 # Step 2: 门限过滤Gating candidate_pairs [] for track in T: for obs in Z: if gate_test(track, obs): # 计算欧氏距离/马氏距离是否小于门限 candidate_pairs.append((track, obs)) # Step 3: 生成新的轨迹假设集 new_hypotheses [] for pair in candidate_pairs: new_track deepcopy(track) new_track.update(obs) # 用当前观测值更新滤波器状态 new_track.score log_likelihood(pair) new_hypotheses.append(new_track) # 没配对到任何观测的目标标记为“丢失”进行惩罚 for track in T: if track not in candidate_pairs: lost_track deepcopy(track) lost_track.score - penalty new_hypotheses.append(lost_track) # 没配对到任何轨迹的观测生成新目标初始轨迹 for obs in Z: if obs not in candidate_pairs_observation: new_born create_track(obs) new_born.score birth_score new_hypotheses.append(new_born) # Step 4: 全局假设管理 G extract_global_hypotheses(new_hypotheses) # 通过“最大加权独立集”求解 G_best choose_best_global(G) # Step 5: 剪枝 prune_hypotheses(new_hypotheses)这个流程看着并不算特别复杂对吧但真正的复杂度藏在各个Step的实现细节里。就拿Step 3来说deepcopy一条轨迹假设——如果轨迹状态是卡尔曼滤波里的均值向量加协方差矩阵那拷贝还便宜但如果每条轨迹附带了一整棵特征历史队列例如ReID的外观特征序列那拷贝起来就是开销巨大的操作。我在第一版实现里天真地用了全量深拷贝结果发现每帧耗时随轨迹数量的增加呈指数级增长。后来优化成了“写时复制”Copy-on-Write即在新的假设生成时只保留和旧轨迹不同的部分公共历史部分用共享引用速度直接提升了一个量级。这个问题如果不做优化再好的算法也只是纸面文章。3.2 卡尔曼滤波之外观测模型与似然计算说完了流程框架我们来拆一个看起来很不起眼、但实际上对效果影响极大的点观测模型的似然计算。MHT里轨迹得分恰恰由这个似然数值来决定如果你的似然函数是拍脑袋写的那么所有假设分支的排序都是不准确的。最常见的做法是用卡尔曼滤波的预测结果来构造一个高斯似然函数。假设当前轨迹的状态分布是一个高斯分布有均值μ和协方差矩阵Σ那么一个观测值z对该轨迹的“似然”就是这个高斯分布在z点处的概率密度值。具体计算时因为会把分数映射到对数域进行所以最后得到的是一个负的二次型结果。数学化的表达是这样的假设观测值是z轨迹的预测位置是μ从状态空间到观测空间的观测矩阵是H那么z和μ之间的“残差”innovation为y z - Hμ其对应的协方差矩阵为S H P H^T R其中P是滤波器状态协方差R是观测噪声协方差。那么马氏距离d y^T S^{-1} y。这个d越小说明观测值和轨迹预测之间越吻合似然值越高。这里我踩过一个坑最开始我图省事直接用欧氏距离来做门限过滤和似然计算。在目标静止或者运动较为平缓的场景里结果差异不算大。但我一旦把算法迁移到车辆高速运动的数据集上目标移动速度飞快位置分布的真实不确定性已经拉成了一个细长的“椭圆”此时用各向同性的欧氏距离来衡量“是否匹配”结果就非常糟糕。后面我全线换成马氏距离预测协方差矩阵会在每一帧根据运动模型自动调整方向和大小整个系统的精度才稳定下来。所以这里我的建议是在你的框架里任何涉及“距离计算”的地方优先使用基于马氏距离的高斯似然而不要停留在欧氏距离。尤其当你的目标运动模型带明显的加速度或转向机动时这个差异会被无限放大。3.3 代码骨架与数据结构设计思路写MHT代码的时候数据分析结构设计比算法主逻辑更影响整体实现效率。我分享下我目前比较偏好的一套结构设计轨迹类至少要包含三个字段状态估计对象里面存放卡尔曼滤波器均值向量和协方差矩阵得分浮点数记录当前轨迹假设的累积得分生命状态标记轨迹当前是“活跃”、“暂时丢失”还是“已消亡”。此外为了支持后续的ReID或者通知外观信息一个可选的“观测历史队列”也值得预留着。这个队列不用太长保留最近10帧的特征向量就足够应对多数遮挡恢复的场景。全局假设类的设计同样重要。我会维护一个观测索引到轨迹索引的字典确保每一条全局假设内部的关联不冲突。全局假设还应包含一个成员得分总和方便在“选择最优全局假设”时直接排序。树的表示方式我用的是“虚拟树”的思路每个轨迹节点指向其父节点但父节点数据并不物理拷贝到子节点里。子节点只保存增量信息例如关联到的观测值索引、本帧得分增量。要回溯整条轨迹历史时从当前节点一路向父节点走即可。这种指针式结构会比节点物理拷贝的做法节省很多内存也方便后期剪枝——只要调整引用计数就能比较轻量地摘下无用分支。3.4 逐步反馈在代码里跑通“多假设”的第一步如果你现在准备自己动手实现一个最小的MHT系统我建议第一步千万别贪多求全。你可以先固定目标数量不超过5个简化运动模型去掉外观特征只依赖位置信息来做关联。这一步的核心目标是把“假设生成-假设管理-剪枝”这条主链路跑通。我当初的最低实现思路是这样的状态向量只包含位置和速度观测值只有位置坐标运动模型是恒定速度模型门限过滤用简化的马氏距离全局假设用最大加权二分匹配——先不考虑多目标的最优全局分配只做局部配对加剪枝。跑通这一版之后再逐步引入“观测值可以属于新目标”、引入“轨迹未关联观测则丢失”等机制让假设空间真正“多”起来。这一过程让我意识到一个规律MHT的复杂度上涨并不是线性的而是呈跳变的。当你允许的假设空间到达某个阈值时时间复杂度突然高到算法卡顿。这种时候不要急于调大剪枝力度先检查代码里是否有无谓的对象拷贝和索引重复计算。很多时候时间复杂度的爆炸是“低效的数据结构 过深的拷贝链”叠加出来的而不是MHT本身的复杂度造成的。4. 别把MHT玩成传说也别忘了它的“边界”4.1 为什么说MHT“在实际场景里并不总是最优”MHT在理论上被视为多目标追踪的“金标准”几乎所有其他追踪算法在对比精度时都会拿它作为参照。但“理论上最优”和“实际中必须用”之间还隔着几座大山。第一个大山是实时性。MHT的假设空间在高密度场景下增长极快即使加了种种剪枝策略你依然要面临“为了让系统实时跑最优性打了折扣”的处境。这种「理论最优性衰减」是所有在真实系统里用过MHT的工程师必然面对的妥协。第二个大山是参数敏感性。这个算法的效果极大依赖于门限阈值、惩罚系数、生成新目标的置信度、剪枝频率等一系列参数。我曾在同一个算法架构下换了一个数据集原先调好的参数就必须重新标定否则追踪的ID Switch会飙升到无法接受的程度。MHT不是一把“一键调好”的利器它更像一把需要你经常保养的瑞士军刀。第三个大山是在线学习能力不足。MHT基于的是“先有模型再关联数据”的思路——它假设你对目标的运动模型、观测噪声方差有一定的先验了解。但如果你遇到的是一类全新场景目标运动特征和你预设模型严重不符MHT的滤波器预测就会系统性地偏离真实位置导致门限过滤把正确的关联对提前丢掉了。而类似基于学习的关联算法如基于图神经网络的数据关联方法能够在大量标注数据中自动提取关联模式抗模型失配的能力更强。4.2 对比其他关联算法为什么JPDA没有MHT“翻盘”能力在讲MHT时有一个经常被放在一起对比的算法叫做JPDA——联合概率数据关联Joint Probabilistic Data Association。JPDA的核心思路是对每个轨迹把该帧所有观测值按“属于某轨迹”的概率进行加权融合最终用加权平均来更新轨迹状态。它不等同于选择某个单一关联对而是做一个概率上的“软分配”。JPDA和MHT的核心差异在于对“不确定性”解决方案的不同JPDA把不确定性直接“平均化”了用加权的方式顺滑地消化掉关联模糊MHT则把不确定性“保留”了她同时维护多个可能的关联历史最后用新证据逐步消歧。这意味着当出现严重的轨迹交叉或者遮挡时JPDA的模糊处理常常会把目标位置拉向“中间地带”——本来两条轨迹应该一个走左边、一个走右边但JPDA在模糊期间会把两轨迹都推向画面中央等模糊解除后你会发现它们的估计位置已经明显偏移了。MHT因为保留了“轨迹A走左边、轨迹B走右边”的多种假设后期可以随着观测值的出现让正确的假设胜出从而把位置误差控制得更小。这是我的切身体会如果你的场景目标密度不高目标运动稳定JPDA那套“平均化”的做法非常管用简单、快、稳但如果目标常常遮挡、轨迹互相交叉JPDA的位置偏移会积累成为硬伤而MHT虽然实时性差些但至少不会严重“跑偏”。所以我的项目里通常是这样取舍的低密度场景优先JPDA或SORT系高密度、强互扰的场景就直接上MHT密度再高就考虑分层、分块来缓解MHT的复杂度。4.3 用MHT要注意的三个“暗坑”我想share几个我在用MHT时踩得非常深的坑既然讲到这里希望后来的朋友能提前避开。第一个坑是“出生分数设置不当”。很多MHT相关文献里都会提到“新目标观测值生成出生轨迹时给定一个起始分数”。如果这个开始分数太高你几乎每看到一个界外点就立刻判定为新目标场景里的虚警率会被无限放大。随之而来的是大量无意义的轨迹假设内存爆炸且耗散掉了对真实轨迹的注意力。如果起点分数太低目标短暂被遮挡几帧后观测重新出现时系统不会把它看作一个“恢复的新目标”而会直接舍弃。经过多次试验我习惯把出生分数设为略低于“正常轨迹关联一帧后的得分”这样既能对虚警保持敏感也不至于完全错过新目标。第二个坑是“门限阈值的手动标定”。我之前遇到一个有趣的问题门限设太宽候选关联对会非常多假设空间爆炸设太窄正确的关联对往往被排除掉系统会出现“明明目标就在眼睛前却追踪不住”的废物状态。我后来找到的解决办法是不要只用一个固定的门限而是搞一个“自适应门限”——基于马氏距离的累积分布函数做一个百分比门限比如要求一个关联对的马氏距离必须小于某个置信区间比如95%置信度才被接受。这样门限会随着目标运动模型的状态不确定性自动伸缩鲁棒性大大增加。第三个坑是“全局假设树的维护代价失控”。这个问题前面提到过但你可能会低估它的严重性。在你上线第一个MHT版本时我强烈建议先在代码里打印出每条假设的数量、全局假设的数量以及整棵树的节点总数。如果运行一小时之内这些数字呈指数增长且很快失控就一定意味着你的某个剪枝规则失效了。我当时遇到这个情况查了整整两天才发现问题在于新目标生成分支没有计入“单帧最大新生轨迹数”的限制——同一帧里有上百个虚警点算法以为都是新目标全部留下了。后来限定每帧新生轨迹数的上限通常为2到5低频场景甚至为1假设树规模立刻回归理性区间。5. 三个典型场景下的MHT实战配置清单5.1 场景A停车场车辆追踪这类场景的特点是目标数量不多几十辆车但车辆外观相似、可能出现短时遮挡。你的核心困境往往是两辆同色系的车前后相随中间经过遮挡后ID是同一辆还是换了很多贪心算法在这里会出现频繁的ID切换。我在这类场景下的MHT配置思路是门限距离选得稍紧一些因为停车场里车辆运动相对缓慢一帧间移动距离不大过宽的门限只会引入过多杂乱的候选对。运动模型选择“恒定速度”就足够了不需要引入加速度项。出生分数要偏低一些防止检测器在阴影边缘、反光处产生的虚警被当成新目标。奖励系数适当拉高因为车辆在短时间遮挡后再次出现时位置连续性很强一旦关联成功应该给予较高的正反馈。我实测过这样的配置在30帧每秒的摄像头数据规模下追踪ID切换比SORT系方案下降了近50%。代价是单帧计算耗时增加但对比实用价值来说完全可以接受。5.2 场景B密集人群中的个体追踪密集人群是这个行业里公认的难点目标数量大、相互遮挡严重、外观一致性差——每个人都穿得差不多而且互相穿插。在这种极端场景下MHT不能单独完成所有任务。它需要搭配外观ReID特征和运动模型共同决策。我在这个场景里用的特征是每个目标在最近10帧中的平均外观特征向量把外观相似度作为代价矩阵中的一个加权项再把这个加权项送进MHT的轨道得分公式。这样一来位置信息负责“短期稳”外观信息负责“长期辨”。MHT在这里的核心价值并不在于每帧判得多准而在于它提供了一个“暂缓决策”的缓冲层。当两个目标交叉外观又相似时若采用贪心策略那个瞬间很多算法都会出错但MHT不会立刻判死它会维持两三个候选假设直到后续几帧的累积证据出现再决定谁是A谁是B。这个“延迟裁决”的特性简直就是密集人群场景的福音。5.3 场景C低信噪比雷达目标追踪雷达目标追踪是MHT的传统主场。在这个场景中雷达回波里往往充斥着大量的虚警点真实目标的信噪比很低。每个帧面里真实轨道和虚警点交织在一起人眼看数据都是一团混沌。我发现MHT相比其他算法的优势在这里被放大得更明显因为在虚警率高的场景下任意一帧的“单次关联”都极不可靠你非常需要“多重假设延迟决策”来渡过短暂的不确定期。同时雷达运动模型的非线性特征明显我习惯用交互多模型IMM或者无迹卡尔曼滤波UKF作为底层滤波器MHT负责更高层的关联层。这两者搭配起来的整体效果比用过简单卡尔曼滤波的MHT系统在目标切换率上低一个数量级。在这个场景下必须重点调节的是“代价计算里的虚警惩罚项”。如果虚警惩罚设得过高所有虚警都会被判为新目标数量爆炸如果过低真实目标会被虚警带偏轨迹。我后期采用了一个动态策略根据最近10帧的虚警率动态调整惩罚系数虚警率越高新目标出生的门槛就越高。这个自适应机制在野外复杂环境下对我的系统稳定性帮助极大。5.4 参数速查建议表这里我整理了一张表供大家在最初配置MHT时快速参考基于的是我个人的多次实践不一定通用但可以作为初始值。参数项场景A停车场场景B密集人群场景C雷达低信噪比门限类型马氏距离95%置信度马氏距离外观特征距离加权马氏距离99%置信度偏宽运动模型恒定速度恒定加速度加强噪声协方差交互多模型IMM出生分数偏低如-2.0中等如0.0不超过平均轨迹分数单帧最大新生轨迹数3510轨迹丢失惩罚中-0.8/帧低-0.3/帧视信噪比而定低则高惩罚关联奖励高1.5中1.0低0.3假设树最大深度3帧5帧7帧这张表不是金科玉律它更像是我在不同场景下爬起来后留下的路标。你完全可以在这些初始值基础上按照你的传感器噪声、检测器质量、目标运动特征逐步调整。6. 稳住下限之后再看MHT的上限扩展6.1 把MHT和ReID融合让外观成为第二个维度前面讲过在密集人群场景里搭配ReID特征的重要性这里我可以把这个点展开来说得更细一点。为什么在MHT里要融合外观特征因为MHT的核心是数据关联而数据关联在数学上终究是“分配问题”。如果只依靠位置信息和运动预测当两个目标距离极为靠近时其位置似然函数会发生严重的混叠——此时无论你怎么调运动模型参数数据关联的不确定性都降不下来。而外观特征为这个分配问题提供了另一个正交的信息维度。实际操作时我会为每个轨迹维护一个外观特征队列。我会用一个轻量级的外观特征提取器例如小型卷积网络或直接使用检测器的特征头部获取每个检测框的外观嵌入向量。在门限过滤阶段我把“马氏距离”和“特征余弦距离”按一定的比例加权成一个综合代价。比如在某些实现里我会取total_cost alpha * mahalanobis_cost (1 - alpha) * appearance_costalpha可以在0到1之间调节。alpha这个参数很有意思——alpha过大会退化成纯运动MHTalpha过小则会严重依赖外观判别力。好的外观提取器能够显著提升MHT的长期追踪能力但如果外观提取器本身性能不稳例如在光照变化剧烈的环境中强行使用反而会拖垮系统。我一般会在多样环境下做一次校准观察目标外观特征在同ID和不同ID两种情况下的分布距离关系然后据此确定alpha。比如如果不同ID之间的特征距离离散度很大、判别力强alpha就能调小如果特征严重同质化那只能保守一点多用运动信息。6.2 优化求解器从“精确解”到“近似最优”的平衡前面提到MHT的全局最优解本质上是一个加权最大独立集问题在规模中等时可用精确方法但规模一大就必须求快。我对这个环节做过几轮迭代可以分享一下不同策略给我带来的体感差异。最初我用的是暴力递归枚举对全局假设集合做深度优先搜索加入剪枝。这种方案在小场景轨迹数小于10时候非常直观代码写起来也简洁。缺点是当轨迹数超过20候选配对一多DFS就会山穷水尽。后来我改成了整数线性规划ILP方案。它的建模很优雅将每个候选“观测-轨迹关联对”看作一个二进制变量取值为1表示采纳0表示不采纳然后加上两条硬性约束——每个观测值最多分配给一个轨迹每个轨迹最多关联一个观测值目标函数是所有被采纳关联对的得分加和最大化。这个版本在40条轨迹以内、30个观测值的场景下Intel CPU实时求解也稳得住。但到了雷达大规模场景求解耗时一下子就拉长了实时性不达标。最终我采用的是“贪心起始解局部搜索优化”的方式先按得分高低排序从最高分开始不断尝试加入关联对并检查是否与已选集合冲突得到一个可用的初始解然后做“交换邻域搜索”——就是尝试把所有当前未被选入的高分关联对和已选入的低分关联对做一个交换模拟如果总分上升则执行。这个近似解的质量通常在精确解平均损失的1%-5%以内但速度提升了十倍还多。我觉得在实际工程项目里这种“99%接近最优”的方案远比“理论最优但实时天方夜谭”的方案有价值得多。6.3 MHT与深度学习的交接让特征既做输入也做判别现在的多目标追踪领域纯靠手工特征做关联的MHT已经慢慢退出主流主流方案逐步走向深度学习LSTM/Transformer关联建模。但我想强调这不意味着MHT失去了存在的意义。恰恰相反MHT的框架为深度学习提供了一个非常优的“外壳”让网络来负责特征的提取与判别让MHT来负责结构化推理和全局假设管理。我在某个密集目标追踪系统里最后采用的架构是这样的检测器输出目标框和外观特征向量外观特征进入MHT的代价计算模块同时轨迹的得分函数中的似然项不再是用手工设定的高斯似然而是换成了一个可学习的打分函数——基于一个多层感知机输入是“运动特征外观特征历史轨迹信息”输出是“关联成立”的概率。这个概率作为轨迹得分的增量底层仍然由MHT的假设树来维护整个解空间。这种混合架构的好处非常明显既保留了MHT的“暂缓决策、全局优化”结构优势又借助深度特征弥补了MHT在长期视觉特征上的短视。我比较推荐有充足标注数据集的小伙伴试试这条路。它是把经典理论和现代工具结合起来相当有效的一条路径。7. 自己的实战心得三个让我“悟了”的时刻7.1 第一件别把所有模糊帧都交给MHT求解最初我上MHT的时候以为“既然是全假设搜索那我每一帧都把所有模糊关联都丢给它去枚举它总会给我最优解”。结果程序跑起来的直观感受就是电脑风扇狂转、内存逐步爬升、跑十分钟已经卡到不行。后来我仔细分析了耗时分布发现真正需要MHT“延迟决策”的帧其实非常有限。大多数时刻目标分布稀疏、运动轨迹清晰直接用简单的最近邻关联就能得出和MHT同样正确的结果。我干脆加了一个“模糊度检测”模块如果当前帧的总体关联模糊度低于某个阈值就直接走贪心匹配只有模糊度高的时候才切换到MHT的完整假设分支。这个两阶段策略让系统在大多数帧上的计算量减少了90%同时遇到关键遮挡场景时又能启动完整的MHT能力效果和全时MHT几乎没有差异。7.2 第二件追踪器的输出要留“退路”还有一次让我印象深刻的经历是我在MHT系统上线后发现它偶尔会“犯错”——它的错误不是目标跟丢而是它把一条错误假设维持得太久甚至到了后期才在下一条证据出现后修正。这个“修正”过程本身没问题但由于MHT高层输出只会发布每帧的最优全局假设底层修正会导致输出ID在小范围内反复跳跃。后来我调整了输出策略MHT的最终决策层不直接输出每帧最优全局假设而是输出“当前最优全局假设中所有活跃轨迹的置信度”再由下游模块决定何时把这条轨迹“确认”为最终跟踪目标。换句话说我让MHT在“内部”可以大胆保留多条假设但在“对外”则保守发布只有某条轨迹的置信度连续多帧稳定居首时才会将其正式提交给业务层。这种“内紧外松”的设计显著削弱了ID切换给下游造成的干扰。7.3 第三件评价指标不要只看MOTA在做多目标追踪算法对比实验时大家最常看的指标是MOTAMulti-Object Tracking Accuracy。这个指标综合了漏检、误检和ID切换三个方面的表现。如果你只盯着MOTA去调MHT的参数你会发现它的提升空间相对有限甚至在某些数据集上不如简单方法。但我后来认识到MHT的很多价值并不体现在这个单一指标上而是体现在“轨迹连续性和平滑性”这些二级隐性指标上。比如我做视频分析项目时业务方最关心的并非ID切换计数——他们关心的是“同一个目标有没有被打断成两条轨迹”“车辆轨迹是否平滑连贯”。在这个维度上MHT的优势就体现得非常明显它输出的轨迹通常具备更长的连续性、更低的轨迹碎片率。后来我会在调参时额外关注“平均轨迹长度”和“轨迹碎片率”这两个指标而不是被MOTA这一个指标绑架。我建议做工程评估的时候从业务场景反向推导追踪指标别让它变成纯粹的数字游戏。第一性原则、延迟决策、全局最优——这三个词怎么听都像是一套学生时代崇拜的华丽理论。但在真正上手实现MHT、跑通仿真、又杀进真实场景之后我反而觉得它更像一位老派的匠人它不肯帮你做临时的决定它宁可让所有假设在时间里自行沉淀最后把最扎实的那一条轨迹呈现给你。每次我在密集场景里遇到ID切换比分都用MHT的机制来救场时我都能重新理解一次“不急于求成才能等到真相浮出水面”这句话。希望你读完这篇文章以后也能在MHT的复杂表象下看到它那份朴素的智慧——并且有勇气在你的下一个项目里试试它。