本文将带大家解析一下SORT和DeepSORT的基本思路，废话不多说，开始正题。

1. SORT

首先要说明一点，现在多目标跟踪算法的效果，与目标检测的结果息息相关，因为主流的多目标跟踪算法都是TBD（Tracking-by-Detecton）策略，这里不再赘述，有不懂的小伙伴可以去看本系列的第一篇领域综述。

在SORT论文的一开始，作者也强调了这一点。作者原话是说通过更换检测器可以将跟踪效果提高18.9个百分点。说这点是为了给做工程的朋友们一个启示，用再花哨的跟踪算法，有时也不如用针对性训练的检测器来的效果好。在实际工程中，为了提高多目标跟踪的效果，可以从检测器处多做文章（比如多收集一些对应任务的数据来训练检测器），跟踪的效果也会水涨船高。

抛开检测不谈，我们来看SORT的跟踪思路。SORT采用的是在线跟踪的方式，不使用未来帧的信息。在保持100fps以上的帧率的同时，也获得了较高的MOTA（在当时16年的结果中）。

 

                                                                SORT与当时State-of-the-art跟踪器效果对比

多目标跟踪中SORT算法思想理解流程：

在跟踪之前，对所有目标已经完成检测，实现了特征建模过程。 
1. 第一帧进来时，以检测到的目标初始化并创建新的跟踪器，标注id。 
2. 后面帧进来时，先到卡尔曼滤波器中得到由前面帧box产生的状态预测和协方差预测。求跟踪器所有目标状态预测与本帧检测的box的IOU，通过匈牙利指派算法得到IOU最大的唯一匹配（数据关联部分），再去掉匹配值小于iou_threshold的匹配对。 
3. 用本帧中匹配到的目标检测box去更新卡尔曼跟踪器，计算卡尔曼增益、状态更新和协方差更新，并将状态更新值输出，作为本帧的跟踪box。对于本帧中没有匹配到的目标重新初始化跟踪器。

其中，卡尔曼跟踪器联合了历史跟踪记录，调节历史box与本帧box的残差，更好的匹配跟踪id。

SORT的贡献主要有三：

• 利用强大的CNN检测器的检测结果来进行多目标跟踪
• 使用基于卡尔曼滤波（Kalman filter）与匈牙利算法（Hungarian algorithm）的方法来进行跟踪
• 开源了代码，为MOT领域提供一个新的baseline

现在看可能不觉得有什么，思路并不新奇也并不复杂，但在当时还是作出很大的贡献的，有力推动了MOT的发展。

其中卡尔曼滤波（Kalman filter）与匈牙利算法（Hungarian algorithm）对于大家来说可能是两个新名词。先简单解释一下，匈牙利算法是一种寻找二分图的最大匹配的算法，在多目标跟踪问题中可以简单理解为寻找前后两帧的若干目标的匹配最优解的一种算法。而卡尔曼滤波可以看作是一种运动模型，用来对目标的轨迹进行预测，并且使用确信度较高的跟踪结果进行预测结果的修正，是控制领域常用的一种算法。有熟悉无人机飞控算法的小伙伴应该会对这个感到很亲切。

可能初次接触的小伙伴还不是非常理解，不用担心，我们存疑，后文还会更详细地讲到。

---

至于具体的跟踪过程，SORT在以往二阶段匹配算法的基础上进行了创新。

以往二阶段匹配算法是先使用匈牙利算法对相邻帧之间的目标进行匹配生成很多tracklets，之后使用这些tracklets进行二次匹配，以解决遮挡等问题引起的轨迹中断。但这种二阶段匹配方式弊端也很明显，因为这种方式先天地要求必须以Offline的方法进行跟踪，而无法做到Online。

SORT将这种二阶段匹配算法改进为了一阶段方法，并且可以在线跟踪。

具体而言，SORT引入了线性速度模型与卡尔曼滤波来进行位置预测，在无合适匹配检测框的情况下，使用运动模型来预测物体的位置。

在数据关联的阶段，SORT使用的依旧是匈牙利算法逐帧关联，不过作者还引入了IOU（Intersection-Over-Union）距离。不过SORT用的是带权重的匈牙利算法，其实就是KM算法，用IOU距离作为权重（也叫cost矩阵）。作者代码里是直接用sklearn的linear_assignment实现，有兴趣的话也可以去看看这个函数的实现细节，我下一篇文章会稍微讲讲匈牙利算法和KM算法的原理，这里不懂可以先存疑。并且当IOU小于一定数值时，不认为是同一个目标，理论基础是视频中两帧之间物体移动不会过多。作者在代码中选取的阈值是0.3，

不过我个人在实验中对这一点不是完全认同，虽然两帧之间物体的运动量可能不大，但由于检测器自身检测结果不准，目标框偏移可能较大，还是会造成IOU过小，这时再用论文中这种方法，会导致误判引起的轨迹中断。具体案例在MOT的DPM检测结果中很容易找到。说起DPM，真可谓是MOT研究者的梦魇了……衷心希望MOT19能抛弃DPM。

2. DeepSORT

一年之后，原团队发布了SORT的续作DeepSORT，到现在都有很多人在用这个跟踪器。

MOT数据集中的典型遮挡情形

 

整体框架没有大改，还是延续了卡尔曼滤波加匈牙利算法的思路，在这个基础上增加了Deep Association Metric。Deep Association Metric其实就是在大型行人重识别网络上学习的一个行人鉴别网络。目的是区分出不同的行人。个人感觉很类似于典型的行人重识别网络。输出行人图片，输出一组向量，通过比对两个向量之间的距离，来判断两副输入图片是否是同一个行人。

此外还加入了外观信息（Appearance Information）以实现较长时间遮挡的目标跟踪。

跟踪流程延续上作，在卡尔曼滤波的预测结果的基础上，继续使用了匈牙利算法进行目标分配，但在这个过程中加入了运动信息和外观信息。这个说起来简单，实现起来比较复杂，感兴趣的读者可以细看论文和代码。在这里就不赘述了。

其他方面没有太多变化，还是使用了标准的卡尔曼滤波和固定速度模型等来进行预测。

最终实现了较好的跟踪效果（MOTA61.4@MOT16），并且能够实时运行（40FPS）。

---

代码和论文可以在以下链接获得。感谢SpyderXu的整理。

DeepSort : Wojke, Nicolai and Bewley, Alex and Paulus, Dietrich "Simple Online and Realtime Tracking with a Deep Association Metric" [paper] [code] In ICIP 2017
Sort : Bewley, Alex and Ge, Zongyuan and Ott, Lionel and Ramos, Fabio and Upcroft, Ben "Simple Online and Realtime Tracking"[paper] [code] In ICIP 2016.
https://github.com/SpyderXu/multi-object-tracking-paper-list

这一篇和大家一起过了一遍SORT这个经典的算法，虽然思路并不复杂，但还是值得细细品味的。当然其中还有几点概念没有说清，下一篇将带大家继续深入。

下一篇将着重讲解MOT中常用的一些算法，比如匈牙利算法和KM算法等。打下一个良好的基础，才能走的更远，朋友们下篇见！