基于稀疏表示和粒子滤波的在线目标跟踪算法

王海罗， 汪渤， 高志峰， 周志强， 李笋

(北京理工大学 自动化学院，北京 100081)



基于稀疏表示和粒子滤波的在线目标跟踪算法

王海罗， 汪渤， 高志峰， 周志强， 李笋

(北京理工大学 自动化学院，北京 100081)

针对目标跟踪过程中由于外形变化或者遮挡所造成的跟踪效果下降或导致漂移的问题，提出一种粒子滤波框架下基于稀疏表示的在线目标跟踪算法. 采用分层梯度方向直方图(PHOG)特征对目标模板进行描述，并且每一个候选模板都可以通过PHOG基向量和琐碎模板进行稀疏表示，进而利用L1范数最小化方法进行最优求解. 为保证在遮挡的情况下目标跟踪的精度，对目标遮挡部分和非遮挡部分进行拆分建模，并利用PCA子空间增量学习的方式不断更新目标跟踪模型. 通过对具有挑战性的跟踪视频进行定性和定量分析，实验证明该方法在跟踪精度上要优于传统的跟踪方法.

稀疏表示；PCA增量学习；PHOG特征；在线目标跟踪

视频目标跟踪是计算机视觉领域中的经典问题，融合了图像处理、模式识别、机器学习等多种技术，在跟踪过程中，由于光照变化、目标形变以及遮挡等因素存在，给跟踪造成很大困难，研究精度高而且鲁棒的目标跟踪方法仍是一项挑战.

为了克服这些困难，学者们提出了大量的跟踪方法，根据实现方式的不同，主要分为基于辨别模型的目标跟踪和基于产生模型的目标跟踪. 在辨别模型中，目标跟踪被归类为一种二进制分类问题，通过分类器的学习将目标从背景中分离出来，如Ensemble tracker[1]，在线多目标跟踪[2]、压缩跟踪[3]. 产生模型是通过对目标外观进行建模，将目标跟踪问题转化为寻找具有最小重构误差的目标观测值，如Eigentracker[4]，Mean-shift跟踪[5]，增量跟踪[6]以及协方差跟踪[7].

近几年来，稀疏表示逐渐被用于目标跟踪[8-9]. 稀疏表示的最大优势在于对图像目标变化和遮挡情况具有很好的鲁棒性. Mei等[10]提出一种基于L1范数最小化的跟踪方法，将稀疏表示引入粒子滤波的框架，取得了很好的跟踪结果，不过这种方法每帧图像都要处理上百次的L1最小化过程，计算复杂度高，处理速度较慢，为了平衡跟踪速度，只能降低模板的分辨率，而低分辨率的模板并不能提供足够的跟踪信息来表示目标. 另外，L1跟踪不像子空间表示方法那样能够利用丰富的图像属性，例如目标本身的结构信息来进行判断. 针对以上问题，本文对其进行了两部分改进，一是对目标模板的描述不再采用模板本身，而是采用分层梯度方向直方图特征(PHOG)对目标模板进行表示，PHOG特征具备空间结构性，对目标类别有很强的辨别力，能够提供更好的分类性能，而且该特征维数少，可加快处理速度. 二是对稀疏表示的数学模型进行优化，将目标外观部分和其他噪声部分进行拆分建模，并利用PCA增量学习的方式不断更新目标跟踪模型来适应跟踪过程中的目标变化.

1 L1范数跟踪

1.1 粒子滤波框架

粒子滤波是估计随机变量后验概率分布的工具，通常包括两个部分：预测和更新. 假设t帧时刻，定义xt为目标位置信息的状态值，定义z1:t={z1，z2，…，zt-1}为从第一帧到t-1帧的观察值，则粒子滤波通过下面两个步骤计算t帧时刻的目标信息

(1)

(2)

(3)

为了避免退化情况，样本要根据其权值大小进行重采样，即以权值较大粒子进行复制来代替权值较小的粒子.

1.2 稀疏表示

在L1跟踪中，候选目标采样都可以用字典模板T=[t1t2…tn]∈Rd×n(d≫n)稀疏的线性表示，其中n为目标模板个数，d为模板维数，每一个目标模板都会以一维列向量进行存储. 目标模板中经常掺杂了一些噪声或者遭遇遮挡的情况，因此候选跟踪目标y∈Rd可以由字典模板T近似表示为

(4)

式中：a=[a1a2… an]T∈Rn为候选目标系数向量；ε为含有非0值的误差向量；非0值所对应y中的位置表示被噪声干扰或者被遮挡. 由于噪声干扰具有随机性，无法进行量化描述，但对于遮挡情况，可以采用琐碎模板I=[i1i2…id]∈Rd×d进行描述为

(5)

式中：琐碎模板ii∈Rd为只包含一个非0值的向量；e=[e1e2…ed]T∈Rd为琐碎模板的系数向量. 假设每一个候选目标可以用目标模板和琐碎模板稀疏表示，则上式可以通过L1最小化求解

(6)

由于误差向量e可以表示任意稀疏噪声，所以可以处理各种目标外观变化的情况.

2 目标跟踪算法

2.1 分层梯度方向直方图(PHOG)特征

分层梯度方向直方图(pyramid histogram of oriented gradients，PHOG)是一种描述空间形状的特征向量，具有较强的抗噪性能，广泛应用于图像检索等模式识别工作中，并已取得稳定、良好的效果. 本文采用该特征作为跟踪目标的向量化表示.

PHOG特征提取方法如下：

① 获取图像边缘. 利用Canny边界检测算法提取目标模板的边缘，而PHOG特征就是在目标边缘的位置进行提取. PHOG描述的是目标形状特征.

② 塔式分层结构. 将目标模板分为L层，第0层为目标模板本身，第i层则将目标模板沿行列两个方向均分割成2i个单元，共形成4i个区域来进行直方图统计，这样每一层的子区域都是前一层子区域的1/4.

③ 梯度方向直方图统计. 将[0，180°]平均分为K个区间，在目标模板中检测到边缘的位置进行HOG特征提取，并在所有层的所有子区域进行梯度直方图统计.

④ PHOG特征获取. 将所有层所得的向量串联起来得到一个K∑4i维的列向量，即作为该目标模板的PHOG特征，并对其进行归一化处理.

图1为PHOG特征示意图，第1行为目标模板和不同塔层的区域划分，第2行为各个塔层所对应的梯度方向直方图统计. 从图1中可以看出，同一类别的物体，具有相似的PHOG分布特征，而非同类别的物体，其PHOG分布特征差异很大.

2.2 跟踪目标模型

在跟踪过程中，根据图像仿射变换对相邻帧间的目标运动进行建模. 设状态变量xt由6个仿射参数构成：xt={xt，yt，θt，st，αt，φt}，其中xt，yt，θt，st，αt，φt分别定义坐标x，y变换、旋转角度、尺度、长宽比和歪斜变化. 通过使用xt作为仿射变换的参数，可以从图像zt中获得兴趣区域并统一归一化为目标模板的大小. 使用高斯分布对状态变化分布p(xt|xt-1)进行建模，且假设6个仿射参数相互独立. 观察模型p(zt|xt)反映了候选目标与目标模板的接近程度，通过使用L1最小化方法进行求解.

L1跟踪通过解方程(6)来求取候选目标的最佳位置，但是由于表征目标模板的向量维数很高，所以计算复杂耗时明显. 为了更加有效地描述目标模板和进行稀疏求解，本文采用子空间学习和稀疏表示的方法对目标模型进行建模，也可以理解为通过PCA方法将子空间学习引入到L1跟踪的框架里. 对跟踪目标进行如下建模

(7)

式中：y为观察向量；U为PHOG特征经PCA处理后得到的基向量矩阵；z为基向量系数；e为误差项也即琐碎模板系数. 相区别于L1跟踪框架中的模板项，不再由目标模板和琐碎模板组成，而是由PCA基向量和琐碎模板组成. 可以通过下式对式(7)进行求解

(8)

与式(6)不同的是，L1跟踪中不论是目标模板还是琐碎模板其模板系数都应该是稀疏的，而式(8)中PHOG特征的PCA基向量系数并不是稀疏的，只有琐碎模板的系数才是稀疏的(当琐碎模板的数量远大于基向量个数的时候，这个模型仍然可以是一个稀疏表示).

在预测阶段，在第i个采样状态xi下，每一个候选模板的观测似然概率可以用下面的公式表示为

(9)

然而，式(9)是在没有发生遮挡的情况下的概率，当遮挡发生时，这里采用将遮挡部分和非遮挡部分分开处理的方式，按照式(10)来表示观测概率

(10)

2.3 更新目标模型

在跟踪过程中，更新目标跟踪模型对处理目标外观变化起很重要的作用. 如果不更新模板，模板就不能适应因光照或者姿态改变而发生的外观变化；如果更新模板过于频繁，由于每次更新都会引入小的误差，这些误差会随着频繁更新而被积累最终产生漂移问题导致跟踪失败. 为此，由于琐碎模板的稀疏系数可以用来检测遮挡，可根据遮挡情况选择更新时机. 首先，根据琐碎模板系数，将其映射为2D图，图中非零像素就表示该位置被遮挡. 其次，根据下式计算遮挡比率

(11)

设定两个阈值T1与T2来描述遮挡的程度(例如T1=0.1，T2=0.6). 最后，根据η的取值范围判定遮挡程度. 如果ηT2说明目标有大部分遭遇遮挡，这种情况下则放弃使用该采样模板进行更新. 当积累了足够的样本模板以后，采用增量PCA的方法对目标跟踪模型进行更新.

3 实验结果与分析

本文算法的实验硬件平台为Intel (R) Core i3 3.4 GHz处理器，内存4 GB的PC机，在Matlab 环境下进行实现. 至于PHOG特征，为了防止过拟合的问题，取L=3，K=20，这样每一个目标模版可以用420维向量进行表征. 式(8)中的正则化常量λ设为0.05，为平衡算法的效率和精度，在所有实验中取粒子数为600并且每5帧进行一次更新. 为了验证算法的有效性，将本文算法与4种经典传统算法进行比较，包括L1[10]，MIL[11]，VTD[12]，FragTrack[13]，通过实验给出了定性和定量的比较结果.

3.1 定性分析

实验中选取了3段有挑战的视频序列作为测试视频(Occlusion2，Car11，Jumping)，所选用的视频中包含了目标遮挡、光线变化以及目标快速运动等具有代表性的目标跟踪难题. 为更好地比较几种算法的跟踪精度，将实验结果同时标注在同一视频帧上，其中L1对应黑色框，MIL对应蓝色框，VTD对应绿色框，FragTrack对应黄色框，本文算法对应红色框，如下文所示.

① 目标遮挡. 在Occlusion2的视频序列中，目标被严重遮挡，当在目标伴有歪头等仿射变化的时候，由于本算法将目标形变参数纳入目标估计的考量范畴，所以在处理350帧和470帧的时候能够很好的随目标歪头而跟着旋转，并且在遮挡情况下仍保持很好的精度，其他几种算法虽也能成功跟踪目标，但精度却不及本文算法，并且在第700帧时候目标被严重遮挡，通过图2可以看出本文算法较其他几种算法能够获得更好的跟踪结果.

② 光线变化. Car11序列中目标车辆在夜间行驶，光线条件差，而且周围光源对跟踪任务也有干扰，跟踪难度大. 图3是各个算法的跟踪效果展示，从跟踪结果可以看出，FragTrack在第150帧的时候开始发生漂移，一直到视频结束，未能再次捕获目标，跟踪失败；而L1、MIL和VTD在第250帧之前一直能够跟踪目标车辆，虽然有跟踪偏移但是并没有丢失跟踪目标，到250帧之后，对面有车辆靠近的时候，这3种算法转而跟踪到了对面的车辆上面，未能成功跟踪到最后；但是本文提出的算法能够从始至终很稳定的跟踪目标，即使在光线变化，相似目标干扰的情况下均保持了很好的跟踪性能.

③ 快速运动. 由于传统算法通常是基于相邻帧目标变化微弱的假设进行建模，故在应对快速变化的运动目标时容易发生丢失跟踪. 图4为Jumping视频序列，目标一直处于运动过程中，这为跟踪增加了很大的难度. 不适应这种快速变化的VTD算法很快就丢失跟踪目标；而L1和FragTrack在第100帧的时候也已经发生漂移，只有MIL和本文算法能够成功稳定地跟踪处于快速运动的目标，从第150及第200帧可以看出，在跟踪精度上本文算法要明显优于MIL算法.

3.2 定量分析

跟踪误差定量分析中，本文采用常用的中心误差准则，定义为目标实际位置与手动标注位置之间的均方根. 如图5所示，其中横坐标为图像帧序号(frame number)，纵坐标为以像素为单位的跟踪误差(tracking error). 从跟踪误差曲线可以看出，在Occlusion2、Car11和Jumping 3个视频序列的实验中，本文算法(红色实线)都以最小的跟踪误差明显优于目前几种主流的目标跟踪算法.

跟踪算法中最耗时的部分为模板系数的计算过程，L1跟踪是通过LASSO方法进行系数求解，其算法复杂度为O(d2+dk)，其中d为目标模板的向量维数，k为模板个数，通常d≫k. 本文算法在L1跟踪基础上进行改进，复杂度降为O(ndk)，其中n为算法执行迭代次数，有效提升了算法效率.

4 结 论

提出了一种基于稀疏表示和粒子滤波的在线目标跟踪算法，通过采用具有强区分度的分层梯度方向直方图(PHOG)特征作为目标模版的基向量，加上琐碎模板一起作为稀疏表示的字典来对跟踪目标进行建模. 对目标状态进行建模的时候，将目标遮挡部分与非遮挡部分进行拆分，加强了对遮挡情况的检测，并利用PCA增量学习方式来更新目标跟踪模型，很好地克服了在跟踪过程中由于目标形变和遮挡所带来的跟踪困难，并通过实验验证了该算法的有效性和鲁棒性.

[1] Avidan S. Ensemble tracking[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2007，29(2):261-271.

[2] Babenko B， Yang M H， Belongie S. Visual tracking with online multiple instance learning[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.[S.l.]: IEEE， 2009:983-990.

[3] Zhang K， Zhang L， Yang M H. Real-time compressive tracking[M]. Berlin, Heidelberg: Springer, 2012.

[4] Black M J， Jepson A D. Eigentracking: robust matching and tracking of articulated objects using a view-based representation[J]. International Journal of Computer Vision， 1998，26(1):63-84.

[5] Comaniciu D， Ramesh V， Meer P. Kernel-based object tracking[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2003，25(5):564-577.

[6] Ross D A， Lim J， Lin R S， et al. Incremental learning for robust visual tracking[J]. International Journal of Computer Vision， 2008，77(1-3):125-141.

[7] Porikli F， Tuzel O， Meer P. Covariance tracking using model update based on lie algebra[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]: IEEE， 2006:728-735.

[8] Li H， Shen C， Shi Q. Real-time visual tracking using compressive sensing[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]: IEEE，2011:1305-1312.

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

[10] Mei X， Ling H. Robust visual tracking using L1 minimization[C]∥Proceedings of IEEE 12th International Conference on Computer Vision. [S.l.]: IEEE，2009:1436-1443.

[11] Jia X， Lu H， Yang M H. Visual tracking via adaptive structural local sparse appearance model[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR).[S.l.]: IEEE， 2012:1822-1829.

[12] Kwon J， Lee K M. Visual tracking decomposition[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR). [S.l.]: IEEE，2010:1269-1276.

[13] Adam A， Rivlin E， Shimshoni I. Robust fragments-based tracking using the integral histogram[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. [S.l.]: IEEE， 2006:798-805.

(责任编辑：李兵)

Sparse Representation and Particle Filter Based Online Object Tracking Algorithm

WANG Hai-luo， WANG Bo， GAO Zhi-feng， ZHOU Zhi-qiang， LI Sun

(School of Automation， Beijing Institute of Technology， Beijing 100081， China)

Changes of object appearance and occlusion always lead to tracking performance degradation or drift problem during tracking. To solve these problems， a sparse representation and particles filter based online tracking algorithm was proposed which used pyramid histogram of oriented gradients (PHOG) to describe the object template. In the framework， the candidate template can be represented by object templates and trivial templates sparsely， and then L1 minimization was exploited to find the optimal solution. To ensure the accuracy of tracking， the object function was divided into two parts to model the occlusion part and non-occlusion part separately. Both qualitative and quantitative evaluations on challenging image sequences demonstrate that the proposed algorithm performs favorably against several state-of-the-art methods.

sparse representation; PCA incremental learning; PHOG feature; on-line object tracking

2015-01-07

王海罗(1985—)，男，博士生，E-mail：hailuo0112@163.com；汪勃(1963—)，男，教授，博士生导师，E-mail:wangbobit.edu.cn.

TP 391

A

1001-0645(2016)06-0635-06

10.15918/j.tbit1001-0645.2016.06.016