【算法分析】SORT/Deep SORT 物体跟踪算法解析

概述

解析SORT算法代码

SORT算法的优缺点

Deep SORT - SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC

关联度量(ASSOCIATION METRIC)

关联算法 Matching Cascade

SORT - SIMPLE ONLINE AND REALTIME TRACKING

• 论文 http://arxiv.org/pdf/1602.00763.pdf
• 代码 https :// github.com/abewley/sort

概述

SORT跟踪算法到底在干什么？（以单目标跟踪为例说明如下）

• 假设T1时刻成功跟踪了某个单个物体，ID为1，绘制物体跟踪BBox（紫色）
• T2时刻物体检测BBox总共有4个（黑色），预测T2时刻物体跟踪的BBox（紫色）有1个，解决紫色物体跟踪BBox如何与黑色物体检测BBox关联的算法，就是SORT物体跟踪算法要解决的核心问题
• SORT关联两个BBox的核心算法是：用IOU计算Bbox之间的距离 + 匈牙利算法选择最优关联结果

物体跟踪与物体检测是两件不同的事

物体跟踪是把物体跟踪预测的BBox与物体检测的BBox关联，然后用对应的物体检测BBox代表成功跟踪的BBox结果

以上图为例

• T1时刻已经成功跟踪了3个检体(不同颜色的BBox代表不同的物体ID)
• T2时刻除了所有物体检测的新位置BBox（灰色），还要物体跟踪预测的Bbox（非灰的其它不同颜色BBox）与物体检测Bbox（灰色）关联，从而分辨出哪一个物体跟踪的Bbox对应哪一个物体检测的BBox，从而产生T2时刻的物体跟踪BBox结果（包括新增物体跟踪器跟踪T2中新检测到的物体）
• T3时刻如果被追踪的物体发生了遮挡(红框BBox的物体)，那么要继续能找到该物体并追踪 (避免ID Switch)

物体跟踪有几个主要任务以及它们对应的解决方案

• 检测-深度学习的各种检测网络来实现物体检测
• 跟踪预测与关联-Tracking的算法来实现物体追踪(比如 本文介绍的SORT)
• ID Switch- Tracking的算法来解决遮挡物体(比如 deep SORT)
• ReID(跨摄像头发现和跟踪同一个物体，避免ID switch) -  比如 deep SORT

解析SORT算法代码

SORT算法的优缺点

SORT是一个很粗糙的跟踪算法，所以又有了Deep SORT

Deep SORT - SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC

• 论文: https:// arxiv.org/pdf/1703.07402.pdf
• 代码: https:// github.com/nwojke/deep_sort

关联度量(ASSOCIATION METRIC)

• 计算公式(1) 
• 马氏距离计算物体检测Bbox dj和物体跟踪BBox yi之间的距离
• 注：不使用欧式距离的原因是dj和yi 的空间域分布不同，欧式距离忽略空间域分布的计算结果不能准确反映两者的真实距离
• 当两者距离≤特定阈值，则表示两者关联 
• 但马氏距离依然不能很好的解决物体被长时间遮挡后关联不正确导致ID Switch的问题
• 计算公式（2）
• 物体检测BBox dj 通过CNN网络计算对应的128维feature向量rj 称为appearance descriptor
• 具体的做法是把物体检测BBox dj  对应的图像patch作为下图的CNN输入，输出128维feature向量rj

• 对于跟踪器i，为它创建一个集合保留它过去Lk 次成功跟踪后物体检测Bbox对应的Lk 个Feature向量集合，公式（2）是在计算第i个物体跟踪的所有Feature向量和第j个物体检测之间的最小余弦距离（具体含义参考下图）
• 当两者距离≤特定阈值，则表示两者关联 

  

  •组合计算公式（1）和（2）作为计算第i个物体跟踪和第j个物体检测之间关联度量的总公式

  •组合距离阈值判断不等式，作为总的判断第i个物体跟踪和第j个物体检测之间的距离（关联度量）是否关联的总公式

• 关联算法 Matching Cascade

T是物体跟踪集合

D是物体检测集合

1. C矩阵存放所有物体跟踪i与物体检测j之间距离的计算结果
2. B矩阵存放所有物体跟踪i与物体检测j之间是否关联的判断(0/1)
3. 关联集合M初始化为{}
4. 将找不到匹配的物体检测集合初始化为D
5. 从刚刚匹配成功的跟踪器循环遍历到最多已经有Amax 次没有匹配的跟踪器
6. 选择满足条件的跟踪器集合Tn
7. 根据最小成本算法计算出Tn与物体检测j关联成功产生集合[xi,j]
8. 更新M为匹配成功的（物体跟踪i，物体检测j） 集合
9. 从U中去除已经匹配成功的物体检测j
10. 循环
11. 返回 M U 两个集合