本文首发于微信公众号【DeepDriving】，欢迎关注。
SORT是2016年发表的一篇文章《Simple Online and Realtime Tracking》中提出的一个经典的多目标跟踪算法，该算法结合常用的卡尔曼滤波器和匈牙利匹配算法实现了一个简单的在线多目标跟踪框架。由于其超简单的设计，SORT可以以260 Hz的更新速率实现多目标跟踪，远超当时其它的目标跟踪算法。
论文地址：https://arxiv.org/abs/1602.00763
代码地址：https://github.com/abewley/sort
SORT是一种采用Tracking-by-Detection策略的目标跟踪算法，也就是说算法的输入数据来源于目标检测器，其本身是不参与目标检测过程的。作者在论文里对比了以Faster-RCNN和ACF在PASCAL VOC数据集上的行人检测结果作为MDP和SORT跟踪算法的输入，得出的结论是目标检测结果的好坏直接决定了目标跟踪的性能，使用最好的目标检测器会得到最好的跟踪效果。
这也告诉我们一个道理：解决问题要从源头开始。如果不从源头提升目标检测算法的性能，花再多时间去提升目标跟踪的性能可能都是徒劳。
为了在帧与帧之间传递目标的状态信息，作者对每个目标采用一个独立于其他目标和相机运动的线性恒速模型进行建模，每个目标的状态被建模为一个向量：
x = [ u v s r u ˙ v ˙ s ˙ ] T \mathbf{x} =\begin{bmatrix} u & v & s & r & \dot{u} & \dot{v} & \dot{s} \end{bmatrix}^T x=[uvsru˙v˙s˙]T
其中 u u u和 v v v分别表示目标中心点的横、纵坐标， s s s和 r r r分别表示目标边界框的面积和长宽比， u ˙ \dot{u} u˙、 v ˙ \dot{v} v˙和 s ˙ \dot{s} s˙分别代表 u u u、 v v v和 s s s的变化率。在跟踪过程中，当一个检测结果被关联到一个目标的时候，检测到的边界框（观测值）就被用来更新卡尔曼滤波器的状态，变化率 u ˙ \dot{u} u˙、 v ˙ \dot{v} v˙和 s ˙ \dot{s} s˙也可以通过卡尔曼滤波器推导出来。如果没有检测结果与目标进行关联，那么目标的状态则只是简单地通过卡尔曼滤波器进行预测得到（没有观测值进行校正）。
如果对卡尔曼滤波器不了解，可以看一下我之前整理的资料，里面有卡尔曼滤波器的详细推导过程：
给已存在的目标分配当前帧检测到的边界框时，目标在当前帧中的边界框是基于之前的状态预测出来的。所有当前帧检测的边界框与已存在目标做预测得到的边界框通过计算它们之间的IOU来求代价矩阵，然后用匈牙利算法求解最优匹配结果。
如果检测边界框与预测边界框匹配成功且它们之间的IOU值大于阈值
I
O
U
m
i
n
IOU_{min}
IOUmin，那么就认为它们是一对有效的匹配对，否则是无效的。匹配成功后，就可以基于检测的边界框对目标状态进行更新了。
作者发现采用IOU作为距离度量进行匹配可以隐式地解决由于传递目标引起的短期遮挡的问题。具体来说，当一个目标被另一个物体覆盖时，检测器只能检测到这个遮挡物体而检测不到被遮挡物体，因为IOU距离有利于具有相似比例的检测框。这样的话遮挡物体可以正常被分配检测框去更新状态，而被遮挡物体则不会受误分配带来的影响，因为当前没有检测框会分配给它。
如果对IOU不了解，可以参考我之前的文章：
当一个目标出现在图像中的时候，我们需要为其创建一个全局唯一的身份标识（ID）；反之，当目标消失的时候就要销毁它的跟踪信息。
对于一个检测的边界框，如果它与所有当前跟踪目标的IOU小于阈值
I
O
U
m
i
n
IOU_{min}
IOUmin，那么就认为它还是一个从未被跟踪的目标，需要为它创建一个卡尔曼跟踪器。跟踪器的初始状态向量由检测框的几何信息得到，变化率设置为零。由于此时变化率是无法观测的，所以变化率的协方差设置为一个比较大的值（10000），表示其不确定度非常大。另外，一个跟踪器创建后并不是马上生效而是需要经历一个“试用期”，在这个过程中，跟踪的目标连续几帧都与检测的边界框匹配成功才会认为这个跟踪器是有效的，这样做的目的是为了抑制对假阳性的检测结果进行跟踪。
如果连续
T
L
o
s
t
T_{Lost}
TLost帧都没有与之匹配的检测框，那么这个跟踪器的信息就会被删除。这么做有两个目的，一是不让大量的跟踪器占用内存，另外一个目的是减少因长时间没有检测框进行校正而仅靠预测得到的跟踪结果（这种预测是极不准确的）。在论文中，作者出于两个原因将
T
L
o
s
t
T_{Lost}
TLost设置为1：
SORT算法的处理流程非常简单，感兴趣的可以去看源码。下图是我整理的算法流程图：
对当前帧的检测结果Detections和已存在的目标Tracker使用匈牙利算法进行匹配会出现三种情况：
Detection未匹配成功，那么就以该边界框的几何信息为初始状态去创建一个Tracker;Detection与Tracker匹配成功，那么就以该检测结果为观测值更新Tracker的状态；Tracker，前面说到
T
L
o
s
t
T_{Lost}
TLost设置为1，也就是只要一帧没匹配上该Tracker就会被删除。SORT的代码里创建了一个类KalmanBoxTracker用于对卡尔曼滤波器的状态进行管理，卡尔曼滤波器使用的是filterpy.kalman包中的KalmanFilter，官方文档地址为：https://filterpy.readthedocs.io/en/latest/kalman/KalmanFilter.html。
卡尔曼滤波器的状态向量 x \mathbf{x} x和观测向量 z \mathbf{z} z分别为
x = [ u v s r u ˙ v ˙ s ˙ ] T \mathbf{x} =\begin{bmatrix} u & v & s & r & \dot{u} & \dot{v} & \dot{s} \end{bmatrix}^T x=[uvsru˙v˙s˙]T
z = [ u v s r ] T \mathbf{z} =\begin{bmatrix} u & v & s & r \end{bmatrix}^T z=[uvsr]T
卡尔曼滤波器初始化时需要初始化下面几个矩阵：
def __init__(self,bbox):
# 创建卡尔曼滤波器时需设置状态向量和观测向量的维度
self.kf = KalmanFilter(dim_x=7, dim_z=4)
# 状态转移矩阵
self.kf.F = np.array([[1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1]])
# 观测矩阵
self.kf.H = np.array([[1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0]])
# 测量噪声协方差矩阵
self.kf.R[2:,2:] *= 10.
# 状态协方差矩阵，变化率不可观测所以设置一个较大值表示其较大的不确定性
self.kf.P[4:,4:] *= 1000.
self.kf.P *= 10.
# 过程噪声协方差矩阵
self.kf.Q[-1,-1] *= 0.01
self.kf.Q[4:,4:] *= 0.01
#状态向量前面四个值用bbox初始化，变化率设置为0
self.kf.x[:4] = convert_bbox_to_z(bbox)
滤波器生命周期的管理是通过几个变量来实现的，KalmanBoxTracker创建的时候会初始化几个变量：
self.time_since_update = 0
self.hits = 0
self.hit_streak = 0
如果Tracker匹配成功，就会更新这几个变量的状态:
def update(self, bbox):
self.time_since_update = 0
self.hit_streak += 1
如果Tracker做了一次预测，同样会更新这几个变量的状态:
def predict(self):
if (self.time_since_update > 0):
self.hit_streak = 0
self.time_since_update += 1
time_since_update表示距离上一次带观测值更新滤波器状态过去了多久，hit_streak表示Tracker连续匹配成功并更新的次数，一旦调用predict()函数对当前帧做了预测，time_since_update就加一，表示其已经对当前帧做过一次预测了。
在算法的处理类Sort中，会对Tracker的这几个变量做判断：
Tracker，需要判断其是否还在“试用期”，只有连续几帧都匹配成功才能使用它的跟踪信息：if (trk.time_since_update < 1) and
(trk.hit_streak >= self.min_hits or self.frame_count <= self.min_hits):
ret.append(np.concatenate((d, [trk.id+1])).reshape(1, -1))
Tracker未匹配成功，该Tracker就会被删除：if (trk.time_since_update > self.max_age):
self.trackers.pop(i)
SORT目标跟踪算法仅使用卡尔曼滤波器和匈牙利算法解决帧与帧之间的状态预测和数据关联问题，跟踪的效果高度依赖于目标检测结果的好坏，算法整体设计非常简单，在速度和精度上取得较好的平衡，主要体现一个“快”字。当然，速度提升必然导致精度损失，SORT的缺点在于仅仅使用物体的边界框进行跟踪而忽略其表面特征，在复杂的场景中效果会比较差。另外，SORT没有目标重识别过程，一旦目标丢失就需要重新创建跟踪器去更新状态（一帧未匹配成功就需要重新跟踪），导致同一目标的ID频繁变换。
YOLOv3+SORT实现行人检测与跟踪的效果可以看下面的视频：
行人目标检测与跟踪