基于压缩特征的稀疏表示运动目标跟踪

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

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



基于压缩特征的稀疏表示运动目标跟踪

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

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

摘要：为了应对目标跟踪中光照、遮挡、以及自身运动等因素的影响，采用积分图方法提取目标模板的haar-like特征，用满足有限等距条件(RIP)的随机稀疏矩阵对特征投影压缩，简化目标特征字典的构建；同时，在字典中融入背景信息，利用目标与背景的简单关系提高跟踪的精度;最后，利用块正交匹配追踪(BOMP)算法进行成块重构目标，加快了对稀疏表示的求解，增强了跟踪的实时性.通过实验发现，使用基于压缩特征的块正交匹配跟踪算法(CF-BOMP)能构建一个有效的目标外观模型，增强跟踪的稳定性，提高跟踪的实时性.

关键词：特征压缩；稀疏表示；粒子滤波；块正交匹配

0引言

稀疏表示是近年来信号处理领域的热点之一，为一种对原始信号的分解过程，该分解过程借助一个事先得到的字典，将输入信号表示为字典的线性近似.文献[1]首次在人脸识别中运用稀疏表示的方法;文献[2]则利用线性表示特征构建模板，结合稀疏表示理论，成功进行目标识别.随着稀疏表示运用领域的推广，在ICCV 2009上L1 tracker算法被首次提出来，文献[3]提出L1 tracker算法是将跟踪问题看成稀疏求解的过程,结合粒子滤波和稀疏表示思想，通过构建含有琐碎模板的目标外观模型，将跟踪问题转化为求解稀疏表示的问题；文献[4]将压缩感知理论应用到跟踪算法中，目的在于解决实时性问题；文献[5]通过设定L1正则范数的错误边界，减少求解稀疏表示待选目标个数，一定程度上提高了跟踪速度；文献[6]从重构算法入手对L1 tracker进行改进，采用APG(Accelerated Proximal Gradient algorithm)重构算法，加快了L1求解的速度，提高了跟踪的效率.但以上方法在跟踪的实时性、准确性、稳定性方面仍面临着巨大挑战.

因此，笔者提出了一种利用压缩特征进行稀疏表示的目标跟踪方法——CF-BMOP算法.该算法基于压缩感知理论[7-8]降维后的特征能够有效表征目标，简化目标特征模板的构建，并引入背景信息从而增强跟踪的准确性与稳定性；同时，根据结构关系采用了块正交匹配追踪(BOMP)重构算法优化了稀疏表示求解，实现对目标跟踪准确性与实时性的提升，通过实验证明了CF-BOMP算法在实时性和准确性方面得到提升.

1字典构建与稀疏求解

1.1目标的稀疏表示

目标的稀疏表示是对原始信号的分解过程，该分解过程借助事先得到的目标字典D=[s1,s2…,sn]，将输入信号表示为字典的线性近似的过程.对于一个待检测的目标y，能够通过模板及向量线性组合重构，即

(1)

式中：α=[α1,α2,…,αn]T是系数向量.考虑到干扰情况的存在，目标的重构情况为

(2)

式中：A=[D,Dε]含有遮挡字典Dε的目标的过完备基.利用A来线性组合表示目标，主要目标就是求出系数向量ω.由于式(2)是欠定的，有无穷多个解，而求解该方程可以通过求解0范数来求解稀疏信号，但0范数问题是一个NP-hard问题，很难计算.Donoho等人提出，对于某些测量矩阵，这个问题可以等价于1范数求解形式:

(3)

1.2压缩特征提取

haar-like特征是将目标物不同位置的像素灰度特征建模成不同的区域时具有较好的表征能力，并且能够利用积分图来对haar-like特征进行加速计算.

另外，对于提取每个样本，z∈Rw×h，为了表明矩形特征海量问题，用多尺度的矩形滤波器跟z做卷积，得到样本的所有矩形特征，滤波器集合H={h1,1,h1,2,…,hw,h}，定义如下：

(4)

式中：w、h分别是矩形滤波器的长与宽.

(5)

其中，1/p为稀疏矩阵中不为零元素出现的概率，本文中设置1/p=4/m.

将高维度特征空间X投影到低维空间中，即

V=(v1,…,vn)=RX .

(6)

Haar-like类特征投影如图1所示，采用满足有限等距条件RIP的测量矩阵Rn×m提取目标的haar类特征，不仅保留了原始图像的大量信息，保证了特征的有效性，而且在目标模版出现部分遮挡时候，减少了异常像素对于目标将产生的影响，增强了特征的稳定性.

1.3含有背景信息的字典构造

笔者在提取目标模板Nf的同时，在其周围位置提取背景Nb，利用1.2节的特征提取压缩方法,得到目标模板与背景模板对应的特征Vf与Vb；同时，为了减少光照和遮挡带来的影响，在目标模板中加入单位矩阵I=(i1,i2,…,in)∈Rn×n,构成含有背景信息的目标过完备字典A：

A=[Vf,Vb,I].

(7)

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

1.4块正交匹配重构

在实际情况中，稀疏信号出现的非零元素是具有一定的相关性，在位置上表现出一定的结构性，表现出成块出现非零元素的情况.因此，笔者使用块正交匹配追踪(BOMP)，利用信号过完备字典的块稀疏结构，选择残差最配子块进行更新，提高了重构的速度.块正交匹配追踪算法的步骤如下.

(1)初始化步骤.设定初始化残差r0=y，测量矩阵为Φ，初始化块稀疏度为K.

(2)感知步骤.进行第k步迭代，计算残差rk-1，并选择与残差rk-1最匹配的块：

(8)

(3)残差更新步骤.令Ek=Ek-1∪ik，然后对残差进行更新:

(9)

(4)收敛条件.判断k与K的大小关系，如果k小于K，返回步骤2继续迭代;否则停止迭代.

2稀疏表示目标跟踪

2.1粒子滤波

粒子滤波主要由预测和更新递推得到：

(10)

(11)

(12)

权重更新方法为

(13)

其中上式分母为采样粒子的建议分布.

2.2基于稀疏表示的观测

基于稀疏表示的系数向量α，笔者用组建的目标压缩特征字典A对候选目标的压缩特征进行重构，根据候选样本的目标观测计算重构残差:

‖y-Aα‖2=‖y-(Vf,VB,I)(αf,αb,αi)T‖2.

(14)

式中：αf、αb分别为目标模板部分与背景模板部分的稀疏系数向量.如果候选目标为跟踪目标，那么候选目标对应于目标模板部分的重构误差会很小，而在背景模板中的重构误差会很大，反之亦然.因此，定义基于重构误差比的观测值为

(15)

基于重构误差比的观测似然函数为

(16)

式中：λ是控制参数.当目标的重构误差越小的时候，式(13)所表示的权重就会越大，也就证明候选样本与目标样本越相似.

2.3字典模板更新

目标的外观以及背景关系会随着自身运动或者环境的变化而发生改变，为了保证跟踪的稳定性，需要对目标及背景模板进行实时更新.针对背景模板在短时间内变化小的情况，采用间隔n帧进行重新采样更新的方法，设置n=5.同时，采用文献[3]的方法进行目标模板更新，步骤如下.

(1)记vy代表跟踪的结果所对应的haar-like特征;a是vy在目标模板特征下的稀疏表示系数;τ是设定的阈值.

(3)根据vy在目标模板特征下的稀疏表示系数对板重w进行更新，即wi=wi·exp(ai).

当跟踪结果的特征vy与最优目标模板特征的相似度小于给出的阈值，则用跟踪结果的特征vy代替目标模板特征中权重最小的模板.为了防止偏移，其权重设为目标模板权重的中值.

2.4算法流程

笔者提出的CF-BOMP算法流程如下：

(1)前M帧时，快速提取目标模板与背景模板的压缩haar-like特征，添加单位矩阵I，构建融入背景信息的目标特征过完备字典.

(2)下一帧时，在上一帧目标中心附近采样候选目标，并提取候选目标的压缩haar-like特征.

(3)利用过完备字典对候选目标特征进行稀疏表示，采用BOMP重构算法来快速精确重构，计算重构残差并引入观测似然函数对目标进行最大似然估计，求出最佳候选目标.

(4)根据跟踪结果，计算模板与最新结果相似度，替换相似度最小模板，更新目标过完备字典.

(5)返回继续执行第2步操作，实现对目标下一帧的跟踪，直到视频序列结束.

3实验结果

实验设置：候选目标的搜索半径为r=15，对前20帧取样构建初始目标模板，目标模板个数为nf=20，背景目标模板数nb=10，采样的候选目标数是n=600，目标模板更新的阈值设置为τ=40，所有实验都是在CPU为i5-3230M、内存2GB的计算机上运用Matlab 2010b进行仿真.

为了检验多种干扰情况下的跟踪效果，实验选用公认测试帧：David indoor、Girl、Coke，其特性如表1所示.选用CT算法[10]、L1-APG算法[6]和MIL算法[11]进行对比实验，文献[10]提出的CT算法是基于haar压缩特征的二分类判别式跟踪方法.而L1-APG算法是一种基于L1 tracker，采用加速逼近梯度重构算法(APG)优化求解速度，但其含有仿射模型来应对目标尺度变化的问题.MIL算法将多示例学习方法加入到Online Boosting中，进而利用具有学习能力分类判决器跟踪目标.

稀疏求解的重构算法直接影响了跟踪的效果[12](准确度与速度)，为充分验证块正交匹配算法(BOMP)能够提高目标跟踪的准确性与实时性，本文在相同情况下，对算法的重构精度和运行速度进行比较，对比了正交匹配追踪算法(OMP)、增广拉格朗日算法(ALM)、加速共轭梯度算法(APG)，表2显示了各重构算法在3种视频帧中的平均重构误差，可以看出，BOMP误差最小.

表1　测试视频帧特性

表2　平均重构误差

表3显示了各重构算法的重构平均帧率，由于BOMP利用重构系数的结构关系，能够成块地对目标进行重构，提高了重构速度.综合表2与表3的结果可以看出，块正交匹配算法(BOMP)在稀疏表示重构中能够提高重构的效率.

表3　平均重构帧率

图2～图4分别显示了4种算法在测试帧David indoor、Girl、Coke中的跟踪情况.综合分析可知，CT算法和MIL算法在跟踪的过程中易受光照变化与目标旋转的干扰，一旦发生偏移，会使目标模板更新并引入错误信息，逐渐远离目标.L1-APG算法虽然能够在目标变小时利用仿射模型准确跟踪目标，但在快速运动与目标旋转的过程中易受到干扰，引起跟踪失败.CF-BOMP算法在整个过程中能够有效跟踪目标，应对光照变化、目标旋转、快速运动、遮挡等干扰.

表4记录了CF-BOMP算法、CT算法和L1-APG算法、MIL算法所对应的3套测试帧的跟踪中心误差数值范围，而该误差能够有效表征跟踪算法的稳定性.通过实验对比发现，CF-BOMP算法误差浮动范围小，跟踪更加稳定.

图2　David indoor 跟踪结果Fig.2　Tracking result for David indoor

图3　Girl 跟踪结果Fig.3　Tracking result for Girl

图4　Coke 跟踪结果Fig.4　Tracking result for Coke表4　跟踪误差范围Tab.4　Tracking error

视频帧CF-BOMPMinMaxL1-APGMinMaxCTMinMaxMILMinMaxDavidindoor0.541.71.654.691.185.82.2139.7Girl2.156.32.164.90.5111.01.594.4Coke1.062.61.1275.91.481.02.2154.6平均值1.253.51.6131.81.092.62.0129.6

表5显示了4种种算法在跟踪过程中的平均中心误差.从表5可以看出，CF-BOMP算法中心误差在3组测试帧中均是最小，说明跟踪精度最高，跟踪更加精确.

图5为4种算法的每帧跟踪中心误差连接成的平滑曲线.从图5可以直观看出，CF-BOMP算法在4种算法中跟踪精度最高，跟踪的稳定性最好.

表5　跟踪中心误差

图5　4种算法的中心误差曲线Fig.5　Tracking error on the videos

表6为4种算法的平均帧率.表6中的CF-BOMP跟踪算法由于构建了简单的外观特征字典，而且使用BOMP算法加速重构计算速度，使得跟踪速度提高到同为稀疏表示跟踪的L1-APG算法速度的2倍左右，是多示例学习的MIL算速度的3倍左右，但与判决式的CT算法相比，速度还是逊色不少.但是，判决式的跟踪会因为一旦判决失误，目标模板大面积更新后，就不能反映出目标本身的特性，跟踪结果的偏离会更大.而CF-BOMP算法可以利用过完备字典中的背景信息提高跟踪精度，同时在产生新结果后，能够把重构贡献最小的粒子更新掉，但之前其他粒子模板仍会保留，也就保留了跟踪目标多个时态特征，保证跟踪效果的稳定.

表6　平均帧率

4结论

笔者提出了一种基于压缩特征的块正交匹配跟踪算法即CF-BOMP算法.该算法在粒子滤波框架下，运用积分图加速计算跟踪目标haar-like特征，并将特征投影到满足有限等距条件RIP的随机稀疏矩阵上，以实现对特征的压缩，达到降维的目的，简化目标特征的过完备字典.同时，在过完备字典中融入背景信息，利用目标与背景存在的简单关系提高跟踪的精确度.最后，在稀疏表示求解过程中，根据实际情况利用块正交匹配追踪(BOMP)提高求解L1-min的速度，引入基于重构误差比的观测模型，实现对目标的快速预测与跟踪，并根据跟踪结果实时更新目标特征模版.通过实验发现，该跟踪方法简化了过完备字典，构建了有效的外观模型，提升了跟踪的实时性，并能够稳定跟踪目标.

参考文献：

[1]WRIGHT J, YANG A, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on pattern analysis and machine intelligence, 2009, 31(2)：2368-2378.

[2]张勇,党兰学.线性判别分析特征提取稀疏表示人面识别方法[J].郑州大学学报(工学版),2015,36(2):94-98.

[3]MEI Xue, LING Haibin. Robust visual tracking and vehicle classification via sparse representation[J]. IEEE Transactions on software engineering, 2011, 33(11): 2259-2272.

[4]LI Haixi, SHEN Chunhua, SHI Qinfeng. Real-time visual tracking using compressive sensing[C]∥2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Colorado Springs, CO, USA: IEEE Press, 2011: 1305-1312.

[5]Mei Xue, Ling Haibin, Wu Yi, et al. Minimum error bounded efficient1 tracker with occlusion detection[C]∥2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Washton DC,USA:IEEE Press, 2011: 1257-1264.

[6]BAO Chenglong, WU Yi, LING Haibin, et al. Real time robust l1 tracker using accelerated proximal gradient approach[C]∥2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, Rhode Island:IEEE Press, 2012: 1830-1837.

[7]DONOHO D L. Compressed sensing[J]. IEEE Transactions on information theory, 2006, 52(4): 1289-1306.

[8]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.

[9]ELDAR Y C,KUPPINGER P,BOLCSKEI H.Block-sparsesignals:uncertainty relations and efficient recov-ery[J]. IEEE Transactions on signal processing, 2010 ,58(6):3042-3054.

[10]ZHANG Kaihua, ZHANG Lei, YANG Ming-Hsuan. Real-time compressive tracking[C]∥Computer Vision-ECCV 2012.Berlin,Heidelberg:Springer, 2012: 864-877.

[11]BABENKO B, YANG, M H , BELONGIE, S. Robust object tracking with online multiple instance learning[J].IEEE Transactions on pattern analysis and machine intelligence, 2011, 33(8)：1619-1632.

[12]GONZLEZ R C,WOODS R E.数字图像处理[M].阮秋琦，阮宇智，译.2版.北京:电子工业出版社，2007.

Sparse Representation Tracking Based on Compressed Features

ZHANG Hongmei， WEN Huiran， ZHANG Xiangli， LI Pengfei

(School of Information and Communication Engineering, Guilin University of Electronic Technology,Guilin 541004,China)

Abstract:In order to deal with the influence of the factors such as light, shade,movement of object and etc.,the integral graph method is used to extract the Haar-like features of the target template, and the features are compressed by a random sparse matrix which meets the limited equidistant conditions(RIP), then the construction of the target features dictionary is simplified .Meanwhile,the background information is added in the dictionary,and the simple relationship between the target and the background is used to improve the accuracy of tracking. At last, the target can be reconstructed in block by using the block orthogonal matching pursuit (BOMP) reconstruction algorithm, through which can enhances tracking speed. The experimental results show that, the block orthogonal matching pursuit tracking algorithm based on compression feature is powerful in valid target appearance model construction.And it also enhances the tracking stability and improves tracking speed.

Key words:features compression; sparse representation; particle filter; block orthogonal matching

收稿日期:2015-10-10；

修订日期：2016-01-20

基金项目：国家自然科学基金资助项目(61461010,61363031)；桂林电子科技大学研究生教育创新计划资助项目(GDYCSZ201413)

作者简介:张红梅(1970—)，女，广西桂林人，桂林电子科技大学教授，主要从事嵌入式、信息安全及机器视觉等研究，E-mail：hmzh630@gmail.com.

文章编号:1671-6833(2016)03-0021-06

中图分类号：TP391

文献标志码：A

doi:10.13705/j.issn.1671-6833.2016.03.005