KCF算法全称是Kernelized Correlation Filters，是在2014年由Joao F. Henriques, Rui Caseiro, Pedro Martins, and Jorge Batista提出来的跟踪算法，这个算法不论是在跟踪效果还是跟踪速度上都有十分亮眼的表现。该算法主要使用循环矩阵对样本进行采集，使用快速傅里叶变换对算法进行加速计算。

第一部分 线性回归

Linear regression

       首先介绍一下脊回归，线性回归函数是f(z)=wTz，给定样本xi和对应的标签yi，目标是优化最大平方和误差来求出参数w，即

       其中λ是正则化参数，来防止过拟合现象的发生，就像深度学习中的那样。这个函数的通用求解公式是

       其中，矩阵X的每一行对应着一个向量xi，向量y的每一个值对应着yi，I是一个单位矩阵。

       ，每个样本是一个n*1维的向量

       ，X一共有m个样本

      

      

      

Cyclic shifts

       为了简单说明这种操作，先考虑一个通道，一维信号的情况。考虑一个n*1的向量x来表示一个感兴趣区域，把它当作一个基本样本，我们的目标是用基本样本(一个正样本)和通过移位操作来得到的几个虚假样本(作为负样本)来训练分类器。我们可以用循环移位算子来模拟这个向量的一维平移操作，用P矩阵来操作，P是n*n的矩阵：

                                                                       

       通过用P矩阵和向量x相乘的方式，我们就可以得到另一个向量，那么再用P*Px我们就可以再得到一个不同的向量，我们就可以说，通过在x向量前面乘上P的1到n-1次幂，我们能得到n-1个不同的虚假向量，得到新的负样本，如下图所示：

       对于二维图片，经过这种平移操作，可以得到很多张新的图片，如下图所示：

 

Circulant matrices

       经过上面的操作，我们只需要给出一个样本，我们就能生成n个不同的样本，那么对于求解脊回归问题，我们给出一个基础向量x=[x1,x2,x3,…,xn]T，然后我们就能得到X了：

       带入到上面脊回归的求解公式，我们就可以计算出w了，是不是很巧妙呐。可是如果进行这种矩阵运算求解还是很复杂，所以怎么办呐？一个非常令人震惊的有用的发现出现了，所有的循环矩阵都能够在傅氏空间中使用离散傅里叶矩阵进行对角化，X相似于对角阵

       其中对应于生成X的向量(就是X的第一行矩阵)x傅里叶变化后的值，=F(x)=，F是离散傅里叶矩阵，是常量

 

Putting it all together

       现在我们发现可以用上面的方式在求X了，上面脊回归在傅里叶域的求解方法是这样的

       然后我们就可以X=带入上面的公式里了

注意这里的分号是点除运算，就是对应元素相除。因为

 

所以

                                                                                      

       非常简洁高效的公式，不由得说一句，数学真美！！！

第二部分 非线性回归

Kernel trick – brief overview

       对于非线性回归问题来说，我们希望找到一个非线性映射函数，使映射后的函数在线性空间下是可分的，那么对于非线性回归问题我们就可以描述为找到一个回归函数，给定样本xi和对应的标签yi，目标是优化最大平方和误差来求出参数w。

       设w由训练样本的非线性变换ψ(xi)的线性组合构成：

       记κ(xi,xj)=ψ(xi)ψ(xj)，称为核函数。所以

       ，,k(z)中的第i个元素为训练样本xi和测试样本z的核函数值。

Fast kernel regression

f(z)是关于z的非线性函数，但却是关于κ(z)的线性函数，可以使用线性函数的优化方法求解α。

       K是所有训练样本的核相关矩阵。如果核函数选择得当，使得x内部元素顺序更换不影响核函数取值，则可以保证K也是循环矩阵。以下核都满足这样的条件：

这里k是核相关矩阵的第一行，表示原始生成向量x0和移位了i的向量xi的核函数。

       两者都是同一个向量和自身位移结果进行运算。因为所有涉及到的核函数都只和位移的绝对值有关，所以ki=kN−i，即k是对称向量。因为对称向量的傅里叶变换是实数，有：

Fast detection

       对于第一帧图像来说，在第一帧标注好的框的周围划分一个上下文目标区域，得到训练样本和标签来训练检测器，其中训练集是由上下文目标区域和由其移位得到的若干样本组成，对应的标签是根据距离越近正样本可能性越大的准则赋值的，然后可以得到α。

假设我们要预测第二帧图中目标的位置，我们就在上一帧框的附近划分一个感兴趣区域，对于这个感兴趣区域z，我们对这个感兴趣区域进行移位操作，即，，其中

                                                                                           

                                                       ，X是循环矩阵，每一行表示的是训练集x向量

                                                                                         

然后选择f(zj)值最大的作为新目标区域，由zj可以知道目标移动的位置。

定义是测试样本和训练样本在核空间上的核矩阵，。

       ，ψ(Z)中的每一行代表zj向量，1*n X n*n X n*n=1*n.

      ，因为是循环矩阵，所以，,类似前面的推导，                                                                                                     

第三部分 核相关矩阵快速计算

Dot-product and polynomial kernels

经过上面的推导，我们发现现在我们要计算的部分只有了。

对于内积和多项式核：

对于多项式核：

Radial Basis Function and Gaussian kernels

       对于径向基核：

       对于高斯核：

第四部分 多通道问题

       首先让我们来看一下二维特征怎么应用到上面的各种公式中去。

       设图片，假设存在一个函数，使，然后计算核相关矩阵K。

       移位生成的样本数量一共是m*n个，所以，。

       其中，是二维傅里叶变换矩阵，是生成块矩阵K的生成矩阵，是对进行傅里叶变换。

                                                                                    

       论文中在提取目标区域的特征时可以是灰度特征，但是使用Hog特征能够取得更好的效果，那么Hog特征该如何加入前面提到的模型呢？

       Hog特征是将图像划分成较小的局部块，称为cell，在cell里提取梯度信息，绘制梯度方向直方图，然后为了减小光照影响，将几个cell的方向直方图串在一起进行block归一化，最终将所有的cell直方图串联起来就是图像的特征啦。

那么，按照传统的方式一张图像就提取出一个向量，但是这个向量怎么用啊？我们又不能通过该向量的移位来获得采样样本，因为，你想啊，把直方图的一个bin循环移位有什么意义啊？

所以论文中Hog特征的提取是将sample区域划分成若干的区域，然后在每个区域提取特征，代码中是在每个区域提取了32维特征，即3XnOrients+5，其中nOrients=9就是梯度方向划分的bin个数，每个方向提取了3个特征，2个是对方向bin敏感的，1个是不敏感的，另外4个特征是关于表观纹理的特征还有一个是零，表示阶段特征。提取了31个特征(最后一个0不考虑)之后，不是串联起来，而是将每个cell的特征并起来，那么一幅图像得到的特征就是一个立体块，假设划分cell的结果是mXn,那么fhog提取结果就是mXnX31,我们就相当于得到了31张图片。那么就可以通过cell的位移来获得样本，这样对应的就是每一通道对应位置的移位，所有样本的第i通道都是有生成图像的第i通道移位获得的，所以独立的在每一个通道上计算，就可以利用循环矩阵的性质了。

对于线性核来说，求k的公式如下所示，其中xc和xc‘代表每个通道的图片：

同理对于高斯核来说，公式如下：

以此类推。。。

第五部分 整体代码和实验结果

 

从实验结果可以看出，用hog特征对跟踪效果有个非常大的提升。

第五部分 总结

KCF算法引入了hog特征和核方法，在跟踪的精度核速度上都取得了非常好的效果，但是KCF也有一些问题，比如它对尺度变化，高度运动和遮挡问题会很敏感。