https://blog.csdn.net/crazyice521/article/details/53525366
http://www.cnblogs.com/YiXiaoZhou/p/5925019.html
一、算法介绍
KCF全称为Kernel Correlation Filter 核相关滤波算法。是在2014年由Joao F. Henriques, Rui Caseiro, Pedro Martins, and Jorge Batista提出来的，算法出来之后也算是轰动一时，这个算法不论是在跟踪效果还是跟踪速度上都有十分亮眼的表现，所以引起了一大批的学者对这个算法进行研究以及工业界也在陆续把这个算法应用在实际场景当中。这个算法主页里面有论文还有代码都可以在这里面下载，也有一些简介之类的，这篇文章在2015年作者又发在了TPAMI上面，所以大家可能会看到两个版本，但是没有改动，都是可以看到。论文下载地址相关滤波算法算是判别式跟踪，主要是使用给出的样本去训练一个判别分类器，判断跟踪到的是目标还是周围的背景信息。主要使用轮转矩阵对样本进行采集，使用快速傅里叶变化对算法进行加速计算。
二、详细介绍
这部分就直接根据论文当中的安排给大家解释一下，这样大家对照论文去看，也算是比较舒服的理解了。
Abstract：主要介绍了一下这篇文章的想法的由来以及算法的成就和所使用的东西，还介绍了一下论文在哪些数据集上测试了等。简介一般就是论文的总结，对论文做一个总体的介绍，大致的思想基本看了间接之后就能明白了，就是上面我写的那些，使用核相关滤波器训练一个判别式分类器，使用轮转矩阵生成样本去训练分类器，代码也是开源的。
1、Introduction
第一部分就是对整个跟踪的问题进行一个介绍，跟踪是计算机视觉领域一个比较重要的成分，可以应用在多种领域，人机交互、监控等我就不一一列举了，这个大家可以自己去查了，在第一部分比较重要的有这么几句话，Although the reasons for doing so are understandable, we argue that under sampling negatives is the main factor inhibiting performance in tracking. In this paper, we develop tools to analytically incorporate thousands of samples at different relative translations, without iterating over them explicitly. This is made possible by the discovery that, in the Fourier domain, some learning algorithms actually become easier as we add more samples, if we use a specific model for translations.
主要的意思就是说负样本对训练一个分类器是一个比较重要的存在，但是在训练的时候负样本的数量是比较少的，所以我们本文的算法就是为了更加方便地产生更多的样本，以便于我们能够训练一个更好的分类器。
Our framework easily incorporates multiple feature channels, and by using a linear kernel we show a fast extension of linear correlation filters to the multi-channel case.
相关滤波器是根据之前的MOSSE算法（论文地址）改进的，可以说是后来CSK、STC、Color Attributes等tracker的鼻祖。Correlation Filter（以下简称CF）源于信号处理领域，后被运用于图像分类等方面。而Correlation Filter应用于tracking方面最朴素的想法就是：相关是衡量两个信号相似值的度量，如果两个信号越相似，那么其相关值就越高，而在tracking的应用里，就是需要设计一个滤波模板，使得当它作用在跟踪目标上时，得到的响应最大，最大响应值的位置就是目标的位置。（详细的介绍大家可以参考一下王泥喜龙一的博客地址）如下图所示：
CSK（论文下载地址）是这个算法改进的初级版本，这篇是主要引进了循环矩阵生成样本，使用相关滤波器进行跟踪，本篇KCF是对CSK进行更进一步的改进，引进了多通道特征，可以使用比着灰度特征更好的HOG（梯度颜色直方图）特征或者其他的颜色特征等。
2、Related Work
2.1、基于检测的跟踪
这个听名字就比较好理解了，基于检测到的目标进行跟踪，首先在跟踪之前对目标进行检测，得到目标的位置，然后对目标进行学习，跟踪。
2.2、样本转换和相关滤波
对一些以前存在的样本转换的方法和相关滤波的一些知识进行一个介绍。For us, this hinted that a deeper connection between translated image patches and training algorithms was needed, in order to overcome the limitations of direct Fourier domain formulations.而且说出了样本和训练算法都是必须的，直接在频域使用傅里叶变化加快算法。
2.3、后来的工作
初始版本就是我上面说的CSK那篇，然后把多通道特征以及核函数这个加进来对算法进行提升。
3、Contributions
提出了一个快速的效果良好的跟踪算法，把以前只能用单通道的灰度特征改进为现在可以使用多通道的HOG特征或者其他特征，而且在现有算法中是表现比较好的，使用HOG替换掉了灰度特征，对实验部分进行了扩充，充分证明自己的效果是比较好的。使用核函数，对偶相关滤波去计算。
4、Building Blocks
4.1、 Linear regression
主要使用岭回归函数，能够像SVM那些有良好的表现。训练的目的就是找到这么一个函数使得我们的误差函数最小，在本文中使用的误差函数为
接下来的一切内容都是去讲怎么去最小化这个二次函数，以及怎么去找这个函数，这个方法也是比较简单的，就是对函数求导，然后使导数等于0，然后得到w，既是我们要求的函数。
4.2、Cyclic Shifts
本文的重点来了，循环矩阵，文章中为了介绍方便，作者使用了单通道一维的数据表示去进行讲解，可以直接扩展到二维的情况。一维的情况下就是矩阵想乘的问题了，就是矩阵分析当中学过的左乘一个单位矩阵和右乘一个单位矩阵。左乘是行变换，右乘列变化。目的就是得到更多的样本，每乘一次都是一个新的样本，这样的话就可以多出来n*n个样本了，这就是循环矩阵在这里最大的用处，制造样本的数量，以图像的形式展示就是这样的，一个样本经过循环矩阵之后就可以产生这么多的样本。
在二维图像的情况下就是像下图这样
把图像向上、向下分别移动不同的像素得到新的样本图像，这就是循环之后的样本，这样算是直接增加了样本的数量，然后用来对分类器进行训练，更多的样本肯定能够训练的分类器的效果就更好了。
4.3、Circulant matrices
循环矩阵的计算可以直接把所有的样本都转换为对角矩阵进行处理，因为在循环矩阵对样本进行处理的时候，样本并不是真实存在的样本，存在的只是虚拟的样本，可以直接利用循环矩阵所特有的特性，直接把样本矩阵转换为对角矩阵进行计算， 这样可以大幅度加快矩阵之间的计算，因为对角矩阵的运算只需要计算对角线上非零元素的值即可。Eq. 7 expresses the eigendecomposition of a general circulant matrix. The shared, deterministic eigenvectors Flie at the root of many uncommon features, such as commutativity or closed-form inversion. 说的意思就是大概是做了特征分解，其实是一个意思就是简化运算，加快速度。
4.4 Putting it all together
本节就是对上面w进行一个求解的过程，具体的公式推导的部分我不会做详细的推导，主要是我也不是很懂，哈哈，虽然自己推出来了，如果有想知道的或者大神希望指点，想要知道没有推出来的同学也可以问问我，我给你们说一下我的思路。
4.5 Relationship to Correlation filters
Correlation filters have been a part of signal processing since the 80’s, with solutions to a myriad of objective functions in the Fourier domain . Recently, they made a reappearance as MOSSE filters [9], which have shown remarkable performance in tracking, despite their simplicity and high FPS rate.
相关滤波一开始是信号处理的东西，经过MOSSE的发表之后引进到tracking 当中，因为计算的速度和精度都很不错，所以取得了很好的效果。
Circulant matrices allow us to enrich the toolset put forward by classical signal processing and modern correlation filters, and apply the Fourier trick to new algorithms.
循环矩阵丰富了样本库，给出了更好的相关滤波算法。
这一个小节可以好好看一下，就是相关滤波跟踪算法怎么来的。
5 Non-linear regression
使用非线性回归对模型进行训练。
5.1 Kernel trick- brief overview
核技巧，这个是本文的另外一大亮点，把低维空间的计算映射到高维的核空间，在低维空间不可分的情况到高维空间之后变的线性可分了，这样用一个简单的核函数直接做映射可以很好的完成这个工作。
核函数主要的目的就是把一个线性问题映射到一个非线性核空间，这样把在低维空间不可分的到核空间之后就能够可分了。
本章节接下来的部分就是对核技巧进行很好的解读了。
5.2 Fast kernel regression
快速的核回归。就是怎么去计算核函数，怎么快速得到最优解。
5.3 Fast detection
快速检测。核函数训练完成之后，新来的样本直接进行映射到核空间，然后使用训练得到的函数进行运算得到函数值，对所有的位置都进行计算，就能快速的检测到目标的位置所在。
6 Fast kernel Correlation
本节就是介绍了几种常见的核函数的形式，以及每种核函数所对应的计算方式。
6.1 Dot-product and polynomial kernels
6.2 Radial Basis Function and Gaussian kernels
6.3 Other kernels
7 MULTIPLE CHANNELS
In this section, we will see that working in the dual has the advantage of allowing multiple channels (such as the orientation bins of a HOG descriptor [20]) by simply summing over them in the Fourier domain. This characteristic extends to the linear case, simplifying the recently-proposed multi-channel correlation filters [31], [32], [33] considerably, under specific conditions.
7.1 General case
这个公式看明白了这一节就没什么问题了，无非就是单通道转换为多通道，使用高斯核函数。
7.2 Linear kernel
这个就是线性核函数多通道
In conclusion, for fast element-wise operations we can choose multiple channels (in the dual, obtaining the DCF) or multiple base samples (in the primal, obtaining the MOSSE), but not both at the same time. This has an important impact on time-critical applications, such as tracking. The general case [31] is much more expensive and suitable mostly for offline training applications.
8 EXPERIMENTS
8.1 Tracking pipeline
8.2 Evaluation
在50个序列集上进行测试对比。
最后结果是0.732，精度还是不错的，比着原有算法有大幅度提升。
9 CONCLUSIONS AND FUTURE WORK
In this work, we demonstrated that it is possible to analytically model natural image translations, showing that under some conditions the resulting data and kernel matrices become circulant. Their diagonalization by the DFT provides a general blueprint for creating fast algorithms that deal with translations. We have applied this blueprint to linear and kernel ridge regression, obtaining state-of-the-art trackers that run at hundreds of FPS and can be implemented with only a few lines of code. Extensions of our basic approach seem likely to be useful in other problems. Since the first version of this work, circulant data has been exploited successfully for other algorithms in detection [31] and video event retrieval [30]. An interesting direction for further work is to relax the assumption of periodic boundaries, which may improve performance. Many useful algorithms may also be obtained from the study of other objective functions with circulant data, including classical filters such as SDF or MACE [25], [26], and more robust loss functions than the squared loss. We also hope to generalize this framework to other operators, such as affine transformations or non-rigid deformations.
---------------------
作者：小小菜鸟一只
来源：CSDN
原文：https://blog.csdn.net/crazyice521/article/details/53525366
版权声明：本文为博主原创文章，转载请附上博文链接！
correlation filter
Kernelized correlation filter
tracking
读"J. F. Henriques, R. Caseiro, P. Martins, J. Batista, 'High-speed tracking with kernelized correlation filters'" 笔记
KCF是一种鉴别式追踪方法，这类方法一般都是在追踪过程中训练一个目标检测器，使用目标检测器去检测下一帧预测位置是否是目标，然后再使用新检测结果去更新训练集进而更新目标检测器。而在训练目标检测器时一般选取目标区域为正样本，目标的周围区域为负样本，当然越靠近目标的区域为正样本的可能性越大。
注意论文中关于向量是行向量还是列向量总是指示不清楚，所以本文对变量符号统一之后进行推导，首先所有的小写字母均表示列向量，所有的大写字母表示矩阵，其中矩阵的每一行是一个样本，文中的函数除了
是对行向量操作，其余都是对元素操做的，四则运算符号也都是针对元素操作的。还有所有对循环矩阵使用傅里叶变换时使用的生成向量都是循环矩阵的第一行向量，这点很重要。
使用目标周围区域的循环矩阵采集正负样本，利用脊回归训练目标检测器，并成功的利用循环矩阵在傅里叶空间可对角化的性质将矩阵的运算转化为向量的Hadamad积，即元素的点乘，大大降低了运算量，提高了运算速度，使算法满足实时性要求。
将线性空间的脊回归通过核函数映射到非线性空间，在非线性空间通过求解一个对偶问题和某些常见的约束，同样的可以使用循环矩阵傅里叶空间对角化简化计算。
给出了一种将多通道数据融入该算法的途径。
脊回归
设训练样本集
,那么其线性回归函数
,
是列向量表示权重系数，可通过最小二乘法求解
其中
用于控制系统的结构复杂性，也就是VC维以保证分类器的泛化性能。
写成矩阵形式
其中
的每一行表示一个向量，
是列向量，每个元素对应一个样本的标签，于是令导数为0，可求得
因为后面实在傅里叶域内计算，牵涉到复数矩阵，所以我们将结果都统一写成复数域中形式
其中
表示复共轭转置矩阵。
循环矩阵
KCF中所有的训练样本是由目标样本循环位移得到的，向量的循环可有排列矩阵得到，比如
当然对于二维图像的话，可以通过x轴和y轴分别循环移动实现不同位置的移动
举例
1474942884758.jpg
1474942898329.jpg
所以由一个向量
可以通过不断的乘上排列矩阵得到n个循环移位向量,将这n个向量依序排列到一个矩阵中，就形成了x生成的循环矩阵，表示成
1D向量得到的循环矩阵.jpg
2D图像不同循环次数后的移位.jpg
循环矩阵傅氏空间对角化
所有的循环矩阵都能够在傅氏空间中使用离散傅里叶矩阵进行对角化
其中x对应于生成X的向量(就是X的第一行矩阵)的傅里叶变化后的值，
,
是离散傅里叶矩阵，是常量
关于矩阵的傅里叶对角化请参加 循环矩阵傅里叶对角化,后面的笔记会专门讲解傅里叶变换。
傅氏对角化简化的脊回归
将
带入脊回归公式得到
注意这里的分号是点除运算，就是对应元素相除。因为
,（ 循环矩阵傅里叶对角化）对上式两边同时傅氏变换得
于是
这里和论文式(12)不一样，论文里(12)式分子上似乎多了个共轭符号,因为Appendix A.5中的式(55)后面那个
应该是少了个共轭转置符号。
这样就可以使用向量的点积运算取代矩阵运算，特别是求逆运算，大大提高了计算速度。
我们希望找到一个非线性映射函数
列向量,使映射后的样本在新空间中线性可分，那么在新空间中就可以使用脊回归来寻找一个分类器
,所以这时候得到的权重系数为
是
行向量张成的空间中的一个向量，所以可以令
上式就变为
该问题称为
的对偶问题
令关于列向量
导数为0,
注：
其实类似于核空间变量的协方差矩阵，矩阵的转置乘以矩阵，一定可逆。
对于核方法，我们一般不知道非线性映射函数
的具体形式，而只是刻画在核空间的核矩阵
，那么我们令
表示核空间的核矩阵，由核函数得到，那么
于是
论文提出的一个创新点就是使循环矩阵的傅氏对角化简化计算，所以这里如果希望计算
时可以同样将矩阵求逆运算变为元素运算，就希望将
对角化，所以希望找到一个核函数使对应的核矩阵式循环矩阵。
Theorem 1. Given circulant data C(x), the corresponding kernel matrix K is circulatant if the kernel function satisfies
,for any permutation matrix M.
即核矩阵是循环矩阵应该满足两个条件：第一个样本和第二个样本都是由生成样本循环移位产生的，可以不是由同一个样本生成；满足,其中
是排列矩阵。
证明：设
,则
,于是
因为K的第一行为
所以
相当于将第一行的第
个元素放到K的第i行j列上，
那么
就得到了循环矩阵，所以
是循环矩阵。证明里
表示除
的余数，因为这个过程是循环的。
证毕。
若K是循环矩阵，则
其中
是K中第一行。这里觉得奇怪？两个转置？这是因为我们已经约定
是列向量，而
的第i行是
，是不是明白了~
这里推出来的公式和论文中公式(17)也不大一样
那么那些核函数满足上述性质呢？论文中给出
Radial Basis Function kernels -e.g. Gaussian
Dot-Product kernels -e.g. linear, polynomial
Additive kernels - e.g. intersection, 
and Hellinger kernels
Exponentiated additive kernels.
首先由训练样本和标签训练检测器，其中训练集是由目标区域和由其移位得到的若干样本组成，对应的标签是根据距离越近正样本可能性越大的准则赋值的，然后可以得到
待分类样本集，即待检测样本集，是由预测区域和由其移位得到的样本集合
那么就可以选择
最大的样本作为检测出的新目标区域,由
判断目标移动的位置。
定义
是测试样本和训练样本间在核空间的核矩阵
由于核矩阵满足
,即
类似于theorem 1 的证明可得
是循环矩阵
我记得曾经见到过有人问
非方阵的情况，假设采样窗口非方形，即
那么采样窗口通过移位都会产生
个样本，无论是训练样本还是测试样本，所以
一定是方阵
于是得到各个测试样本的响应
注意我们说过小写的都是列向量，
是列向量。注意我们这里
是矩阵
的第一行，即
的第一列，而文中(22)式中
是论文中
的第一行，这是因为本文和论文中关于
的定义正好是相转置的。也就是说我觉得(22)式只是少了一个共轭。。。
觉得蛮奇怪的，怎么和论文中推导结果好多都差一个共轭符号？？
这是因为
都是对称向量，而对称向量的共轭转置是实数，所以就和论文中一样了，这点参考KCF高速跟踪详解
现在还存在的矩阵运算就是核矩阵的第一行的计算
内积和多项式核
这种核函数核矩阵可以表示成
，于是
因此对于多项式核
有
径向基核函数
比如高斯核，这类函数是
的函数
所以
对于高斯核则有
上面公式推导的很爽，可是都是在1D情况下得到了结论，2D图像该怎么办呢？
这个问题困扰了我好久。。。。刚开始我也想从线性空间的脊回归推导，假设
是目标图像，
是由
生成的循环矩阵块，即
表示
的第
块，是由
右移
，下移
得到的样本块。那么即使块循环矩阵能够通过2D傅里叶变换矩阵对角化又怎么用呢？？因为我们不可能带入
类似的式子中啊（这个式子是类比于1D脊回归写的，并无实际意义）
哎呀，想破脑袋啊！
啊哈，想明白了，线性假设下没办法用，直接在核空间推导，发现豁然开朗~
现在有一个函数
，自变量
,因变量
,也不知道怎么映射的，也不知道
是多少，反正是个确定但未知的值。那么在核空间我们就可以使用脊回归的公式了~
注意:由
移位生成的样本共有
个，所以
，这里
,
是对应样本的标签，
是对应样本标签的矩阵形式。
ok，现在再来看看定理2
Theorem 2. The block matrix
with elements
is a Block-Circulant Matrix (BCCM) if
is a unitarily invariant kernel.
这里和Theorem 1是类似的，a unitarily invariant kernel就是说,定理的证明参见Theorem 1.
而径向基核，dot-product kernel等都满足这个条件，所以得到的核矩阵都是块循环矩阵。
块循环矩阵可以使用2D傅里叶变换矩阵对角化（ 循环矩阵傅里叶对角化）
其中
是2D傅里叶变换矩阵，
是生成块循环矩阵
的生成矩阵，
表示对
进行2D傅里叶变换的结果。
ok，那现在
其中
表示全1的m维列向量。
这里的
分别对应着
的矩阵形式。
对应的响应
其中
表示块循环矩阵
的生成矩阵。
后面测试就类似于1D不推了
论文中在提取目标区域的特征时可以是灰度特征，但是使用Hog特征能够取得更好的效果，那么Hog特征该如何加入前面提到的模型呢？
Hog特征是将图像划分成较小的局部块，称为cell，在cell里提取梯度信息，绘制梯度方向直方图，然后为了减小光照影响，将几个cell的方向直方图串在一起进行block归一化，最终将所有的cell直方图串联起来就是图像的特征啦。
那么，按照传统的方式一张图像就提取出一个向量，但是这个向量怎么用啊？我们又不能通过该向量的移位来获得采样样本，因为，你想啊，把直方图的一个bin循环移位有什么意义啊？
所以论文中Hog特征的提取是将sample区域划分成若干的区域，然后再每个区域提取特征，代码中是在每个区域提取了32维特征，即
,其中
就是梯度方向划分的bin个数，每个方向提取了3个特征，2个是对方向bin敏感的，1个是不敏感的，另外4个特征是关于表观纹理的特征还有一个是零，表示阶段特征，具体参见fhog。提取了31个特征(最后一个0不考虑)之后，不是串联起来，而是将每个cell的特征并起来，那么一幅图像得到的结果就是一个立体块，假设划分cell的结果是
,那么fhog提取结果就是
,我们成31这个方向为通道。那么就可以通过cell的位移来获得样本，这样对应的就是每一通道对应位置的移位，所有样本的第i通道都是有生成图像的第i通道移位获得的，
，所以分开在每一个通道上计算，就可以利用循环矩阵的性质了。
我们来看1D的情况，1D弄明白了，2D也就明白咯，因为我们上面说了怎么推导2D的
样本cell数为M，每个cell特征维数为L,第
个样本的第
通道向量表示成
,样本的总特征可以表示成
.
于是K矩阵的第一行有
这里用到
这是dot product kernel的情况，那径向基核就很容易推了
多通道的处理.jpg
KCF相对于其他的tracking-by-detection方法速度得到了极大的提升，效果也相对较好，思想和实现十分简单。
KCF目标检测.jpg
借上图来总结下KCF的过程，左图是刚开始我们使用红色虚线框框定了目标，然后红色实线框就是使用的padding了，其他的框就是将padding循环移位之后对齐目标得到的样本，由这些样本就可以训练出一个分类器，当分类器设计好之后，来到了下一帧图像，也就是右图，这时候我们首先在预测区域也就是红色实线框区域采样，然后对该采样进行循环移位，对齐目标后就像图中显示的那个样子 了，（这是为了理解，实际中不用对齐。。。），就是周围那些框框啦，使用分类器对这些框框计算响应，显然这时候白色框响应最大，因为他和之前一帧红色框一样，那我们通过白色框的相对移位就能推测目标的位移了。
然后继续，再训练再检测。。。。
论文中还说到几点
对特征图像进行cosine window加权，这主要是为了减轻由于边界移位导致图像不光滑。
padding的size是目标框的2.5倍，肯定要使用padding窗口，要不然移位一次目标就被分解重组合了。。。效果能好哪去。。
对于标签使用了高斯加权
对
前后帧结果进行了线性插值，为了让他长记性，不至于模型剧烈变化。
但是其缺点也是很明显的。
依赖循环矩阵，对于多尺度的目标跟踪效果并不理想。当然可以通过设置多个size，在每个size上进行KCF运算，但这样的话很难确定应预先设置多少size，什么样的size，而且对size的遍历必将影响算法的速度。KCF最大的优势就是速度。
我在想能不能通过少量特征点的匹配来调整窗口的size，当然这样的话，速度也是个问题。
1475242117128.jpg
这种情况下还能保证最大响应就对应着目标中心所在的框吗？如果不能偏差会不会越来越大？
初始化矩阵不能自适应改变，其实这个问题和上一个缺点类似，这里强调的是非刚体运动，比如跳水运动员，刚开始选定区域肯定是个瘦长的矩形框，但当运动员开始屈体的时候显然这个预选定框就很大误差了。
1475242288757.jpg
3.难处理高速运动的目标
难处理低帧率中目标，这个和3类似，都是说相邻帧间目标位移过大。
1475242373962.jpg
目标下一帧出现位置不在你的padding内，你怎么也不可能移位找到。。。
5.虽然算法中对模型系数
进行线性插值，但是对于目标一旦被遮挡若干帧之后，可能模型就再也回不去了。。。因为模型已经完全被遮挡物污染掉了。
6.我觉的论文还有一个问题就是仅仅通过检测到的框中心和目标实际中心的距离来度量性能，这是有问题的。
比如我现在有一个人垂直我的镜头逐渐远去了，但他的中心一直在我镜头的中心处，那我就开始画个框就是镜头的视角范围，那这样我检测结果百分之百，可是有什么用呢。。。。当然论文方法是在很多不同数据集上检验的性能还是很有说服力的。我的意思就是对于单个数据集不能仅凭这个指标定方法的好坏。
