deepsort 算法的原理与代码解析

概述

前边我们讲了 sort 算法的原理，并且指出了它的不足--IDsw 过大，为了解决该问题，17 年时候 sort 算法的团队又提出了 DeepSort 算法。Deepsort 在原来 Sort 算法的基础上，改进了以下内容：

1. 使用级联匹配算法：针对每一个检测器都会分配一个跟踪器，每个跟踪器会设定一个 time_since_update 参数。
2. 添加马氏距离与余弦距离：实际上是针对运动信息与外观信息的计算。
3. 添加深度学习特征：这一部分也就是 ReID 的模块，也是 deepsort 的亮点之一。

代码流程

由于 deepsort 的流程和算法原理几乎和 sort 一样，只是说增加了上边三个特色，因此我们直接从代码开始讲起：

整体流程图

算法的整体流程图如下所示：

源码流程

首先我们从主函数部分开始说起，主函数部分整体逻辑是比较简单的，首先是将命令行参数进行解析，解析的内容包括，MOTChanlleng 序列文件所在路径、需要检测文件所在的目录等一系列参数。解析之后传递给 run 方法，开始运行。

进入 run 函数之后，首先会收集流信息，包括图片名称，检测结果以及置信度等，后续会将这些流信息传入到检测框生成函数中，生成检测框列表。然后会初始化 metric 对象，metric 对象简单来说就是度量方式，在这个地方我们可以选择两种相似度的度量方式，第一种叫做余弦相似度度量，另一种叫做欧拉相似度度量。通过 metric 对象我们来初始化追踪器。

接着根据 display 参数开始生成对应的 visuializer，如果选择将检测结果进行可视化展示，那么便会生成 Visualization 对象，我从这个类中可以看到，它主要是调用 opencv image viewer 来讲追踪的结果进行展示。如果 display 是 false 则会生成一个 NoVisualization 对象，它一个虚拟可视化对象，它以给定的顺序循环遍历所有帧以更新跟踪器，而无需执行任何可视化。两者主要区别其实就是是否调用 opencv 将图片展示出来。其实前边我们所做的一系列工作可以说都是准备的工作，实际上核心部分就是在执行这个 run 方法之后。此处我们可以看到，在 run 方法中传入了一个 frame_callback 函数，这个 frame_callback 函数可以说是整个算法的核心部分，每一帧的图片都会执行该函数。

为什么这样说那？

首先进入 run 函数之后我们会发现，无论当时选择是可视化操作还是非可视化操作，它的 run 函数最终都要调用 frame_callback 函数的，比如说 Visualization 中的 run 方法，它首先判断帧序号是否大于最大帧，如果大于最大帧，直接返回。否则回调执行 frame_callback 函数；同样的如果是 NoVisualization 对象，它的 run 方法也是类似的，也是调用 frame_callback 函数，然后帧序号加 1。最后上边追踪结果处理完之后，然后将追踪的结果保存到对应的目录下边。

上边我们说了 frame_callback 函数实际上是整个函数的核心内容。进入 frame_callback 函数，我们可以看到，它第一步是根据之前的参数，生成检测框列表，然后将置信度小于最小置信度阈值的检测框剔除掉。

然后执行非极大值抑制。

什么叫做非极大值抑制那？

简单来说就是就是一个寻找局部最大值的过程，我们以下边检测框为例，我们可以看到在检测人脸的过程中可能会产生多个检测框，通过非极大值抑制，可以在局部范围内选择出那个得分最高的检测框，剔除掉其他得分低的检测框。

接着调用 predict 函数执行预测操作，进入 predict 函数，我们可以看到，它其实主要就是对轨迹列表中所有的轨迹使用卡尔曼滤波算法进行状态的预测。接着调用 update 函数执行更新操作。在 update 函数中，主要如下几件事：

1. 根据之前预测的结果，进行匹配操作。在该开始匹配的时候都处于不确定态，然后若干次匹配之后，如果匹配成功的次数大于 n_init 的话，轨迹便会从初始态转换成确定态。如果一直没有匹配到检测框则会直接进入删除态。由于追踪的目标体可能会消失，因此就算进入到了确定态，如果在后续的匹配中多次没有匹配到，大于 max_age 的时候轨迹便会从确定态转换成删除态。一旦轨迹进入到删除态，则证明这个轨迹失效，后续便会被删除。
2. 针对不同状态进行不同的操作
   a) 对未匹配的 tracker,调用 mark_missed 标记，后续会删除对应的轨迹
   b) 针对未匹配的 detection（检测框）。没有匹配到目标，因此检测框失配，进行初始化操作
   c) 更新轨迹列表，得到最新的 tracks
   d) 更新处于确定态的 trac_id
   e) 最后对特征集更新。

执行到此处当前帧的处理就完成了，直接帧序号加 1，继续进行下一帧的操作。

结论

最后我们将代码整体原理整理成树图如下：

了便于大家阅读源码，我将源码的具体逻辑也整理成了一个树图：