基于改进的随机森林TLD目标跟踪方法

张　丹，陈兴文，赵姝颖

(1.大连民族大学 工程教育学院，辽宁 大连 116605;2.东北大学 信息科学与工程学院，辽宁 沈阳 110819)



基于改进的随机森林TLD目标跟踪方法

张丹1，陈兴文1，赵姝颖2

(1.大连民族大学 工程教育学院，辽宁 大连 116605;2.东北大学 信息科学与工程学院，辽宁 沈阳 110819)

摘要：针对TLD算法中采用的随机森林分类器的决策树阈值固定，不能根据目标特征随时调整，影响分类精度和时间开销的问题，引入极端随机森林的思想，提出了基于改进的随机森林TLD目标跟踪方法。该方法用Gini系数度量样本集合的混乱程度，通过比较Gini系数是否超过了给定阈值，判断叶节点何时转变成决策节点进行分裂；再结合TLD算法中的P-N学习框架和在线模型训练更新样本；最终基于改进的TLD算法完成目标跟踪。将本文方法应用于多个视频集进行目标跟踪实验，验证了算法的有效性和稳定性。

关键词：目标跟踪；随机森林；TLD；分裂阈值；在线学习

针对决策树阈值固定，影响分类精度和实时性问题，引入极端随机森林的思想，结合在线学习模型，提出了一种基于极端随机森林的TLD改进算法，解决了分裂阈值不能根据目标特征随时调整，影响跟踪适应性的问题。

1TLD目标跟踪算法

TLD 算法主要由三部分组成：跟踪、在线学习和检测，其三者相互作用，将得到的数据整合，最终确定下一帧中目标的位置。

TLD算法各变量互相作用关系如图1。运动目标被一个短期的跟踪器跟踪。growingevent和pruningevent分析特征空间的轨迹，连续不断的试图扩展或是限制在线学习模型的特征。growingevent识别判断目标样本，使运动目标特征Lt不断扩大；pruningevent识别Lt中错误样本，并将它们去掉，growingevent和pruning共同进行，使得目标特征Lt→L*。

图1　TLD算法相关量关系图

TLD算法的检测器主要是一个级联分类器，其主要由方差滤波器、集成分类器及最近邻分类器三部分组成，集成分类器主要由n个随机蕨分类器构成的随机森林组成，随机蕨主要采用的是2bitBP特征，图像区域输入到集成分类器之后，获得后验概率。计算n个随机蕨分类器的后验概率，如果平均值大于阈值，则将该区域定为正样本，否则为负样本。

1.1.1 母本高不育系 W0176A选育。2003—2004年，用不同来源种质与0176A不育株广泛测交，配制各类测交组合，F1自交。

极端随机森林每棵决策树的决策点分裂测试阈值是随机选择的，不是以某一特征进行设定，保证了样本的丰富性，极端随机森林分类器在分类精度和训练时间开销等方面的性能较好，但采用的不是bootstrap策略，直接采用原始的训练样本，只能支持离线的训练方式，不支持增量学习[10]，本文充分利用极端随机森林和TLD在线学习模型的特性，提出了一种基于改进的随机森林TLD目标跟踪方法。

2基于改进的随机森林TLD方法

2.1改进的随机森林方法

本文将深入讨论和研究阈值参数选择的问题。引入样本混合比α，用于度量样本集合各种类别样本比例关系，α为叶节点上非数量最多的样本相对于数量最多的样本的比例。

假设在某一叶节点上存储的样本为K种，其中数量最多的类样本标号为Lm，占全部样本数量比例为pm，其余样本所占比例为pi(i≠m,i=1,2,…K)，Lm样本数量为n，其余类别的样本数目相对Lm的比例为αi，非Lm的样本相对Lm的比例为

(1)

则经实验验证该叶节点的分裂阈值参数为：

(2)

对叶节点分裂阈值参数讨论如下：

分类阈值参数Δ会影响极端随机森林方法的性能，合适的阈值可以保证算法具有高的分类正确率和较少的训练时间。由前所述，分裂阈值的选择与混合比α大小有关，本文中将α按照0,0.1,…1.0取值，对不同的α值下的分类错误率、叶节点数量和训练时间分别进行统计，最终考核各个方面确定阈值参数Δ。

本文采用的实验数据来自于标准目标跟踪视频数据，训练次数设为50次，设置8棵树，每棵树有10个特征，得到的训练图如图2。

所以综合分类错误率、叶节点数量以及训练时间等因素，选择样本混合比为0.2，这使得极端随机森林既具有较高的分类正确率，又保证了叶节点的数量同时训练时间也不长，此时分裂参数Δ=0.31。

(a) 分类错误率图

(b) 产生叶节点数量图

(c) 时间对比图

2.2改进后的TLD跟踪算法描述

(1)手动获得目标区域，在第一帧确定目标边界框，每个子窗口从9×9像素大小到整幅图像大小随机产生，将图像块作为样本处理，记录图像块边界框，用于后面的评估；

(3)进入级联分类器的第一级分类器方差分类器，检测滑动窗口像素点的灰度值方差，滤掉一部分背景图像；

(4)通过方差分类器的图像块进入随机森林分类器，在这部分按照2.1节改进的随机森林设置分类阈值训练决策树，基于各个决策树是相互独立的，计算各决策树的后验概率，决定是否接受滑动窗口，这个过程是离线进行的；

(5)采用最近邻分类器更新样本，将分类器与在线学习模块growingevent和pruningevent相结合，使得极端随机森林变成增量式，设定滑动窗口与在线模型的相关相似度阈值，growingevent将自身置信度高的样本给特征空间进行增量学习分类，同时pruningevent根据自身样本的置信度判断特征空间中的不正确样本，将其从特征空间中去掉，更新检测器；

(6)在更新检测的同时也更新跟踪器，在目标框内均匀采样，采用LK光流法跟踪，并进行扩展误差检测，计算图像块的位置信息，估计目标框在当前帧中的位置，信息像素点也用于在线学习模块的样本信息，综合跟踪模块、检测模块、在线学习模块完成一个跟踪过程。

3实验结果及分析

实验用计算机为CPUE5500，2.80GHz，2GB内存，在MatlabR2009a环境下运行。实验数据来自标准目标跟踪测试数据集，分别为Car、Face、Moto。

为了验证算法的有效性，本文将改进方法和随机森林算法进行对比，分别比较两个算法的分类正确率、叶节点数量和训练时间。两种算法分别在数据集上运行50次，使用8棵树，分裂阈值参数为0.31。得到的统计结果见表1。

表1　改进算法与随机森林算法的比较结果

从表1中可以看出改进后的方法分类正确率与随机森林的相差不大，略优于随机森林；产生的叶节点数量多于随机森林，训练速度明显快于随机森林。通过以上实验可以看出，改进算法在按照样本混合比选定正确分裂阈值的情况下，结果优于随机森林，所以本文将极端随机森林加入TLD算法中，用于提高算法的速度以及精度。

Car、Face、Moto三个视频集包含了目标跟踪过程中的尺度变化、快速频繁转动、快速运动、目标相似、光照变化等情况，针对以上三个视频集，将本文方法与TLD方法进行对比，处理结果如图3-图5。

从图3-图5中可以看出视频初始帧的跟踪两种算法都较为准确，但到后续帧中，由于目标的快速转动、遮挡、尺度变化等因素的干扰，原始方法出现了分类不精确的现象，跟踪边框出现了一定程度的偏移，而本文方法进行了较为准确的跟踪。本文采用文献[10]的评价方法，如果目标物体有25 %以上没能被跟踪，那么这帧数据被认为跟踪错误，统计结果见表2。从表中可以看出，本文方法的跟踪效果更准确，对于目标多种情况变化适应性更强，稳定性更好。

第6帧　　　　　　第236帧

第253 帧　　　　　 第669帧

第13帧　　　　　第43帧

第284　　　　　　第331帧

第12帧　　　　　　第26帧

第57帧　　　　　　　第92帧

数据集改进方法(正确帧数/总帧数)TLD算法(正确帧数/总帧数)Carsequence504/600489/600Facesequence412/550389/550Motosequence92/10086/100

4结论

本文在随机森林中引入样本混合比α，选定分裂阈值，采用极端随机森林进行分类，加入在线

学习模型，构成增量式极端随机森林，用于TLD算法中，提出基于改进的随机森林TLD目标跟踪方法。实验首先验证了本文算法时间开销低、分类准确性高，其次进行目标跟踪实验，结果表明，本文方法对于复杂情况下的目标跟踪准确，稳定性强。但本文方法只进行了单目跟踪，还要进一步处理，实现多目标跟踪。

参考文献：

[1] MARCO P,RADU T,TINNE T，et al.An Elastic Deformation Field Model for Object Detection and Tracking[J]. International Journal of Computer Vision, 2015, 111(2):137-152.

[2] REHMAN A,KIHARA K,MATSUMOTO A,et al. Attentive tracking of moving objects in real 3D space[J]. Vision Research,2015,109(part A):1-10.

[3] PERNICI F ,DEL BIMBO.A.Object Tracking by Oversampling Local Features[J]. Pattern Analysis and Machine Intelligence.2014,36(12):2538-2551.

[4] 彭爽, 彭晓明. 基于高效多示例学习的目标跟踪[J]. 计算机应用, 2015,35( 2) : 466 -469, 475.

[5] 李想，汪荣贵，杨娟. 基于示例选择的目标跟踪改进算法[J]. 计算机工程,2015,41(1):150-157.

[6] KALAL Z, MATAS J, MIKOLAJCZYK K. Online learning of robust object detectors during unstable tracking [C]∥ Computer Vision Workshops (ICCV Workshops), 2009:1417-1424.

[7] KALAL Z, MIKOLAJCZYK K, MATAS J. Face-TLD: Tracking -Learning-Detection Applied to Faces[C]∥ International Conference on Image Processing, 2010:3789-3792.

[8] KALAL Z, MIKOLAJCZYK K, MATAS J. Forward-Backward Error: Automatic Detection of Tracking Failures [C]∥ International Conference on Pattern Recognition (ICPR 2010), 2010: 23-26.

[9] KALAL Z, MIKOLAJCZYK K, MATAS J. P-N Learning: Bootstrapping Binary Classifiers by Structural Constraints [C]. Computer Vision and Pattern Recognition (CVPR), 2010:49-56.

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

(责任编辑王楠楠)

TLD Target Tracking Method based on Improved Random Forest

ZHANG Dan1, CHEN Xing-wen1, ZHAO Shu-ying2

(1.School of Engineering Education, Dalian Minzu University, Dalian Liaoning 116605, China;2.School of Information Science and Engineering, Northeastern University,Shenyang Liaoning 110819, China)

Abstract:The fixed threshold value of the random forest classifier can not be readily adapted to the target feature of TLD (Tracking Learning Detecting) algorithm, which affects classification accuracy and time overhead issues. Aiming at this problem, an idea of extreme random forest was introduced, and a TLD target tracking method based on improved random forest is proposed. This method used Gini coefficient to measure the degree of confusion of sample sets, by deciding the Gini coefficient whether exceeded a given threshold to judge when a leaf node changed into the decision node to split. Combining P-N learning framework and online model, samples were trained and updated. Finally, the target tracking was completed based on improved TLD algorithm. The proposed method was used in many video sets for target tracking to verify its effectiveness and stability.

Key words:target tracking; random forests; TLD; split threshold; online learning

收稿日期：2015-09-21；最后修回日期：2016-12-21

基金项目：中央高校基本科研业务费专项资金资助项目(DC201502060303，DC201501075)。

作者简介：张丹(1987-)，女，辽宁葫芦岛人，工程师，主要从事图像处理，机器视觉研究。通讯作者：陈兴文(1969-)，男，辽宁锦州人，教授，主要从事图像处理、模式识别研究，E-mail: mycxw@dlnu.edu.cn.

文章编号：2096-1383(2016)03-0255-05

中图分类号：TP391

文献标志码：A