融合KCF和HOG的改进TLD目标跟踪算法

储开斌， 朱 磊， 张 继

(1.常州大学 微电子与控制工程学院， 江苏 常州 213164；

2.常州大学 阿里云大数据学院， 江苏 常州 213164)

目标跟踪技术是计算机视觉领域的研究热点，其在无人驾驶、军事侦察等领域具有重要作用。但由于在跟踪过程中目标可能出现遮挡、尺度变化、光照强度变化等问题，从而导致跟踪失败，使其应用受到一定的限制，这些弊端引发了众多学者开展相关研究并取得一定的成果。

2002年，COMANICIU等[1]将均值漂移(MeanShift)算法运用到了目标跟踪领域，该算法快速准确，但在背景复杂场景下跟踪效果差。2010年，BOLME等[2]提出了MOSSE(Minimum Output Sum of Squared Error)滤波算法，该算法通过傅里叶变换将滤波器的运算转换到频域，加快了运算速度，但MOSSE滤波算法采用的特征为简单的灰度像素，从而造成跟踪结果不够准确。2014年，HENRIQUES等[3]提出了KCF算法，通过核回归运算大大降低了运算量，具有较快的跟踪速度，但当目标出现尺度变化时，算法鲁棒性较差，一旦目标丢失，很难继续跟踪到目标，不具备长时间跟踪能力。近年来，随着深度学习的发展，许多学者提出了基于深度学习的目标跟踪算法，这些算法虽然结果较为准确，但需要大量训练样本和长时间的训练，在实际应用时存在一定的困难[4-5]。

TLD算法是KALAL等[6]在2011年提出的，该算法可以长时间准确地跟踪目标，在目标发生形变、部分遮挡等问题时也能有良好的鲁棒性。但是这种经典TLD算法跟踪速度慢，当目标从遮挡中恢复时，重新检测到目标所需时间较长，不具备实时跟踪性。该算法对于光照强度变化也很敏感，一旦光照强度发生变化，往往容易导致跟踪失败。目前，针对TLD算法的改进有很多。2019年，郭巳秋等[7]用颜色特征粒子群跟踪算法更新了TLD算法，提高了算法的鲁棒性，但跟踪速度较慢。同年，胡欣等[8]将ViBe模型加入TLD算法，提高了算法的运行速度，但该算法稳定性较差。

针对TLD算法存在的跟踪速度慢、对光照强度敏感的问题，本文在TLD算法的跟踪模块中，用KCF算法替代原有的中值流跟踪算法，提高了TLD算法的跟踪速度；
通过在检测模块中加入HOG[9]特征，对图像局部进行归一化，从而使该算法不受光照强度影响，解决了光照变化鲁棒性差的问题。

TLD算法是KALAL等在2012年提出的一种单目标长时间跟踪算法，主要由跟踪模块[10]、检测模块[11]、学习模块[12]3个部分组成。TLD算法将视频帧图像送入跟踪、检测、学习3个模块，将跟踪和检测的结果输入学习模块，学习模块通过学习判断跟踪和检测模块是否出现错误，若出现错误则更新检测器和跟踪器，否则就将跟踪和检测模块的结果进行综合并输出，得到目标位置。TLD算法的框架如图1所示。

图1 TLD算法框架Fig.1 TLD algorithm framework

检测模块根据跟踪目标模型判断下一帧中是否存在目标，若存在则定位出可能出现的位置。TLD算法检测模块由方差检测器、随机森林检测器[13]和最近邻分类器3部分级联组成[14]。当检测开始时，一幅视频帧会被分成许多大小不一的图像块，这些图像块首先经过方差检测器计算方差，方差大于阈值的图像块进入随机森林检测器，在随机森林检测器中对图像块进行特征提取，计算后验概率，后验概率大于阈值的图像块进入最近邻分类器，在最近邻分类器计算图像块与样本的相关相似度，大于阈值的图像块就是最终的目标。

学习模块采用半监督学习方法中的P-N学习，通过P和N两个专家系统对正负样本进行约束，消除检测器误将正样本认为是负样本、负样本认为是正样本的情况，使得分类所得到的结果更加准确。最后，跟踪和检测两个模块进行综合，将两个模块输出的目标区域与检测器中的样本进行相似度对比，相似度最大的区域即为最终的跟踪目标。

但TLD算法的跟踪模块采用的是中值流跟踪算法，该算法以光流法为基础，加入了前向后向跟踪机制和正则化系数，这样导致算法的跟踪模块计算量巨大，降低了跟踪速度。另外，光流法对于跟踪目标的要求也比较高，若跟踪目标特征较少或者目标与背景接近时，跟踪结果也会产生偏差。

同时，由于TLD算法检测模块中的随机森林检测器采用的是灰度特征，该特征由对比图像中的像素点对获得，对光照变化敏感，一旦光照发生变化，随机森林检测器就会出现误判，甚至导致跟踪失败。

针对TLD算法存在的不足，在TLD算法的基础上，对跟踪模块及检测模块进行改进。在跟踪模块中用KCF算法代替中值流跟踪算法，提高了算法的跟踪速度。在检测模块的随机森林检测器中，将灰度特征替换为图像的HOG特征，提高了算法对光照强度变化的鲁棒性。

改进TLD目标跟踪算法流程如图2所示。该算法首先读取视频的第一帧图像，并从第一帧图像中选择跟踪目标，用不同尺度的扫描窗将第一帧图像分成大小不一的多个图像块。然后对每个图像块进行HOG特征提取，将所得特征用于TLD的各个模块，完成初始化。接着将读取的下一帧图像送入检测模块和跟踪模块，跟踪模块采用KCF跟踪算法对图像中的目标进行跟踪；
检测模块用不同尺度的扫描窗对图像进行分块，再将图像块送入方差检测器，当图像块经过随机森林检测器时会进行HOG特征提取，用HOG特征代替原算法的灰度特征，最后再进入最近邻分类器进行检测。最后再将跟踪和检测模块所得结果输入P-N学习模块，P-N学习纠正跟踪器和检测器出现的误判，得到该帧图像中目标位置，完成本帧图像的跟踪。

图2 改进的TLD目标跟踪算法流程图Fig.2 Improved TLD target tracking algorithmflowchart

2.1 基于KCF的TLD跟踪模块

本文的改进算法将KCF算法作为TLD算法的跟踪模块，提高了TLD算法的跟踪速度。

KCF算法是一种相关滤波算法，该算法的核心是求得一个响应值最大的目标模板。原始问题可以表示为

(1)

式中：xi为训练样本；
yi为xi经过高斯函数后的结果；
f(xi)为xi与目标模板ω在频域内的点积；
λ为正则项系数，防止目标模板过拟合。

将样本xi的整体用X来表示，yi的整体用y来表示，则式(1)可以写成

(2)

对ω求偏导可得

ω=(XTX+λI)-1XTy

(3)

式中：X为循环矩阵；
I为单位阵。

通过离散傅里叶变换进行对角化，计算式为

(4)

根据循环矩阵的性质可得

(5)

将式(5)进行离散傅里叶逆变换就得到了目标模板。

由于KCF目标模板计算跟踪目标是通过循环矩阵进行的，循环矩阵可以将时域计算转换到频域，将卷积转换为乘积，大大降低了计算量，提高了跟踪速度。

2.2 基于HOG的TLD检测模块

在TLD算法中随机森林检测器共有3棵决策树，每棵决策树对图像块的检测是通过对比13对不同位置的像素点对的值来进行的，对比结果用0和1表示，得到一串二进制的结果作为图像块的特征值，所得特征值就是灰度特征。根据灰度特征和训练集求得图像块为目标的概率，将3棵决策树所求得的概率取平均，得到该图像块为目标的最终概率。最终概率大于阈值的图像块被保留，进入最近邻检测器。在上述过程中，决策树对比图像块中像素点是假设光照强度恒定不变的，当光照强度发生变化时所得特征值误差较大，影响检测结果，甚至会导致跟踪失败。针对该不足，本文在随机森林检测器用目标的HOG特征替换灰度特征来解决光照强度影响检测结果的问题。HOG通过计算梯度来描述物体的轮廓和形状信息，并且会对图像进行归一化，归一化后的检测器对光照变化不敏感，从而解决了光照强度变化影响检测结果的问题。

在HOG运行过程中，1帧图像会被分成若干个block，而1个block会被分成若干个cell，cell由像素点组成，如图3所示。

图3 图像组成示意图Fig.3 Schematic diagram of image composition

像素梯度的计算是HOG特征的核心，其大小G(x,y)和方向α用公式表示为：

(6)

(7)

得到像素点梯度后建立block方向梯度直方图，流程如图4所示。将1个block进行均匀分割，得到4个cell，对每个cell建立直方图，直方图的横坐标为梯度方向，范围从0°～180°，每个直方条的间隔为20°，每1个直方条称为1个bin；
纵坐标是权值，权值是梯度的大小。将像素点的梯度方向对应到bin中，像素点的梯度大小累加到该组bin中对应为权值，这样就得到该cell的方向梯度直方图，最后将4个cell的直方图进行组合，就得到了该block的方向梯度直方图。

图4 基于block的方向梯度直方图Fig.4 Histogram based on the directional gradient of the block

通过对比不同bin中像素的梯度值，得到block的特征值，对比公式见式(8)，为

f(x;u,θ)=F(H(x;u,b)>H(x;u,b"))

(8)

式中：F(a)为布尔值，a为真，F(a)=1，反之，F(a)=0；
H(x;u,b)为第b个bin所对应的梯度值，u为block的中心点。

(a) 整体精确度图

(a) 光照变化下的精确度图

随机森林检测器采用的特征值是13位的二进制串，将式(8)运行13次，得到13位的二进制串，该二进制串就是block的特征值，见式(9)，为

f(x;u,θ)=[f(x;u,θ1),…,f(x;u,θ13)]

(9)

通过对block的梯度归一化能够减少光照强度对检测器的影响，公式为

(10)

式中ε为一个很小的常数，避免分母为0。

由于HOG特征提取的是图像的梯度信息而非灰度信息，对光照变化不敏感，将其加入随机森林检测器，代替灰度特征，可以有效解决光照变化造成随机森林检测器检测失败的问题。

3.1 实验方法

为验证该算法的效果，将TLD算法、KCF算法和本文算法(标记为Ours)进行对比。实验数据集选用WU等[15]的OTB2013中的50组视频序列进行测试，视频序列共包含光照变化、尺度变化、遮挡、形变、运动模糊、旋转、离开视野、相似的背景、低分辨率等9种属性。采用WU提出的一次通过评估(One-Pass Evaluation, OPE)来评估算法精确度和成功率，其中精确度表示算法预测的中心位置误差小于给定阈值帧数的百分比，阈值设置为20，精确度图按照算法结果的百分比由大到小排序。成功率表示跟踪区域和人工标注区域的重叠率大于阈值的帧数百分比，成功率图按照算法的曲线下面积由大到小排序。本实验在Windows10，Visual Studio 2013，Matlab 2019a，Opencv2.4.11环境下运行，测试硬件环境为Intel Core i5 2.6GHz。实验数据包含OTB2013所有视频序列。

3.2 定量分析

将本文算法、TLD算法和KCF算法加入OTB2013测试平台进行对比，结果如图5所示。由图5可以看出：本文算法的精度变化曲线和成功率曲线都处于第1名的位置，分别达到了78.7%和74.1%，分别高出了TLD算法19.2%和23.5%。

在光照强度发生变化时3种算法在OTB2013测试平台下的精度图和成功率图如图6所示。在光照变化的情况下，本文算法的精度和成功率都要高于TLD算法，说明本文算法在光照变化下的鲁棒性要好于TLD算法；
本文算法的精度曲线与KCF算法几乎相同但成功率高于KCF算法。

3.3 定性分析

为了更直观地对算法进行分析，本文选取了3个最具代表性的视频序列进行分析，这3个视频序列均包含光照强度变化，另外还有旋转、背景相似等挑战，见表1。

表1 所选视频序列目标包含的挑战

图7～图9为3种方法在3个视频序列中的跟踪结果的对比。图7中，在49帧，当光照变强，TLD算法未能跟踪到目标；
在第109帧，目标出现旋转，本文算法和KCF算法均跟踪到了目标，TLD算法跟踪失败；
在第277帧，视频序列快要结束，目标从遮挡中出现，此时KCF算法未能及时更新目标尺度，跟踪失败，本文算法和TLD算法均跟踪到目标。图8中，在210帧和258帧中，当目标光照强度出现变化，TLD算法出现了目标框漂移现象，KCF算法目标框尺度过大，本文改进算法能够准确跟踪到目标；
在620帧，视频序列即将运行结束时，TLD算法通过学习模块重新跟踪到了目标，KCF算法的目标框依旧存在尺度过大的情况。图9中，光照强度由低到高的情况下，TLD算法完全失效，本文算法和KCF算法均能跟踪到目标；
在408帧，目标出现快速移动时，本文算法和KCF算法均跟踪到目标，但KCF算法目标框出现轻微尺度变化。

图7 Car4序列跟踪结果Fig.7 Car4 sequence tracking results

图8 Coke序列跟踪结果Fig.8 Coke sequence tracking results

图9 Trellis序列跟踪结果Fig.9 Trellis sequence tracking results

本文还对3种算法的运行速度进行对比验证，表2是本文算法、KCF算法和TLD算法在3个视频序列中的平均帧率。KCF算法的帧率最高，跟踪速度最快，但不具备长时间跟踪的能力。本文算法结合了KCF算法的优势，平均帧率相较于TLD算法提升了2倍，可满足实时性的需求。由于本文算法是在TLD算法基础上进行改进，虽然将跟踪模块替换成KCF算法，但检测和学习模块也较为耗时，所以跟踪速度相较于KCF算法还有一定差距。

表2 平均帧率对比

TLD算法是一种优异的目标跟踪算法，它能对目标进行学习，实现目标的长时间跟踪。本文算法对TLD算法进行改进，用KCF算法替换跟踪模块的中值流跟踪法，提升了算法的速度；
对检测模块中的随机森林检测器进行改进，在随机森林检测器中加入了目标HOG特征，弥补了TLD算法在光照强度发生变化时跟踪结果差的不足。实验表明，本文算法的鲁棒性和跟踪速度均优于TLD算法。