High-Speed Tracking withKernelized Correlation Filters（KCF）原理及代码详解

文章目录

• KCF原理
• 实验步骤
• 代码分析

---

关于KCF 在网上的文章已经很多了，这篇文章就从我自己的理解分析的角度 来详细分析其原理以及代码

KCF原理

首先，我们假设训练的样本集为\left( \boldsymbol{x}_{\boldsymbol{i}},\boldsymbol{y}_{\boldsymbol{i}} \right)，那么其线性回归函数\boldsymbol{f}\left( \boldsymbol{x}_{\boldsymbol{i}} \right) =\boldsymbol{\omega }^{\boldsymbol{T}}\boldsymbol{x}_{\boldsymbol{i}} ，这其中，\boldsymbol{\omega }是列向量表示的权重系数，可以通过最小二乘法来求解，\underset{\boldsymbol{\omega }}{\min}\sum_{\boldsymbol{i}}{\left( \boldsymbol{f}\left( \boldsymbol{x}_{\boldsymbol{i}} \right) -\boldsymbol{y}_{\boldsymbol{i}} \right) ^2+\boldsymbol{\lambda }}||\boldsymbol{\omega }||^2

目标是最小化我们的采样数据\boldsymbol{x}_{\boldsymbol{i}}的计算标签 \boldsymbol{f}\left( \boldsymbol{x}_{\boldsymbol{i}} \right)与下一帧真实目标位置的真实标签\boldsymbol{y}_{\boldsymbol{i}}（回归目标）的距离，我计算出来的标签越像真实标签，说明我找到的下一帧的位置就离他真实的位置就越近，写矩阵的形式就是：\underset{\boldsymbol{\omega }}{\min}||\boldsymbol{X}_{\boldsymbol{w}}-\boldsymbol{y}||^2+\boldsymbol{\lambda }||\boldsymbol{\omega }||^2

其中\boldsymbol{X}=\left[ \boldsymbol{x}_1,\boldsymbol{x}_2,\cdots ,\boldsymbol{x}_{\boldsymbol{n}} \right] ^{\boldsymbol{T}}的每一行表示一个向量， \boldsymbol{y}是列向量，每个元素对应一个样本的标签，于是令导数为0，可求得：\boldsymbol{\omega }=\left( \boldsymbol{X}^{\boldsymbol{T}}\boldsymbol{X}+\boldsymbol{\lambda I} \right) ^{-1}\boldsymbol{X}^{\boldsymbol{T}}\boldsymbol{y}

因为后面实在傅里叶域内计算，牵涉到复数矩阵，所以我们将结果都统一写成复数域中形式：\boldsymbol{\omega }=\left( \boldsymbol{X}^{\boldsymbol{H}}\boldsymbol{X}+\boldsymbol{\lambda I} \right) ^{-1}\boldsymbol{X}^{\boldsymbol{H}}\boldsymbol{y}

其中\boldsymbol{X}^{\boldsymbol{H}}表示复共轭转置矩阵。这里我们看到在求\boldsymbol{\omega }得最小值的时候有矩阵求逆的操作，这使得计算量比较大。然而根据之前说的\boldsymbol{X} 是一个循环矩阵，形式为：

将矩阵进行傅立叶变换后，循环矩阵有一个性质:
\boldsymbol{X}=\boldsymbol{F}\text{diag}\left( \boldsymbol{\hat{x}} \right) \boldsymbol{F}^{\boldsymbol{H}}

即一个循环矩阵可以用它的第一行的向量进行傅里叶变换之后表示， \boldsymbol{\hat{x}}表示对向量 \boldsymbol{x}进行了傅里叶变换，然后就可以发现一个循环矩阵可以转换成用一个向量来表示。将 \boldsymbol{X}=\boldsymbol{F}\text{diag}\left( \boldsymbol{\hat{x}} \right) \boldsymbol{F}^{\boldsymbol{H}}式带入\boldsymbol{\omega }=\left( \boldsymbol{X}^{\boldsymbol{H}}\boldsymbol{X}+\boldsymbol{\lambda I} \right) ^{-1}\boldsymbol{X}^{\boldsymbol{H}}\boldsymbol{y} 式化简：
\boldsymbol{X}^{\boldsymbol{H}}\boldsymbol{X}=\boldsymbol{F}\text{diag}\left( \boldsymbol{\hat{x}}^* \right) \text{diag}\left( \boldsymbol{\hat{x}} \right) \boldsymbol{F}^{\boldsymbol{H}}

\boldsymbol{X}^{\boldsymbol{H}}\boldsymbol{X}=\boldsymbol{F}\text{diag}\left( \boldsymbol{\hat{x}}^*\odot \boldsymbol{\hat{x}} \right) \boldsymbol{F}^{\boldsymbol{H}}

\boldsymbol{\hat{\omega}}=\text{diag}\left( \frac{\boldsymbol{\hat{x}}^*}{\boldsymbol{\hat{x}}^*\odot \boldsymbol{\hat{x}}+\boldsymbol{\lambda }} \right) \boldsymbol{\hat{y}}

\boldsymbol{\hat{\omega}}=\frac{\boldsymbol{\hat{x}}^*\odot \boldsymbol{\hat{y}}}{\boldsymbol{\hat{x}}^*\odot \boldsymbol{\hat{x}}+\boldsymbol{\lambda }}

其中\boldsymbol{\hat{\omega}} 的意思就是进行了傅里叶转换，这样就从一个矩阵的运算换到了向量的运算。减少了求逆的操作。
但是我们大部分情况下都是面对的是非线性问题，这里就需要高维求解和核函数的概念
在求解非线性回归中的\boldsymbol{\omega }时，如果将数据\boldsymbol{x}_{\boldsymbol{i}} 映射到高维空间，那么就可以将非线性回归问题转换为线性求解，同时需要找到一个非线性映射函数\boldsymbol{\varphi }\left( \boldsymbol{x}_{\boldsymbol{i}} \right)，这时的 \boldsymbol{\omega }可以表示为：
\boldsymbol{\omega }=\sum_{\boldsymbol{i}}{\boldsymbol{\alpha }_{\boldsymbol{i}}\boldsymbol{\varphi }\left( \boldsymbol{x}_{\boldsymbol{i}} \right)}
其中 \boldsymbol{\varphi }\left( \boldsymbol{x}_{\boldsymbol{i}} \right)表示将 \boldsymbol{x}映射到高位空间的函数。
那我们这里 的目标函数 就可以表示成：
\boldsymbol{f}\left( \boldsymbol{z} \right) =\boldsymbol{\omega }^{\boldsymbol{T}}\boldsymbol{z}=\sum_{\boldsymbol{i}=1}^{\boldsymbol{n}}{\boldsymbol{\alpha }_{\boldsymbol{i}}\boldsymbol{\kappa }\left( \boldsymbol{z},\boldsymbol{x}_{\boldsymbol{i}} \right)}

其中\boldsymbol{\kappa }表示核函数的定义运算为：
\boldsymbol{\varphi }^{\boldsymbol{T}}\left( \boldsymbol{x} \right) \boldsymbol{\varphi }\left( \boldsymbol{x}' \right) =\boldsymbol{\kappa }\left( \boldsymbol{x},\boldsymbol{x}' \right)

最后可以解得
\boldsymbol{\alpha }=\left( \boldsymbol{K}+\boldsymbol{\lambda I} \right) ^{-1}\boldsymbol{y}

其中， \boldsymbol{K}为核函数的矩阵表示， \boldsymbol{K}也是一个循环矩阵，可以表示成\boldsymbol{K}=\boldsymbol{C}\left( \boldsymbol{k}^{\boldsymbol{xx}} \right) ， \boldsymbol{k}^{\boldsymbol{xx}}是核函数矩阵 \boldsymbol{K}的第一行向量
通过傅里叶对角化的性质 \boldsymbol{K}^{\boldsymbol{z}}=\boldsymbol{C}\left( \boldsymbol{k}^{\boldsymbol{xz}} \right)进行简化，得到下式：
\boldsymbol{\hat{\alpha}}=\frac{\boldsymbol{\hat{y}}}{\boldsymbol{\hat{k}}^{\boldsymbol{xx}}+\boldsymbol{\lambda }}

这里\boldsymbol{\hat{k}}^{\boldsymbol{xx}} 代表 \boldsymbol{K}矩阵的第一行元素的傅里叶变换。这样式子
\boldsymbol{f}\left( \boldsymbol{z} \right) =\boldsymbol{\omega }^{\boldsymbol{T}}\boldsymbol{z}=\sum_{\boldsymbol{i}=1}^{\boldsymbol{n}}{\boldsymbol{\alpha }_{\boldsymbol{i}}\boldsymbol{\kappa }\left( \boldsymbol{z},\boldsymbol{x}_{\boldsymbol{i}} \right)}

由于\boldsymbol{K}^{\boldsymbol{z}}=\boldsymbol{C}\left( \boldsymbol{k}^{\boldsymbol{xz}} \right) ，其中\boldsymbol{C}\left( \boldsymbol{x} \right)表示由向量 \boldsymbol{x}循环移位得到的矩阵， \boldsymbol{K}^{\boldsymbol{z}}是所有训练样本和候补patch之间的核矩阵，可以表示成：
\boldsymbol{f}\left( \boldsymbol{z} \right) =\left( \boldsymbol{K}^{\boldsymbol{z}} \right) ^{\boldsymbol{T}}\boldsymbol{\alpha }

傅里叶变换后的形式为：

\boldsymbol{\hat{f}}\left( \boldsymbol{z} \right) =\boldsymbol{\hat{k}}^{\boldsymbol{xz}}\odot \boldsymbol{\hat{\alpha}}

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

\boldsymbol{k}^{\boldsymbol{xx}'}=\exp \left( -\frac{1}{\boldsymbol{\sigma }^2}\left( ||\boldsymbol{x}||^2+||\boldsymbol{x}'||^2-2\mathcal{F}^{-1}\left( \boldsymbol{\hat{x}}^*\odot \boldsymbol{\hat{x}}' \right) \right) \right)

实验步骤

代码分析

首先，读取视频帧，并判断是否读取成功

然后，用鼠标框选需要跟踪的目标

如果目标很大，就将其缩小，并且将我们自己画的框向外扩展1.5倍作为window_sz，我们在window_sz内进行寻找目标

再创建高斯形状的回归标签

这里最初的标签是这样的

将峰值移动到(0,0)的位置，主要作用是便于计算，因为峰值在(0,0)的位置的话，根据目标的坐标就可以很轻易的得出目标移动的方向和距离

再存储预先计算的余弦窗口

这里的余弦窗是这样的
，

再将相应的参数写入：

至此，以上只是前期准备工作，接下来进入真正的跟踪过程