基于随机森林的长期目标跟踪方法

张 丹，陈兴文，赵姝颖，程立英，3

(1.大连民族学院创新教育中心，辽宁大连116605;2.东北大学信息科学与工程学院，辽宁沈阳110819;3.沈阳师范大学物理科学与技术学院，辽宁沈阳110034)

目标跟踪的研究与应用是计算机视觉的一个重要分支，也是其研究领域中的难点和热点，广泛应用于科学研究、航空航天、医学、国防军事、人机交互、机器人及国民经济的各个领域。目标跟踪的关键技术在于合理提取特征和准确的识别目标，实时、准确的长期目标跟踪对于人机交互技术、人工智能等技术的发展具有重要的理论意义和应用价值。

长期目标跟踪过程中，易出现目标的遮挡、丢失、运动速度过快等问题。光照干扰、复杂多变背景使得跟踪过程中计算量大、处理滞后，影响跟踪效果。这些问题给快速、精确的长期目标跟踪造成很大的难度。

国内外学者已经对长期跟踪作了大量研究，Jorge［1］等人提出区域跟踪算法，利用分割结果，将连续帧的目标匹配起来进行跟踪;Moravec［2］提出利用图像灰度自相关函数的特征点检验算子;Kass［3］等人提出 Snake 模型，Menet［4］提出 B-Snake模型，解决了快速跟踪的问题;Deilamani M.J［5］等人提出了将色彩与边缘特征相结合的Mean-Shift算法，可以很好的克服部分遮挡和光照的变化;Dr.Zdenek Kalal［6］在 2007 年到 2010 年间提出来并不断完善的TLD算法，适合长时间跟踪;chen等人［7］提出基于四元数的光流估计跟踪方法，提高了算法的鲁棒性;陈添丁等人［8］提出的稀疏光流快四计算动态目标检测与跟踪算法，一定程度上提高了跟踪的实时性;Wang等人［9］提出在线学习跟踪的方法，提高了目标跟踪的精度，王爱平［10］等人提出增量式随机森林分类器，提高了短视屏流跟踪的准确性;袁红卫等人［11］提出一种基于光流的运动小目标检测算法;佟国峰等人［12］提出一种基于随机蕨丛的长期目标跟踪方法，提高了跟踪的适应性;李劲菊［13］，郝志成［14］等人提出了一种复杂背景下运动目标检测与跟踪的方法，提高了复杂背景下目标跟踪的准确性。这些方法一定程度上解决了目标遮挡、快速运动的跟踪问题，但是目标一旦丢失，无法快速恢复跟踪，在复杂背景快速变化的过程中也难以实现实时、准确的跟踪。

本文针对长期跟踪情况下目标由于遮挡、快速运动易丢失、跟踪实时性、准确性差等问题，结合正负样本相互作用的思想和随机森林算法，提出了一种基于TLD的随机森林目标跟踪方法。该方法在TLD算法的基础上，采用随机森林方法，构建在线学习模型，融合大运动捕捉跟踪器，分别从跟踪实时性、准确性上进行改进。

1 随机森林算法及分析

1.1 随机森林算法

单棵决策树可以按照结点属性值进行分类，为了明显提高精度，很容易想到种植一片树林，并让所有树参加投票，选出最好的分类，这就是随机森林［13］的思想。对第k棵树引入随机变量θk，它与前面的k-1 个随机变量 θ1，θ2，…θk-1是独立同分布的。通过训练集θk来生成第k棵树，相当于产生一个分类器h(X，θk)，其中X是一个输入量。随机森林有较好的数学理论基础，不会出现过度拟合，符合大数定律。构建随机森林有多种形式和方法，可以根据实际需要，采用不同的方式构建随机森林。本文中采用更新权重构建方法中的Adaboost方法进行构建。Adaboost方法是由Freund和 Schapire于1996年正式提出的，它是在前面分类器错误分类的基础之上，为下一个分类器的输入，更新训练集上的权重，每个分类器都可以利用一个训练集和一个权重训练集来改进。

设w(1)，…w(k)(∑wi(k)=1，wi(k)≥0)为关于训练集的k个不同的权重向量，对训练集进行k种不同方式加权，这样，得到的加权数据构成一个大集合。取权重概率p(1)，p(2)，…p(k)且(i)=1 时，依据概率p(1)，p(2)，…p(k)从1，2，…k抽取整数，记为θ。利用训练集与权重w(k)产生分类器h(x，θ)。

在 Adaboost算法中，w(k+1)= φ(w(k))，φ是由起初分类器定义的函数。设第k个分类器为h(x，wk)，其投票权重为Q(wk)，所以对于将输入x分类为j的规范化投票等于:

Adaboost算法主要针对一个训练集训练不同的分类器，然后把这些弱分类器集合起来，构成一个最终分类器(强分类器)。

1.2 算法分析

随机森林有很多优点:精度高，稳定性好，可以有效的处理大数据集，在分类的过程中给出变量重要性的估计等，与其他集成方法相比，对于数据噪声更稳定［15］。随机森林方法虽然支持在线学习，但是在学习过程中也较为容易出现误判，如果数据集较大，算法运行时间长，那么积累的误差就更大，分类错误率将会上升［15］。而TLD方法加入正负样本互限思想，进行误差一致矫正，提高样本判别的准确性。因此，本文提出一种基于TLD的随机森林方法。

2 基于TLD的目标跟踪方法

2.1 在线学习模型

本文在线学习的过程主要使用正样本增长、负样本减少的方法。正样本增长与负样本减少同时进行，主要基于一个相似的阈值θ，当两个目标窗口样本的距离小于θ时就认为其与目标轨迹相似，反之亦然，这样不断的更新在线学习模型中的特征，使得特征更加精确。正样本增长过程为从跟踪轨迹中选择相似的样本并进行模型的更新。在负样本减少过程中，假设被跟踪的目标在场景中是唯一的，如果跟踪器和检测器都认为其中探测点是正确的，那么其余的探测点就被认为是负样本，并且从模型中移走。

在线学习模型主要依靠正负样本学习框架进行特征的更新。与目标轨迹接近的特征窗口使用正样本更新探测器，正样本增长。使用检测器检测目标，非最大置信度的探测点使用负样本更新，即负样本减少。它们相互作用产生误差，并不断的消除误差，使得学习更稳固，特征更精确。相互作用关系如图1。

图1 正负样本相互作用关系示意图

2.2 基于在线学习的随机森林目标检测器

将随机森林的思想与在线学习模型结合起来，以实现目标的在线学习检测模型，具体步骤如下:

(1)初始化分类器。提取正样本训练随机森林分类器，包含目标物体的矩形区域为正样本区域，其他部分被视为负样本区域，将大小规则的图像块作为样本进行处理，相对于单个像素而言，图像块包含更丰富的信息。在此阶段，为了给分类器提供足够的训练样本，在正样本区域和负样本区域内随机产生大量子窗口，这些窗口可相互重叠，且位置随机，每个子窗口从9×9像素大小到整幅图像大小随机产生，子窗口对应的图像块即可作为样本进行处理，这样即可完成分类器的初始化。

(2)在线学习模型。将分类器与在线学习模型相结合，构成增量式的随机森林分类器。采用2bitBP特征形成特征空间，利用滑动窗口方法，在线学习模型分别对同一视频图像进行分类识别，正样本增长模型将自身置信度高的样本给特征空间进行增量学习分类，同时负样本减少模型根据自身样本的置信度判断特征空间中的不正确样本，将其从特征空间中去掉。这样他们相互作用使得特征空间在不断扩大的同时，使得其特征更加精确，也使得分类更加精确。

得到的分类器与在线学习模型相结合，不断训练样本，如图2，具体步骤为:

(1)使用分类器标记未标记的样本;

(2)识别并重新标记违背结构限制的样本;

(3)不断的扩大训练集;

(4)重新训练分类器。

图2 在线学习与分类器训练数据示意图

其中Xu为未标记的用于训练的数据，(X1，Y1)为已经标记的训练集数据，(Xt，Yt)为训练集输出的数据，需要再进行训练的数据，结构限制主要是正样本增长和负样本减少，(Xc，Yc)是通过在线学习输出的数据，θ为在线学习所对应的分类器的估计数据。

2.3 基于捕获最大运动的目标跟踪器

基于在线学习的随机森林方法可进行目标检测，但是无法实现较大运动的目标跟踪。本文集合金字塔技术，采用LK光流法，根据所取特征，使用均值方式预测目标的运动和位移方向，与目标检测器相结合，实现长期的目标跟踪。

LK光流法［16］最初于1981年提出，由于算法易于应用在输入图像中的一组点上，后来成为求稀疏光流的一种重要方法，该方法基于亮度恒定、时间连续或者运动是“小运动”、空间一致三个假设，光流约束方程如(4)式所示。

将亮度的定义I(x(t)，t)表示，应用偏微分链式规则:

其中，Ix是图像的偏导数，It是随时间的导数，v是要求的速度。

前面是LK光流法在一维空间上的用法，将其扩展到二维图像上，速度的y分量为v，x分量为u，得到:

孔径问题即用小孔或小窗口去测量运动，只能观测到物体边缘而观测不到角点，只依靠边缘是不足以判断整个运动物体的运动朝向的。而角点是可用于跟踪的良好特征点，其检测几乎不受摄像机姿态和光照条件的影响，具有旋转不变性，在图像配准与匹配、运动估计等计算机视觉领域有着非常重要的作用。

但是，对于大多数30HZ的摄像机，大而不连贯的运动是普遍存在的。也正因为这个原因LK光流法在实际中的跟踪效果并不是很好，本文结合金字塔技术，计算所取特征均值进行改进，解决此问题。

该方法的思想如下:原图像作为金字塔基层I=0，将原图减采样至原尺寸的(一般N=1)，获得I=1层图像，则该层相邻帧间的目标像素运动距离为(D为原图中相邻帧间的目标像素运动距离)。当I达到一定值时(一般3≤I≤5)，可满足光流约束条件。在最高层Vf=0，图像细节最少，ΔVf是f层的光流计算结果，作为下一层图像的运动估计。

LK算法在帧与帧之间跟踪这些点，产生矢量光流场，根据所取的特征，使用均值的方式预测下一帧中目标的运动和位移方向。在每一帧中都有一系列的新的特征点被跟踪，因此使得跟踪具有较强的适应性，对部分遮挡的物体跟踪具有较好的鲁棒性，跟踪算法示意图如图3。

图3 跟踪算法示意图

2.4 算法描述

本文算法流程描述如下，算法流程图如图4:

1)根据视频帧，获得相应的训练集;

2)进行特征在线学习学习;

3)根据获得的特征不断的更新检测器和跟踪器，同时跟踪器和检测器也将得到的数据反馈给在线学习模型;

4)检测器对目标进行检测，与跟踪器相融合，对比置信度，实现目标的跟踪。

图4 算法流程图

3 实验结果与分析

实验计算机为 CPU E5500@2.80GHz，2GB内存，在Matlab R2009a环境下运行。本文中图像是RGB格式，分辨率为320*240，帧率为30帧每秒。视频包括原参考文献中的及自己录制的，分别为摩托车的运动［17］，由2917帧组成(2分33秒)，在这段视频中包含了目标的遮挡、消失、快速运动、特征的突然变化等;复杂背景下的非刚性球的运动，由(2452)帧组成(1分22秒)，包括了目标的遮挡、消失和相机的移动;复杂边缘物体的运动由(4740)帧组成(2分36秒)，包括了目标由慢向快的运动、遮挡、丢失、相似背景干扰和相机的移动。

图5中被跟踪的目标是非刚性软球，5(a)中由于手力的作用使得球变形，虽然深色采样点所取范围变小，但是从图中可以看出本算法依然可以找到跟踪目标的中心点，实现跟踪;5(b)中球面进行了滚动，即所跟踪的球面已经不是第一帧获得运动目标时的球面，但是通过球在运动过程中，对特征的不断学习，使得算法越来越精确，虽然球换面，但是依然能实现目标跟踪;5(c)中可以看到在手离开之后，本算法恢复了对变形球的跟踪，而且跟踪效果较好，这就是跟踪器、检测器和在线学习共同作用的结果。

图5 非刚性物体跟踪效果图

目标跟踪过程中获得的样本图如图6，6(a)中为所有样本，既包括目标样本也包括背景样本，6(b)为目标样本，即在跟踪过程中，通过计算与第一帧获得的标准目标样本的重合率大于50%的样本，这些样本主要是通过在线学习模型获得，虽然这些样本有各种变化，各不相同，但是还是可以搜索到漂移，时刻进行修正，跟踪目标。

图6 跟踪目标样本图

对三个目标的跟踪如图7，第一个是复杂背景的非刚性球跟踪，第二个是复杂背景下复杂边缘物体跟踪，第三个虽然背景较为简单，但是目标的运动速度非常的快。从图中可以看出无论是出现部分遮挡还是快速运动，本算法都进行了较好的跟踪。在7(a)和7(b)中运动目标的背景相当复杂，甚至有些背景的灰度与目标很接近，但是从跟踪效果可以看出，本算法在复杂背景下进行了实时准确的跟踪。在测试摩托车手的视频中，在出现部分遮挡之后，目标丢失，目标中心点与深色取样点出现了较大的偏差，但是在下一帧时，依然能检测到运动的目标，原因就是在前后两帧中运动目标由于运动速度非常快，位置发生很大的变化，而追踪对象的搜索范围较小产生的，但是在下一帧时算法便克服其误差，进行大范围的搜索，得到了运动目标。

图7 跟踪效果图

本文采用文献［18］中的评估标准，将跟踪过程中算法选择的所有目标窗口数(样本)定义为ST，手动选择的目标窗口(样本)个数定义为GT，如果跟踪获得的窗口和手动选择的窗口的重合率超过70%，就认为获得是正样本，用TP表示，否则为FP，准确率用P表示，定义为:

用R来表示正样本和手动选择目标窗口的比，定义为:

本文使用P和R这两个参数估计跟踪方法的质量。将本文方法与Mean-Shift算法和原TLD算法进行对比，跟踪质量见表1。

表1 跟踪质量表

从表1中可以看出TLD算法的准确率明显高于Mean-Shift算法，无论是哪种视频资源，都进行了很好的跟踪，复杂背景并没有影响跟踪效果;正样本对于手动选择的样本比例，本文算法也明显高于Mean-Shift算法，且高于TLD算法。由此可见，本文算法得到了较好的跟踪效果，准确率较高，可以进行复杂背景下运动目标的跟踪。

4 结论

对随机森林算法进行分析研究，结合TLD的思想，构建在线学习模型进行结构限制，使得分类结果更准确;为捕捉大运动目标，改进光流法构建跟踪器，设计结构，实现检测器与跟踪器的融合，并通过一系列实验对本文方法的有效性进行验证。实验表明，本文算法实现了刚性物体、非刚性物体在快速运动、部分遮挡、完全丢失、摄像机运动等情况下的跟踪，取得了较好的跟踪效果，跟踪准确率可以达到93%以上。

［1］JORGE B，BOBER M，PLA F.Motion and intensity based segmentation and its application to traffic monitoring［C］.In Proceedings，International Conference on Image Analysis and Processing ICIAP，Florence，Italy，1997:502-509.

［2］MORAVEC H P.Towards automatic visual obstacle avoidance［C］.In Proceedings of the 5th International Joint Conference on Artificial Intelligence，1977.

［3］KASS M，WITKINM A，TERZOPOULOS D.Active contour models［J］.International Journal on Computer Vision(IJCV)，1988，1(4):321-331.

［4］ MENET S，SAINT-MARC P，MEDIONI G.BSnakes:Implementation and application to stereo［C］.DARPA Image Understanding Workshop，1990，720-726.

［5］ DEILAMANI M.J，ASLI R N Moving object tracking based on mean shift algorithm and features fusion ［J］.Artificial Intelligence and Signal Processing(AISP).2011:48-53.

［6］KALAL Z，MIKOLAJCZYK K，MATAS J.Face-TLD:Tracking-Learning-Detection Applied to Faces［J］.International Conference on Image Processing，2010.

［7］CHEN E，XU Y，YANG X K，et al.Quaternion based optical flow estimation for robust object tracking［J］.Digital Signal Processing，2013，23(1):118-125.

［8］陈添丁，胡鉴，吴涤.稀疏光流快速计算的动态目标检测与跟踪［J］.中国图象图形学报，2013，18(12):1593-1600.

［9］WANG J，CHEN F，YANG J M，et al.Transferring visual Prior for online object tracking［J］.IEEE Transactions on Image Processing，2012，21(7):3296-3305.

［10］王爱平，万国伟，程志全，等.支持在线学习的增量式极端随机森林分类器［J］.软件学报，2011，22(9):2059-2074.

［11］袁卫红，卢雁，毛海岑，等.基于光流的运动小目标检测算法［J］.光学与光电技术，2012，1(10):67-70.

［12］佟国峰，蒋昭炎，谷久宏，等.基于随机蕨丛的长期目标跟踪算法［J］.东北大学学报:自然科学版，2013，43(1):4-8.

［13］李劲菊，朱青，王耀南.一种复杂背景下运动目标检测与跟踪方法［J］.仪器仪表学报，2010，31(10):2242-2247.

［14］郝志成.决策主导的多模式融合目标跟踪算法［J］.仪器仪表学报，2013，34(3):487-492.

［15］BREIMAN L.Random forests［J］.Machine Learning，2001，45(1):5-32.

［16］LUCAS B，KANADE T.An iterative image registration technique with an application to stereo vision［C］.Proceedings of DARPA Image Understanding WorkShop.San Francisco，USA:Morgan Kaufmann Publishers Inc.1981，147-151.

［17］CHAN T，VESE L.Active contours without edges［J］.IEEE Transaction on Image Processing，2001，10(2):266-277.

［18］ZDENEK K，JIRI M，KRYSTIAN M.Online learning of robust object detectors during unstable tracking ［J］.On-line Learning for Computer Vision Workshop，2009.