文章标题：《Simple Online and Realtime Tracking with a Deep Association Metric》
论文地址：https://arxiv.org/pdf/1703.07402.pdf
参考匈牙利算法： https://zhuanlan.zhihu.com/p/90835266
马氏距离：https://blog.csdn.net/lzhf1122/article/details/72935323
deepsort代码详解帮助理解： https://blog.csdn.net/sgfmby1994/article/details/98517210
1.摘要
??基于多目标跟踪的研究问题，发现SORT算法存在ID switch和长时间遮挡的目标容易丢失的问题，于是提出了deepsort，发现集成外观信息可以提升SORT的性能。该算法将大部分计算复杂性置于离线前训练阶段，在此阶段，我们在大规模的人员再识别数据集上学习深度关联度量。在online应用阶段，使用可视化外观空间中的近邻查询建立度量跟踪关联(数据关联：是指测量和预测之间的关联，用关联好之后的结果来更新卡尔曼滤波器）。实验评估表明，我们的扩展减少了45%的身份交换机数量，在高帧率下实现了整体竞争性能。
2.引言
??随着目标检测的迅速进展，tracking-by-detection已经成为多目标跟踪中的主流算法。在这种模式下，对象轨迹通常出现在一次处理整个视频批量的全局优化问题中。
例如，流网络公式和概率图形模型已经成为这种类型的流行框架。但是，由于批处理的原因，这些方法不适用于在线场景（流网络公式和概率图形模型），在这些场景中，目标ID必须在每个时间步骤中可用。更传统的方法是多假设跟踪(MHT)和联合概率数据关联过滤器(JPDAF)。这些方法在逐帧基础上执行数据关联。在JPDAF中，单个状态假设是通过根据它们的关联可能性对单个测量值进行加权而产生的。在MHT中，所有可能的假设都被跟踪，但是剪枝方案必须应用于计算的可跟踪性。最近，这两种方法都在 tracking-by-detection 场景中被重新使用，并显示出了良好的结果。然而，这些方法的性能增加了计算和实现的复杂性（JPDAF,MHT）
??SORT算法是一个更简单主流的框架，基于卡尔曼滤波，使用匈牙利方法进行匹配，匹配的度量标准（association metric）是bounding box的IOU。
??本文是基于SORT的一个改进，SORT存在大量的ID switches问题，原因是SORT的association metric只在状态估计不确定性较低时才准确。因此，SORT在遇到遮挡进行跟踪方面存在缺陷，我们通过将关联度量（association metric）替换为一个结合运动和外观信息的更多信息的度量方式(也就是下文提到的匈牙利匹配的代价矩阵）来克服这个问题（Insight）
3.核心思想
??算法的核心思想还是用一个传统的单假设追踪方法，方法使用了递归的卡尔曼滤波和逐帧的数据关联。
3.1 轨迹处理和状态估计
??跟踪处理和卡尔曼滤波框架与SOT中的原始公式基本相同，我们假设一个非常普遍的跟踪场景，摄像机没有校准，我们没有可用的自我运动（ego-motion）信息。它是最近的多个目标跟踪基准测试中考虑的最常见的设置。因此,我们的跟踪场景是定义在八维状态空间包含了bounding box中心点坐标，长宽比，高度，以及他们4个图像坐标系中的速度信息。我们使用标准的卡尔曼过滤，具有恒速运动和线性观测模型。
??对于每个轨迹k（我理解每个轨迹实际就是指对应的那个卡尔曼滤波器），我们会进行一个计数。
重点！！！计数器具体执行方法和轨迹（track）处理步骤总结：
- 卡尔曼滤波每预测一次，计数器加1
- 当track和detect匹配上时，计数器清0
- track的状态有confirmed和unconfirmed（tentative），已经confirmed的track，如果连续max_age帧没匹配到detect，才会被移除。
- 只有unconfirmed track连续和detect匹配达到3次，才可从unconfirmed状态转为confirmed状态，unconfirmed状态的track有一次没匹配上就会被删除。
- 未确认的track不会被画在图上，所以第一帧只能看到检测结果。第一帧都是利用检测结果创建对应的track。
- 对于unmatched的detect要为其创建新的tracker。
3.2 分配问题（用匈牙利算法进行分配，创新点是其中的代价矩阵计算结合了运动特征和外观特征）
??解决预测的卡尔曼状态和新测量之间的关联的一种传统方法是建立一个可以使用匈牙利算法解决的分配问题。在这个问题的描述中，我们通过结合两个合适的度量来整合运动信息和外观信息。
??马氏距离（运动特征）：为了合并运动信息，我们使用预测的卡尔曼状态和新的测量值之间的马氏距离的平方（为什么用马氏距离不用欧式距离： 它和欧氏距离是一种距离度量方式，主要针对位置进行区分，如果去掉马氏距离中的协方差矩阵，就退化为欧氏距离。马氏距离的目的就是把方差归一化，使得特征之间的关系更加符合实际情况）：
其中上面公式中，dj表示第j个检测框的位置，yi表示第i个追踪器对目标的预测位置，Si表示检测位置与平均追踪位置之间的协方差矩阵，马氏距离的计算是利用检测结果和跟踪结果的：【center x,center y,aspect ration,height】进行计算。如果某次关联的马氏距离小于指定的阈值t(1)，则设置运动状态的关联成功。作者设置阈值t(1)=9.4877。这里作者利用逆卡方分布（下面公式），想象有一个概率密度函数，给定样本数据值为9.4877，看作横坐标，纵坐标为概率密度，给定一个置信区间如0.95（具体自己设置），从而求出bi,j(1)作为一个阈值区间，直接排除在区间外的关联。
??外貌特征： 当运动的不确定性很低的时候（也就是满足卡尔曼滤波算法的假设，即所有物体的运动具有一定规律，且没有什么遮挡），上述的马氏距离匹配是一个合适的关联度量方法，但是在图像空间中使用kalman滤波进行运动状态估计只是一个比较粗糙的预测。特别是未记入相机的运动在成像平面上引入快速位移会使得马氏距离的关联方法失效，造成出现ID switch的现象。因此引入外貌特征。计算外貌特征会计算检测和预测的特征向量的余弦距离。同样也会同马氏距离一样引入一个阈值区间bi,j(2)来卡掉一部分根本不可能的关联，t(2)阈值由训练集中得到
余弦相似度和余弦距离公式理解：
??最后使用两种度量方式的线性加权作为最终的组合关联代价矩阵（见下图公式5），在进行匹配时，只有当两个指标（马氏距离和余弦距离）都满足各自阈值条件的时候才进行融合（见公式6），意思是它们的距离只有位于两种度量阈值的交集内时【即在bi,j(1)和bi,j(2)分别的阈值区间内】，才认为是可接受的。
距离度量（马氏距离：衡量的是空间各点的绝对距离，跟各个点所在的位置坐标直接相关）对短期的预测和匹配效果很好。但对于长时间的遮挡的情况，使用外观特征的度量（余弦距离：衡量在方向上的差异）比较有效。
3.3 级联匹配（目的是解决不同优先级的匹配，只有confirmed状态的track才能进行级联匹配，unconfirmed的只能采用SORT算法中的IOU匹配）
??级联匹配换句话说就是不同优先级的匹配。在级联匹配中，会根据这个参数来对跟踪器分先后顺序，参数小的先来匹配，参数大的后匹配。通过循环实现，参数越小循环顺序越靠前，每层循环实现一批匹配。也就是给上一帧最先匹配的跟踪器高的优先权，给好几帧都没匹配上的跟踪器降低优先权（慢慢放弃）。因为当一个目标长时间被遮挡之后，kalman滤波预测的不确定性就会大大增加，状态空间内的可观察性就会大大降低。假如此时两个追踪器竞争同一个检测结果的匹配权，往往遮挡时间较长的那条轨迹的马氏距离更小，使得检测结果更可能和遮挡时间较长的那条轨迹相关联，这种不理想的效果往往会破坏追踪的持续性。马氏距离更倾向于较大的不确定度，因为它有效地减小了任何检测相对于投影跟踪平均值的标准偏差的距离（insight）
3.4 深度特征描述器
??这一部分是ReID的模块，在行人重识别数据集上离线训练残差网络模型。输出128维的归一化的特征。作者将所有confirmed的追踪器每次完成匹配对应的detection的feature map存储进一个list。存储的数量作者使用budget超参数（100帧，自己设置）进行限制，从而我们在每次匹配之后都会更新这个feature map的list，比如去除掉一些已经出镜头的目标的特征集，保留最新的特征将老的特征pop掉等等。这个特征集在进行余弦距离计算的时候将会发挥作用。 实际上，在当前帧，会计算第i个物体跟踪的所有Feature向量和第j个物体检测之间的最小余弦距离，取最小值作为该track和检测结果的计算值。