核相关滤波融合稀疏表示的目标跟踪算法

邱泽敏

(中山大学新华学院 信息科学学院，广东 广州 510520)

0 引 言

受遮挡、光照变化、尺度变化、旋转、快速运动等因素的影响，设计鲁棒性强、实时性好的目标跟踪器仍然是计算机视觉研究者们面临的一个重点和难题。近5年学者们的研究显示，深度学习的方法在目标跟踪方面取得显著效果，但这些算法都是以高配置的硬件设备和不断加深的网络层次来保证算法的强鲁棒性。目标跟踪最重要是要处理好目标的特征信息，核相关滤波和稀疏表示正是两种有效处理特征信息的常用的跟踪方法。核相关滤波从信号的角度去处理目标信息以提高算法的运行速度，稀疏表示则力求用最少的信息去表达目标各部分信息。本文提出一种将核相关滤波和稀疏表示融合的方式进行目标跟踪，在保证算法运行速度的同时最大限度地提取候选目标的特征信息，且不需要很大的机器设备开销。在标准数据集上的实验结果表明，本算法在跟踪速度和跟踪效果上与其它算法相比具有最好的跟踪效果。

1 核相关滤波和稀疏表示

目标跟踪算法可分为相关滤波器和非相关滤波器[1]。KCF[2]是相关滤波中的优秀代表，其利用循环矩阵的特性，将核相关函数引入到频域里，使得算法的时间复杂度O(n3)降到O(nlogn)。KCF的目标跟踪是基于岭回归，主要是找到一个函数f(z)=wTz使得样本点xi和目标yi的均方差最小，即最小化式(1)

(1)

式中：λ是控制过拟合的正则化参数(regularization para-meter)。当采用式(2)将输入的线性问题映射到非线性特征空间Φ(x)，求解问题就从求解w变为求解系数向量α

w=∑iαiΦ(xi)

(2)

α可通过式(3)求解

(3)

与同时期的其它跟踪算法相比，KCF运算速度非常快，能达到实时跟踪的要求。但是KCF目标位置的预测是在上一帧目标的一定范围内进行搜索，超过这个范围跟踪很容易发生漂移。此外，KCF并不处理尺度变化和平面内旋转等情况。

相关滤波器随着神经网络特别是卷积神经网络在图像识别中的应用而得到发展。Ma等[3]从VGGNet中析取出三层卷积特性，通过“双线性内插法”将深度特征统一为相同尺寸，用一种适用于相关响应的从粗到细的方法预测目标位置。为处理尺度问题，Danelljan等[4]提出DSST算法，算法根据目标不同采用不同的尺度采样从而估算目标尺度，然后采用平移滤波器和尺度滤波器训练得到目标位置。Siam[5-7]等深度学习的方法往往以高配置的硬件设备为基础，通过大量图片作为学习样本构造具有一定规模的学习模型，以提高目标跟踪的准确度。由于采用了神经网络，这些方法无一例外需要配置高性能的设备开销，方能保证算法结果的鲁棒性。视频跟踪最重要是要处理好目标的特征信息，基于产生式模型的稀疏表示跟踪方法通过对信号进行稀疏编码，能很好地表征目标的特征信息。

基于稀疏表示的目标跟踪方法一直受到很多学者的推崇和研究。稀疏表示通过构造完备的目标模板字典来表示跟踪目标的结构化信息，在后续帧的跟踪过程中将候选目标映射为目标的稀疏线性表示，以此对候选目标进行相似度度量，并最终确定跟踪目标的位置。早期的基于稀疏表示的跟踪算法通过在第一帧中构造正模板和负模板作为完备字典，通过对候选目标密集采样提取模板特征参数，同时求取局部图像块在完备字典中的映射等手段提高目标模板的精准度。有的则是以K最近邻分类算法对最开始的10帧图片进行计算求得目标模板，在局部图像块密集采样之后通过线性回归对候选目标进行相似度度量。Zhang等[8]提出一种一致性低秩稀疏跟踪器，该算法能自适应地修剪和选择候选目标，利用低秩约束联合对应目标的图像区域。Zhang的团队还提出了一种结构稀疏跟踪算法SST[9]，该算法利用候选目标与局部块之间的内在关系，共同学习其稀疏表示，同时保留了候选目标内部局部块之间的空间布局结构。总体而言，稀疏表示构建起的完备字典由于包含了较多的目标特征信息，能较好处理遮挡、旋转、尺度变化等情况，仍然具有重要的研究价值和意义。

2 本文算法

本文提出一种核相关滤波和稀疏表示相结合的目标跟踪方法，算法总体思路如图1所示。该算法先对每一个输入的视频帧快速地求出目标的最大可能位置，然后采用仿射参数密集采样确定候选目标集，接着以稀疏表示和对齐池化构建外观模型，最后采用探测后重定位的方式更新算法模型。与其它同类跟踪器的对比实验结果表明本算法跟踪结果鲁棒性最好。

图1 本文算法框架

2.1 候选目标集的获得

算法先用核相关滤波获取目标的最大可能位置，主要过程分为训练阶段和预测阶段，然后在该位置上通过仿射函数进行密集采样从而获得候选目标集。

2.1.1 最大可能位置

训练阶段，对于输入的每一帧，提取给定位置目标的HOG特征x，对于第一帧，给定位置就是标注，而后续帧的给定位置则是本帧的预测位置。然后按照式(3)在频域内计算岭回归的系数向量α，即分类器参数。核相关函数采用高斯核计算该帧的核自相关，即kxx由式(4)计算得到，x*是x的复共轭，F-1表示傅里叶逆变换，⊙表示点乘

(4)

考虑目标在跟踪过程中相邻帧间位置信息的连续性，本算法采取简单的模型更新方式，即在计算本帧的系数向量α和HOG特性x时，采用式(5)和式(6)进行计算

α=(1-i)×α′+i×α

(5)

x=(1-i)×x′+i×x

(6)

其中，α′和x′分别为上一帧的系数向量和HOG特性，i为某一常数。

在预测阶段，求解响应最大值，响应通过式(7)求得

(7)

式中：α为上一帧的分类器参数，kxz表示样本点和候选目标的内核矩阵，采用相邻两帧的核相关，即x和z分别为上一帧训练后和当前帧的HOG特征，求解方式如式(8)所示

(8)

2.1.2 密集采样

响应最大值所处的位置意味着是目标的可能性最大，由此可获得跟踪目标的最大可能位置pos，但是该位置信息并不表征目标的尺度变化、平面内旋转等信息。因此，本算法在该最大可能位置附近，采用仿射参数进行密集采样，构成候选目标集合A=[a1,a2,…,an]，ai表示某个候选目标，n表示采样的个数，采样过程如式(9)、式(10)所示

P0=h(g(pos),[1,n])

(9)

P1=P0+R.*h(opt.affsig(:),[1,n])

(10)

上述公式中函数g将矩阵转换为仿射参数，函数h则将函数g的结果扩充为1×n的矩阵，R为随机生成的矩阵。

仿射参数的设置为opt.affsig[px,py,scaling,RA,AR,SA]， 其中px和py表示位置在横轴和纵轴方向的偏移量，scaling表示缩放的比例，RA(rotationangle) 为目标的旋转角度，AR(aspectratio) 是目标长宽比，SA(skewangle) 是倾斜角。

由此，P1构成候选目标集合，这些集合能全面表示目标在跟踪过程中尺度变化、旋转等情况的变化。

2.2 外观模型构建

算法采用基于字典的稀疏表示和对齐池化的方式来构建外观模型。

算法先以视频序列第一帧作为模板，通过在模板上采样N个相互重叠的局部图像块构造模板字典D=[d1,d2,…,dN]∈Rd×N， 其中d是局部图像块的维度，字典D的每一列通过L2归一化获得。通过这种方式，每个局部图像块就表征目标物体的某一部分内容，因此能完整地描述目标的结构。

接着是对候选目标集A中的每个候选目标通过字典进行映射，以求得相应的稀疏编码。目标区域内的局部图像块可表示为字典D中几个基本元素的线性组合，即能通过求解式(11)计算得到候选目标集中每一个候选目标的每一个局部图像块在字典中的映射情况

(11)

式中：yi是候选目标第i个局部图像块，B=[b1,b2,…,bN]T∈RN×(N×n)则是相应的稀疏编码，bi表示模板中第i个图像块对候选目标集A中每个候选目标的每个图像块的编码，λ1为稀疏性约束参数。

由于字典中构成模板的各个局部图像块表征的是目标某个位置的具体信息，那么上式求得的某个候选目标ai的第j个局部图像块与模板中同一位置的图像块应该具有更高的相似度，即模板中第j个图像块能最好表征该位置信息。如字典中第一个元素b1能更好地描述目标左上角的图像块信息。故此本算法采用对齐池化的方式来处理稀疏编码，以提高算法位置预测的准确度。对齐池化过程如图2所示，候选目标ai与目标的相似度可以用式(12)求得

(12)

式中：Bi=[v1,v2,…,vN]T∈RN×N表示模板对候选目标ai的稀疏表示，vi∈RN则是第i个图像块对该候选目标的编码。

图2 对齐池化

2.3 模型更新

在跟踪过程中，目标由于遮挡、光照、尺度变化等因素，使得跟踪过程异常复杂，跟踪模型的更新就显得非常重要。本算法采用先检测再重新定位跟踪目标位置的方式应对跟踪目标的漂移。

2.3.1 漂移检测

将第一帧与当前候选目标帧的跟踪目标分成N个局部图像块，针对模板第一帧的每一个局部图像块Tk，提取其灰度特征k，然后采用多项式核相关函数计算其核自相关tkk，即按照式(13)进行计算，a、b是多项式常量

(13)

同时与高斯标签yt通过式(14)计算局部图像块Tk的岭回归系数向量αk

(14)

对于候选目标的对应局部图像块Tk′，同理求取其灰度特征k′，仍然采用多项式核相关函数计算模板和候选目标特征的相关性，计算如式(15)所示

(15)

则该局部图像块的响应用式(16)计算

(16)

最后，计算所有响应值小于某个阈值ε的个数count，响应值小于阈值表示该局部图像块与第一帧的相似度较低。当count的数值大于N的一定比例时，跟踪发生漂移，漂移检测算法如下。

算法1：漂移检测算法

输入：模板(即第1帧)的局部图像块TP，当前帧的局部图像块CP，局部图像块大小patch和数量N，采样数n。

输出：发生漂移的局部图像块数量count。

(2)提取CP的灰度特征， 加汉宁窗得k′， 按式(15)计算模板和候选目标得核相关tkk′， 按式(16)计算响应rp(:,:,j)。

(3)求响应rp(:,:,j) 的最大值MAX。

if MAX<阈值ε(本实验取0.4)count=count+1;

(4)转步骤(1)执行N次。//N为局部图像块的数量

2.3.2 重定位

跟踪漂移通常在目标快速变化的情况下发生，此时相邻帧之间目标的位置变化幅度较大，本算法重定位采用在当前帧位置pos的上、下、左、右4个方向上，以一定的步距s调整跟踪位置，加上原本帧的位置共5个候选位置，位置探测的方式由式(17)计算

dp=[p1,p2;p1-s,p2;p1+s,p2;p1,p2-s;p1,p2+s]

(17)

式中：p1和p2为位置pos的横坐标和纵坐标，然后按上述方式重新计算5个位置上的所有局部图像块的响应值，提取count值最小的那个位置作为调整后的目标位置。重定位并不在当前帧进行调整，位置调整将在下一帧跟踪时进行，重定位算法如下。

算法2：重定位算法

输入：漂移检测count值，局部图像块数量N，字典D。

面对严峻的形势，林洋多次主持召开会议，广泛征求职工意见，最终达成共识：在配合政府征地拆迁的同时，因势利导，初步理出了适合本单位转型发展的工作思路——将剩余土地转型发展，建日光温室大棚。他将上述工作思路形成报告后，上报了市政府和市国资委，赢得市政府大力支持。2011年，云城乳业“日光温室大棚建设项目”顺利实施，当年建起标准化日光温室大棚131座。

输出：重新定位的目标仿射参数(含目标位置)。

(1)当count≥0.6*N时， 执行本算法后续步骤。

(2)按式(17)重新给出5个候选位置。

(3)求5个候选位置的局部图像块， 按式(11)计算其稀疏系数， 按式(12)计算其与目标的相似度。

(4)按算法1再次计算5个候选位置的count值。

(5)取5个候选位置中count值最小的，并保存其仿射参数。

3 实 验

实验环境为i7-3.4 G/16 G/win10(64 bit) /MATLAB R2017b，本文算法的正则化参数λ取值0.0001，N=49，d=8×8，n=20，σ=0.5，λ1=0.01。漂移检测时，多项式常量a=1，b=7，ε取值0.4，设置count数值大于0.6N时，跟踪发生漂移，步距s取值8。

我们将本文算法与现有公开的同类型跟踪算法进行比较，这些算法包括Siam-FC[5]、CFNet[6]、SiamRPN[7]、SST-2015[9]、RSSTDeep[11]、MCPF[10]和KCF[2]，各算法参数均使用该算法的默认参数，受实验环境和不可控因素影响，实验结果可能与相关文献有出入。

实验在OTB100上的98个视频，100个测试场景中进行，这些视频基本涵盖了目标跟踪中最常见的遮挡、变形、尺度变化、光照变化等挑战因素。

实验采用OPE、SRE的评价方式。OPE(one-pass evaluation)是单次通过评估，即视频帧序列只运行一次；而SRE(spatial robustness evaluation)是空间鲁棒性评估，即通过移动初始帧的位置(12个方向)和缩放窗口的大小来评估算法的敏感度。

3.1 定量比较

精度曲线和成功率曲线如图3所示，从图中可以看到，本算法与其它算法相比都能取得最好的效果。

精度曲线显示中心误差小于中心误差阈值的变化情况，通常将阈值20像素时的值作为算法的跟踪精度，图3中本文算法的OPE跟踪精度为0.833，比第二位的CFNet高出1.1%。

成功率曲线表示随重叠率阈值从0变为1时成功帧的比率，成功帧表示其重叠量大于给定阈值，本算法取成功曲线下的面积作为算法评估的依据。图3中显示本文算法的OPE的成功率比CFNet算法高出9.2%。

为更好地验证算法在实时性方面的性能，实验记录了每个算法每秒处理的视频帧数，统计数据见表1。Mean FPS(frames per second)表示算法平均每秒跟踪的视频帧数，该数值越大表明算法运行速度越快。KCF的处理速度最快，达到平均每秒处理143帧的速度，本文算法次之。

实验过程发现，本算法在取得最大可能目标位置之后的采样数对算法准确率的影响很大，如分别设置采样数为10、20、40、100时，算法每秒运行的视频帧数有较大差别，采样数量越多，算法每秒处理的视频帧数越少，同时算法的精确度和成功率也越高。通过多次重复实验，综合考虑算法在准确率和实时性两方面的性能，本算法设置20左右的采样数，跟踪能达到最好的鲁棒性。

图3 OTB100下的精度曲线和成功率曲线

表1 算法视频帧率

表2显示了各个算法在遮挡(Occlusion)、照明变化(Illumination variation)、快速运动(Fast motion)、尺度变化(Scale variation)、平面外旋转(Out-of-plane rotation)、平面内旋转(In-plane rotation)等属性下的跟踪成功率，表中第一和第二的成功率分别用粗体下划线和粗体表示，从表中可以看到，本文算法的跟踪成功率最高。

表2 各算法在各种属性下的成功率

3.2 定性比较

图4显示各算法的跟踪效果，图中选取CFNet、SiamRPN、SiamFC、MCPF、RSSTDeep等几个表现较好的算法与本文算法在序列Walking2、FaceOcc1、FaceOcc2、David3、Singer1、CarScale、Woman中的跟踪结果进行比较，可以看到本文算法具有最优性能，以下从遮挡、旋转、快速移动等方面进行详细论述。

本算法能很好处理遮挡问题。遮挡在视频跟踪中时常发生，很多跟踪算法都在尽力解决这个问题。图4(a)显示了上述几个算法在遮挡发生时的跟踪效果。可以看到，Walking2序列中，在241帧的时候，由于跟踪目标和突然闯入的男子都为深色系色衣服，MCPF算法跟踪发生漂移，而其它几个算法都能不受影响准确跟踪到目标。图4(c)的CarScale序列在第172帧发生遮挡后，MCPF和SiamRPN已经跟丢目标，其它算法仍能准确定位到目标，随着目标尺度的变化，本算法的匹配度最高。图4(d)的FaceOcc2发生多次遮挡，所有的算法都能定位到目标的大致位置，但有些算法由于遮挡次数太多，尺度已经不符合目标尺度，而本算法总能匹配目标。图4(e)的Woman序列在第132帧目标路过第1辆汽车时，只有CFNet和本算法能跟踪到目标。

本算法尺度变化和旋转的鲁棒性高。图4(b)～图4(d)显示了旋转时的跟踪结果。图4(b)中David3序列，David从左走到右边，经过了电线杆和树，只有本文算法能持续跟踪到，在第131帧David走到最右边往回走经过树和电线杆之后，仅有本算法和MCPF能准确跟踪到目标。Singer1序列中，受光照、尺度和旋转的影响，所有的算法都能定位到目标位置，但显然本算法的跟踪结果最优，尺度上也最为匹配。图4(d)中的FaceOcc2目标在视频序列除了遮挡之外，目标也发生旋转，如第368帧只有本算法处理了旋转情况。本算法这种表现，归因于在密集采样过程中采用仿射参数进行随机探测，以及采用基于稀疏表示的外观模型建立方案。

本算法在快速移动时能较好跟踪到目标。图4(c)的汽车由远及近，越靠近汽车尺度越大，汽车运行速度越快，本算法在200多帧的时候仍能跟踪到目标，但随着目标的快速移动特别是快驶出界面时，每个算法都无法定位到目标。图4(e)的Woman序列，目标移动过程中经过了很多辆汽车，在564帧附近，跟踪的视频画面突然放大，实验中的所有算法在随后的几帧里都失去了跟踪目标，而本算法能在第578帧的时候又再次定位到目标，是其它几个算法所没有的。本算法较好地处理快速移动，主要是由于采用较为合理的漂移检测和重定位的模型更新方案，结合局部图像块的稀疏表示能在较大范围内检测到目标。

图4 算法在视频序列上的跟踪结果示例

4 结束语

本文提出一种结合核相关滤波和稀疏表示的视频目标跟踪算法，该算法有效利用核相关滤波处理跟踪的高效性和稀疏表示在目标信息表示方面的优势，在保证跟踪器的跟踪准确度和成功率的同时兼顾跟踪器的实时性。本算法在检测到漂移发生后，采取在确定的区域内计算每个局部图像块与模板图像块的相似性，最终实现漂移后再定位跟踪。在OTB100的实验结果表明，本文所提出来的算法具有最高准确度和成功率，在遮挡、旋转和快速移动等方面跟踪效果最好。