基于改进On-line Boosting算法的视频目标跟踪

蔡明琼，郭太良，姚剑敏

(福州大学 平板显示技术国家地方联合工程实验室，福建 福州 350116)

基于改进On-line Boosting算法的视频目标跟踪

蔡明琼，郭太良，姚剑敏

(福州大学 平板显示技术国家地方联合工程实验室，福建 福州 350116)

针对目前基于在线学习的On-line Boosting 算法用于视频目标跟踪时对于快速移动的目标，容易引起跟踪漂移的问题，提出一种将Surf算法融合于On-line Boosting的Surf-Boosting视频目标跟踪算法。该算法在原先的On-line Boosting算法的基础上增加跟踪漂移判断，对已跟踪漂移的视频帧使用Surf算法进行目标定位，将Surf定位到的目标作为正样本放到后续On-line Boosting算法中继续跟踪学习。实验结果表明，该方法能够很好地抑制原有算法的跟踪漂移问题，在跟踪过程中的正确率达到98%，实现对快速移动目标的正确跟踪，并具有很好的鲁棒性。

On-line Boosting；Surf；快速移动；目标跟踪

在计算机视觉中，视频目标跟踪是一个重要的研究方向，它是后续更高层次行为理解如：目标行为分析、行为识别、视频图像压缩等的基础核心技术之一，广泛应用于公共安全领域、军事国防领域、医学检测领域等。On-line Boosting算法应用于视频目标跟踪，是一种基于在线学习的目标跟踪算法，它把跟踪问题看做是一个背景和目标的分类问题[1]，得到了广泛的应用。

基于学习的目标跟踪算法，近年来引起了国内外学者的广泛关注，在文献[2-4]中提出的基于在线关键帧的选择，是一种无结构的最近邻在线学习模型，该方法的优点是数据简单，学习速度快，可以时时更新，缺点是模板匹配准确度低，容易丢失跟踪目标；在文献[5]中Jepson 等人重点研究了3种基周期混合学习模型：长期稳定模板、短期稳定模板和噪声模板，并认为任何的跟踪模型都是上述3种模板的线性叠加；Sung， Kim和 Ross等人在文献[6-7]中提出快速有效的增量学习策略，利用新到来的数据更新原有的均值向量和特征子空间。

Grabner 从2006年开始对在线学习的目标跟踪算法进行了大量的研究，发表了众多的文献，其经典的算法是文献[8]提出的基于Haar-like 特征的On-line Boosting算法，该算法具有学习速度快、无需提前训练分类器以及可实现实时跟踪的优点，2012年其在文献[9]中提出了一种基于目标的运动特点，并将运动特点考虑到目标跟踪中的算法，该算法虽然能够在一定程度上抑制跟踪漂移，但是对快速移动的目标的跟踪漂移抑制能力仍然不足。对于快速移动的目标，目前的方法还不能进行正确有效的跟踪，对于跟踪过程中引起跟踪漂移，没有一个合适的机制，用于恢复这种漂移，以便进行后续的跟踪。针对以上所述的一些不足，本文提出了一种改进的On-line Boosting算法用于视频目标跟踪，该算法在跟踪过程中增加跟踪漂移的判断，对跟踪漂移的视频帧使用Surf(Speeded up robust features)[10]算法正确定位目标，再把定位到的目标当做正样本，放到后续的跟踪中继续学习，Surf算法具有快速计算能力，保证了跟踪的实时性，最终实现对快速移动目标的正确跟踪，具有良好的鲁棒性。

1 基于On-line Boosting的视频目标跟踪及其不足

在机器学习中，Boosting算法是一种用于提高任意给定学习算法准确度的通用方法，其思想是源于Valiant提出的 PAC (Probably Approximately Correct)学习模型。Boosting 通过给定的样本，循环训练N个弱分类器，再将这些弱分类器按照一定的方式组合成一个强分类器，On-line Boosting 用于视频目标跟踪中，弱分类器的训练是在线的，最终的强分类器可用于区分背景和目标，从而将目标从复杂的背景中识别出来。

1.1 算法的理论介绍

强分类器：一个强分类器hstrong(x)是由若干个弱分类器线性组合而成的，它的识别误差率很低，强分类器的识别结果是由式(1)决定的

(1)

式中：an表示每个弱分类器所对应的权重；N表示所有弱分类器的个数。

图1 On-line Boosting算法用于视频跟踪流程图

(2)

按照同样的方式更新一个特征池中所有的弱分类器，选择器从中选择误差率en最小的弱分类器m+=argminm(en,m)作为当前选择的结果

(3)

en=en,m+

(4)

1.2 算法应用在视频目标跟踪中的不足

由算法的流程描述可知，一个强分类器的形成是由若干的弱分类器组成的。从单个视频帧中的训练样本来看，在训练弱分类的过程中，前n个弱分类器训练后得到的样本权重值，将影响到第n+1个弱分类器的误差以及受误差影响的弱分类器权重和样本权重的更新值，当视频目标快速移动的时候，可能出现前n个弱分类器更新完毕，但是后面的弱分类器没有得到训练，也就是目标移动的速度超过了弱分类器的学习速度，那么就会造成特征学习不充分，形成的强分类器就不会有强的区分能力。从多个连续的视频帧来看，对于快速移动的目标，由于目标移动太快，使得当前帧学习到的特征来不及更新到下一帧，那么下一帧学习到的特征有可能是错误的特征，在后续的跟踪中，错误特征得到累积，最终就会造成跟踪的漂移，并且该漂移是不可逆的。

2 改进的On-line Boosting算法

2.1 改进算法流程

改进的On-line Boosting 算法用于视频跟踪中，其创新点体现在原有的算法基础上，增加跟踪漂移的判断，并将Surf 算法融入到On-line Boosting中，用于正确定位目标，恢复漂移，实现实时而准确的跟踪。通过增加阈值判断，对算法中的分类器学习情况进行判断，学习特征值高于指定阈值，则继续跟踪学习，低于指定阈值的则用Surf算法进行二次定位。Surf算法具有尺度和旋转不变的检测器和特征描述子，最大的优点在于计算速度快，可实现实时匹配的效果，因此适于用在视频目标跟踪中用于实时对所跟踪的目标进行匹配。

图2 改进的算法框架

2.2 Surf算法融于On-line Boosting目标跟踪算法

Surf算法用于目标跟踪是一种基于特征的图像匹配算法，由Herbert Bay等人在2006年提出[10]，其算法原理分为：特征点提取、构建特征点描述子以及特征点匹配三部分，其与基于On-line Boosting 视频目标算法的融合体现在辅助原算法在跟踪漂移时快速有效地进行模板特征匹配，从而正确地定位到跟踪目标。在跟踪漂移时，Surf算法的流程如下。

1)对匹配模板和跟踪错误帧进行特征点提取

在Surf算法中，特征点是指比周围领域的点更暗或者更亮的点，采用近似Hessian矩阵的行列式值的局部最大值来定位该特征点。高斯滤波后的Hessian矩阵表达式为

(5)

(6)

det(H)=LXX·LYY-(LXY)2

(7)式中：X表示像素点的位置；δ表示尺度；L(X,δ)是图像在不同尺度下的表示；LXX是高斯模板与图像的卷积；g(δ)为高斯滤波器；δ是高斯滤波器的方差；det(H)表示该点的特征值。

通过以上的步骤可以分别得到匹配模板和跟踪错误帧的Hessian行列式图，接下去需要构造图像金字塔，这一步是通过改变滤波器模板的尺寸大小和高斯模糊尺寸大小来构造不同的图片层的，同一层中的图片用到的高斯模板尺度也不同。算法允许尺度空间多层图像同时被处理，不需对图像进行二次抽样，从而提高算法性能。

利用非极大值抑制初步确定特征点，方法是通过将金字塔图像中的每一个像素点与其三维领域的26个点大小比较，如果该像素点为最大值，则初步定为特征点。通过3维线性差值找到亚像素的特征点，实现精准定位特征点，最后去掉一些小于一定阈值的点。

2)构建匹配模板和跟踪错误帧特征点描述子

以特征点为中心，在半径为r领域内计算Harr小波特征。在一个60°扇形内统计所有点的水平Haar小波特征和垂直Haar小波特征总和。每个扇形得到一个值，然后以一定间隔旋转60°扇形，选出最大值那个扇形的方向作为该特征点的主方向，以达到旋转不变性，选定主方向后，在特征点周围取一个带方向的正方形框，方向为特征点的主方向，将该框分为16个子区域，统计每个子区域相对于主方向的水平方向和垂直方向的Haar小波特征，计算该Haar小波特征水平方向值之和，水平方向绝对值之和，垂直方向之和，垂直方向绝对值之和，这样每个小区域就有4个值，所以每个特征点就是 16×4=64维的向量。

该过程的示意图如图3所示。

图3 构建特征点描述子

3)对匹配模板和跟踪错误帧进行特征点匹配

当匹配模板和跟踪错误帧进行特征点匹配时，是计算跟踪错误帧中每个特征点与匹配模板中的所有特征点的欧氏距离，形成一个距离集合，比较距离集合中的最小欧氏距离和次小欧氏距离的比值，如果小于设定的阈值，则认为该特征点是与最小欧氏距离点匹配，否则该点没有匹配点，所设定的阈值越小，匹配就越稳定。

3 实验结果及分析

本次实验在Microsoft Visual Studio 2010 的软件环境下，针对快速移动的视频目标，将改进后的Surf-Boosting与Grabner等人在文献[9]提出的基于运动特点的目标跟踪算法进行比较，在跟踪过程对跟踪结果取置信值0.5，对Surf算法的匹配结果取阈值0.2。针对快速移动的目标，在第一帧中框出跟踪目标，实验结果如下。

对于快速移动的目标，基于运动特点的实验结果如图4所示。

图4 基于运动特点的实验结果

对于快速移动的目标，改进后的Surf-Boosting算法实验结果如图5所示。

图5 改进后的Surf-Boosting算法实验结果

从实验结果可以看出，原有算法对于快速移动的目标的跟踪效果不佳，会出现跟踪的漂移，并且这种漂移是不可逆的，从第139帧后，分类器更新错误，这种错误会直接传递到后续的跟踪中，直接影响到后续的跟踪结果。通过改进后的算法，由于结合了鲁棒的Surf 算法，并增加了阈值判断，对于快速移动的目标有了较好的鲁棒性，能很好地适应跟踪过程中目标的快速变化。在所检测的2 000帧视频帧中能够正确检测到1 960张，正确率达到98%。

4 小结

本文所提出的一种新的改进On-line Boosting算法，是一种普遍的视频目标跟踪算法，在保证原有算法的优点的同时，弥补了原有算法在快速移动目标跟踪上的不足，减少了原有算法跟踪漂移的可能，更加适应实际生活中的各种场景，具有广阔的应用前景。

[1] AVIDAN S. Ensemble tracking[C]//Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]：IEEE Press，2005：494-501.

[2] VACCHETTI L，LEPETIT V，FUA P. Stable real-time 3D tracking using online and offline information[J].IEEE Trans. Pattern Analysis and Machine Intelligence，2004，26(10)，1385-1391.

[3] MORENCY L P，WHITEHILL J，MOVELLAN J. Generalized adaptive view based appearance model：integrated framework for monocular head poseestimation[C]//Proc. 8th IEEE International Conference on Automatic Face and Gesture Recognition(FG 2008).[S.l.]：IEEE Press，2008：1-8.

[4] WANG Q，ZHANG W，TANG X，et al. Real-time Bayesian 3-d pose tracking[J].IEEE Trans. Circuits and Systems for Video Technology，2006，16(12)：1533-1541.

[5] JEPSON A D，FLEET D J，El-MARAGHI T F. Robust online appearancemodels for visual tracking[J]. IEEE Trans. Pattern Analysis and Machine Intelligence，2003，25(10)：1296-1311.

[6] SUNG J，KIM D. Adaptive active appearance model with incremental learning[J].Pattern Recogn. Lett.，2009，30(4)：359-367 .

[7] DAVID R，LIM J，LIN R S，et al. Incremental learning for robust visual tracking[J].International Journal of Computer Vision， 2008，77(1)：125-141.

[8] HELMUT G，BISCHOF H. On-line boosting and vision[C]//Proc. Computer Vision and Pattern Recognition.[S.l]：IEEE Press，2006：260-267.

[9] STALDER S，GRABNER H，VANGOOL L. Dynamic objectness for adaptive tracking[C]//Proc. Asian Conference on Computer Vision.[S.l]：IEEE Press，2012：43-56.

[10]HERBERT B，ANDREAS E，TUYTELAARS T，et al. Speeded-up robust features(SURF)[J]. Computer Vision and Image Understanding，2008，110(3)：349-356.

责任编辑：时 雯

Video Target Tracking Based on Impoved On-line Boosting Algorithm

CAI Mingqiong，GUO Tailiang，YAO Jianmin

(NationalandLocalJointEngineeringLaboratoryofFlatPanelDisplayTechnology，FuzhouUniversity，Fuzhou350116，China)

In view of that the present way of On-line Learning video target tracking algorithm based on the On-line Boosting algorithm would cause tracking drift easily， the thesis put forward a kind of new improved algorithm called Surf-Boosting which combine Surf algorithm to the On-line Boosting algorithm in video target tracking .Compared with the original On-line Boosting algorithm，the improved algorithm add the judgment of tracking drift and can locate target by using Surf algorithm when tracking drift.After that the target located by surf algorithm can be learned as a positive sample in follow-up tracking. The experimental result whose accuracy is 98% show that the improved robust method can restrain the tracking drift and realize good tracking on fast moving target effectively.

On-line Boosting；Surf；fast moving；target tracking

国家“863”重大专项(2013AA030601)；福建省自然科学基金项目(2011J01347)

TP227

A

10.16280/j.videoe.2015.16.018

2014-11-23

【本文献信息】蔡明琼，郭太良，姚剑敏.基于改进On-line Boosting算法的视频目标跟踪[J].电视技术,2015，39(16).