一种基于稀疏表示的判别式目标跟踪算法

戴平阳，洪景新，李翠华，詹小静

（厦门大学信息科学与技术学院，福建 厦门361005）

目标跟踪是计算机视觉领域的热点研究课题，它在智能视频监控、人机交互、精确制导以及虚拟现实等领域有着广泛的应用.目标跟踪的主要难点包括复杂场景下目标平移、旋转、光照变化、视角变化等目标外观变化，目标的遮挡与自遮挡，动态场景中嘈杂背景干扰及雨、烟、雾、阴影等因素干扰.视觉目标跟踪问题近十多年来已经进行了广泛而又深入的研究，但实践表明，复杂场景下的运动目标跟踪算法还远未成熟.因此在复杂场景下设计一个鲁棒、准确地进行视觉目标跟踪的算法仍然是一项具有挑战性的课题.

目标跟踪指的是图像序列中对目标的运动状态进行持续估计与预测过程.目标外观模型的好坏是跟踪算法的关键.根据目标模型建立方法不同，通常将跟踪方法分为两类：产生式模型和判别式模型.基于产生式模型的跟踪方法首先学习一个外观模型作为目标观测，然后在目标可能运动的范围内搜索与该生成模型最相似的区域，从而实现目标的跟踪.Black［1］等提出了一种子空间学习方法，采用主成分分析方法建立感兴趣目标的外观模型来进行跟踪；Zhou［2］等则在粒子滤波框架中嵌入自适应的外观变化模型来处理跟踪过程中目标外观变化.Ross等［3］将提出一种增量子空间更新方法，通过渐进获取子空间的基构建跟踪框架，以适应目标外观的动态变化.基于判别式模型的跟踪方法将目标跟踪表示成一个分类问题，通过选择合适的特征及分类器将目标从背景中区分开来.Collins等［4］提出了一种基于判别式在线学习跟踪算法，该算法在线选择具有背景和前景区分性的RGB颜色值的线性组合来作为跟踪特征.Wang等［5］将Haar特征应用于跟踪领域，通过在特征空间中使用Fisher判别方法，选择得到有判别力的特征，在粒子滤波框架中提出一种具有判别力的在线跟踪算法.Avidan［6］利用AdaBoost算法从弱分类器中学习得到一个强分类器来进行目标跟踪.Grabner等［7］则设计一个在线Boosting分类器，该分类器从候选的特征池中选择最具有判别力的特征来进行目标跟踪.

近年来，稀疏表示成为计算机视觉的研究热点，出现了大量基于稀疏表示的目标跟踪算法［8－11］.Mei等［12］最早将稀疏表示引入跟踪领域，提出了L1跟踪器.该算法在粒子滤波框架下用模板字典对目标建模，通过独立求解受约束的L1最小化问题得到候选区域在目标字典上的稀疏表示，以重构误差来判断当前目标位置.由于L1跟踪的目标模板是通过对目标区域抖动构建得到，因此其缺点是对于线性表示的稀疏性假设不是在所有情况下都成立.当目标发生较大遮挡或目标快速运动时，候选目标区域在目标字典单位模板对应的系数可能会出现较多的非零元素，目标的整体表示系数将不再稀疏，从而导致目标跟踪错误.

为了在目标遮挡、噪声干扰及目标快速运动等复杂场景进行鲁棒跟踪，本文将目标的稀疏表示和判别式在线学习相结合，提出了一种基于稀疏表示的判别式目标跟踪算法.该算法首先采用稀疏表示对目标进行特征提取，得到具有判别力的目标特征表示，然后利用朴素贝叶斯分类器对候选目标进行分类，选取概率最大的样本作为当前的目标估计.为了适应场景及目标外观变化，设计动态更新机制对分类器和字典进行了在线更新.和传统的基于稀疏表示的跟踪算法相比，本文算法通过目标的稀疏表示获得具有判别力的目标特征表示，而在线的朴素贝叶斯分类器则确保了目标跟踪算法的快速有效，克服了基于传统稀疏表示的跟踪算法无法在目标发生较大遮挡及快速运动等复杂场景进行鲁棒跟踪的缺点.

1 基于稀疏表示的目标外观模型

设图像序列的初始m帧为训练图像，T＝［T1，…，Tm］为目标模板集合，其中Ti∈Rd×d.为了构建目标外观的特征向量，我们采用与文献［11］类似方法.对于每个目标模板Ti，采用w×w的滑动窗口进行稠密采样，将得到的所有图像块列向量化并进行L2范数归一化，得到每个目标模板的局部字典Ti＝［t11，…，tM］，联合所有目标模板，从而得到最终的稀疏编码字典：

其中，l＝w×w表示图像块向量的维度，m表示模板数量，M表示每个模板采样得到图像块的数量.y∈Rd×d是候选目标样本，那么可以使用上述方法提取该样本的局部图像块，得到候选目标样本的采样表示：

根据稀疏表示理论，样本的局部图像块可以由稀疏编码字典D稀疏表示，可通过求解凸优化问题得到各个图像块在字典D中的稀疏编码：

其中，λ1和λ2为正则化参数.当λ2＝0时，公式（3）为L1范数稀疏编码，λ2＞0使得公式（3）为严格凸优化问题.由公式（3）可得局部图像块yi在字典D的稀疏表示：

从而得到候选样本y∈Rd×d的稀疏编码为：

通过候选样本图像块与字典中目标模板之间的投票关系，可以获得候选区域的特征表示.令稀疏字典中每个目标模板对候选样本的局部图像块进行投票，即将局部图像块的稀疏系数加权从而得到权重向量，其中为所有目标模板的第j个图像块对候选目标的第i个图像块的投票权重，C为归一化参数.因此，可以得到目标模板与候选样本的投票权重矩阵V＝ ［v1，…，vM］∈RM×M.由于权重矩阵V的对角线表示目标模板图像块与对应候选样本图像块之间的投票，因此选取X＝diag（V），X∈RM，为候选样本的特征向量.

2 基于稀疏表示的判别式目标跟踪

候选区域中，一个好的候选样本可以由目标模板字典稀疏表示，其对应的稀疏编码向量只有几个大的系数.同样地，每个局部图像块的稀疏编码向量在其对应位置的目标模板图像块上的系数也比较大，那么提取得到的特征向量则对应了这些系数中的大系数，即保留了大部分的能量.而非目标样本在字典上的表示是稠密的，能量均匀分布在字典空间.因此，目标样本与非目标样本在特征向量表示上存在很大差异.在此观测基础上，利用判别式在线学习方法，设计分类器在跟踪过程中将目标与背景区分开来.

2.1 朴素贝叶斯分类器

朴素贝叶斯分类器是一种基于独立假设贝叶斯定理的简单概率分类器.朴素贝叶斯分类器假定样本的各个属性之间相互独立，根据少量的训练数据进行参数估计.尽管变量相互独立假设现实中难以满足，但该分类器需要估计的参数少，对缺失数据不敏感，并且有着分类误差小，简单高效稳定等特点.

在跟踪问题中，样本只有2种类别属性：目标或背景，是一个二分类问题.假设目标和背景的先验概率为p（y），y∈｛＋1，－1｝，对于测试样本X，其类条件概率为p（X｜y），根据贝叶斯公式及最小错误率的贝叶斯决策准则可得二元分类器：

若选择分类器的后验概率比值作为似然函数可得：

设样本X包含M 个属性，即X＝［x1，…，xM］，并且各个属性之间相互独立，则有：

若先验概率p（y＝＋1）＝p（y＝－1），则式（7）可表示为：

利用稀疏表示的外观模型，目标由特征向量X＝［x1，…，xM］表示.特征向量X＝［x1，…，xM］每个元素代表了目标模板图像块与候选样本对应图像块的投票值.假设特征向量各个元素之间相互独立，且服从高斯分布，则朴素贝叶斯分类器的类条件概率p（X｜y）满足参数（μ＋i，σ＋i，μ－i，σ－i）高斯分布：

联合所有特征向量元素的类条件概率得到候选样本在分类器下的置信值为：

2.2 分类器更新和字典更新

在跟踪过程中，随着时间推移以及遮挡、光照、噪声干扰等因素作用，目标的外观模型会发生很大变化.因此，为了保证跟踪的准确性及鲁棒性，必须对分类器进行在线更新.对于模板字典更新采用文献［12］的方法，在跟踪过程中，使用跟踪结果图像块替换模板字典中重构误差最大的图像块，从而实现字典集合的动态更新.

在t时刻获得目标位置后，在目标周围及远离目标区域分别采样正负样本更新分类器.在跟踪过程中，设置一个动态更新参数δ，采用动态更新机制，每隔δ帧重新训练分类器.训练样本除了来自初始化训练的静态训练样本库外，还包括最近δ帧的正负样本.

2.3 算法步骤

本文的基于稀疏表示的判别式目标跟踪算法具体描述如下：

输入：视频图像序列 ｛I1，…，In｝，初始目标位置 ｛r1，…，rm｝.

输出：视频图像序列中的跟踪结果目标矩形框 ｛r1，…，rn｝.

初始化：

1）构造稀疏编码字典D，

2）获取训练样本｛Xi，yi｝，并将其保留作为静态训练样本.其中Xi∈RM为局部稀疏特征向量，yi∈｛－1，＋1｝为样本标记，

令 t＝1，…，n，

1）根据设定搜索半径r采样目标候选矩形框，稀疏编码提取得到对应特征向量｛Xi｝，

2）利用朴素贝叶斯分类器L（Xi）计算样本作为目标置信值li，

4）由当前跟踪结果获取动态训练样本，判断是否进行分类器更新.若满足更新条件，则合并静态样本与动态样本库，重新训练分类器，清空动态样本库用于收集新的样本.

3 实验结果与分析

本文算法在Visual Studio 2010上采用C＋＋和OpenCV实现.跟踪目标采用矩形框表示，初始状态在起始帧手动或自动选定.实验参数设置如下：训练图像数量m＝5，目标模板及所有候选样本均缩放为32×32像素，d＝32，滑动窗口为16×16，w＝16，滑动步长为8个像素；稀疏表示正则化参数λ1＝0.01，目标搜索半径r＝30，正样本采样半径为2，负样本圆环为目标矩形框的长边，样本数量N＝20，分类器动态更新参数δ＝5.以上参数在实验过程中对所有视频序列均固定不变.

实验在几组跟踪领域常用的图像视频序列上进行.根据测试视频的不同挑战，实验将测试视频分为3组，其中：Occlusion1和Girl视频包含了目标遮挡及外观变化难点；Animal和Jumping序列挑战在于目标快速运动及运动模糊；Car4和Car11是汽车尾部跟踪视频，其中包含了光照变化、噪声、外观变化等挑战.实验将本文算法与当前主流的6种算法进行比较：Frag［13］，L1［12］，MIL［14］，PCA［3］，PN［15］，VTD［16］.

3.1 目标遮挡及外观变化

该组视频实验主要针对严重遮挡与外观变化的目标跟踪.

Occlusion1视频序列是女子被书本遮挡场景.书本多次从各个不同方向对人脸进行遮挡，遮挡面积最大可达面部可视面积70%.实验部分结果如图1（a）所示.其中，第575帧遮挡面积达70%，6种对比算法均出现漂移、被挤压现象，而本文算法几乎不受影响.图2（a）给出7种算法在Occlusion1视频上的中心误差.该图显示，本文算法的中心误差是最小的，特别是500～600帧，6种对比算法误差很大，这一结果显示本文算法在遮挡条件下的鲁棒性.

另一个视频序列为Girl，该视频包含女子多次转动，目标外观发生巨大变化，同时还包含相似目标遮挡.实验部分结果如图1（b）所示.中心误差分析如图2（b）所示.实验结果同样表明本文算法对比其它6种算法，在目标发生遮挡与外观变化时具有鲁棒性.

图1 视频序列跟踪效果Fig.1 Tracking results of video sequences

3.2 目标快速运动及运动模糊

该组实验是针对快速运动及运动模糊的目标跟踪.

Animal视频序列的主要挑战在于目标快速运动并且背景中相似目标干扰.实验部分结果如图1（c）所示.由42帧实验结果表明，目标快速跳跃运动时，对比算法明显漂移甚至丢失目标，而本文算法依然准确跟踪目标.由图2（c）的中心误差分析图可以看出，6种主流算法中除了VTD算法外均出现较大的中心误差，跟踪效果很不理想.而本文算法的中心误差自始至终都保持在最小，显示了本文算法对于目标快速运动的鲁棒性和准确性.

Jumping视频序列是男子在室外跳绳，其脸部为跟踪目标.该视频的主要难点在于人脸的上下快速运动及其伴随的运动模糊.实验部分结果如图1（d）所示.16帧目标突然跳起，人脸模糊，Frag、L1、VTD均出现漂移.实验结果显示，在跟踪过程中，Frag、L1、VTD和PCA均逐渐丢失目标，而MIL和PN算法则向上或向下漂移，只有本文算法比较准确锁定目标.中心误差分析如图2（d）所示.

3.3 汽车跟踪视频

该组实验是针对汽车尾部进行目标跟踪.

Car4视频序列白天车辆跟踪场景，跟踪的目标为前方车辆的尾部，其主要挑战在于目标在行进过程中多次经过路桥阴影区域，带来光照剧烈变化，同时还存在外观尺度变化.实验部分结果如图1（e）所示.178帧目标第一次进入阴影区域，Frag和MIL出现轻度漂移，194帧目标完全进入阴影区域，PN开始出现漂移，240帧目标离开阴影区域，Frag发生严重漂移.304，451和620帧目标发生尺度变化，MIL丢失目标，PN和VTD也出现轻度漂移.整个跟踪过程中，L1和PCA表现十分稳定，本文算法也取得了相近的跟踪效果.中心误差分析如图2（e）所示.

Car11视频序列是夜晚车辆跟踪场景，跟踪目标也是前方车辆尾部.目标在街道穿行，期间多次发生尺度变化、光照变化及快速运动.同时，跟踪目标车辆较小，能获取的信息量较小，跟鲁棒跟踪带来很大难度.实验部分结果如图1（f）所示.目标在60，207帧快速运动，235帧发生尺度变化，MIL发生严重漂移，Frag丢失目标，除了本文算法和PCA能稳定跟踪，其它算法均出现不同程度漂移.目标在300，384帧转弯快速运动，PCA算法发生漂移，其他5种对比算法均丢失目标，只有本文算法全程准确跟踪目标.中心误差分析如图2（f）所示，与6种流行算法相比，本文算法误差一直保持最小.

为了更加直观地对比跟踪算法的准确性，我们统计了上述7种算法在6个视频序列上的中心平均误差，如表1所示.在6个视频序列测试中，本文算法有3个取得最低评价误差，2个排在第二以及1个第三，总平均误差最小.这清楚地表明本文算法在各种挑战下对目标具有良好的准确性和鲁棒性.

图2 跟踪结果中心误差Fig.2 The center position error of sequence

表1 算法平均中心误差Tab.1 Average center error pixel

4 结 论

本文提出了一种基于稀疏表示的判别式目标跟踪算法.该算法采用稀疏表示对目标进行特征提取，获得具有判别力的目标特征表示.在跟踪过程中利用朴素贝叶斯分类器对候选目标进行分类，选取概率最大的样本作为当前的目标估计.为了适应场景及目标外观动态变化，分类器和字典进行了在线更新.该算法将稀疏表示与判别式分类器结合，采用目标的稀疏表示获得具有判别力的目标特征表示，而在线的朴素贝叶斯分类器则确保了目标跟踪的快速有效，克服了基于传统稀疏表示的跟踪算法无法在目标发生较大遮挡及快速运动等复杂场景进行鲁棒跟踪的缺点.实验结果表明，与目前流行的多种跟踪算法相比，本文的算法具有良好的跟踪鲁棒性和准确性.

［1］Black M J，Jepson A D.Eigen tracking：robust matching and tracking of articulated objects using a view－based representation ［J］.International Journal of Computer Vision，1998，26（1）：63－84.

［2］Zhou S K，Chellappa R，Moghaddam B.Visual tracking and recognition using appearance－adaptive models in particle filters［J］.Image Processing，IEEE Transactions on，2004，13（11）：1491－1506.

［3］Ross D，Lim J，Lin R S，et al.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77（1）：125－141.

［4］Collins R T，Liu Y X，Leordeanu M.Online selection of discriminative tracking features［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2005，27（10）：1631－1643.

［5］Wang J Y，Chen X L，Gao W.Online selecting discriminative tracking features using particle filter［J］.IEEE Computer Society Conference on，2005，2：1037－1042.

［6］Avidan S.Ensemble tracking ［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2007，29（2）：261－271.

［7］Grabner H，Bischof H.On－line boosting and vision ［J］.Computer Vision and Pattern Recognition，IEEE Computer Society Conference on，2006，1：260－267.

［8］Bao C L，Wu Y，Ling H B，et al.Real time robust L1 tracker using accelerated proximal gradient approach ［C］∥Computer Vision and Pattern Recognition （CVPR），IEEE Conference on.Providence，RI：IEEE，2012：1830－1837.

［9］Wang Q，Chen F，Xu W L，et al.Online discriminative object tracking with local sparse representation［C］∥Applications of Computer Vision（WACV），2012IEEE Workshop on.Breckenridge，CO：IEEE，2012：425－432.

［10］Zhong W，Lu H C，Yang M H.Robust object tracking via sparsity－based collaborative model［C］∥Computer Vision and Pattern Recognition （CVPR），2012IEEE Conference on.Providence，RI：IEEE，2012：1838－1845.

［11］Jia X，Lu H C，Yang M H.Visual tracking via adaptive structural local sparse appearance model［C］∥Computer Vision and Pattern Recognition（CVPR），2012IEEE Conference on. Providence， RI： IEEE， 2012：1822－1829.

［12］Mei X，Ling H B.Robust visual tracking and vehicle classification via sparse representation ［J］.Pattern A－nalysis and Machine Intelligence，IEEE Transactions on，2011，33（11）：2259－2272.

［13］Adam A，Rivlin E，Shimshoni I.Robust fragments－based tracking using the integral histogram［J］.Computer Vi－sion and Pattern Recognition，2006IEEE Computer Society Conference on，2006，1：798－805.

［14］Babenko B，Yang M，Belongie S.Visual tracking with online multiple instance learning［C］∥Pattern Analysis and Machine Intelligence，IEEE Transactions on.Miami，FL：IEEE，2009：983－990.

［15］Kalal Z，Mikolajczyk K，Matas J.Tracking－learning－de－tection［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2012，34（7）：1409－1422.

［16］Kwon J，Lee K M.Visual tracking decomposition［C］∥Computer Vision and Pattern Recognition （CVPR），2010IEEE Conference on.San Francisco，CA：IEEE，2010：1269－1276.