基于稀疏表达的超像素跟踪算法

齐苑辰吴成东 陈东岳 陆云松

(东北大学信息科学与工程学院 沈阳 110819)

基于稀疏表达的超像素跟踪算法

齐苑辰*吴成东 陈东岳 陆云松

(东北大学信息科学与工程学院 沈阳 110819)

该文针对真实场景下视频跟踪过程中可能出现的目标形变、运动和遮挡等问题，该文分别构建了基于超像素局部信息的判别式模型和基于颜色与梯度全局信息的产生式模型，通过两者的结合提升了目标表观特征描述的可区分性和不变性；此外，提出一种基于稀疏主成分分析的更新策略，在更新特征字典的同时减少其冗余度，在判别式模型的更新阶段分别对每帧图像获得的跟踪结果进行二次判别从而避免漂移现象的发生。实验结果表明，与其它跟踪算法相比，该算法在应对目标姿态变化、背景干扰以及遮挡等复杂情况时具有更好的稳定性和鲁棒性。

计算机视觉；目标跟踪；稀疏表达；超像素分割；稀疏主成分分析

1 引言

基于视频的运动目标跟踪是指在视频序列中对目标状态进行估计的过程。作为计算机视觉领域的重要研究方向，目标跟踪技术在视频监控、人机交互以及智能机器人等领域都有着广泛的应用。一个完整的跟踪系统包括运动模型、搜索策略以及观测模型3个部分。其中，运动模型用于预测目标可能的状态，一般通过卡尔曼滤波[1]或者粒子滤波[2,3]得以实现；搜索策略用于寻找目标状态的最优估计，均值漂移(Mean Shift)[4]以及滑动窗口(Sliding Window)[5]等都可以达到此目的；观测模型用来度量候选目标与参考目标之间的相似性，欧氏距离、扩散距离[6]、交叉元(Cross-bin)距离[7]等都可以作为度量标准。

观测模型必须建立在对目标表观的精确描述的基础上。采用全局特征建立目标观测模型是视频跟踪算法中常见的研究思路[8-11]，此类算法在目标为刚体且观测视角变化不大的情况下能够取得较好的效果。但是当目标在运动过程中发生比较剧烈的几何形变和表观变化时，这种全局方法就会失效并直接引发跟踪漂移问题。另一种研究思路是采用局部特征建立目标观测模型，将目标视为若干个子图像块的集合，通过对子图像块的跟踪实现对整体目标的跟踪。由于子图像块内图像模式的不变性较强，这类算法对于目标形变和遮挡问题处理能力更强。文献[12]将子图像块的表示纳入到稀疏表达框架下，通过对子图像块集合的训练建立字典，并将候选区域的观测模型的估计问题转化为该区域内子图像块的稀疏系数求和问题，从而实现对目标状态的最优估计。文献[13]引入超像素分割算法以减少传统算法中的硬性分块对于目标边缘信息的破坏，通过对超像素进行聚类获取目标区域的特征分布以及每个超像素从属于某个类别的概率分布，最后整合候选区域所有超像素的后验概率给出候选样本属于目标的概率。这类算法虽然对于目标形变和遮挡问题的鲁棒性更好，但是当目标图像块与背景图像块的色彩特征相似时容易产生误判，并将这种误判造成的误差引入到更新阶段，从而导致跟踪失败。

通过分析可知，全局信息可区分度较高，但不变性差；而局部信息不变性好，但可区分性差。观测模型的建立包括产生式和判别式两种，前者强调模型的完整性和不变性[4,8,10,12]，后者旨在更好地区分目标与背景[5,11,13]。考虑到两者的互补性，本文分别在全局特征与局部特征的基础上建立产生式模型与判别式模型，并通过两者的融合实现对目标的有效描述。因为在跟踪过程中目标可能发生各种变化，所以为了获得更可靠的跟踪结果需要对模板进行在线更新。目前已提出很多方法(模板更新[9]，增量子空间学习[10]，在线分类器[5]等)，然而直接使用跟踪结果对模板进行更新会造成误差累积，进而导致跟踪漂移。这种现象在有遮挡的情况下表现得尤为严重，为解决这一问题，本文在模板更新阶段增加了对跟踪结果的判别机制。

2 算法描述

跟踪问题被广泛理解为贝叶斯估计问题。令Xt表示目标在t时刻的状态，Y1:t表示从初始帧累加到t时刻的观测序列，则待跟踪目标的后验概率p(Xt|Y1:t)可以由式(1)定义：

其中，p(Yt|Xt)表示观测模型；p(Xt|Xt-1)表示运动模型。利用最大后验概率(Maximum A Posteriori, MAP)通过在t时刻得到的候选样本中搜索使后验概率p(Xt|Y1:t)达到最大的样本，便可以确定t时刻目标状态的最优估计，如式(2)所示。

因为观测模型必须建立在对目标表观信息的准确描述的基础上，所以本文分别基于全局和局部信息建立全局和局部模型，并将观测模型分解为这两者的乘积的形式，从而体现了目标全局与局部信息的融合，其数学形式为

其中，p(Yt|)表示候选样本对应的观测模型；pg(Yt|)表示基于全局信息对构建的观测模型；pl(Yt|)表示基于局部信息对构建的观测模型。之所以选择这种分解策略是因为考虑到目标的全局和局部信息各自的优点及其互补性；而之所以选择这种乘法的融合机制是因为局部和全局这两种模型是彼此独立的，两者的计算将分别在4.1节和4.2节给出详细说明。

3 运动模型

其中，N表示均值为ˆX1t-，协方差矩阵为Ψ的正态分布；考虑到目标状态内部变量彼此间相互独立所以假设Ψ为对角阵，其对角线上的元素分别为目标在位置和尺度上变化的方差。

运动模型用于描述目标在相邻帧的状态的变化规律，在对目标运动规律没有先验知识的情况下，可假设运动模型服从正态分布：

4 观测模型

4.1 基于超像素的判别式模型

局部模型建立的基础是局部特征的提取，而局部特征提取的前提是局部区域的分割。常见的基于局部特征的跟踪算法大多选择基于矩形格的硬性分割方法[11]，此类算法虽然操作简单但会破坏目标与背景的边界以及目标内部的纹理结构。而超像素分割[14]技术将图像中位置相邻且颜色相似的像素划分到一个小区域，从而可以在不破坏边界的同时实现对图像的分割。因此，本文采用基于超像素分割的局部区域划分策略。

假设共有m帧训练图像，在字典的建立阶段共分4个步骤，如图1所示。首先围绕目标中心截取矩形区域作为观测区域，矩形边长为目标的外接矩形的对角线长度τt′的λs倍，如图2(a)所示红色线表示跟踪结果，蓝色线表示观测区域的范围。通过对观测区域做超像素分割可以获得如图2(b)所示的分割结果。在判定类别标签步骤，对于首帧图像，由于红色跟踪框是手动框的，所以红色框与蓝色框之间的回字形区域一定是属于背景的，故将中心落在该区域的超像素分类到背景区域，并利用这些超像素对中心落在红色框内部的超像素进行重建，对于重构误差大于某个指定阈值的超像素将其判定为目标，否则判定为背景。如图2(c)所示，红色星号表示被划分到目标区域的超像素的中心，其中重构误差的计算将在式(5)后面给出介绍。而对于其它帧图像，对观测区域内分割得到的每个超像素分别用已经求得的目标字典和背景字典进行重构，并根据得到的重构误差对其类别属性做判断，判断原则在第5节字典更新环节将做详细介绍，最后使用被分到目标区域和背景区域的超像素分别建立目标字典和背景字典。

图1 字典建立的流程图

在跟踪阶段，当获得新图像时，首先围绕上一时刻目标中心建立如图3(a)所示的观测区域，通过对该区域做超像素分割可获得如图3(b)所示的k个超像素块。对每个超像素块分别提取颜色直方图特征记为yi,i=1,2,…,k ，每个yi可以用前面训练好的字典D=[d1d2…dn]进行稀疏重构，如式(5)所示。

其中，dj,j=1,2,…,n表示字典D的基向量；αij表示yi的第j个稀疏系数；ai=[αi1αi2… αin]T∈表示yi的稀疏系数向量；ri∈表示误差向量。稀疏表达一方面希望yi在字典D上的稀疏系数向量ai中非零元素尽可能地少，另一方面又希望减小重构误差。因此可由式(6)求得稀疏系数向量ai的解。

其中，参数λ用于控制重构误差与系数稀疏性之间的比例，具体求解方法详见文献[9]。在针对超像素单元iy进行稀疏重构时，如果iy与字典中的某些基向量越接近，那么重构误差就越小，反之则越大。因为每个超像素属于目标的概率与属于背景的概率的和等于1，因此建立表达式为

其中，ω1和ω2分别表示目标和背景两个类别；P(ω1|yi)和P(ω2|yi)分别表示yi属于目标和背景的后验概率，如图3(c)，图3(d)所示；和分别表示用目标字典D+和背景字典对yi重建后获得的重构误差。如果yi属于目标，那么必定大于，利用式(7)计算得到的P(ω1|yi)也必定会大于P(ω2|yi)，显然这符合yi属于目标的假设；如果yi属于背景，那么必定小于，利用式(7)计算得到的P(ω1|yi)也必定小于P(ω2|yi)，这同样符合yi属于背景的假设。

考虑到超像素块内像素特征的连续性和相似性，可认为每个像素s从属于目标和背景的概率等于该像素所在的超像素iy从属于目标和背景的概率。即

根据贝叶斯定理，对矩形观测区域内的所有像素综合考虑，即可以得到目标和背景在观测区域内的概率密度分布函数p(s|ωu)，如式(9)所示。

其中，s表示观测区域内的每个像素；p(s)表示像素的概率密度函数；P(ω1)=1-P(ω2)表示类别的先验概率。将t时刻的第l个候选框看作是一个分类器，即认为框内区域为目标而框外区域为背景，则该分类器错误分类的加权平均风险可定义为

其中，P1为对应的跟踪框内像素si,i=1,2,…,本属于背景却被错分为目标的风险；P2为位于观测区域内但是却并不属于当前跟踪框的像素本属于目标却被错分为背景的风险。由于在跟踪问题中，跟踪框一般被定义为目标的最小外接矩形，因此模型更加希望使像素被错分为背景的风险最小化，但考虑到实际问题中对于每个像素的后验概率P(ωu|s)的估计可能存在误差，仅考虑P2会降低算法的鲁棒性，因此分别为P1和P2赋予权重λ1和λ2，一般情况下λ1＜λ2，且λ1+λ2=1。综合式(8)到式(10)可知，跟踪问题已经转化为在贝叶斯框架下寻找一个跟踪框使得R()达到最小的问题。现以“bird”视频的第6帧为例说明其合理性。图4(a)给出了围绕目标中心由小到大依次建立的21个候选框，图4(b)中的3条曲线分别描述了利用本文方法对上述候选框计算得到的P1,P2和R(这里λ1=0.4, λ2=0.6)，其中最小值Rmin=0.044对应的候选框就是在当前时刻对目标状态的最优估计，如图4(c)所示。

图2 字典建立阶段样本类别标签的判定

图3 跟踪阶段超像素后验概率图的生成

图4 平均风险估计值曲线及其最小化示意图

加权平均风险R可以看作是对错误分类概率的一种有偏估计，它可以用于估计目标局部模型pl(Yt|)，为了与全局模型更好地融合，构建如式(11)所示的基于局部特征的目标观测模型。

4.2 基于全局信息的产生式模型

在获得候选样本局部模型的基础上，为了更精确地跟踪目标需要对目标的整体信息加以把握。在训练阶段通过提取跟踪框内图像的色调、饱和度、亮度以及梯度共4个特征来建立目标的全局模板ht′,f(t′=1,2,…,m;f=1,2,…,4)，其中f表示4种特征的索引。在跟踪阶段令,f=1,2,…,4表示对候选框提取的4个特征直方图，则基于全局信息的观测模型可由式(12)计算：其中，η表示权重参数；φ表示扩散距离函数，用来计算两个直方图向量的距离。

5 字典更新策略

字典更新可以分为样本的选择与基向量的更新两部分。在样本选择阶段，本文并未简单地根据跟踪框进行正负样本的划分，而是根据观测区域内的超像素块iy在目标和背景字典上的重构误差和对其类别属性做出判断。如果＜，则yi被划分为正样本，否则为负样本。在基向量更新阶段，引入稀疏主成分分析技术[15](Sparse Principal Component Analysis, SPCA)。与传统的主成分分析不同，SPCA计算得到的基向量并非原始样本的一般性线性组合，而是直接从样本集中选取表征能力和互补性最强的样本作为基向量。该方法在保持了稀疏表达类算法在超完备性和有效性方面的优势的同时，还能保证最后得到的基向量具有明确的物理含义，因此更适合应用于自然场景下的非特定目标跟踪问题。

令F=[f1f2… fN]表示由训练样本构成的矩阵，那么A=FTF可以被定义为关于样本的格拉姆(Gramian)矩阵，则SPCA的第1个基向量x*为

其中，||x||0≤γ表示向量x中非零元素的个数小于等于γ 。为了减少约束项现将式(13)改写为

其中，ρ表示惩罚项，其值越大，x的稀疏度越高。使用文献[15]可以对式(14)求解，解后便可以得到第1个稀疏特征向量1x，令1=AA，将1A,1x代入Ai+1=Ai-(Aixi)xix,i=1,2,…,n -1便可以得到A2，将A2代入式(14)可获得第2个稀疏特征向量x2，将上述过程迭代n次便可以获得n个特征向量x1,x2,…,xn。对于每个向量xi，如果其第c个元素xi(c)≠0，则选取F中第c个列向量fc作为字典的基向量。由于每个特征向量ix的计算相当于在F中选择了γ个样本，且不同的ix选择的样本不同，所以n次迭代共选择nγ个样本来建立字典D，表示为

其中，dj表示字典的第j列。基于上述分析，可以发现基于SPCA学习的字典可以在全面表征目标表观的同时避免冗余。在对其进行更新时，首先利用新获得的样本与旧字典一起构建新样本，之后通过对新样本做SPCA便可以获得更新后的字典。

6 实验分析

实验在Matlab R2012a环境下进行，采用简单线性迭代聚类(Simple Linear Iterative Clustering, SLIC)[14]算法完成对图像的分割，并利用色度-饱和度-亮度颜色空间下的归一化直方图作为特征来表征分割后获得的超像素。SLIC算法包括超像素个数和空间近似权重两个参数，前者越小表示分得的超像素个数越少，后者越小表示分得的超像素内部越光滑，图像边界信息保留的越好，在本文的所有实验中两者分别取10和300。式(4)中标准差取3～8，式(6)中λ取0.01，式(10)中sλ取1.50，式(12)中η取5，式(14)中ρ取90。考虑到基于全局信息的产生式模型主要强调特征的不变性，而基于局部信息的判别模型则对于目标和背景的变化比较敏感，因此本文算法只对局部模型使用的字典进行更新。在跟踪的初始阶段为了获得训练数据，在第1帧目标初始位置由手动框出，后9帧通过开源的VLFeat库函数对目标中心作出估计。

6.1 定性分析

为了验证本文算法的有效性，文中给出了“bird”，“woman”视频的测试结果，并分别与1范数(L1)算法[9]、视频跟踪分解(Visual Tracking Decomposition, VTD)算法[8]以及块跟踪(FragTrack)算法[16]做了比较。其中，L1算法是在稀疏表达框架下建立的基于全局信息的跟踪算法；VTD算法是在模型分解基础上建立的基于全局信息的跟踪算法；FragTrack算法是在积分直方图基础上建立的基于局部信息的跟踪算法，均与本文算法的提出背景具有相关性，与之相比较更能体现出本文算法的稳定性和鲁棒性。

实验 1 图5给出了4种算法在“bird”视频[13]上获得的跟踪结果。该视频中目标发生了较大程度的姿态变化，而且受背景干扰严重。从第13帧开始VTD算法由于受到周围几只飞翔的小鸟的影响，跟踪框开始发生漂移，直到第16帧目标完全从框内消失；同样受此干扰，L1算法获得的结果从第49帧开始逐渐偏离目标的真实位置，直到第60帧跟踪框完全漂移到背景上；FragTrack算法从第24帧开始只能跟踪到部分目标，直到第72帧完全失效。与这3种算法相比，本文算法因为采用了局部与全局信息相融合的目标表示方法，因此获得了更精准的跟踪结果。

实验 2 图6给出了4种算法在“woman”视频[16]上获得的跟踪结果。该视频中目标受到其它物体长时间的干扰和遮挡影响，整个视频长度为530帧，待跟踪的目标为行走的女士。从第120帧开始由于受到周围白色轿车的干扰，VTD, L1以及FragTrack 3种算法的跟踪结果均出现了漂移，直到第157帧3种算法完全失效。与这3种算法相比，本文算法由于在字典更新阶段对样本类别的判定增加了判断机制，因此在面对较长时间遮挡以及背景干扰时依然能够很好地捕捉到目标。

6.2 定量分析

4种算法在“bird”，“woman”两段视频上的定量对比分析如图7所示，横轴表示图像帧数，纵轴表示4种算法获得的目标估计相比于目标真实位置的中心误差，以像素为单位。为了保证实验数据的可靠性，每个算法都运行5次并将求出的平均值作为最后的定位误差。通过对图5，图6，图7进行分析，可以看出本文算法很好地解决了目标在跟踪过程中可能出现的各种变化，并取得了比较精确的结果。

图5 “bird”视频序列跟踪结果

图6 “woman”视频序列跟踪结果

图7 VTD算法、L1算法、FragTrack算法与本文算法跟踪结果的定量对比

7 结束语

本文提出一种基于目标局部与全局信息相融合的鲁棒跟踪算法，通过分别计算每个候选样本的观测模型来确定最终的目标估计。在字典更新阶段利用SPCA技术在添加新信息的同时删除旧信息，从而更准确地对目标在跟踪过程可能发生的各种变化做出描述，且保证字典的基向量间彼此互补。针对姿态变化、背景干扰、遮挡等情形，在真实场景视频下对本文提出的算法进行测试，实验结果表明，与其它算法相比本文算法具有更好的鲁棒性，能够更精准地定位目标。

[1] Yilmaz A, Javed O, and Shah M. Object tracking: a survey[J]. ACM Computing Surveys, 2006, 38(4): 2371-2378.

[2] Wang Dong, Lu Hu-chuan, and Yang Ming-hsuan. Least soft-threshold squares tracking[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Portland, USA, 2013: 2371-2378.

[3] Yang Fan, Lu Hu-chuan, and Yang Ming-hsuan. Robust visual tracking via multiple kernel boosting with affinity constraints[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2014, 24(2): 242-254.

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

[5] Grabner H and Bischof H. Online boosting and vision[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, USA, 2006: 260-267.

[6] Ling Hai-bin and Okada K. Diffusion distance for histogram comparison[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, USA, 2006: 246-253.

[7] Leichter I. Mean shift trackers with cross-bin metrics[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(4): 695-706.

[8] Kwon J and Lee K. Visual tracking decomposition[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, USA, 2010: 1269-1276.

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

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

[11] Babenko B, Yang Ming-hsuan, and 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] Jia Xu, Lu Hu-chuan, and Yang Ming-hsuan. Visual tracking via adaptive structural local sparse appearance model[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Providence, USA, 2012: 1822-1829.

[13] Yang Fan, Lu Hu-chuan, and Yang Ming-hsuan. Robust superpixel tracking[J]. IEEE Transactions on Image Processing, 2014, 23(4): 1639-1651.

[14] Achanta R, Shaji A, Smith K, et al.. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11): 2274-2282.

[15] D’Aspremont A, Ghaoui L, Jordan M, et al.. A direct formulation for sparse PCA using semidefinite programming[J]. Society for Industrial and Applied Mathematics (SIAM) Review, 2007, 49(3): 434-448.

[16] Adam A, Rivlin E, and Shimshoni I. Robust fragments-based tracking using the integral histogram[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, USA, 2006: 798-805.

齐苑辰： 女，1983年生，博士生，研究方向为计算机视觉、智能视频监控、机器学习.

吴成东： 男，1960年生，博士，教授，博士生导师，研究方向为图像智能处理、无线传感器网络、建筑智能化技术、机器人控制、多源信息融合.

陈东岳： 男，1980年生，博士，副教授，研究方向为图像数据挖掘、仿生视觉计算模型、目标检测跟踪与识别技术.

Superpixel Tracking Based on Sparse Representation

Qi Yuan-chen Wu Cheng-dong Chen Dong-yue Lu Yun-song
(College of Information Science and Engineering, Northeastern University, Shenyang 110819, China)

A novel tracking algorithm is proposed that can work robustly in real-world scenarios, in order to overcome the problems associated with severe changes in pose, motion and occlusion. A discriminative model based on the superpixels and a generative model based on global color and gradient features are constructed respectively. Through combining these two models, the distinguishing and invariance of target appearance features description are increased. Furthermore, an update strategy based on sparse principal component analysis is proposed, which can reduce the redundancy of feature dictionary when it updates. A discrimination mechanism is added in the update process of discriminative model to alleviate the drift problem. The experimental results demonstrate that the proposed algorithm performs more stable and robustly compared with several state-of-the-art algorithms when dealing with complex situations such as pose variation, background interference, and occlusion.

Computer vision; Object tracking; Sparse representation; Superpixel segmentation; Sparse principal component analysis

TP391.4

A

1009-5896(2015)03-0529-07

10.11999/JEIT140374

2014-03-19收到，2014-07-14改回

国家自然科学基金(61273078, 61005032)，中央高校基本科研业务费(N1106040065032)，国家科技支撑计划项目(2013BAK02B01-02)和辽宁省科技计划项目(2013231025)资助课题

*通信作者：齐苑辰 qiyuanchen649@163.com