雷锋网（公众号：雷锋网） AI科技评论按：本文源自YaqiLYU在知乎问题【计算机视觉中，目前有哪些经典的目标跟踪算法？】下的回答，雷锋网 AI科技评论已获得授权发布，我来为大家科普一下关于多目标跟踪有哪些算法?下面希望有你要的答案，我们一起来看看吧!
多目标跟踪有哪些算法
雷锋网（公众号：雷锋网） AI科技评论按：本文源自YaqiLYU在知乎问题【计算机视觉中，目前有哪些经典的目标跟踪算法？】下的回答，雷锋网 AI科技评论已获得授权发布。
上部分内容请查阅计算机视觉中，究竟有哪些好用的目标跟踪算法（上）
五
VOT2015竞赛VOT2015 Challenge | Home（http://votchallenge.net/vot2015/） 如期而至，这一年有60个精挑细选的序列，62个tracker，最大看点是深度学习开始进击tracking，MDNet直接拿下当年的冠军，而结合深度特征的相关滤波方法DeepSRDCF是第二名，主要解决边界效应的SRDCF仅HOG特征排在第四：
随着VOT竞赛的影响力扩大，举办方也是用心良苦，经典的和顶尖的齐聚一堂，百家争鸣，多达62个tracker皇城PK，华山论剑。除了前面介绍的深度学习和相关滤波，还有结合object proposals（类物体区域检测）的EBT（EBT：Proposal与Tracking不得不说的秘密 - 知乎专栏）（http://zhuanlan.zhihu.com/p/26654891）排第三，Mean-Shift类颜色算法ASMS是推荐实时算法，还请注意另一个颜色算法DAT，而第9的那个Struck已经不是原来的了。除此之外，还能看到经典方法如OAB, STC, CMT, CT, NCC等都排在倒数位置， 经典方法已经被远远拉开了距离，所以在决定用那些经典方法之前，可以先测试几个新算法看看，说不定有惊喜。
在介绍SRDCF之前，先来分析下相关滤波有什么缺点。总体来说，相关滤波类方法对快速变形和快速运动情况的跟踪效果不好。
快速变形主要因为CF是模板类方法。容易跟丢这个比较好理解，前面分析了相关滤波是模板类方法，如果目标快速变形，那基于HOG的梯度模板肯定就跟不上了，如果快速变色，那基于CN的颜色模板肯定也就跟不上了。这个还和模型更新策略与更新速度有关，固定学习率的线性加权更新，如果学习率太大，部分或短暂遮挡和任何检测不准确，模型就会学习到背景信息，积累到一定程度模型跟着背景私奔了，一去不复返。如果学习率太小，目标已经变形了而模板还是那个模板，就会变得不认识目标。（举个例子，多年不见的同学，你很可能就认不出了，而经常见面的同学，即使变化很大你也认识，因为常见的同学在你大脑里面的模型在持续更新，而多年不见就是很久不更新）
快速运动主要是边界效应（Boundary Effets），而且边界效应产生的错误样本会造成分类器判别力不够强，下面分训练阶段和检测阶段分别讨论。
训练阶段，合成样本降低了判别能力。如果不加余弦窗，那么移位样本是长这样的：
除了那个最原始样本，其他样本都是“合成”的，100*100的图像块，只有1/10000的样本是真实的，这样的样本集根本不能拿来训练。如果加了余弦窗，由于图像边缘像素值都是0，循环移位过程中只要目标保持完整那这个样本就是合理的，只有目标中心接近边缘时，目标跨越边界的那些样本是错误的，这样虽不真实但合理的样本数量增加到了大约2/3（padding= 1），即使这样仍然有1/3（3000/10000）的样本是不合理的，这些样本会降低分类器的判别能力。再者，加余弦窗也不是“免费的”，余弦窗将图像块的边缘区域像素全部变成0，大量过滤掉分类器本来非常需要学习的背景信息，原本训练时判别器能看到的背景信息就非常有限，我们还加了个余弦窗挡住了背景，这样进一步降低了分类器的判别力（是不是上帝在我前遮住了帘。不是上帝，是余弦窗）。
检测阶段，相关滤波对快速运动的目标检测比较乏力。相关滤波训练的图像块和检测的图像块大小必须是一样的，这就是说你训练了一个100*100的滤波器，那你也只能检测100*100的区域，如果打算通过加更大的padding来扩展检测区域，那样除了扩展了复杂度，并不会有什么好处。目标运动可能是目标自身移动，或摄像机移动，按照目标在检测区域的位置分四种情况来看：
1、如果目标在中心附近，检测准确且成功。
2、如果目标移动到了边界附近但还没有出边界，加了余弦窗以后，部分目标像素会被过滤掉，这时候就没法保证这里的响应是全局最大的，而且，这时候的检测样本和训练过程中的那些不合理样本很像，所以很可能会失败。
3、如果目标的一部分已经移出了这个区域，而我们还要加余弦窗，很可能就过滤掉了仅存的目标像素，检测失败。
4、如果整个目标已经位移出了这个区域，那肯定就检测失败了。
以上就是边界效应（Boundary Effets），推荐两个主流的解决边界效应的方法，但速度比较慢，并不推荐用于实时场合。
一种方法是Martin Danelljan大牛的SRDCFLearning Spatially Regularized Correlation Filters for Visual Tracking（http://www.cvl.isy.liu.se/research/objrec/visualtracking/regvistrack/index.html），主要思路：既然边界效应发生在边界附近，那就忽略所有移位样本的边界部分像素，或者说边界附近滤波器系数为0：
Danelljan M, Hager G, Shahbaz Khan F, et al. Learning spatially regularized correlation filters for visual tracking [C]// ICCV. 2015.
SRDCF基于DCF，类SAMF多尺度，采用更大的检测区域（padding = 4），同时加入空域正则化，惩罚边界区域的滤波器系数，没有闭合解，采用高斯-塞德尔方法迭代优化。
另一种方法是Hamed Kiani提出的基于灰度特征MOSSE的CFLMCorrelation Filters with Limited Boundaries（http://www.hamedkiani.com/cfwlb.html）和基于HOG特征的BACF，主要思路是采用较大尺寸检测图像块和较小尺寸滤波器来提高真实样本的比例，或者说滤波器填充0以保持和检测图像一样大，同样没有闭合解，采用ADMM迭代优化：
Kiani Galoogahi H, Sim T, Lucey S. Correlation filters with limited boundaries [C]// CVPR, 2015.
Kiani Galoogahi H,, Fagg A, Lucey S.Learning Background-Aware Correlation Filters for Visual Tracking [C]// arXiv preprint arXiv:1703.04590, 2017.
其实这两个解决方案挺像的，都是用更大的检测和更新图像块，训练作用域比较小的相关滤波器，不同点是SRDCF的滤波器系数从中心到边缘平滑过渡到0，而CFLM直接用0填充滤波器边缘。
VOT2015相关滤波方面还有排在第二名，结合深度特征的DeepSRDCF，因为深度特征都非常慢，在CPU上别说高速，实时都到不了，虽然性能非常高，但这里就不推荐，先跳过。
六
标出来了前面介绍过的或比较重要的方法，结合多层深度特征的相关滤波C-COT排第一名，而CNN方法TCNN是VOT2016的冠军，作者和MDNet是同一人，纯颜色方法DAT和ASMS都在中等水平（其实两种方法实测表现非常接近），其他tracker的情况请参考论文。再来看速度，SMACF没有公开代码，ASMS依然那么快，排在前10的方法中也有两个速度比较快，分别是排第5的Staple，和其改进算法排第9的STAPLE ，而且STAPLE 是今年的推荐实时算法。首先恭喜Luca Bertinetto大牛的SiamFC和Staple都表现非常不错，然后再为大牛默哀三分钟（VOT2016的paper原文）：
This was particularly obvious in case of SiamFC trackers, which runs orders higher than realtime （albeit on GPU）, and Staple, which is realtime, but are incorrectly among the non-realtime trackers.
VOT2016竟然发生了乌龙事件，Staple在论文中是80FPS，怎么EFO在这里只有11？幸好公开代码有Staple和STAPLE ，有兴趣您可以去实测下，虽然我电脑不如Luca Bertinetto大牛，但Staple我也能跑60-70FPS，而更可笑的是，STAPLE 比Staple慢了大约7-8倍，竟然EFO高出4倍，到底怎么回事呢？
首先看Staple的代码，如果您直接下载Staple并设置params.visualization = 1来跑，Staple调用Computer Vision System Toolbox来显示序列图像，而恰好如果您没有这个工具箱，默认每帧都会用imshow（im）来显示图像所以非常非常慢，而设置params.visualization = 0就跑的飞快，建议您将显示图像部分代码替换成DSST中对应部分代码就可以正常跑和显示了。
再来看STAPLE 的代码，改进包括额外从颜色概率图中提取HOG特征，特征增加到56通道（Staple是28通道），平移检测额外加入了大位移光流运动估计的响应，所以才会这么慢，而且肯定会这么慢。
所以很大可能是VOT举办方把Staple和STAPLE 的EFO弄反了，VOT2016的实时推荐算法应该是排第5的Staple，相关滤波结合颜色方法，没有深度特征更没有CNN，跑80FPS还能排在第五，这就是接下来主要介绍的，2016年最NIUBILITY的目标跟踪算法之一Staple （让排在后面的一众深度学习算法汗颜，怀疑人生）。
颜色特征，在目标跟踪中颜色是个非常重要的特征，不管多少个人在一起，只要目标穿不同颜色的衣服就非常明显。前面介绍过2014年CVPR的CN是相关滤波框架下的模板颜色方法，这里隆重介绍统计颜色特征方法DATLearning, Recognition, and Surveillance @ ICG，帧率15FPS：
Possegger H, Mauthner T, Bischof H.In defense of color-based model-free tracking [C]// CVPR, 2015.
如果要用一句话介绍Luca Bertinetto大牛（牛津大学）的StapleStaple tracker（http://www.robots.ox.ac.uk/~luca/staple.html），那就是把模板特征方法DSST（基于DCF）和统计特征方法DAT结合：
Bertinetto L, ValmADRe J, Golodetz S, et al.Staple: Complementary Learners for Real-Time Tracking [C]// CVPR, 2016.
前面分析了相关滤波模板类特征（HOG）对快速变形和快速运动效果不好，但对运动模糊光照变化等情况比较好；而颜色统计特征（颜色直方图）对变形不敏感，而且不属于相关滤波框架没有边界效应，快速运动当然也是没问题的，但对光照变化和背景相似颜色不好。综上，这两类方法可以互补，也就是说DSST和DAT可以互补结合：
两个框架的算法高效无缝结合，25FPS的DSST和15FPS的DAT，而结合后速度竟然达到了80FPS。DSST框架把跟踪划分为两个问题，即平移检测和尺度检测，DAT就加在平移检测部分，相关滤波有一个响应图，像素级前景概率也有一个响应图，两个响应图线性加权得到最终响应图，其他部分与DSST类似，平移滤波器、尺度滤波器和颜色概率模型都以固定学习率线性加权更新。
另一种相关滤波结合颜色概率的方法是CSR-DCF，提出了空域可靠性和通道可靠性，13FPS性能直逼C-COT:
Luke？i？ A, Vojí？ T, ？ehovin L, et al.Discriminative Correlation Filter with Channel and Spatial Reliability [C]// CVPR, 2017.
CSR-DCF中的空域可靠性得到的二值掩膜就类似于CFLM中的掩膜矩阵P，在这里自适应选择更容易跟踪的目标区域且减小边界效应；以往多通道特征都是直接求和，而CSR-DCF中通道采用加权求和，而通道可靠性就是那个自适应加权系数。采用ADMM迭代优化。
相关滤波还有第一名的C-COT，和DeepSRDCF一样先跳过。
七
以前提到的很多CF算法，也包括VOT竞赛，都是针对short-term的跟踪问题，即短期跟踪，我们只关注短期内（如100~500帧）跟踪是否准确。但在实际应用场合，我们希望正确跟踪时间长一点，如几分钟或十几分钟，这就是长期跟踪问题。
Long-term就是希望tracker能长期正确跟踪，我们分析了前面介绍的方法不适合这种应用场合，必须是short-term tracker detecter配合才能实现正确的长期跟踪。
用一句话介绍Long-term，就是给普通tracker配一个detecter，在发现跟踪出错的时候调用自带detecter重新检测并矫正tracker。
接下来介绍CF方向一篇比较有代表性的long-term方法，马超大神的LCT chaoma99/lct-tracker（http://github.com/chaoma99/lct-tracker）：
Ma C, Yang X, Zhang C, et al.Long-term correlation tracking[C]// CVPR, 2015.
LCT在DSST一个平移相关滤波Rc和一个尺度相关滤波的基础上，又加入第三个负责检测目标置信度的相关滤波Rt，检测模块Online Detector是TLD中所用的随机蕨分类器（random fern），在代码中改为SVM。第三个相关滤波类似MOSSE不加padding，而且特征也不加cosine窗，放在平移检测之后。
LCT加入检测机制，对遮挡和出视野等情况理论上较好，速度27fps，实验只跑了OTB-2013，跟踪精度非常高，根据其他论文，LCT在OTB-2015和 VOT上效果略差一点可能是两个核心阈值没有自适应， 关于long-term，TLD和LCT的思想都值得参考 。
接下来介绍跟踪置信度。 跟踪算法需要能反映每一次跟踪结果的可靠程度，这一点非常重要，不然就可能造成跟丢了还不知道的情况。有两种指标可以反映相关滤波类方法的跟踪置信度：前面见过的最大响应值，和没见过的响应模式，或者综合反映这两点的指标。
LMCF（MM Wang的目标跟踪专栏：目标跟踪算法 - 知乎专栏）提出了多峰检测和高置信度更新：
Wang M, Liu Y, Huang Z.Large Margin Object Tracking with Circulant Feature Maps [C]// CVPR, 2017.
高置信度更新，只有在跟踪置信度比较高的时候才更新跟踪模型，避免目标模型被污染，同时提升速度。 第一个置信度指标是最大响应分数Fmax，就是最大响应值（Staple和LCT中都有提到）。第二个置信度指标是平均峰值相关能量（average peak-to correlation energy, APCE），反映响应图的波动程度和检测目标的置信水平，这个（可能）是目前最好的指标，推荐：
跟踪置信度指标还有，MOSSE中的峰值旁瓣比（Peak to Sidelobe Ratio, PSR）， 由相关滤波峰值，与11*11峰值窗口以外旁瓣的均值与标准差计算得到，推荐：
跟踪置信度指标还有，在CSR-DCF的空域可靠性中，也用了两个类似指标反映通道可靠性， 第一个指标也是每个通道的最大响应峰值，就是Fmax，第二个指标是响应图中第二和第一主模式之间的比率，反映每个通道响应中主模式的表现力，但需要先做极大值检测：
以上就是目前相关滤波方法中提到的比较好的跟踪置信度指标。
八
最后这部分是Martin Danelljan的专场，主要介绍他的一些工作，尤其是结合深度特征的相关滤波方法，代码都在他主页Visual Tracking（http://www.cvl.isy.liu.se/research/objrec/visualtracking/），就不一一贴出了。
Danelljan M, Shahbaz Khan F, Felsberg M, et al.Adaptive color attributes for real-time visual tracking [C]// CVPR, 2014.
在CN中提出了非常重要的多通道颜色特征Color Names，用于CSK框架取得非常好的效果，还提出了加速算法CN2，通过类PCA的自适应降维方法，对特征通道数量降维（10 -> 2），平滑项增加跨越不同特征子空间时的代价，也就是PCA中的协方差矩阵线性更新防止降维矩阵变化太大。
Danelljan M, Hager G, Khan F S, et al.Discriminative Scale Space Tracking [J]. IEEE TPAMI, 2017.
DSST是VOT2014的第一名，开创了平移滤波 尺度滤波的方式。在fDSST中对DSST进行加速，PCA方法将平移滤波HOG特征的通道降维（31 -> 18），QR方法将尺度滤波器~1000*17的特征降维到17*17，最后用三角插值（频域插值）将尺度数量从17插值到33以获得更精确的尺度定位。
SRDCF是VOT2015的第四名，为了减轻边界效应扩大检测区域，优化目标增加了空间约束项，用高斯-塞德尔方法迭代优化，并用牛顿法迭代优化平移检测的子网格精确目标定位。
Danelljan M, Hager G, Shahbaz Khan F, et al.Adaptive decontamination of the training set: A unified formulation for discriminative visual tracking [C]// CVPR, 2016.
SRDCFdecon在SRDCF的基础上，改进了样本和学习率问题。以前的相关滤波都是固定学习率线性加权更新模型，虽然这样比较简单不用保存以前样本，但在定位不准确、遮挡、背景扰动等情况会污染模型导致漂移。SRDCFdecon选择保存以往样本（图像块包括正，负样本），在优化目标函数中添加样本权重参数和正则项，采用交替凸搜索，首先固定样本权重，高斯-塞德尔方法迭代优化模型参数，然后固定模型参数，凸二次规划方法优化样本权重。
Danelljan M, Hager G, Shahbaz Khan F, et al.Convolutional features for correlation filter based visual tracking [C]// ICCVW, 2015.
DeepSRDCF是VOT2015的第二名，将SRDCF中的HOG特征替换为CNN中单层卷积层的深度特征（也就是卷积网络的激活值），效果有了极大提升。这里用imagenet-vgg-2048 network，VGG网络的迁移能力比较强，而且MatConvNet就是VGG组的，MATLAB调用非常方便。论文还测试了不同卷积层在目标跟踪任务中的表现：
第1层表现最好，第2和第5次之。由于卷积层数越高语义信息越多，但纹理细节越少，从1到4层越来越差的原因之一就是特征图的分辨率越来越低，但第5层反而很高，是因为包括完整的语义信息，判别力比较强（本来就是用来做识别的）。
注意区分这里的深度特征和基于深度学习的方法，深度特征来自ImageNet上预训练的图像分类网络，没有fine-turn这一过程，不存在过拟合的问题。而基于深度学习的方法大多需要在跟踪序列上end-to-end训练或fine-turn，如果样本数量和多样性有限就很可能过拟合。
Ma C, Huang J B, Yang X, et al.Hierarchical convolutional features for visual tracking [C]// ICCV, 2015.
值得一提的还有马超大神的HCF，结合多层卷积特征提升效果，用了VGG19的Conv5-4, Conv4-4和Conv3-4的激活值作为特征，所有特征都缩放到图像块分辨率，虽然按照论文应该是由粗到细确定目标，但代码中比较直接，三种卷积层的响应以固定权值1, 0.5, 0.02线性加权作为最终响应。虽然用了多层卷积特征，但没有关注边界效应而且线性加权的方式过于简单，HCF在VOT2016仅排在28名（单层卷积深度特征的DeepSRDCF是第13名）。
Danelljan M, Robinson A, Khan F S, et al.Beyond correlation filters: Learning continuous convolution operators for visual tracking [C]// ECCV, 2016.
C-COT是VOT2016的第一名，综合了SRDCF的空域正则化和SRDCFdecon的自适应样本权重，还将DeepSRDCF的单层卷积的深度特征扩展为多层卷积的深度特征（VGG第1和5层），为了应对不同卷积层分辨率不同的问题，提出了连续空间域插值转换操作，在训练之前通过频域隐式插值将特征图插值到连续空域，方便集成多分辨率特征图，并且保持定位的高精度。目标函数通过共轭梯度下降方法迭代优化，比高斯-塞德尔方法要快，自适应样本权值直接采用先验权值，没有交替凸优化过程，检测中用牛顿法迭代优化目标位置。
注意以上SRDCF, SRDCFdecon，DeepSRDCF，C-COT都无法实时，这一系列工作虽然效果越来越好，但也越来越复杂，在相关滤波越来越慢失去速度优势的时候，Martin Danelljan在2017CVPR的ECO来了一脚急刹车，大神来告诉我们什么叫又好又快，不忘初心：
Danelljan M, Bhat G, Khan F S, et al. ECO:Efficient Convolution Operators for Tracking [C]// CVPR, 2017.
ECO是C-COT的加速版，从模型大小、样本集大小和更新策略三个方面加速，速度比C-COT提升了20倍，加量还减价，EAO提升了13.3%，最最最厉害的是， hand-crafted features的ECO-HC有60FPS。吹完了，来看看具体做法。
第一减少模型参数，定义了factorized convolution operator（分解卷积操作），效果类似PCA，用PCA初始化，然后仅在第一帧优化这个降维矩阵，以后帧都直接用，简单来说就是有监督降维，深度特征时模型参数减少了80%。
第二减少样本数量， compact generative model（紧凑的样本集生成模型），采用Gaussian Mixture Model （GMM）合并相似样本，建立更具代表性和多样性的样本集，需要保存和优化的样本集数量降到C-COT的1/8。
第三改变更新策略，sparser updating scheme（稀疏更新策略），每隔5帧做一次优化更新模型参数，不但提高了算法速度，而且提高了对突变、遮挡等情况的稳定性。但样本集是每帧都更新的，稀疏更新并不会错过间隔期的样本变化信息。
ECO的成功当然还有很多细节，而且有些我也看的不是很懂，总之很厉害就是了。ECO实验跑了四个库（VOT2016, UAV123, OTB-2015, and TempleColor）都是第一，而且没有过拟合的问题，仅性能来说ECO是目前最好的相关滤波算法，也有可能是最好的目标跟踪算法。hand-crafted features版本的ECO-HC，降维部分原来HOG CN的42维特征降到13维，其他部分类似，实验结果虽然没给ECO-HC在VOT2016的结果，但其他三个都很高，而且论文给出速度是60FPS。
最后是来自Luca Bertinetto的CFNetEnd-to-end representation learning for Correlation Filter based tracking（http://www.robots.ox.ac.uk/~luca/cfnet.html），除了上面介绍的相关滤波结合深度特征，相关滤波也可以end-to-end方式在CNN中训练了：
Valmadre J, Bertinetto L, Henriques J F, et al. End-to-end representation learning for Correlation Filter based tracking [C]// CVPR, 2017.
在SiamFC的基础上，将相关滤波也作为CNN中的一层，最重要的是cf层的前向传播和反向传播公式推导，两层卷积层的CFNet在GPU上是75FPS，综合表现并没有很惊艳，可能是难以处理CF层的边界效应吧，持观望态度。
九
目前相关滤波方向贡献最多的是以下两个组（有创新有代码）：
牛津大学：Joao F. Henriques和Luca Bertinetto，代表：CSK, KCF/DCF, Staple, CFNet （其他SiamFC, Learnet）
林雪平大学：Martin Danelljan，代表：CN, DSST, SRDCF, DeepSRDCF, SRDCFdecon, C-COT, ECO
雷锋网版权文章，未经授权禁止转载。详情见转载须知。
