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

程中建 李康 徐龙香

摘要：目标跟踪是计算机视觉领域重要的研究方向之一。基于l1最小化稀疏表示的目标跟踪算法跟踪精度高，但是在跟踪部分遮挡目标或当背景中存在与目标相似的干扰物时会发生漂移。这主要是因为算法仅关注目标的整体特征，而忽略了目标局部特征的变化情况。为了解决该问题，提出基于目标外观局部稀疏表示的跟踪算法。首先，对待选样本进行分块，然后利用采集得到的模板对各分块进行稀疏表示并计算重构误差，最后选取累积误差最小的待选样本作为跟踪目标。实验结果表明，该算法在跟踪被部分遮挡的目标时相比l1跟踪算法有更高的准确度。

关键词：目标跟踪；稀疏表示；l1算法；分块策略；生成模型

DOIDOI：10.11907/rjdk.181568

中图分类号：TP312

文献标识码：A 文章编号文章编号：1672-7800（2018）008-0106-04

英文摘要Abstract：Object tracking is one of the most important research areas in computer vision.The object tracking algorithm based on l1 sparse representation minimization has high tracking accuracy.However，when the object is partially occluded or the environment is similar to the object，the tracker may drift.This is mainly because the algorithm only focuses on the overall characteristics of the object and ignores the changes of the local characteristics of the object.In order to solve this problem，we propose a tracking algorithm based on the local sparse representation.Firstly，the candidate sample is divided into several overlaped blocks.Then，we employ each block using the collected templates to calculate reconstructive error.Finally，the candidate sample with the smallest reconstructive error is selected as the target.Experimental results show that our algorithm has higher accuracy than l1 tracker when tracking partially occluded objects.

英文關键词Key Words：object tracking； sparse representation； l1algorithm； block strategy； generative model

0 引言

目标跟踪是计算机视觉领域重要研究课题之一。在交通导航、虚拟现实、视频监控、无人机飞行等领域应用广泛。近年来，国内外大量跟踪算法被开发出来[1-6]。但由于受到目标外观变化、目标局部遮挡和目标信息缺失等众多干扰因素影响，开发出鲁棒性的跟踪算法仍然面临巨大挑战。

按照外观模型的不同，现有目标跟踪算法可以分为两类：生成式模型和判别式模型。判别式算法模型[7-11]将目标跟踪视为二值分类问题，通过使用采样得到的正样本和负样本训练分类器分离目标与背景，然后选择具有最大分类响应值的待选样本作为跟踪结果。文献[8]提出了一种基于在线增强方法更新判别特征的目标跟踪算法。在此基础上，文献[9]提出一种半在线算法处理跟踪漂移问题。多实例目标跟踪（MIL）[10]使用在线Boosting算法训练分类器处理非线性分类问题。邸男等[11]利用棱锥面方程的单峰特性并结合似然相似度函数提高目标与背景的区分度。判别式算法在跟踪复杂环境中的目标时会得到鲁棒性结果，但在处理外观变化不大的目标时往往会丢失目标。

生成式算法模型[12-17]通过训练样本学习目标外观模型，然后在候选样本中选择重构误差最小的样本作为跟踪结果。Adam等[12]提出使用多尺度灰度直方图表示目标特征。Mei等[13-14]利用目标整体特征建模外观模型，通过求解l1最小化问题选择具有最小重构误差的候选样本作为跟踪目标。Liu等[15]结合稀疏表示思想和均值漂移模型，提出了一种基于局部稀疏表示的目标跟踪算法。周等[16]提出了帧间差分与局部Camshift的跟踪算法解决运动目标提取后存在的”空洞”现象。Zhang等[17]通过将跟踪过程建模为多任务稀疏学习问题，提出了一种协同跟踪算法。与判别式跟踪算法不同，基于生成式模型的算法具有较高的跟踪精确度，但是在目标环境较为复杂时跟踪结果不够鲁棒。

基于l1最小化稀疏表示的目标跟踪算法[13]跟踪精度高、跟踪速度快，但是该算法在跟踪被遮挡的目标时容易发生漂移，主要因为该算法仅考虑了目标的整体外观而忽略了目标被遮挡部分的外观。为解决该问题，本文提出一种基于局部稀疏表示的目标跟踪算法。首先，将目标样本分割成多个有部分重叠的局部区域；然后针对每个局部区域分别进行稀疏表示，计算重构误差；最后选择累积误差最小的候选样本作为跟踪结果。算法在考虑目标整体外观特征的同时，结合目标局部信息，解决被遮挡目标的跟踪问题，提高跟踪的鲁棒性。

1 局部稀疏表示跟踪算法实现

近年来，基于生成式模型的稀疏表示方法被应用于目标跟踪，取得了鲁棒的跟踪效果[13-15，18]。该算法使用模板稀疏表示目标的整体外观模型，并根据最小化l1选取具有最小重构误差的待选样本作为跟踪结果。但是，这类算法仅考虑了目标整体的外观模型，忽略跟踪目标的局部结构信息，因此在利用l1最小化计算被部分遮挡的待选样本时会产生较大的重构误差，导致这类算法在跟踪被部分遮挡的目标时容易丢失目标。

为了改进稀疏表示算法（简称L1算法）存在的问题，提出一种局部分块稀疏表示的跟踪策略。如图1所示，首先对所有样本进行分块处理，然后使用稀疏表示计算每一个分块的重构误差，最后选择具有最小累积误差的待选样本作为跟踪结果。分块稀疏表示的策略综合考虑了目标整体外观和局部外观信息，相较于L1算法在处理目标部分遮挡等问题时具有更高精准度。

1.2 模板更新

为了适应目标背景受非确定因素影响发生的变化，算法应及时更新各分块区域对应的模板集。如果模板更新过快，模板的重构误差将会不断积累，进而导致跟踪结果发生偏移，与此相反，如果模板更新太慢或模板固定不变，将不能准确表达目标外观模型，最终丢失目标。

2.3 实验结果分析

从表1、表2（最好结果由粗体标出）可以看出，本文提出的算法与其它经典算法相比具有较好的跟踪效果。结合图2，根据所选测试跟踪序列特点进行具体分析。

（1）Basketball。该测试跟踪序列中由于目标区域存在大面积背景区域，如目标头部两侧及腿部之间的区域，目标整体外观模型随背景变化，造成跟踪困难。跟踪过程中，VTD、L1分别在第33、351帧丢失目标，MIL在第351帧时偏移到非目标上，只有本文算法能够准确跟踪目标。测试结果表明，本文算法在光照变化和背景复杂的跟踪环境中能够准确跟踪。

（2）Dudek。该测试视频序列为室内环境，由于目标姿势和运动变化，目标外观模型剧烈改变，造成跟踪困难。跟踪过程中，MIL在第214帧发生漂移，L1、VTD、Ours均能够准确跟踪到目标。

（3）Woman。该测试视频在目标经过汽车时，目标遮挡面积约为其总面积的2/3，遮挡过程持续时间近60帧。由于无法处理目标被部分遮挡的区域，第126帧时，L1漂移到车辆上，MIL与VTD丢失跟踪目标。本文算法由于运用分块策略，能够对目标分块区域分别处理，再由稀疏表示计算出的重构误差从局部角度分析目标是否存在遮挡，避免L1算法中整体外观模型产生的不足。本算法不更新存在严重遮挡的分块对应的模板集，最大限度上降低了由于更新产生的误差累积，使算法能够准确针对目标的各块外观建模。跟踪结果验证了本算法能够准确跟踪部分遮挡的目标。

（4）David2。在该视频中，跟踪目标区域较小、目标与背景区域局部相似造成跟踪难点。L1、MIL分别在第28、198帧时发生漂移，并在第537帧完全丢失目标，仅VTD与本文算法能够较准确跟踪到目标。

（5）David3。该测试视频中，目标被树木大面积遮挡。L1，MIL均在第90帧丢失目标，VTD在103帧丢失目标，而由于本文算法采用了分块策略处理目标存在的部分遮挡问题，因此能够准确地跟踪到目标。

3 结语

本文通过分析传统L1算法中目标整体稀疏表示存在忽略跟踪区域局部信息的缺陷，提出了一种基于局部分块稀疏表示的目标跟踪算法。通过对目标区域进行分块处理，可以对各分块单独运用稀疏表示求解重构误差，并以此判断目标当前是否处于被遮挡状态。在模板更新时，提出不更新重构误差较大的分块，避免被遮挡的目标模板污染模板集，提高了算法的鲁棒性。利用分块思想对L1算法忽略的局部信息加以利用，使算法能够处理更加复杂的跟踪环境。本文算法将分块稀疏表示理论应用于目标跟踪，探讨了局部重构误差对跟踪结果的影响，加深了对多模块联合稀疏表示方法的认识，丰富了稀疏表示在目标跟踪中的理论应用。实验结果表明，该算法在跟踪被部分遮挡的目标时，相比其它经典跟踪算法有更高的准确度。在未来工作中，将在现有研究基础上结合深度特征对目标进行跟踪。

参考文献：

[1] DANELLJAN M，SHAHBAZ KHAN F，FELSBERG M，et al.Adaptive color attributes for real-time visual tracking[C].IEEE Conference on Computer Vision and Pattern Recognition，2014：1090-1097.

[2] ZHANG T，JIA K，XU C，et al.Partial occlusion handling for visual tracking via robust part matching[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition，2014：1258-1265.

[3] 王宇霞，趙清杰，蔡艺明，等.基于自重构粒子滤波算法的目标跟踪[J].计算机学报，2016，39（7）：1294-1306.

[4] 姜文涛，刘万军，袁姮，等.视觉量子目标跟踪方法[J].软件学报，2016，27（11）：2961-2984.

[5] 黄庆俊，何儒汉.基于协方差矩阵的压缩感知跟踪算法[J].软件导刊，2017，16（4）：31-35.

[6] LIU Q，YANG J，ZHANG K，et al.Adaptive compressive tracking via online vector boosting feature selection[J].IEEE Transactions on Cybernetics，2017，47（12）：4289-4301.

[7] AVIDAN S.Ensemble tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29 （2）：261-271.

[8] GRABNER H，BISCHOF H.On-line boosting and vision[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006，1：260-267.

[9] GRABNER H，LEISTNER C，BISCHOF H.Semi-supervised on-line boosting for robust tracking[C].European Conference on Computer Vision，2008：234-247.

[10] BABENKO B，YANG M H，BELONGIE S.Visual tracking with online multiple instance learning[C].IEEE Conference on Computer Vision and Pattern Recognition，2009：983-990.

[11] 邸男，朱明，韩广良.似然相似度函数在目标跟踪中的鲁棒机理研究[J].软件学报，2015，26（1）：52-61.

[12] ADAM A，RIVLIN E，SHIMSHONI I.Robust fragments-based tracking using the integral histogram[C].2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006，1：798-805.

[13] MEI X，LING H.Robust visual tracking using 1 minimization[C].2009 IEEE 12th International Conference on Computer Vision，2009：1436-1443.

[14] MEI X，LING H，WU Y，et al.Minimum error bounded efficient 1 tracker with occlusion detection[C].2011 IEEE Conference on Computer Vision and Pattern Recognition，2011：1257-1264.

[15] LIU B，HUANG J，YANG L，et al.Robust tracking using local sparse appearance model and k-selection[C].2011 IEEE Conference on Computer Vision and Pattern Recognition，2011：1313-1320.

[16] 周文靜，陈玮.基于改进帧间差分与局部Camshiift相结合的目标跟踪算法[J].软件导刊，2018，17（3）：68-70.

[17] ZHANG T，GHANEM B，LIU S，et al.Robust visual tracking via multi-task sparse learning[C].2012 IEEE Conference on Computer Vision and Pattern Recognition，2012：2042-2049.

[18] LIU B，YANG L，HUANG J，et al.Robust and fast collaborative tracking with two stage sparse optimization[C].European Conference on Computer Vision，2010：624-637.

[19] KWON J，LEE K M.Visual tracking decomposition[C].2010 IEEE Conference on Computer Vision and Pattern Recognition，2010：1269-1276.

[20] WU Y，LIM J，YANG M H.Online object tracking：a benchmark[C].2013 IEEE Conference on Computer Vision and Pattern Recognition，2013：2411-2418.

（责任编辑：江 艳）