本篇是基于单目标跟踪的论述 

目标跟踪概述

          1.1 定义：

                1，单目标，即在给定的视频中只跟踪一个目标

                2，在第一帧中会通过矩形的bounding box将目标给出。给定后，使用tracker找出每一帧的目标。

                3，短期

          1.2 目标跟踪面临的挑战有：

                1，运动模糊（Motion Blur）

                      

                      在获取视频时由于环境因素，相机抖动或物体运动等多种因素的影响，导致获取的视频帧像素退化，这种退化会导致角点，边缘等显著特征受损甚至消失。一般存在两种情况，当点扩散函数处于未知状态时，叫做盲去模糊，当点扩散函数已知时叫做非盲去模糊。

                2，遮挡（Occlusion）

                     

                     遮挡是目标跟踪中比较常见的挑战因素。遮挡又分为部分遮挡（Partial Occlusion）和完全遮挡（Full Occlusion）。解决部分遮挡目前较为常用的大致有两种思路：（1）利用检测机制判断目标是否被遮挡，从而决定是否更新模板，保证模板对遮挡的鲁棒性。（2）把目标分成多个块，利用没有被遮挡的块进行有效的跟踪。而对于完全遮挡目前并没有特别好的办法完全解决这个问题。

                3，形变（Deformation）（与第一帧差异过大）

                      

                      通常而言跟踪的目标并非一层不变的。而跟踪目标的形变，如果过大则会导致跟踪发生漂移（Drift）。而解决这个挑战的主要解决点就在解决漂移问题。常用的方法是更新目标的表观模型，使其适应表观的变化。因此面对这个问题时，至关重要的是模型更新方法。能否及时，准时更新，能否确定好更新的频率变成面对这个挑战时要关注的问题。

                4，尺度变化（Changing In Scale）（镜头的拉近或拉远）

                      

                      尺度变换是指目标在运动过程中距离拍摄的镜头距离的变化而产生的尺度大小的变化现象。由于尺度变换如果不能快速准确的预测出跟踪目标变化的系数就会影响跟踪的准确率。现在通常的做法有：（1）在运动模型产生候选样本的时候，生成大量的尺度大小不等的候选框，选择最优作为目标。（2）在多个不同尺度的目标上进行目标跟踪，产生多个预测结果，选择其中最优作为最后的预测目标。

                5，快速移动（Fast Motion）

                      

                      快速移动指的是要跟踪的目标在接下来的帧中，快速的变换位置。这样很可能会导致目标丢失，因此也是目标跟踪的一个比较重要的点。

                还有背景杂斑（Background Clutter），光照变化（illumination variation）等其他挑战。总而言之对于视觉跟踪而言，由于运动目标的运动场景大多较为复杂，并且经常发生变化，或者要跟踪的目标本身也会发生变化。这样就导致要考虑的问题变成了，如何在复杂变换的场景中识别并跟踪不断变化的目标。

                经过上述的方法总结就个人而言感觉视觉跟踪大致有两个比较困难的点：

                1.上述的各个挑战，由于要考虑的视频中跟踪的目标的具体情况不同，所以对应的挑战也不相同，想要一劳永逸的解决是不现实的。可能一个算法在面对一个挑战时表现的很好，但面对另一个挑战时表现的又很差。

                 2.缺乏训练样本，假如我们使用深度学习的方法来进行目标跟踪。那么我们需要对应的数据集来训练网络，但因为目标跟踪任务的特殊性，只有初始帧的图片数据可以利用，因此缺乏数据供神经网络学习。

          1.3 目标跟踪方法：

                就目前为止，追踪器大致分为两大类生成性追踪器和鉴别性追踪器。

                 （1）生成性追踪器（Generative Method）：通过在线学习的方式建立目标模型，然后使用模型搜索重建误差最小的图像区域，完成目标定位。这一类方法没有考虑目标的背景信息，图像信息没有得到较好的应用。通俗点讲就是在当前帧对目标区域建模，下一帧寻找与模型最相似的区域就是预测位置，比较著名的有卡尔曼滤波，粒子滤波，mean-shift等。

                 （2）鉴别性追踪器（Discriminative Method）：将目标跟踪看作是一个二元分类问题，同时提取目标和背景信息用来训练分类器，将目标从图像序列背景中分离出来，从而得到当前帧的目标位置。CV中的经典套路图像特征+机器学习， 当前帧以目标区域为正样本，背景区域为负样本，机器学习方法训练分类器，下一帧用训练好的分类器找最优区域：与生成类方法最大的区别是，分类器采用机器学习，训练中用到了背景信息，这样分类器就能专注区分前景和背景，所以判别类方法普遍都比生成类好。

          1.4 跟踪方法：

                稀疏表示(Sparse Representation)：对于生成性追踪器来说，较为典型的就是稀疏矩阵了。给定一组过完备字典，将输入信号用这组过完备字典线性表示，对线性表示的系数做一个稀疏性的约束（即使得系数向量的分量尽可能多的为0），那么这一过程就称为稀疏表示。基于稀疏表示的目标跟踪方法则将跟踪问题转化为稀疏逼近问题来求解。但实际上近些年来生成性追踪器使用的较少。因此系数表示也用的也比较少。基本上相关滤波和深度学习占据了目标跟踪的大半。

                相关滤波(Correlation Filter)：相关滤波本身源于信号领域。其基本思想为衡量两个信号是否相关，两个信号越相似，那么相关的操作越强。对于目标跟踪而言，对应的上一帧得到的目标与下一帧中的区域越相似，响应越高。通常使用卷积表示相关的操作。当其应用到目标跟踪上时，其基本思想就是，寻找一个滤波模板，让下一帧的图像与得到的滤波模板做卷积操作，响应最大的区域就是预测的目标。

                深度学习(CNN-Based)：对于神经网络来说由于CNN引入了卷积层和池化层的概念。而卷积层在输入的时候不仅考虑到了输入的值，还可以保持输入的形状不变。当输入数据是图像时，卷积层会以三维数据的形式接收输入数据，并且同样以三维数据的形式输出至下一层，因此，CNN可以正确理解图像等具有形状的数据。所以对于计算机视觉领域有着独特的优势。对于检测，人脸识别等早CNN早以发出自己的声音。但对于目标跟踪领域而言，开始并不顺畅。正如上文所述由于目标跟踪的特殊，只有初始帧的图片数据可以用，所以缺乏大量的数据供神经网络学习。直到后来将在分类图象数据集上训练的卷积神经网络应用到目标跟踪上后，基于深度学习的目标跟踪方法才得到充分的发展。

          1.5 数据集：

                OTB：OTB分为OTB50和OTB100，其中OTB100包含OTB50，该数据集的特点是人工标注的groundtruth，同时包含有25%的灰度数据集。

                VOT：本身是竞赛数据集更具有代表性。同时VOT每年更新。

                VOT与OTB的区别：这两个数据集都是目标跟踪常用的数据集，但还有一定的差别。

                 （1）OTB包括有25%的灰度序列，但VOT都是彩色序列，这也导致了很多颜色特征算法性能的差异。

                 （2）两个库的评价标准也不一样。

                 （3）OTB有随机帧开始，或者矩形框加随机干扰初始化去跑，但VOT是第一帧初始化跑，每次跟踪失败时，5帧之后重新初始化，VOT以短时跟踪为主，并且认为跟踪监测应该在一起不分离，detecter会多次初始化tracker。

 

目标跟踪基本流程

          2.1 基本流程

                单目标视觉跟踪的任务就是在给定某一个视频序列初始帧的目标大小与位置的情况下，预测后续帧中该目标的大小与位置，其基本流程如下图所示：

                              

                  输入初始化目标框，在下一帧中产生众多候选框（Motion Model），提取候选框的特征（Feature Extractor），然后对这些候选框评分（OBservation Model），最后在这些评分中找到一个最高得分的候选框作为预测的目标（Prediction A），或者对多个预测值进行融合（Ensemble）提高准确率。

                  基于上述过程将该流程大致分为以下五个模块进行研究：

                  1.运动模型（Motion Model）：基于对前一帧的估计，运动模型生成一组可能包含当前帧中目标的候选区域或包围盒。

                      运动模型旨在描述帧与帧目标运动状态之间的关系，显式或隐式地在视频帧中预测目标图像区域，并给出一组可能的候选区域。常用的有两种方法：粒子滤波和滑动窗口。其中粒子滤波是一种序贯贝叶斯推断方法，通过递归的方式推断目标的隐含状态。滑动窗口是一种穷举搜索方法，它列出目标附近的所有可能的样本作为候选样本。

                  2.特征提取（Feature Extractor）：征提取器使用一些特征表示候选集中的每个候选者。

                      适用于目标跟踪的特征一般要求，既能较好地描述跟踪目标又能快速计算。常用的特征也被分成两类：手工设计的特征和深度特征。常用的手工设计的特征有：灰度特征，颜色特征，纹理特征等。而深度特征则是通过大量的训练样本学习出来的特征，更具有鉴别性。

                 3.观测模型（Observation Model）：观察模型根据从候选人中提取的特征判断候选人是否是目标。

                    观测模型返回给定目标候选人的置信度，因此通常被认为是跟踪器的关键部件。与特征提取器和观察模型组件相比，运动模型对性能的影响一般很小。然而，在尺度变化和快速运动的情况下，合理地设置参数仍然是获得良好性能的关键。如上文中提到的，追踪器大致分为两大类生成性追踪器和鉴别性追踪器一致。观测模型可分为两类即生成式模型和鉴别式模型，生成式模型通常寻找与目标模板最为相似的候选作为跟踪结果，可简单视为模板匹配。较为常用为上文中提到的稀疏表示。而鉴别式模型则通过训练一个分类器去区分目标与背景，选择置信度最高的候选样本作为预测结果。判别式方法已经成为目标跟踪中的主流方法，如上文中提到的相关滤波，深度学习。

                 4.模型更新（Model Update）:模型更新器控制更新观测模型的策略和频率。它必须在模型适应和漂移之间取得平衡。

                    为了捕捉目标( 和背景) 在跟踪过程中的变化，目标跟踪需要包含一个在线更新机制，在跟踪过程中不断更新外观模型。在本文中考虑两种方法。1.每当目标可信度低于阈值时更新模型。这样做可以确保目标始终具有很高的信心。 2.当目标的置信度与背景样本的置信度之差低于阈值时，对模型进行更新。这种策略只是在正面和负面的例子之间保持足够大的差距，而不是强迫目标有很高的信心。

                   5.集成结果处理（Ensemble Method）：当一个跟踪系统由多个跟踪器组成时，集成后处理器获取组成跟踪器的输出，并使用集成学习方法将它们组合成最终结果。

                      单个跟踪器的结果有时可能非常不稳定，因为即使在很小的扰动下，性能也会发生很大的变化。参数采用集成方法的目的就是为了克服这一限制。

         2.2 总结

               由上述的过程可得知模块之间的关系为：运动模型负责描述帧与帧目标运动状态之间的关系，给出一组目标可能会出现的候选区域。特征提取则能够很好的跟随目标同时又保证计算较为简洁。而观测模型作用于当前帧，用来判断区域内是否是要跟踪的目标。因为在较长的跟踪过程中目标的特征可能会出现变化，因此需要一个目标更新模块来不时的对观测模型进行实时更新以此来确保跟踪目标的正确性。而单个跟踪器其结果不确定。并不能一定确保跟踪的稳定性。所以需要集成结果处理来确保结果的稳定性。

相关算法

          就目前来说相关滤波与深度学习在视觉目标跟踪领域占据主要的地位。如下图所示。

          

          3.1基于相关滤波的典型算法

               3.1.1相关滤波在视频跟踪的应用方法：设计一个对目标高响应，同时对背景低响应的滤波器，由此实现对目标模式的快速检测。简单来说就是设计一个滤波模板，利用该模板与目标候选区域做相关运算，最大输出响应的位置即为当前帧的目标位置。

               

                  其中y表示响应输出，x表示输入图像，w表示滤波模板。利用相关定理，将相关转换为计算量更小的点击。

                  

                   如上图所示的分别是y，x，w的傅里叶变换。而相关滤波的任务就是寻找最优的滤波模板w。

               3.1.2具体的算法：

                       （1）MOSSE

                                如同在3.1.1中所提出的相关滤波的应用方法一样，MOSSE的具体做法就是利用了信号处理中的相关性，通过提取目标特征来训练相关滤波器，对下一帧的输入图像进行滤波，当两个信号越相似（后一帧中图像的某个位置与前一帧用于训练的特征越相似），那么在该位置滤波器所计算得到的相关值越高。如下图所示为相关值得计算。

                                

                              其中g表示的是计算的相关值，f为输入的图像，h为滤波器模板。运算的过程大致如下，卷积中的卷积层和池化层。

                               

                                为了减少计算量，加快响应，通过快速傅里叶变换（FFT）将卷积操作变成了点乘操作。同时为了在每一帧后更新相关滤波器，采用将前面的图像都相加的办法，求得相加最小。

                                 所以MOSSE的工作流程大致为：

                                 1.先手动或者条件给定第一帧目标区域，提取特征。

                                 2.对下一帧输入图像裁剪下预测区域，进行特征提取，做FFT运算，与相关滤波相乘后将结果做IFFT运算，得到输出的相应点，其中最大响应点为该帧目标的位置。

                                 3.将该帧的目标区域加入到训练样本中，对相关滤波进行更新。

                                 4.重复步骤2，3.  

                       （2）CSK

                                CSK针对MOSSE采用稀疏采样造成样本冗余的问题，扩展了岭回归，基于循环移位的近似密集采样方法，以及核方法。

                                岭回归：

                                CSK为求解滤波模板的使用了岭回归。如下图：

                                 

                                   

                                  其中x是训练样本，而X是x构成的样本矩阵，y是样本的响应值，w是待求得滤波模板，而λ是正则化系数。使用岭回归为了防止过拟合。使得求到的滤波器在下一帧的图像中的泛化能力更强。

                                 循环移位：

                                 CSK的训练样本是通过循环移位产生的。密集采样与循环移位产生的样本很像，可以用循环移位来近似。循环矩阵原理如图，第一行是实际采集的目标特征，其他行周期性地把最后的矢量依次往前移产生的虚拟目标特征。

                                   

                                 对图像进行循环移位的效果实例如图

                                                 

                                

                                循环移位的样本集是隐性的，并没有真正产生过，只是在推导过程中用到，所以也不需要真正的内存空间去存储这些样本。同时生成的近似样本集结合FFT极大地减少了计算量，但这种近似引入边界效应。

                       （3）CN

                                MOSSE与CSK处理的都是单通道灰度图像。引入多通道特征扩展只需要对频域通道响应求和即可。HOG+CN在近年来的跟踪算法中是常用的特征搭配，HOG是梯度特征，而CN是颜色特征，二者可以互补。

                                CN其实是一种颜色的命名方式，与RGB,HSV同属于一类。CN在CSK的基础上扩展了多通道颜色。将RGB的3通道图像投影到11个颜色通道，，分别对应英语中常用的语言颜色分类，分别是black, blue, brown, grey, green, orange, pink, purple, red, white, yellow，并归一化得到10通道颜色特征。也可以利用PCA方法，将CN降维到2维。

                       （4）KCF/DCF

                                KCF可以说是对CSK的完善。论文中对岭回归、循环矩阵、核技巧、快速检测等做了完整的数学推导。KCF在CSK的基础上扩展了多通道特征。KCF采用的HoG特征，核函数有三种高斯核、线性核和多项式核，高斯核的精确度最高，线性核略低于高斯核，但速度上远快于高斯核。

                       在前面提到的挑战中有一种挑战是尺度变化。对于这一问题上述的KCF/DCF和CN都没有涉及到。这样的话如果目标发生尺度变化，那么滤波器就会学习到大量的背景信息，如果目标扩大，滤波器可能会跟踪到目标局部纹理。这两种情况都可能出现非预期的结果，导致跟踪漂移和失败。基于此提出SAMF（基于KCF，特征是HOG+CN。采用多尺度检测。取响应最大的平移位置及所在的尺度。因此可以同时检测目标中心变化和尺度变化），DSST（将目标跟踪分解为目标中心平移和目标尺度变化两个独立问题，这样对应的模块只负责一部分，如尺度滤波器仅需要检测出最佳匹配尺度无须关心平移的情况。）

          3.2基于深度学习的典型算法

                       （1）MDNet

                                MDNet直接使用跟踪视频预训练CNN获得的general目标表示能力，但实际上训练序列也存在问题，因为不同的视频中我们要跟定的目标是不相同的，可能这个视频中要跟踪的目标在下一个视频中就是背景，因此只使用单独一个CNN完成所有的训练序列中前景和背景区分的任务较为困难。

                              

                              上图包含了MDNet的基本思想。MD分为共享层和domain-specific层两部分。其具体做法是将每个训练序列当成一个单独的domain,每个domain都有一个针对它的二分类层(fc6)，用于区分当前序列的前景和背景，而网络之前的所有层都是序列共享的。这样共享层达到了学习跟踪序列中目标general的特征表达的目的，而domain-specific层又解决了不同训练序列分类目标不一致的问题。在具体的训练时，MDNet的每一个mini-batch只由一个特定序列的训练数据构成，只更新共享层和针对当前序列的特定fc6层。这样使得共享层获得了所有的序列共有特征的表达能力，而对应于特定序列的fc6层则只保存有当前序列的特征。

                              在具体的跟踪阶段，MDNet的主要做法为：

                              （1）随机初始化一个新的fc6层

                              （2）使用第一帧的数据来训练该序列的bounding box回归模型。

                              （3）用第一帧提取正样本和负样本，更新fc4，fc5和fc6层的权重。

                              （4）之后产生256个候选样本，并从中选择置信度最高的，之后做bounding-box regression得到的结果。

                              （5）如果当前帧的最终结果置信度比较高，那么采样更新样本库，否则根据情况对模型做短期或者长期的更新。

                       （2）TCNN

                                TCNN用了很多个CNN的模型，并构建成一棵树的结构，如图1所示，红色的框越粗说明对应的CNN模型的可靠性（reliability）越高。连接的红色的线越粗，说明两个CNN之间的相关性越高(affinity)。黑色的箭头越粗表示对应的CNN模型对目标估计的权重越高。TCNN还对每一个CNN模型进行了可靠性评估。如下图所示：

                                  

                                 每个CNN的网络结构是一样的，前面的卷积层的参数共享，是来自于事先用imageNet训练好的VGG-M网络，再加上后面的全连接层。构成了TCNN。其在第一帧的时候随机初始化并进行迭代训练，后面每次更新的时候都只更新全连接层的参数。如下图所示：

                                  

                                    总的来说TCNN效果较好，但差于ECO。

                                    效果好的原因：

                                    （1）使用了多个CNN模型进行检测（10个）

                                    （2）使用了树的结构来组织CNN模型，避免它们只对最近的帧过拟合

                                    （3）CNN会一直有新的模型加进来，且经过fine-tuning。

                                    （4）在确定最终的位置时还做了Bounding Box Regression，进一步提高定位准确性。

                       

          3.3深度学习与相关滤波相结合

                       （1）SRDCF&DeepSRDCF

                                SRDCF在KCF优化目标的基础上加入了空域正则化，增强了模型的判别能力，优化目标变为：

                                                  

                                其中的指的是对w施加的空间正则化权重。这表明，某些位置（主要是边界）的滤波器系数会受到惩罚。

                                

                               DCF（左）与SRDCF（右）的效果对比。

                               传统方式获取特征是HOG+CN，后来发现CNN浅层特征比HOG手工特征效果要好后。于是作者将SRDCF的模型更改为使用CNN，也就形成了一个新的模型，即：DeepSRDCF

                       （2）C-COT

                                使用一种隐式的插值方式将模型的学习投射到一个连续的空间域中，提出了一种在连续空间域上的卷积算子。C-COT将多种分辨率的深度特征进行了高效的集成，使得模型在各个数据集上的性能都得到了很大的提升。

                                

                              C-COT的特征图，卷积核，各层置信图和融合后连续空间的输出置信图。

                       （3）ECO

                                 ECO在C-COT的基础上进一步提升。主要有两点。①ECO降低了C-COT的参数量，对特征提取作了降维简化，提升效率，防止过拟合。②使用高斯混合模型生成不同样本组合，简化训练集的同时还增加了多样性；另外，提出了一种高效的模型更新策略，在提升速度的同时还提升了鲁棒性。

                                 

                                 C-COT学习后的卷积核与ECO学习后的卷积核。

                       （4）SiamFC

                                SiamFC开创了端到端深度学习相关滤波方法的先河，同时也为深度学习方法逐渐超越相关滤波方法拉开了序幕。其对应的网络如下：

                                

                                 图中φ是CNN编码器，而上下使用的两个CNN结构相同，同时参数也共享。而z和x分别是要跟踪的目标模板图像和新的一桢中的搜索范围（255*255）.二者经过同样的编码器后得到各自的特征图，对二者进行互相关运算后则会得到一个如上图所示的响应图（17*17），其每一个像素的值对应了x中与z等大的一个对应区域出现跟踪目标的概率。

                       （5）SiamRPN&DaSiamRPN

                                SiamRPN在x和y经过孪生CNN得到各自的特征图后，没有直接对二者进行互相关运算，而是将这两个特征图各自放入RPN部分的两个分支中，每个分支中的两个特征图分别经过一个CNN再进行互相关运算。RPN部分的两个分支分别用于进行目标概率的预测和目标边框的回归，并且同样借鉴了目标检测领域的anchor方法，从而降低了目标边框回归的训练难度。                                 其具体步骤如下图：

                               

                              在SiamRPN提出之后，又提出其改进型------DaSiamRPN，对训练数据进行了增强以提升模型对同类别物体干扰的判别能力。同时，DaSiamRPN加入了增量学习的Distractor-aware模块，在运行时采样并更新模型的参数。使得模型模型能够更好的迁移到当前视频的域中。

  

                    

参考文献

          [1] 张微, 康宝生. 相关滤波目标跟踪进展综述[J]. 中国图象图形学报, 2017(8).

          [2] 李娟. 基于目标跟踪的视频去运动模糊[D]. 电子科技大学, 2016.

          [3] 吴小俊, 徐天阳, 须文波. 基于相关滤波的视频目标跟踪算法综述[J]. 指挥信息系统与技术,2017(3).

          [4] 王硕. 基于相关滤波的目标跟踪算法[D].

          [5] Wang N , Shi J , Yeung D Y , et al. Understanding and Diagnosing Visual Tracking Systems[J]. 2015.

          [6] https://www.zhihu.com/question/26493945/answer/156025576

          [7] https://www.cnblogs.com/jjwu/p/8512730.html

          [8] https://blog.csdn.net/qq_34919792/article/details/89893433

          [9] https://blog.csdn.net/zhu_hongji/article/details/80515031

          [10] https://blog.csdn.net/weixin_39467358/article/details/84568474

          [11] https://www.zhihu.com/question/26493945

         

          

                          

                             

 

月月我好想你啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

1.视觉目标跟踪基本流程与框架

 视觉目标（单目标）跟踪任务就是在给定某视频序列初始帧的目标大小与位置的情况下，预测后续帧中该目标的大小与位置。



 

 输入初始化目标框，在下一帧中产生众多候选框（Motion Model），提取这些候选框的特征（Feature Extractor），然后对这些候选框评分（Observation Model），最后在这些评分中找一个得分最高的候选框作为预测的目标（Prediction A），或者对多个预测值进行融合（Ensemble）得到更优的预测目标。

根据如上的框架，我们可以把目标跟踪划分为5项主要的研究内容. （1）运动模型：如何产生众多的候选样本。（2）特征提取：利用何种特征表示目标。（3）观测模型：如何为众多候选样本进行评分。（4）模型更新：如何更新观测模型使其适应目标的变化。（5）集成方法：如何融合多个决策获得一个更优的决策结果。下面分别简要介绍这5项研究内容。

运动模型（Motion Model）：生成候选样本的速度与质量直接决定了跟踪系统表现的优劣。常用的有两种方法：粒子滤波（Particle Filter）和滑动窗口（Sliding Window）。粒子滤波是一种序贯贝叶斯推断方法，通过递归的方式推断目标的隐含状态。而滑动窗口是一种穷举搜索方法，它列出目标附近的所有可能的样本作为候选样本。

特征提取（Feature Extractor）: 鉴别性的特征表示是目标跟踪的关键之一。常用的特征被分为两种类型：手工设计的特征（Hand-crafted feature）和深度特征（Deep feature）。常用的手工设计的特征有灰度特征（Gray），方向梯度直方图（HOG），哈尔特征（Haar-like），尺度不变特征（SIFT）等。与人为设计的特征不同，深度特征是通过大量的训练样本学习出来的特征，它比手工设计的特征更具有鉴别性。因此，利用深度特征的跟踪方法通常很轻松就能获得一个不错的效果。

观测模型（Observation Model）:大多数的跟踪方法主要集中在这一块的设计上。根据不同的思路，观测模型可分为两类：生成式模型（Generative Model）和判别式模型（Discriminative Model）. 生成式模型通常寻找与目标模板最相似的候选作为跟踪结果，这一过程可以视为模板匹配。常用的理论方法包括：子空间，稀疏表示，字典学习等。而判别式模型通过训练一个分类器去区分目标与背景，选择置信度最高的候选样本作为预测结果。判别式方法已经成为目标跟踪中的主流方法，因为有大量的机器学习方法可以利用。常用的理论方法包括：逻辑回归，岭回归，支持向量机，多示例学习，相关滤波等。

模型更新（Model Update）: 模型更新主要是更新观测模型，以适应目标表观的变化，防止跟踪过程发生漂移。模型更新没有一个统一的标准，通常认为目标的表观连续变化，所以常常会每一帧都更新一次模型。但也有人认为目标过去的表观对跟踪很重要，连续更新可能会丢失过去的表观信息，引入过多的噪音，因此利用长短期更新相结合的方式来解决这一问题。

集成方法（Ensemble Method）: 集成方法有利于提高模型的预测精度，也常常被视为一种提高跟踪准确率的有效手段。可以把集成方法笼统的划分为两类：在多个预测结果中选一个最好的，或是利用所有的预测加权平均。

2.视觉目标跟踪面临的挑战

视觉运动目标跟踪是一个极具挑战性的任务，因为对于运动目标而言，其运动的场景非常复杂并且经常发生变化，或是目标本身也会不断变化。那么如何在复杂场景中识别并跟踪不断变化的目标就成为一个挑战性的任务。如下图我们列出了目标跟踪中几个主要的挑战因素：





其中遮挡（Occlusion）是目标跟踪中最常见的挑战因素之一，遮挡又分为部分遮挡（Partial Occlusion）和完全遮挡（Full Occlusion）。解决部分遮挡通常有两种思路：（1）利用检测机制判断目标是否被遮挡，从而决定是否更新模板，保证模板对遮挡的鲁棒性。（2）把目标分成多个块，利用没有被遮挡的块进行有效的跟踪。对于目标被完全遮挡的情况，当前也并没有有效的方法能够完全解决。

形变（Deformation）也是目标跟踪中的一大难题，目标表观的不断变化，通常导致跟踪发生漂移（Drift）。解决漂移问题常用的方法是更新目标的表观模型，使其适应表观的变化，那么模型更新方法则成为了关键。什么时候更新，更新的频率多大是模型更新需要关注的问题。

背景杂斑（Background Clutter）指得是要跟踪的目标周围有非常相似的目标对跟踪造成了干扰。解决这类问题常用的手段是利用目标的运动信息，预测运动的大致轨迹，防止跟踪器跟踪到相似的其他目标上，或是利用目标周围的大量样本框对分类器进行更新训练，提高分类器对背景与目标的辨别能力。

尺度变换（Scale Variation）是目标在运动过程中的由远及近或由近及远而产生的尺度大小变化的现象。预测目标框的大小也是目标跟踪中的一项挑战，如何又快又准确的预测出目标的尺度变化系数直接影响了跟踪的准确率。通常的做法有：在运动模型产生候选样本的时候，生成大量尺度大小不一的候选框，或是在多个不同尺度目标上进行目标跟踪，产生多个预测结果，选择其中最优的作为最后的预测目标。

        当然，除了上述几个常见的挑战外，还有一些其他的挑战性因素：光照（illumination）,低分辨率（Low Resolution）,运动模糊（Motion Blur）,快速运动（Fast Motion），超出视野（Out of View），旋转（Rotation）等。所有的这些挑战因数共同决定了目标跟踪是一项极为复杂的任务。

3.视觉目标跟踪方法

        视觉目标跟踪方法根据观测模型是生成式模型或判别式模型可以被分为生成式方法（Generative Method）和判别式方法（Discriminative Method）。前几年最火的生成式跟踪方法大概是稀疏编码（Sparse Coding）了, 而近来判别式跟踪方法逐渐占据了主流地位，以相关滤波（Correlation Filter）和深度学习（Deep Learning）为代表的判别式方法也取得了令人满意的效果。下面我们分别简要概括这几种方法的大体思想和其中的一些具体的跟踪方法。

稀疏表示(Sparse Representation)：给定一组过完备字典，将输入信号用这组过完备字典线性表示，对线性表示的系数做一个稀疏性的约束（即使得系数向量的分量尽可能多的为0），那么这一过程就称为稀疏表示。基于稀疏表示的目标跟踪方法则将跟踪问题转化为稀疏逼近问题来求解。如稀疏跟踪的开山之作L1Tracker, 认为候选样本可以被稀疏的表示通过目标模板和琐碎模板，而一个好的候选样本应该拥有更稀疏的系数向量。稀疏性可通过解决一个L1正则化的最小二乘优化问题获得，最后将与目标模板拥有最小重构误差的候选样本作为跟踪结果。L1Tracker中利用琐碎模板处理遮挡，利用对稀疏系数的非负约束解决背景杂斑问题。随后在L1Tracker基础上的改进则有很多，比较有代表性的有ALSA，L1APG等。

相关滤波(Correlation Filter)：相关滤波源于信号处理领域，相关性用于表示两个信号之间的相似程度，通常用卷积表示相关操作。那么基于相关滤波的跟踪方法的基本思想就是，寻找一个滤波模板，让下一帧的图像与我们的滤波模板做卷积操作，响应最大的区域则是预测的目标。根据这一思想先后提出了大量的基于相关滤波的方法，如最早的平方误差最小输出和（MOSSE）利用的就是最朴素的相关滤波思想的跟踪方法。随后基于MOSSE有了很多相关的改进，如引入核方法（Kernel Method）的CSK，KCF等都取得了很好的效果，特别是利用循环矩阵计算的KCF，跟踪速度惊人。在KCF的基础上又发展了一系列的方法用于处理各种挑战。如：DSST可以处理尺度变化，基于分块的（Reliable Patches）相关滤波方法可处理遮挡等。但是所有上述的基于相关滤波的方法都受到边界效应（Boundary Effect）的影响。为了克服这个问题SRDCF应运而生，SRDCF利用空间正则化惩罚了相关滤波系数获得了可与深度学习跟踪方法相比的结果。

深度学习（CNN-Based）：因为深度特征对目标拥有强大的表示能力，深度学习在计算机视觉的其他领域，如：检测，人脸识别中已经展现出巨大的潜力。但早前两年，深度学习在目标跟踪领域的应用并不顺利，因为目标跟踪任务的特殊性，只有初始帧的图片数据可以利用，因此缺乏大量的数据供神经网络学习。只到研究人员把在分类图像数据集上训练的卷积神经网络迁移到目标跟踪中来，基于深度学习的目标跟踪方法才得到充分的发展。如：CNN-SVM利用在ImageNet分类数据集上训练的卷积神经网络提取目标的特征，再利用传统的SVM方法做跟踪。与CNN-SVM提取最后一层的深度特征不同的是，FCN利用了目标的两个卷积层的特征构造了可以选择特征图的网络，这种方法比只利用最后的全连接层的CNN-SVM效果有些许的提升。随后HCF, HDT等方法则更加充分的利用了卷积神经网络各层的卷积特征，这些方法在相关滤波的基础上结合多层次卷积特征进一步的提升了跟踪效果。然而，跟踪任务与分类任务始终是不同的，分类任务关心的是区分类间差异，忽视类内的区别。目标跟踪任务关心的则是区分特定目标与背景，抑制同类目标。两个任务有着本质的区别，因此在分类数据集上预训练的网络可能并不完全适用于目标跟踪任务。于是，Nam设计了一个专门在跟踪视频序列上训练的多域（Multi-Domain）卷积神经网络（MDNet），结果取得了VOT2015比赛的第一名。但是MDNet在标准集上进行训练多少有一点过拟合的嫌疑，于是VOT2016比赛中禁止在标准跟踪数据集上进行训练。2016年SRDCF的作者继续发力，也利用了卷积神经网络提取目标特征然后结合相关滤波提出了C-COT的跟踪方法取得了VOT2016的冠军。

4.视觉目标跟踪最新进展

        目标跟踪最近几年发展迅速，以基于相关滤波（Correlation Filter）和卷积神经网络（CNN）的跟踪方法已经占据了目标跟踪的大半江山。如下图给出的2014-2017年以来表现排名靠前的一些跟踪方法。



可以看到前三名的方法不是基于相关滤波的方法就是基于卷积神经网络的方法,或是两者结合的方法。比如ECCV2016的C-COT就是在相关滤波的基础上结合卷积神经网络的杰作。下图给出这些方法在标准跟踪数据集OTB2013上的跟踪结果



可以看到基于卷积神经网络的方法取得了惊人的突破。预计未来两年相关滤波和卷积神经网络将仍然会是目标跟踪领域的主角。

Henriques, João F., et al. “High-speed tracking with kernelized

correlation filters.” Pattern Analysis and Machine Intelligence, IEEE

Transactions on 37.3 (2015): 583-596.

本文的跟踪方法效果甚好，速度奇高，思想和实现均十分简洁。其中利用循环矩阵进行快速计算的方法尤其值得学习。另外，作者在主页上十分慷慨地给出了各种语言的实现代码。

本文详细推导论文中的一系列步骤，包括论文中未能阐明的部分。请务必先参看这篇简介循环矩阵性质的博客。
思想
一般化的跟踪问题可以分解成如下几步：

在$I_t$帧中，在当前位置$p_t$附近采样，训练一个回归器。这个回归器能计算一个小窗口采样的响应。
在$I_{t+1}$帧中，在前一帧位置$p_t$附近采样，用前述回归器判断每个采样的响应。
响应最强的采样作为本帧位置$p_{t+1}$。

循环矩阵表示图像块
在图像中，循环位移操作可以用来近似采样窗口的位移。



训练时，围绕着当前位置进行的一系列位移采样可以用二维分块循环矩阵$X$表示，第ij块表示原始图像下移i行右移j列的结果。类似地，测试时，前一帧结果附近的一系列位移采样也可以用$X$表示。



这样的$X$可以利用傅里叶变换快速完成许多线性运算。
线性回归训练提速
此部分频繁用到了循环矩阵的各类性质，请参看这篇博客。

线性回归的最小二乘方法解为：

$w=\left( X^HX+\lambda I\right)^{-1}X^Hy$
根据循环矩阵乘法性质，$X^HX$的特征值为$\hat x \odot \hat x^*$。$I$本身就是一个循环矩阵，其生成向量为$[1,0,0...0]$，这个生成向量的傅里叶变换为全1向量，记为$\delta$。

$w=\left( Fdiag(\hat x \odot \hat x^*)F^H+\lambda Fdiag(\delta)F^H\right)^{-1}X^Hy$
$=\left( Fdiag(\hat x \odot \hat x^*+\lambda\delta)F^H \right)^{-1}X^Hy$
根据循环矩阵求逆性质，可以把矩阵求逆转换为特征值求逆。

$w=F\cdot diag\left(\frac{1}{\hat x \odot \hat x^*+\lambda\delta} \right) \cdot F^H X^H y$
$w=F\cdot diag\left(\frac{1}{\hat x \odot \hat x^*+\lambda\delta} \right) \cdot F^H \cdot Fdiag(\hat{x}^*)F^H\cdot y$
利用$F$的酉矩阵性质消元：

$w=F\cdot diag\left(\frac{\hat{x}^*}{\hat x \odot \hat x^*+\lambda\delta} \right) \cdot F^H \cdot y$
分号表示用1进行对位相除。

反用对角化性质：$Fdiag(y)F^H=C(\mathcal{F}^{-1}(y))$，上式的前三项还是一个循环矩阵。

$w=C\left( \mathcal{F}^{-1}\left( \frac{\hat{x}^*}{\hat x \odot \hat x^*+\lambda\delta}\right) \right) \cdot y$
利用循环矩阵卷积性质$\mathcal F(C(x)\cdot y)=\hat x ^* \odot \hat y$：

$\mathcal{F}(w)=\left( \frac{\hat{x}^*}{\hat x \odot \hat x^*+\lambda\delta}\right )^* \odot \mathcal  F(y)$

由于$\hat x \odot \hat x^*$的每个元素都是实数，所以共轭不变：
$\mathcal{F}(w)=\frac{\hat{x}}{\hat x \odot \hat x^*+\lambda\delta} \odot \mathcal F(y)=\frac{\hat{x}\odot \hat{y}}{\hat x \odot \hat x^*+\lambda\delta}$

论文中，最后这一步推导的分子部分写成$\hat x ^* \odot \hat y$，是错误的。但代码中没有涉及。

线性回归系数$\omega$可以通过向量的傅里叶变换和对位乘法计算得到。
核回归训练提速
不熟悉核方法的同学可以参看这篇博客的简单说明。核回归方法的回归式为：

$f(z)=\alpha^T \kappa(z)$

其中$\kappa(z)$表示测试样本$z$和所有训练样本的核函数。参数有闭式解：

$\alpha = \left( K + \lambda I\right)^{-1}y$
$K$为所有训练样本的核相关矩阵：$K_{ij}=\kappa(x_i,x_j)$。如果核函数选择得当，使得$x$内部元素顺序更换不影响核函数取值，则可以保证$K$也是循环矩阵。以下核都满足这样的条件：


设核相关矩阵的生成向量是$k$。推导和之前线性回归的套路非常类似：

$\alpha = \left( Fdiag(\hat k)F^H+Fdiag(\lambda\delta)F^H \right)^{-1}y=\left( Fdiag(\hat k + \lambda\delta)F^H \right)^{-1}y$
$=Fdiag\left(\frac{1}{\hat k + \lambda\delta}\right)F^Hy=C\left( \mathcal F^{-1} \left(\frac{1}{\hat k + \lambda\delta} \right) \right)y$
利用循环矩阵卷积性质$\mathcal F(C(x)\cdot y)=\hat x ^* \odot \hat y$：

$\hat{\alpha}=\left( \frac{1}{\hat k + \lambda\delta} \right)^* \odot \hat y$

这里$k$是核相关矩阵的第一行，表示原始生成向量$x^0$和移位了$i$的向量$x^i$的核函数。考察其处于对称位置上的两个元素：

$k_i=\kappa(x^0,x^i), k_{N-i}=\kappa(x^0,x^{N-i})$
两者都是同一个向量和自身位移结果进行运算。因为所有涉及到的核函数都只和位移的绝对值有关，所以$k_i=k_{N-i}$，即$k$是对称向量。

举例：$x^0=[1,2,3,4]$，$x^1=[4,1,2,3]$，$x^3=[2,3,4,1]$。使用多项式核$\kappa(x,y)=x^Ty$，容易验证$\kappa(x^0,x^1)=\kappa(x^0,x^3)$。

对称向量的傅里叶变换为实数，有：
$\hat{\alpha}=\left( \frac{1}{\hat k + \lambda\delta} \right) \odot \hat y=\frac{\hat y}{\hat k + \lambda\delta}$

论文中，利用$k$的对称性消除共轭的步骤没有提及。

线性回归系数$\alpha$可以通过向量的傅里叶变换和对位乘法计算得到。
核回归检测提速
所有待检测样本和所有训练样本的核相关矩阵为$K$，每一列对应一个待测样本。可以一次计算所有样本的响应（$N\times 1$向量）：
$y'=K^T\alpha$
利用循环矩阵的转置性质性质，$C^(k)$的特征值为$\hat k^*$：

$y'=C(k)^T\cdot \alpha=C(\hat k ^*)\cdot \alpha =k^**\alpha$
利用循环矩阵的卷积性质：

$y'=(k^*)*\alpha=k*\alpha$
两边傅里叶变换：

$\hat {y'}=\hat k \odot \hat \alpha$

论文中，利用转置消除共轭的步骤没有提及。

所有侯选块的检测响应可以通过向量的傅里叶变换和对位乘法计算得到。
核相关矩阵计算提速
无论训练还是检测，都需要计算核相关矩阵$K$的生成向量$k$。除了直接计算每一个核函数，在某些特定的核函数下可以进一步加速。
多项式核
$\kappa(x,y)=f\left( x^Ty\right)$
其中$f$为多项式函数。写成矩阵形式：

$K=f\left( X^T Y\right)$
$f$在矩阵的每个元素上单独进行。根据循环矩阵性质，$X^TY$也是一个循环矩阵，其生成向量为$\mathcal F^{-1}(\hat y\odot \hat x^*)$。所以核相关矩阵的生成向量为：

$k=f\left( \mathcal F^{-1}(\hat y\odot \hat x^*) \right)$
RBF核
$\kappa(x,y)=f(||x-y||^2)$

其中$f$是线性函数。简单展开：

$\kappa(x,y)=f(||x-y||^2)=f(||x||^2+||y||^2+2x^Ty)$

由于$X$中的所有$x$都通过循环移位获得，故$||x||^2$对于所有$x$是常数，同理$||y||^2$也是。所以核相关矩阵的生成向量为：

$k=f\left( ||x||^2 + ||y||^2+\mathcal F^{-1}(\hat y\odot \hat x^*) \right)$
其他核
有一些核函数，虽然能保证$K$是循环矩阵，但无法直接拆解出其特征值，快速得到生成向量。比如Hellinger核：$\sum_i\sqrt{x_iy_i}$，Intersection核：$\sum_i\min(x_i,y_i)$。
多通道
在多通道情况下（例如使用了HOG特征），生成向量$x$变成$M\times L$，其中$M$是样本像素数，$L$是特征维度。在上述所有计算中，需要更改的只有向量的内积：

$x^Ty=\sum_l(x^l)^Ty^l$

注：非常感谢GX1415926535和大家的帮助，发现原文一处错误。(21)式中不应有转置，应为：

$f(z)=K^z\alpha$

 

单目标跟踪OTB和VOT

http://cvlab.hanyang.ac.kr/tracker_benchmark/datasets.html