走进Deep Sort系列（三）--《DeepSORT-Simple Online and Realtime Tracking with a Deep Association Metric》翻译及理解

2019年7月14日：继续上一部分内容，完成了对《Multiple Object Tracking A Literature Review》综述的大概翻译，初步了解了多目标跟踪大概是干什么的，现在我们进行对deep sort这样一个知识的文献翻译，作为具体到某一种算法的入门，目标：了解 Sort 和deepsort 的内容，知道它的框架，流程。

文献名称：《DeepSORT-Simple Online and Realtime Tracking with a Deep Association Metric》

知乎最新阅读笔记：

https://www.zhihu.com/people/geng-yi-fei-24/posts

来源：https://arxiv.org/pdf/1703.07402.pdf

参考翻译https://blog.csdn.net/zjc910997316/article/details/83721573

参考大佬阅读记：https://www.cnblogs.com/yanwei-li/p/8643446.html

参考大佬笔记：https://blog.csdn.net/cdknight_happy/article/details/79731981

参考大佬笔记：https://www.bbsmax.com/A/xl56bOa15r/

知乎大佬借鉴：https://zhuanlan.zhihu.com/p/62858357 （sort与deep sort的关系与区别）

必备知识点：马氏距离离：https://blog.csdn.net/lzhf1122/article/details/72935323

COS距离　最小余弦距离：https://blog.csdn.net/lin00jian/article/details/51209715

匈牙利算法

融合度量的方式

KM滤波器

级联匹配决策

摘要

简单在线和实时跟踪(SORT)是一种注重简单、有效算法的多目标跟踪的实用方法。

为了提高排序的性能，本文对外观信息进行了集成。

由于这种扩展，我们能够通过更长时间的闭塞来跟踪对象，有效地减少了标识开关的数量。

在原始框架的精神下，我们将大量的计算复杂度放到了离线预训练阶段，在此阶段我们学习了大规模的人员再识别数据集上的深度关联度量。

在实时应用过程中，我们使用可视化外观空间中的***近邻查询***建立度量跟踪关联。

实验评估表明，我们的扩展减少了45%的身份交换机数量，在高帧率下实现了整体竞争性能

2019年7月15日：

1 引言

因为近年来的目标检测的进步，基于检测的跟踪已经在多目标跟踪领域成为了主要模式。在这种模式下，对象轨迹通常出现在一次处理整个视频批量的全局优化问题中。例如，流网络公式[1,2,3]和概率图形模型[4,5,6,7]已经成为这种类型的流行框架。

但是，由于批处理的原因，这些方法不适用于在线场景（流网络公式和概率图形模型），在这些场景中，目标ID必须在每个时间步骤中可用。更传统的方法是多假设跟踪(MHT)[8]和联合概率数据关联过滤器(JPDAF)[9]。「Multiple Hypothesis Tracking (MHT) [8] and the Joint Probabilistic Data Association Filter (JPDAF) [9].」这些方法在逐帧基础上执行数据关联。

在JPDAF中，单个状态假设是通过根据它们的关联可能性对单个测量值进行加权而产生的。

在MHT中，所有可能的假设都被跟踪，但是修改方案必须应用于计算的可跟踪性。

最近，这两种方法都在 tracking-by-detection 场景中被重新使用[10,11]，并显示出了良好的结果。然而，这些方法的性能增加了计算和实现的复杂性（JPDAF,MHT）。

简单的在线和实时跟踪(SORT)[12]是一个更简单的框架，它使用匈牙利方法在图像空间中执行卡尔曼滤波和逐帧数据关联，使用关联度量测量边界框重叠。这种简单的方法在高帧率下取得了良好的性能。在MOT challenge数据集[13]中，使用最先进的行人检测器[14]在标准检测中的平均排名高于MHT。这不仅强调了目标检测器性能对总体跟踪结果的影响，而且从实践者的角度来看，这也是一个重要的见解。

虽然在跟踪精度和精度方面获得了总体良好的性能，但SORT返回的身份交换机数量相对较高。这是因为所使用的关联度量仅在状态估计不确定性较低时才准确。因此，SORT在通过遮挡进行跟踪方面存在缺陷，因为它们通常出现在前端视图摄像机场景中。我们通过将关联度量替换为更合理的度量来克服这个问题它结合了运动和外观信息。

特别地，我们应用了一个卷积神经网络(CNN)，它被训练用来在一个大规模的人再识别数据集中辨别行人。通过对该网络的集成，我们提高了对遗漏和遮挡的鲁棒性，同时使系统易于实现、高效并适用于在线场景。我们的代码和预先训练的CNN模型被公开，以促进研究实验和实际应用开发。

2 使用深度关联度量的排序（SORT WITH DEEP ASSOCIATION METRIC）第二代sort

我们采用一种传统的单假设跟踪方法，采用递归卡尔曼滤波和逐帧数据关联。

在下一节中，我们将更详细地描述这个系统的核心组件。

2.1 跟踪处理和状态估计（Track Handling and State Estimation）

跟踪处理和卡尔曼滤波框架与[12]中的原始公式基本相同。我们假设有一个非常一般的跟踪场景，在这个场景中，摄像机是没有校准的，并且我们没有可用的自我运动信息。虽然这些情况对过滤框架构成了挑战，但它是最近在多个对象跟踪基准测试[15]中考虑的最常见的设置。因此,我们的跟踪场景是定义在八维状态空间(u,v,γ,h,ẋẏ,γ̇,ḣ)包含边界框的中心位置(u,v),长宽比γ,高度h,各自的速度在图像坐标。我们用标准卡尔曼滤波器与匀速运动和线性观测模型,我们把边界坐标(u,v,γ,h)作为直接观察对象的状态。

对于每一个轨迹k，我们计算自上次成功测量关联到ak后的帧数。此计数器在卡尔曼滤波预测期间递增，一旦当跟踪与测量相关联就重置为0。超过预先设定的最大年龄的轨迹被认为已经离开场景并从轨迹集中删除。

对新目标出现的判断则是: 如果某次检测结果中的某个目标始终无法与已经存在的追踪器进行关联，那么则认为可能出现了新目标。这些新的轨迹在它们的前三帧被分类为暂定的。

在此期间，我们期望在每个时间步骤中都有一个成功的度量关联。在前三个帧中没有成功关联到度量的跟踪被删除。

(My

目标的创建与移除

对每一个追踪目标，记录自其上一次检测结果与追踪结果匹配之后的帧数ak，一旦一个目标的检测结果与追踪结果正确关联之后，就将该参数设置为0。

如果ak超过了设置的最大阈值Amax，则认为对该目标的追踪过程已结束。

对新目标出现的判断则是，如果某次检测结果中的某个目标始终无法与已经存在的追踪器进行关联，那么则认为可能出现了新目标。

如果连续的3帧中潜在的新的追踪器对目标位置的预测结果都能够与检测结果正确关联，那么则确认是出现了新的运动目标；

如果不能达到该要求，则认为是出现了“虚警”，需要删除该运动目标。

My)

2.2 指派问题（Assignment Problem）

传统的解决检测结果与追踪预测结果的关联的方法是使用匈牙利方法。本文作者同时考虑了运动信息的关联和目标外观信息的关联。

1. 运动信息的关联：使用了对已存在的运动目标的运动状态的kalman预测结果与检测结果之间的马氏距离进行运行信息的关联。

   

   dj表示第j个检测框的位置，yi 表示第i个追踪器对目标的预测位置，Si表示检测位置与平均追踪位置之间的协方差矩阵。马氏距离通过计算检测位置和平均追踪位置之间的标准差将状态测量的不确定性进行了考虑。

   如果某次关联的马氏距离小于指定的阈值t(1) ，则设置运动状态的关联成功。使用的函数为

   

   ，作者设置t(1)=9.4877.

2. 当运动的不确定性很低的时候，上述的马氏距离匹配是一个合适的关联度量方法，但是在图像空间中使用kalman滤波进行运动状态估计只是一个比较粗糙的预测。特别是相机存在运动时会使得马氏距离的关联方法失效，造成出现ID switch的现象。因此作者引入了第二种关联方法，对每一个的检测块dj求一个特征向量ri，限制条件是∣∣ri∣∣=1

   作者对每一个追踪目标构建一个gallary，存储每一个追踪目标成功关联的最近100帧的特征向量。那么第二种度量方式就是计算第i个追踪器的最近100个成功关联的特征集与当前帧第j个检测结果的特征向量间的最小余弦距离。计算公式为：

   

   如果上面的距离小于指定的阈值，那么这个关联就是成功的。阈值是从单独的训练集里得到的。
3. 使用两种度量方式的线性加权作为最终的度量，

   

   ，只有ci,j位于两种度量阈值的交集内时，才认为实现了正确的关联。

   距离度量对短期的预测和匹配效果很好，但对于长时间的遮挡的情况，使用外观特征的度量比较有效。对于存在相机运动的情况，可以设置λ=0

   λ=0.

   在此设置中，仅在关联成本项中使用外观信息。然而，马氏门仍然被用来忽略不可行的分配基于可能的目标位置推断的卡尔曼滤波器。

2.3 级联匹配

在全局分配问题中，我们引入了一个级联方法来解决一系列子问题，而不是求解度量到跟踪的关联。要激发这种方法，请考虑以下情况：

当一个目标长时间被遮挡之后，kalman滤波预测的不确定性就会大大增加，因此，概率质量在状态空间中扩散，观测的似然值减小，状态空间内的可观察性就会大大降低。在理论上，关联度量应该通过增加测量到跟踪的距离来解释这种概率质量的扩展。与直觉相反，假如此时两个追踪器竞争同一个检测结果的匹配权，往往遮挡时间较长的那条轨迹因为长时间未更新位置信息，追踪预测位置的不确定性更大，即协方差会更大，马氏距离计算时使用了协方差的倒数，因此马氏距离会更小，因此使得检测结果更可能和遮挡时间较长的那条轨迹相关联，这种不理想的效果往往会破坏追踪的持续性。这么理解吧，假设本来协方差矩阵是一个正态分布，那么连续的预测不更新就会导致这个正态分布的方差越来越大，那么离均值欧氏距离远的点可能和之前分布中离得较近的点获得同样的马氏距离值。

所以，作者使用了级联匹配来对更加频繁出现的目标赋予优先权，具体的算法如下图：

级联匹配的核心思想就是***由小到大对消失时间相同的轨迹进行匹配，这样首先保证了对最近出现的目标赋予最大的优先权，也解决了上面所述的问题。***

在匹配的最后阶段还对unconfirmed和age=1的未匹配轨迹和检测目标进行基于IoU的匹配。这可以缓解因为表观突变或者部分遮挡导致的较大变化。当然有好处就有坏处，这样做也有可能导致一些新产生的轨迹被连接到了一些旧的轨迹上。但这种情况较少。

2.4 深度特征描述器

通过使用简单的最近邻查询而不需要额外的度量学习，我们的方法的成功应用需要在实际的在线跟踪应用程序之前离线训练一个良好的识别嵌入特性。为此，我们使用了一个CNN，它已经训练了一个大规模的人再识别数据集[21]，其中包含超过110万幅图像(1,261个行人)，使它非常适合在人跟踪上下文中进行深度学习。

我们网络的CNN架构如表1所示。综上所述，我们使用了一个宽频域的残差网络[22]，该网络由两个卷积层和六个残差块组成。在稠密层10中计算了128维的全局有限元图。最后的批处理和l2标准化将特性投射到单位超球面上，使其与余弦外观度量兼容。总的来说，网络有2,800,864个参数，在Nvidia GeForce GTX 1050 mobile GPU上，32个边界框的一次向前传递大约需要30 ms。因此，这个网络非常适合在线跟踪，只要有一个现代GPU可用。而我们培训程序的设计超出了这个范围在行人重识别数据集上离线训练残差网络模型。输出128维的归一化的特征。在GTX1050m显卡上，输入32个bounding box提取特征的时间约为30ms。预训练的模型和代码位于 https://github.com/nwojke/deep_sort 。

3 实 验总结

我们评估了我们的跟踪器在MOT16基准[15]上的性能。这个基准测试评估了七个具有挑战性的测试序列的跟踪性能，包括带有移动摄像机的前视图场景以及自上而下的监视设置。作为对我们的跟踪器的输入，我们依赖于Yu等人提供的detec- tions。他们在一组公共和私有数据集上训练了一个更快的RCNN，以提供出色的性能。为了进行公平的比较，我们对相同的检测结果重新进行排序。

评价测试序列进行了使用λ= 0和Amax = 30帧。与[16]一样，检测的阈值为0.3。我们的方法的其余参数是在基准提供的单独的训练序列上找到的。评估按以下指标进行:

作者使用《Poi:

Multiple object tracking with high performance detection and appearance feature》文章训练的高性能faster rcnn模型进行检测。检测的置信度阈值设置为0.3。λ=0,Amax=30

λ=0,A

max=30。

和sort对比，好处是：

♦ 减少了45%的ID switch；

♦ 结合了深度外观信息，对遮挡目标的追踪效果大大提升；

♦FP的升高很多，文章中提出这主要是由于静态场景中detection的错误以及过长的允许丢失的track age所导致的（相对于SORT只用相邻帧进行匹配来说，Deep SORT允许高达30帧的丢失，而Kalman的等速运动模型没有改变，这主要造成了FP的升高）。

♦ 20Hz，依旧实用；

♦达到了state-of-art online tracking的效果。

结论

我们提出了一种扩展，可以通过预先训练的关联度量对包含外观信息的排序。由于这种扩展，我们能够通过更长的闭塞时间跟踪，使SORT成为最先进的在线跟踪算法的强大竞争对手。然而，该算法实现起来仍然很简单，并且可以实时运行。