局部自适应加权的逆结构稀疏表示跟踪算法

吉训生，陈 赛，王荣飞



局部自适应加权的逆结构稀疏表示跟踪算法

吉训生，陈 赛，王荣飞

( 江南大学 物联网工程学院，江苏 无锡 214122 )

传统的稀疏表示跟踪算法直接利用较为简单的灰度特征进行稀疏表示系数计算，易受遮挡、形变等影响。为此，提出一种局部自适应加权算法来增加受遮挡、形变等影响的候选目标与未受遮挡、形变等影响的候选目标之间的区分度。另外，一般稀疏表示算法利用数量较少的目标模板构建过完备字典。无法获得较好的稀疏系数。提出逆稀疏表示算法，利用包含丰富目标特征和背景特征的候选目标构建过完备字典来重构目标模板，相同维度的目标模板条件下可以获得更好的稀疏系数。实验表明，该算法在目标背景差异小或严重遮挡、形变情况下，都能够较好的跟踪目标。

稀疏表示；自适应加权；过完备字典；候选目标

0 引 言

目标跟踪在智能监控、人机交互、机器人导航、自动驾驶和自动交通控制等方面具有重要的应用价值。虽然已经提出了许多优异的跟踪算法，但是因为噪声、光照、遮挡、快速运动和突然运动等干扰因素存在，目标跟踪仍然是一个具有挑战性的研究课题。Wu详述了近年来视觉跟踪的主要方法[1]。目标跟踪中，外观模型用于每帧中的目标表示和验证目标预测。运动模型(如Meanshift和粒子滤波[2]等)用于预测目标状态。本文重点研究外观模型，因为其是跟踪算法中最重要的部分。

目标跟踪主要包括外观表示和目标预测两步，外观表示可分为全局表示和局部表示。全局表示反应的是目标外观全局的统计特性。如灰度特征、颜色特征、纹理特征等。Bradski等人在HSV颜色空间中使用颜色直方图来表示目标[3]。然而当目标发生遮挡和形变时全局特征变化较大，使跟踪鲁棒性较差。局部表示主要是提取目标局部区域的信息来来表示目标外观信息。如分块，超像素[4]、梯度方向直方图特征[5]等。侯跃恩等人对目标局部分块，提高了算法对遮挡抵抗能力[6]，但没考虑到分块之间的联系，失去目标的空间信息。导致在严重遮挡时跟踪精度下降。Jia等人利用叠加局部图像块构建目标的结构稀疏表示模型，利用了目标空间信息提高对遮挡的抵抗能力[7]。稀疏表示是近年来比较流行的目标预测方法。Mei等人首先将稀疏表示理论应用到目标跟踪领域，提出基于-范式最小化的目标跟踪算法[8]，其在目标模板和单位模板上重构候选目标，提高了对遮挡目标的鲁棒性，但是它也存在速度慢等不足。文献[9]利用APG(accelerated proximal gradient)方法计算稀疏表示，提高了稀疏表示过程的计算速度。Wang等认为稀疏表示是一种带稀疏约束的线性回归问题。提出一种新的距离函数来计算候选目标和目标模板之间的相似性，提高了跟踪精度[10]。

本文在粒子滤波框架下提出一种快速、高效局部自适应加权的逆稀疏表示跟踪算法。这种算法利用视频的时间和空间连续性设计了一个鲁棒的局部自适应加权算法，该算法利用Adaboost算法[11]计算每个像素的权值，统计出局部像素权值来对局部图像块加权。当遮挡、形变导致外观变化，没有被遮挡、形变影响的目标区域将会被赋予比那些受到遮挡、形变影响的目标区域更大的权值，增加了外观变化的候选目标与没有变化候选目标之间的区分度。稀疏表示算法要求构建过完备字典重构候选目标，但目标模板数量较少很难构造过完备字典，导致跟踪精度不高。提出利用候选目标构建过完备字典，候选目标数量庞大并包含大量目标特征和背景特征，比较容易构建过完备字典。相同维度的目标模板条件下获得更好的稀疏系数。

1 粒子滤波算法

粒子滤波算法可以很好地解决复杂环境中存在的非线性、非高斯等问题，对目标状态、观测模型等分布没有限制，已广泛应用于目标跟踪中。该算法包括预测和更新两个步骤。

2 局部自适应加权

本文提出一种局部自适应加权算法对图像块进行自适应动态加权，以此增加受到遮挡、形变等影响的候选目标与没受到遮挡、形变等影响的候选目标之间的区分度，该算法利用的先验知识是视频信息的空间和时间的连续性，主要分为两步：1) 利用Adaboost算法计算前一帧跟踪到的目标区域每个像素的权值，得到目标区域的置信图；2) 根据置信图得到局部图像块的自适应权值。

为了得到目标区域的置信图，我们利用Adaboost算法训练一个强分类器。在训练阶段，初始训练样本在第一帧中手动提取，每个样本都是一个三维的特征，由对应像素的RGB值组成。所有在手动标定的目标区域(图1实线框)内的像素对应的特征为正样本，在目标区域周围(图1实线外点画线内)的像素对应的特征为负样本。负样本的数量是正样本的三倍。本文中的Adaboost分类器由五个弱分类器组成，弱分类器为通过权值线性回归得到的正负样本之间的分类超平面。强分类器。

图1 由像素的RGB特征组成的训练样本许多弱分类器组成初始强分类器

图2 第t帧中，从t-1帧跟踪结果中采集测试样本，利用强分类器计算置信图

3 逆结构稀疏表示

在稀疏表示目标跟踪过程中，由于目标样本有限，很难构建较完备的稀疏表示模板字典。文献[7]利用目标模板和单位矩阵来构建稀疏模板字典，这种方法额外增加了模板字典的维度，计算量随之增加。与之相反，本文利用候选目标构建完备稀疏模板字典，在不增加目标模板维度的情况下提高目标跟踪精度。为与传统稀疏表示区别开来，称本文的稀疏表示模型为逆稀疏表示。另外提取目标区域一系列局部图像块表示目标，增加局部变化对跟踪的影响。如图3所示。

在第帧中，首先利用粒子滤波算法在前一帧跟踪目标周围提取个候选目标。根据第二节的算法统计每个候选目标的权值得到，将这些权值排序，排除和目标相似度非常低的个候选目标，降低背景信息对跟踪的影响。在剩余的个候选目标中按照和目标模板同样的方法重叠的采样个局部图像块，利用这些候选目标的局部图像块构成完备稀疏表示字典。用稀疏表示字典对局部目标模板集系数编码：

结构稀疏的核心思想是只考虑目标模板中局部目标块和候选目标中局部目标块对应位置之间的稀疏系数。这样利用了目标区域局部块之间的几何信息，消除颜色和目标局部相似，但是几何位置不正确的干扰信息对跟踪的仍具有干扰。

图3 逆稀疏表示过程.目标模板由一系列对应 正稀疏系数的候选目标重构

图4 a的整体结构。a1~aN是第一个目标模板所有局部图 像块的稀疏系数，椭圆圈中系数平均化后得到v

4 Adaboost分类器和目标模板更新

为了适应目标的外观变化，提出了一种更新Adaboost分类器和目标模板的方法。与之前构造目标的外观模型过程相反，把目标模板中的局部图像块作为字典去对跟踪结果图像区域内采样得到的局部图像块进行编码，即：

为了更新Adaboost分类器，我们首先要判断分类器是否需要更新，若，是一个预设的阈值。在当前跟踪目标处按照图1所示方法重新采样正、负样本来训练弱分类器，并替换强分类器中权值较小的弱分类器。否则，不更新强分类器。

关于目标模板的更新，提出一种局部更新方法使目标模板适应目标的变化。该方法独立考虑目标模板中各个局部图像块。令，：

5 实验分析

以Matlab R2011a为开发工具，为了验证本文所提跟踪算法的性能，将它与ivt[12]、L1APG[9]、ODFS[13]和ALSA[7]四种跟踪算法在都存在严重干扰的视频序列Tiger1序列、Coke 序列、jumping序列、shaking序列进行比较。其中，L1APG和ALSA跟踪算法和本文算法同属于基于稀疏表示跟踪算法。本文中，参数，，，分别设为0.2，0.95，0.2和0.1。所有采用粒子算法的跟踪算法中粒子数都设定为600。按照文献[12]中的方法将所有目标模板和候选目标先仿射到[32，32]空间，叠加8个像素提取[16，16]目标块来用于下面的计算。利用SPAMS包[14]计算式(6)和式(7)。

5.1 定量分析

本文使用两个标准来衡量跟踪的精度，分别为中心点距离误差和重叠率。其中，中心点距离误差是和的中心点之间的欧氏距离，重叠率定义为

本文将每种跟踪算法在视频序列各帧中的中心点距离误差和重叠率分别绘制成曲线图形式，如图5所示。可以看出在各视频序列中，相比其它几种跟踪算法，本文算法具有更低的中心点距离误差和较高的重叠率。这主要得益于本文提出的局部自适应加权算法赋予目标像素较大权值，赋予受干扰像素小权值，这样降低遮挡等干扰对跟踪的影响，另外利用候选目标构造过完备字典来提高稀疏表示系数的精确度，从而提高稀疏表示的判别能力。

图5 5种跟踪算法在4个视频集上的中心距离误差(像素)和重叠率

表1中给出了各种跟踪算法在每个视频序列上的平均中心点距离误差(Center Err [Pixel])、成功率(Success Rate[%])和帧率。可以看出基于稀疏表示的跟踪算法、L1APG算法、ALSA算法和本文算法在存在遮挡、形变的视频序列(Tiger1、Coke)上成功率相对较高。说明基于稀疏表示跟踪算法在处理这方面的干扰具有较强的优势。另外，本文算法在目标和背景分辨率较低的Jumping和shaking中也具有较高的成功率，说明本文算法对这方面干扰的抵抗能力也比较强。帧率定义为总帧数与算法总的运行时间的比值。帧率越大，运行时间越短。可以看出本文算法和ALSA算法的帧率相近，主要是本文算法和ALSA算法实时性相近。L1APG算法中目标模板包含琐碎模板，额外增加了目标模板的尺寸，从而导致实时性较差。IVT和ODFS算法没有计算量较大的稀疏表示计算过程，所以实时性较好。

5.2 定性分析

Tiger1序列(图6(a))中存在不同尺度的遮挡、形变、不同程度的光照和快速运动等。其中遮挡和形变导致目标区域中部分区域像素值彻底变化。光照和快速运动会降低目标和背景区域的分辨率。60帧时目标被完全遮挡，只有ALSA和本文算法成功跟踪目标。主要因为这两种算法都利用目标区域的局部信息和空间信息，增强了对遮挡目标的抵抗能力。之后ODFS又成功找回目标。120帧时目标发生快速运动，使目标变得模糊，降低了其与周围环境的差异。ODFS和本文算法成功跟踪。两种算法采用的分类算法都利用了目标和背景信息，降低了目标漂移的概率。225帧处同时存在强光和快速运动的影响。只有本文算法跟踪成功。说明本文算法对多种干扰有较强的抵抗力。

表1 跟踪算法性能指标和帧率

Coke序列(图6(b))中存在全遮挡、旋转的影响。40帧处大部分的目标都被叶子遮挡。L1APG、ALSA和本文算法这三种基于稀疏表示的跟踪算法都跟踪成功。得益于稀疏表示算法在处理遮挡方面的优势。88帧时目标发生旋转。ALSA和本文算法跟踪成功。主要是因为两种算法都利用率目标的局部信息和空间信息来增强对目标内部变化的抵抗力。191帧左右，目标被全遮挡之前ALSA和本文算法成功跟踪目标，全遮挡发生之后只有本文算法跟踪成功。ALSA算法和本文算法都采用局部目标块表示目标来降低像素彻底变化类干扰的影响，但本文另外利用局部自适应加权算法来提高对干扰抵抗力。

Jumping序列(图6(c))中目标持续快速的运动。整个过程中只有L1APG跟踪失败。主要是其采用新跟踪到的目标整体直接替换目标模板集中权值小的目标模板。在目标变化较快时这种方法会使目标模板集过度频繁更新，而且背景信息会被整体的加入到目标模板集中。从而导致目标模板集漂移。

Shaking序列(图6(d))中目标和背景之间差异较小，而且目标发生剧烈的摇晃，整个过程只有Ivt算法跟踪失败。主要原因是其采用的增量PCA更新目标模板算法不能有效更新发生较大变化的目标，而Shaking中目标存在剧烈的摇晃使目标发生大尺度的变化。

图6 5种跟踪算法在4个视频集上的跟踪结果

6 总 结

本文提出的局部自适应加权算法，其通过Adaboost分类算法对目标区域的目标像素和受到遮挡等干扰的像素分类，并赋予目标像素较大权值，赋予受干扰像素小权值，这样降低遮挡等干扰对跟踪的影响。另外利用候选目标构造过完备字典，提高稀疏表示系数的精确度，从而提高稀疏表示的判别能力。实验表明，本文提出的跟踪算法对严重遮挡、形变、光照变化等干扰有较强的抵抗能力。

[1] WU YI，LIM Jongwoo，YANG Ming-Hsuan. Online object tracking：A benchmark [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Portland，USA，June 23-28，2013：2411–2418.

[2] Doucet A，de Freitas N，Gordon N. Sequential Monte Carlo Methods In Practice [M]. New York，Springe，2001.

[3] Bradski G R. Real time face and object tracking as a component of a perceptual user interface [C]// Workshop on Applications of Computer Vision，Princeton，USA，Oct 19-21，1998：214-219.

[4] YANG Fan，LU Huchuan，YANG Ming-Hsuan. Robust superpixel tracking [J]. IEEE Transactions on Image Processing (S1057-7149)，2014，23(4)：1639-1651.

[5] HOANG Vandung，Le Myha，Jo Kanghyun. Hybrid cascade boosting machine using variant scale blocks based HOG features for pedestrian detection [J]. Neurocomputing(S0925-2312)，2014，135(8)：357-366.

[6] 侯跃恩，李伟光，容爱琼，等. 融合背景信息的分块稀疏表示跟踪算法[J]. 华南理工大学报(自然科学版)，2013，41(8)：21-27.

HOU Yue¢en，LI Weiguang，RONG Aiqiong，. Tracking Algorithm of Block Sparse Representation with Background Information [J]. Journal of South China University of Technology(Natural Science Edition)，2013，41(8)：21-27.

[7] JIA Xu，LU Huchuan，YANG Minghsuan. Visual tracking via adaptive structural local sparse appearance model [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，USA，June 16-21，2012：1822–1829.

[8] MEI Xue，LING Haibin. Robust visual tracking using l1 minimization [C]// IEEE International Conference on Computer Vision (ICCV)，Kyoto，Japan，Sept. 29-Oct. 2，2009：1436–1443.

[9] BAO Chenglong，WU Yi，LING Haibin，. Real time robust L1 tracker using accelerated proximal gradient approach [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，USA，June 16-21，2012：1830–1837.

[10] WANG Dong，LU Huchuan，YANG Ming-Hsuan. Least soft-threshold squares tracking [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Portland，USA，June 23-28，2013：2371-2378.

[11] Freund Yoav，Schapire Robert E. A desicion-theoretic generalization of on-line learning and an application to boosting [M] Computational Learning Theory：Springer Berlin Heidelberg，1995：23-37.

[12] LIM Jongwoo，ROSS David，LIN Ruci-Sung，. Incremental learning for robust visual tracking [J]. International Journal of Computer Vision(S0920-5691)，2008，77(1)：125–141.

[13] ZHANG Kaihua，ZHANG Lei，YANG Ming-Hsuan. Real-time object tracking via online discriminative feature selection [J]. IEEE Transactions on Image Processing(S1057-7149)，2013，22(12)：4664-4677.

[14] WebLink. SPAMS: http://www.di.ens.fr/willow/ SPAMS/downloads.html, 2015, October.

Local Adaptive Weighted Tracking Via Inverse Structure Sparse Representation

JI Xunsheng，CHEN Sai，WANG Rongfei

( School of Internet of Things, Jiangnan University, Wuxi 214122, Jiangsu, China )

Traditional sparse representation tracker use simple grayscale characteristics in calculating sparse coefficient, which is easily affected by the heavy occlusions and deformation. To this end, a local adaptive weighting algorithm is put forward to increase degree of differentiation between the candidate targets affected by shade, deformation, etc and not affected by the shade, deformation, etc. In addition, the general sparse representation algorithm use a small number of target templates to build a complete dictionary, which unable to get a better sparse coefficient. Inverse structure sparse representation algorithm, using the candidate target which contains rich target and background features to build a complete dictionary to reconstruct the target template under the condition of the same dimension target template better sparse coefficient can be obtained, is proposed. Experiments show that the proposed algorithm in the small differences between target and background or serious barrier, deformation, can better track the target.

sparse representation; adaptive weighting; over-complete dictionary; candidate target

1003-501X(2016)12-0085-07

TP391

A

10.3969/j.issn.1003-501X.2016.12.014

2016-02-29；

2016-09-18

国家自然科学基金资助项目(61170120)

吉训生(1969-)，男(汉族)，江苏南通人。硕士生导师，副教授，主要研究工作是信号处理。

陈赛(1990-)，男(汉族)，江苏徐州人。硕士研究生，研究计算机视觉跟踪。E-mail: chenvssai@163.com。