朱征宇，李帅，朱威（.重庆大学计算机学院，重庆400030；2.软件理论与技术重庆市重点实验室，重庆　400030）

基于自适应模型的时空上下文跟踪

朱征宇1，2，李帅1，朱威1
（1.重庆大学计算机学院，重庆400030；2.软件理论与技术重庆市重点实验室，重庆400030）

针对当前时空上下文目标跟踪算法存在的易发生模型漂移的问题，提出基于自适应模型的时空上下文跟踪算法。该算法通过对常规模板保存多个历史快照模型作为多模板，当历史快照模板估计到比常规模板适应性更强的结果时，立即对常规模板进行回滚，可有效提升时空上下文跟踪算法的鲁棒性，在目标快速运动、快速旋转、运动模糊和严重遮挡的情况下依然跟踪准确。在Tracker Benchmark v1.0测试集上与原时空上下文目标跟踪算法的对比实验表明，平均正确率由38.61%提高到42.02%，并将平均中心坐标误差从85.57降低到62.78，而平均帧速则从45.89 fps下降到36.64 fps，依然满足实时跟踪的要求，表明该算法在面对多种因素干扰的场景下，仍能完成稳定的实时跟踪。

目标跟踪；实时跟踪；时空上下文；自适应模型；模板快照

国家科技支撑计划重点项目（No.2011BAH25B04）、软件理论与技术重庆市重点实验室

0　引言

视频目标跟踪作为机器视觉领域的重要问题之一，是视频内目标识别、行为识别等后续工作的基础，所以目标跟踪有着广阔的应用前景，受到了世界各地研究者的高度关注。

目前实时跟踪的热点模型是基于在线学习的跟踪，而其中又分为生成模型和判别模型两种。生成模型以视频目标本身特征为考虑对象，根据目标样本生成模型参数，在后续帧中搜索与该模型特征最接近的图像块作为视频目标的结果。如使用颜色直方图作为特征模板的跟踪算法［2-3］。判别模型则将目标与背景的区分度作为考虑对象，在特征空间中建立目标与背景的判别函数，将后续的目标跟踪问题转换成搜索具有目标与背景具有最大区分度的视频块的问题。如基于SVM的光流跟踪［4］，在线学习跟踪［5］。目前从总体上讲，判别模型相较于生成模型有一定的优势，由于生成模型丢弃了背景信息，而背景信息可以用来辅助判别一个样本是否更偏离跟踪目标，而判别模型同时利用了目标信息和背景信息，最终可以得到更好的跟踪效果。

此外尽管视频目标跟踪算法已经研究发展了数十年，并且已有各式各样的算法被提出，但是目前常见的跟踪算法依然是基于线性结构模型，如图1（a）所示的时间线性结构模型和1（b）中是贝叶斯平均结构模型。这两种模型都是简单且可靠的选择，因为它能很好地适应在线跟踪类型的框架且后验概率密度传播也非常简单。但是这两者模型过于简单，或仅使用了前一帧结果或盲目的平均前向帧的结果，在某些场景下其估计的结果会不可靠，如突然的外观变化、快速运动以及遮挡等时，因此不能处理复杂环境下的目标跟踪。

1　时空上下文跟踪算法

文献［11］提出了一个基于时空上下文模型的快速鲁棒性算法（STC）用于视频目标跟踪，它本质上是基于生成模型，但是加入了背景信息作为空间位置信息考量，用于辅助定位目标中心，同时通过FFT加速实现了一个非常快速有效的跟踪算法。

图1　基于在线学习框架的跟踪算法的常见图解模型

每一个节点代表一帧，节点上的数字代表了视频帧在时间轴上的先后顺序

但是STC算法采用的结构模型为贝叶斯平均模型，故而存在着易发生模型漂移的先天缺陷，其主要原因由于选择了基于Markov时间平滑假设，导致其对每一帧的跟踪都不加选择地学习，极易导致误差积累引起跟踪漂移乃至失败。如果算法能够保存多个历史快照模板，用于在必要时刻替换常规模板实现模板快照回滚即可实现主动丢弃掉某一段时间间隔内的连续学习可能引入的积累误差。另外待跟踪目标往往处于复杂的干扰环境，如遮挡、面内外旋转等，而当这些干扰结束以后目标将继续变回原先之前的外观特征，通过保存多个历史快照模板，当快照模板得到更好更佳的匹配，然后对常规模板进行回滚，以便实现更加鲁棒的跟踪。

2　基于自适应模型的时空上下文跟踪

本文通过结合多模板和快照回滚的思想，提出一种适合应用在对实时性要求较高的在线学习算法的自适应结构模型，如图1（c）所示，并将之应用在时空上下文跟踪算法得到一种改进的时空上下文目标跟踪算法（ASTC算法）。

新模型保存一定数量的历史快照模板。每当新的一帧到来时，同时使用快照模板和常规模板进行预估计，当快照模板估计到比常规模板适应性更好的结果时，本文采纳快照模板预估计得到的结果并用快照模板对常规模板进行回滚，相当于丢弃了从保存快照时刻开始到现在的这段时间间隔内的学习积累的潜在的背景特征内容。

针对模板快照替换准则，本文提出一个适应性公式用于判断，其公式如下：

目前本文算法采集快照模板策略是设定一个间隔常量φ，即每间隔φ帧就对常规模板采集一次快照并加入快照模板组，其公式如下：

其中Indexframe表示视频帧序号。

为了保证算法的实时性，须对快照组的容量进行限制，其对应公式为：

其中Sizesnap为快照模板组的大小，φ是常量，为快照模板组的最大容量限制。当有新的快照模板加入且超出快照组的容量限制时，根据LRU（Least Recently Used，最近最少使用）原则进行剔除。

本文改进算法ASTC对应的流程图如图2所示。

3　实验结果及分析

实验中对本文算法（ASTC），Spatio-temporal Context Tracking（STC）算法［11］和Compressive Tracking（CT）算法［6］进行了比较。三种算法对51个常见的公开测试基准视频序列（Tracker Benchmark v1.0［1］）进行了测试，均使用C/C++进行实现，并辅以OpenCV 2.4.9环境，PC为一台普通的i5，4GB内存的计算机。对于ASTC新提出的有关适应性公式的参数设置，其中公式（1）适应性阈值幅度常量ξ=10%，公式（2）中的快照模板抓取间隔阈值φ=50以及快照模板组的容量上限φ=4。而STC和CT对比算法均使用原作者开源代码的默认参数设置。由于代码未做优化，同时为了利于肉眼观看并方便帧速计算，均对每一帧的处理都加入了一定的延时，故而帧速只可作为相对参考对比，不可作为绝对参考数值。

我们使用了三个评价标准对这三个跟踪算法进行定量评判：分别为成功率（SR）、中心坐标误差（CLE）以及帧速（FPS），其中前两者均是与手工标注的基准数据对比得出。评价标准的详细说明可参见Wu等人在文献［1］中的定义。从表1和表2展示的51个视频序列定量分析中可以看出，本文所提出的算法无论是从成功率上还是中心坐标误差方面都比STC算法更好。在反映跟踪精确性的成功率上，本文算法27次最好、STC 有22次、CT仅10次。此外在反映综合性能平均成绩上，包括Average SR（平均成功率）和Average ACLE（平均平均中心坐标误差），ASTC算法均为最优秀的结果，仅在Average FPS（平均处理帧速）上低于原STC算法，但仍然达到了36.64 FPS的平均帧速，这表明本文所提出的ASTC算法是合理有效的。三种算法对部分视频序列的跟踪结果如图3所示，其对应的中心坐标误差曲线如图4所示。

图2　基于自适应模型的时空上下文跟踪算法流程图

下面将通过对ASTC、STC和CT三种算法的具体实验效果，从多个角度分小节进行对比分析。

3.1快速运动、面内旋转及运动模糊

如图3（a）所示的Boy视频序列，在该视频中待跟踪目标受到了包括快速运动、面内旋转以及运动模糊等因素的干扰，给目标跟踪带来相当大的挑战。在#234帧，CT算法的估计结果已经出现了严重的漂移，之后CT算法已经彻底丢失了目标，因此仅实现了约37%的成功率。对于STC算法而言，前期跟踪效果较好，但在#407帧附近视频发生了一次极快速的面外旋转和运动模糊，STC开始出现漂移且之后丢失了待跟踪的目标，实现了67%的成功率。在该视频序列中，本文所提出的ASTC算法实现了最好的效果，达到了95%的成功率，且仅为3.1的平均中心坐标误差也同时优于CT的 85.38和STC的42。这是由于ASTC算法及时采用历史快照模板对常规模板进行了修正，丢弃了积累的误差，提高了跟踪鲁棒性。

3.2运动模糊及背景混乱

在图3（b）所示为Deer视频的跟踪结果截图，在Deer视频序列中，目标受到了剧烈的运动模糊和背景混乱干扰。待跟踪目标为一只小鹿的头部，而小鹿身体的其他部分和周围干扰鹿均有一致的纹理特征，给目标跟踪带来了相当严峻的考验，因而在该视频上实验结果表明包括CT和STC在内的两个算法的跟踪效果均不甚理想，分别只有8%和6%的成功率，而且平均中心坐标误差也分别达到了150.18和374.38。而ASTC算法在这个视频上达到了83%的成功率和9.7的平均中心坐标误差。此外从对应的中心坐标误差曲线图4 （b）中可以看出ASTC虽也出现了一定程度的漂移，但ASTC通过历史快照模板及时进行了矫正并恢复了正确的跟踪。

3.3遮挡

遮挡问题是视频跟踪领域一个常见的干扰因素，并且给跟踪算法带来了巨大的挑战，是当前衡量一款跟踪算法性能和鲁棒性的关键要素。

如图3（c）所示的FaceOcc1视频，在该序列中，目标不断受到各种不同程度的遮挡，因此如何处理遮挡过程中的跟踪以及遮挡后的恢复是跟踪算法亟待解决的问题。由于FaceOcc1视频序列分辨率较低，待跟踪目标本身较大，且CT算法限定了结果目标框必须在视频内容内，因而即便CT结果出现漂移也能包含部分正确目标区域不至于导致中心坐标误差过大，导致CT算法在该视频序列上意外的实现了75%的成功率和31.84的中心坐标误差。对于STC算法而言，由于长时间的遮挡，导致其过多的学习了背景特征，故而成功率不高，仅为25%。从对应的中心坐标误差曲线4（c）可以看出STC完全丢失了目标。对于该视频序列，ASTC算法实现了最优秀的结果，正确率和平均中心坐标误差分别达到了98%和12.72。究其原因在于ASTC采用了新的自适应结构模型，通过对STC常规模板结果进行适应性检查，当检测到STC常规模板适应性弱于历史快照模板时，通过常规模板进行回滚，使其回滚到最契合当前状态的历史上的某一时刻，有效抑制了跟踪漂移，提升了跟踪效果。

表1　成功率（SR）（%），其中粗体字表示最好

表2　平均中心坐标误差（ACLE）（单位：像素），含平均帧速（FPS）

图3　部分视频序列的跟踪结果截图

图4　部分视频序列的跟踪中心坐标误差曲线图

对于图3（d）中的FaceOcc2视频序列，从#733帧、#748帧可以明显看出STC被遮挡物所吸引出现漂移直至完全丢失，而CT算法虽较好的估计到正确目标但由于不支持尺度变化导致其成功率并不高，仅为56%，只有本文的ASTC算法较好的完成了跟踪，实现了98%的成功率。图3（e）中的Girl视频序列同样包含了遮挡以及面内外旋转等干扰因素。从#360帧可以看出CT和STC算法均出现了一定程度的漂移，至#470帧时，STC已完全跟丢，而本文的ASTC则能较好的完成了跟踪。图3（g）中的Suv序列，#220帧附近出现一次部分遮挡，CT算法已被遮挡物所吸引导致跟踪丢失，#795帧再次出现了遮挡并且更为严重，STC已经完全丢失，ASTC算法则通过适应性检查及时修正了常规模板中积累的误差，实现了最好的跟踪，达到了86%的成功率和5.32的平均中心坐标误差。

3.4光照变化及面内外旋转

Sylvester视频序列包含了光照变化、面内外旋转以及尺度缩放等多种因素的干扰。如图3（h）所示，在#670帧和#1190帧中可以看出CT的跟踪已发生漂移并完全丢失目标。而STC算法也由于不能及时修正模板积累的误差，出现了明显的漂移，仅实现了54%的成功率。对于本文所提出的ASTC算法由于及时丢弃了常规模板中积累的误差，有效提升了成功率，达到了85%。从对应的中心坐标误差曲线4（h）也可以看出ASTC实现了最好的效果。

3.5跟踪丢失后的目标寻回

CT算法属于局部候选搜索算法，其搜索半径限定在上一帧目标中心半径25个像素距离的范围内；同样的对于STC算法也是局部搜索候选搜索算法，STC算法的搜索范围是限定在初始目标框两倍大小的局部上下文区域内。因此当目标重新出现的位置超出了局部搜索范围是无可能重新找回目标的，如图3（f）的Jogging2视频序列中看出，#53帧出现了严重的遮挡，CT、STC均被遮挡物所吸引，至#65帧目标重新完整出现后已完全超出了其候选目标中心的搜索范围，是无可能重新找回，因而CT和STC分别仅实现了16%和17%的成功率。同样对于该视频序列，ASTC的成功率达到了99%，原因在于ASTC的历史快照模板完整保存了各项参数信息，包括位置估计等，有效增大了候选搜索区域，故而实现了最好的实验效果。

4　结语

本文针对当前STC算法中存在的易发生模型漂移问题进行了改进，提出一种新的自适应结构模型，并将之应用到STC上得到了一种改进的上下文目标跟踪算法ASTC。新模型通过保存多个历史快照模板，且同时使用历史快照模板组和常规模板进行预估计，当检测到历史快照模板的适应性高于常规模板时，立即对常规模板进行回滚，丢弃之前一段时间内学习积累的误差，以实现更加鲁棒的跟踪。实验结果表明，本文算法在目标受到不同程度因素干扰和遮挡条件下，跟踪成功率以及跟踪稳定性都有所提高，既保证了实时性，又提高了精确率，增强了算法的鲁棒性。

［1］Wu Y，Lim J，Yang M H.Online Object Tracking∶A Benchmark［C］.Computer Vision and Pattern Recognition（CVPR），2013 IEEE Conference on.IEEE，2013∶2411-2418.

［2］D.Comaniciu，V.Ramesh，P.Meer.Kernel-Based Object Tracking.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）∶564-577.

［3］C.Shen，J.Kim，H.Wang.Generalized Kernel-Based Visual Tracking.IEEE Transactions on Circuits and Systems for Video Technology，2010，20（1）：119-130.

［4］S.Avidan.Support Vector Tracking.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（8）：1064-1072.

［5］R.Collins，Y.Liu，M.Leordeanu.Online Selection of Discriminative Tracking Features.IEEE Transactions on Pattern Analysis andMachine Intelligence，2005，27（10）：1631-1643.

［6］K.Zhang，L.Zhang，M.-H.Yang.Real-Time Compressive Tracking.in Proceedings of European Conference on Computer Vision，2012：864-877.

［7］Zhang K，Zhang L，Yang M H.Fast Compressive Tracking［J］.IEEE Transactions on Pattern Analysis&Machine Intelligence，2014，36 （10）∶2002-2015.

［8］朱秋平，颜佳，张虎，等.基于压缩感知的多特征实时跟踪［J］.光学精密工程，2013，02（2）∶437-444.

［9］Kaihua Z，Lei Z，Ming-Hsuan Y.Real-Time Object Tracking Via Online Discriminative Feature Selection［J］.IEEE Transactions on Image Processing，2013，22（12）∶4664-4677.

［10］Zhang K，Zhang L，Yang M H，et al.Robust Object Tracking Via Active Feature Selection［J］.IEEE Transactions on Circuits&Systems for Video Technology，2013，23（11）∶1957-1967.

［11］Zhang K，Zhang L，Liu Q，et al.Fast Visual Tracking Via Dense Spatio-Temporal Context Learning［M］.Computer Vision-ECCV 2014.Springer International Publishing，2014∶127-141.

［12］Hong S，Han B.Visual tracking by Sampling Tree-Structured Graphical Models［M］.Computer Vision-ECCV 2014.Springer International Publishing，2014∶1-16.

［13］胡士强，敬忠良.粒子滤波算法综述［J］，2005.

［14］宋策.基于粒子滤波的目标跟踪技术研究［D］.中国科学院研究生院 （长春光学精密机械与物理研究所），2014.

［15］章学静，陈禾，杨静.结合卡尔曼滤波和 Mean Shift的抗遮挡跟踪算法［J］.北京理工大学学报，2013，33（10）.

［16］郭崇霄.目标缩放和遮挡情形下在线视频目标跟踪算法研究［D］.重庆大学，2014.

Object Tracking；Real-Time Tracking；Spatio-Temporal Context；Adaptive Structure Model；Snapshot Template

Visual Tracking Using Adaptive Structure Model Based on Spatio-Temporal Context

ZHU Zheng-yu1，2，LI Shuai1，ZHU Wei1
（1.College of Computer Science，Chongqing University，Chongqing 400030；2.Chongqing Key Laboratory of Software Theory and Technology，Chongqing 400030）

Object tracking is one of the basic problems in the field of computer vision.There are many algorithms presented，and STC is a quite novel one.But the STC tracking method can't deal with model drift problem.To overcome this weakness，proposes an algorithm using adaptive structure model based on STC.This algorithm takes a set number of snapshots of normal template as snapshot templates，and saves them to snapshot set.When one of the snapshot templates gets an enough better outcome than normal template，the algorithm uses the snapshot template to roll back the normal template，which can effectively enhance the tracking robustness and keep accurate even when object suffers all kinds of interferences such as fast motion，in-plane rotation，motion blur，severe occlusion and so on.The experiment on Tracker Benchmark v1.0 dataset compared to STC shows that the average accuracy is improved from 38.61%to 42.02%，the average center location error is decreased from 85.57 to 62.78 and the average frame rate decreased from 45.89 fps to 36.64 fps.It still meets the requirements of real-time tracking.In conclusion，this algorithm can accomplish the real-time tracking steadily even when disturbed by all kinds of interferences.

1007-1423（2016）20-0003-07

10.3969/j.issn.1007-1423.2016.20.001

朱征宇（1959-），男，重庆人，博士，教授，研究方向为计算机视觉

李帅（1991-），男，山西长治人，硕士研究生，研究方向为计算机视觉

朱威（1992-），男，湖南常德人，硕士研究生，研究方向为计算机视觉

2016-04-19

2016-06-29