返回论文笔记资料库
arXiv 2016ICIP 2016多目标跟踪论文笔记

SORT

奥卡姆剃刀

原始论文

Simple Online and Realtime Tracking

论文作者

Alex Bewley · Zongyuan Ge · Lionel Ott · Fabio Ramos · Ben Upcroft

发表版本
ICIP 2016会议
arXiv 首次提交
arXiv:1602.00763
引用此论文 · BibTeX

引用信息对应所链接的论文版本,作者为原论文作者。

@misc{multiobjecttrackingsort2016,
  title = {{Simple Online and Realtime Tracking}},
  author = {Alex Bewley and Zongyuan Ge and Lionel Ott and Fabio Ramos and Ben Upcroft},
  year = {2016},
  eprint = {1602.00763},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.00763}
}
本页内容

2015 年,MOTChallenge 上线了。这个基准把多目标跟踪的视频、标注、公开检测结果和评测代码放在一起,大家终于能在同一张排行榜上比较跟踪器。

榜单前列挤满了精巧的系统。多假设跟踪(Multiple Hypothesis Tracking, MHT)和联合概率数据关联(Joint Probabilistic Data Association, JPDA)这些源自雷达跟踪的老方法被重新搬了出来,配上外观模型、在线学习,以及各种处理遮挡的规则。准确度确实上去了,速度却常常掉到每秒一两帧。

昆士兰科技大学的 Alex Bewley 等人看着这张榜,注意到两件事。第一,排名最高的跟踪器,恰好是唯一没有使用官方 ACF 检测结果的方法。第二,最准的那几个方法,都慢到无法实时运行。

如果检测质量才是瓶颈,跟踪器还需要这么复杂吗?

这篇论文想知道,多目标跟踪可以简单到什么程度,又能做得多好。

定义问题

多目标跟踪(Multi-Object Tracking, MOT)的输入是一段视频,输出是每一帧里每个物体的框,加上一个跨帧不变的 ID。

主流做法叫 tracking-by-detection。检测器先在每一帧独立找出所有的框,跟踪器再把这些框串成轨迹。检测器只管「这一帧有谁」,跟踪器负责回答「这个框是上一帧的哪一个」。后者就是数据关联(data association)问题。

这篇论文还加了一个限制,跟踪器必须是 online 的。也就是说,处理第 tt 帧的时候,只能看到第 tt 帧和之前的信息,必须当场给出 ID。另一类 batch 方法可以先看完整段视频,再回头做全局优化,效果通常更好,却没法用在自动驾驶汽车或机器人这类必须实时响应的场景。

当时的排行榜长这样:

原论文 Fig. 1:横轴是 MOTA 准确度,纵轴是跟踪速度(Hz,对数刻度),虚线标出实时运行的分界。多数准确度高的方法落在右下角,速度只有每秒几帧;速度快的方法则落在左上角,准确度较低。SORT 位于右上角,MOTA 约 33、速度约 260 Hz。
原论文 Fig. 1(Bewley 等人),取自 PDF 第 1 页,arXiv 许可,学术引用。

横轴是准确度,纵轴是速度,越往右上越好。右下角是准但慢的方法,左上角是快但不准的方法,右上角原本是空的。

作者引用奥卡姆剃刀原则,给自己的跟踪器做了几个很极端的取舍:

  • 只用框的位置和大小。 检测器之外,不提取任何外观特征,运动估计和数据关联都只看框。
  • 不处理遮挡。 作者认为短期与长期遮挡在这组数据里很少发生,为它们写专门的机制只会让系统变复杂。(这个「很少发生」,后来的 MOT20 和 DanceTrack 大概都不会同意。)
  • 不做重识别。 物体离开画面再回来,就当成新的物体。作者的理由是,重识别会带来可观的计算开销,妨碍实时应用。

剩下要做好的,只有相邻两帧之间的匹配。

解决问题

SORT 由四个部分组成:检测、状态估计、数据关联,以及轨迹的创建与删除。

检测器

作者使用 Faster R-CNN,比较了较浅的 ZF 和较深的 VGG16 两种骨干网络。权重直接用在 PASCAL VOC 上训练好的默认参数,没有针对行人重新训练;输出只保留「人」这一类,而且概率要高于 50%。

这一步看起来平平无奇,却是整篇论文最重要的实验变量,我们在讨论部分再回来看。

每个目标的状态

每个被跟踪的物体,都用一个七维向量描述:

x=[u,v,s,r,u˙,v˙,s˙]⊤\mathbf{x} = [u, v, s, r, \dot{u}, \dot{v}, \dot{s}]^\top

(u,v)(u, v) 是框中心的像素坐标,ss 是框的面积,rr 是宽高比,最后三项是前三者的速度。宽高比没有速度项,作者假设它不会变。

运动模型是匀速模型:每过一帧,位置加上速度,速度不变。官方代码把它写成一个 7×77 \times 7 的状态转移矩阵 FF,以及一个只取前四项的观测矩阵 HH:

F=[1000100010001000100010001000000010000000100000001]F = \begin{bmatrix} 1&0&0&0&1&0&0\\ 0&1&0&0&0&1&0\\ 0&0&1&0&0&0&1\\ 0&0&0&1&0&0&0\\ 0&0&0&0&1&0&0\\ 0&0&0&0&0&1&0\\ 0&0&0&0&0&0&1 \end{bmatrix} H=[1000000010000000100000001000]H = \begin{bmatrix} 1&0&0&0&0&0&0\\ 0&1&0&0&0&0&0\\ 0&0&1&0&0&0&0\\ 0&0&0&1&0&0&0 \end{bmatrix}

FF 的前三行说的是「新位置 = 旧位置 + 速度」;HH 说的是检测器只能直接看到 (u,v,s,r)(u, v, s, r),看不到速度。速度要靠卡尔曼滤波(Kalman filter)从连续几帧的观测里推出来。

卡尔曼滤波每一帧做两件事。第一步是预测,用运动模型把状态往前推一帧,同时让不确定性变大:

x^t∣t−1=F xt−1Pt∣t−1=FPt−1F⊤+Q\begin{aligned} \hat{\mathbf{x}}_{t|t-1} &= F\,\mathbf{x}_{t-1} \\ P_{t|t-1} &= F P_{t-1} F^\top + Q \end{aligned}

第二步是更新。如果这一帧有检测框 zt\mathbf{z}_t 分配给它,就用检测结果修正预测:

Kt=Pt∣t−1H⊤(HPt∣t−1H⊤+R)−1K_t = P_{t|t-1} H^\top \left(H P_{t|t-1} H^\top + R\right)^{-1} xt=x^t∣t−1+Kt(zt−Hx^t∣t−1)Pt=(I−KtH) Pt∣t−1\begin{aligned} \mathbf{x}_t &= \hat{\mathbf{x}}_{t|t-1} + K_t\left(\mathbf{z}_t - H\hat{\mathbf{x}}_{t|t-1}\right) \\ P_t &= (I - K_t H)\,P_{t|t-1} \end{aligned}

PP 是状态的协方差,代表滤波器对自己有多没把握;QQ 是运动模型的噪声,RR 是检测框的噪声。卡尔曼增益 KtK_t 决定要相信预测还是相信检测:预测越不确定(PP 大),就越听检测的;检测越不可靠(RR 大),就越听预测的。

如果这一帧没有检测框分配给它,就只做预测,不做更新。

怎么匹配

每一帧开始时,先让所有已有轨迹做一次预测,得到它们在这一帧「应该」出现的框。接着计算每个检测框和每个预测框之间的交并比(Intersection over Union, IoU),排成一个矩阵。

匹配要求一对一,一个检测框最多分给一条轨迹,一条轨迹最多拿一个检测框。在这个约束下让总 IoU 最大,就是经典的指派问题(assignment problem),用匈牙利算法(Hungarian algorithm)可以求出最优解。

为什么不直接挑 IoU 最大的配一配就好?我们来看一个小例子。

假设有两条轨迹 A、B,和两个检测框 1、2,IoU 矩阵如下:

检测 1检测 2
轨迹 A0.600.50
轨迹 B0.550.00

如果用贪心法,先挑全表最大的 0.60,把检测 1 分给 A。剩下 B 只能配检测 2,IoU 是 0,配不上。结果 B 这一帧失去观测,检测 2 被当成新物体,总 IoU 是 0.60。

匈牙利算法看的是整体。A 配检测 2(0.50),B 配检测 1(0.55),总 IoU 是 1.05,两条轨迹都有着落。两个人并肩走、框互相重叠的时候,这种情况很常见。

匹配完成后,再把 IoU 低于阈值 IOUminIOU_{min} 的匹配拆掉,避免两个根本不重叠的框被硬凑成一对。官方代码的阈值是 0.3。

作者还注意到 IoU 有一个顺带的好处。当一个人从另一个人前面走过,检测器通常只会框到前面那个人。这个框的大小和前面那个人的预测框比较接近,IoU 会倾向于把它分给前面那个人;被挡住的人没有配到检测框,状态只做预测,不会被错误的观测拉走。短暂的交错,就这样在没有任何遮挡处理规则的情况下扛过去了。

轨迹的生与死

一个检测框如果和所有预测框的 IoU 都低于 IOUminIOU_{min},就视为新出现的物体,创建一条新轨迹。位置直接取检测框,速度设为零,速度的协方差则设得很大,表示还不知道它往哪走。

新轨迹要先经过一段试用期,连续匹配成功几次才算数,用来过滤检测器偶尔冒出来的误报。论文没有写出次数,官方代码的 min_hits 是 3。

删除的规则更干脆。一条轨迹连续 TLostT_{Lost} 帧没有配到检测框,就删掉。作者在所有实验中都把 TLostT_{Lost} 设为 1,理由有两个:匀速模型本来就预测不准,放着不管只会越漂越远;而且这篇只处理相邻帧的匹配,重识别不在范围内。

物体如果被挡住一阵子再出现,就会拿到一个新的 ID。

讨论

作者在 MOTChallenge 2015(MOT15)上评估。调整卡尔曼滤波的初始协方差、IOUminIOU_{min} 和 TLostT_{Lost} 时,用的是 MDP 这篇论文的训练与验证划分。

这里需要先认识两个指标:

  • MOTA(Multi-Object Tracking Accuracy):把漏检(FN)、误报(FP)和 ID 切换(ID switch)三种错误加起来,除以真实框的总数,再用 1 去减。三种错误一视同仁,但前两种的数量通常比 ID 切换多出一两个数量级,所以 MOTA 主要反映检测质量。
  • ID sw:一条真实轨迹被分配到的 ID 改变了几次,直接反映匹配做得好不好。

换一个检测器

原论文 Table 1:两种跟踪器(MDP 与 SORT)各搭配三种检测器(ACF、FrRCNN(ZF)、FrRCNN(VGG16)),列出检测的召回率与精确率,以及跟踪的 ID 切换次数与 MOTA。SORT 的 MOTA 从 ACF 的 15.1 升到 ZF 的 24.0,再升到 VGG16 的 34.0;MDP 则是 24.0、22.6、33.5。
原论文 Table 1(Bewley 等人),取自 PDF 第 3 页,arXiv 许可,学术引用。

这张表在验证集上,把两个跟踪器各自搭配三种检测器。MDP 是当时表现很好的在线跟踪器,有学习式的决策流程;SORT 是本文的方法。

先看 SORT 那三行。检测器从 ACF 换成 FrRCNN(VGG16),MOTA 从 15.1 升到 34.0,差了 18.9 分。摘要里「换检测器最多可提升 18.9%」指的就是这个差距。跟踪算法完全没动。

再看 MDP。换成 FrRCNN(ZF) 之后,召回率从 36.6 升到 46.2,MOTA 却从 24.0 降到 22.6。问题出在精确率。ZF 的精确率从 75.8 掉到 67.2,误报增加,MOTA 跟着扣分。检测器「找得到更多」,不见得对跟踪有利,误报也一样要付出代价。

两个跟踪器搭配最好的检测器时,MOTA 分别是 33.5 和 34.0,相差很小。检测器带来的差距,比跟踪器之间的差距大得多。

MOT15 测试集

原论文 Table 2:MOT15 测试集上的比较,分为 batch 与 online 两类方法,各列包括 MOTA、MOTP、FAF、MT、ML、FP、FN、ID sw、Frag。SORT 的 MOTA 为 33.4,是在线方法中最高,与 batch 方法 NOMT 的 33.7 接近;FP 7318 和 ML 30.9% 都是全表最低;ID sw 为 1001。
原论文 Table 2(Bewley 等人),取自 PDF 第 4 页,arXiv 许可,学术引用。

测试集有 11 段视频,真实标注不公开,结果由官方服务器计算。

SORT 的 MOTA 是 33.4,是在线方法中最高的,和会偷看未来几帧的 NOMT(33.7)几乎一样。误报数 7318 是全表最少,几乎跟丢的轨迹比例(ML)30.9% 也是最低。

但 ID 切换那一列就不太好看了。SORT 有 1001 次,而 MDP 是 680,TDAM 是 464,NOMT 只有 442。这就是 TLost=1T_{Lost} = 1 和不使用外观信息的代价:物体被挡住超过一两帧,回来时就换了一个 ID。轨迹断裂次数(Frag)1764,同样偏高。

MOTA 因为检测做得好而高,ID 切换却因为匹配太简单而多。这两列并排放在一起,SORT 的强项和弱点就很清楚了。

速度

跟踪部分在单核 Intel i7 2.5GHz 上跑到 260 Hz,也就是每帧不到 4 毫秒,比表中其他方法快 20 倍以上。

不过,这个数字只算跟踪,不含检测。SORT 用的 FrRCNN(VGG16),在 Faster R-CNN 原论文的 GPU 上大约每秒 5 帧。整套系统要实时运行,瓶颈其实在检测器。这不影响论文的论点,它要说明的是跟踪这一步可以几乎不花时间,把计算预算留给检测器。

后来

官方代码的说明写着,SORT 发表时是 MOT15 上排名最好的开源跟踪器,也提醒 SORT 的准确度有很大一部分要归功于检测结果。代码本身不到三百行,于是很快成了各种项目的默认基线。

它的参数也跟着四散。不同的移植版本里,max_age 有 1,也有 30,min_hits 和 IoU 阈值各有调整。拿别人的 SORT 数字做比较时,最好先确认用的是哪一组设置。

作者在结论里写,简单的框架很适合当基线,让新方法专心处理长时间遮挡与重识别;未来则打算把检测和跟踪更紧密地结合。一年后,Wojke、Bewley 等人发表的 DeepSORT,就在这副骨架上加回了外观特征;JDE、FairMOT 和 CenterTrack 这些把检测与跟踪放进同一个网络的方法,则走了另一条路。

结论

卡尔曼滤波、IoU、匈牙利算法,三样教科书里的东西,就让 SORT 在 MOT15 上做到在线方法中最高的 MOTA,跟踪本身每帧只花不到 4 毫秒。论文里最有说服力的一组数字,是换检测器让 MOTA 从 15.1 跳到 34.0,而两个跟踪器配上同一个好检测器时,只差 0.5 分。

要做新的跟踪系统,先把 SORT 跑起来当基线,再换一个更好的检测器,看看分数变了多少。剩下的差距,才轮到跟踪算法去解决。

五年后的 ByteTrack 在 MOT17 上拿下第一,用的关联方法仍然是卡尔曼滤波加 IoU,只是多捡了几个低分框。