目标跟踪算法—

一、前情提要

如果你对目标跟踪和KCF是什么东西还不了解的话欢迎你看前一篇博文KCF入门详解：http://blog.csdn.net/crazyice521/article/details/53525366。如果你已经对基于KCF的目标跟踪有了一定的了解，并想知道这个算法有怎么样的后续的发展的话，就请听我慢慢介绍以下的东西。

二、KCF的弊端

说道KCF的缺点的话作者在文章中也已经算是说明了，第一点，KCF因为在跟踪过程当中目标框是已经设定好的，从始至终大小为发生变化，但是我们的跟踪序列当中目标大小时有发生变化，这个就会导致跟踪器跟踪过程当中目标框漂移，从而导致跟踪失败。第二点，KCF对在跟踪过程当中当目标被遮挡时候的处理问题没有进行很好的解决，不过呢，这个问题一直也算是跟踪界的一个大难题，有哪位朋友有看到好的文章和算法的话请与我联系，欢迎赐教。

三、解决方法

（1）有问题就要解决，对于存在的这两个大的问题有什么解决方法呢，首先对于尺度的解决，近些年来解决比较好的就先看
1、Danelljan, Martin大神的Accurate Scale Estimation for Robust Visual Tracking论文代码都在这里下载（直接点击此处）。大神在文章中使用尺度池技术，对目标模版进行解决。
2、Yang Li大神的A Scale Adaptive Kernel Correlation Filter Tracker with Feature Integration
SAMF下载地址（直接点击此处）两篇文章大同小异，都是使用尺度模版不过是使用的个数不一样和对尺度设计的方法不一样，最终效果都是差不多。
两篇文章对尺度解决的细节我就不再叙述了，用一张图形象的描述一下两篇文章的思想：
对初试目标进行尺度缩放，经过相关滤波器之后得到对应的响应值response，然后比较各个不同尺度的response之间的大小，找到最大的一个，此时的尺度值即为最佳的目标尺度值，使用最佳尺度值对目标进行跟踪，能够解决目标跟踪过程当中目标尺度变化的问题。

（2）对于遮挡问题的解决就相对来说比较困难了，这个问题算是Long-term tracking 的问题。因为对于目标跟踪过程当中，跟踪器是没有办法知道目标是否被遮挡，是不是完全被遮挡还是被遮挡一部分的，对于我们人来说，这个我们很容易就能判断出来，但是对于计算机来说这个是很困难的，近些年来也提出一些方法，
比如使用分块的方法对目标进行跟踪：
1、2014年ICPR上的一篇文章Online Learning and Detection with Part-Based, Circulant Structure这个下载的话对于不会翻墙的同学比较麻烦，就传到云盘里面了，链接:https://pan.baidu.com/s/1hs3ehA8 密码: yi8v
2、基于分块的目标跟踪Real-time part-based visual tracking via adaptive correlation filters论文下载地址

图中很清晰的表达出来了分块的总体思想，就是把要跟踪的目标进行分割，分割成不同的部分去学习特征，然后分别进行跟踪，然后融合起来得到目标最终的位置。
3、马超大哥的Long-term correlation tracking

把跟踪分开一个对尺度预测，一个对目标外观变化通过上下文信息进行学习，使用KNN进行分类得到一个最好的目标位置。

四、其他方法

近些年来对于跟踪当中问题的解决方法的文章也是层出不穷，在这里我也没有办法把所有的文章都列出来完，只能算是把一些经典的东西展现出来给大家做一个参考，这样的话大家可以借助这些方法，进而可以搜素一些其他的相关文献，文章一直都在出，思想没有什么大变化，抓住核心思想，对问题的本质进行理解和探索，这样就能更好的解决问题。
一些其他的方法诸如PSR对跟踪过程当中目标是否遮挡进行判断，因为这个方法经过自己测试没发现特别大的作用，就不放出来了，有兴趣的可以自己搜索一下相关的文献看一下。

KCF是João F. Henriques的论文High-Speed Tracking with Kernelized Correlation Filters提出的一种目标跟踪算法。

KCF，由目标区域形成循环矩阵，再利用循环矩阵在傅立叶空间可对角化等一些性质，通过岭回归得到通用的预测公式，特别要说一点就是该预测公式没有矩阵求逆的计算，这都归功于作者巧妙地将循环矩阵在傅立叶空间的性质与目标跟踪时循环采样相结合，大大减少的计算量。

KCF的论文中分别实验了三种情形的岭回归，分别是普通线性岭回归、多项式岭回归、核空间下的岭回归。前两种不必多说，最后一种核空间，大家可以回忆一下SVM将低维空间映射到高维空间的方法，可以将线性不可分的样本变得线性可分。当然在KCF里由于要利用循环矩阵的性质，所以这里的核矩阵是循环矩阵（必为方阵）。

KCF跟踪算法是目标跟踪阶段中的目标搜索部分，因此目标特征表达可以有很多种选择，作者在论文用的是HOG，还有一些学者用了CNN之类的。

二、可能遇到得问题

（1）岭回归里面样本对应的输出y是什么？

答：y不是（0，1）标签哦，是高斯加权后的值。初始目标的位置在padding后的search window的中心，循环移位得到的多个样本反应的是背景信息，而且离中心越远，就越不是目标，所以我们对标签进行高斯加权就刚好可以体现这种可能性准则。KCF里的输出是一个二维response矩阵，里面元素的大小代表该位置下的目标为预测目标的可能性，因此，在训练的时候就是输入是特征，而输出是一个gaussian_shaped_label，一般分类的标签是二值的，或者多值离散的，但是这个高斯标签反应的是由初始目标移位采样形成的若干样本距离初识样本越近可能性越大的准则，在代码中，高斯的峰值被移动到了左上角（于是四个角的值偏大），原因是“after computing a cross-correlation between two images in the Fourier domain and converting back to the spatial domain, it is the top-left element of the result that corresponds to a shift of zero”，也就是说目标零位移对应的是左上角的值。这样一来，我们在预测目标位置的时候，只需要pos=pos+find(response==max(response(:)))就好。

（2）按照文章里面的公式，岭回归的输入是1D的，循环采样形成多个样本，然后并联成了矩阵X，而图像是2D的，循环采样后得到是矩阵块，那么这种情况是怎么应用到岭回归预测的？

答：注意这里不可以从线性空间的脊回归推导，因为2D样本无法写成岭回归的一般形式解。我们应在核空间推导，首先2D数据（大小为 m×n ）循环移位生成了 m×n 个样本，而2D情况下循环移位形成的样本通过高斯映射得到的核矩阵是块循环矩阵（这是一个定理），而块循环矩阵可以使用2D傅里叶变换矩阵对角化（这是二维循环矩阵傅里叶对角化的一个性质），至此，对角化再次实现，剩下的推倒就和1D形况下类似了。

（3）如果特征是灰度像素，那么特征就是个2D灰度图，应用到KCF比较好理解，那如果是多通道特征呢？假如HOG特征？

答：经典的HOG首先在cell内统计各方向梯度，然后串联block内的各个cell的输出并进行归一化用来减弱光照对特征的影响，最后再将所有block的输出串联，也就是说一副图片的HOG特征是一个一维向量，但在KCF里，我们假设把3通道图片分成了 m×n 个cell，然后梯度方向划分为9个，那么首先统计各个cell在0~40度之间的结果，完成所有cell在该梯度范围内的统计，我们就会得 m×n×1 的一个特征，因为特征个数为 3×9=27 ，所以最终我们会得到 m×n×27 的特征块（实际上fHOG是 m×n×31 ，还加了4个特征是关于表观纹理的特征），也就说没有采用串联，而是采用的并联，至此就和灰度特征差不多了，只不过厚度变成了31而不是1，KCF的代码中，在对这31个2D特征进行傅里叶变换后厚度压扁为1，具体操作是sum(x.conj(x), 3) / numel(x)，然后接下就和灰度特征的操作一模一样了。

（4）为什么对目标进行padding？

答：不padding的话怎么学习背景信息呢？你刚循环移位就把目标给打散了。所以padding就是能让样本中含有特别需要学习的背景信息，而且可以尽量保证样本中目标的完整性。

（5）文中的给padding后的图像加余弦窗的目的是什么？

答：如果不加余弦窗，我们可以想象，除了那个最原始样本，其他移动样本的边缘都比较突兀，也就说这些样本数据是比较差的，会干扰训练的结果。而如果加了余弦窗，由于图像边缘像素值就都接近0了，循环移位过程中只要目标保持完整那这个样本就是合理的，不过加了余弦窗也会弱化掉目标的背景信息，对训练也有一定的影响，不过总的来看应该是利大于弊。

（6）为何KCF论文里公式那么多，看起来及其复杂，但是实际代码那么简短？

答：KCF虽然原理复杂，但实现起来简单，而且速度快。本质上讲，KCF做的就是将循环矩阵在傅立叶空间的性质与图像中目标的循环移位采样结合，做出一系列的推导最终得出少数一般性的公式，这样在编程的时候直接用一般性公式就好，大大减少计算量，加快跟踪速度。

（7）KCF的缺点有？

答：首先就是对尺度变化的适应性不强，解决办法是加一个尺度变化的比例系数进行多次检测，代价是牺牲一些速度。第二个缺点对目标快速变形（假设用的是HOG特征）或颜色快速变化（假设用的是颜色特征）不鲁棒，这个好理解，毕竟HOG描述的就是形状信息，变化得太快必然会导致效果变差。第三个缺点是对物体快速运动或者低帧率视频不太鲁棒，这两中情况都是意味着在跟踪过程中下一帧图像中目标得位置偏离search window中心太远，要么靠近边缘，要么出去一半，要么全出去，我们是给样本加了余弦窗的，也就是说目标位置靠近边缘会由于余弦窗的存在损失了部分目标信息，更不用说那些目标超出search window一半或者全超出去的情况了，这也就是CF类算法中的边界效应（Boundary Effets）。