原标题：计算机视觉中，究竟有哪些好用的目标跟踪算法（上）
一
先来混个脸熟，大概了解一下目标跟踪这个方向都有些什么。一切要从2013年开始说起，那一年的冬天和往常一样冷。如果你问别人近几年有什么比较niubility的跟踪算法，大部分人都会扔给你吴毅老师的论文，OTB50和OTB100(OTB50这里指OTB-2013，OTB100这里指OTB-2015，感谢指正)：
WuY,LimJ,YangMH.Onlineobjecttracking:Abenchmark[C]//CVPR,2013.
WuY,LimJ,YangMH.Objecttrackingbenchmark[J].TPAMI,2015.
论文在数据库上对比了包括2012年及之前的29个顶尖的tracker，有大家比较熟悉的OAB,IVT,MIL,CT,TLD,Struck等，大都是顶会转顶刊的神作，由于之前没有比较公认的数据库，论文都是自卖自夸，大家也不知道到底哪个好用，所以这个database的意义非常重大，直接促进了跟踪算法的发展，后来又扩展为OTB100发到TPAMI，有100个序列，难度更大更加权威，我们这里参考OTB100的结果，首先是29个tracker的情况(标出了一些性能速度都比较好的算法)：
接下来再看结果(更加详细的情况建议您去看论文比较清晰)：
2012年以前的算法基本就是这样，自从2012年AlexNet问世以后，CV各个领域都有了巨大变化，所以我猜你肯定还想知道2013到2017年发生了什么，抱歉我也不知道(容我卖个关子)，不过我们可以肯定的是，2013年以后的论文确定以及必定都会引用OTB50这篇论文，借助谷歌学术中的被引用次数功能，得到如下结果：
TrackerKCF接口实现了KCF和CN，影响力可见一斑，这一点就可以说明很多问题了，还有个GOTURN是基于深度学习的方法，速度虽快但精度略差，窃以为太激进了...
二
总体介绍下目标跟踪。这里说的目标跟踪，是通用单目标跟踪，第一帧给个矩形框，这个框在数据库里面是人工标注的，在实际情况下大多是检测算法的结果，然后需要跟踪算法在后续帧紧跟住这个框，以下是VOT对跟踪算法的要求：
通常目标跟踪面临几大难点(吴毅在VALSE的slides)：外观变形，光照变化，快速运动和运动模糊，背景相似干扰：
平面外旋转，平面内旋转，尺度变化，遮挡和出视野等情况：
OTB和VOT区别：OTB包括25%的灰度序列，但VOT都是彩色序列，这也是造成很多颜色特征算法性能差异的原因；两个库的评价指标不一样，具体请参考论文；VOT库的序列分辨率普遍较高，这一点后面分析会提到。对于一个tracker，如果两个库(最好是OTB100和VOT2016)都跑了且结果上佳，那性能肯定是非常优秀的(两个库调参你能调好，我服，认了~~)。如果只跑了一个，(仅供参考)我比较认可的是VOT2016，因为序列都是精细标注，且评价指标我更加认可(人家毕竟是竞赛，评价指标发过TPAMI的)，差别最大的地方，OTB是随机帧开始，或矩形框加随机干扰初始化去跑，作者说这样更加符合检测算法给的框框；而VOT是第一帧初始化去跑，每次跟踪失败(预测框和标注框不重叠)时，5帧之后再次初始化，VOT以short-term为主，且认为跟踪检测应该在一起永不分离，detecter会多次初始化tracker。至于哪个更好，看你，和你的需求。
补充：OTB在2013年公开了，对于2013以后的算法是透明的，有调参的可能性，尤其是那些只跑OTB，而且论文中有关键参数直接给出还精确到小数点后两位的算法，建议您先实测再评价(人心不古啊~被坑的多了)，但VOT竞赛的数据库是每年更新，还动不动就重新标注，动不动就改变评价指标，对当年算法是不可见且难度很大的，所以结果更可靠。如果您认可以上看法，后面会推荐很多在我看来顶尖又快速的算法。如果您不认可以上看法，后面也就没必要看下去了，谢谢！（看每篇论文都会觉得这个工作太好太重要了，如果没有这篇论文，必会地球爆炸，宇宙重启~~所以就像大家都通过历年ILSVRC竞赛结果为主线了解深度学习的发展一样，第三方的结果更具说服力，所以我也以竞赛排名+是否公开源码+实测性能为标准分析每个方法）
目标视觉跟踪(VisualObjectTracking)，大家比较公认分为两大类：生成(generative)模型方法和判别(discriminative)模型方法，目前比较流行的是判别类方法，也叫检测跟踪tracking-by-detection，为保持完整性，以下简单介绍。
判别类方法，OTB50里面的大部分方法都是这一类，CV中的经典套路图像特征+机器学习，当前帧以目标区域为正样本，背景区域为负样本，机器学习方法训练分类器，下一帧用训练好的分类器找最优区域(马超在VALSE的slides)：
与生成类方法最大的区别，是分类器训练过程中用到了背景信息，这样分类器就能专注区分前景和背景，所以判别类方法普遍都比生成类好。举个例子，在训练时告诉tracker目标80%是红色，20%是绿色，还告诉它背景中有橘红色，要格外注意别搞错了，这样的分类器知道更多信息，效果也肯定更好。tracking-by-detection和检测算法非常相似，如经典行人检测用HOG+SVM，Struck用到了haar+structuredoutputSVM，跟踪中为了尺度自适应也需要多尺度遍历搜索，区别仅在于跟踪算法对特征和在线机器学习的速度要求更高，检测范围和尺度更小而已。这点其实并不意外，大多数情况检测识别算法复杂度比较高不可能每帧都做，这时候用复杂度更低的跟踪算法就很合适了，只需要在跟踪失败(drift)或一定间隔以后再次检测去初始化tracker就可以了。经典判别类方法推荐Struck和TLD，实时性能还行，Struck是2012年之前最好的方法，TLD是经典long-term的代表，即使效果差一点但思想非常值得借鉴：
三
1.为什么只用单通道灰度特征的KCF和用了多通道HOG特征的KCF速度差异很小？
第一，HOG，作者用了HOG的快速算法fHOG，来自Piotr'sComputerVisionMatlabToolbox，C代码而且做了SSE优化。如对fHOG有疑问，请参考论文ObjectDetectionwithDiscriminativelyTrainedPartBasedModels第12页。
第二，HOG特征常用cellsize是4，这就意味着，100*100的图像，HOG特征图的维度只有25*25，而Rawpixels是灰度图归一化，维度依然是100*100，我们简单算一下：27通道HOG特征的复杂度是27*625*log(625)=47180,而单通道灰度特征的复杂度是10000log（10000）=40000，结果也是相差不多，符合表格(不知道这种算法对不对，如果有误请指出，谢谢)。
看代码你会发现，作者在扩展后目标区域面积较大时，会先对提取到的图像块做因子2的下采样，到50*50这样复杂度就变成了2500log（2500）=8495，下降了非常多。那你可能会想，如果下采样再多一点，复杂度就更低了，但这是以牺牲跟踪精度为代价的，再举个例子，如果图像块面积为200*200，先下采样到100*100，再提取HOG特征，分辨率降到了25*25，这就意味着响应图的分辨率也是25*25，也就是说，响应图每位移1个像素，原始图像中跟踪框要移动8个像素，这样就降低了跟踪精度。在精度要求不高时，你完全可以稍微牺牲下精度提高帧率(但真的不能再下采样了)。
2.HOG特征的KCF和DCF哪个更好？
可能会有这样的疑问，kernel-trick这么强大的东西，怎么才提高这么点？这里就不得不提到Winsty的另一篇大作：
四
其实前三名除了特征略有差异，核心都是扩展了多尺度检测，概要如下：
尺度变化是跟踪中比较基本和常见的问题，前面介绍的三个算法都没有尺度更新，如果目标缩小，滤波器就会学习到大量背景信息，如果目标扩大，滤波器就跟着目标局部纹理走了，这两种情况都很可能出现非预期的结果，导致漂移和失败。
简单对比下这两种多尺度方法：
DSST和SAMF所采用的尺度检测方法哪个更好？
首先给大家讲个笑话：MartinDanelljan大神提出DSST之后，他的后续论文就再没有用过。
1、虽然SAMF和DSST都可以跟上普通的目标尺度变化，但SAMF只有7个尺度比较粗，而DSST有33个尺度比较精细准确；
2、DSST先检测最佳平移再检测最佳尺度，是分布最优，而SAMF是平移尺度一起检测，是平移和尺度同时最优，而往往局部最优和全局最优是不一样的；
3、DSST看成两个问题可以采用不同的方法和特征更加灵活，但需要额外训练一个滤波器，每帧尺度检测需要采样33个图像块，分别计算特征，加窗，FFT，尺度滤波器还要额外训练；SAMF只需要一个滤波器，不需要额外训练和存储，每个尺度检测就一次提特征和FFT，但在图像块较大时计算量比DSST高。
所以尺度检测DSST并不总是比SAMF好，其实，在VOT2015和VOT2016上SAMF都是超过DSST的，当然这主要是因为特征更好，但至少说明尺度方法不差。虽然DSST比SAMF更具创新度，但SAMF也是很优秀的方法。(记得高中数学老师说过，“一个人一生能有一点点创新就非常了不起了”，所以我们才会看到那么那么多灌水论文，创新真的太难了，那些虽然创新力不够但踏踏实实有效果，敢公开源码经得起验证的论文同样值得钦佩)
DSST一定要33个尺度吗？
如果你认真跑过实验，就会发现DSST标配的33个尺度非常非常敏感，轻易降低尺度数量，即使你增加相应步长，尺度滤波器也会完全跟不上尺度变化。关于这一点我想到的可能解释是，训练尺度滤波器用的是一维样本，而且没有循环移位，这就意味着一次训练更新只有33个样本，如果降低样本数量，会造成训练不足，分类器判别力严重下降，不像平移滤波器有非常多的移位样本(如果不对或您有其他看法欢迎交流)。总之，请不要轻易尝试大幅降低尺度数量，如果非要用尺度滤波器33和1.02就好。