SORT: SIMPLE ONLINE AND REALTIME TRACKING
Alex Bewley
Queensland University of Technology, 2016
之前囫囵地学习了deep SORT，近期有深入需要了才发现看得不是很懂，故又把SORT论文翻出来看了一遍。
1. Introduction
本文为多物体跟踪（Multiple Object Tracking MOT）问题提出了一种基于检测的跟踪框架的精简实现，即对每帧中的物体以限位框的方式进行检测。与batch的方式相反，本论文主要目标是在线跟踪，tracker仅得到前一帧和当前帧。此外，重点在于为了满足实时追踪的效率上，希望能促进如自动驾驶等的应用。
MOT问题可以看做数据关联data association问题，其目标是将视频序列中不同帧的检测关联起来。各种tracker对场景中的物体的移动和外观使用多种方式建模。本论文的方法灵感来自于对MOT benchmark的观察。首先，近期有成熟的数据关联技术再起的现象，包括Multiple Hypothesis Tracking（MHT）和Joint Probabilistic Data Association（JPDA），占据了许多MOT benchmark的前列。其次，唯一没有使用Aggregate Channel Filter（ACF）的tracker也是排第一的tracker，说明检测质量可能拖了其它tracker后腿。此外，速度和精度间的权衡太明显，因为很多精确的tracker速度离实时差很多（图1）。
遵守奥卡姆剃刀原则，超出检测组件的特征信息会在tracking中忽略，仅使用限位框位置和大小进行移动估计和数据关联。而且也忽略关于短期和长期的遮挡问题，因为这些遮挡很稀少，而对它们的显式处理会为跟踪框架引入不需要的复杂度。我们认为以re-id的形式引入复杂度会为跟踪框架显著增加overhead，限制了它的实时应用。
这一设计哲学与许多引入了种种组件来处理不同的edge case和检测错误的tracker不同。本论文焦点在于性能和可靠的逐帧关联。与其关注对检测误差的健壮性，我们利用近期的物体检测的进步，来直接解决此问题。我们对常见的基于ACF的和CNN的行人检测器进行了对比。另外，我们使用了两个经典而非常高效的方法，卡尔曼滤波和匈牙利算法，分别进行移动估计和数据关联。
2. Literature Review
使用MHT或JPDA的传统MOT方法在对物体分配高度不确定时会推迟困难决策。这些方法的这一组合combinatorial复杂度与跟踪物体数量呈指数关系。近期Rezatofighi等人的[2]解决了JPDA的这一问题，通过有效的近似。
许多在线跟踪方法目标是在在线学习中构建物体个体或整体的外观模型。除了外观模型，通常还应用移动来与踪片tracklet关联。当仅考虑一对一的模型，就成了二分图，可以使用匈牙利算法寻找全局最优解。
Geiger等人的使用匈牙利算法的方法[20]分两步。首先，通过位置和外观线索关联邻接帧的检测得到踪片，形成亲和矩阵。接下来，踪片同样通过位置和外观线索互相关联起来，解决遮挡导致的断连。这一两步方法使它仅能应用于batch计算。
3. Methodology
3.1 Detection
我们使用了Faster RCNN作为检测器。比较了几种方法（表1）。不再赘述。
3.2 Estimation Model
我们为每个物体使用具有线性常量速度的模型估计逐帧间的位移，它与其它物体以及摄像机移动无关。每个目标的状态建模如下：
其中u和v代表目标中心的水平和垂直的像素坐标，s和r分别是面积和宽高比。当一个检测与一个目标关联后，被检出的限位框就被用于更新目标状态，速度通过卡尔曼滤波框架[14]得出。如没有任何关联，则其状态仍不加修改地沿用线性速度模型。
3.3 Data Association
每个目标预测一个在当前帧的限位框坐标。Assignment cost矩阵通过每个检测和每个目标预测的限位框的IOU距离计算得出，然后通过匈牙利算法求解。另外添加了一个最小IOU阈值，低于它的将不会进行关联。
我们发现IOU距离隐式地处理了由经过目标导致的短期遮挡。当目标被一个遮挡目标挡住时，仅会检出遮挡目标，因为IOU距离偏好有着类似大小的检测。
3.4 Creation and Deletion of Track Identities
当物体进入或离开图片时，需对应创建或销毁唯一的id。我们把任何重叠小于IOUmin当做是一个未跟踪的物体存在的标志。tracker会使用限位框坐标初始化，速度设为0。因为在此刻尚未观察到速度，故速度的协方差covariance设置得较大，反映出这一不确定性。然后，该tracker会进行一段试用期，它需要关联足够的detection来证明自己不是false positive tracking。
当track有$T_{Lost}$帧未能检测到时，它们将被终止。这防止了tracker数无限制的增长，以及由于长时间没有得到来自检测器的纠正导致的定位误差。所有实验中$T_{Lost}$都设为1，因为首先常量速度模型是一个不怎么样的预测器。其次，我们主要关心逐帧的最终，re-id超出了范畴。另外，尽早移除丢失的目标有助于效率。当物体重现时，追踪会以一个新的id继续。
4. Experiments
我们在一个MOT数据集[6] benchmark。为了调优卡尔曼滤波器的协方差，IOUmin和$T_{Lost}$参数，我们使用了[12]报告的训练、验证划分。检测架构使用了FrRCNN（VGG16）[22]。
tracking部分在i7的2.5GHz单核，16GB内存的机器上运行时间为260Hz。
References
[1] C. Dicle, M. Sznaier, and O. Camps, “The way theymove: Tracking multiple targets with similar appearance,” in International Conference on Computer Vision, 2013.
[2] S. H. Rezatofighi, A. Milan, Z. Zhang, A. Dick, Q. Shi,and I. Reid, “Joint Probabilistic Data Association Revisited,” in International Conference on Computer Vision, 2015.
[3] C. Kim, F. Li, A. Ciptadi, and J. M. Rehg, “MultipleHypothesis Tracking Revisited,” in International Conference on Computer Vision, 2015.
[4] J. H. Yoon, M. H. Yang, J. Lim, and K. J. Yoon,“Bayesian Multi-Object Tracking Using Motion Context from Multiple Objects,” in Winter Conference onApplications of Computer Vision, 2015.
[5] A. Bewley, L. Ott, F. Ramos, and B. Upcroft, “ALExTRAC: Affinity Learning by Exploring Temporal Reinforcement within Association Chains,” in InternationalConference on Robotics and Automation. 2016, IEEE.
[6] L. Leal-Taix´e, A. Milan, I. Reid, S. Roth, andK. Schindler, “MOTChallenge 2015: Towards a Benchmark for Multi-Target Tracking,” arXiv preprint, 2015.
[7] D. Reid, “An Algorithm for Tracking Multiple Targets,”Automatic Control, vol. 24, pp. 843–854, 1979.
[8] P. Dollar, R. Appel, S. Belongie, and P. Perona, “FastFeature Pyramids for Object Detection,” Pattern Analysis and Machine Intelligence, vol. 36, 2014.
[9] S. Oh, S. Russell, and S. Sastry, “Markov ChainMonte Carlo Data Association for General MultipleTarget Tracking Problems,” in Decision and Control.2004, pp. 735–742, IEEE.
[10] A. Perera, C. Srinivas, A. Hoogs, and G. Brooksby,“Multi-Object Tracking Through Simultaneous LongOcclusions and Split-Merge Conditions,” in ComputerVision and Pattern Recognition. 2006, IEEE.
[11] W. Choi, “Near-Online Multi-target Tracking with Aggregated Local Flow Descriptor,” in International Conference on Computer Vision, 2015.
[12] Y. Xiang, A. Alahi, and S. Savarese, “Learning to Track: Online Multi-Object Tracking by Decision Making,”in International Conference on Computer Vision, 2015.
[13] S. Ren, K. He, R. Girshick, and J. Sun, “Faster R-CNN:Towards Real-Time Object Detection with Region Proposal Networks,” in Advances in Neural InformationProcessing Systems, 2015.
[14] R. Kalman, “A New Approach to Linear Filtering andPrediction Problems,” Journal of Basic Engineering,vol. 82, no. Series D, pp. 35–45, 1960.
[15] H. W. Kuhn, “The Hungarian method for the assignmentproblem,” Naval Research Logistics Quarterly, vol. 2,pp. 83–97, 1955.
[16] Y. Bar-Shalom, Tracking and data association, Academic Press Professional, Inc., 1987.
[17] S. H. Bae and K. J. Yoon, “Robust Online Multi-ObjectTracking based on Tracklet Confidence and Online Discriminative Appearance Learning,” Computer Visionand Pattern Recognition, 2014.
[18] Y. Min and J. Yunde, “Temporal Dynamic AppearanceModeling for Online Multi-Person Tracking,” oct 2015.
[19] A. Bewley, V. Guizilini, F. Ramos, and B. Upcroft,“Online Self-Supervised Multi-Instance Segmentationof Dynamic Objects,” in International Conference onRobotics and Automation. 2014, IEEE.
[20] A. Geiger, M. Lauer, C. Wojek, C. Stiller, and R. Urtasun, “3D Traffic Scene Understanding from MovablePlatforms,” Pattern Analysis and Machine Intelligence, 2014.
[21] M. Zeiler and R. Fergus, “Visualizing and Understanding Convolutional Networks,” in European Conferenceon Computer Vision, 2014.
[22] K. Simonyan and A. Zisserman, “Very Deep Convolutional Networks for Large-Scale Image Recognition,” inInternational Conference on Learning Representations, 2015.
[23] H. Pirsiavash, D. Ramanan, and C. Fowlkes, “Globallyoptimal greedy algorithms for tracking a variable number of objects,” in Computer Vision and Pattern Recognition. 2011, IEEE.
[24] Y. Li, C. Huang, and R. Nevatia, “Learning to associate: HybridBoosted multi-target tracker for crowdedscene,” in Computer Vision and Pattern Recognition.2009, IEEE.
[25] K. Bernardin and R. Stiefelhagen, “Evaluating MultipleObject Tracking Performance: The CLEAR MOT Metrics,” Image and Video Processing, , no. May, 2008.