最佳伙伴相似性引导的核相关滤波跟踪算法

林椹尠, 郑兴宁, 吴成茂

(1. 西安邮电大学 理学院， 陕西 西安 710121； 2. 西安邮电大学 通信与信息工程学院， 陕西 西安 710121；3. 西安邮电大学 电子工程学院， 陕西 西安 710121)

目标跟踪算法是指根据目标第1帧位置信息，采用相关算法对目标进行检测，以预测其位置、运动轨迹等信息，进行后续更深入的处理与分析[1]。目标跟踪是计算机视觉中1个重要的研究方向，在视频监控、视频检索、交通监控等领域有广泛应用[2]。

目标跟踪算法分为生成式跟踪方法[3]与判别式跟踪方法[4]2种类型。生成式跟踪算法忽略背景信息，强调对目标本身的建模。这种方法需要构造复杂的目标外观模型，计算复杂度高，不适合用于实时的目标跟踪。判别式方法则是通过结合目标和背景信息训练分类器，在下1帧图像中使用分类器来区分目标和背景，跟踪性能好，在目标实时跟踪领域应用广泛[5]。

核相关滤波[6](kernel correlation filter, KCF)算法是一种常用的判别式跟踪方法。KCF算法通过在目标周围区域循环采样增加样本数量，利用循环矩阵的对角化特性将矩阵求逆转化为傅立叶变换域的点积计算，从而降低了计算的复杂度，提高了算法运行速度和精度，满足了实时性的要求。利用核运算将低维空间的计算映射到高维的核空间，满足大多数实际应用场景的需求[7]。但是，KCF算法在目标物体被遮挡、受到光照影响、快速运动、发生严重形变、旋转等情况下，容易出现跟踪丢失的现象，算法的鲁棒性较差，精确度较低[8]。

为了提高KCF算法的精确度和可靠性，本文利用最佳伙伴相似性(best-buddies similarity, BBS)[9]算法来引导KCF算法。首先采用Edge boxes[10]算法来生成候选区域；其次，结合尺寸、灰度特征归一化互相关 (normalized cross correlation, NCC)[11]算法和色调、饱和度、明度(hue saturation value, HSV)[12]颜色直方图三种筛选机制来减少候选区域的数量；再次，利用BBS算法来寻找目标最大可能位置，以此来降低BBS算法的运行时间；最后，融合KCF最大响应位置得分以及BBS算法得分来预测目标下一帧可能位置。

1 预备知识

1.1 KCF算法

KCF算法以岭回归分类器为核心，利用循环移位在目标区域进行密集采样来训练分类器，并将核函数运用到岭回归中，解决低维空间下的非线性问题，最后计算各样本的响应值。最大响应的位置就是目标的可能位置。算法中利用循环矩阵性质，把样本转换为傅立叶对角矩阵进行处理，简化运算，加快速度，实现对目标的快速检测与跟踪。

但是，KCF算法在上一帧的目标周围位置进行采样并且仅采用梯度方向直方图(histogram of oriented gradient, HOG)[13]特征，当目标快速运动、发生形变、被遮挡或受到光照影响时，容易造成跟踪模型被污染，从而导致跟踪失败。

1.2 BBS算法

BBS算法通过计算模板图像和候选目标区域内匹配特征点的个数来判断模板与候选目标的相似度，在匹配目标发生形变、遮挡、尺度变化、光照变化、背景嘈杂和旋转情况时具有较高的匹配精度。

由于BBS算法通过计算两组特征点集中BBPs的个数来寻找目标区域，所以当目标发生遮挡、形变、尺度变化、旋转或快速运动时，算法鲁棒性较好。本文利用BBS算法来引导KCF目标跟踪算法。

1.3 Edge boxes算法

实际跟踪过程中，BBS算法寻找目标可能位置时运行时间较长，尤其是面对较大尺寸的图像时。为了利用其优点，克服其缺点，引入Edge boxes算法来提高BBS算法速度。

Edge boxes算法根据图像边缘信息生成大量可能包含目标信息的候选区域(region proposals, RP)，通过计算包含在边界框中目标轮廓的个数来表示包含目标的可能性，并且通过计算边缘段的权值为每个RP评分。首先，Edge boxes算法通过结构化边缘检测算子[15]提取待匹配图像的边缘图，并采用非极大值抑制法将其稀疏化表示；其次，通过一定的聚合策略得到多个边缘组，并根据边缘组的相对位置和方向计算相似度；再次，使用基于不同步长的滑动窗口搜寻候选区域，根据所得相似度为滑动窗口内的每一个边缘段计算出一个权值并生成一个得分，表示滑动窗口所在位置包含目标的可能性；最后，根据边框的得分，将其从大到小进行排列，低于边界框得分阈值的RP将不被输出。该方法能够迅速从数百万潜在候选框中搜索到候选区域集合。

2 改进KCF跟踪算法

下面将利用最佳伙伴相似性算法来引导KCF跟踪算法，通过构建BBS目标检测模块，改善KCF算法在跟踪过程中由于目标被遮挡、发生严重形变或运动模糊等而导致跟踪失败的问题，提高KCF算法的精确度和成功率。

2.1 KCF预测目标位置

2.1.1 样本采集

KCF算法通过将目标样本进行循环移位实现正负样本的采集，采集的所有样本构成了循环矩阵，以此来降低训练和检测环节的计算复杂度。给定1幅基础图像,其一维向量表示为x1=(c1,c2,…,cn)，称之为基础样本。通过基础样本和由其平移所得的虚拟样本训练分类器。所有循环移位之后的样本构成的循环矩阵为

(1)

其中矩阵X的第1行是基础样本的向量元素，其他行是基础样本循环移位样本的各向量元素。

2.1.2 训练分类器

利用高斯核函数进行样本之间的点积计算，高斯核函数[6]表达式为

(2)

其中：σ表示高斯核函数的带宽；e表示向量间的点乘运算；^表示傅里叶变换域的值。

将所有点积计算的结果保存在核循环矩阵K中，其元素Kij=k(xi,xj)。此时，非线性回归函数可表示为

(3)

通过最小化样本xi和其对应的标签yi之间的平方误差和，得到由系数αi组成的系数向量

α=(K+λI)-1y。

(4)

其中：λ为正则化参数；y表示由标签yi组成的列向量。

利用循环矩阵对角化性质，可得系数向量α的傅里叶变换形式

(5)

其中：kxx表示核矩阵K的第1行，即由训练样本生成的自相关核向量；E为全1矩阵。

2.1.3 目标位置检测

计算当前图像中所有待检测样本z的回归值响应值

(6)

其中kxz表示训练样本x与检测样本z的互相关核向量。最大响应值位置就是当前帧中目标的可能位置。

2.1.4 参数更新

为适应跟踪环境的变化，在当前帧预测的目标区域继续采集样本，重新训练分类器。交替进行训练和检测，就能实现目标的持续跟踪。当前帧更新后的分类器参数值[6]的计算方法为

(7)

2.2 BBS算法匹配目标

跟踪过程中，利用Edge boxes算法将待匹配图像生成大量的候选区域(region proposals, RP)。由于生成的RP尺寸不同，首先需要筛选RP的尺寸。实际情况中，目标可能会发生严重形变或者尺度变化，所以将RP的筛选范围分为目标尺寸缩小一倍、不变和扩大一倍3部分。将符合目标尺寸变化范围的RP筛选出来，并将其与模板图像T0进行线性插值，形成图像I0，输出符合条件的RP位置和对应的I0。

其次，利用NCC匹配算法进一步筛选RP的数量，通过计算T0与I0的灰度相似度，筛选出与T0相似度较高的I0。

NCC算法首先将T0和I0灰度化，计算T0和I0的灰度均值，然后进行归一化操作得出模板图像t0和I0的灰度相似度值SNCC，NCC灰度相似度[11]计算公式为

(8)

其中：(s,t)表示像素点的位置坐标，s=1,2,…,a,t=1,2,…,b；a、b分别表示T0的长和宽；E(I0)和E(T0)分别表示T0和I0的灰度均值。

记录所有灰度相似度的平均值Smean，将每一次计算所得的SNCC与Smean做比较，保存SNCC大于Smean时的RP与其对应的I0，将其记为I1。

最后，利用图像的HSV颜色特征筛选上一步保存的RP。颜色直方图所计算的是不同颜色在整幅图像中的所占的比例，而不关心图像中不同颜色所处的位置信息。

通过判断T0与I1的HSV颜色分布相似性来筛选出与T0相似度较高的图像。HSV颜色相似度计算公式[12]为

(9)

其中：l表示一维直方图向量的维数，本文取64维；Ir和Tr分别表示图像T0和I1第r(r=1,2,…,l)维的值。如果max(Ir,Tr)为0，则分母用1来代替。

计算所有I1的颜色相似度的均值Rmean，将每一次计算所得的RHSV与Rmean做比较，当RHSV大于Rmean时，输出对应的RP和I1，将符合条件的I1输出，记为I2。将输出的每一个I2与T0进行BBS匹配，寻找拥有最佳伙伴相似对最多的I2，即为匹配的目标,保存此I2的位置坐标。

2.3 预测目标最终位置

将KCF算法预测得到的目标可能位置设为p1，将经过最佳伙伴相似算法匹配得到的候选目标位置设为p2，将两个位置坐标进行加权，构建BBS目标检测模块，得到目标最终位置

p=(1-γ)p1+γp2。

(10)

其中γ表示位置更新参数因子。

算法流程如图1所示。

图1 算法流程图

3 实验结果与分析

采用OTB100数据集[16]测试算法性能。设置目标搜索区域面积为跟踪框的2.5倍，正则化参数0.000 1，空间带宽0.1，更新模型参数的学习率β为0.02，位置更新参数因子γ为0.5，高斯核函数的方差为0.5。Edge boxes算法的滑动步长设置为0.65，候选区域与所标注区域的交并比(intersection over union, IOU)设为0.75，边界框得分最低值设置为0.01，并且在实验过程中算法参数固定不变。

实验环境为Intel(R) Core(TM) i5-5200U CPU @2.20GHz处理器，4GB运行内存，MATLABR2014a平台。

3.1 定性分析

为测试本文算法在面对目标物体被遮挡、发生旋转、严重形变、快速运动、光照变化或运动模糊等情况下的跟踪性能，在OTB100数据集中选取具有代表性的Jump、Jogging、Bird2、Bolt、Trans、Tiger2、Blur Body视频序列进行测试，跟踪结果如图2-8所示。图中的虚线、实线和加粗实线框分别表示KCF、稀疏正则化判别式相关滤波(spatially regularized correlation filters, SRDCF)[17]和本文算法的跟踪框。

3.1.1 旋转情况下的性能

如图2所示，在Jump序列第17帧中，目标物体开始旋转并且发生剧烈形变，本文算法可以正确跟踪目标物体，KCF算法和SRDCF算法出现跟踪丢失的现象；第29帧目标物体完全旋转，第109帧目标旋转结束，整个旋转过程中，只有本文算法可以顺利跟踪目标物体，KCF和SRDCF算法均跟踪失败。这是因为，本文算法所构建的BBS目标检测模块可以有效针对目标旋转现象，而KCF算法和SRDCF算法由于不具有旋转不变性，所以很难在目标旋转情况下实施跟踪，出现跟踪丢失现象。

图2 Jump序列跟踪结果

3.1.2 遮挡情况下的性能

如图3所示，在视频序列Jogging中，从第52帧开始，运动目标受到较长时间遮挡，并且发生形变，直到第65帧目标重现，跟踪结果显示本文算法和SRDCF算法可以正确跟踪到目标，而KCF算法由于在跟踪过程中目标被长时间遮挡而造成跟踪模板被污染，从而跟踪上错误的目标。如图4所示，在Bird2序列整个跟踪过程中，目标受到部分遮挡、发生旋转并且背景嘈杂，跟踪结果显示，本文算法的跟踪框可以包含大部分的目标信息，而KCF和SRDCF算法跟踪框包含着目标信息较少。这是因为，本文算法的BBS目标检测模块在目标物体被完全或部分遮挡又重现后，可以根据模板与待匹配图像中BBPs的个数重新匹配到目标位置，从而能够顺利跟踪。

图3 Jogging序列跟踪结果

图4 Bird2序列跟踪结果

3.1.3 快速运动和严重形变下的性能

如图5所示，在Bolt序列中，从第86帧开始，目标物体发生形变并且运动速度较快，跟踪结果显示，本文算法可以顺利跟踪目标物体，而KCF和SRDCF算法跟踪器出现模板漂移现象。如图6所示，在Trans序列中，目标物体发生严重形变，KCF和SRDCF算法的跟踪框包含大部分的背景信息，而本文算法跟踪框包含着大量目标信息。

3.1.4 光照情况下的性能

如图7所示，在Tiger2序列中跟踪目标受光照的影响较大。跟踪结果显示，在第127帧，由于目标受到较强光照，使得外观变得模糊，跟踪模板被背景物体所占据，导致KCF和SRDCF算法出现跟踪漂移现象。而本文算法依旧可以正确跟踪目标，这说明本文算法的BBS目标检测模块有效，能显著提高目标物体在强烈光照下的跟踪性能。

图5 Bolt跟踪结果

图6 Trans序列跟踪结果

图7 Tiger2序列跟踪结果

3.1.5 运动模糊情况下的性能

如图8所示，在视频序列Blur Body中，跟踪目标由于相机晃动导致运动模糊。Blur Body序列从第137帧开始运动模糊，在第237帧中，KCF算法出现跟踪丢失的现象，本文算法和SRDCF算法可以正确定位目标位置，第303帧，KCF算法和SRDCF算法均不能正确跟踪到目标，只有本文算法可以顺利地跟踪目标物体。说明本文算法的目标检测模块可以不断地更新目标表观模型，在面对跟踪目标外形变化的情况时，表现出较好的跟踪性能。

图8 BlurBody序列跟踪结果

3.2 定量分析

为了进一步验证本文算法在处理特殊属性视频时的跟踪性能，采用跟踪成功率和精确度作为评价算法的准则[18]。跟踪精确度指预测的目标位置与人工标注的目标位置的欧式距离小于指定阈值的帧数占总帧数的比率。成功率指预测的目标边界框和人工标注的边界框的IOU值大于指定阈值的帧数占总帧数的比率。

在OTB100数据集中选取旋转、遮挡、快速运动、严重形变、光照和运动模糊情况下的58组不同属性的视频进行测试，3种算法的平均精确度和成功率如图9-10所示。

由图9可以看出，随着阈值的增大，精确度曲线呈上升趋势。本文算法的精确度始终高于KCF算法和SRDCF算法。当指定阈值为20时，本文算法的精确度为82.3%，比KCF算法的59.5%和SRDCF算法的68.2%分别高了22.8%和14.1%。

由图10可以看出，随着阈值的增大，成功率曲线呈下降趋势，且本文算法的成功率高于KCF算法和SRDCF算法。当指定阈值为0.5时，本文算法的成功率为58.2%，比KCF算法的41.1%和SRDCF算法的55.1%分别高了17.1%和3.1%。

图9 3种算法的精确度

图10 3种算法的成功率

4 结语

提出了一种由BBS算法引导的KCF跟踪算法。利用Edge boxes算法生成大量RP，然后通过BBS算法计算目标图像和RP图像两个特征点集中BBPs的个数来寻找目标的可能位置，融合BBS得分和KCF位置响应得分计算出目标最终位置。在OTB100数据集上测试算法的跟踪性能，实验结果表明，相对于经典的KCF算法和SRDCF算法，本文算法可以在跟踪目标发生旋转、遮挡、严重形变或运动模糊等情况时进行有效跟踪，且精确度和成功率较高。但是，本文算法由于引入BBS匹配法来寻找目标最佳位置，算法运行时间较长，实时性较差，下一步将研究在不影响算法性能的基础上进一步提高算法速度。