简介

SORT是一个快速的在线的多目标跟踪（MOT）算法，基于TBD（Traking-by-Detection）的策略，这些特性决定了SORT实用性非常好，SORT的论文是SIMPLE ONLINE AND REALTIME TRACKING，发表于2016年，SORT在当时对MOT领域起到了基石般的作用。

SORT原理

主要贡献

SORT的主要贡献有两个：

• 证明了一个性能优异的检测器，对于多目标跟踪算法的重要性；
• 提出了一种基于卡尔曼滤波和匈牙利算法的实用跟踪方法；

是不是乍一看上去，其实没啥东西，确实是这样，SORT的论文也只有5页╮(￣▽ ￣)╭，首先SORT提出一个好的目标检测器对跟踪的影响非常大，对于TBD策略的MOT算法，这好像是一句废话，但是SORT给出了定量实验，又因为这和SORT的原理没什么关系，所以在这里地方我们简单提一下：

在上面的实验中，跟踪器有两个，分别是MDP和SORT；检测器有三个，分别是ACF，ZF为主干的Faster R-CNN和VGG16为主干的Faster R-CNN。首先是上图中的蓝色框，VGG16为主干的Faster R-CNN检测器的性能是最优的，所以在这个基础上SORT得到了最高的MOTA，跟踪器换成了MDP时也是一样的结果。这就证明了一个性能优异的检测器对目标跟踪的重要性。 除此之外，还可以关注下红色框，在ID swtich方面，SORT的表现并不好，这是SORT很大的一个缺点。

估计模型

SORT首先会对每一个目标进行建模，这个模型是独立于其他目标和拍摄的镜头，建模的目的是要对这个目标在下一帧的位置进行预测，目标的状态模型表示为：X=[u,v,s,r,u˙,v˙,s˙]T

u和v代表的水平和垂直的目标中心像素位置, s和r代表面积和长宽比。这里的长宽比被假设成为一个常数，也就是说对于同一个目标r是不变的。 这个状态模型里包含了两个部分，一个是描述目标的 [u,v,s,r]用来描述一个目标在图像中的Bounding Box， [u˙,v˙,s˙]则是目标的速度，速度的单位是帧，所以目标在下一帧图像中的Bounding Box就可以被估计出来。 这个估计模型是在迭代中不断更新的，具体是如果检测器的检测框关联到了之前的跟踪目标，那么估计模型 [u,v,s,r]会根据检测框做更新，同时根据卡尔曼滤波算法重新求解 [u˙,v˙,s˙]，如果检测器的检测框没有关联到某个跟踪目标，那么估计模型就不会更新。 这样一来，貌似估计模型已经能知道目标在一下帧的Bounding Box，这都不是目标跟踪了，简直实现了目标的追踪，那还要检测做什么？ 这是因为估计模型是非常不准的，或者说只对下一帧准一些，由于线性的假设，如果每次使用估计出来的结果更新状态模型，那么和实际值就会越偏越多，所以估计模型需要根据关联情况，用实际检测到的值去更新。

数据关联

在当前帧，估计模型给出了上一帧每一个需要被跟踪的目标的估计结果，检测器给出了所有检测到的目标结果，这两组数据其实构成了二分图（二部图），求解二分图的最大匹配问题，就是SORT的数据关联要做的事，这个问题经典的方法就是匈牙利算法。 SORT为匈牙利算法引入了一个权重（也叫cost矩阵），所以SORT中的匈牙利算法其实就是KM算法，这个引入的权重就是图像交并比：IOU（Intersection-Over-Union），这是因为在视频流中，相隔帧的目标IOU是比较大的。无论是哪一种，在这里我们都先将它看做一个黑盒，黑盒的输入是二分图，输出是关联的结果。

创建和销毁跟踪ID

对于一个连续的视频流，总会有新的ID进入和旧的ID的离开的情况，此时需要对应的创建新的ID跟踪和销毁旧的跟踪ID：

• 创建ID 如果检测器检测到的一个框和所有的跟踪目标的IOU小于阈值，那么就认为一个新的ID需要被创建。这个阈值在文中为0.3。
• 销毁ID 如果一个跟踪目标在连续T帧内都没有被关联到，那么就销毁这个ID。

实验结果

我们着重观察下上表中的加粗部分和红色框，会发现都是Online的方法，SORT在很多指标上也不是最优的，最常用的MOTA在所有Online方法中最优，并且SORT的ID switch是所有Online最差的，这也验证了开始时的观点。由于SORT对遮挡情况没有做任何处理，一旦发生了遮挡，检测器无法找到目标，估计模型也就不会更新，当这个ID再次出现时，估计值和检测值偏差过大导致无法关联，所以会创建一个新的ID。

但是谈到实用性，还需要考虑速度的问题，SORT是当时将准度和速度结合的最好的方法，SORT在一块i7CPU+16G内存的配置上可以达到260Hz。