原文链接、代码以及在MOT Challenge上的成绩：https://motchallenge.net/tracker/MHT_DAM_17

---

摘要：

本文回顾了经典的基于tracking-by-detection框架的多假设跟踪算法（MHT），而MHT之所以奏效，很大程度取决于它只维持了一小个潜在假设的列表，这有助于精确地进行目标检测。本文还证明了90年代的经典MHT算法在标准测试数据集上能与目前一流的方法媲美。为了更好地利用MHT来探索高阶信息，本文还为每个跟踪假设采用了一种在线训练外观模型的方法。通过最小正则二乘法框架，每个假设分支只需要一些额外的操作就可以高效地学习到外观模型。

---

一、介绍与相关工作：

MHT最早起源于1979年由Reid提出：为每个候选目标建立一个潜在跟踪假设的树，这样可以为数据关联问题提供一个系统的解决方法。计算每一个跟踪的概率，然后选出最有可能的跟踪组合。因为在计算概率时，整个跟踪假设都会被考虑到，所以MHT理论上适用于高阶信息例如长期的运动和外观模型。

过去的MHT（本质是BFS算法），常受限于剪枝算法的速度、准确性以及搜索空间的结合性增长。针对这些问题，本文主要工作是摘要中提到的部分。相关工作是最大权重独立集（MWIS）、tracking-by-detection等。

---

二、多假设跟踪：

k：帧
Mk：k帧中检测到的目标个数
ik：k帧中的检测到的一个目标
i1,i2,…,ik：k帧中的跟踪假设
zi1,i2,…,ik：判断是否有一个跟踪假设在最后决定中被选中

MHT的关键策略是延迟数据关联的决策，通过保持多个假设的**，直到解决数据关联歧义问题。MHT维持多个跟踪树，每个跟踪树代表从一个观测中产生的所有假设，如Fig.1c。在每一帧，跟踪树根据观测进行更新，每个跟踪都会得到分数。最好的无冲突跟踪集（最佳全局假设）可以由最大权重独立集找出，如Fig.2a。之后，那些偏移太多的分支会从跟踪树中被裁剪出来。最后，算法进入下一帧。

2.1 跟踪树构造和更新：

一个跟踪树保存着由一个观测产生的多个假设。在每一帧，每有一个新的观测产生就会有一个新的跟踪树被构造，表示着这个观测对应一个新目标进入场景的概率。之前已存在的树也需要更新。当跟踪假设在观测的gating范围时，为这个观测对应的树增支。ps：常常会增加一个多余的分支，用于记录丢失的目标。

2.2 Gating

基于动态估计，gating范围常用在跟踪假设上，用来预测下一个检测目标在哪个位置出现。

xl k：在k时刻，第l个跟踪的可能位置

设变量xl k服从基于均值^xl k，协方差∑l k的正态分布，而均值和协方差都由卡尔曼滤波获得。使用观测位置yik和预测位置^xl k的的马氏距离d^2决定是否使用新预测目标ik来更新特定的轨迹：

其中dth表示距离阈值，决定了gating范围，如Fig.1b。

2.3 跟踪得分

第k帧第l个跟踪得分如下公式：

wmot：控制位置yik变量的分布权重
wapp：外观Xik变量的分布权重
sl mot(k)：动态得分
sl app(k)：外观得分

根据log likelihood ratio(LLR)公式，将从同一目标产生的观测序列和从背景产生的观测序列代入有：

因式分解得：

在t时刻中，跟踪假设的每个位置测量概率近似高斯分布，有：

其中，V是测量空间、图像区域。

外观跟踪分数定义如下：

与动态得分因式分解步骤相同：

给定先验观测i1:t-1，定义后验事件：观测it在第l个跟踪中有：

其中F(·）表示外观特征Xit的分类分数，分类权重由Xi1:t-1学习而来。

利用常量c1计算背景假设的后验概率：

当Sl (k) > 0时，表示一个跟踪假设更像是真的目标；当Sl (k) < 0时，表示更可能是错误的警示。因此可以递归得到：

其中△Sl mot(k)和△Sl app(k)分别表示在k时刻两类分数的增量，PD和PFA分别表示检测概率和错误警示概率（实际上都很小）。

由(5),(8),(9)式可以得到：

ps：分数会随着跟踪假设根据检测更新而更新，用于记录丢失目标的跟踪假设将会被移出假设空间。

2.4 Global Hypothesis Formation

这里只列出主要公式，具体作用可以参照Fig.2a：

2.5 跟踪树裁剪

为了防止跟踪假设指数级增长，采用标准N-scan裁剪方法，如Fig.2b。除此之外，还设置阈值Bth。当分支数超过Bth时，只根据跟踪分数保留前Bth个分支。当使用MHT-DAM，如Table.1，外观模型使得我们可以进行更多的剪枝操作，使得不用提高跟踪假设数量也可以有显著的更大的gating区域。另外，当外观模型分数F(Xit) < c2时，设置△Sapp(t) = -∞可以防止进行剪枝。这样就可以减小不必要的剪枝，提高效率。

三、在线外观建模

由于基于动态的约束（匀速、线性等不鲁棒，所以使用多路输出正则最小二乘法框架（multioutput regularized least squares framework）来学习目标外观模型。作为一种在线学习策略，对于漂移现象，它会比局部外观匹配表现得稳定，因为它将从多帧得到的多外观都考虑其中。

3.1 Multi-output Regularized Least Squares
主要回顾了多路输出正则最小二乘法的原理、公式和步骤。

3.2 将MORLS应用到MHT
主要讲述了如何将MHT中使用到的跟踪假设、跟踪树等代入上述公式。

最后利用卷积神经网络对每个检测框提取4096维特征，然后再用PCA降维。在本文实验中主要采用前256个主成分。

ps:最后有关于如何提升裁剪效率，以及实验结果分析对比，有兴趣的读者可以自行查看原文以及MOT官网的贴图，谢谢~