论文解读sortdeep-sort多目标跟踪算法(代码片段)

前言

基于视觉的目标跟踪在智能监控、动作与行为分析、自动驾驶等领域都有重要的应用。例如，在自动驾驶系统中，目标跟踪算法要对运动的车、行人、其他物体的运动进行跟踪，对它们的未来的位置、速度等信息作出预测。

多目标跟踪，Multiple Object Tracking，并不是简单的多个单目标跟踪，因为它不仅涉及到各个目标的持续跟踪，还涉及到不同目标之间的身份识别、自遮挡和互遮挡的处理，以及跟踪和检测结果的数据关联等。

一、Sort算法

Sort算法，是一种简单的在线实时多目标跟踪算法。它以“每个检测”与“现有目标的所有预测边框”之间的交并比IOU 作为前后帧之间目标关系的度量指标。

Sort算法，使用卡尔曼滤波器预测当前位置，通过匈牙利算法关联预测框和目标。

检测框 可以用Faster R-CNN、SSD、YOLO等目标检测模型，进行检测目标的位置，生成检测框。（本文以Faster R-CNN为例，用它作为目标检测的主干网络）

预测框 使用卡尔曼滤波器预测的。

Sort算法整体流程

 首先使用Faster R-CNN得到检测框，卡尔曼滤波根据上一帧的轨迹对当前轨迹进行预测，然后使用匈牙利算法将此预测和检测框进行关联，关联成功的检测框就是所需的跟踪框。

一方面，关联失败的轨迹预示着该跟踪对象可能已经离开观察区域。若在接下来的x帧中仍然未取得关联，则取消对此对象的跟踪，由于动态模型运用的是简单恒速模型，x较大会造成预测偏差过大，但是处于减少目标ID切换不是首先目标的考虑，取x为1。

另一方面，关联失败的检测框预测这可能出现了新的跟踪对象，若在接下来的几帧中仍有此检测框出现，则为此新跟踪对象分配新的跟踪框，此处的几帧可以通过设置阈值进行控制。

优点：Sort目标跟踪算法速度很快；在没有遮挡的情况下准确度很高。

缺点：它对物体遮挡几乎没有处理，导致ID switch 次数很高；在有遮挡情况下，准确度很低。

针对Sort的缺点，研究者们提出了Deep-Sort目标跟随算法。

二、Deep-Sort算法

Deep-Sort是基于Sort目标跟踪进行的改进，它引入深度学习模型，在实时目标跟踪过程中，提取目标的外观特征进行最近邻近匹配。这样可以改善有遮挡情况下的目标追踪效果；同时，也减少了目标ID跳变的问题。

核心思想：使用递归的卡尔曼滤波和逐帧的数据关联。Deep-Sort算法把检测框和预测框的IOU情况输入到匈牙利算法中，同时把目标的外观信息加入到匹配计算之中，进行线性分配来关联帧间ID。

检测框 可以用Faster R-CNN、SSD、YOLO等目标检测模型，进行检测目标的位置，生成检测框。

预测框 使用卡尔曼滤波器预测的。

Deep-Sort算法整体流程

 上图中分别从状态估计、轨迹处理、级联匹配几个方面来对算法进行说明。下面简单讲一下各个关键步骤。

2.1 状态估计

Deep Sort的轨迹处理和卡尔曼滤波框架与Sort算法中基本一致。用一个8维空间表示轨迹在某时刻的运动状态  ，其中(u, v) 是目标框的中心坐标；r是长宽比；h表示高度。

 4个变量表示在图像坐标系中的速度信息，也表示 的对应变化率。我们假设短时间内为匀速直线运动并用4个参数表示轨迹当前的实时状态。

使用一个基于“常量速度模型” 和 “线性观测模型”的标准卡尔曼滤波器进行目标运动状态的预测，预测结果为。

2.2 轨迹处理

对每个轨迹看来说，我们记录它从上一次匹配成功到目前经历的帧数ak，匹配识别时累加1，当该轨迹匹配成功是ak归于0。

当ak大于aMAX时则删除该轨迹，认为轨迹已结束，即该目标离开视线。

对新目标出现的判断则是，当前帧检测无法匹配到适合的轨迹时则认为可能为出现的新目标，根据该检测框信息生成新轨迹，但标记为“潜在轨迹”。当该轨迹接下来连续3帧匹配成功时，将其转正，改为“确认跟踪”；否则认为是“虚警”，删除该潜在轨迹。

2.3 匹配问题

Deep Sort是把检测框和预测框的IOU情况作为输入，同时考虑了运动信息的关联和目标外观信息的关联，采用匈牙利算法，融合度量的方式计算检测和跟踪轨迹之间的匹配程度，输出检测框和预测框的匹配结果。

即：匹配已更新预测的轨迹卡尔曼滤波状态 与 新一帧由检测算法得到的检测框。这里用匹配的损失矩阵，同时考虑了运动信息的关联 和 目标外观信息的关联。

运动信息的关联

我们用马氏距离（Mahalanobis Distance）表示运动距离，马氏距离是常被用于计算两个未知样本的相似度。

独立于测量尺度得到两个服从同一分布并且其协方差矩阵S的随机变量之间的差异程度。不受量纲的影响，排除变量之间的相关性的干扰，考量了位置的接近程度。

 上面公式中，位置均由八个参数表示，表示第i个追踪器对目标的位置预测， 表示第j个检测框的位置，以空间距离为相似度量匹配轨迹与检测。 表示检测位置与平均追踪位置之间的协方差矩阵。

这里马氏距离可以估计出检测框离轨迹预测目标位置相对于轨迹本身协方差偏移的单位数。

 当运动信息的不确定较低时，马氏运动距离是一个很好的关联信息因为卡尔曼滤波得到是一个理想转态的预测位置，但一些运动信息不确定性较高的场景特征是相机存在运动时会使得预测位置不准确以至于运动信息计算的马氏距离失效，造成ID漂移。此时需要引入第二种关联即目标改观信息的关联。

目标外观信息的关联

Deep Sort 采用了经过大规模人员重新识别数据集训练的 Cosine 深度特征网络，该数据集包含 1,261 位行人的 1,100,000 多张图像，使其非常适合在人员跟踪环境中进行深度度量学习。

Cosine 深度特征网络使用了宽残差网络，该网络具有 2 个卷积层和 6 个残差块，L2 归一化层能够计算不同行人间的相似性，以与余弦外观度量兼容。通过计算行人间的余弦距离，余弦距离越小，两行人图像越相似。Cosine 深度特征网络结构如下图所示。

使用 Cosine 深度特征网络参数，将每个检测框内图片压缩为最能表征图片特异信息的128维向量，并归一化后得到外观描述向量。

 这里轨迹使用外观特征向量库保存近期匹配成功的外观特征向量，并在匹配时去余弦距离中最小距离可以适应短时遮挡情况。比如：当前被遮挡，则使用以往外观信息判别，只要进30帧中有出现过较好的匹配，则匹配上该轨迹和检测，较好地减少了遮挡问题。

2.4 级联匹配

当物体被长时间遮挡时，卡尔曼滤波器不能对目标状态准确预测。因此，概率质量在状态空间中散布，并且观察似然性的峰值降低。但是，当两个轨迹竞争同一检测结果时，马氏距离会带来较大的不确定性。因为它有效地减少了任何检测的标准偏差与投影轨迹均值之间的距离，而且可能导致轨迹碎片化增加和不稳定的轨迹。因此，Deep Sort引入了级联匹配，来更加频繁出现的目标赋予优先权，具体算法伪代码如下：

2.5 Deep Sort开源代码

 基于YOLO的Deep-Sort算法，网络上有不同版本的开源代码，下面三个分别是基于YOLOv5、YOLOv4、YOLOv3 实现的Deep Sort 多目标跟踪系统。

【1】YOLOv5+Pytorch+Deep Sort

开源代码地址：Yolov5_DeepSort_Pytorch 

YOLOv5生成的检测结果是一系列在 COCO 数据集上预训练的对象检测架构和模型，被传递到Deep Sort多目标跟踪对象算法。

开发环境：

matplotlib>=3.2.2
numpy>=1.18.5
opencv-python>=4.1.2
Pillow
PyYAML>=5.3.1
scipy>=1.4.1
torch>=1.7.0
torchvision>=0.8.1
tqdm>=4.41.0
seaborn>=0.11.0
pandas
easydict

模型效果：

 【2】YOLOv4+TF+Deep Sort

开源代码地址：Deep-SORT-YOLOv4-tf

开发环境：

# $ conda create --name <env> --file <this file>
# platform: linux-64
imutils=0.5.3=pypi_0
keras=2.3.1=pypi_0
matplotlib=3.2.1=pypi_0
numpy=1.18.4=pypi_0
opencv-python=4.2.0.34=pypi_0
pillow=7.1.2=pypi_0
python=3.6.10=h7579374_2
scikit-learn=0.23.1=pypi_0
scipy=1.4.1=pypi_0
tensorboard=2.2.1=pypi_0
tensorflow=2.0.0=pypi_0
tensorflow-estimator=2.1.0=pypi_0
tensorflow-gpu=2.2.0=pypi_0

模型效果：

 【3】YOLOv3+Pytorch+Deep Sort

开源代码地址：Deep-Sort_pytorch-yolov3

开发环境：

python 3 (python2 not sure)
numpy
scipy
opencv-python
sklearn
torch >= 0.4
torchvision >= 0.1
pillow
vizer
edict

模型效果：

参考文献

[1] 包俊，董亚超，刘宏哲.基于Deep_Sort的目标跟踪算法综述.北京联合大学北京市信息服务工程重点实验室.

[2] 朱镇坤，戴德云，王纪凯，陈宗海.基于FasterR_CNN的多目标跟踪算法设计.中国科学技术大学自动化系.

[3] 谢佳形.拥挤场景下视频多目标跟踪算法研究.浙江大学.

[4] 谷燕飞.基于改进YOLO_V3+Deepsort多目标跟踪系统的研究与实现.辽宁大学.

本文只供大家参考和学习，谢谢。