融合背景信息的分块稀疏表示跟踪算法*

侯跃恩 李伟光 容爱琼 叶国强

(华南理工大学机械与汽车工程学院，广东广州510640)

视频目标跟踪在视觉伺服、视频监控和人机交互等领域得到了广泛的应用，许多学者在目标跟踪领域做了大量的研究，但仍有很多问题没有得到解决［1］，这些问题主要集中在光照条件剧烈变化、目标形态变化和目标被遮挡的情况下的跟踪准确性、鲁棒性和实时性上．近年来，一种被称为“稀疏表示”的外观建模技术在多扰动下目标匹配过程中显示出了强鲁棒性．文献［2］中应用该技术在灰度图像中对现实世界的物体进行识别，获得了极高的识别率．文献［3-5］中将人脸识别看成是稀疏表示的过程，获得了良好的识别效果．文献［6］中将稀疏表示方法用于图像降噪，取得了理想的效果．为解决复杂条件下跟踪鲁棒性的问题，文献［7-8］中将稀疏表示引入目标跟踪领域，采用ℓ1最小化的方法线性表示目标，并用琐碎模板的方法解决目标被遮挡的问题，但该方法存在计算量大和跟踪实时性差的问题．文献［9］中在解稀疏矩阵时采用了分块正交匹配追踪(BOMP)算法，提高了算法的运算速度，但由于没有考虑背景信息，在目标光照条件和形态剧烈变化的时候会出现漂移的现象．文献［10］中采用新方法使稀疏表示在粒子滤波框架中只需要进行一次稀疏计算，大大减少了算法计算量，但该方法模板单一，失去了稀疏表示的鲁棒性．为了提高跟踪的鲁棒性，文献［11］中采用多种特征对目标进行稀疏表示，但该方法没有对特征融合深入分析，只是简单地融合各种特征，同时还存在实时性不高的问题．文献［12］中采用外观模型和稀疏表示的方法对目标进行跟踪，取得了良好的跟踪效果，但没有对跟踪的帧频展开论述，同样存在实时性不强的问题．文献［13］中采用SIFT特征以及 ℓ1和 ℓ2最小化提高了跟踪的鲁棒性，却带来了额外的计算开销．

针对上述问题，文中提出一种新的基于稀疏表示的目标跟踪方法，该方法在提高跟踪鲁棒性的基础上保证了跟踪的速度．

1 算法研究

1．1 粒子筛选方法

在粒子滤波框架下，大部分粒子与目标的相似度较低，这些粒子对确定目标的贡献基本为零，它们可以用快速的计算予以区分．鉴于此，提出了一种快速计算的方法来筛选这些粒子，以减少算法的计算量，这里称为“方差粒子筛选法”．

设 Y={y1，y2，…，yk}∈m×n为粒子滤波中的候选粒子集，其中m为粒子特征的维数，n为粒子数．˜Y∈m为标准模板．将Y的每个列向量与˜Y进行归一化并相除得到 U={u1，u2，…，un}∈m×n，其中中每个列向量包含了候选目标与标准模板的相似度信息，粒子筛选的目的就是根据U中的信息寻找与标准模板相似度高的粒子参与后面的运算．现以ui为例，如果候选目标与模板相似度高，则ui内各元素数值波动小，反之，ui内各元素数值波动大．可以用ui内各元素的波动大小来判断候选目标与模板的相似度，这里采用方差来定量计算各元素波动的大小．因此，模板筛选工作的重点就是寻找矩阵U中方差大的列向量．在图像被遮挡或噪声比较大的情况下，与模板相似度高的粒子可能会出现方差大的现象．为了解决这个问题，排除ui中部分与其均值差值较大的元素，这些元素可能是由遮挡或噪声导致，从而避免目标被排除的情况．至于˜Y的选取，在初始帧由手动选择获得，在跟踪过程中，由模板更新的方法获得，关于模板更新将在1．4 节介绍．

1．2 目标与背景联合稀疏表示算法

为了表述方便，这里先简要介绍稀疏表示原理．假设有一模板字典T={t1，t2…tk}∈m×k，其中m 为每个模板的维数，k为模板的个数．模板字典如图1所示．

图1 模板字典Fig．1 Template dictionary

候选目标特征向量为y∈m，则y可以用模板字典T的各个列向量线性表示:

式中，α∈m，是目标的参数向量，ε是残差．稀疏表示就是用尽量少的向量线性表示y，即

式中，‖·‖2、‖·‖0分别表示2范数和0范数，为残差与稀疏性之间的调节系数．文献［8］中指出，如果解α足够稀疏，ℓ0最小化问题可以等价于ℓ1最小化问题，即

式中，‖·‖1为1范数．文献［4］中用实验证明了用ℓ1或ℓ2对系数α进行稀疏性约束可以得到同样的识别结果，由此可以得到

用ℓ2对系数α进行稀疏性约束的好处是可以使计算量大大减少．

由式(4)可导出:

设P=(TTT+I)-1TT，则P只与模板字典有关，在目标跟踪过程中，每帧只需计算一次即可，可以减少运算量．

在目标跟踪过程中，由于模板数k有限，文中提出一种将背景信息融入模板字典的方法，一方面可以组成较完备的模板字典，另一方面由于融入了背景的信息，可以使跟踪更具鲁棒性．设模板字典T={Ttar，Tbg}，其中 Ttar∈m×k1为目标模板部分，Tbg∈m×k2为背景模板部分，k1为目标模板个数，k2为背景模板个数，且k1+k2=k，模板字典示意见图1．在ℓ2范数稀疏约束的基础上，

式中，αtar、αbg分别为目标模板和背景模板对应的系数．目标模板部分的残差 εtar= ‖y-Ttarαtar‖2，背景部分的残差 εbg=‖y-Tbgαbg‖2，如果候选目标 y与目标的相似度高，则εtar的值小而εbg的值大，反之则εtar的值大而εbg的值小．令目标与背景残差比e=εtar/εbg，则

式中，ei为k个粒子中第i个粒子的值，C为最终的确定目标的粒子序号．因此文中判断候选目标与目标的相似度时不仅考虑到了目标模板的信息，还考虑到了背景模板的信息．

1．3 图像分块权重表示

为了解决跟踪过程中目标被遮挡的问题，使用分块稀疏表示的方法．该方法将目标图像分块，并给每个分块赋予不同的权重，当目标某个分块被遮挡或被噪声干扰时，该分块被赋予的权重低，对整体稀疏解的贡献小．

文献［5］中指出，在稀疏表示过程中，同一个候选目标的不同分块有一定的相似性．如果只考虑目标模板，则它们具有相似的参数向量．当目标部分被遮挡或存在噪声干扰时，该部分与其他部分的相似性将被打破，导致跟踪任务的失败．为了避免这种情况，可以用下式规范其相似性:

式(8)中，L为图像的块数，α为所有分块系数向量的均值向量，ωl为第l块图像的权重，式(9)为权重ω的约束．结合式(4)，权重分块稀疏解的问题可以用以下方程表示:

式中，yl为候选目标第l个分块，为调节系数，^Tl为目标模板中第l个分块．可见该问题可以看成是求解αl和ωl使式(10)取得最小值，这里采用迭代的方法进行求解．

首先，假设所有分块的权重已知，由式(10)可以得出［5］:

算法1:分块权重迭代算法

3．根据式(11)更新稀疏解系数αl

4．根据式(12)更新权重系数ωl

5．end while

6．输出 ωl，l=1，2，…，L

在获得各个分块的权重后，加入背景模板组成模板字典，式(5)和(7)可以改写为

式(14)中，el为第l个分块的目标与背景残差比，εtar，l，εbg，l分别是第 l个分块目标模板部分和背景模板部分残差．式(15)中，ei，l为第i个粒子中第l个分块的目标与背景残差比．

1．4 模板更新

(1)标准模板˜Y的更新

在文中算法中，˜Y的更新对粒子筛选成败有着重要的作用．

最直观的方法是用每帧得到的目标对Y进行更新．如果使用这种方法，当跟踪出现漂移的时候，会导致更新任务的失败．文中在使用每帧目标对˜Y进行更新的基础上，保留初始帧产生的标准模板Yinit．这样就会有两个标准模板Y和Yinit，再用1．1节的方法筛选粒子，得到与Y和Yinit相似性高的粒子．这样做的好处是在某帧目标出现漂移的时候，Y筛选掉了与目标相似性高的粒子，Yinit则保留了与目标相似性高的粒子，使跟踪能够顺利进行．

(2)模板字典T的更新

如2．2节所述，文中的模板字典(T={Ttar，Tbg})包括了两方面的内容，分别是目标模板字典Ttar和背景模板字典Tbg．

目标模板字典Ttar的更新采用文献［8］中的方法进行．背景模板字典Tbg则采用1．1节中与目标相似度最低的k2个粒子进行更新．

1．5 算法总结

除了上文讨论过的几个问题，算法采用仿射变换原理［14］将目标区域映射到一个固定维数的矩形框中，无论目标的大小如何变化，算法的计算量都将保持不变．在粒子滤波框架下利用粒子的速度和高斯分布噪声更新粒子［14］．图2为算法原理图，跟踪算法见算法2，算法的输入为视频和首帧的目标状态，输出为各帧目标的状态．

1．6 计算量分析

文中算法主要通过两部分的算法改进，减轻了计算负担，分别是粒子筛选和ℓ2最小化的稀疏解．粒子筛选算法通过快速计算可以排除掉大部分与目标相似度低的粒子，在解稀疏方程的过程中，ℓ2最小化的计算量远远小于ℓ1最小化．文中主要的计算开销在于权重求解的迭代，现对其计算量进行分析．假设目标模板字典 Ttar={t1，t2，…，tk1}∈m×k1并将其分为 L 块，Ttar={T1，T2，…，TL}，其中 Tl∈m/L×n为第l个分块模板字典．在1．3节中的一次迭代过程中，计算Plyl需要的计算量为O(+(m/L)k1)，所以L个分块的总计算量为O(+mn)．)总的计算量为 O(2Lk21)，所以每次迭代的总计算量为O(3Lk21+nm)．假设迭代次数为 ite，筛选后的粒子数为 N/6，则计算量为O(ite(3L+k1m)N/6)．

图2 文中算法原理图Fig．2 Principle of the proposed algorithm

2 试验

文中算法在Matlab r2009b上编程实现，运行计算机的主频为3．0GHz，内存为2 GB．为了说明文中算法的先进性，将文中算法与另外两个先进的跟踪算法进行比较，它们分别是 ℓ1算法［8］和 IVT算法［15］．这两种算法都基于粒子滤波和仿射变换，目标状态都有6个维度，分别是尺度倍数、长宽比、旋转角度、扭曲角度、横坐标值和纵坐标值，与文中算法具有可比性．文中选取了4个具有挑战性的视频对算法进行比较，3种算法均用600个粒子对目标逼近，将目标区域映射到36×36的矩阵上．文中算法采用10个目标模板和200个背景模板，并将每个图像分成12块，ℓ1算法使用10个目标模板，IVT算法将模板矩阵的维数限制在m×16范围内．本文算法如下:

算法2:文中算法

1．输入:1视频，2首帧目标状态

2．获得初始标准模板和目标模板字典

3．for(f=1:F)，F 为视频帧数

4．利用粒子的速度和高斯分布噪声更新粒子［14］

5．利用仿射变换［14］将候选粒子区域映射至固定的矩形中

6．使用“方差粒子筛选法”对粒子进行筛选，并用筛选结果更新背景模板字典

7．对候选目标和目标模板字典进行分块表示

8．利用式(11)和(12)迭代计算式(10)中的权重

9．用式(13)、(14)和(15)计算出目标粒子的序号

10．更新标准模版

11．if(符合目标模板粒子更新条件)［8］

12．采用文献［8］方法更新目标模板字典

13．end if

14．重采样

15．end for

16．输出:各帧目标状态

2．1 试验结果

第1个实验视频是“David Indoor”，视频跟踪难点主要有3个:①强烈的光照变化;②目标的形态发生改变;③目标尺度的变化．3种算法的结果如图3所示，ℓ1算法在第110帧因为光照条件的变化和目标的形态变化无法锁定目标．文中算法和IVT算法在整个视频中可以准确地跟踪目标．

图3 视频“David Indoor”跟踪结果Fig．3 Tracking results of“David Indoor”

第2个测试的视频是“WalkByShop1cor(WBS)”，该视频的主要难点有2个:①相似物体的干扰;②目标被其他行人遮挡．测试结果如图4所示．ℓ1算法在第102帧目标出现遮挡时锁定了与目标相识的物体，在后面的跟踪过程中，该算法又重新锁定了目标;IVT算法在第102帧目标出现遮挡时偏离了目标;文中算法在整个视频中可以准确地跟踪目标，表现出了强鲁棒性．

第3个测试视频是“Plush Toy”，该视频的主要挑战有3点:①光照的变化;②目标形态的变化;③相似物体的干扰．如图5所示，ℓ1算法在第608帧以前偏离了目标，IVT算法在第608帧由于受相似物体的干扰偏移了目标，文中算法能够完成整个视频的跟踪．

图4 视频“WalkByShop1cor”跟踪结果Fig．4 Tracking results of“WalkByShop1cor”

图5 视频“Plush Toy”跟踪结果Fig．5 Tracking results of“Plush Toy”

第4个测试视频是“Trellis”，对该视频进行跟踪非常具有挑战性，视频中目标经历了目标局部强烈光照变化，目标的形态和尺度也不断变化．如图6所示，ℓ1算法在第103帧偏离了目标，IVT算法在第415帧由于光照和目标拍摄角度的变化偏离了目标，文中算法对光照和目标形态的变化表现出高鲁棒性，可以成功完成跟踪任务．

图6 视频“Trellis”跟踪结果Fig．6 Tracking results of“Trellis”

2．2 结果分析

为了定量分析文中算法与其他两种算法的试验结果，将各种算法的误差进行对比．这里定义跟踪误差为跟踪算法得到的目标中点坐标值和实际目标中点坐标值的欧氏距离．从图7可以看出，文中算法在4个视频中均取得了较小的跟踪误差，而其他两种算法则误差较大．

图7 跟踪误差比较Fig．7 Comparison of tracking error

为了更好地统计各跟踪算法的误差，文中采用了误差百分比进行展示．图8中，横坐标表示误差的像素，纵坐标表示百分比．文中采用10个像素为阈值对跟踪的准确率进行统计．表1为3种算法在4个测试视频中的跟踪成功率，带有下划线的值为最好结果．从图8和表1可以看出，除了视频David Indoor中IVT算法的误差百分比略高于文中算法外，文中算法均取得了最高的跟踪成功率．

3种算法的每帧计算时间比较结果如表2所示．文中算法的运算时间最短，可见粒子筛选方法和ℓ1最小化稀疏解算法可以大大缩短计算时间，这与前面计算量分析结果是相符的．

图8 跟踪误差百分比Fig．8 Precision of location error

表1 跟踪成功率统计Table 1 Statistics of tracking success rate

3 结论

表2 每帧计算时间比较Table 2 Comparison of computation time of one frame

文中提出了一种鲁棒性强的目标跟踪算法，该算法在粒子滤波框架下快速筛选粒子，减少了大量不必要的计算，提高了算法的速度．用目标与背景联合稀疏表示方法将背景信息融入稀疏表示过程，在提高运算速度的同时提高了跟踪的鲁棒性．利用权重分块表示的方法减少目标被遮挡或噪声大的部分对整体结果的影响．试验结果表明，文中算法无论是在计算速度上还是鲁棒性上均取得了良好的效果．

［1］侯志强，韩崇昭．视觉跟踪技术综述［J］．自动化学报，2006，32(4):603-617．Hou Zhi-qiang，Han Chong-zhao．A survey of visual tracking［J］．Acta Automatica Sinica，2006，32(4):603-617．

［2］Agarwal S，Roth D．Learning a sparse representation for object detection ［J］．Computer Science，2006，2353:97-101．

［3］Wright J，Yang Allen Y，Ganesh A，et al．Robust face recognition via sparse representation［C］∥Proceedings of the 8th IEEE International Conference on Automatic Face and Gesture Recognition，2008:210-227．

［4］Yang M，Feng X．Sparse representation or collaborative representation:which helps face recognition［C］∥IEEE International Conference on Computer Vision．［S．l．］:ICCV，2011:471-478．

［5］Yang M，Zhang L，Zhang D，et al．Relaxed collaborative representation for pattern classification［C］∥IEEE Conference on Computer Vision and Pattern Recognition．［S．l．］:CVPR，2012:2224-2231．

［6］Elad M，Aharon M．Image denoising via sparse and redundant representations over learned dictionaries［J］．IEEE Transactions on Image Processing，2006，15(12):3736-3745．

［7］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．

［8］Mei X，Ling H B．Robust visual tracking using ℓ1minimization［C］∥Proceedings of the IEEE International Conference on Computer Vision．［S．l．］:ICCV，2009:1436-1443．

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

［10］Liu H P，Sun F C．Visual tracking using sparsity induced similarity［C］∥Proceedings of the 20th International Conference on Pattern Recognition．［S．l．］:ICPR，2010:1702-1705．

［11］Sun F C，Liu H P．Fusion tracking in color and infrared images using joint sparse representation ［J］．Science Chine-Information Sciences，2012，55(3):590-599．

［12］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．

［13］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-3305．

［14］Ross D A，Lim J，Lin Ruei-sung，et al．Incremental learning for robust visual tracking［J］．International Journal of Computer Vision，2008，77(1/2/3):125-141．

［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．