matlab求kcf算法响应图_Kernelized Correlation Filters(KCF)算法
目前，在online visual tracking这一领域内已出现了众多先进的跟踪算法，在这一领域内已出现了众多先进的跟踪算法，在这一领域内已出现了众多先进的跟踪算法，在这一领域内已出现了众多先进的跟踪算法。
在这一领域内已出现了众多先进的跟踪算法，在这一领域内已出现了众多先进的跟踪算法。
目前在online visual tracking这个领域,已经涌现出很多的跟踪算法,比较知名如TLD,Struck,OAB,CT等等。
但是在实际应用中,真正能够实现快速追踪并且保持良好效果的却相对较少,许多现有方法虽然支持实时处理,但一般仅适用于中分辨率图像同样适用。
此前我在博客中提到过一篇对该领域的综述文章1,系统性地对大部分主流算法进行了评估与分析。
基于包含50个视频的数据集对29种跟踪算法进行了测试,其中表现优异的是TLD2和Struck3两种方法。
其中Struck方法平均运行速度约为20帧每秒,TLD方法稍快一些,平均运行速度约为28帧每秒。
然而即使如此,TFCF4方法于2014年提出后仍然提升了速度表现,
并在同样的测试数据集上(使用HOG特征的情况下),将平均运行速度提升至172帧每秒。
研究表明该方法相较于Struck和TLD具有更高的准确率，
其高效性源于通过巧妙设计循环偏移构建训练样本的方式,
从而使得数据矩阵呈现出循环矩阵的特点，
进而将问题求解转移到了傅里叶变换域,
成功避免了传统矩阵求逆过程,
显著降低了计算复杂度。
问题阐述
目前主要流行于跟踪检测方法的思想仍然是基于tracking by detection框架进行研究，并且在训练集的选择上基本都以目标为中心区域作为正样例来源，在周围区域提取负样例作为背景区域。大多数算法都是采用二元分类的方式来标记训练集中的样例数据集[1]：将正样例标签设为1（positive），负样例设为0（negative）。然而这种简单的二元分类标记方法存在一个明显的问题就是无法充分体现出各个负样例的重要性特征：离目标中心位置较远的位置赋予相同的权重与离目标中心位置较近的位置具有不同的重要性权值是不合理的[2]。因此有学者提出采用连续值来表示各个样例的重要性特征：具体而言就是根据样例到目标中心位置的距离远近分别赋值一个介于[0,1]范围内的数值，在距离目标越近的位置赋予更高的权重而在距离目标越远的位置则赋予较低的权重这样的处理能够更合理地反映各自由其自身位置特异性所导致的影响程度[3]。实践证明这种方法确实能够取得更好的效果例如在Struck和KCF等相关算法中都有较为成功的应用实例：其中Struck通过引入一种隐式的损失函数实现了对这种连续性标记方法的有效模仿而KCF则是直接利用了该方法的核心思想并将其应用于回归问题中从而实现了对不同偏移条件下样例重要性权值的有效刻画
首先介绍一个简单的线性回归模型接着讨论引入核之后的情况样本的训练过程本质上属于一种带正则化的最小二乘问题它具有闭式解考虑给定一组训练样本及其对应的输出值我们的目标是找到一个参数向量\mathbf{w}使得以下损失函数达到最小
minw∑i(f(xi)?yi)2+λ∥w∥2(1)(1)minw∑i(f(xi)?yi)2+λ∥w∥2
在模型中，在公式推导过程中使用了λλ这一项作为正则化系数来防止过拟合现象的发生。针对上述方程组的求解问题，在数学优化框架内可采用闭式解析解的方式进行计算得到所需结果。该问题的闭式解析解可通过线性最小二乘法框架内推导获得
w=(XTX+λI)?1XTy(2)(2)w=(XTX+λI)?1XTy
此处XX表示每行包含一个样本的特征向量所组成的样本矩阵；yy则代表每个样本对应的回归值y_i所构成的列向量；而II是一个单位矩阵。鉴于后续计算需要在傅里叶域进行处理，在此对复数情况下的求解过程进行说明：其中针对复数域的情况进行了相应的求解过程；其中X^H X即为XX的共轭转置；而w^*则表示ww在复数域中的共轭。
w?=(XHX+λI)?1XHy(3)(3)w?=(XHX+λI)?1XHy
现在的问题是：如果我们直接尝试求解这个闭式解？其中涉及的矩阵求逆运算在样本数量增加时会变得非常耗时。显然直接求解的方法并不高效。在这里，这篇论文的作者巧妙地将上述闭式解转换到傅里叶变换域中进行处理？从而避免了矩阵求逆运算？这大大减少了计算时间？这也是这篇论文的主要创新点所在。
DFT下的线性回归
为了解释的简明性，这里仅仅就一维的单通道信息做分析，也就是说这里的 xx 都是一维向量，当然推广到二维也是适用的，而且实际上代码中也的确就是在二维上做的。我们看到式 (3)(3) 中的样本矩阵 XX 如果是一个循环矩阵的话，该式子的计算就会变得容易很多。即，
X=C(x)=?????????x1xnxn?1?x2x2x1xn?x3x3x2x1?x4?????xnxn?1xn?2?x1?????????(4)(4)X=C(x)=[x1x2x3?xnxnx1x2?xn?1xn?1xnx1?xn?2?????x2x3x4?x1]
其中xx代表的是该循环排列的第一行元素；那么我们假设有这样一个完整的周期性结构存在；那么我们可以考察一下(3, 3)位置处的具体数值变化情况；接下来介绍该周期性结构的一个重要特性（标记为特性5）如下：
X=FHdiag(x)F(5)(5)X=FHdiag(x)F
在其中，在xx头上的那个小帽上标有xˆ（即为xx的傅里叶变换）。FF即为此处使用的离散傅里叶变换矩阵。满足关系式xˆ = F_x xˆ = F_x。将上述关系代入到式（3）中得到
w?= (F H diag(x^?) F F H diag(x^) F + λ I)^{-1} F H diag(x^?) F y = F^{-1} (diag(x^? ⊙ x^?) + λ I)^{-1} diag(x^?) F y = F^{-1} diag(x^{?} x^{?} ⊙ x^{+ λ}) F y \quad (6)
其中， ⊙⊙ 代表向量对应元素相乘，然后两边同时左乘 FF 得，
w?=x?⊙yx?⊙x+λ(7)(7)w?=x?⊙yx?⊙x+λ
目前而言，在经过上述一系列的转换操作之后，在研究过程中我们能够观察到权重向量 ww 的求解过程被转移到了傅里叶变换域内，并且计算量显著降低了。
构建循环样本矩阵
不同的提取训练方法：其中左图中的样本围绕base图像移动生成负样本；例如右图则是基于base图像进行周期性偏移生成负样本。
根据上述计算结果可以看出，在具备循环矩阵的情况下可以显著地加速样本的训练进程。这是否可行呢？我们接下来将考察一组基于目标中心周围偏移提取的正负训练样本。
从右图中可以看出，在实际应用中通常会将目标对象设为基准image base image，并在此基础上沿着其周围区域执行左右、上下方向上的偏移操作生成了一系列正sample用于模型训练（左图展示）。然而通过将基准image执行周期性偏移操作可以生成一组近似于真实negative sample的数据用于模型训练（右图展示）。为了缓解这一问题，在处理过程中会对基准image应用汉宁窗滤波器以减少边缘区域的影响程度。经过上述处理后形成的正sample集合构成了一个循环矩阵（如公式（4）所示）。
引入核函数
以上介绍的均为线性回归的情况；若能引入核函数，则分类器性能会更加高效。通过将特征空间映射至一个更高维度的空间中进行处理；这里我们假定这一映射关系由 φ(x) 定义，则分类器权重向量即相应地发生变化。
w=∑iαiφ(x)(8)(8)w=∑iαiφ(x)
我们主要关注参数 α 的确定过程，在这里 α={α1,α2,...,αi,...}^T 。考虑到我们无法直接明确该映射的具体形式（即核函数的作用机制），因此通常的做法是通过引入核函数的概念来间接描述这一过程。具体来说，在应用核方法时我们并不直接计算高维空间中的向量内积（即所谓的"kernel trick"），而是利用一个映射函数将低维空间中的数据点转换到高维特征空间后再进行处理。为了方便后续讨论，在此定义不同样本之间的核函数作用结果构成的矩阵为...
Kij=κ(xi,xj)(9)(9)Kij=κ(xi,xj)
这样最终的回归函数变为，
f(z)=wTz=∑i=1nαiκ(z,xi))(10)(10)f(z)=wTz=∑i=1nαiκ(z,xi))
相较于直接计算而言，该函数的求解耗时较多；基于循环矩阵的特点，我们提出了一种高效的核函数计算方案。
快速训练
基于核函数下的岭回归的解为6，
α=(K+λI)?1y(11)(11)α=(K+λI)?1y
其中所述的核函数矩阵K_K如式（9）所示。如果我们能够通过证明该矩阵是循环矩阵，则上式的求解过程就可以转移到DFT域中进行计算。
α?=ykxx+λ(12)(12)α?=ykxx+λ
这里， kxxkxx 是核函数矩阵 KK 的第一行元素组成的向量。
如果两个向量中的元素顺序发生变动时，不会影响通过核函数计算所得的结果，则由该核函数构成的矩阵即为循环矩阵。例如高斯核函数与多项式核函数都属于满足上述条件的例子。
快速检测
前面已经指出直接计算方式（10）（10）较为耗时，在这种情况下采用类似（9）（9）的有效方法即可解决该问题。具体而言，则是以构造测试集与训练集对应的核函数矩阵作为基础。
Kz=C(kxz)(13)(13)Kz=C(kxz)
其中
f(z)=(Kz)Tα(14)(14)f(z)=(Kz)Tα
值得注意的是，在本节中使用的f(z)与式(10)不同之处在于它是一个由基于base样本z的不同循环偏移下的响应值组成的向量。基于循环矩阵的性质（如前所述, 见图/表5所示），将上述方程转换至DFT域后，
f(z)=(kxz)?⊙α(15)(15)f(z)=(kxz)?⊙α
快速计算核函数相关性
当前阶段只剩下前面部分提及的kxxkxx和kxzkxz尚未明确说明如何计算。首先需要说明的是其计算公式的具体形式。
kxx′=g(C(x′)x)(16)(16)kxx′=g(C(x′)x)
其中g(x)是核函数,C(⋅,x′)是一个基于x'为第一行的循环矩阵.参考式（5）所示循环矩阵具有的特性,将其代入上式可得
kxx′=g(F?1(x⊙x?))(17)(17)kxx′=g(F?1(x⊙x?))
所以，对于多项式核函数，其计算公式如下，
kxx′=(F?1(x⊙x?)+a)b(18)(18)kxx′=(F?1(x⊙x?)+a)b
对于高斯核函数，其计算公式如下，
kxx′=exp(?1σ2(∥x∥2+∥x′∥2?2F?1(x⊙x?)))(19)(19)kxx′=exp(?1σ2(∥x∥2+∥x′∥2?2F?1(x⊙x?)))
总结
在速度方面具有显著优势的情况下
Referenced Y. Wu, J. Lim, and M.-H. Yang's work on "Online object tracking: A benchmark" was published in the 2013 IEEE Conference on Computer vision and pattern recognition (CVPR), covering pages 2411 to 2418.
注
S.Hare,A.Saffari,andP.H.S.Torr,"Struck:StructuredOutputTrackingwithKernels",2011IEEEInternationalConferenceonComputerVision(ICCV),pp.263-270,2011
J. F. Henriques et al., '实现高速目标跟踪技术: 核相关滤镜方法,' IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014
R. M. Gray, Toeplitz and circulant matrices: A review: now publishers inc, 2006.
R. Rifkin, G. Yeo, and T. Poggio, "A method for regularized least-squares classification," Nato Science Series II: Computer and Systems Sciences, vol. 190, pp. 131-154, 2003."