> ## Content Index > Fetch the complete content index at: https://yinguobing.com/blog/llms.txt > Use this file to discover other available public pages before exploring further. # DeepSORT实时在线跟踪算法 - URL: https://yinguobing.com/blog/deepsort/ - Published: 2021-12-19T08:10:00.000Z - Updated: 2022-05-29T06:11:37.000Z - Description: 基于深度学习的实时在线跟踪算法。 - Author: 尹国冰 - Tags: 深度学习, 图像处理, 物体检测 最近忙于写码，好久没有读论文了。今天读一篇与物体检测与跟踪相关的文章。 DeepSORT是由Nicolai Wojke等人在2017年发表的文章*"Simple Online And Realtime Tracking With A Deep Association Metric"*中提出的一种物体跟踪算法。这里的SORT不是排序的意思，是Simple Online And Realtime Tracking的缩写。你可以在下方链接找到文章全文。 [Simple Online and Realtime Tracking with a Deep Association MetricSimple Online and Realtime Tracking (SORT) is a pragmatic approach tomultiple object tracking with a focus on simple, effective algorithms. In thispaper, we integrate appearance information to improve the performance of SORT.Due to this extension we are able to track objects through longer period…![](https://static.arxiv.org/static/browse/0.3.2.8/images/icons/favicon.ico)arXiv.orgNicolai Wojke![](https://static.arxiv.org/icons/twitter/arxiv-logo-twitter-square.png)](https://arxiv.org/abs/1703.07402?ref=yinguobing.com) 以下内容是对文章核心的摘抄。 --- 随着物体检测技术的发展，通过检测实现跟踪在多物体跟踪方案中开始流行。该方案一次性处理整段视频，将物体轨迹转化为一个全局优化问题。由于需要一次性处理全部视频帧，所以该方案并不适用与在线场景（例如实时视频流）。一些传统方案如Multiple Hypothesis Tracking、Joint Probabilistic Data Association Filter可以实现在线逐帧跟踪，并且在检测加强的方案下展现出潜力。但是这些方案以运算量和实现复杂度为代价。 简化的在线实时跟踪 SORT (Simple online and realtime tracking) 是一种更加简化的方案。它通过图像空间的卡尔曼滤波以及基于匈牙利算法的逐帧检测框交叠关联性评估来实现。这种简化方案在准确率与精确度上总体表现较好，但是在目标身份保持上表现不佳。这是由于状态估计的高不确定性直接影响了关联性评估。为解决这个问题，作者使用引入了卷积神经网络来获得更加合适关联信息。该神经网络是通过大规模行人再识别数据集训练获得的。 ### 跟踪与状态评估 DeepSORT的跟踪场景涉及8个维度的状态空间 \\(u, v, \\gamma, h, \\dot{x}, \\dot{y}, \\dot{\\gamma}, \\dot{h}\\)，代表边界框中心的位置 \\(u, v\\) 、纵横比 \\(\\gamma\\)、高度 \\(h\\) 以及它们在图像坐标系中的运动速度。其中 \\( u, v, \\gamma, h \\) 作为物体状态的直接观测对象，并使用恒定速率线性模型的标准卡尔曼滤波器。对于每一个跟踪对象 \\(k\\)，统计上次成功测量\\(a\_k\\)后处理过的帧数量。该计数器随着卡尔曼滤波器的每一次预测递增并当跟踪与某次测量关联后置零。当跟踪对象的计数器持续增加并超过某个阈值\\(A\_{max}\\)之后，该对象被认为从场景中消失并从跟踪集合中移除。每次检测结果中无法被关联到现有跟踪对象集合中的物体会被当做临时跟踪对象添加到集合中。新增的跟踪对象需要在随后的三帧画面中被成功的关联，才会被正式添加到跟踪对象集合中。 ### 指派问题 将卡尔曼滤波的预测结果与实际测量结果相匹配可以转化为指派问题并通过匈牙利算法来解决。DeepSORT通过将运动与外观的评估整合来实现。 运动信息具体表现为卡尔曼预测结果与新到测量结果之间的马氏距离（Mahalanobis distance）： \\\[d^{1}(i,j) = (\\boldsymbol{d}\_j - \\boldsymbol{y}\_i)^T\\boldsymbol{S}\_i^{-1}(\\boldsymbol{d}\_j-\\boldsymbol{y}\_i)\\\] 其中\\((\\boldsymbol{y}\_i, \\boldsymbol{S}\_j)\\)、\\(\\boldsymbol{d}\_j\\)分别为第\\(i\\)次跟踪分布、第\\(j\\)个边界框在测量空间中的投射。通过测量检测结果与平均跟踪位置之间的标准差，匈牙利算法将预测状态的不确定性纳入考量。进一步的，这种方式可以通过计算马氏距离\\(\\varphi^2\\)的反转分布，以95%置信度的阈值排除低关联性目标，可记为： \\\[b\_{i,j}^{(1)}=\\mathbb{1}\[d^{(1)}(i,j)\\le t^{(1)}\]\\\] 当第\\(i\\)个跟踪与第\\(j\\)个检测可以关联时，该式等于1。对于之前提到的四维度测量空间，对应的马氏距离阈值 \\(t^{(1)}=9.4877\\)。 当运动不确定性较低时，马氏距离是一项不错的关联性指标。然而卡尔曼滤波提供的物体位置是一个粗略的估计值。实际状况中预期外的相机运动会导致图像平面的快速移位，导致马氏距离评估的失效。为解决这个问题，DeepSORT引入了一个新的评估指标。对于每个检测结果\\(\\boldsymbol{d}\_j\\)，计算其外观描述\\(\\boldsymbol{r}\_j\\)并确保\\(||\\boldsymbol{r}\_j||=1\\)。进一步的，对于每个跟踪对象\\(k\\)，保留最近100个被关联的外观描述集合\\(\\mathcal{R}\_k=\\{\\boldsymbol{r}\_k^{(1)}\\}\_{k=1}^{L\_k}\\)。该评估指标计算第\\(i\\)个跟踪与第\\(j\\)个检测在外观维度上的最小余弦距离。 \\\[d^{(2)}(i, j) = \\min\\{1-\\boldsymbol{r}\_j^T\\boldsymbol{r}\_k^{(i)} | \\boldsymbol{r}\_k^{(i)}\\in\\mathcal{R}\_i\\}\\\] 同时，引入一个二元变量来表征根据该评价指标某个联系是可接受的。 \\\[b\_{i,j}^{(2)}=\\mathbb{1}\[d^{(2)}(i,j)\\le t^{(2)}\]\\\] 实际中，外观描述是通过将检测对象送入一个预训练的卷积神经网络获得的。 这两种评价指标在实际任务中互为补充。一方面，马氏距离根据物体的运动状态提供可能的位置，适合短期内预测。另一方面，基于外观的余弦距离特别适合时间段较长时物体被遮挡，运动信息有限的状况。可以通过加权求和将两者联系起来。 \\\[ c\_{i,j}=\\lambda d^{(1)}(i,j)+(1-\\lambda)d^{(2)}(i,j) \\\] 如果某个联系处于两个指标的阈值区域内，则将其视为可接受的。 \\\[b\_{i,j}=\\prod\_{m=1}^2b\_{i,j}^{(m)}\\\] 两个指标对整体的影响可以通过超参数\\(\\lambda\\)来控制。当摄像机存在显著运动时，可将\\(\\lambda\\)设定为0。但是马氏距离的限制依旧有效。 ### 匹配级联 设想如下场景：当一个物体被遮挡较长时间时，卡尔曼滤波预测的位置不确定性增加。 此时状态空间的质量开始扩散，观测到的可能性曲线变得平滑。理论上，联系性指标此刻应当增加测量距离来应对质量扩散。实际上，当两个跟踪对象面对同一个检测结果时，由于较大的跟踪不确定性可以减小任意检测结果与投射跟踪平均之间的标准差，马氏距离更加偏好选择具备较大不确定性的跟踪。这会导致跟踪的碎片化与不稳定。 😅 理解上边这段内容需要专业的知识背景，我并没有看懂。 级联算法的输入包括跟踪\\(\\mathcal{T}\\)、检测\\(\\mathcal{D}\\)与最大跟踪时长\\(A\_{max}\\)。首先计算关联代价矩阵与可接受的关联矩阵。然后迭代跟踪周期\\(n\\)来解决随着跟踪时长增加的线性指派问题。先选择最近\\(n\\)帧都没有实现关联的跟踪对象\\(\\mathcal{T}\_n\\)，然后将其指派给未匹配的检测结果\\(\\mathcal{U}\\)，之后更新检测结果中匹配与未匹配的集合，并重复此过程。最后一次迭代则需要针对\\(n=1\\)的未匹配跟踪执行交并比关联。这有助于减少画面中固定物体遮挡造成的外观突变。 ### 深度外观描述 DeepSORT使用简化最近邻查询，因此需要一款离线训练好的特征提取器。该特征提取器是一款在包含1100000张图像与1261个行人的再识别数据集上训练得到的卷积神经网络。该神经网络结构如下： | Name | Patch Size/Stride | Output Size | | -------------------------- | ----------------- | ----------- | | Conv 1 | 3×3/1 | 32×128×64 | | Conv 2 | 3×3/1 | 32×128×64 | | Max Pool 3 | 3×3/2 | 32×64×32 | | Residual 4 | 3×3/1 | 32×64×32 | | Residual 5 | 3×3/1 | 32×64×32 | | Residual 6 | 3×3/2 | 64×32×16 | | Residual 7 | 3×3/1 | 64×32×16 | | Residual 8 | 3×3/2 | 128×16×8 | | Residual 9 | 3×3/1 | 128×16×8 | | Dense 10 | | 128 | | Batch and l2 normalization | | 128 | 网络最终的输出为128维向量。面对30个边界框时的推演耗时约30毫秒（GTX1050移动版）。作者在GitHub上提供了权重文件下载。 [GitHub - nwojke/deep\_sort: Simple Online Realtime Tracking with a Deep Association MetricSimple Online Realtime Tracking with a Deep Association Metric - GitHub - nwojke/deep\_sort: Simple Online Realtime Tracking with a Deep Association Metric![](https://github.com/fluidicon.png)GitHubnwojke![](https://opengraph.githubassets.com/c1caa1f13d2c6b1cf5e9c25c8d4ab72b5eab5f22466bd99c32dcd1472f472e98/nwojke/deep_sort)](https://github.com/nwojke/deep%5Fsort?ref=yinguobing.com) ### 实验与结论 作者在MOT16 Benchmark下完成了实验。结果显示DeepSORT的身份切换是所有结果中最少的一个。具体的数值可以去文章中查询。这里不再列出。 --- 对于视频来说，检测与跟踪一直是捆绑在一起的技术手段。检测给出某一时刻图像空间中的信息分布；跟踪给出某一时间段图像空间中特定目标的变化轨迹。两者结合起来，可以生成更加丰富的抽象语义信息。DeepSORT引入深度神经网络实现基于外观特征的匹配，与卡尔曼滤波相辅相成。这种思路值得借鉴。