一文轻松入门DeepSort

1.背景

Deepsort是目标检测任务的后续任务，得益于Yolo系列的大放异彩，DeepSort目标追踪任务的精度也不断提高，同时，DeepSort属于目标追踪任务中的多目标追踪，即MOT（Multiple Object Tracking，MOT），追踪多个目标的位置。

2.引言-Sort算法

sort算法是deepsort的前身，本身引入了卡尔曼预测和匈牙利匹配算法。

sort算法的匹配过程如下所示：
1.对于之前的每一个track，利用卡尔曼算法预测出下一帧的情况（包括八个部分：x,y,h/w,h,4个速度量）与detect到的每一个框进行IOU匹配。

2.基于IOU矩阵，进行匈牙利匹配，对于匹配的结果有以下三种

（1）有剩余的track未被匹配到，直接删除这些track；

（2）有检测框没和之前的track相匹配，即当前的yolo框出的先验框找不到前几帧的任一图像进行追踪，则将此框作为新的track加入到下一次的匹配当中；

（3）对于所有匹配到的track，继续加入下一次的track进行下一次的追踪

这里的匈牙利匹配，上图中是IOU Match那里，即基于IOU距离构造的成本矩阵对Detection和Track作匹配，SK-learn库的linear_assignment_和scipy库的linear_sum_assignment都实现了这一算法，只需要输入cost_matrix即代价矩阵就能得到最优匹配。

sort的缺点是，没有引入REID深度学习特征，REID是通过预训练好的模型进行特征提取，deepsort中。

3.deepsort算法

3.1卡尔曼滤波

定义：利用线性系统状态方程，通过系统输入输出观测数据，对系统状态进行最优估计的算法。由于观测数据中包括系统中的噪声和干扰的影响，所以这一最优估计也可看作是滤波过程。

tips：（1）线性系统，意思是卡尔曼滤波必须一帧一帧的进行检测，不能跳帧，否则无法进行估计。

（2）分predict和update两部分。predict基于先验的model（状态转移信息），如小车运动方程等，从k-1时刻根据model predict k时刻的状态和协方差；update是基于当下k时刻传感器（观测信息），对prediction进行更新。每一帧做完都要返回来更新之前的卡尔曼增益矩阵。

3.2匈牙利算法

给出代价矩阵后，借助匈牙利算法即可计算出类似于预测框与检测框之间最小距离的对应关系

具体计算过程如下

代价矩阵包括REID和运动信息构建的代价矩阵，这个代价矩阵位于级联匹配之中。

代价矩阵还包括IOU匹配，位于IOU Match中。

3.3 级联匹配

输入为：

        1、基于第k-1帧由卡尔曼滤波predict到的当前第k帧所有confirmed状态的track；

        2、当前第k帧的所有detection

输出为：

        1、match上的detection、track；

        2、没有match上的track；

        3、没有match上的detection。

大概工作流程为，deepsort在第一步会先进行级联匹配，级联匹配时，会优先使用到匹配之前已经匹配过的且按照匹配次数降序排列帧，对于连续匹配3帧的track，会将其置为confirmed状态，对于之前已经匹配的confirmed状态帧，若连续70帧未匹配，将被剔除，只有连续匹配3帧的track才会进入级联匹配，否则会直接进入IOU匹配。

REID和卡尔曼估计在级联匹配过程中生效，对于在级联匹配中未匹配的检测框将和未确认的track一起放入IOU匹配中。

级联匹配按照代价矩阵的距离进行计算（检测框与track之间的代价距离），其中设置有门单元，即对于计算出的代价矩阵中的值，若代价距离大于门限值，则不认为他们直接有关系，在代码中会对这个距离加上一个极小数，然后将大于门限值的值进行剔除。

3.4REID

行人重识别，利用预训练的模型，来提取当前yolo检测到的bbox和当前所有track的128维特征，对于每一个track，不仅检测其上一帧的特征，会保留大概前100帧中计算出的每一帧的特征，bbox的特征与这100帧的特征列表全部进行一次比较，形如[128维向量，128维向量，128维向量，...，128维向量]，选择余弦相似度最大的一帧的特征。

4.追踪任务流程

对于第一帧，不会有track，也即不会有框出现

对于第二帧，还没有confirmed的track，所以不会进入级联匹配，会直接进入到IOU匹配，利用卡尔曼预测的八个值【x,y,w/h........】和检测框构建代价矩阵，然后继续更新卡尔曼参数。

注意，每一次对于匹配到的track，都要更新其卡尔曼参数

代价矩阵的构建包括两大部分：

第一大部分位于级联匹配：

1.REID构建的对于bbox的128维向量和confirmed的track的前100帧的128维向量构建的余弦距离的代价矩阵；（deepsort的核心）

2.卡尔曼估计得到的运动信息，即八个状态量【】和当前框bbox检测到的运动信息，即bbox的八个状态量之间的差异构建的代价矩阵

第二大部分为IOU 匹配

利用检测出的框detect和后验估计，即卡尔曼估计得到的框计算其iou距离，构建代价矩阵。