目标跟踪学习过程（3）：KCF算法

目标跟踪学习过程（3）：KCF算法

论文：https://xueshu.baidu.com/usercenter/paper/show?paperid=13edd1d6ca88e738f7a70

3b3f13c16ce&site=xueshu_se

代码：https://github.com/scott89/KCF

继csk算法之后，今天我给大家讲解CSK算法的进阶版本KCF算法。KCF全称为Kernel Correlation Filter 核相关滤波算法。是在2014年由Joao F. Henriques, Rui Caseiro, Pedro Martins, and Jorge Batista提出来的。KCF算法我想知道的同学可能很多，这是在相关滤波领域比较火的算法，并且在工程领域应用较多。今天我将从算法由来、创新点、计算过程、实验验证、代码讲解这五个角度来进行讲解。

一、算法由来

当时大多数跟踪算法都是基于判别式模型，其任务是区分跟踪目标和背景环境。为了应对自然的图像变化，这个分类器通常使用平移和缩放的样本块进行训练，但是这样的样本集充满了冗余——任何重叠的像素都被限制为相同。

二、创新点

作者提出一种基于核岭回归的跟踪器，该跟踪器不受“核化惩罚”的影响，可以减少复杂度，甚至比非结构化线性回归的复杂度更低。把以前只能用单通道的灰度特征改进为现在可以使用多通道的HOG特征或者其他特征，而且在现有算法中是表现比较好的，使用HOG替换掉了灰度特征，并使用核函数，对偶相关滤波去计算。

1） 它首次证明了岭回归与循环移位样本和经典相关滤波器之间的联系。这使得使用快速傅立叶变换而不是矩阵代数进行快速学习成为可能。还提出了第一个核相关滤波器，但仅限于单个通道。此外，它提出了封闭形式的解决方案来计算所有循环移位的内核。

2） 扩展了原始工作以处理多个通道，还将原始实验从12个视频扩展到50个视频，并添加了基于定向梯度直方图(HOG)特征而不是原始像素的核化相关滤波器 (KCF)跟踪器的新变体。通过线性内核，我们还提出了一种计算复杂度非常低的线性多通道滤波器，几乎可以匹配非线性内核的性能。我们将其命名为双相关滤波器 (DCF)，并展示它与一组最近的、更昂贵的多通道滤波器 [28] 的关系。通过实验，我们证明KCF已经比线性滤波器表现更好，而无需任何特征提取。借助HOG功能，线性DCF和非线性KCF的性能都大大优于Struck或TLD等顶级跟踪器，同时以每秒数百帧的速度轻松运行。

三、计算过程

KCF采用岭回归的方法，训练的目标是找到一个函数f(z) = wTz最小化样本 xi及其回归目标 yi的平方误差。公式表示为：

（1）

式中，λ为控制过拟合的正则化参数。因此，算法的损失函数可以表示为：

（2）

当损失函数的值L为0时，求解可得：

（3）

根据循环矩阵乘法性质：根据循环矩阵能够被离散傅里叶矩阵对角化，使得矩阵求逆转换为特征值求逆的性质；能够将w的求解转换到频域进行运算，应用离散傅里叶变换(DFT)提高运算速度，然后再将解逆变换回空域从而得到响应最大的解。

循环矩阵X可以被DFT矩阵F对角化：

（4）

其中x^是x的傅里叶变换，F是离散傅里叶矩阵。代入公式（3）中，可得：

（5）

利用反对角化性质，可得：

（6）

再利用循环矩阵卷积性质: F(C(x)y)=F∗(x)⨀F(y)得到：

（7）

引入核来将问题扩展到非线性空间，回归系数w用x和对偶空间α的线性组合表示如下：

（8）

回归问题就转为：

（9）

根据文献8，我们可以得到非线性问题的解：

（10）

根据之前w的推导，可以得到：

（11）

当输入图像z时，构造x和z的核相关矩阵，进行回归检测：

（12）

四、实验验证

为了更好的让大家更好的了解KCF算法，我在OTB数据库中挑选了部分视频序列，分别就遮挡、关照变化、尺度变化、快速运动几个方面对CSK算法进行解析评价。

1、遮挡

遮挡问题，即是跟踪目标在跟踪过程中被部分遮挡或者全部遮挡的情况。我在OTB数据库中选取了soccer、Coke两个视频进行说明。

从soccer、Coke两个序列中挑选出存在遮挡的帧进行说明，可以发现当跟踪目标被部分遮挡时，KCF算法能够准确的跟踪目标，但是当跟踪目标被全部遮挡时，跟踪目标丢失，说明KCF算法无法处理目标被全部遮挡的情况。由于全部遮挡和部分遮挡情况不一样，当跟踪目标被部分遮挡时，图像中还存在目标，可以提取目标没被遮挡的部分的特征进行识别，当目标被全部遮挡时，图像中不存在目标。也就没有可以识别的特征，这需要专门针对这种情况设置跟踪机制，而KCF显然没有这种机制。

2 、光照变化

光照变化，即是在跟踪过程中视频中的光照存在剧烈变化，并对跟踪目标产生了影响。我在OTB数据库中选取了David、Trellis两个视频进行说明。

从David、Trellis这两个视频序列中可以看出，KCF算法对于光照变化还是有一定的适应能力的，当视频中光照出现变化时，CSK算法能勉强跟上目标，但提升空间较大。

3、尺度变化

尺度变化，即是在跟踪过程中目标的大小发生快速变化导致的跟踪难点。我在OTB数据库中选取了Crossing、Toy两个视频进行说明。

从Crossing、Toy这两个视频序列中可以看出，KCF算法对于尺度变化适应性不行，当目标的大小发生变化时，跟踪框不能及时适应目标尺度的变化，在Crossing中，目标缓慢变化尺度，KCF算法还能跟踪，但在Toy中，跟踪目标尺度变化比较快，KCF算法明显不能应对这种情况。

4、快速运动

快速运动，即是在跟踪过程中两个相邻帧中目标的位置变化较大，可能超出搜索框的情况。我在OTB数据库中选取了Biker、Soccer两个视频进行说明。

从Biker、Soccer这两个视频序列中可以看出，在Biker序列中，跟踪目标移动较快，可能在某一帧出了搜索框，导致跟踪失败，在Soccer序列中，跟踪目标也在快速运动，但是没出搜索框，说明KCF算法能够处理一定的快速运动情况，但是能力一般。

五、代码讲解

现在我给大家就着算法公式和代码进行一一对应，当然肯定不全，详细的需要大家自己好好研究。

1、回归目标

在KCF算法中，回归目标采用的时高斯响应值，对应的代码为：

y = exp(-0.5 / output_sigma^2 * (rs.^2 + cs.^2));

2、计算核

在KCF算法的代码中，

k =dense_gauss_kernel (sigma,x,z);

这个代码是用于计算核k，在函数dense_gauss_kernel中，

k = exp(-1/sigma^2*max(0,(xx+yy-2*xy)/numel(x)));

这个代码即是对应公式

3 计算alpha

在KCF算法的代码中，

new_alphaf = yf./(fft2(k)+lambda);

这个代码对应的公式为：

对于KCF算法，由于篇幅有限，我就暂时给大家分享这些。KCF算法为目标跟踪领域比较经典的算法，实际工程应用比较多，同时也是大部分相关滤波算法的基础算法，希望对大家有用，接下来我将给大家分享我学习KCF的进阶算法KCFDP的过程。