基于KCF的样本更新与目标重定位方法

吴世宇，李志华，王 威

(河海大学能源与电气学院，江苏 南京 211100)

0 引 言

视觉跟踪在视频监控[1-2]、自动驾驶[3-4]、医学研究[5-6]等领域有着广泛的应用，是计算机视觉领域的一项具有挑战性的任务。跟踪的目的是根据目标在首帧中的位置，预测出目标在后续视频序列中的位置。近年来，涌现出了大量的目标跟踪算法，也取得了显著的成果，但由于目标会出现严重遮挡、外观变化明显以及运动出视线之外等[7]情况，如何实现对目标精准、快速的跟踪仍是一个难题。

通常情况下，跟踪算法可分为生成式跟踪[8-11]和判别式跟踪[12-16]。生成式跟踪使用生成模型对物体表观特征进行描述，通过搜索寻找最佳的匹配窗口定位目标。生成跟踪不需要训练大量的数据，但是易受背景干扰而产生误跟踪现象。判别式跟踪把视觉跟踪看作为分类问题，通过对目标和背景的学习，将预测的区域作为目标所在的位置。在目标跟踪时，判别式方法可以充分利用背景信息，但是通常需要大量的数据进行训练来实现良好的跟踪性能。虽然这2类跟踪算法已经取得了很大的进展，但从有限的训练样本集中归纳出目标的外观模型仍然是一个具有挑战性的任务。在判别式跟踪中，相关滤波[17](Correlation Filter， CF)由于快速的运行速度以及定位的精确度在跟踪领域取得了巨大的成功。Bolme等[18]首次将CF算法应用到跟踪领域，提出了误差最小平方和滤波器(MOSSE)，每秒可以处理上百帧的图像序列。Henriques等[19]提出了CSK算法，使用循环矩阵的结构，通过增加负样本数来增强分类器的训练。为了进一步提高CSK跟踪器的性能，Danelljan等[20]提出了颜色命名方法(Color Name, CN)，充分应用了目标的颜色特征。Danelljan等[21]提出的DSST算法分为位置滤波器和尺度滤波器2大部分，其中尺度滤波器可以与其他相关滤波算法结合，对解决目标尺度变化有较好表现。基于CSK跟踪算法，Henriques等[22]提出了KCF算法。为了提高跟踪算法的精确度和稳定性，KCF计算目标的HOG特征而不是原始的像素值而且简化了计算过程，提高了运算效率。Bertinetto等[23]将HOG特征和CN特征进行融合，提出了Staple算法，在模糊、光照变化明显的情况下可以完成有效跟踪。Danelljan等[24]提出了ECO算法，简化训练样本，解决模型的过拟合问题，在运行速率和跟踪效果上都有很好的表现。Zuo等[25]基于支持向量机对相关滤波算法进行改进，扩大样本间的差异性从而优化了分类效果。但在大多数相关滤波算法中，并没有对预测结果可信度进行判断，直接作为样本训练分类器。在背景误判为目标的情况下，容易污染训练样本集，无法对目标重新定位，导致跟踪失败。

针对样本污染、目标重定位等问题，本文对KCF算法进行改进，提出一种样本更新机制，评价跟踪结果的可信度，自适应地选取样本对跟踪模型进行更新。使用Kalman滤波算法估计目标位置，然后评价其估计结果。若判断为目标丢失时，使用ORB特征点匹配算法完成对目标的重定位。

1 KCF跟踪算法

KCF跟踪算法中，构建样本的循环矩阵，扩充分类器的样本集，结合循环矩阵的性质，提高跟踪效率，然后通过核函数确定输出响应最大的区域作为新的目标区域，最后根据当前区域的信息对分类器进行更新，实现对目标实时跟踪。

1.1 循环矩阵

正样本的获取一直是目标跟踪工作关注的重点，但是用判别式方法进行跟踪时，需要给训练器足够的负样本，负样本的采样不足对跟踪精确度的提升有着重要影响。在KCF跟踪算法中，将目标作为基础样本即正样本，通过循环移位转换获得足够多的负样本。设基础样本表示为x=[x1,x2,…,xn]T，移位矩阵为P，故一次移位之后的结果可表示为Px=[xn,x1,x2,…,xn-1]T。循环矩阵X为：

X=C(x)=(P0x,P1x,P2x，…,Pn-1x)

(1)

循环矩阵可由离散傅里叶变换进行对角化：

(2)

1.2 分类器训练与检测

本文使用线性岭回归对样本进行训练。训练的目的是找到函数f(z)=ωTz，使样本与其目标值的误差平方和最小，即：

(3)

写成矩阵形式：

(4)

其中，列向量y为样本标签，λ为保证系统的泛化性能的参数，列向量ω表示权重系数。求公式(4)的闭式解：

ω=(XHX+λI)-1XHy

(5)

其中，I为单位矩阵，XH表示X的共轭转置矩阵。应用式(2)对式(5)进行计算简化，可得：

(6)

其中，⊙表示向量间的点积运算。该方法在提取图像特征以及求解一般回归问题上节约了计算的成本。考虑到非线性回归问题，为了获得更有效的分类器，引入核技巧，将线性问题映射到非线性空间，非线性回归函数可表示为：

(7)

其中，k(z,xi)为核函数。此时的权重系数列向量为α=[α1,α2,…,αn]T，同样运用式(2)，即循环矩阵的性质，可以快速对其进行求解：

(8)

同样可以应用循环矩阵的技巧来加速整个检测过程。设在下一帧中相同位置处的图像块为z，将其视为基础矩阵，计算其响应值：

(9)

1.3 尺度自适应

在原KCF算法中，没有解决跟踪目标尺度上的变化问题。使用固定大小的跟踪框容易产生漂移现象，导致跟踪精度不够、跟踪失败。为此，将KCF算法与DSST中的尺度滤波器相结合。

训练阶段在目标所在位置，按不同尺度截取一系列图像块并计算每一个图像块的HOG特征，计算图像块的响应值，得到滤波器模版。检测阶段则是在预测位置处分别计算不同尺度图像块的响应值，根据响应的最大值确定目标的大小。

2 改进的KCF算法

2.1 样本更新机制

在长期目标跟踪中，目标可能会存在遮挡、模糊以及变形等问题。通常情况下，相关滤波算法没有对跟踪结果的可靠性进行判断，直接更新跟踪模型。在这种情况下，由于测量误差的不断积累和传播，即使是短暂的遮挡，也有可能导致跟踪目标的丢失。因此，评估跟踪结果的可信度非常有必要。针对以上问题，本文提出样本评价与更新机制。

KCF的跟踪机制是选择响应值最大的图像块来确定跟踪目标的位置，但是在目标受到遮挡、模糊以及变形等情况影响时的响应值不足以将目标和背景区分开来。尤其是在背景与目标相似度较高的情况下，背景处的响应大于目标处的响应，极易造成目标跟踪的丢失，致使跟踪失败。

图1 目标有、无遮挡时的响应图

如图1所示，在模糊和遮挡情况下的目标样本响应的最大值，与邻域的响应值非常相近。此时，背景有可能被判断为前景，并且直接进行样本更新，污染样本集。因此对样本进行选择性的更新是很有必要的。

图2 可信度评价示意图

如图2所示，令响应的最大值为Pa,b，与其去心邻域内响应平均值的比值作为判断是否进行样本更新的标准，即：

(10)

其中，N=(2n+1)2-1，为Pa,b去心邻域内的响应的个数。当I比值大于某一阈值γ，此时的预测目标有较高的可信度。反之，区分度较弱，可信度较低。只取可信度高的目标图像对模型进行更新。这种更新机制不仅可以解决训练样本污染的问题，而且可以为目标遮挡等情况的发生提供预警功能，从而进行后续操作。

2.2 结合Kalman滤波进行跟踪

状态方程：

(11)

观测方程：

(12)

其中，Zk为预测目标位置构成的向量，向量Wk-1为过程噪声，向量Vk为观测噪声。在跟踪过程中，KCF可优先在Kalman预测的位置处计算区域的响应值，迅速对目标定位。

2.3 目标的重定位

当跟踪结果的可信度低时，需要在之后的序列中重新确定目标位置。本文使用ORB特征点匹配的方法，对目标进行重新定位。

ORB采用FAST算法来确定特征点的位置。比较候选点与周围点的差值，如果差值大于某一阈值的点对超过一定的数目，则将其视为角点。为了加速特征点的检测过程，如图3所示，选取候选点P周围的1、5、9、13等4个点中，至少有3个符合要求，否则不将其作为特征点，不再进行其他邻域点的计算。

图3 特征点的选取

ORB的描述子选择BRIEF算法计算。将计算所得的二进制串描述子，比较它们的汉明距离进行特征点的匹配。相比于其他特征点算法，ORB可以较快地完成特征点之间的匹配。使用ORB特征点对目标进行重定位，可以满足跟踪的实时性要求。

当根据判断结果需要重新确定目标位置时，保留当前时刻的目标图像，在之后的图像序列中，使用ORB特征点进行匹配，获得目标在当前图像中的位置信息，完成重新定位。

图4 使用ORB特征点匹配对目标重新定位

如图4所示，在跟踪小女孩时出现遮挡、模糊等问题，故保留前一时刻的目标图像，在后续图像中对其进行匹配，直到匹配成功获得目标的位置信息，确保后续跟踪的顺利进行。

2.4 算法流程

首先，框选出目标进行初始化，采用KCF-DSST框架，结合Kalman滤波对目标进行跟踪，根据图像块响应的峰值与去心邻域平均值的比值I，当I大于阈值γ时，采用当前位置的图像目标对样本集进行更新操作，否则保留当前位置图像，在后续图像序列中使用ORB特征点匹配算法对目标进行重新定位。具体流程如图5所示。

图5 算法流程图

3 实验结果与分析

3.1 实验环境与参数

实验的环境为Intel(R) Core(TM) i5-3230M CPU 2.60 GHz 6 GB的Win7 64 bit操作系统，使用Python3.5完成算法的实现工作。实验中的比值参数γ=2.25,其他参数继承了原KCF算法里的参数值。最后使用TB数据集[26]对算法进行对比验证。

3.2 跟踪性能对比

在TB数据集中选取具有遮挡、模糊、运动变化明显等干扰特征的视频序列，本文使用精确度与成功率对算法性能进行评估。对比情况如图6、图7所示。

图6 精确度图

图7 成功率图

由图6、图7可知，在如Jogging等存在遮挡的视频序列中，KCF、KCF-DSST跟踪算法由于缺少对跟踪结果可靠性的评价机制和重定位方法，所以在目标丢失、样本污染后，无法进行重新定位跟踪，而本文提出的方法在精确度和成功率上都有着突出的提升。在如MotorRolling等存在背景复杂、目标突变的序列中，也有着较为明显的改善。在其他视频序列中，跟踪性能也有一定的提高。直观的跟踪结果如图8所示。

…KCF，--KCF-DSST，—本文方法图8 跟踪结果对比

3.3 跟踪时间效率对比

在实现有效跟踪的同时，跟踪算法的实时性也是跟踪算法的重要评价标准之一。本文在测试视频中统计并对比了相关跟踪算法的时间效率，即算法平均每秒处理的视频帧数，如表1所示。

表1 相关跟踪算法运行速率

跟踪算法KCFKCF-DSST本文算法平均速率/(帧数·s-1)121.7430.327.81

由表1可知，本文提出的算法的运行速率达到了27.81帧/s，虽不及KCF算法上百帧的运行速率，但与KCF-DSST算法相差无几，可以满足实时性的要求。

4 结束语

本文使用KCF-DSST框架结合Kalman滤波对目标位置进行预测，提出目标样本更新机制，目标发生遮挡、模糊等强干扰时，跟踪结果可信度较低，当前目标不加入训练样本进行模型更新，保留前一时刻的可信度高的图像，提取角点并计算描述子，在后续序列中通过特征点的匹配操作，定位出目标当前位置，重新进行跟踪。本文算法相比于原KCF算法在运行速度上有所降低，但在跟踪性能上都有一定的提升，在遮挡、模糊等情况下改进明显，可以满足跟踪实时性的要求。但在运动位置突变、场景变化迅速、高速运动等情况下，跟踪精确度和成功率还有很大的提升空间。在优化跟踪性能的同时，如何提高算法的运行速率也将是今后研究工作的重点之一。