0 引言

视觉跟踪是机器视觉的核心问题之一，在人机交互、视频监控、增强现实等领域有广泛的应用。虽然在过去十年里该领域取得了很多进步，但由于光照变化、几何形变、局部遮挡、快速运动、背景嘈杂等因素，对任意模型的跟踪仍然是一个困难的问题。

近年来基于Tracking-by-detection的跟踪由于高效性与精确性而流行。这类方法通常采用一个二值分类器区分被跟踪目标与背景，它也被称为判别式方法。代表性的如Struck(Structured output tracking with kernel)^[1]，采用结构化的支持向量机以直接将目标位置与训练样本相关联。TLD(Tracking-Learning-Detection)^[2]采用了一系列结构性约束，用以集成分类器的采样，重新检测的策略使得TLD方法在一些有挑战性的视频中更具鲁棒性。受压缩感知技术的影响，Zhang等^[3]利用从原始空间投影得到的压缩特征来训练一个朴素贝叶斯分类器，得到压缩感知算法(Compressive Tracking,CT)。多实例学习(Multiple Instance Learning,MIL)^[4]利用了正样本包的概念,采用增强算法构建分类器。

本文提出的算法与相关滤波器跟踪相关，它将传统信号处理技术中的相关滤波概念应用到跟踪领域。Bolme等^[5]提出最小输出平方误差和(Minimum Output Sum of Squared Error,MOSSE)相关滤波器的跟踪方法，对目标外观变化有较强的适应性；Henriques等^[6]提出循环结构跟踪器(Circulant Structure Kernel,CSK)，它利用了循环样本的结构来增加负样本，以提高分类器的效果，它采用了核相关滤波器以实现高效性。基于CSK，核跟踪滤波器(Kernelized Correlation Filter,KCF)^[7]采用了方向梯度直方图(Histogram of oriented Gradient,HoG)特征代替原始像素，同时提高了跟踪器的准确性与鲁棒性。为了更好地增强CSK跟踪器的效果，Danelljan等^[8]采用了颜色空间特征，并且将11维特征降低到2维以提高运行速度。

卷积理论表明，在时域的卷积相当于在傅里叶频域的按元素相乘，因此相关滤波器的本质是通过在傅里叶域计算相关性，以避免耗时的卷积运算。尽管相关滤波器的引入在精确性及鲁棒性上都取得了很好的效果，但是这些以相关滤波器为基础的跟踪器目标模板大小都固定不变，从而不能解决跟踪目标尺度变化的问题。

本文改进了KCF算法。首先利用前向后向法跟踪相邻两帧的特征点，再利用特征点估计目标尺度的变化。其次结合尺度估计，引入可调高斯窗函数，更好地将目标周围的背景与目标相区分，增加了正负样本的准确性。同时利用前向后向法判断目标是否被遮挡，修改了模板更新策略，使得算法更加稳定。

1 KCF跟踪基本原理

KCF的核心思想是用大量的负样本来提高分类器的判别能力，同时运用循环矩阵的结构提升运算效率。

首先在初始帧选定被跟踪的目标，将目标框扩大指定倍数以构建被跟踪区域，用以提供周围的信息，再将被跟踪区域循环位移以近似为对目标周围进行密集采样。通常将样本乘以cos窗函数来消除由于循环位移引起的边缘的不连续。

1.1 样本表示

设初始帧目标框(扩大后)图像块x=[x₁,x₂,…,x_n],给定置换矩阵P，x的循环位移为Px=[x_n,x₁,…,x_n-1]，所有的循环位移样本{x_i=Pⁱx|i=0,1,…,n-1}构成循环矩阵X=[x,Px,…,P^n－1x]^T，循环矩阵^[9]可表示为：

$\mathbf{X}=\mathbf{F}\text{diag}\left( {\mathbf{\hat{x}}} \right){{\mathbf{F}}^{H}}$

(1)

其中：F是离散傅里叶矩阵，$\mathbf{\hat{x}}=\mathbf{Fx}$表示x的离散傅里叶变换，F^H是F的共轭转置。每个循环样本x_i对应分类标签y_i，y_i值服从相对于基样本的距离的高斯分布，范围为[0,1],Y=[y₀,y₁,…,y_n－1]^T。

1.2 分类器训练

利用循环样本学习一个分类器f(x)，通过最小化代价函数以求得w：

$\underset{\text{ }\mathbf{w}}{\mathop{\text{min}}}\,\sum\limits_{i\text{=}0}^{n\text{-}1}{{{\left( f\left( {{\mathbf{x}}_{i}} \right)-{{y}_{i}} \right)}^{2}}+\lambda \left\| \mathbf{w} \right\|}$

(2)

其中：λ是正则化参数，防止过拟合，式(2)也被称为岭回归问题。

当f(x)为线性分类器时，f(x)=w^Tx对式(2)求导得闭式解为：w=(X^TX+λI)^-1X^TY，式(1)代入有${{\mathbf{\hat{w}}}^{*}}=\frac{{{{\mathbf{\hat{x}}}}^{*}}\otimes \mathbf{\hat{y}}}{{{{\mathbf{\hat{x}}}}^{*}}\otimes \mathbf{\hat{x}}+\lambda }$。${{\mathbf{\hat{x}}}^{*}}$表示$\mathbf{\hat{x}}$的复共轭，⊗表示按元素对应(element-wise)相乘,分数表示按元素对应相除。

当f(x)非线性时，可提高分类性能，解决方法为将x映射到高维空间，设为φ(x)，再在高维空间进行分类。由表示理论^[10]，解w可以由映射后的样本的线性组合表示$\mathbf{w}=\sum\limits_{i=0}^{n-1}{{{\alpha }_{i}}\varphi \left( {{\mathbf{x}}_{i}} \right)}$，核函数κ表示x与x′映射到高维空间后的点积φ^T(x)φ(x′)=κ(x,x′)，给定单个测试样本z，分类器的响应为：

$f\left( \mathbf{z} \right)={{\mathbf{w}}^{T}}\mathbf{z}=\sum\nolimits_{i=0}^{n\text{-}1}{{{\alpha }_{i}}\kappa \left( \mathbf{z},{{\mathbf{x}}_{i}} \right)}$

(3)

且α=(Κ+λΙ)^－1Y^[11],其中α=(α₀,α₁,…,α_n－1)^T,Κ为核矩阵，Κ_ij=κ(x_i,x_j)，如果核函数为酉不变的^[6]，Κ为循环矩阵，再次利用(1)可得${{\mathbf{\hat{\alpha }}}^{*}}=\frac{{\mathbf{\hat{y}}}}{{{{\mathbf{\hat{k}}}}^{xx}}+\lambda }$，k^xx表示Κ的第一行。这样将求w转化为求α。

1.3 目标检测

循环矩阵同时被应用到检测中以加速整个过程。在下一帧的同样位置的图像块z被用作检测基样本。将z也进行循环位移，构成循环矩阵，设z_i=Pⁱz，f_i为z_i的响应，设x_t－1为上一帧的更新目标模板，则重写式(3)可得方程组：

${{f}_{i}}=\sum\limits_{j=0}^{n-1}{{{\alpha }_{j}}\kappa \left( {{\mathbf{P}}^{i}}\mathbf{z},{{\mathbf{P}}^{j}}{{\mathbf{x}}_{t-1}} \right);i=0,2,\ldots ,n\text{-}1}$

(4)

定义Κ^z矩阵：Κ_ij^z=κ(Pⁱz,P^jx_t－1)，此也为循环矩阵。式(4)重写为矩阵形式：f(z)=(Κ^z)^Tα，其中f(z)=[f₁,f₂,…,f_n]^T。式(1)代入得$\hat{f}\left( \mathbf{z} \right)={{\left( {{{\mathbf{\hat{k}}}}^{{{x}_{t-1}}z}} \right)}^{*}}\otimes \mathbf{\hat{\alpha }}$,其中k^x_t-1z为Κ^z的第一行。

将$\hat{f}\left( \mathbf{z} \right)$变换回时域，响应最大的值所对应的区域被认为是目标的检测位置，该方法暗含了搜索范围是目标框扩大后的窗口大小，也即实际参与运算的被跟踪区域。整个模型只有两个样本实际参与运算，它们都在上一帧与当前帧同样的位置被采样。

将当前检测到的区域x′同样作循环位移，用相同方法训练分类器参数α_x′,则x_t与α_t的更新过程为：

$\begin{align} & {{\mathbf{x}}_{t}}=\left( 1-\beta \right){{\mathbf{x}}_{t-1}}+\mathbf{{x}'} \\ & {{\mathbf{a}}_{t}}=\left( 1-\beta \right){{\mathbf{a}}_{t-1}}+{{\mathbf{a}}_{{{x}'}}} \\ \end{align}$

其中：β为更新系数；a_t与a_t-1分别为当前帧与上一帧的分类器更新系数；x_t与x_t-1分别为当前帧与上一帧的更新目标模板。

当采用高斯核函数时：

${{\mathbf{k}}^{\text{x{x}'}}}=\text{exp}\left( -\frac{1}{{{\sigma }^{2}}}\left( {{\left\| \mathbf{x} \right\|}^{2}}+{{\left\| {\mathbf{{x}'}} \right\|}^{2}} \right)-2{{\mathbf{F}}^{-1}}\left( \mathbf{\hat{x}}\otimes {{{\mathbf{{\hat{x}}'}}}^{*}} \right) \right)$

其中：F^－1表示逆DFT运算。由于算法只需要内积与离散傅里叶正反变换，计算代价是Ο(n log n)。

2 改进的KCF算法

在KCF跟踪算法中，一个隐含的假设是目标的尺度是固定不变的，这是由于跟踪框大小不变，以及相应的扩大后的被跟踪区域(搜索范围)也大小不变，由于需要作内积运算，所以两个信号的长度应当相等，也即隐含了尺度不变的假设。这是KCF算法的局限性，一般被跟踪目标由于与摄像头的远近或者形变等因素，尺度是变化的，在接下来的帧数中，如果相对于第一帧目标的尺度变小，会使得接下来的训练，让更多的背景信息进入正样本(也即进行循环位移的基样本)；尺度变大，则会使得正样本包含不完整的信息，同时一部分目标信息进入负样本(如当循环位移量为一个完整的目标框大小时所采样的负样本)，这两种情况都会使得采样样本不准确，由此造成分类器训练不准确，并在接下来的分类也即跟踪中形成误差。由此有必要解决尺度变化的问题，具体到几点，由上述的分析可得：1)首先要估计出目标的尺度变化；2)在作内积运算时应当保证信号的长度相等；3)进行后续采样时应当利用估计的尺度变化，使得采样准确。

2.1 尺度估计

一种直观的估计尺度变化的方法如下：

设初始模板大小为A_T(长×宽)，定义一系列的尺度变化值{s₁,s₂,…,s_k}，如可取为{0.9,0.95,1,1.05,1.1}。假设前一帧的模板大小为A_C，将其乘以尺度变化值s_i(i=1,2,…,k)，再将当前帧按s_iA_C大小在相同位置取样，接着采用双线性插值法将取样后的图像块重新调整到A_T大小，然后计算其响应向量。将所有尺度变化后的响应向量串联，然后计算最大响应，则其对应的s_i值为当前帧的尺度变化，s_iA_C即为当前帧的模板大小。在计算目标框中心位移时，同时记得乘上s_i。由于最终进行运算时模板大小调整为固定的A_T，所以更新策略以及进行跟踪与原KCF方法相同，同时解决了作内积运算时需要保证信号长度相同的问题。此方法的优点是思路简单，缺点是尺度变化为固定的离散值，为人工选取，且计算量增大,无法满足实时性要求(帧数过低)。同时在进行插值法调整到A_T大小时，也会使得部分信息丢失或者产生不真实信息，且计算开销也不小。

本文采用另一种尺度估计方法如下：

在TLD中，使用了一种前向后向跟踪方法^[12]，受其启发，另一种尺度更新策略如下：在上一帧的目标框中选择N个像素点(可选取方格点)作为特征点{a₁,a₂,…,a_N}，寻找上一帧的特征点在当前帧中的对应位置，设为{b₁,b₂,…,b_N}，再将跟踪得到的点反向跟踪到上一帧，设为{c₁,c₂,…,c_N}。设每一个点的前向后向跟踪误差为e_i=‖c_i－a_i‖，将e_i小于某一阈值的点保留下来，认为是可信赖的跟踪点。该方法基于这样的假设：正确的跟踪应当与时间流的方向无关，也即时间向前跟踪与向后跟踪，如果跟踪同一点，应当保持一致，如果未保持一致，说明该点不是可靠点，有可能受到遮挡等影响。设有T个可信赖点保留下来，将它们用于尺度估计，可用金字塔Lucas-Kanade光流法^[13]来估计相邻视频帧之间特征点的运动。

进行尺度估计时，设a_i,j=a_i－a_j,b_i,j=b_i－b_j，于是特征点之间的尺度变化分布为D={‖a_i,j‖/‖b_i,j‖,i≠j}，分布的中值s=med(D)可作为尺度的估计。前向后向跟踪算法的前提假设是被跟踪目标是可见的，当目标完全遮挡或者离开当前场景时，跟踪失败，令d_i表示跟踪中某一特征点的位移，即d_i=‖a_i－b_i‖，L={d_i,i=1,…,T}为所有位移的集合，d_m=med(L)表示所有特征点位移的中值，定义某一特征点的位移的残差‖d_i－d_m‖，当其大于某一阈值(如为10)，认为跟踪目标被遮挡。同时注意到，当目标处于遮挡状态时，我们应当停止对模板的更新，也即更新系数β设为0。

2.2 自适应高斯窗

在KCF中作者认为采用cos窗，平滑了由于循环位移导致的图像边缘的不连续。并且被跟踪区域是目标框的2.5倍大小，从而提供了背景信息与额外的负样本。cos窗大小固定，与被跟踪区域相关：cos_window=h(m)×h(n)′，h(x)为汉明窗函数：

$h\left( N \right)=\frac{1}{2}\left( 1-\cos \left( 2\pi i/N \right) \right),0\le i\le N$

通常加窗是为了提取图像的感兴趣部分且在进行DFT计算时减轻频率泄露问题。当目标变小时，cos窗会把目标与背景相混合，如果目标变大，将会丢弃其一部分信息。前文已计算出目标尺度变化，为了更好地将目标与背景相分离，减轻频率泄露，将cos窗替换为可调高斯窗，且高斯函数的傅里叶变换也是高斯函数。

$G\left( m,n,{{\sigma }_{w}},{{\sigma }_{h}} \right)=g\left( m,{{\sigma }_{w}} \right)\times g{{\left( n,{{\sigma }_{h}} \right)}^{\prime }}$

函数g(N,σ)返回一长度为N的向量：

$g\left( N,\sigma \right)=\exp \left( -\frac{1}{2}{{\left( \frac{i}{\sigma \left( N-1 \right)} \right)}^{2}} \right),0\le i\le N$

设目标框大小为W₁×H₁，扩大为被跟踪区域后大小为W×H，二维高斯窗大小为m×n。m与n是被跟踪区域提取特征后的维数，如当使用HOG特征，以4×4为单元格时，m=W/4,n=H/4。在第一帧,初始化高斯窗的带宽参数σ_w=W₁/W，σ_h=H₁/H，在当前帧，计算得到当前尺度变化因子s后，σ_w与σ_h的更新公式为：σ_w=σ_w×s，σ_h=σ_h×s。

这样利用尺度因子，通过引入可调高斯窗，间接地调整了样本采样策略，使得样本的正负信息更加准确。

3 实验评估 3.1 实验环境与参数

本文使用Window7操作系统，处理器AMD A6-5400K(3.6 GHz),4 GB内存，在Matlab上运行，为便于比较，本文使用了与原KCF算法相同的参数设置，学习因子β=0.02，高斯核σ=0.5，正则化参数λ=1E－4，单元格4×4,9方向的HOG特征。

3.2 评估方法

在OTB(Online Object Tracking: a Benchmark)^[14]中，采用两种评估图。

精确度图(precision plot) CLE(Center Location Error)为跟踪结果的中心坐标与人工标定的实际中心坐标之间的欧氏距离，值越小越精确。当CLE小于某一阈值认为跟踪成功(常取20)。precision plot显示了阈值从0变化到50时，视频成功跟踪的帧数占总帧数的百分比变化。

成功率图(success plot) 给定跟踪框r_t与实际的目标框r_a，重叠率定义为$VOR=\frac{\text{area}\left( {{r}_{t}}\bigcap {{r}_{a}} \right)}{\text{area}\left( {{r}_{t}}\bigcup {{r}_{a}} \right)}$，∩与∪分别为两个区域的交集与并集，area表示区域面积，当VOR大于给定阈值(常取0.5)时认为跟踪成功。success plot显示了阈值从0到1变化时，成功跟踪的帧数占总帧数的比率变化。使用曲线下面积(Area Under Curve,AUC)值进行算法评级。采用一次性评估(One-Pass Evaluation，OPE)方式。

所有实验显示结果为所有视频的平均值。

3.3 OTB视频比较

采用OTB的51个标准视频，画出precision plot与success plot，并与算法MIL、Struck、TLD、CSK、MIL、CT等以及原KCF算法相比较。本文算法为SAKCF,评估工具采用OTB提供的工具包^[15]。

首先是51个视频整体比较，如图 1(a)~(b)；同时51个视频中有28个的跟踪目标具有尺度变换属性,如图 1(c)~(d)；同时51个视频中有29个有遮挡属性的视频比较结果，如图 1(e)~(f)。

图 2中，图 2(a)、(d)、(f)是带有尺度变化的视频，从图中可见，改进后的KCF算法较原算法具有了尺度适应能力，跟踪框能随着目标尺度的变化而改变，更好地区分背景和跟踪目标，在训练中减少了背景的干扰，使得正负样本信息更加准确，能够很好地检测位置和尺度。由重叠率的定义可知跟踪框适应目标的尺度变化使得VOR的分子更大(尺度变大时)或者分母更小(尺度变小时)，从而VOR值更大，此为在成功率图中具有尺度变化属性的视频改进明显的原因。图 2(b)、(c)为同一视频下不同的跟踪目标,从图中可见，本文算法在跑步者受到电杆的遮挡后仍能继续跟踪,而其他算法大多跟踪丢失。视频图 2(e)中，玩具受到打火机的遮挡后仍能被跟踪，而原KCF算法由于受到遮挡时间过长，模板仍在更新，当玩具继续移动时，跟踪框停留在原处，导致跟踪目标丢失。

实验结果显示，本文提出算法改进明显，尤其在跟踪目标具有尺度变化属性的视频表现上更为优异。在运行速度上，KCF算法的平均帧率为63.7 frame/s，本文算法帧率为42.8 frame/s，在提高算法精确度与成功率的基础上，并未下降多少，能够满足实时性的要求。

4 结语

针对KCF算法不能很好处理目标跟踪中的尺度变化问题，在其基础上提出了改进的尺度自适应算法。利用前向后向法跟踪特征点，将其用于尺度估计，将得到的尺度估计值运用于高斯窗，更好地将背景与目标相分离，间接地修正了采样策略，特征点同时能够用于遮挡判断。本方法同时避免了大量的运算，在保证帧率的同时提高了算法的准确性与鲁棒性。