基于排名的结构稀疏表示目标跟踪算法*

侯跃恩 李伟光 四库 曾顺星 容爱琼

(1.华南理工大学 机械与汽车工程学院，广东 广州 510640;2.东莞理工学院 机械工程学院，广东 东莞 523808)

视觉目标跟踪技术是目前机器视觉研究的热点之一，该技术已经广泛应用于机器人控制、视频监控、驾驶助理、动作识别和人机交互等领域中.虽然目前有许多视觉目标跟踪算法在一定范围内取得了很好的效果，但仍然存在很多问题有待解决.在被跟踪目标背景、形态、大小和光照条件发生剧烈变化的情况下，对目标的稳定跟踪仍然具有非常大的挑战性［1］.

目前，一种称为稀疏表示的外观建模技术在模式识别领域得到了广泛的应用.文献［2-4］将稀疏表示技术应用在人脸识别过程中并取得了理想的结果.文献［5-6］将稀疏表示引入到目标跟踪领域，并提出了一种琐碎模板，减少了遮挡对跟踪结果的影响，但该方法计算量大，难于胜任复杂的跟踪环境.文献［7］提出了一种结构稀疏表示的方法进行目标跟踪，该方法对模板进行分块表示，提高了跟踪的鲁棒性，并通过分块正交匹配追踪算法(BOMP)减少了稀疏方程的计算量，同时采用增量学习方法更新模板字典，但该方法在目标外形和光照变化强烈的情况下鲁棒性不强.在结构稀疏表示框架下，文献［8］采用对齐合成法对稀疏系数进行处理，以得到各候选目标与目标的相似度，该方法既考虑了目标的全局信息，又考虑了目标的局部性息，具有较高的鲁棒性，但该方法只用到了结构稀疏表示的系数信息，在环境复杂的情况下往往会跟踪失败.文献［9］将增量学习引入到稀疏表示过程中，提高了运算速度和跟踪效果，同时在相似度函数中增加了一个惩罚项减少目标被遮挡对跟踪结果的影响.文献［10］结合稀疏表示和在线外观建模，提高了跟踪算法在复杂环境下的鲁棒性.在稀疏表示框架下，许多基于学习分类的跟踪算法表现出良好的性能.文献［11］将分类器嵌入到稀疏表示过程中，同时在线更新模板字典和分类器，提高了算法的跟踪性能，但该方法只考虑了图像的整体信息，没有涉及图像的局部和空间信息，跟踪准确度有待提高.文献［12］利用现实世界的图像和跟踪结果构成模板字典进行目标跟踪，同时利用基于稀疏表示的分类器区分目标和背景，但该方法实施困难，需要跟踪视频以外的输入信息.文献［13］用分类器训练一个映射矩阵，通过该映射矩阵选取区分度高的图像特征，同时利用结构稀疏系数直方图构建相似度函数，提高了跟踪的准确度.在结构稀疏表示框架下，文献［14］通过稀疏系数训练线性分类器，并提出了一种基于目标信息和观察目标信息的两步定位算法，在一定程度上解决了跟踪漂移的问题，但该算法的运算量较大，在目标形态和光照变化剧烈的情况下容易丢失目标.

针对目前跟踪算法在环境复杂的情况下鲁棒性不高的问题，文中在结构稀疏表示框架下，提出了一种新的目标跟踪算法.算法通过对结构稀疏表示系数和残差得分进行排名的方式获得各候选目标的相似度信息，提高了跟踪算法在复杂环境下的鲁棒性和准确度，同时没有增加额外的计算量.

1 目标跟踪算法研究

文中提出的目标跟踪算法原理见图1.与其他算法相比，文中的算法有以下特点:

(1)算法通过对稀疏系数和残差信息对目标的相关度进行排名，采用排名方式使候选目标各分块更具可比性，有效融合了稀疏系数和残差信息，采用自然对数对排名信息进行处理，减少了遮挡和噪声的影响，提高了跟踪算法鲁棒性.

(2)文中构造了一种融合目标信息和背景信息的稀疏表示模板字典，提出了一种融合背景和目标信息的残差得分代替纯粹的残差信息，使跟踪算法能更好地区分目标和背景，增加了跟踪的准确度.

图1 跟踪算法原理Fig.1 Principle of tracking algorithm

1.1 结构稀疏表示

与传统稀疏表示相比［6］，结构稀疏表示不仅包含了目标的全局信息，还包含了目标的局部信息和空间信息，具有更高的跟踪鲁棒性［7-8，11，13］.

文中在结构稀疏表示的基础上，提出了一种含有目标模板和背景模板的模板字典.在初始帧，假设初始帧真实目标中心坐标为o，则目标模板的中心坐标Itar在一个半径为r1的圆形区域内采用高斯分布随机获得，即|Itar-o| ＜r1，而背景模板的中心坐标Ibg在一个内径为r1、外径为r2的圆环区域内采用高斯分布随机获得，即r1＜|Ibg-o| ＜r2.

假设T 为有n1个模板的目标模板集，T =［t1t2… tn1］，B 为有n2个模板的背景模板集，B =［b1b2… bn2］，T 和B 构成文中的稀疏表示模板字典［T，B］，［T，B］∈Rm×n，m 为每个模板的维数，n=n1+n2，为字典里模板数量.采用文献［8］的方法对模板进行分块处理，可以得到分块模板字典D=［DtarDbg］，其中，Dtar为模板字典目标模板部分，Dbg为模板字典背景模板部分，为模板字典第i 个模板第j 个分块，k 为每个模板分块的数量.候选目标Y∈Rm×1，采用同样的处理方式，可得k 个分块(y1，y2，…，yk).分块yi可用D 稀疏表示为

式(1)是1 范数最小化问题，有较大的计算量，为提高计算速度，文中用2 范数最小化来进行稀疏表示，文献［4］通过试验证明，在稀疏表示模式识别过程中，2 范数最小化和1 范数最小化有几乎一样的识别结果.

由式(2)可以得出:

1.2 稀疏系数排名算法

在结构稀疏表示框架下，候选目标Y 的稀疏系数为A = (a1，a2，…，ak)T，其中ai= (，，…，)，ai为第i 个分块yi的系数.如果Y 是真实目标，则ai中会获得较大值，因为这些系数与yi相对应.设ci=++，…，+，则整个样本Y 能够得到矩阵C =［c1c2… ck］T∈Rk×1.假设算法每帧共有N 个候选目标，可以获得矩阵F =［C1C2… CN］∈Rk×N，将矩阵F 每个行向量从大到小排名，得到每个元素在该行的名次，组成一个排名矩阵G∈Rk×N，将G 的每个元素进行自然对数运算，并对每个列向量相加，得到各候选目标系数总名次向量H =(H1，H2，…，HN)T∈R1×N.

图2 结构稀疏表示系数排名算法原理Fig.2 Principle of structured sparse representation ranking algorithm

1.3 残差得分排名算法

在目标跟踪过程中，为了更好地区别目标和背景，文中提出了一种残差得分.通过对各候选目标的残差得分进行排名，可以与系数排名共同确定目标的状态.

yi的残差由两部分组成，第1 部分为与其位置对应的目标模板线性组合的残差ζi，第2 部分为与其位置不对应的目标模板和背景模板线性组合的残差εi.

第1 部分残差为

第2 部分残差为

式中，σi=yi-aiD.

文中定义样本Y 的第i 个分块的残差得分Si为

可以看出，Si不仅包含了与分块位置对应的目标信息，还包含了背景和位置不对应的目标信息，可以使跟踪算法更好地区分目标和背景，定位精度更高.如果Y 是真实目标，则Si获得一个较大的值，如果Y 不是真实目标，则Si获得一个较小的值.

与上节计算G 与H 一样，算法对每个候选目标各分块残差得分排名，可获得残差得分排名矩阵PRk×N和残差总名次向量Q =(Q1，Q2，…，QN)∈R1×N.

1.4 跟踪算法

文中在粒子滤波框架下对目标进行跟踪，第1 帧初始状态采用鼠标点取获得.设z1，z2，…，zt为第1 帧到第t 帧的目标观测状态.xit为第t 帧第i 个候选目标状态.则第t 帧的目标状态xt为

式中，z1:t为目标第1 帧到第t 帧的观测值，p(xt|z1:t)可由下式得到:

式中，p(zt|xt)是相似度变量，p(xt|xt-1)是状态转移变量，文中采用6 维仿射变换(ε1，ε2，ε3，ε4，ε5，ε6)定义目标的状态xt，分别代表x 轴坐标、y 轴坐标、旋转角、尺度、长宽比和扭角［15］.假设这6 个参数相互独立，都服从高斯分布，则状态转移变量可以表示为

式中，Σ 为方差对角矩阵.

文中的相似性函数与系数总名次和残差总名次的关系为

文中采用稀疏表示和增量学习相结合的方法更新模板字典的目标模板，具体参见文献［8］.

在每次更新目标模板的时候，同时用新得到的背景替代原来的背景模板.

文中算法的流程归纳如下.

输入:①视频，②首帧目标状态

获得初始背景模板和目标模板构成对象字典

for(f=1:T)，T 为视频的帧数

粒子更新，仿射变换

结构稀疏表示各候选目标

计算系数总名次向量H

计算残差总名次向量Q

利用式(12)计算各候选目标相似度函数

if(符合模板字典更新条件)

目标模板更新［8］

背景模板更新

end if

end for

输出:各帧目标状态

2 目标跟踪试验

文中在主频为2.4 GHz、内存为2 GB 的计算机上用Matlab2009b 对算法进行验证.为证明文中算法的先进性，在5 个具有挑战性的视频上将4 种先进的跟踪算法与文中算法进行比较，它们分别是ℓ1跟踪算法［6］、SCM 算法［13］、ASLSAM 算法［8］和IVT 算法［16］

文中将目标区域通过仿射变化映射到32 ×32的矩阵上，设为0.01［8］，粒子数设为600［6，8，13，16］，每个样本分为9 个分块，相邻分块一半面积重叠［8］，模板字典中，目标模板和背景模板数均为30.

2.1 试验结果

试验采用白色实线框表示文中算法结果，用黑色虚线框表示ℓ1算法结果，用白色虚线框表示ASLSAM 算法的结果，用黑色实线框表示SCM 算法的结果，用黑色点虚线框表示IVT 算法的结果.

第1 个测试视频是ThreePastShop2cor(TPS)，该视频的主要挑战是目标遮挡和相似目标干扰，试验中Σ =［5，5，0.01，0，0.001，0］.试验结果如图3 所示，可以看出，文中算法与SCM 算法可以完成对整个视频的跟踪，而ℓ1算法、ASLSAM 算法和IVT 算法都受到了遮挡或相似目标的影响而偏离了实际目标.

第2 个测试视频是Woman Sequence(WS)，目标被遮挡和复杂的背景是该视频的主要挑战.试验中Σ 设为［4，4，0.02，0，0，0］.从图4 可以看出，文中算法与SCM 算法能够完成对整个视频的跟踪，而ℓ1算法、ASLSAM 算法和IVT 算法在目标被遮挡时失去了目标.

第3 个视频是Panda，视频中，目标受到了严重的遮挡，同时发生了大幅度的旋转，Σ 值为［10，10，0.01，0.18，0，0］.图5 是视频的试验结果，文中算法完成了整个视频的跟踪，SCM 算法在目标发生大幅度旋转时丢失了目标，ℓ1、ASLSAM 和IVT 跟踪算法在目标被遮挡时丢失了目标.

图3 视频TPS 的跟踪结果Fig.3 Tracking results of TPS

图4 视频WS 的跟踪结果Fig.4 Tracking results of WS

图5 视频Panda 跟踪结果Fig.5 Tracking results of Panda

第4 个测试视频是Trellis，视频的主要难点是光照的变化和目标形态的变化，实验中Σ 值为［5，5，0.02，0，0.002，0.001］.图6 是视频的试验结果，文中算法、SCM 和ASLSAM 算法在第422 帧由于光照和目标形态的变化丢失了目标，但文中算法能恢复对目标的跟踪，而另外两个算法无法恢复.ℓ1和IVT 算法在228 帧由于光照的变化丢失了目标.

第5 个视频是Shaking，视频的主要挑战是强烈光照变化和目标形态变化.Σ 值为［10，10，0.01，0，0，0.001］，从图7 可以看出，文中算法可以完成对整个视频跟踪，而其他算法由于光照和目标形态变化强烈在跟踪过程中失去了目标.

图6 视频Trellis 的跟踪结果Fig.6 Tracking results of Trellis

图7 视频Shaking 的跟踪结果Fig.7 Tracking results of Shaking

2.2 结果分析

首先对跟踪误差进行分析，这里对跟踪误差的定义是实际目标中点到跟踪结果中点的欧氏距离.图8 为5 种跟踪算法在5 个视频上的跟踪误差图.从图中可以看出，与其他算法相比，文中算法在视频Panda、Trellis 和Shaking 中获得了最好的跟踪结果.在视频ThreePastShop2cor 和Woman Sequence 中，文中算法与SCM 跟踪算法都获得了较好的跟踪结果.

为进一步说明问题，文中对各个算法的跟踪误差最大值、平均值和标准方差进行统计，统计结果见表1，表中加粗下划线的数据为比较中最好结果，加粗斜体数据为比较中第二好结果.从表中可以看出，文中算法除了在视频ThreePastShop2cor 和Woman Sequence 的最大值比较中取得第二好的结果外，在其他的比较中均获得了最好的结果.在5 个视频平均值比较中，文中算法获得了最好的结果.

表1 跟踪误差的最大值、平均值和标准方差Table 1 Maximum，mean and standard variance values of the location error

由于跟踪误差只是反映了跟踪结果和实际目标中心点的距离，并没有反映出跟踪结果形状与实际目标形状的关系，文中采用PASCAL VOC 标准［16］对跟踪成功率进行评估:

式中，Wt是跟踪结果，Wg是目标的实际状态，Z 表示面积.如果某帧的R 大于等于0.5，那么认为该帧跟踪成功，否则认为跟踪失败.

图8 5 种跟踪算法的跟踪误差比较Fig.8 Comparison of location errors of 5 trackers

表2 列出了各跟踪算法的跟踪成功率，可以看出，文中算法在全部比较中均有最高成功率.

表2 各跟踪算法成功率Table 2 Success rate of tracking algorithms

除了跟踪误差和成功率，跟踪帧频也是算法的重要指标，IVT 算法帧频最高，为6.58 帧/s，文中算法与ASLSAM 算法帧频分别为4.06 帧/s 和4.20 帧/s，而SCM 算法和ℓ1算法实时性较差，帧频分别为0.47 帧/s 和0.30 帧/s.可见文中算法在提高跟踪鲁棒性和准确性的基础上没有增加计算量.

3 结语

文中在粒子滤波和结构稀疏表示框架下，提出了一种新的目标跟踪算法.该算法结合目标和背景信息的残差得分，使跟踪算法能更好地区分目标和背景信息.文中提出的基于稀疏系数和残差得分排名的方法，使稀疏系数和残差能更有效地融合，同时对目标的遮挡和噪声干扰更具鲁棒性.在试验部分，将文中算法与ℓ1算法、SCM 算法、ASLSAM 算法和IVT 算法进行比较.试验结果表明，文中算法在目标光照、形态变化和目标被遮挡时具有更好的跟踪效果.然而，文中算法只适用于目标没有长时间离开视野的情况，同时在特别复杂的环境下，文中算法会出现丢失目标的情况.未来工作将围绕这些不足进行深入研究.

［1］Yilmaz A，Javed O，Shah M.Object tracking:a survey［J］.ACM Computing Surveys，2006，38(4):1158-1166.

［2］Wright J，Yang Allen Y，Arvind G，et al.Robust face recognition via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(2):210-227.

［3］Zhang L，Yang M，Feng X C.Sparse representation or collaborative representation:which helps face recognition［C］∥IEEE International Conference on Computer Vision.Barcelona:IEEE，2011:471-478.

［4］Yang M，Zhang L，Zhang D，et al.Relaxed collaborative representation for pattern classification［C］∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Providence:IEEE，2012:2224-2231.

［5］Mei X，Ling H B.Robust visual tracking and vehicle classification via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(11):2259-2272.

［6］Mei X，Ling H B.Robust visual tracking using ℓ1minimization［C］∥Proceedings of 2009 IEEE 12th International Conference on Computer Vision.Kyoto:IEEE，2009:1436-1443.

［7］Bai T X，Li Y F.Robust visual tracking with structured sparse representation appearance model［J］.Pattern Recognition，2012，45(6):2390-2404.

［8］Xu J，Lu H C，Yang M H.Visual tracking via adaptive structural local sparse appearance model［C］∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Providence:IEEE，2012:1822-1829.

［9］Wang D，Lu H C，Yang M H.Online object tracking with sparse prototypes［J］.IEEE Transactions of Image Processing，2013，22(1):314-325.

［10］Chen F，Wang Q，Wang S，et al.Object tracking via appearance modeling and sparse representation［J］.Image and Vision Computing，2011，29(11):787-796.

［11］Bai T X，Li Y F，Zhou X L.Discriminative sparse representation for online visual object tracking ［C］∥Proceedings of the 2012 International Conference on Robotics and Biomimetics.Guangzhou:IEEE，2012:79-84.

［12］Wang Q，Chen F，Yang J M，et al.Transferring visual prior for online object tracking［J］.IEEE Transactions on Image Processing，2012，21(7):3296-3350.

［13］Zhong W，Lu H C，Yang M H.Robust object tracking via sparsity-based collaborative model［C］∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Providence:IEEE，2012:1838-1845.

［14］Wang Q，Chen F，Xu W L，et al.Online discriminative object tracking with local sparse representation［C］∥Proceedings of IEEE Workshop on Applications of Computer Vision.Breckenridge:IEEE，2012:425-432.

［15］Li M，Tan T N，Chen W，et al.Efficient object tracking by incremental self-tuning particle filtering on the affine group ［J］.IEEE Transactions on Image Processing，2012，21(3):1298-1313.

［16］Ross David A，Lim J，Lin R S，et al.Incremental learning for robust visual tracking ［J］.International Journal of Computer Vision，2008，77(1/2/3):125-141.

［17］Everingham M，Gool L V，Williams C，et al.The pascal visual object classes (voc)challenge［J］.International Journal of Computer Vision，2010，88(2):303-338.