视频目标跟踪典型算法比较与分析

王 苹，张 磊，吴泽民，徐任晖，赵晓通，徐明月

(解放军理工大学 通信工程学院，江苏 南京210007)

视频目标跟踪实质是在连续图像序列中找到具有最相似特征的区域，核心问题是对输入图像序列每一帧图像中的目标能够实现鲁棒地预测其运动趋势。随着计算机自身硬件配置性能的不断提高，加之图像处理分析技术的不断发展，实时目标跟踪得以实现。

稳定的视频跟踪正是视频分析处理和计算机视觉的重要问题，在军事侦查、自动机器人导航、人机交互接口、视频标注等方面有广泛应用。视频图像提供的信息是复杂和海量的，依靠人工进行信息识别和提取是不现实的。2009 年，美军通过无人机在阿富汗和伊拉克获得的视频信息总量，一个人需要24 年才能看完;在通常战备执勤时，需要至少一个人紧盯屏幕发现可疑目标，而其他的辅助人员进行信息甄别和记录。在我国，边海防哨所已经配备了大量的视频采集装备，但是受人员数量限制，仅仅依靠人工方法进行视频目标的捕捉与记录不但工作强度大，而且工作效率低，及时发现可疑目标的时机往往把握不住。目前，各大城市的智能交通系统都具有车辆违章检测功能，可以极大地提高发现交通违法事件的效率。但是受目前视频目标跟踪性能的限制，还仅能对交通灯道口的违章行为进行识别，不能完全获得各路段的违章行为。各方面的需求不断推动着视频目标跟踪研究的进一步深化。

然而，当目标发生剧烈的运动或者形变、背景相对复杂或者与目标相似、外界环境发生较大变化时，大多数视频目标跟踪算法不具有很好的鲁棒性。归结来看，对于大量跟踪算法［1］的问题主要是由于外观和运动的变化造成的。外观变化包括目标几何和光度变化，如遮挡、形变、亮度变化等。运动变化往往发生在较低帧率的视频中或者目标运动剧烈的情况下。以上问题的存在，使得视频目标跟踪研究仍有很长的路要走。

本文将对视频目标跟踪技术的研究背景、系统组成原理进行阐述;对当前几种前沿的跟踪算法进行详细的分析比较;并且对跟踪算法的评价指标和典型的标准库进行介绍;最后总结了视频目标跟踪技术的发展前景和面临的困难挑战。

1 视频目标跟踪系统构成及研究现状

视频目标跟踪系统是一个动态系统的估计问题，利用的是目标在时间上的连续性和空间上的相关性。视频目标跟踪系统的一般框架如图1 所示。

图1 视频目标跟踪系统框架

典型的视频目标跟踪系统由四部分组成:目标初始化，外观模型，运动估计，目标定位。目标初始化包括手动初始化和自动初始化，手动初始化是用户用边缘框注释出目标的位置，自动则通过检测器进行检测目标。外观模型包括视觉描述和统计模型。视觉描述主要是用不同类型的视觉特征来构造鲁棒的目标描述子。统计模型是用统计学习的方法构造有效的数学模型来识别目标。运动估计主要是利用了状态方程和观测方程构成的预测器进行估计，常用预测器包括线性回归技术［2］，卡尔曼滤波［3］和粒子滤波［4－6］等。目标的跟踪定位是目标跟踪中的核心问题，主要利用贪婪搜索或者是最大后验概率来实现［7］。

目前，很多跟踪算法通过在特征提取、外观模型和结构信息方面的改进，跟踪的精度和鲁棒性得到极大的提高。较为常用的特征包括像素值［8］、颜色［9－12］、文本描述子［13－14］。利用目标外观模型较为常用的有颜色分布［10－11］、子空间［8，15］、支持向量机SVM［16］以及稀疏表示［17－19］等。类似于目前较为流行的目标检测［20］和识别［21］的算法，通过获取结构信息对目标进行跟踪的算法也越来越多［9，22－24］。在目标发生遮挡和形变时，目标的内部结构信息对于模型的恢复和鲁棒性跟踪尤为重要。

2 典型视频目标跟踪算法

判定目标跟踪算法好坏往往从鲁棒性、准确性和快速性三个方面比较［25］:

1)鲁棒性(Robustness)。鲁棒性是指在各种环境中算法都能实现对目标的稳定持续跟踪。但往往会受到目标自身形变、环境中的光照变化、部分或者全遮挡等影响。

2)准确性(Accuracy)。在目标跟踪的研究中，准确性包括两个方面，一是对运动目标检测的准确性，这一点主要是在监控系统中要求比较严格，为的是对目标检测的漏警率和虚警率的降低，将检测到真实目标的概率提高;另一个是对运动目标分割的准确性，主要应用在图像压缩编码领域，其实质是图像分割(Image Segmentation)问题。将运动目标和背景进行准确的分割后，方便提取目标准确的运动信息。

3)快速性(Speed)。在实际的视频目标跟踪系统中，对运动目标实时的跟踪就要求跟踪算法必须快速，计算量相对较小。然而跟踪算法本身处理的图像序列包含大量的数据，所需的运算量极大，很难能够满足实时的要求。一种通用的减小运算量的方法是利用金字塔分解或者小波变换将图像分层处理;另一种思路是设计专用硬件实现实时的视频目标跟踪。

本节将从以上提到的跟踪器性能出发，详细介绍当前前沿的四种视频目标跟踪算法，即LGT，TLD，ALIEN 和DGT，并对其工作原理、性能进行分析和比较。

2.1 LGT(Local-Global layer Tracker)跟踪器

随着低成本、小规模摄像机传感器的应用不断增多，对视频序列的鲁棒的自动跟踪需求也随之迅速增加［26］。实际应用中，目标外观随着形变、角度变化、光照变化等因素的变化而变化。因此，鲁棒的跟踪取决于能否随着目标外形的变化自适应地更新目标模型。

最早是Stolkin 等人［27］进行的两层模型的尝试。目标像素的亮度模型的重新学习使用刚性目标物体的运动和几何模型增强结构。L.Cehovin 等人在2013 年针对目标迅速和剧烈的外观变化提出一种双层视觉LGT 模型［28］，即整合的目标全局和局部外观的两层模型。跟踪算法如图2 所示。

图2 双层结构目标跟踪算法

其中，局部层是由局部块组成的集合，反映目标外观发生的几何变化。随着目标几何形变，局部层通过移除或添加局部块来更新结构。添加的局部块是由全局层约束得到的。全局层主要是反映目标全局的视觉特性，包括颜色、形状和表面上的局部运动。全局层的更新需要依赖跟踪过程中得到的稳定的局部块。LGT 算法的鲁棒性更好，并且跟踪精度更高，对参数变化不敏感。这篇文章的重要贡献就是在两层模型的贝叶斯公式中应用了双层约束。

这种交叉的双层视频模型是较为先进的技术，效果优于其他的跟踪器。

2.2 TLD(Tracking-Learning-Detection)跟踪器

考虑手持摄像机拍摄的视频流，各种事物从相机拍摄范围内出入。仅在单独的一帧中用边缘框框出了感兴趣目标，而需要解决的问题是，在接下来的每一帧中自动标出目标的边缘框或者当目标没有出现时给出提示。该视频流需要长时间实时跟踪处理。在文献［29］中，将这类任务定义为长期跟踪问题。

解决长期跟踪问题的关键是目标的检测。首先，目标外观会变化，甚至跟初始帧中外观没有任何关联;其次一个成功的长期跟踪器要能够应对尺度、光照的变化，复杂背景，部分遮挡，以及实时地完成处理。

在文献［29］中Kalal 的出发点立足于单独的跟踪或检测无法解决长期跟踪问题。文中提出一种新颖的跟踪框架TLD(Tracking－Learning－Detection)，如图3 所示。文章将长期的目标跟踪分解为跟踪、学习、检测。跟踪器逐帧跟踪目标，检测器局部化目前位置出现的所有外观，在必要时修正跟踪器，学习阶段评估检测器的误差并更新，避免这些误差。作者研究确定检测器误差并学习，提出一种新颖的学习方式(P－N学习):1)P 评估遗漏的检测;2)N 评估错误预警。学习过程模型化为一个离散的动态系统，学习中确保有改善的情况被查找到。

图3 TLD 算法跟踪框架

Kalal 提出的TLD 跟踪系统，能够实现对视频流中的目标的实时地跟踪、学习、检测，利用标准数据库和同时期较为前沿的跟踪器相比，TLD 的长期实时跟踪性能优于其他跟踪器。

2.3 ALIEN(Appearance Learning In Evidential Nuisance)跟踪器

文献［30］中给出妨碍因素(Nuisance Factors)的定义。妨碍因素是指影响图像结构处理的因素，不是用于跟踪的直接兴趣点，然而又必须考虑在内。妨碍因素分为可逆妨碍和不可逆妨碍。可逆妨碍主要是指反差、视角变化等，不可逆妨碍包括遮挡、传感器量化、一般光照变化等。不可逆的妨碍通常可以转化为可逆妨碍。

ALIEN 跟踪器利用弱匹配目标模板的多尺度不变局部特征，考虑到三维形状和平面的绝对偏差，以及阴影、遮挡、传感器量化等不可逆妨碍因素的影响。同时基于传递匹配特性的无参学习算法，将目标从上下文分离出来，防止遮挡情况下的目标模板的错误更新。这种学习准则在缓慢变化的情况下具有渐近稳定的特性，确保了算法在长时间跟踪中的无偏移特性。

文章作者从一般的观察出发，尝试同时解决可逆和非可逆的妨碍因素。基于这种考虑，作者选用局部特征来表示目标，同时利用过采样保留多数目标和场景信息。

文中算法的基本流程如图4 所示。

图4 ALIEN 算法流程图

2.4 DGT(Dynamic-Graph-Tracking)跟踪器

目前，很多文章对遮挡问题都有所讨论，例如将目标进行水平垂直的分割对抗遮挡;稀疏表示对遮挡问题也不敏感;以及利用场景学习机制、上下文信息等。绝大多数的跟踪器在解决遮挡问题［9，18，31］时没有考虑到目标自身的形变［12，23］问题。针对目标形变问题通常采用局部块进行表示，但此时块之间的结构信息将被忽略。

文献［35］在一个统一的框架中同时考虑到遮挡和形变的问题，引入动态图进行跟踪。图表示利用目标的内部结构信息，能够识别几何形变的目标，同时能够借助目标未被遮挡部分定义出被遮挡目标。

作者的基本思路是:首先，将视频目标跟踪问题公式化为跟踪动态无向图的问题，即目标图和候选图的匹配问题，利用马尔科夫随机场(Markov Random Filed)将候选图中的局部块与背景分割，再利用谱聚类(Spectral Clustering)的方法完成图匹配;其次，目标状态利用块一致性的依赖关系通过带权重的投票获得，同时由前景和背景的分割进一步改善;最后，有效地在线更新机制更新模型，鲁棒地适应目标结构的变化。

文中的算法同时考虑到目标出现遮挡和发生形变的情况，利用无向图更好地记录目标的内部信息，有效对抗遮挡和形变。

2.5 对比与归纳

通过对上述4 种跟踪器的工作原理的详细分析，可以归纳出以下几点:

1)LGT 算法在目标表示上结合局部和全局特征。局部特征包含大量空间信息，对部分遮挡具有鲁棒性，全局特征作为局部特征选取时的约束信息。双层的贝叶斯公式对跟踪进行双层约束，提高目标模型更新的精确性，基本达到实时的要求。但是实际应用中该算法对于杂乱背景，以及目标发生尺度变化时都较为敏感。

2)TLD 算法能够通过检测、学习跟踪目标，针对长期实时的跟踪环境，处理效果较好。但由于算法没有考虑到目标的遮挡和形变等问题，在处理非刚性目标跟踪中存在一定的局限性。同时针对剧烈运动的目标跟踪效果不佳。

3)ALIEN 算法无差别地处理可逆和不可逆妨碍因素，算法对遮挡是否发生作出判定给出不同的计算思路。将目标和上下文同时进行建模和模型更新，保留了较多跟踪目标的信息。但在复杂背景下以及目标发生形变的情况下，跟踪器将无法准确跟踪。

4)DGT 算法提出利用无向图表征目标，将目标跟踪的问题公式化为无向图匹配问题，同时在长期跟踪中具有渐近稳定的特性。该算法同时考虑到目标的遮挡和形变问题。但是无加权表示的无向图在尺度发生变化时较为敏感。同时由于光照变化造成的前景、背景不易区分也给跟踪带来一定的难度。

几种算法各有优势和劣势，针对不同的应用场景，需要充分理解它们的算法特性加以改进应用。同时算法较为新颖的思路为今后的研究给出极大的启示。

3 算法评价指标及标准库

近年来，视频目标跟踪技术在计算机视觉领域的广泛应用推动着跟踪算法的不断提升改进。但是仍旧有很多的因素影响着跟踪算法的性能。因此，评估主流跟踪算法的优势和劣势非常重要，能够给未来这个方向的研究提供更多的方向。

首先，关于跟踪算法的评价指标问题。定量分析(Quantitative Analysis)算法性能，能够更加清晰地看出算法的各方面优势。较为常用的指标包括成功率(Success Rate)如Pascal Score［33］，F－measure，和精度率(Precision Rate)如CLE(Center－Location－Error)，Precision Plot［13，34］。其次，用于测试的数据库也是至关重要的部分。具有代表性的数据库对综合评估跟踪算法至关重要。现有的用于视频跟踪的监控场景的视频库包括VIVID［35］，CAVIAR［36］，PETS，VIRAT(Video and Image Retrieval Analysis Tool)等。

3.1 视频目标跟踪算法评价指标

多数跟踪算法将目标表示为边缘框(A Bounding Box)，通过比较边缘框重叠面积确定跟踪的成功率(Success Rate)。

式中，Bp，Bgt分别表示跟踪器跟踪的目标边缘框和真实边缘框(Ground Truth)，等式右边表示边缘框交叠部分面积占边缘框并面积的比率。设置门限值t0(一般取0.5)，大于此门限为跟踪成功，小于则跟踪失败。

2)F－measure，与之类似

跟踪精度率(Precision Rate)的比较，较为常用的指标也有两种。

3)CLE(Center－Location－Error)，计算跟踪的边缘框内中心点与真实边缘框内中心点的像素距离。距离越大表示跟踪的精确度越低。

4)Precision Plot，近段时间的研究常用Precision Plot 来衡量整体跟踪的表现。主要反映的是跟踪器估计出的位置距离真实位置在某个门限范围内的图像帧的百分率。门限值单位为像素。

3.2 视频目标跟踪算法标准库

可用于测试的视频库有很多，但是大多数的图像序列没有给出真实位置注释(Ground Truth Annotations)，在进行定量评估时会产生误差。包含多种特殊场景(光照变化、复杂背景、部分遮挡或全遮挡等)同时具有真实位置的数据库非常的重要。

2008 年美国国防部高级研究项目署开始的VIRAT(Video and Image Retrieval Analysis Tool)系统，用于进行无人机航拍图像的分析处理，用以实现针对特定事件的有效预警等功能。视频库包含多场景，如大型公共场所、停车场、校园等。背景复杂简单情况不一，同时包含摄像机自身运动的情况。另外，文献［37］收集构建了目前较为常用且含真实位置标注的具有典型代表性的图像序列数据库，如遮挡、剧烈形变、光照变化、阴影情况等。

以上数据库都包含复杂多样的场景状况，普遍适用于跟踪器的测试，是较为全面合理的测试数据库。

4 视频目标跟踪技术发展前景与挑战

视频目标跟踪技术是一个多学科相结合的研究领域，包括机器视觉、人工智能、计算机科学、模式识别、图像处理等方面。该领域仍处在发展阶段，很多的问题亟需解决。跟踪的特征选择、动态外观模型、运动估计等方面将是研究非常重要的领域。目前，研究人员针对特定的应用场景下的视频目标跟踪问题已经提出了很多的解决的方案策略，但是仍然存在着很多的进步空间，需要新的思路进行完善。

综上，对视频目标跟踪技术的未来发展趋势可以归结如下:一是运动目标外观的模型化，即外观建模，运动目标外观模型随着目标自身运动能够自适应的作出调整是目前的一个研究的热点问题;二是目标模型的更新策略，较多的算法在模型更新阶段会出现误差和偏移，往往会导致跟踪失败;三是多传感器的视频目标跟踪，这其中就要重点考虑到数据关联融合的问题;四是对目标动作的识别问题，通过目标运动状态进行目标的进一步的行为分析。

5 结语

本文对视频目标跟踪算法中较为常见的问题进行归纳，对该技术进行了综述，重点分析比较了目前较为前沿的跟踪算法。对跟踪性能比较的评价指标以及标准库进行简单介绍。视频目标跟踪基本流程是利用目标的运动信息、颜色、纹理等特征采样描述子形式描述目标，通过外观建模以及模型更新的策略实现运动目标的运动状态的预测，获取目标的位置信息。

由于最终的具体应用背景的不同，视频目标跟踪领域的研究内容存在较大差异，极具挑战性的问题也有很多，不管是在研究领域还是在实际的工程应用中都具有非常重要的意义和广阔的前景。

［1］蔡荣太，吴元昊，王明佳，等.视频目标跟踪算法综述［J］. 电视技术，2010，34(12):135－138.

［2］ELLIS L，DOWSON N，MATAS J，et al. Linear regression and adaptive appearance models for fast simultaneous modelling and tracking［J］. International Journal of Computer Vision，2011，95(2):154－179.

［3］KALMAN R E. A new approach to linear filtering and prediction problems［J］. Journal of Fluids Engineering，1960，82(1):35－45.

［4］ISARD M，BLAKE A. Condensation—conditional density propagation for visual tracking［J］. International Journal of Computer Vision，1998，29(1):5－28

［5］ARULAMPALAM M S，MASKELL S，GORDON N，et al.A tutorial on particle filters for online nonlinear/non－Gaussian Bayesian tracking［J］.IEEE Trans.Signal Processing，2002，50(2):174－188.

［6］SHEN C，BROOKS M J，VAN DEN H A.Augmented particle filtering for efficient visual tracking［C］//Proc. ICIP 2005.［S.l.］:IEEE Press，2005:856－859.

［7］LI X，HU W，SHEN C，et al. A survey of appearance models in visual object tracking［J］. ACM Trans. Intelligent Systems and Technology，2013，4(4):58.

［8］LIM J，ROSS D A，LIN R S，et al.Incremental learning for visual tracking［C］//SAUL LK，WEISS Y BOTTOU L.Advances in Neural Information Processing Systems 7.［S.l.］:Neural Information Processing Systems Foundation，Inc.，2004:793－800.

［9］ADAM A，RIVLIN E，SHIMSHONI I. Robust fragments－based tracking using the integral histogram［C］//Proc.2006 IEEE Computer Society Conference on Computer vision and pattern recognition，［S.l.］:IEEE Press，2006:798－805.

［10］COMANICIU D，RAMESH V，MEER P. Real－time tracking of non－rigidobjects using mean shift［C］//Proc.2000 IEEE Conference on Computer Vision and Pattern Recognition.［S.l.］:IEEE Press，2000:142－149.

［11］PéREZ P，HUE C，VERMAAK J，et al. Color－based probabilistic tracking［M］//Computer vision—ECCV 2002.［S.l.］:Springer Berlin Heidelberg，2002:661－675.

［12］WANG S，LU H，YANG F，et al.Superpixel tracking［C］//Proc.ICCV 2011.［S.l.］:IEEE Press，2011:1323－1330.

［13］BABENKO B，YANG M H，BELONGIE S. Robust object tracking with online multiple instance learning［J］. IEEE Trans. Pattern Analysis and Machine Intelligence，2011，33(8):1619－1632.

［14］GRABNER H，BISCHOF H. On－line boosting and vision［C］//Proc.CVPR 2006.［S.l.］:IEEE Press，2006:260－267.

［15］WEN L，CAI Z，LEI Z，et al. Online spatio－temporal structural context learning for visual tracking［M］//Computer Vision–ECCV 2012.Berlin:Springer，2012:716－729.

［16］TIAN M，ZHANG W，LIU F.On－line ensemble SVM for robust object tracking［M］//Computer Vision – ACCV 2007. Berlin:Springer，2007:355－364.

［17］LIU B，HUANG J，YANG L，et al. Robust tracking using local sparse appearance model and k－selection［C］//Proc. CVPR 2011.［S.l.］:IEEE Press，2011:1313－1320.

［18］MEI X，LING H. Robust visual tracking using L1 minimization［C］//Proc. ICCV 2009.［S.l.］:IEEE Press，2009:1436－1443.

［19］ZHANG K，ZHANG L，YANG M. Fast compressive tracking［J］.IEEE Trans. Pattern Analysis＆Machine Intelligence，2014，36(10):2002－2015.

［20］FELZENSZWALB P F，GIRSHICK R B，MCALLESTER D，et al.Object detection with discriminatively trained part－based models［J］. IEEE Transa. Pattern Analysis and Machine Intelligence，2010，32(9):1627－1645.

［21］QUATTONI A，COLLINS M，DARRELL T. Conditional random fields for object recognition［C］//Proc.Advances in Neural Information Processing Systems 2004.［S.l.］:Neural Information Processing Systems Foundation，Inc.，2004:1097－1104.

［22］GRACIANO A B V，CESAR R M，BLOCH I. Graph－based object tracking using structural pattern recognition［C］//Proc.Computer Graphics and Image Processing，2007.［S.l.］:IEEE Press，2007:179－186.

［23］KWON J，LEE K M. Tracking of a non－rigid object via patchbased dynamic appearance modeling and adaptive basin hopping monte carlo sampling［C］//Proc. CVPR 2009. ［S.l.］:IEEE Press，2009:1208－1215.

［24］YANG M，WU Y，HUA G. Context－aware visual tracking［J］.IEEE Trans. Pattern Analysis and Machine Intelligence，2009，31(7):1195－1209.

［25］侯志强，韩崇昭. 视觉跟踪技术综述［J］. 自动化学报，2006，32(4):603－617.

［26］WANG X. Intelligent multi－camera video surveillance:a review［J］.Pattern recognition letters，2013，34(1):3－19.

［27］STOLKIN R，GREIG A，HODGETTS M，et al.An EM/E－MRF algorithm for adaptive model based tracking in extremely poor visibility［J］.Image and Vision Computing，2008(26):480－495.

［28］CEHOVIN L，KRISTAN M，LEONARDIS A. Robust visual tracking using an adaptive coupled－layer visual model［J］. IEEE Trans.Pattern Analysis and Machine Intelligence， 2013， 35(4):941－953.

［29］KALAL Z，MIKOLAJCZYK K，MATAS J. Tracking－learning－detection［J］. IEEE Trans. Pattern Analysis and Machine Intelligence，2012，34(7):1409－1422.

［30］PERNICI F，DEL BIMBO A.Object tracking by oversampling local features［J］. IEEE Trans. Pattern Analysis and Machine Intelligence，2014，36(12):2538－2551.

［31］GRABNER H，MATAS J，VAN GOOL L，et al. Tracking the invisible:Learning where the object might be［C］//Proc. CVPR 2010.［S.l.］:IEEE Press，2010:1285－1292.

［32］CAI Z，WEN L，LEI Z，et al.Robust deformable and occluded object tracking with dynamic graph［J］. IEEE Trans. Image Processing，2014，23(12):5497－5509.

［33］EVERINGHAM M，VAN GOOL L，WILLIAMS C K I，et al. The pascal visual object classes(VOC)challenge［J］. International Journal Of Computer Vision，2010，88(2):303－338.

［34］HENRIQUES J F，CASEIRO R，MARTINS P，et al.Exploiting the circulant structure of tracking－by－detection with kernels［M］//Computer Vision–ECCV 2012.Berlin:Springer，2012:702－715.

［35］COLLINS R，ZHOU X，TEH S K.An open source tracking testbed and evaluation web site［C］//Proc.IEEE International Workshop on Performance Evaluation of Tracking and Surveillance. ［S.l.］:IEEE Press，2005:17－24.

［36］FISHER R B.The PETS04 surveillance ground－truth data sets［C］//Proc.6th IEEE international workshop on performance evaluation of tracking and surveillance.［S.l.］:IEEE Press，2004:1－5.

［37］WU Y，LIM J，YANG M H. Online object tracking:A benchmark［C］//Proc.CVPR 2013.［S.l.］:IEEE Press，2013:2411－2418.