本文首发于公众号【DeepDriving】，欢迎关注。
简介
上篇文章介绍了多目标跟踪算法 SORT，该算法虽然速度很快，但是也存在 ID切换频繁等问题。针对这些问题，作者时隔一年后又在文章《 Simple Online and Realtime Tracking with a Deep Association Metric》中提出了 DeepSORT算法。与 SORT仅仅采用边界框的 IOU作为匹配时的距离度量不同的是， DeepSORT采用一种更可靠的距离度量方法，该方法结合了物体的运动和外观信息，其中外观信息是通过一个在大规模行人重识别数据集上离线训练的 CNN网络提取的。基于这些改进， DeepSORT提升了跟踪算法的鲁棒性，将 ID切换率减少了 45%，并同时保持容易部署、高效运行的优点。
论文地址：https://arxiv.org/abs/1703.07402
代码地址：https://github.com/nwojke/deep\_sort
具体实现
状态估计
跟 SORT一样， DeepSORT还是对每个目标采用线性恒速模型进行建模并用标准卡尔曼滤波器进行状态估计，不过状态向量由 7维变成了 8维：
相应的，观测向量变为：
其中表示物体边界框的中心点，和分别表示边界框的长宽比和高度，表示它们在图像中的变化率。
对于每个 track，都要计算其距离上一次成功与检测结果匹配的那帧与当前帧的差，在代码中是用 time_since_update变量来表示。这个变量在调用卡尔曼滤波器的 predict()函数进行预测后会加一，在 track与检测结果匹配成功并更新状态后则会被清零。如果这个值大于预设的阈值，那么就认为目标已经消失，这个 track会被删除。
如果当前帧的检测结果 detection未能与任何已存在的 track匹配成功，那么就为其创建一个新的 track。这个新的 track在被创建后的三帧内都处于未确定状态，在此期间如果每帧都有检测结果与之匹配成功才会把它的状态转为确定态，否则将会被删除。
track的状态转移过程如下图所示：
匹配问题
运动信息度量
为了将运动信息运用到匹配问题中，作者采用马氏距离（ Mahalanobis distance）来度量卡尔曼滤波器预测的状态与新到达的测量值之间的匹配程度：
其中表示第个 track，表示第个 detection，表示二者的协方差矩阵。作为此距离度量的指示器，当马氏距离小于等于阈值时被赋值为 1否则置为 0，论文中阈值设置为 9.4877。
当运动的不确定性较低时，马氏距离是一个比较合适的数据关联度量指标。但是，卡尔曼滤波器预测的状态只是在图像空间中对物体位置的粗略估计，尤其是没有考虑相机自身运动会在图像平面中引入快速位移，因此马氏距离不适合作为处理有遮挡情况下的度量指标。为此，作者加入第二个度量指标，即外观信息。
外观信息度量
对于每个检测边界框，为其计算外观描述子并且。对于每个 track，则为其保留个关联的外观描述子
把表示第个 track和第个 detection在外观空间的最小余弦距离作为第二个度量指标，定义如下：
同样的，为该度量指标设置一个二值指示器：
当余弦距离小于等于阈值时，被赋值为 1否则置为 0。
综合度量
结合运动信息和外观信息，最终的距离度量指标为马氏距离和余弦距离的加权和：
每个指标的权重由超参数控制，作者在实验中发现在存在相机自身运动的场景中将设置为 0会有比较好的结果。这样设置相当于只有外观信息参与计算匹配过程中的代价矩阵，但是这并不表示马氏距离没有用，因为 track和 detection之间的匹配是否有效还需要判断两个度量距离指示器的乘积是否为 1:
相当于一个门控信号，只有两个距离都在各自阈值范围内该信号才有效。因此，马氏距离仍然被用于抑制一些不合理的匹配。具体来说，即使 track和 detection因外观相似匹配成功，如果它们的马氏距离大于阈值，这个匹配还是会被认为是无效的。
级联匹配
当一个物体被长时间遮挡，由于没有新的测量值进行校正，卡尔曼滤波器对其位置的预测会越来越不准确，不确定度会越来越大。一般凭直觉会认为，数据关联度量指标应该会增加测量到跟踪( measurement-to-track)的距离来解释这种概率质量的扩散。但是与这种直觉相反的是，当两个 track竞争同一个 detection时，马氏距离会更有利于匹配具有更大不确定性的 track（这里为什么会这样我看了原文的解释也没看懂）。因此，作者引入了一个级联匹配操作，在数据关联中优先考虑出现更频繁的目标。级联匹配的伪代码如下：
对于处于未确定状态 track和未匹配成功且 time_since_update=1的 track，还会对它们进行一次与 SORT中一样的基于 IOU的匹配，这有助于解决由于外观特征突然有大的改变而导致匹配失败的情况，从而增强算法的鲁棒性。
DeepSORT的算法流程大致如下：
外观特征提取
为了提取行人目标的外观特征，作者设计了一个 CNN模型并在一个大规模的行人重识别数据集上进行离线训练，训练好的模型被用于在线跟踪时提取目标的外观特征。这个 CNN网络包含 2个卷积层和 6个残差网络块，输出一个 128维的向量用来表示目标的外观特征，具体结构如下：
最后，需要对该网络输出的 128维向量使用了 L2归一化来将特征映射到单位超球面上，以便计算余弦距离来度量相似度。
总结
DeepSORT在 SORT的基础上进行了扩展，采用物体的外观信息作为匹配时的距离度量，并在跟踪流程中加入级联匹配方法，大大提升了算法的鲁棒性。