目标跟踪：KCF

Mar 20, 2017 1 minute read

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×nm×n）循环移位生成了m×nm×n个样本，而2D情况下循环移位形成的样本通过高斯映射得到的核矩阵是块循环矩阵（这是一个定理），而块循环矩阵可以使用2D傅里叶变换矩阵对角化（这是二维循环矩阵傅里叶对角化的一个性质），至此，对角化再次实现，剩下的推倒就和1D形况下类似了。

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

答：经典的HOG首先在cell内统计各方向梯度，然后串联block内的各个cell的输出并进行归一化用来减弱光照对特征的影响，最后再将所有block的输出串联，也就是说一副图片的HOG特征是一个一维向量，但在KCF里，我们假设把3通道图片分成了m×nm×n个cell，然后梯度方向划分为9个，那么首先统计各个cell在0~40度之间的结果，完成所有cell在该梯度范围内的统计，我们就会得m×n×1m×n×1的一个特征，因为特征个数为3×9=273×9=27，所以最终我们会得到m×n×27m×n×27的特征块（实际上fHOG是m×n×31m×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）。