基于核相关滤波器的尺度自适应追踪算法*

时鹏飞,高清维,卢一相,孙 冬

(安徽大学 电气工程与自动化学院，安徽 合肥 230000)

0 引 言

目标追踪是机器视觉中最重要的任务之一。近年来，目标追踪算法已广泛应用于各种应用，比如自动跟车系统以及智能监控等。使用计算机进行自动追踪一直都是一项复杂的工作。但是，由于其日益增长的重要性，目前已进行了大量的研究寻求更加快速准确的追踪算法，比如均值漂移(mean shift)算法[1]、粒子滤波(particle filtering)追踪算法[2]以及增量视觉追踪(incremental visual tracking)算法[3]和时空上下文(spatio-temporal context)追踪算法[4]。总体来说，追踪算法可以分为两大类，即生成式方法[5]和判别式方法[6]。生成式方法通过提取目标中的某些特性来建立一个目标模型，然后通过比较模型与各候选目标之间的距离或相似性来确定被追踪目标在下一帧中的位置；而判别式方法通过训练一个分类器直接将目标从背景之中分离出来。

近年来，大量基于判别式的相关滤波器(discriminative correlation filter，DCF)被提出并成功应用于目标追踪[7,8]。DCF的原型是一个由Bolme等人于2010年提出的MOSSE(minimum output sum of squared error)的追踪器[9]。该追踪器通过将一个训练好的滤波器与视频帧进行相关操作，找出视频帧中与滤波器最为相似的部分。由于相关滤波器(correlation filter，CF)实现的简易性和结果的准确性以及运算的快速性，使此类追踪算法已经成为目标追踪领域中最受欢迎的方法之一[10,11]。

但相关滤波器仍然存在很大的进步空间。Henriques J F等人[6]将循环矩阵的思想注入相关滤波器，从而增加了训练集样本的数量，但是同时使训练时间保持在原来的水平上。一些现代的图像特征如方向梯度直方图(histogram of oriented gradients，HOG)等也被应用于相关滤波[11]，从而使滤波器能够应对光照变化等各种不利因素。相关滤波器是将滤波结果的最大值所在处视为目标的新位置的，而一些局部的极值点会削弱追踪器的健壮性。因此Mueller M等人[12]通过抑制最大值周围的其它极值点，使得目标与背景之间的差异更加明显化。

核相关滤波器[11]是相关滤波器的一个改进版本，它使用了岭回归而不是相关算子来解决追踪问题。为了增加算法的健壮性与快速性，核方法与循环矩阵也被应用到了算法之中。虽然KCF表现出了极佳的特点，但是它却仍不能够应对尺度变化带来的问题。为此，本文将提出一个应对此问题的解决方法。

1 核相关滤波器

1.1 岭回归

岭回归使用线性函数f(z)=wTz将训练样本z映射为一个标量f(z)，使得映射后的样本与其标签之间的距离能够最小化。同时，应该避免数据过拟合

(1)

这里的xi为一个训练样本，yi为其对应的标签。λ为一个用来控制过拟合的惩罚因子。如果将所有的样本表述为一个矩阵X，X的每一行都是一个样本，而将所有的标签表述为一个列向量y，则优化公式最小化变量的解可由下式给出

w=(XHX+λI)-1XHy

(2)

1.2 循环矩阵

循环矩阵是由一个基本信号不断变换产生的。基本信号每次循环平移一个位置产生一系列新的信号,将这些信号按生成顺序拼接在一起，就组成了一个循环矩阵。为简化原理分析过程，这里将使用一维单通道信号进行推导。

假定基本信号x是一个大小为N×1的列向量，则其循环平移的过程可以使用一个大小为N×N的交换矩阵P来描述。P是由一个单位矩阵不断进行初等行变换得到的。单位阵的最后一行不断地与其上面的行进行交换，一直达到最顶部。而乘积Px是对x进行的相同变换，x的最后一个值升到首位而其它值都下降一位。第i个样本可由xi=Pix生成。Pi是一个以N为周期的函数，即包含基本信号在内，一共有N个不同的信号可以用作训练样本。因此，样本矩阵X可以写作下式

(3)

式中X为由基本信号x生成的循环矩阵。从文献[13]中可以查到循环矩阵的很多性质，其中一条是循环矩阵总是可以对角化的

(4)

(5)

循环矩阵的另一个特性表现在矩阵乘法上。在向量y的元素都是实数时，循环矩阵X与y的乘积Xy与y和x的圆周相关是等价的。利用傅里叶变换的性质，公式中的w可以在频域中求解出来

(6)

1.3 核方法

使用一个核函数φ将训练样本xi映射至高维空间的φ(xi)，而滤波器w可视为所有映射后样本的线性组合

w=ΦT(X)α

(7)

这里的α=[α0,α1,α2,…，αN-1]T，而Φ(X)中的每一行都是一个高维的输入。求解出对偶变量α为

α=(K+λI)-1y

(8)

这里K=ΦT(X)ΦT(X)，K中的每一个元素都是两个映射后向量的内积,Kij=φT(xi)φ(xj)。可以利用核技巧在低维空间中计算两个高维样本的内积。选取合适的函数可以使K+λI成为一个循环矩阵，而高斯核κ(xi,xj)=exp(-‖xi-xj‖2/σ2)正好可以满足此条件

(9)

(10)

式中kxx为矩阵K的第一行。在求解α的过程中利用了对称序列傅里叶变换的性质去除了分母的共轭。

在检测阶段，需要计算所有候选位置的与滤波器的相关响应。幸运的是，所有候选目标的响应可以同时被计算出来

f(Z)=(Kz)Tα

(11)

其中,Kz=Φ(Z)ΦT(Z)=C(kxz)，等式与圆周卷积有着相同的意义，这意味着它可以很容易地在频域中进行求解

(12)

目标在当前帧中的预测位置为响应在时域中的最大值所在处。确定了新位置后，就可以为对偶变量和目标模型进行更新以应对下一次迭代。

2 尺度估计

尺度变化一直都是目标追踪中的一个难解决的问题。如粒子滤波[2]这样本身就包含尺度信息的追踪器是很稀少的。大多数的追踪器都没有能力处理尺度问题，还有一些算法使用暴力搜索来确定尺度大小。Danelljan M等人[14]设计了另外一种用在标准DCF上进行尺度估计的方法，基于尺度变化要比位移小的假设，在大多数的现实情况中都是可以满足的。在此假设下，追踪问题可以拆分为位移变化与尺度变化两部分。第一部分应对位移，由标准KCF完成,在此部分中，尺度保持不变。第二部分应对尺度，在上一部分中获得的位移中心周围，这里提取出一些尺度样本，然后在尺度样本上运行一个一维的核相关滤波器。图1是一个尺度提取的演示。中间的矩形为目标在上一帧中预测的大小，而其它的矩形代表在其周围提取的尺度样本。

图1 尺度样本提取

假设在上一帧中目标的尺度大小被估计为M×N，其中心点被标记为P。这里在新帧的P点周围提取S个尺度，并使用一个相应的余弦窗口与之相乘以降低边缘区域的重要性。尺度图像块IPn的大小为anM×anN。a是一个比1稍大的实数，而n是一个整数，其范围从-(S-1)/2到+(S-1)/2。如果设定a=1.02和S=33，那么尺度因子an就被具体到0.728 4～1.372 8之间。

当尺度信息被确定后，它就可以加入到位移滤波器中对目标模型进行更新。因为取样的图像块大小与目标模型的大小是不一定相同的，所以应将所有的图像块缩放到一个标准的大小。在更新了尺度模型后，算法即可以开始进行下一次迭代，其具体的流程被描绘在算法1中。

算法1 尺度估计的一次迭代过程

输入:

图像帧It，当前目标位置Pt，上次的尺度大小M×N

输出：

估计的尺度大小St

特征提取：

1)for 每一个尺度sdo

2)在图像It的点周围提取一个大小为sM×sN的图像块

3)将图像块缩放至标准大小M0×N0

4)对缩放后的图像块提取HOG特征

5)将特征拉成一个列向量,为列向量添加余弦窗

6)end for

7)将所有向量整合为一个矩阵

8)将矩阵的每一行变换到频域

尺度检测:

9)使用等式计算互相关

10)在频域中将互相关的各列相加

11)使用等式和等式计算对偶变量和响应

12)在时域中查找响应的最大值并设定当前尺度St

13)对滤波器的目标模型进行更新

3 实 验

测试样本是来自OTB[15,16]基准库的60个视频序列。这些序列包含了快速运动、遮挡、背景杂乱和尺度变化等各种挑战因素。这里使用两个分别叫做距离精度(distance precision，DP)和交叉精度(overlap precision，OP)的准则来表示追踪器的准确性。DP表现了目标中心与估计中心之间的距离，而OP是目标区域与估计区域相交面积与相并面积之间的比值。二者都随着追踪器精度的增加而增加。

表1为CSK，DSST，KCF以及本文追踪器的对比结果。与标准KCF相比，本文算法在距离精度和交叉精度上都要略胜一筹。标准KCF追踪器在位置估计上很准确，而DSST在尺度估计上更好。本文结合了二者的优点，在位置与尺度上都能较为准确地给出估计。但是与标准KCF相比，算法在运行速度上急剧下降。其主要的时间消耗在尺度样本采集上，包括图像块缩放与特征提取。CSK是其中运行速度最快的，因为它只考虑了图像的亮度信息并没有解决尺度问题，结果是其表现在两个准则上都不理想。与标准KCF相比，本文算法在距离精度上略有优势，而在表现尺度效果的交叉精度上，优势便显示得更加明显。

表1 实验结果

图2为2种算法的距离精度图和交叉精度图。

图2 距离精度图和交叉精度图

由图2可见本文算法在二者中的表现都很不错。弧下面积(area under the curve，AUC)是另外一个用来表现追踪效果的指标，它也随着追踪效果的增加而增加，其数值被标注在交叉精度图的图例中。标准KCF的获得的AUC分数为0.536 9，DSST由于使用了尺度信息获得的分数比KCF更高，为0.561 3分。然而，本文的追踪器进一步提升了追踪效果，使分数达到了0.580 0。

图3提供了一些追踪结果的例子，分别对应光照变化，平面外旋转，杂乱背景以及遮挡等各种干扰因子。相较于其它的算法，本文算法可以更有效地抵制各种不利因素，实现更加准确的追踪效果。

图3 在部分序列上的追踪效果

4 结 论

通过添加一个额外的核相关滤波器，可以实现对目标尺度变化的有力应对。此算法在中心距离和交叉面积两方面都优于标准核相关滤波器。若使用传统方法，则需要在每一个尺度上都进行一次标准KCF算法，这会使算法的处理时长增加至大约S倍。但本文算法仅用8倍时间就处理了33个尺度。实验结果表明:本文算法可以有效地处理尺度变化带来的问题。