KCF追踪算法

Magicmanoooo 3月 09, 2019

目前大多数追踪器的核心组件是一个能有效区分目标和背景的分类器。而KCF算法则巧妙地通过魂环偏移进行都贱分类器的训练样本，从而使得数据矩阵变为了一个循环矩阵。然后基于循环矩阵的特性把问题的求解变换到傅里叶变换域，从而避免了矩阵求逆的过程。

1. `KCF`简介

KCF（Kernel Correlation Filter，核相关滤波算法），其中，Correlation Filter（以下简称CF）源于信号处理领域，后被运用于图像分类等方面。而Correlation Filter应用于tracking方面最朴素的想法就是：相关（Correlation）是衡量两个信号相似值的度量，如果两个信号越相似，那么其相关值就越高，而在tracking的应用里，就是需要设计一个滤波模板，使得当它作用在跟踪目标上时，得到的响应最大，最大响应值的位置就是目标的位置。

Correlation包含Cross-correlation和Auto-correlation，在这里一般指的就是Cross-correlation。Cross-correlation的定义（假设有和两个函数（信号））：

其中，表示的复共轭。Correlation的直观解释就是：衡量两个函数在某个时刻τ的相似程度。

如下图所示，假设和的形状一样，但相差了若干个时刻，那么
取得最大值的时候一定是和对齐的时候。但因为两者有时间差，想要取得最大值，就需要把其中一个函数在时间轴上进行平移，所以就代表把平移τ个时刻。

2. `MOSSE`简介

MOSSE（Minimum Output Sum of Squared Error filter，误差最小平方和滤波器），是CF中的开山鼻祖。按照之前的思路，需要寻找一个filter模板，使得其在目标上的响应最大。则有：

其中，表示响应输出，表示滤波模板，表示输入图像。可以为任意形状的响应输出。在最上面的的示意图里，假设它为Gaussian。那么只需要求出就可以了。这样做看起来很简单，但为何CF类方法的速度如此之快呢？就是因为：在求解等一系列操作中，都利用了快速傅里叶变换FFT。

由卷积定理的Correlation版本可知，函数互相关的傅里叶变换等于函数傅里叶变换的乘积，即：

那么，假设所含的像素个数为n，而已知FFT的时间开销为O(nlogn)，因此上式的计算开销也为O(nlogn)，远比其他跟踪算法要快。

剩下的就是如何计算。为了方便起见，令，就有：

但是在实际应用中，因为目标的外观变换等因素的影响，需要同时考虑目标的m个图像作为参考，以提高模型的鲁棒性，于是就有如下的目标函数：

根据卷积定理，在频率域的操作都是元素级别的，因此可以分别求解中的每一个元素，那么上式变为：

然后，对上式求导并使其为0：

按以上方式处理所有中的所有元素，得到：

于是，便可以开始追踪了。在追踪的过程中，只需要把以上模板与当前帧的图像作相关操作，然后将得到的响应结果中的最大的那点所对应的坐标，作为目标在当前帧的位置就可以了（相当于在二维空间上平移模板）。然后，模板的更新方式可以按照如下的方式进行：

其中，表示在第t帧求得的滤波模板，为经验常数

3. `KCF`详解

3.1 Linear regression（线性回归）

主要使用Ridge Regression（岭回归函数），使得模型能够像SVM那些有良好的表现。训练的目的就是找到这么一个函数，使得误差最小（此处使用平方误差，squared error）。使用的误差函数为：

其中：λ是一个正则化参数，用于防止过拟合（overfitting）。

其中，矩阵每行都具有一个样本（sample），并且的每个元素都是一个回归目标（regression target）
。是一个单位矩阵（identity matrix）。

由于后面需要在傅里叶域内（Fourier domain）进行计算，牵涉到复数矩阵，所以将结果都统一写成复数域的形式：

其中，，表示复共轭矩阵。

3.2 Cyclic shifts（循环矩阵）

先使用单通道、一维的数据（
的vector）进行举例，可以直接扩展到二维的情况。可以通过循环移位算子（cyclic shift operator）对该vector进行平移，循环移位算子是一个置换矩阵（permutation
matrix）：

对于二维图像，可以通过x轴和y轴分别循环移动实现不同位置的移动：

所以，由一个向量可以通过不断地乘上排列矩阵得到n个循环移位向量。将这n个向量依序排列到一个矩阵中，就形成了由生成的循环矩阵，表示成：

一维向量得到的循环矩阵：

即，一维的情况下就是矩阵相乘的问题，即左乘一个单位矩阵和右乘一个单位矩阵。左乘是行变换，右乘列变化。目的就是得到更多的样本，每乘一次都是一个新的样本，这样就可以多出来n*n个样本了，这就是循环矩阵在这里最大的用处，制造样本的数量，以图像的形式展示就是这样的，一个样本经过循环矩阵之后就可以产生这么多的样本。

二维向量得到的循环矩阵：

3.3 循环矩阵在傅氏空间内的对角化

所有的循环矩阵都能够在傅氏空间中使用离散傅里叶矩阵进行对角化：

其中，
对应于生成的向量（就是的第一行矩阵）的傅里叶变换后的值，，为离散傅里叶矩阵，为一个常量：

傅式对角化简化的岭回归（Ridge Regression）

将带入之前的Fourier domain的Ridge Regression的公式，可以得到：

【注】：分号表示点除运算，即对应元素相除。

因为，。对上式两边同时进行Fourier transform，可以得到：

于是，（亦或是）

这样，就可以使用向量的点积运算取代矩阵运算，特别是求逆运算，大大提高了计算速度。

核空间的Ridge Regression

现在希望找到一个非线性映射函数列向量，使映射后的样本在新空间中线性可分，那么在新空间中就可以使用Ridge Regression来寻找一个分类器。所以，这时候得到的权重系数为：

是行向量空间中的一个向量，所以可以令

则，上式将变为：

该问题称为的对偶问题。

令关于列向量的导数为0，则有：

所以，可以解得：

【注】：在计算时，可以将当做一个整体，计算一个向量的模的平方，相当于让其自己与自己的转置相乘。

对于核方法，一般不知道非线性映射函数的具体形式，而只是刻画在核空间的核矩阵。那么，令表示核空间的核矩阵，由核函数得到。那么，，于是，

论文提出的一个创新点就是：使循环矩阵的傅里叶对角化简化计算。所以，如果希望计算时，可以将矩阵的求逆运算变为元素运算，就应该希望先将对角化。所以希望找到一个核函数，使对应的核矩阵是一个循环矩阵。

Theorem 1. Given circulant data , the corresponding kernel matrix is circulant if the kernel function satisfies
, for any permutation matrix .
即核矩阵是循环矩阵应该满足两个条件：第一个样本和第二个样本都是由生成样本循环移位产生的（可以不是由同一个样本生成）；满足，其中是置换矩阵。