浅议 Sort 算法（目标体识别）

概述

多目标追踪（Multiple Object Tracking），简单来说其主要任务就是给定一个图像序列，在识别出图像中的物体后，通过一个 Trace id 将不同帧中的同一个物体进行表示，从而完成目标追踪的任务。当然这些物体可以是任意的，例如行人车辆各种动物等。

本文讲述的是 sort 算法全称为 Simple Online and Realtime Tracking。从名字上看我们就可以看去其实它是一个比较简单的目标体识别算法，其本身并不涉及复杂的网络计算， 可以说是比较纯粹的算法。

本文的书写并不会完全论文结构来进行全文翻译，感觉这样子没有任何意义，因此本文更多的是去讲个人在学习 sort 算法过程中的理解和遇到的相关问题。

论文地址：sort

代码地址：code

算法

sort 算法的提出，大程度上是为了证明作者提出的是个观点---**追踪的质量很大程度上受到检测质量的影响。**为了验证这个观点，作者设计了 SORT 算法。

因此，Sort 算法在设计之初就十分重视检测环节，它以检测作为关键组件，传播目标状态到未来帧中，将当前检测与现有目标相关联，并管理跟踪目标的生命周期。其中状态传播是通过 FRrCNN 网络来实现，目标关联通过匈牙利算法来实现。

首先在检测环节，作者选择用 FRRCNN 网络作为目标检测网络，参数使用的是 PASCAL VOC 挑战中的默认参数，对于检测的类别作者也给了一个约定，即只检测识别概率大于 50% 的行人检测类别，而忽略其他类别。

到这里可能会有两个问题：

第一个问题：为何要选择 FRRCNN 网络作为目标检测网络？

选择 FRRCNN 网络的原因很大程度上是有该网络的特点决定，FRRCNN 网络有三个特点：

1. 快，FFRRCNN 网络，是一个 two-stage 算法，两个阶段共享参数，使得检测速度大大提升，这某种程度上保证了算法的实时性。
2. 网络结构灵活，框架结构容易替换，这样作者在进行验证的时候便于将网络的框架结构进行替换，验证在不同网络下架构下，检测结果。

为何只检测识别概率大于 50% 的目标？

一方面检测目标类别的减少可以更快的出实验效果，另一方面，cnn 网络比较灵活，在实际工程应用中我们可以很方便的将行人这一类别替换成其他类别。

并且作者在该部分做了一个实验验证，下图是其实验的结果图，从实验结果中我们可以看到，作者替换了 MDP 和其所提供算法的检测，发现跟踪效果有显著的改善，这在某种程度上也验证则作者在论文开始的时候提出的观点即：追踪的质量很大程度上受到检测质量的影响。

估计模型部分，选择的是线性常速模型。

该模型有七个参量组成，u 表示目标中心点的水平坐标，v 表示目标中心的的垂直坐标，s 标尺检测框的尺寸，r 表示检测框的纵横比。u ’ v’ s’分别表示下一帧检测目标中心的水平坐标垂直坐标和检测框的尺寸。我们注意到该模型中没有 r’，这是因为在目标追踪中，我们认为物体的纵横比是不变变量。

数据关联则是由四个阶段组成：

1. 预测每个目标在当前帧的位置，估计其边界形状，预测的功能通过卡尔曼滤波来实现。
2. 根据目标检测框和预测边界框的交并比计算分配矩阵。

3. 有了代价矩阵之后我们便可以通过匈牙利算法来求出一个最大匹配，从而得出相邻两帧物体的轨迹。
4. 最后它会拒绝检测目标重叠小于IoUmin的分配。

当目标进入和离开图像时，需要相应地创建或销毁唯一标识。对于创建跟踪程序，文中认为任何重叠小于IoU_min的检测都表示存在未跟踪的目标。使用速度设置为零的边界框信息初始化跟踪器。由于此时无法观测到速度，因此速度分量的协方差用较大的值初始化，反映出这种不确定性。此外，新的跟踪器将经历一个试用期，其中目标需要与检测相关联以积累足够的证据以防止误报的跟踪。删除时，将 Tlost 设置为 1，如果 Tlost 未被检测到则删除此物体跟踪。

此处可能会有个问题--为何作者要将 Tlost 设置为 1？

分析其原因有三部分组成：

首先，sort 算法使用的是等速模型，等速模型对真实动力学的预测能力较差，即使 Tlost 设置较大的值追踪性能提升也不明显；

其次，sort 算法主要关注逐帧跟踪，目标重识别超出本工作范畴；

此外，早期删除丢失的目标有助于提高效率。如果目标重新出现，跟踪将在新标识下隐式恢复。

实验

作者为了验证自己的观点，设计了一系列实验，对比 sort 算法和当时几种有效的多目标追踪效果，得出了如下的结果图。从图中我们可以看到，SORT 算法在 MOTA、FAG、ML 以及 FP 这些指标都取得了不俗的表现，但它也有不足之处，它 ID sw 指标标记大，表明在实际检测中追踪 id 更换频繁。

结论

从结果图上看，总体来说，sort 算法当时兼顾了追踪效果和速度取得了不错的结果，作者认为实用性高。

但实际上我们可以看出 sort 算法的不足之处，首先我们可以先看一个 sort 检测结果 gif 图，gif 图中的检测类别设置成了汽车。从 gif 图中我可以看到，追踪汽车的 id 在频繁的更换。这种情况下实际上已经失去了追踪的价值。

为了解决该问题，有人就提出了 deepsort 算法，deesort 算法是如何解决 sort 算法的不足的？以及其原理是怎样的？后续我会在写篇文章详细进行展开。