KCF目标跟踪算法

最近刚开始学习単目标跟踪，最近想搞明白KCF的思想，看了一个星期的公式推导，要看哭了！！！！把自己现在已经知道的一些结论写下来理理思路。欢迎指正。

先说一下它的优点吧：

1.通过图片的矩阵循环，增加了训练样本，提高了正确率。

2.进行傅里叶变换，避免矩阵求逆操作，计算更快速。

3.使用高斯label，更合理。

现在来梳理一下它整个计算的流程：

1.目标函数：

（1）

我们的目标是最小化我们的采样数据xi的计算标签f(xi)与下一帧真实目标位置的真实标签yi（回归目标）的距离。（这个应该不难理解吧，我计算出来的标签越像真实标签，说明我找到的下一帧得得位置离它真实位置越近）

（2）

这个表示的形式为脊回归，下面的部分求解过程，可以参考SVM的求解过程。虽然不是一摸一样的形式，但是帮助理解本篇文章中的求解方式是非常有用的（“支持向量机通俗导论（理解SVM的三层境界）LaTex最新版_2015.1.9.pdf”这篇文章中关于表达式的意思和求解写的很清楚）

在线性问题中：

在求解这里的最小值的时候，将f(xi)根据公式（1）换成矩阵形式Wt*X（为什么可以转换成这种形式参考SVM），X的每一行表示一个采样结果的xi，X是经过第一行的xi不断循环得到的一个矩阵,Wt表示W的转置。y表示yi组成的向量。然后计算公式（2）对W的求导等于0可以得到：

（3） （4）

（4）式即将（3）式中的转置转换成了共轭，只要是考虑在下面的傅里叶转换中有负数的出现。

这里我们看到在求w得最小值的时候有矩阵求逆的操作，这使得计算量比较大。然而根据之前说的X是一个循环矩阵，形式为：

（5）

将矩阵进行傅立叶变换后，循环矩阵有一个性质:

---

(6)

即一个循环矩阵可以用它的第一行的向量进行傅里叶变换之后表示，x带一个帽子表示对向量x进行了傅里叶变换。傅里叶变换的具体理解可以参考：此篇傅里叶博客

对于如何进行傅里叶转换可以参考：傅里叶转换方法

然后就可以发现一个循环矩阵可以转换成用一个向量来表示。将（6）式带入（4）式化简：

w戴帽子的意思就是进行了傅里叶转换，这样就从一个矩阵的运算换到了向量的运算。减少了求逆的操作。

当然在大多数情况下我们解决的是非线性问题：

那我们就引进了高维求解和 核函数的概念（仔细的求解参考上文提到的SVM文章）。

在高维空间中非线性问题w可以变成一个线性问题。

（7）

fai(xi)表示将x映射到高位空间的函数。

那我们的目标函数就可以表示成

（8）

其中k表示核函数它的定义运算如下：

由（8）可见之前求最小w的问题转换成了求最小阿尔法的问题。将（8）带入（2）阿尔法的求解参考一篇文章“R. Rifkin, G. Yeo, and T. Poggio, “Regularized least-squares classification,Nato Science Series Sub Series III Computer and Systems Sciences, vol. 190, pp. 131–154, 2003.”

最后可以解得

（9）

进行傅里叶变换：

这里Kxx代表K矩阵的第一行元素的傅里叶变换。K也是一个循环矩阵可证，此处省略具体方式可参考“High-Speed Tracking with Kernelized Correlation Filters João F. Henriques, Rui Caseiro, Pedro Martins, and Jorge Batista”的5.2节。

这样（8）式可以表示成：

C（x）表示由向量x循环移位得到的矩阵

Kz是所有训练样本和候补patch之间的核矩阵

（9） 傅里叶变换后的形式

现在就剩讨论一下k的形式，如果k是线性核的话就可以转换成我们在讨论线性问题时求得的w的傅里叶转换之后的形式。本篇文章中用的是高斯核，形式如下：

高斯核

这就是里面用到的主要的公式的推倒吧。

推倒下一帧的地方时就是计算采样的特征和之前的训练完的数据做高斯匹配再与阿尔法相乘，得到的一个响应值最大的就是下一帧的可能值最大的地方。