【强基固本】目标跟踪系列--KCF算法

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—单字卓

地址：https://zhuanlan.zhihu.com/p/67162876

个人思考：其实KCF算法仅仅是在MOSSE算法上引入了核技巧和多通道特征的处理，他的核心思想是和MOSSE一样的。而且KCF算法是通过循环矩阵生成多样本然后利用每一个样本进行回归训练，仔细思考其实是和MOSSE算法直接用滤波器与基样本求相关是一样的过程。只不过是一种处理的两种层面的理解，大道至简，原理是统一的：时域的卷积可以用频域的点乘表示

PS：本文原创（有一部分懒得打了直接从我的论文里截图了），如要引用请注明出处

01

KCF核相关滤波算法

有了MOSSE算法之后，人们开始对这个简单但是高效的算法进行改进，各种相关滤波算法随之产生，而这之后最具影响力的应该是KCF算法。KCF十分简单，它的核心思想就是扩充了负样本的数量以增强跟踪器的性能，而其扩充负样本的方法就是采用了循环矩阵的构造方法，如下图所示。

通过循环矩阵方法生成的训练样本，其中只有base sample为正样本

02

循环矩阵与密集采样

循环矩阵是一种特殊的矩阵，它的一维形式就是由一个n维向量每次向右循环移动一个元素，直到生成一个n×n的矩阵，具体效果如下图所示。

由基准向量生成的循环矩阵

在KCF的算法中，训练样本的生成都是基于循环矩阵形式来构建的，其中基样本为正样本，其他都是虚构出的负样本，这样的样本集具有很好的特性，可以很方便的利用快速傅里叶变换和傅里叶对角化的性质来进行计算，而不需要得知负样本的具体形式，算法将有关负样本的计算都转换到了频域进行求解。这样，采用了循环矩阵的性质对输入图像的搜索区域进行密集采样之后，使得进行跟踪器训练时缺少样本的问题迎刃而解。因此，整个KCF算法对跟踪器进行训练的目的就是利用生成的这些样本，生成一个滤波器，使得其作用于这些样本时会生成我们期望的分布形式，具体效果如下图所示：

训练样本经过滤波器滤波后得到的期望分布图

对于任意的基样本x所生成的循环矩阵都能够在傅氏空间内使用离散傅里叶矩阵进行对角化处理，如下式：

其中，x'是x的离散傅里叶变换（此符号对以下各公式均适用），即：

03

岭回归与核技巧

（1）岭回归

与MOSSE算法不同，KCF算法采用如下式的岭回归的方法来训练跟踪器：

（2）核技巧

对于现实中大部分非线性的模型，我们没办法找到它们的确定形式，但是可以通过将低维数据映射到高维，以此达到将非线性计算转换成线性计算的目的，同时这样的操作还会使的跟踪的准确性得到很大的提高。

04

快速检测和跟踪器更新

（1）快速检测过程

在检测过程中，算法使用已经训练好的跟踪器对padding窗口区域进行滤波计算，得到输出的分布图，将其中最大响应位置作为预测目标的中心位置。根据上述定义的核相关向量的概念，输入样本和模板样本在高维空间的核矩阵形式为：

那么检测过程中的输出响应方程为下式：

（2）跟踪器模板更新过程

由之前的公式推导可以知道，我们在更新跟踪器的过程中只需要对  和训练样本集x进行更新即可。因此，在算法执行完检测部分之后，得到了新的目标预测位置，并得到了新的基样本，以此生成循环矩阵得到新的样本集  ，然后训练得到新的   ，最后利用上一帧的模型参数，使用线性插值的方法设定好更新步长  后对跟踪器进行更新，具体更新公式如下式所示：

05

算法图解

整个KCF算法的具体流程如下图3-5所示：

KCF算法具体流程

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！