传统追踪算法：SORT 和 DeepSORT

SORT

simple online and realtime tracking 核心是卡尔曼滤波和匈牙利算法

  • 卡尔曼滤波作用：用当前的一系列运动变量去预测下一时刻的运动变量

  • 匈牙利算法：解决分配的问题，将检测框和卡尔曼滤波的框做分配，让卡尔曼预测的框找到和自己最匹配的检测框，达到追踪的效果。

  • IOU 作为前后帧间目标关系度量指标。

工作流程

image-20211215144135190

匈牙利算法分配之后有三个结果，第一种是 track失配（前一帧 18 ，当前帧 16，变少）；第二种detection 失配（目标变多）；刚好能被match 上。

结果：快速却不是那么准。

This paper explores a pragmatic approach to multiple object tracking where main focus is to associate objects effeciently for online and realtime applications.

Despite only using a rudimentary combination of familiar techniques such as the Kalman Filter and Hungarian algorithm for the tracking componets, this approach achieves an accuracy comparable to state-of-the-art onlein trackers. Furthermore, due to the simplicity of our tracking method, the tracker updates at a rate of 260 Hz which is over 20x faster than other state-of-the-art trackers.

使用的主要技术：Kalman Filter 和 Hungarian algorithm （匈牙利算法）

跟踪算法主要是处理 frontal-view camera 算法。

SORT (Simple Online and Realtime Tracking) 最大的特点就是就有 Faster R-CNN 的目标检测方法，利用卡尔曼滤波算法 + 匈牙利算法，极大提高了多目标跟踪的速度，同时达到了 SOTA 的准确率。

你可以在任何含有不确定信息的动态系统中使用卡尔曼滤波，对系统下一步去的走向做出有根据的预测，即使伴随着各种干扰，卡尔曼滤波总是能指出真实。

卡尔曼滤波，简单来说就是基于传感器的测量值来更新预测值，以达到更精确的估计。

在目标跟踪中，需要估计 track 的两种状态：

  • 均值（Mean）：表示目标的位置信息，由bbox的中心坐标 (cx, cy)，宽高比r，高h，以及各自的速度变化值组成，由8维向量表示为 x = [cx, cy, r, h, vx, vy, vr, vh]，各个速度值初始化为0。
  • 协方差（Covariance）：表示目标位置信息的不确定性，由8x8的对角矩阵表示，矩阵中数字越大则表明不确定性越大，可以以任意值初始化。

初始化的时候，假设卡尔曼滤波是一个均速模型。（参考代码中的状态转移矩阵 F， dt是当前帧和前一帧之间的差）

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

缺陷：

受遮挡情况影响较大，会有大量的的 ID 切换

一旦物体收到遮挡或者其他原因没有检测到，卡尔曼滤波预测的状态信息将无法和检测结果匹配，那么该追踪片段将会提前结束。遮挡结束后，车辆检测可能有被继续执行，那么 SORT 只能分配给物体一个新的 ID 变好，表示一个新的追踪片段的开始。

DeepSORT 的解决方案

需要利用到前面已经检测到的物体的外观特征（假设之前被检测的物体的外观特征都被保存下来了），那么当物体收到遮挡后到遮挡结束，我们能够利用之前保存的外观特征分配该物体受遮挡前的ID编号，降低ID切换。

We overcome this issue by replacing the association metric with a more informed metric that combines motion and appearance information.In particular,we apply a convolutional neural network (CNN) that has been trained to discriminate pedestrians on a large-scale person re-identification dataset.

DeepSORT

simple online and realtime tracking with a deep association metric

多目标追踪的主要步骤

  • 获取原始视频帧
  • 利用目标检测器对视频帧中的目标进行检测
  • 将检测到的目标中框中的特征提取出来，该特征包括表观特征（方便特征对比，避免 ID switch）和运动特征（方便卡尔曼滤波对其进行预测）
  • 计算前后两帧目标之间的匹配程度（利用匈牙利算法和级联匹配），为每个追踪到的目标分配 ID

deepsort 算法的贡献

  • 引入了在行人重识别数据集上离线训练的深度学习模型（reid）
  • 在实时目标追踪过程中，提取的目标特征进行最近邻匹配

image-20211215145028744

DeepSort 的流程图：新增了级联匹配（matching cascade）和新轨迹确认。tracks 分为确认太（confirmed）和不确认态（unconfirmed），新产生的 tracks 是不确认态。不确认态的 tracks 必须要和 detections 连续匹配一定的次数（默认是 3）才能转换成确认态。确认态的 tracks 必须要 detections 连续失配一定次数（默认是 30）才会被删除。

细节：将第一帧检测的结果创建 tracks；一开始 tracks 只有 unconfirmed 的状态。

Due to this extension we are able to track objects through longer peri- ods of occlusions, effectively reducing the number of identity switches. Experi- mental evaluation shows that our extensions reduce the number of identity switches by 45%, achieving overall competitive performance at high frame rates.

DeepSORT 主要是处理 occlusion 方面的问题，减少了 identity switch 的情况。

Deep SORT 算法是在 SORT 算法的基础上增加了级联匹配（Matching Cascade）+ 新轨迹的确认（confirmed）。总体流程：

  • 卡尔曼滤波器预测轨迹 Tracks
  • 使用匈牙利算法将预测得到的轨迹 Tracks 和当前帧的 detections 进行匹配（级联匹配和 IOU 匹配）
  • 卡尔曼滤波更新

惯例中（类似SORT），解决分配问题使用的是匈牙利算法（仅使用运动特征计算代价矩阵），该算法解决了由滤波算法预测的位置与检测出来的位置间的匹配。DeepSORT中，作者结合了外观特征（由小型CNN提取的128维向量）和运动特征（卡尔曼滤波预测的结果）来计算代价矩阵，从而根据该代价矩阵使用匈牙利算法进行目标的匹配。

DeepSORT 通过以下的方式处理遮挡问题

To this end, we employ a CNN that has been trained on a large-scale person re-identification dataset that contains over 1100000 images of 1261 pedestrians, making it well suited for deep metric learning in a people tracking context.

通过一个 CNN 网络提取的特征去区分不同的人（identity）

DeepSORT中采用了一个简单（运算量不大）的CNN来提取被检测物体（检测框物体中）的外观特征（低维向量表示），在每次（每帧）检测+追踪后，进行一次物体外观特征的提取并保存。

后面每执行一步时，都要执行一次当前帧被检测物体外观特征与之前存储的外观特征的相似度计算，这个相似度将作为一个重要的判别依据（不是唯一的，因为作者说是将运动特征与外观特征结合作为判别依据，这个运动特征就是SORT中卡尔曼滤波做的事）。

DeepSORT 增强了长宽比的变化率。在 SORT 中使用的卡尔曼滤波是一个 7 维的向量 $$ \mathbf{x}=[u, v, s, r, \dot{u}, \dot{v}, \dot{s}]^{T} $$ 在 DeepSORT 中使用的是一个 8 维的向量 $$ \mathbf{x}=[u, v, s, r, \dot{u}, \dot{v}, \dot{s},\dot{r}]^{T} $$ 这个是合情合理的，毕竟随着镜头运动或者物体和相机的相对运动，物体的长宽比是会发生变化的。 $$ d^{(1)}(i, j)=\left(\boldsymbol{d}{j}-\boldsymbol{y}{i}\right)^{\mathrm{T}} \boldsymbol{S}{i}{ }^{-1}\left(\boldsymbol{d}{j}-\boldsymbol{y}_{i}\right) $$ 马氏距离通过测量科尔曼滤波器的追踪位置均值（mean track location）之间的标准差和检测框来计算状态估计间的不确定性。即 $d^{(1)}(i, j)$ 为第 $i$ 个追踪分别和第 $j$ 个检测框之间的马氏距离（不确定度）。$i$ 表示追踪的序号，$j$ 检测框的序号。对马氏距离设定一定的阈值，可以排除那些没有关联的目标。

Mahalanobis distance at a 95% confidence interval computed from the inverse χ2 distribution

马氏距离是用来衡量 motion 特征的，但是实际情况中还需要 appearance 来弥补不足。（比如遮挡情况）

外观特征

外观特征提取网络接受reshape的检测框（大小为128x64，针对行人的）内物体作为输入，返回128维度的向量表示。

motion特征和appearance特征是相辅相成的。在DeepSORT中，motion特征（由马氏距离计算获得）提供了物体定位的可能信息，这在短期预测中非常有效。appearance特征（由余弦距离计算获得）可以在目标被长期遮挡后，恢复目标的ID编号，减少ID切换次数。为了结合这两个特征，作者还进行了一个简单的加权运算。

马氏距离

马氏距离（Mahalanobis Distance）是一种距离的度量，可以看做是欧氏距离的一种修正，修正了欧氏距离汇总各个维度尺度不一致且相关的问题。单个数据点的马氏距离 $$ D_{M}(x)=\sqrt{(x-\mu)^{T} \Sigma^{-1}(x-\mu)} $$ 数据点 $x, y$ 之间的马氏距离 $$ D_{M}(x, y)=\sqrt{(x-y)^{T} \Sigma^{-1}(x-y)} $$ 其中 $\Sigma$ 是多维随机变量的协方差矩阵，如果协方差矩阵是单位向量，也就是各个维度独立同分布，马氏距离就变成了欧氏距离。马氏距离可以衡量不同 scale 数据之间的距离，而欧氏距离不行。

级联匹配（cascade：串联，小瀑布）让“more frequently seen objects” 分配的优先级更高。

当一个目标长时间被遮挡之后，kalman滤波预测的不确定性就会大大增加，状态空间内的可观察性就会大大降低。假如此时两个追踪器竞争同一个检测结果的匹配权，往往遮挡时间较长的那条轨迹的马氏距离更小，但是从直观上，检测结果应该分配给时间上最近的轨迹。这么理解吧，假设本来协方差矩阵是一个正态分布，那么连续的预测不更新就会导致这个正态分布的方差越来越大，那么离均值欧氏距离远的点可能和之前分布中离得较近的点获得同样的马氏距离值。所以，作者使用了级联匹配来对更加频繁出现的目标赋予优先权。当然同样也有弊端：可能导致一些新产生的轨迹被连接到了一些旧的轨迹上。但这种情况较少。

将 Detection 和 Track 进行匹配，可能出现以下几种情况：

  • Detection和Track匹配，也就是 Matched Tracks。普通连续跟踪的目标都属于这种情况，前后两帧都有目标，能够匹配上。
  • Detection 没有找到匹配的Track，也就是Unmatched Detections。图像中突然出现新的目标的时候，Detection无法在之前的Track找到匹配的目标。
  • Track 没有找到匹配的Detection，也就是Unmatched Tracks。连续追踪的目标超出图像区域，Track无法与当前任意一个 Detection 匹配。
  • 以上没有涉及一种特殊的情况，就是两个目标遮挡的情况。刚刚被遮挡的目标的Track也无法匹配Detection，目标暂时从图像中消失。之后被遮挡目标再次出现的时候，应该尽量让被遮挡目标分配的ID不发生变动，减少IDSwitch 出现的次数，这就需要用到级联匹配了。

下面这种算法思想是 匈牙利算法的改进版：KM 算法

这个方法是在SORT中被提出的。又是比较陌生的名词。实际上匈牙利算法可以理解成“尽量多”的一种思路，比如说A检测器可以和a，c跟踪器完成匹配（与a匹配置信度更高），但是B检测器只能和a跟踪器完成匹配。那在算法中，就会让A与c完成匹配，B 与a完成匹配，而降低对于置信度的考虑。所以算法的根本目的并不是在于匹配的准不准，而是在于尽量多的匹配上，这也就是在deepsort中作者添加级联匹配与马氏距离与余弦距离的根本目的，因为仅仅使用匈牙利算法进行匹配特别容易造成 ID switch，就是一个检测框id不停地进行更换，缺乏准确性与鲁棒性。那什么是匹配的置信度高呢，其实在这里，作者使用的是 IOU 进行衡量，计算检测器与跟踪器的IOU，将这个作为置信度的高低（比较粗糙）。

DeepSORT 涉及到以下算法：

  • 卡尔曼滤波

  • 马氏距离

  • PCA 主成分分析

  • 匈牙利算法

  • 行人重识别（ReID，用于提取表观特征，原论文中生成了 128 维的 embedding）

  • MOT 评价指标

ReID 是独立于目标检测和耿总器的模块，功能是提取对应 bounding box 中的 feature，得到一个固定维度的 embedding 作为该 bbox 的代表，供计算相似度时使用。

从实践上仍然是通过抠图实现的，而不是通过抠 feature map 实现的。

DeepSORT 是如此通用的一个追踪器，可以被接在任意一个检测器上，比如 YOLO V3+DeepSORT、YOLO V4+DeepSORT、CenterNet +DeepSORT

DeepSORT 算法

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

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

跟踪流程延续上作（SORT 和 DeepSORT 是同一个团队的产出），在卡尔曼滤波的预测结果的基础上，继续使用了匈牙利算法进行目标分配，但在这个过程中加入了运动信息和外观信息。实现起来比较复杂，具体可以看看代码。

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

在DeepSORT中，匈牙利算法用来将前一帧中的跟踪框tracks与当前帧中的检测框detections进行关联，通过外观信息（appearance information）和马氏距离（Mahalanobis distance），或者IOU来计算代价矩阵。

这里的 代价矩阵是如何进行计算？需要对应一下代码。

DeepSORT 工作流程：

检测器得到bbox → 生成detections → 卡尔曼滤波预测→ 使用匈牙利算法将预测后的tracks和当前帧中的detecions进行匹配（级联匹配和IOU匹配） → 卡尔曼滤波更新

Frame 0：检测器检测到了3个detections，当前没有任何tracks，将这3个detections初始化为tracks Frame 1：检测器又检测到了3个detections，对于Frame 0中的tracks，先进行预测得到新的tracks，然后使用匈牙利算法将新的tracks与detections进行匹配，得到(track, detection)匹配对，最后用每对中的detection更新对应的track

下面是 DeepSORT 的流程图

preview

目标跟踪初探（DeepSORT）

这个后面有一些代码的注释，需要看看

DeepSORT，让你的检测器实现简单的多目标追踪！

DeepSORT 和 SORT 论文，进行了很详细的对比，改进点是配有代码解释的。

（附代码）实战 | 从零开始学习Deep SORT+YOLO V3进行多目标跟踪

非常不错的讲解

centerNet-deep-sort

这个算是很不错的项目了， centerNet + deepSORT

整理一下 DeepSORT 流程，然后硬啃代码了

可以先过一遍，加上一些基本函数的注释

tracking 主要是用来辅助 od 的，以下情况：当前帧没有检测出来（遮挡或者其他因素），根据上一帧补全。

红绿灯 tracking，如果发现当前是黑的（对应实际情况中的闪烁），那么根据 tracking 的结果进行修复。

一步走的方案目前的进展：

  • 目前缺少 tracking 数据，缺少帧之间 offset (matrix) 等信息

  • od+ tracking 中使用公开数据集 train， 然后在 own data 上 test 效果不是很好。

目前正在尝试的事情：

  • 将雷达信息投影到图像上，将摄像头投影到图像上。maybe 这个图像是一个虚拟的摄像头。这是一种融合的方案。

代码解析

代码来源：https://github.com/mikel-brostrom/Yolov5_DeepSort_Pytorch/tree/master/deep_sort_pytorch

deep_sort/deep_sort/sort目录下

detection.py：保存通过目标检测的一个检测框框，以及该框的置信度和获取的特征；同时还提供了框框的各种格式的转化方法。

iou_matching.py：计算两个框框之间的IOU。

kalman_filter.py：卡尔曼滤波器的相关代码，主要是利用卡尔曼滤波来预测检测框的轨迹信息。

linear_assignment.py：利用匈牙利算法匹配预测的轨迹框和检测框最佳匹配效果。

nn_matching.py：通过计算欧氏距离、余弦距离等距离来计算最近领距离。

preprocessing.py：非极大抑制代码，利用非极大抑制算法将最优的检测框输出。

track.py：主要储存的是轨迹信息，其中包括轨迹框的位置和速度信息，轨迹框的ID和状态，其中状态包括三种，一种是确定态、不确定态、删除态三种状态。

tracker.py：保存了所有的轨迹信息，负责初始化第一帧，卡尔曼滤波的预测和更新，负责级联匹配,IOU匹配。

deep_sort/deep_sort/deep_sort.py：deepsort的整体封装，实现一个deepsort追踪的一个整体效果。

deep_sort/utils：这里最主要有一些各种各样的工具python代码，例如画框工具，日志保存工具等等。

demo.py：针对读取的视频进行目标追踪

objdetector.py：封装的一个目标检测器，对视频中的物体进行检测

objtracker.py：封装了一个目标追踪器，对检测的物体进行追踪

总结与思考

评价多个模型的性能，从精度、速度、稳定性、功耗等方面综合评价，选择一个合适的模型进行部署。

视频讲解：

(1) https://www.bilibili.com/video/BV1YU4y1A7vb?from=search&seid=7296163169805661079&spm_id_from=333.337.0.0

(2) https://github.com/emasterclassacademy/Single-Multiple-Custom-Object-Detection-and-Tracking/blob/master/object_tracker.py

这个是基于 tf 的 tracker 的实现，有相应的视频