基于稀疏表示的目标跟踪算法

温荟然,张红梅,张向利,李鹏飞

(桂林电子科技大学信息与通信学院,广西桂林 541004)

基于稀疏表示的目标跟踪算法

温荟然,张红梅,张向利,李鹏飞

(桂林电子科技大学信息与通信学院,广西桂林 541004)

为了解决目标跟踪忽视背景信息的问题,运用非常稀疏的矩阵对目标与背景样本提取低维Haar特征,并将候选目标在过完备字典中进行稀疏表示,用块正交匹配追踪的方式对稀疏表示进行求解,通过残差对目标作最大似然估计,提高跟踪效果。实验结果表明,在光照变化、遮挡、复杂背景等情况下,基于稀疏表示的目标跟踪算法具有较高的鲁棒性,且在跟踪速度上有所提升。

Haar特征;背景信息;稀疏表示;块正交匹配

稀疏表示是将信号分解到一个过完备字典的线性表示过程。在机器视觉中,由于稀疏表示在应对遮挡和光照变化方面的良好表现,近几年被广泛应用。在人脸识别领域,文献[1]的稀疏表示人脸识别算法为今后的稀疏表示视觉处理打开了一扇大门。文献[2]提出基于稀疏表示的L1 tracker算法,将跟踪问题看作求解稀疏解的过程,其主要思想是在粒子滤波框架下,提取候选目标,为解决遮挡问题增加正负冗余模板,并计算重构残差,选择残差最小的候选目标作为跟踪结果,最后根据跟踪结果对目标模板和粒子的权重进行更新。文献[3]将稀疏表示压缩感知原理运用到目标跟踪,通过正交匹配追踪(orthogonal match pursuit,简称OMP)加速跟踪。文献[4]通过设定L1正则范数的错误边界,减少了求稀疏解的待选目标个数,一定程度上提高了跟踪速度。文献[5]从重构算法入手,对L1 tracker算法加以改进,采用加速近端梯度(accelerated proximal gradient,简称APG)重构算法,提高了L1的求解速度和跟踪效率。

上述方法虽然能有效地对目标进行跟踪,但其生成模型的方法存在以下不足:1)外观模型基于整体特征,在增加冗余模板后,使得计算量增加;2)忽视了背景与目标的关系,不能有效利用背景筛选目标。鉴于此,运用满足有限等距性质(restricted isometry property,简称RIP)的随机稀疏矩阵投影压缩Haar特征,将背景信息融入目标的过完备字典中,并利用块正交匹配追踪(block orthogonal match pursuit,简称BOMP)算法求解稀疏表示L1范数最小化,实现对目标的稳定跟踪。

1 稀疏表示与过完备字典

1.1 目标的稀疏表示

目标的稀疏表示是对原始信号的分解过程,该过程借助一个事先得到的字典D=[s1,s2,…,sn](也叫过完备基),将输入信号表示为字典的线性近似过程。对于一个待检测的目标y,通过模板集向量线性组合n重构,y=∑aisi=Dα,其中α=[α1,α2,…,αn]T为i=1系数向量。考虑干扰情况,目标重构为:

其中A=[D,Dε]为含遮挡字典Dε的目标的过完备基。信号y在过完备字典A通过系数向量ω的线性组合进行表示。由于式(1)是欠定的,系数向量ω有无穷个解,可通过求解0范数来求解稀疏信号,

但式(2)是一个NP-hard问题,很难计算。对于某些测量矩阵,此问题可等价于1范数的求解形式[6]:

1.2 特征的提取

Haar特征及其积分图的求解由美国麻省理工学院的Viola博士提出,它是对目标不同区域的像素灰度进行有机组合,属于一种综合性特征,具有稳定表达目标的效果。另外,Haar特征可用积分图的方法,一次性扫描各点到起点组成的矩形空间的像素并静态保存在计算机内存中,当需要计算某个区域特征时,可直接读取数组的元素,运用简单的加减运算得出结果,以提高计算速度。

为了说明矩形特征的海量问题,对每个样本Z∈Rw×h,用多尺度矩形滤波器与Z作卷积,得到样本的所有矩形特征。滤波器集合H={h1,1,h1,2,…,hw,h}定义如下:

其中i、j分别为矩形滤波器的长和宽。

设定X=[x1,x2,…,xm]T∈Rm为样本Z的所有矩形特征,其中X=ZH,引入一个满足RIP的非常稀疏的随机矩阵Sn×m,且n≪m。该矩阵为一个扁矩阵,通过投影可将特征向量降维压缩。矩阵Sn×m的元素定义为:

其中p为设定数值,设定p=m/4产生一个非常稀疏的测量矩阵,该测量矩阵S的每一行只需计算4个非零元素,计算量非常低。将高维度特征空间X投影到低维空间:

其中V为压缩后的特征,即通过测量矩阵提取的Harr类特征组,其提取过程如图1所示。

图1 类特征投影Fig.1 Harr-like feature projection

采用满足RIP的测量矩阵提取Harr类特征,得到的特征不仅几乎保留了原始图像的所有信息[6-7],保证了特征的有效性,而且在目标模板出现部分遮挡时,部分异常像素对于目标将不会产生影响,增强了特征的稳定性。

1.3 过完备字典组建

由于目标存在于背景中,目标与背景总是具有相关性,运用其相关性,可更好地确定目标的位置。因此,构建过完备字典时在模板中增加背景模板信息,一方面,可更好地运用目标与背景的关系来稳定跟踪,另一方面,若下一帧候选粒子存在背景,其仍可在过完备字典中稀疏表示。提取目标模板中背景模板的压缩Haar特征组,分别记为:

为了减少光照和遮挡对跟踪结果的扰动,在琐碎模板中加入正琐碎模板,即非负单位矩阵,则融合背景模板的目标特征模板为:

其中I=[i1,i2,…,in]∈Rn×n为单位矩阵。

2 融合背景信息的跟踪

2.1 观测模型

将第i个候选目标的特征Viy用融合背景模板的特征稀疏表示:

其中:af、ab为候选目标特征组的表示系数;ef为正琐碎模板的表示系数。

对候选目标采用重构算法求其在目标字典中的稀疏表示,并分别求候选目标特征在目标模板特征和背景模板特征下的重构误差:

准确的目标特征在目标模板特征下的重构误差很小,而在背景模板特征下的重构误差很大;不准确的目标(无需跟踪的目标)特征在背景模板特征下的重构误差很小,而在目标模板特征下的重构误差很大。综合这2方面的考虑,最佳候选目标的观测器为:

2.2 BOMP重构算法

重构算法的目的是求解式(8)中的稀疏表示系数。重构算法的好坏直接影响跟踪结果,OMP作为经典的重构算法,已被广泛应用,而在实际情况中,这种迭代的重构算法非常耗时。目标系数出现不为零的情况是成块出现的,且块稀疏信号中不为零的系数也成块随机出现,而非杂乱无规律分布[8],因此利用BOMP算法成块重构,既提高速度又保证与OMP几乎同样的精度。

BOMP算法流程:

1)初始化。设定初始化残差r0=y,初始化测量矩阵Φ,初始化块稀疏度K。

2)感知。进行第k步迭代,计算残差rk―1,并选择与残差rk―1最匹配的块:

3)残差更新。令Ek=Ek―1∪ik,对残差进行更新:rk=(ik―ΦEkΦETk)y。

4)收敛条件。判断k与K的大小关系,若k＜K,则返回步骤2)继续迭代,否则停止迭代。

2.3 目标模板更新

由于跟踪过程中目标会发生姿态、光照等变化,需及时更新目标模板。设定跟踪结果的特征与最优目标模板特征的相似度小于某个阈值,将相似度最低的目标模板特征更新为当前跟踪结果特征,其权重初始化为所有权重的中值。更新主要包括模板替代、模板更新和权重更新3个步骤。用跟踪结果的特征代替目标模板特征中权重最小的模板,其权重设为目标模板权重的中值。权重的计算采用文献[3]的计算公式。

3 实验结果

1)实验设置。候选目标的搜索半径r=20,针对前20帧手动取样,目标模板个数Nf=20,采样的候选目标数N=500,目标模板更新的阈值设置为τ= 40,在CPU i5-3230M、内存4 GB的计算机上用Matlab 2010仿真。

2)评价指标。若一个视频序列帧数为n,第i帧跟踪到的目标中心坐标为(xi,yi),目标中心坐标为(^xi,^yi),则定义该帧的跟踪误差为:

该帧的跟踪误差越小,表明跟踪精度越高。视频序列的平均误差为:

视频序列的平均误差越小,则表明整个视频序列的跟踪精度越高。

为了验证跟踪效果,将评价指标用于跟踪David indoor、girl、coke三种视频序列,这些视频序列包含了目标跟踪过程中常出现的情形,如视角变化、光照变化、遮挡等,如表1所示。

表1 各视频帧特征

为了凸显算法的有效性,选取2种流行的跟踪算法L1-APG[5]算法、CT[9]算法与本算法作比较,其中CT算法为基于压缩感知原理的判决型跟踪算法。3种跟踪算法在3组视频帧的实际跟踪情况如图2所示。从图2可看出,本算法在跟踪的过程中借助背景信息而使得跟踪变得更加准确,鲁棒性更强。

图2 各视频帧的跟踪结果Fig.2 Tracking results of each video

通过对比各个时刻的跟踪误差,分析各跟踪算法在目标跟踪中的稳定性与准确性,以中心误差作为衡量跟踪误差的指标,不同跟踪算法在不同视频上的跟踪误差如图3所示。从图3可看出,本算法的跟踪精度更高,在各个时刻更加稳定,鲁棒性更强。

各个跟踪算法在不同视频帧的跟踪误差数据如表2所示。由表2可算出本算法、CT算法、L1-APG算法的平均跟踪误差分别为18.630 6、42.857 7、 56.503 3,因此本算法在3组测试视频帧中的平均跟踪误差最小,表明跟踪精度最高。

图3 各视频上的跟踪误差Fig.3 Tracking errors on the videos

表2 跟踪误差Tab.2 The tracking errors

通过记录跟踪算法处理全部视频帧的时间,计算本算法与L1-APG算法的平均帧率,结果如表3所示。从表3可看出,本算法的跟踪速率约为L1-APG算法的3倍,平均帧率达到12 frame/s,基本达到了实时性的要求。

表3 平均帧率比较Tab.3 The comparison of average frame rate frame/s

4 结束语

基于压缩特征提出了一种稀疏表示跟踪算法,该算法在粒子滤波框架下,运用积分图快速计算跟踪目标的Haar特征,并将特征投影到满足RIP的高斯矩阵上,实现对特征的压缩,达到降维的目的;在过完备字典中融合背景信息特征,用BOMP实现对候选目标特征的重建,利用重构误差比值构建最优观测模型,达到对目标的估计与跟踪,且能根据跟踪结果实时更新目标特征模板。实验结果表明,该跟踪方法达到了稳定跟踪目标的目的,在速度方面相比L1-APG算法有所提升。

[1] Wright J,Yang A Y,Ganesh A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31 (1):210-227.

[2] Mei Xue,Ling Haibin.Robust visual tracking and vehicle classification via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(11):2259-2272.

[3] Li Haixi,Shen Chunhua,Shi Qinfeng.Real-time visual tracking using compressive sensing[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2011:1305-1312.

[4] Mei Xue,Ling Haibin,Wu Yi,et al.Minimum error bounded efficient l1 tracker with occlusion detection [C]//IEEE Conference on Computer Vision and Pattern Recognition,2011:1257-1264.

[5] Bao Chenglong,Wu Yi,Ling Haibin,et al.Real time robust l1 tracker using accelerated proximal gradient approach[C]//IEEE Conference on Computer Vision and Pattern Recognition,2012:1830-1837.

[6] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[7] Candes E J,Tao T.Near-optimal signal recovery from random projections:universal encoding strategies[J]. IEEE Transactions on Information Theory,2006,52 (12):5406-5425.

[8] Eldar Y C,Kuppinger P,Bolcskei H.Block-sparsesignals:uncertainty relations and efficient recovery[J]. IEEE Transactions on Signal Processing,2010,58(6): 3042-3054.

[9] Zhang Kaihua,Zhang Lei,Yang M H.Real-time Compressive Tracking[M]//Fitzgibbon A,Lazebnik S,Perona P,et al.Computer Vision-ECCV 2012.[S.l.]: Springer Berlin Heidelberg,2012:864-877.

[10] Gonzlez R C,Woods R E.数字图像处理[M].阮秋琦,阮宇智,译.2版.北京:电子工业出版社,2007,236-257.

编辑:张所滨

Target tracking algorithm based on sparse representation

Wen Huiran,Zhang Hongmei,Zhang Xiangli,Li Pengfei
(School of Information and Communication Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

In order to solve the defects of tracking algorithm which ignores the background information,a very sparse matrix is used to get low dimensional Haar feature of target and background,and the candidate target can be sparse representation in the over complete dictionary.Block orthogonal matching pursuit method is used to solve the sparse representation and get residual,then the maximum likelihood estimation is achieved.Experimental results show that the tracking method based on sparse representation still has very high robustness in illumination,occlusion and complex background conditions,and the tracking speed is improved.

Haar feature;background information;sparse representation;block orthogonal match

TP391

:A

:1673-808X(2015)04-0305-05

2015-03-13

国家自然科学基金(61461010);桂林电子科技大学研究生教育创新计划(GDYCSZ201413)

张红梅(1970―),女,广西桂林人,教授,博士,研究方向为网络安全、嵌入式系统。E-mail:hmzh630@gmail.com

温荟然,张红梅,张向利,等.基于稀疏表示的目标跟踪算法[J].桂林电子科技大学学报,2015,35(4):305-309.