在线机器学习跟踪算法的研究进展

钟必能，陈雁，沈映菊，陈锻生，陈维斌

（华侨大学 计算机科学与技术学院，福建 厦门361021）

在计算机视觉领域，目标跟踪有着广泛的应用［1－3］.基于在线学习的目标跟踪，把跟踪看作分类问题，用在线机器学习算法来处理目标跟踪.与传统离线机器学习相比，在线机器学习算法应用更加广泛和灵活，尤其是在跟踪目标非特定，以及目标在跟踪过程中变化大的情况.因此，随着在线机器学习算法的迅速发展，基于在线学习的目标跟踪算法成为近几年的研究热点之一.视频是三维物体向二维平面的投影，复杂场景中噪声、遮挡、背景干扰和目标表观的变化等都给目标跟踪带来极大挑战［4］.一个好的目标跟踪算法，一般得满足如下3点要求［5］：1）鲁棒性，即在在复杂条件下，跟踪算法也能很好地跟踪目标；2）适应性，即跟踪算法能够自适应处理目标自身及其周围背景的变化；3）实时性，即目标跟踪需要实现对视频流的实时处理.本文对基于在线机器学习的目标跟踪算法的研究现状进行比较和分析.

1 跟踪器关键技术

目标描叙模型是跟踪器中关键的一环，它和最终的跟踪效果密切相关［5］.由于目标是被背景环绕的，除了考虑目标本身的模型外，还需要考虑目标周围的背景给跟踪器带来的有用信息.考虑背景信息，可以使目标的描叙模型针对背景特征构建，从而获得强的识别能力.Collins等［6］提出实时的，在候选特征空间中选择最能区别目标和背景的特征来构建前景和背景模型，巧妙地把背景信息融入前景描叙模型建立的过程，获得鲁棒的跟踪结果.如果背景中物体（特征块）和跟踪目标在运动上有一定关系，可以假设背景中的物体（特征块）与目标的相对位置在短时间内不变，用背景物体（特征块）和前景模型共同定位跟踪目标的位置［7］.在目标跟踪中，背景中有很多临时但和跟踪目标有很强关联的非目标物体.

跟踪器要有强的适应性，目标的描叙模型需要实时更新.建立自适应的模型后，用估计出来不精确的前景和背景区域来更新目标模型时，就会使目标模型的质量下降，最终发生目标漂移.在视觉领域，有很多研究者提出减少自适应模型漂移问题的方法，如在线学习过程中加入结构限制［8］，用多实例学习来更新分类器［9］，使用半监督范式更新Boosting分类器［10］，使用多分类器融合［11－13］，提出对野点鲁棒的方法［14］，等等.这些方法都能在不同程度上减少自适应模型的漂移问题.但对于长时间的跟踪，模型的更新仍然是一个非常具有挑战性的问题.

如何有效在当前帧中搜索目标位置，是保证精确度下提高实时性的重要方向.由于跟踪的特殊性，目标在当前帧的位置只可能出在前一帧目标位置的周围.因此，可以使用粒子滤波［15］等随机搜索策略来搜索目标.与穷尽搜索相比，随机搜索策略主要优势就是在跟踪过程中减少采样图像块数目.然而，粒子滤波也有自身的问题，即容易出现优秀粒子贫乏的问题.很多学者提出方法来解决这个问题，如LU等［16］采用RANSACK和粒子滤波的混合采样策略来解决好粒子贫乏的问题.

2 基于在线Boosting的目标跟踪算法

大多数Boosting方法都是离线学习，训练和分类器预测是分开的.有研究者把随机过程及优化方法与分类器更新结合起来，实现在线的机器学习.但不管是引入随机过程还是优化方法，都需要解决两个问题：1）在训练样本依次送给分类器时，如何更新分类器；2）如何高效地在所有候选弱分类器中挑选好的分类器来Boosting.

Avidan［17］提出使用AdaBoost方法来结合若干弱分类器，构成一个比较强的分类器，用获得的强分类器对当前帧像素点进行二值分类，产生置信图，使用MeanShift进行目标定位.即为了解决分类器对目标外观变化的适应性，在每一帧跟踪完成后，会在训练一些新的弱分类器来替换在当前帧性能较差的弱分类器.算法最大亮点就是分类器在线更新以适应目标外观变化.

Oza等［18］提出在训练Boosting分类器时，把Possion过程与在线更新弱分类器权值相结合来更新分类器，彻底改变离线状态下训练样本批量处理的方式.从理论上可以证明，当在线分类器获得的样本数达到一定数目后，其性能只稍逊离线训练的分类器.

Grabner等［19］把在线Boosting算法引入计算机视觉领域，用于Boosting的弱分类器都是从对应的特征池挑选出来的当前最优弱分类器.在用于Boosting的分类器数目相同的情况下，Grabner的在线学习算法比Oza的适应能力更强，更能获得当前样本模式.

Liu等［20］用基于梯度寻优的算法来选择最优的弱分类器.该方法比随机方式效率更高地找到较优的分类器.Saffari等［21］首次将在线学习与多类Boosting结合，其认为二值分类和基于二值分类的多类别分类通常不能完全获得特征空间中类别的结构和关系.Saffari把离线线性规划Boosting拓展到在线学习领域［22］，并把在线多类别Boosting转化为一个线性规划领域的优化问题，通过原－对偶梯度下降策略来解决这个优化问题.该算法不需要事先指定类别数，能在线根据需要添加新类别.在目标跟踪中，把快速变化、复杂和杂乱目标背景当做单一类别处理是不合理的，在线多类别Boosting能自适应调整背景对于类别数，使得跟踪器更加鲁棒.

Grabner等［10］为缓解跟踪中的漂移问题，把半监督的Boosting引入到跟踪领域［23］.Grabner提出的在线半监督Boosting和其在文献［19］中提出的在线Boosting最大区别，就是能够使用没有标记的样本来更新分类器模型.该算法对没有标记的样本有一个动态变化的伪标记，即可以用在线Boosting来组合弱分类器.在为更新分类器获取训练样本时，可以在最有可能是目标的位置周围随机抽取图像块（无标记），使用这些图像块来更新分类器.

3 基于森林的目标跟踪算法

随机森林及由随机森林衍生得到的霍夫森林主要有以下4个优点：1）算法简单，训练和分类速度很快；2）容易并行处理及在当前流行的多核、GPU框架中实现；3）随机森林能很自然处理多类问题；4）相对于Boosting及其他组合弱分类器的方法，随机森林对样本错误标记更加鲁棒.通常随机森林是离线训练，其具有和离线算法共通的内存消耗大、自适应弱、目标特定等缺陷.实现在线随机森林主要有3个思路：1）在一定规则指导下，在线的生成树的节点；2）树结构不变，在线更新叶子节点统计信息；3）融合前两种在线策略.

Saffar等［14］用在线Bagging和极度随机树来实现在线随机森林.由于硬分裂规则，决策时的递归特性使得发生的误差无法修正，进而使基于随机森林的在线学习成为一个困难的问题.Saffar把在线Bagging［18］和特征随机选择的在线决策树结合，使用算法时加权遗忘，并以新树替换旧树的方法来减小以前的样本对当前森林的影响.

Schulter等［24］使用文献［14］中的决策树在线生成规则生成在线霍夫森林.文献［25］用霍夫森林代替ISM中的码本，用投票机制来检测和跟踪目标.霍夫森林是从训练数据学习到的一些决策树组成一颗森林，森林中每一颗树可以把图像或者视频元素中的局部表观对应到树的叶子节点，每个叶子节点存有向霍夫空间投票的投票向量及其投票权重.该文中随机森林结构是离线训练的，在跟踪过程中实时更新叶子节点的统计信息.利用跟踪结果，向森林反馈那些投向目标的投票向量，对这些投票向量加大权重.利用这种反馈机制使跟踪效果更加鲁棒.

Godec等［26］提出一种在线霍夫森林算法及一种基于分割的精确目标表示.该算法用边界框表示非刚性目标，即使目标定位准确，还是会在森林在线自学习过程中引入大量噪声.基于分割的精确目标表示能够很好地处理非刚性目标，是因为分割后的目标能够减少很多错误标记的训练样本.Godec等把霍夫森林拓展到在线领域，把基于投票的检测、反向投票，以及GrabCut分割联合起来，很好地处理跟踪问题.为了让森林中的决策树有强的泛化能力，把树的分裂测试和阈值的选择都随机化.由于完全随机化无法保证树的表达能力，有些树的大多数叶子节点会很稀疏.为了解决这个问题，该算法先生成很多树，然后在这些树中挑选表达能力强的一些树来组成森林，即不仅保证森林的泛化能力，又具有一定表达能力.该算法采用在线更新叶子节点统计信息的方法来使森林适应目标变化，其分割过程采用反向投票机制获得分割算法的前景种子，接着用Grabcut来进行粗略分割，并用分割得到的结果更新森林叶子节点的统计信息.

4 在线协同训练

协同训练（co－training）是一种半监督学习技术［27］，需要同一数据的不同角度的特征.协同学习首先从每个特征角度用标记样本学习一个分类器；然后，用这些相互独立的分类器来对未标记的数据进行预测.每个分类器都会对样本预测都有置信度.挑选置信度较高的作为有标记的训练样本来更新与之相对的分类器，增强分类器的能力.从协同学习的角度来看，前面介绍的两种目标跟踪算法都是自学习方式，即用自己的预测结果来更新自己.自学习方式无纠错机制，容易倒置误差积累，最终发生漂移.

Tang等［28］把在线支持向量机和协同训练结合到一起，实现鲁棒跟踪.首先使用相互独立的特征（颜色直方图和HOG特征）训练两个独立SVM分类器；然后，使用SVM遍历下一帧视频，得到两张置信图，把置信图融合，定位目标位置；最后，使用协同训练方式在线更新SVM分类器.

Liu等［29］提出在协同训练框架下的Boosting误差上界来指导跟踪器的更新.该算法使用协同训练框架下衍生来的Boosting误差边界［30］来指导协同训练和Boosting的结合.多视角分类器之间的不一致率很大可能就是分类器误差上界.每一轮Boosting从两个独立特征池中挑选出两个视角独立的弱分类器，最小化分类器误差上界来协同挑选两个视角的弱分类器.多轮挑选后，把从这些两个视角得到的多个弱分类器加权组合成强分类器.

Leistner等［31］提出使用多视角的在线随机森林来做跟踪，使用多角度特征训练不同随机树组成多视角森林.在线更新树时，用Bagging方法从森林中随机采样一些树（不能包括更新的树）组成子森林对无标记样本进行标记，然后用标记的样本更新树.这样使得同一样本更新不同树时有可能出现不同标记，使森林更加鲁棒.由于很难保证不同特征之间完全独立性，因此也有可能造成模型更新时误差累积.

5 多跟踪器融合

单个分类器都有自身的缺陷，如果有好的方式把这些跟踪器融合起来，肯定能够增加跟踪器的鲁棒性.融合的关键在于选取用于融合的跟踪器及融合的机制.

Stalder等［32］提出分类器系统的思想.该系统由三类分类器构成，即离线训练得到的分类器（检测器）；在线有监督分类器（识别器）；在线半监督分类器（跟踪器）.离线分类器找到目标可能区域，该分类器的要求是泛化能力强，能够应用到任何场景.在线有监督分类器是特定目标的识别器，识别器只需要能在特定场景中有效.在线半监督分类器作用是在下一帧跟踪识别器识别到的目标.把跟踪得到的目标样本通过检测器检测后最终用来更新识别器.该算法有效解决了半监督学习［10］中先验分类器固定不变对半监督学习效果的影响.

Santner等［12］提出把基于模板相似度的跟踪算法（稳定）、基于光流的均值漂移算法（适应性强）及基于表观的在线随机森林（适应性适中）3个跟踪算法用分层方式结合起来，通过并行处理实现实时跟踪.此外，Stenger等［33］还提出使用多个跟踪器来跟踪目标，对每个跟踪器单独进行评估，用跟踪器中结果最好的或者用所有结果的组合作为最终结果.算法首先离线训练获得置信度和跟踪误差之间的关系，然后利用学习到的对应关系来在线评估跟踪器性能，根据当前帧各个跟踪器性能来融合跟踪器.文献［33］提出两种融合方式：1）并行启用多跟踪器，挑选最优或者加权组合跟踪器结果；2）跟踪器依次启用，一旦有一个跟踪器性能超过设定的性能阈值，该跟踪器结果作为跟踪结果（其他跟踪器就不启动）.

Zhong等［13］把跟踪问题视为弱监督学习问题来解决.把多个跟踪器看做多个标记源，使用弱监督学习来得到目标位置，以及在线评估每个跟踪器的性能.与文献［33］相比，该算法不需要离线获得跟踪器性能与某个可观测变量之间关系，而是通过EM算法迭代获得最优的标记结果和各跟踪器的精度.

6 算法性能比较与分析

目前，跟踪算法的评价主要有定性评价和定量评价两种方法.定量评价与定性评价相互补充，使得评价效果更为完善和充分.通过在公共的视频数据库上，使用视频跟踪算法来跟踪同一目标，跟踪器得到的目标位置与真实的目标位置的偏差来评估算法的跟踪精度.

总的来说有3种主要计算方法：1）跟踪到目标的帧数占全部视频帧的比例；2）从视频每一帧跟踪器得到的目标位置和实际位置偏差所获得的目标位置偏差图；3）计算跟踪器得到的目标框与真实目标框之间的重叠面积占所有面积的比例.

为了对目前系统有一个直观的认识，对一些典型算法的实验结果和所采用方法的特点进行比较，结果如表1所示.从表1可以看出：使用基于在线机器学习的方法，越来越优秀的机器学习算法、更加有效地在线学习策略、以及跟踪算法与分割算法的协调或跟踪算法与检测算法的协同等，可以极大地改进的跟踪算法的精度.但是由于每一种跟踪算法都有其自身的优点和缺点，因此通常情况下只能处理某一些特定类型的变化，很难确保某一特定类型的跟踪算法能够处理复杂跟踪场景中的所有不确定因素.

表1 典型跟踪算法的比较Tab.1 Comparison of the typical tracking algorithms

7 总结与展望

基于自学习的方法使用自身对样本的标记来更新模型，容易引入错误标记的样本，并且容易产生误差积累，最终发生目标漂移.为了解决自学习的漂移，有些研究者提出不对新样本进行确切的标记，而用半监督的方式来处理这些样本，减少漂移.虽然半监督学习能够解决一些漂移问题，但当实际目标跟踪发生很大变化时，先验分类器无法对当前目标的预测给予很大置信度，就弱化了半监督过程，也容易发生漂移.目前，有研究者提出多先验（先验更新）的半监督学习［32］来解决单纯半监督的问题.

此外，一些研究者提出使用协同训练的方式来解决目标漂移过程，同一样本提取独立的两类特征，训练两个独立的分类器，使用协同方式来在线更新分类器.由于很难保证特征之间的独立性，因此可能会造成模型更新时误差累积.由于单一跟踪器总是有其不足之处，有一部分研究者从多跟踪器融合的角度来处理漂移问题.

从总的思路来看，本文认为可以从3个方面入手来解决漂移问题.1）提出新的鲁棒在线学习算法，使其能够有鲁棒跟踪结果；2）对在线分类器获得的目标位置使用其他方法进行修正，如使用分割算法修正目标位置；3）使用多跟踪器的融合，实现鲁棒跟踪.

［1］韩崇昭，侯志强.视觉跟踪技术综述［J］.自动化学报，2006，32（4）：603－617.

［2］谭铁牛，王亮，胡卫明.人运动的视觉分析综述［J］.计算机学报，2002，25（3）：225－237.

［3］章毓晋，贾慧星.车辆辅助驾驶系统中基于计算机视觉的行人检测研究综述［J］.自动化学，2007，33（1）：84－90.

［4］YILMAZ A，JAVED O，SHAH M.Object tracking：A survey［J］.ACM Computing Surveys，2006，38（4）：13－20.

［5］YANG Han－xuan，SHAO Ling，ZHENG Feng，et al.Recent advances and trends in visual tracking：A review［J］.Neurocomputing，2011，74（18）：3823－3831.

［6］COLLINS R T，LIU Yan－xi，LEORDEANU M.Online selection of discriminative tracking features［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1631－1643.

［7］GRABNER H，MATAS J，VAN G L.Tracking the invisible：Learning where the object might be［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：1285－1292.

［8］KALAL Z，MATAS J，MIKOLAJCZYK K.PN learning：Bootstrapping binary classifiers by structural constraints［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：49－56.

［9］BABENKO B，YANG M H，BELONGIE S.Visual tracking with online multiple instance learning［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.Colorado：IEEE Press，2009：983－990.

［10］GRABNER H，LEISTNER C，BISCHOF H.Semi－supervised on－line boosting for robust tracking［C］∥Proceedings of the Europe Conference on Computer Vision.Marseille：Springer Press，2008：234－247.

［11］KIM T K，WOODLEY T，STENGER B，et al.Online multiple classifier boosting for object tracking［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition Workshops.San Francisco：IEEE Press，2010：1－6.

［12］SANTNER J，LEISTNER C，SAFFARI A，et al.Prost：Parallel robust online simple tracking［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：723－730.

［13］ZHONG Bi－neng，YAO Hong－xun，CHEN Sheng，et al.Visual tracking via weakly supervised learning from multiple imperfect oracles［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：1323－1330.

［14］SAFFARI A，LEISTNER C，SANTNER J，et al.On－line random forests［C］∥Proceedings of the International Conference on Computer Vision Workshops（ICCV Workshops）.Kyoto：IEEE Press，2009：1393－1400.

［15］ISARD M，BLAKE A.Condensation：Conditional density propagation for visual tracking［J］.International Journal of Computer Vision，1998，29（1）：5－28.

［16］LU L，DAI X T，HAGER G.A particle filter without dynamics for robust 3dface tracking［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition Workshop.Washington：IEEE Press，2004：70.

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

［18］OZA N C，RUSSELL S.Online bagging and boosting［C］∥Proceedings of the International Conference on Artificial Intelligence and Statistics.Florida：IEEE Press，2001：2340－2345.

［19］GRABNER H，BISCHOF H.On－line boosting and vision［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.New York：IEEE Press，2006：260－267.

［20］LIU Xiao－ming，YU Ting.Gradient feature selection for online boosting［C］∥Proceedings of the International Conference on Computer Vision.Rio de Janeiro：IEEE Press，2007：1－8.

［21］SAFFARI A，GODEC M，POCK T，et al.Online multi－class lpboost［C］∥Proceedings of the International Conference of Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：3570－3577.

［22］DEMIRIZ A，BENNETT K P，SHAWE T J.Linear programming boosting via column generation［J］.Machine Learning，2002，46（1）：225－254.

［23］LEISTNER C，GRABNER H，BISCHOF H.Semi－supervised boosting using visual similarity learning［C］∥Proceedings of the International Conference of Computer Vision and Pattern Recognition.Alaska：IEEE Press，2008：1－8.

［24］SCHULTER S，LEISTNER C，ROTH P M，et al.Online hough forests［C］∥Proceedings of British Machine Vision Conference.Dundee：Springer Press，2011：1－11.

［25］GALL J，YAO A，RAZAVI N，et al.Hough forests for object detection，tracking，and action recognition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（11）：2188－2202.

［26］GODEC M，ROTH P M，BISCHOF H.Hough－based tracking of non－rigid objects［C］∥Proceedings of International Conference of Computer Vision.Barcelona：IEEE Press，2011：81－88.

［27］BLUM A，MITCHELL T.Combining labeled and unlabeled data with co－training［C］∥Proceedings of the eleventh Annual Conference on Computational Learning Theory.Madison：ACM Press，1998：92－100.

［28］TANG Feng，BRENNAN S，ZHAO Qi.Co－tracking using semi－supervised support vector machines［C］∥Proceedings of the International Conference of Computer Vision.Rio de Janeiro：IEEE Press，2007：1－8.

［29］LIU Rong，CHENG Jian，LU Han－qing.A robust boosting tracker with minimum error bound in a co－training framework［C］∥Proceedings of the International Conference on Computer Vision.Kyoto：IEEE Press，2009：1459－1466.

［30］DASGUPTA S，LITTMAN M L，MCALLESTER D.Pac generalization bounds for co－training［C］∥Proceedings of the Advances in Neural Information Processing Systems.Whistler：MIT Press，2002：375－382.

［31］LEISTNER C，GODEC M，SAFFARI A，et al.Online multi－view forests for tracking［J］.Pattern Recognition，2010，6327（10）：493－502.

［32］STALDER S，GRABNER H，VAN G L.Beyond semi－supervised tracking：Tracking should be as simple as detection，but not simpler than recognition［C］∥Proceedings of the International Conference on Computer Vision Workshops.Kyoto：IEEE Press，2009：1409－1416.

［33］STENGER B，WOODLEY T，CIPOLLA R.Learning to track with multiple observers［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.Florida：IEEE Press，2009：2647－2654.