自适应多策略融合快速KCF跟踪算法

王 玲 马胜楠 王 鹏

(长春理工大学计算机科学技术学院 吉林 长春 130022)

0 引 言

目标跟踪是计算机视觉中重要的研究领域,在人机交互[1]、监控、增强现实、无人驾驶等场景有着广泛的应用。近几年,深度学习与相关滤波这两类算法推动了目标跟踪领域的发展。深度学习类算法虽然跟踪精度高但实时性较差;相关滤波类算法跟踪精度和实时性都具有良好的性能,逐渐成为广大学者的研究对象。

Bolme等[2]首次将相关滤波理论应用到目标跟踪算法中,提出最小平方误差和(Minimum Output Sum of Squared Error filter,MOSSE)算法。Henriques等[3]在MOSSE算法的基础上引入循环矩阵和核函数,提出CSK(Circulant Structure of tracking-by-detection with Kernels)算法,之后又在CSK的基础上扩展了多通道HOG(Histogram of Oriented Gradient)特征,提出了核相关滤波(Kernelized Correlation Filters,KCF)算法[4],有效地提升了跟踪速度和精度。Danelljan等[5]在MOSSE算法基础上通过添加尺度滤波器解决目标尺度变化问题,提出多尺度空间滤波(Discriminative Scale Space Tracking,DSST)算法,又在CSK算法基础上通过增加颜色特征对目标进行跟踪,提出了CN(Color Name)算法[6]。Li等[7]融合HOG和CN特征并引入七尺度的尺度因子解决尺度不变的问题,提出SAMF(Scale Adaptive Multiple Feature)算法,但实时性较差。Bertinetto等[8]融合HOG和CN特征,添加尺度滤波器,提出Staple——基于互补学习的目标跟踪(Complementary Learners for Real-Time Tracking)算法,提高了算法在目标形变下的鲁棒性,但增加了计算量实时性较差。经过不断地改进,目标跟踪算法在速度与精度上已有很大的提升,但由于复杂的背景环境、目标外观与尺度的变化等众多影响因素,使目标能够在复杂场景中实现精准快速地跟踪依然充满着巨大挑战。

本文以KCF算法为基础,首先针对该算法无法应对跟踪目标尺度变化的问题,提出尺度自适应更新策略[9]来完善KCF算法采用固定尺度窗口进行跟踪的缺陷;然后分别提取FHOG(F Histogram of Oriented Gradient)特征和利用PCA降维[10]后的CN特征进行串联融合,来提高算法在复杂背景下的跟踪精度;最后利用自适应目标响应策略训练KCF滤波器,并用子网格插值算法[11]代替简单线性插值算法,来提高跟踪器的整体性能。本文算法能够以较高的精度与速度完成复杂场景下的鲁棒跟踪。

1 KCF算法

KCF算法对样本循环采样,增加样本容量;利用循环矩阵对角化性质将矩阵运算转化成向量点乘,减少运算量;提取HOG特征,提高分类器识别能力;利用核函数,将特征映射到高维空间使其线性可分。KCF利用最小二乘法训练更新分类器,公式如下:

(1)

式中:X为训练样本;g为目标响应峰值;λ为正则化系数。通过训练找到一组权值w,w=(XHX+λI)-1XHg,其中,XH=(X*)T,X*为X的共轭;在傅里叶域中,利用循环矩阵可对角化性质求解w,公式如下:

(2)

(3)

于是可以得到检测样本的响应值,公式如下:

(4)

2 自适应多策略融合快速KCF算法

本文算法架构图如图1所示。首先,对输入的视频帧(除了第一帧以外)使用自适应尺度[12]更新策略,判断是否需要更新跟踪目标的尺度,采用SSIM(Structural Similarity)作为衡量依据,如果SSIM值小于阈值T则进行多尺度采样;然后,从多个尺度的目标样本中分别提取FHOG特征和利用PCA降维后的CN特征进行串联融合,计算多个尺度图像块的特征响应图,其中响应值最大的图像块即为最佳尺度;否则,认为目标尺寸没有发生变化,延用上一帧图像尺寸,不进行尺寸更新;最后,利用自适应目标相应策略训练位置滤波器,并用子网格插值算法代替线性插值算法,减少离散傅里叶变换次数,提高核相关滤波算法速度,更新训练集与滤波模板,在对下一帧图像进行同样操作,直到最后一帧为止。

图1 算法架构图

2.1 自适应尺度更新策略

KCF算法采用固定尺寸窗口对目标进行跟踪,跟踪过程中,目标的尺寸易于发生变化,KCF算法难以应对此问题,因此,本文采用自适应尺度更新策略来解决跟踪窗口尺寸固定不变的问题,自适应尺度更新策略如图2所示。

图2 自适应尺度更新策略

首先预定义尺度池P={Sp|p=1,2,…,p},Sp为尺度因子,设第t帧图像目标中心位置为(rt,ct),目标尺度为St,当输入第t+1帧图像时,以(rt,ct)为中心,然后提取尺度大小为St的图像块,第t帧与第t+1帧图像提取到的图像块分别为F1与F2,尺度池的引入严重增加算法计算量,导致算法难以满足实时性的需求,基于此,本文通过添加SSIM校验,来提高算法运行速度。计算第t帧与第t+1帧目标响应图像的SSIM值,公式如下:

(5)

式中:μF1与μF2分别表示图像块F1与F2的平均值,σF1F2表示图像的协方差,σF12与σF22表示图像F1与F2的方差,C1=(k1L)2,C2=(k2L)2,C1与C2是使分母不为0,维持稳定的常数,L是像素值,k1=0.01,k2=0.03。设定阈值T(取值范围0到1)作为判断图像相似的标准,当SSIM的值大于阈值T时,认为F1与F2响应图像相似[13],则保持当前目标的尺寸,不对目标进行尺度更新;如果SSIM的值小于阈值T,认为F1与F2不相似,即可认为目标尺寸发生变化,这时候在分别提取大小为Sp·St的p个图像块,归一化图像块为Zp,求出所有图像块的响应值,其中最大值y即为跟踪目标的最佳尺度。y的计算公式为:

(6)

式中:F-1为傅里叶逆变换。y取最大值时的Zp对应的Sp即为第t+1帧的最佳尺度St+1。在训练阶段更新滤波器系数和目标模板。通过添加尺度更新机制来减少算法计算量以此提高算法运行速度。

2.2 特征融合策略

KCF算法提取单一的HOG特征训练分类器,无法满足目标特征的多样性,在背景复杂的环境中,由于特征信息量不足,分类器难以有效地区分出目标,导致跟踪精度低、鲁棒性差,将HOG特征与CN特征进行融合的确是一个很好的解决办法,目前一些算法利用这种方式对其进行改进,效果显著,但是特征信息量的增加也增大了算法计算量,导致算法运行速度慢,难以满足实时性需求。因此,本文提出采用FHOG特征与利用PCA降维后的CN特征进行融合,在不过多损失特征信息量与增加算法计算量的双重情况下,为分类器提供更充分的特征信息,提高复杂背景下,分类器的辨别能力。

FHOG特征具有31个维度,是在36维HOG特征的基础上降维得到的,包含了HOG特征的所有信息,在对目标的特征提取中具有同样的效果,提取FHOG特征前后的图像如图3所示。

(a) 原图

(b) FHOG图图3 提取FHOG特征图

PCA首先将11维度的CN特征通过线性变换表示成线性无关的向量,利用协方差矩阵计算向量的分散程度,取方差最大的方向做投影,使降维后的数据最大限度地包含全部信息。设特征向量为X={x(1),x(2),…,x(m)},x(i)∈Rn,m=11,协方差矩阵为:

(7)

由特征值λ与特征向量u变换后得到:

WT=(u1,u2,…,um)m

(8)

式中:(u1,u2,…,um)是按特征值λ1,λ2,…,λn由大到小序列对应排放组成的矩阵,通过Y=WTX计算降维后的CN特征为:

(9)

式中:WCN是由协方差矩阵的前2个最大特征值向量组成。本文通过PCA对CN颜色特征自适应[14]降维至2维,实时地选择2维比较显著的颜色特征与31维FHOG特征再加1维灰度特征进行串联融合,最终的特征信息量为34维向量,避免损失过多特征信息量的同时最大限度地提高算法的速度。

2.3 自适应目标响应策略

KCF跟踪算法在第一帧图像初始化目标位置,然后提取目标特征训练分类器,在下一帧图像中找到响应最大的位置,更新分类器。因此在跟踪过程中,目标的外观会随着的时间的推移发生变化,在检测[15]步骤容易出现错误,对于每一帧模板都进行更新,这样可能会导致错误累积,最终模板不完全适合目标,发生偏移甚至完全跟丢目标,同时,KCF跟踪器应用一个简单的线性插值(α)t=(1-η)(α)t-1+η(α)t与一个固定的学习率η来更新模板,这样会导致算法运算效率低,模板不能很好地适应目标外观的变化。因此,本文提出了自适应目标响应策略使滤波模板的更新更贴合目标形变,其中g作为每一帧图像的响应,第一帧的目标响应为g0。测量响应最大值的相关性与目标运动特性和目标外观特性相结合,所以对式(1)的优化如下:

(10)

设图像响应g与g0的关系为g=g0+ε,并且g∈N(g0,diag-1(1/2ξ))。模型训练时,需要对样本进行移位,响应最大值为目标估计位置。接下来我们要计算这些移位的相关的分数作为模板的更新参数,使用高斯插值来填充其余分数。模板w用下式表示:

(11)

利用KCF算法巧妙地使用内核技巧,将输入向量通过高斯核函数映射到高维空间做运算,以此得到对偶域的闭型解,公式如下:

(12)

与此同时,由于子网格插值算法可以使用更粗的特征网格来训练和检测样本,因此利用三角多项式插值方法代替简单线性插值方法,通过对高频零填充来获得(α)t的大小,使其大小等于插值网格的大小,然后获得差值分数,减少目标样本与模板相关响应时的离散傅里叶变换次数,降低计算量,从而提高分类器的运行速度。

3 实 验

3.1 实验环境

实验数据环境为OTB2015数据集[16]中的51组视频序列,涵盖了11种复杂场景属性。实验运行环境为Windows 10 64 bit操作系统、处理器Intel @R Xeon @R SILVER4110C @2.10 GHz 16 GB的计算机,程序代码的编译环境为MATLAB软件R2016b版本。实验参数环境设置与KCF算法基本一致,尺度因子P设置为5,具体为{0.96,0.98,1,1.02,1.04},SSIM阈值T为0.9。本文采用以上实验环境进行跟踪实验。

3.2 评价标准

本文采用跟踪精度、跟踪成功率和跟踪速度来评估算法性能。

设视频总帧数为N,跟踪精度P是指中心位置误差D在阈值T1范围内的帧数与N的比值,计算公式如下:

(13)

式中:精度阈值T1的范围为0到50,P取值为阈值T1等于20像素时所对应的结果。中心位置误差D的计算公式如下:

(14)

式中:x1、y1表示目标真实位置;x2、y2表示目标预测位置。

跟踪成功率S是指计算跟踪目标预测位置和真实位置的重叠率O在给定阈值T2范围内的帧数和N的比值。计算公式如下:

(15)

式中:阈值T2的取值范围为0到1,S取值为取阈值T2等于0.5时所对应结果。重叠率O的计算公式如下:

O=area(RZ∩RY)/area(RZ∪RY)

(16)

式中:RZ为目标真实区域;RY为目标预测区域。

FPS代表算法跟踪速度,是N与算法处理整个视频序列所耗费的时间Ttoc的比值。计算公式如下:

(17)

FPS的值越大,代表跟踪算法的速度越快。

3.3 跟踪性能测评

3.3.1消融实验分析

为了验证本文算法的有效性,首先在OTB 2015数据集上进行了消融实验,对比算法及实验结果如表1所示。实验结果表明,在KCF算法基础上逐个添加改进策略,算法的跟踪精度与成功率在逐步提高,验证了本文算法的有效性。

表1 消融实验

3.3.2定量分析

本文选取5种具有代表性的跟踪算法与4种近年较优秀的跟踪算法进行对比实验,这些算法包括KCF算法、CN算法、DSST算法、KCFHS算法[17]、SAMF算法、FDSST算法[18]、CFNet算法[19]、LMCF算法[20],以及ECO-CH[21]算法,在OPE测试方法下,评测这些算法的跟踪精度和跟踪成功率,实验结果如图4-图5所示。

图4 跟踪精度

图5 跟踪成功率

实验结果表明本文算法在跟踪精度与成功率上优于近几年较优秀的相关滤波类跟踪算法LMCF、FDSST和融合了浅层深度特征的CFNet、ECO-HC算法,同时大幅度提升了基础算法KCF的跟踪性能,验证了本文算法的有效性。

另外,本文算法在11种复杂场景中均表现良好,特别在目标形变、尺度变化、平面内旋转、背景复杂这4种属性下,本文算法展现了较为优异的跟踪精度,实验结果如图6-图9所示。自适应尺度更新策略避免算法每一帧都进行多个尺度循环检测运算,减少了大量计算量的同时解决了KCF算法无法处理目标尺度变化的问题,使算法实现自适应调节跟踪框的大小;多特征融合策略利用PCA对特征降维后再融合,避免增加过多计算量的同时提取更加丰富的特征信息,提高滤波器的分辨能力,使算法以更加鲁棒的性能应对目标形变、背景复杂等跟踪场景;自适应目标响应策略通过结合第一帧的目标响应值获取目标外观信息并结合目标运动信息调节每一帧目标的响应值,使目标响应的最大值更接近目标真实位置,提高了跟踪算法在目标形变与平面旋转等复杂场景下的跟踪精度。

图6 形变跟踪精度

图7 尺度变化跟踪精度

图8 平面内旋转跟踪精度

图9 背景复杂跟踪精度

3.3.3定性分析

本文选取滤波类跟踪算法KCF、SAMF、FDSST和融合浅层深度特征算法ECO-HC在4种具有代表性的视频序列上进行定性分析,每个视频序列具有的属性如表2所示,可视化结果如图10所示。

表2 视频序列属性

(a) Shaking

(b) Soccer

(c) Football

(d) CarScale

图10 部分视频序列可视化结果

(1) Shaking序列。第23帧,跟踪目标的形状与尺度略微变化,KCF算法与SAMF算法严重漂移;第147帧,被跟踪目标发生了剧烈形变且伴有平面外旋转、光照变化等干扰因素,本文算法对目标定位的最好;第242帧,跟踪目标产生尺度变化与形状变化,此时本文算法对目标尺度控制得最好。

(2) Soccer序列。第59帧,跟踪目标发生快速移动且伴有严重模糊,ECO-HC算法与SMAF算法开始产生漂移;第179帧,ECO-HC算法与SMAF算法由于提取到过多背景信息而完全丢失目标,KCF与FDSST算法轻微漂移;第252帧,跟踪目标的尺度发生变化且伴有背景复杂、光照变化等影响因素,此时本文算法依然可以准确地跟踪到目标的位置,对尺度的控制优于FDSST算法。

(3) Football序列。第286帧,目标发生快速移动且被相似障碍物严重遮挡,此时本文算法与FDSST算法可以准确捕获目标的位置,SAMF、KCF与ECO-HC算法发生略微漂移,被相似障碍物牵引;第298帧,跟踪目标轻微形变且伴有平面内旋转等干扰因素,此时SAMF算法与KCF算法已经完全漂移,其他算法还可以勉强跟踪到目标;第319帧,跟踪目标快速移动且伴有平面外旋转,此时本文算法对目标的定位最好。

(4) Carscale序列。第188帧到220帧再到最后240帧,跟踪目标尺度由小到大逐渐变化着,且伴有平面内外旋转、快速移动等干扰因素,这些算法都能顺利完成跟踪任务,由于本文算法与SAMF算法采用尺度因子对目标尺度变化有一定的局限性,超过最大限度,本文算法也失去了对尺度的控制能力,此时基于尺度滤波器的FDSST算法与采用浅层深度特征的ECO-HC算法对目标的尺度定位的最好,本文算法虽没有FDSST与ECO-HC算法对目标尺度产生大幅度变化时定位得好,但是当目标的尺度在一定范围内变化时,本文算法对尺度的控制较优于其他算法。

3.3.4实时性分析

复杂的背景下,跟踪速度也是衡量一个跟踪算法的重要指标。表3是本文实验比较的10种跟踪算法的FPS值,本文算法的FPS较KCF算法虽然有所降低,但是权衡算法的跟踪精度和成功率的提高,损失的速度也是值得的,并且相比于其他跟踪算法,本文算法仍然占据一定的优势。SSIM检测标准对多尺度更新的效验、利用PCA对CN颜色特征的降维、将子网格插值算法代替线性插值均在保证算法跟踪精度的同时大幅度降低算法的计算量,提高计算效率,使算法快速运算满足实时性需求。

表3 跟踪速度

4 结 语

针对KCF算法存在的缺陷以及提高算法在复杂跟踪场景下的综合性能,提出了一种自适应多策略融合快速KCF跟踪算法。在Benchmark评测集OTB2015上进行了大量实验,对比了9种优秀的相关滤波类跟踪算法,充分验证本文对算法所做的改进具有实际效果,能够在目标形变、平面外旋转、背景复杂、尺度变化多种复杂场景挑战下,准确、鲁棒、快速地跟踪目标,满足实时性需求。但改进后的算法缺乏对跟踪目标重检测机制,一旦目标被遮挡或者经历严重外观形变,分类器难以适应目标瞬时的变化,导致跟踪失败,将再也不会检测到跟踪目标,进行后续的跟踪,完善此缺陷将是接下来的研究重点。