基础知识

匹配算法：

• SORT算法： Kalman滤波， 匈牙利算法(匹配算法)， 马氏距离(损失指标)；

• Kalman滤波是通过对上一帧每个检测对象进行预测，得到一个BBox_predicted，然后再将predicted与当前帧的检测对象BBox_measure进行匹配，这样的话就能固定ID了；
  如果不用Kalman滤波，将当前帧的BBox_measure与上一帧的BBox_measure’进行匹配？

追踪为什么需要卡尔曼滤波？

通常要对一些事物的状态去做估计，为什么要做估计呢？因为我们通常无法精确的知道物体当前的状态。为了估计一个事物的状态，我们往往会去测量它，但是我们不能完全相信我们的测量，因为我们的测量是不精准的，它往往会存在一定的噪声，这个时候我们就要去估计我们的状态。卡尔曼滤波就是一种结合预测（先验分布）和测量更新（似然）的状态估计算法；其二，若出现视频中目标运动过快，前后两帧中同一个目标运动距离很远，那么这种直接匹配的方式就会失效。因此，可以通过现预测目标下一帧出现的位置，然后与检测的位置进行匹配关联，这样就不会由于速度太快而产生误差。 参考1

匈牙利算法

匈牙利算法只是尽可能地多匹配，而对于准确度没有很好的约束；

马氏距离

欧式距离是度量两点间的距离方法，而马氏距离针对的是多变量情况下的协方差距离。

即当量纲不同，考虑各种特性之间的联系下的一种距离尺度。由公式可知，欧式距离除以了一个协方差距离。

• 方差：方差是标准差的平方，而标准差的意义是数据集中各个点到均值点距离的平均值。反应的是数据的离散程度。
• 协方差： 标准差与方差是描述一维数据的，当存在多维数据时，我们通常需要知道每个维数的变量中间是否存在关联。协方差就是衡量多维数据集中，变量之间相关性的统计量。比如说，一个人的身高与他的体重的关系，这就需要用协方差来衡量。如果两个变量之间的协方差为正值，则这两个变量之间存在正相关，若为负值，则为负相关。
• 协方差矩阵： 当变量多了，超过两个变量了。那么，就用协方差矩阵来衡量这么多变量之间的相关性。

余弦距离

余弦相似度的取值范围是[-1,1]，相同两个向量的之间的相似度为1。

余弦相似度定义公式：

c
o
s
(
A
,
B
)
=
A
⋅
B
∥
A
∥
2
∥
B
∥
2
cos(A,B) = \frac{A\cdot{B}}{\lVert{A}\rVert_2\lVert{B}\rVert}_2
cos(A,B)=∥A∥2​∥B∥A⋅B​2​
余弦距离定义：

d
i
s
t
(
A
,
B
)
=
1
−
c
o
s
(
A
,
B
)
=
∥
A
∥
2
∥
B
∥
2
−
A
⋅
B
∥
A
∥
2
∥
B
∥
2
dist(A,B) = 1 - cos(A,B) = \frac{{\lVert{A}\rVert_2\lVert{B}\rVert_2}-A\cdot{B}}{\lVert{A}\rVert_2\lVert{B}\rVert_2}
dist(A,B)=1−cos(A,B)=∥A∥2​∥B∥2​∥A∥2​∥B∥2​−A⋅B​

DeepSORT

SORT

SORT算法是通过检测的测量值和卡尔曼滤波得到的预测值进行IOU匹配。

对于没有匹配到的detections，创建新的trackers；

对于成功匹配的detections，对kalman的trackers进行更新；

对于未成功匹配的trackers，则进行剔除。

DeepSORT

algorithm base

• 对于每个tacker，有三种状态，分别是tentative，confirmed， unconfirmed;其中，第一种状态为每个tacker的初始化状态；
• tentative转换为confirmed状态，需要连续匹配上n_init次；
• 对于每一个tracker，有time_since_update参数，每次与detection关联更新后重置为0；
• 级联匹配根据time_since_update来作为优先级，先匹配那些一直得到更新的tracker，对于状态为confirmed，但没有得到更新的tracker(tracker每predict一次，time_since_update增加一次),也能使之得到更新，只是优先级靠后；即根据time_since_update参数来控制更新的顺序。由小到达对消失时间相同的轨迹进行匹配。
• 当time_since_update>max_age(70)时，则将confirmed状态改变为deleted状态；
• unconfirmed trackers和 unmatched trackers 一起组成iou candicates，与unmatched detections进行IOU匹配；

cost matrix

• 使用平方马氏距离来度量tracker和detection之间的距离；实际代码中没有用到运动信息（保留）
• 使用cosine距离来度量表观特征之间的距离；
• 综合匹配度通过运动模型和外观模型加权得到。

其中$\lambda$是一个超参数，在代码中默认为0。作者认为在摄像头有实质性移动的时候这样设置比较合适，也就是在关联矩阵中只使用外观模型进行计算。但并不是说马氏距离在Deep SORT中毫无用处，马氏距离会对外观模型得到的距离矩阵进行限制，忽视掉明显不可行的分配。

Mahalanobis Distance/Cosine Distance

两者分别针对运动信息和外观信息的计算。马氏距离就是加强版的欧式距离。它实际上是规避了欧氏距离中对于数据特征方差不同的风险，在计算中添加了协方差矩阵，其目的就是进行方差归一化，从而使所谓的“距离”更加符合数据特征以及实际意义。马氏距离是对于差异度的衡量中，的一种距离度量方式，而不同于马氏距离，余弦距离则是一种相似度度量方式。前者是针对于位置进行区分，而后者则是针对于方向。换句话说，我们使用余弦距离的时候，可以用来衡量不同个体在维度之间的差异，而一个个体中，维度与维度的差异我们却不好判断，此时我们可以使用马氏距离进行弥补，从而在整体上可以达到一个相对于全面的差异性衡量。而我们之所以要进行差异性衡量，根本目的也是想比较检测器与跟踪器的相似程度，优化度量方式，也可以更好地完成匹配。

代码在linear_assaignment._match.gated_metric下，将外观余弦距离和马氏距离进行了封装。（保留意见）。

Cascaded match

级联匹配是Deep SORT区别于SORT的一个核心算法，致力于解决目标被长时间遮挡的情况。为了让当前Detection匹配上当前时刻较近的Track，匹配的时候Detection优先匹配消失时间较短的Track。

当目标被长时间遮挡，之后卡尔曼滤波预测结果将增加非常大的不确定性(因为在被遮挡这段时间没有观测对象来调整，所以不确定性会增加)， 状态空间内的可观察性就会大大降低。在两个Track竞争同一个Detection的时候，消失时间更长的Track往往匹配得到的马氏距离更小， 使得Detection更可能和遮挡时间较长的Track相关联，这种情况会破坏一个Track的持续性，这也就是SORT中ID Switch太高的原因之一。

---

使用级联匹配算法，是为每个追踪器设定一个time_since_update参数。如果跟踪器完成匹配并进行更新，那么参数会重置为0，否则就会+1。实际上，级联匹配换句话说就是不同优先级的匹配。在级联匹配中，会根据这个参数来对跟踪器分先后顺序，参数小的先来匹配，参数大的后匹配。也就是给上一帧最先匹配的跟踪器高的优先权，给好几帧都没匹配上的跟踪器降低优先权（慢慢放弃）。

在级联匹配中，通过根据每个tracker的time_since_update是否等于max_age level来控制track更新的顺序；即有限匹配距上次出现间隔短的目标；

IOU match

在级联匹配后的IOU匹配中，更新对象是unmatch_trackers和unconfirmed trakcers，且since_time_update=1，即仅仅对上一帧的tracker进行iou匹配；

现在处理上面未参与外观匹配的新的轨迹，即uncofirmed tracks，同时把那些虽然是confirmed track,但外观匹配仅在上一帧没有成功的track放进来;那些长时间没有被匹配成功的track不用iou匹配，因为长时间没有匹配到，人早就走掉了，iou重合率也会非常低，iou比较高的也不太可能是同一个人.

Steps

说明：在deep sort代码中，tracker.py主要是匹配算法；track为每一个tracker的类属性声明；

1. 检测器得到每一帧的检测结果，生成detections；
2. 对self.tracks()进行卡尔曼滤波预测，self.tracks()存放的是状态为confirmed的track；第一帧为空；
3. 接着进行匹配，匹配对象为self.tracks()和detection，先进行级联匹配，然后对
4. 基于当前帧的detections，校正与其关联的上一帧trackers的状态，得到一个更精确的结果，即使用卡尔曼滤波预测前一帧中的tracks在当前帧的状态：；
5. 将预测后的trakers与当前帧的detecion进行匹配:级联匹配和IOU匹配；IOU匹配对象为级联匹配结束后的unmatched_tracks和self.tracks()中未确定的track(确定状态需要连续n_init帧匹配成功)；初始帧为空；
6. 将匹配结果进行整理，匹配成功(matchs)的卡尔曼更新，匹配未成功的(unmatched_tracks)进行标记删除；对于剩下下的detections(unmatched_detections)进行track初始化，即生成track，并加入到self.tracks()中，但状态依然为tentative；
7. 接着开始第二帧，同理。

总而言之，DeepSORT的级联匹配主要是为了解决SORT算法中，对于长时间遮挡目标IDs较高的问题；因为SORT匹配原则是基于IOU；而级联匹配就是根据特征的余弦距离，然后经过马氏距离进行门限，根据since_time_update的数目来进行级联匹配，也就是说，除了优先考虑最近一帧的tracker，还考虑之前帧的tracker，而这个值最大默认设置为30；然后再将没有匹配成功的tracker和detections进行IOU匹配。

代码

min_cost_matching: 根据不同度量尺寸来计算cost_matrix, 然后调用linear_assignment()来进行匈牙利匹配算法；distance_metric是度量函数，为余弦距离函数或IOU距离函数；

参考：

多目标跟踪DeepSORT

Deep SORT多目标跟踪算法代码解析(上) - 知乎 (zhihu.com)

分步解析deepsort代码

马氏距离与欧氏距离

*多目标跟踪入门篇(1)：SORT算法详解

DeepSort论文阅读总结

DeepSORT多目标算法笔记

SORT 多目标跟踪算法笔记

匈牙利算法

ByteTrack

在byte之前, 利用上游检测结果送入卡尔曼滤波进行融合处理;在对于遮挡的情况下,检测结果置信度较低, 会直接排除不进行后者的滤波;
而byte认为, 遮挡只是短期的,在目标检测中丢弃置信度的结果无可厚非;但是在追踪中,这就是先验信息,仅凭置信度阈值就丢弃显得不够合理;

以上图举例的话，这里我们假设把阈值设置为0.3，在第一帧和第二帧中都可以将图片中的三个行人正确识别，但当第三帧中出现了遮挡现象，其中一个行人的置信度则变为0.1，这样这个行人则会在遮挡的情况下，失去了跟踪信息，但对与目标检测来说，他确实被检测出来了，只是置信度较低而已。

Byte算法则是用来解决如何充分利用，由于遮挡导致置信度变低的得分框问题。

同时ByteTrack没有用到ReID模型, 作者解释是因为第一点是为了尽可能做到简单高速，第二点是发现在检测结果足够好的情况下，卡尔曼滤波的预测准确性非常高，能够代替 ReID 进行物体间的长时刻关联。实验中也发现加入 ReID 对跟踪结果没有提升。
ref：
多目标跟踪（三） ByteTrack —— 利用低分检测框信息Byte算法
目标跟踪之 MOT 经典算法：ByteTrack 算法原理以及多类别跟踪

匹配流程

bytetrak匹配流程如下：

1. 将高置信度的检测结果与confirmed tracked_stracks进行匹配,得到matches,u_track, u_detections;
2. 将低置信度的检测结果second_detections与第一步得到u_track且状态为Tracked的tracker进行IOU匹配,得到新的matches,u_track,u_detections_second; 因为只有之前确定的tracker与低置信度的结果匹配才有意义;
3. 将第一步的高置信度的u_detecions与unconfirmed tracks进行匹配,得到最终的matches, u_unconfirmed, u_detection;对于此步得到的u_detetion进行track初始化;u_track进行mark lost处理; 这一步不同于deepsort需要连续几帧(3)匹配才能将状态从unconfirm状态转换为confirm状态，而是直接使用IOU匹配;如果能匹配上，则是confirmed,否则直接进行track初始化;
4. unconfirmed track状态都是Tracked, 但是不一定全部都是is_activated;当frame-id不是第一帧时, tracker不是activated;所以对于中途新建的tracker, 默认状态都是unconfirmed, unconfirmed筛选如下:

    for track in self.tracked_stracks:
    if not track.is_activated:
        unconfirmed.append(track)
    else:
        tracked_stracks.append(track)