Tracking-KCF Algorithm
注：本文涉及的算法的代码实践已上传至GitHub，恳求大佬们指点！^ _ ^
1. 目标检测跟踪与算法背景概述
目标跟踪任务在许多的计算机视觉系统中都是极为关键的一个组成部分。对于任意给定的一个初始图像的Patch（Filter滑过的区域），目标跟踪任务的目的在于训练一个分类器来将待跟踪的目标与它所处的环境区分开，为了能够在后续帧中能继续检测到这个目标，分类去需要能够在很多位置上都能进行详尽的评估，同时在滑动的过程中都会提供一个新的图像Patch来帮助提升模型的性能。
在上述任务中，我们将感兴趣的对象——即待追踪的目标称作正样本（positive samples），将目标所在的环境或者背景称作负样本。一幅图像中包含的负样本数量几乎是无限的，在达到合并尽可能多的样本和保持较低的计算量之间的平衡上，前人作出了很多尝试。KCF算法中，引入了轮转矩阵（circulant matrices）这一工具来合并大量的样本，实现了一个基于“核岭回归”的跟踪器（tracer），该跟踪器可以认为是一个核化版的线性相关滤波器（Linear Correlation Filter ）。
Correlation Filter（CF）源于信号处理领域，其用于tracking方面的想法是：相关是衡量两个信号相似值的度量，如果两个信号越相似，那么其相关值就越高。在tracking的应用里，设计一个滤波模板，利用该模板与目标候选区域做相关运算，最大输出响应的位置即为当前帧的目标位置。
用数学语言来表述，表示一幅图像，
表示相应的滤波模板，
表示模板与相关候选区域进行相关运算后的相应输出，则有如下关系：
，为减小计算量，可将
分别转换到其傅里叶空间后计算点积，即
。相关滤波的任务则是寻找最优的滤波模板
。
目下以相关滤波类的方法和深度学习方法为代表的判别类模型方法效果普遍好于生成模型，其显著特点是分类器的训练过程中运用到了前景与背景信息，分类器的任务专注于区分前景与背景。Kernelized Correlation Filter(KCF)是相关滤波方法中的典型算法，该方法的一般流程是：在跟踪的过程中训练一个目标检测器，使用目标检测器去检测下一帧预测位置是否是目标，然后再使用新检测结果去更新训练集进而更新目标检测器。
2. HOG特征
KCF算法中使用了图像的HOG特征替代了传统跟踪器所用的灰度特征。
HOG特征全称为Histogram of Oriented Gradients，即方向梯度直方图。作为一种图像的特征描述子（图像的一种表示，通过提取有用的信息并扔掉多余的信息来简化图像），HOG特征将一张大小为的图像转化为一个长度为
的特征向量，例如输入图像大小为
，HOG特征的输出为长度
的向量。HOG特征的计算过程如下：
(1)图像预处理
最早提出的HOG特征通过在一张的图像上计算得到，预处理的操作要求图片保持1:2的横纵比，原文中提及的
矫正已知其增益效果较小，不再考虑。
(2)计算梯度图
首先计算图像的水平方向梯度和竖直方向的梯度
，以如下公式来计算梯度的强度值
和梯度方向
：
同时梯度方向有如下的性质：。
(3)计算梯度直方图
这一步中，首先将图像分割成多个的cell，在这些cell中计算梯度直方图。(2)中计算的每个像素点的位置处包含了2个值：
，一个cell就保存了128个值，单个像素的梯度信息往往包含了噪声，采用
的图片块表示后能够是的直方图对噪声不敏感。
由(2)的性质，将0-180度分成9个区间：0,20,40,…160，之后统计每个像素点所在的区间——将这个区间命名为bin，采取的原则是对每个像素点处的值，按
的比例将
分配给相邻的bin，如下图所示。
文章出处登录后可见！
