基于HOG与多实例在线学习的目标跟踪算法

刘 哲,陈 恳,郑紫微

(宁波大学信息科学与工程学院,浙江宁波315211)

基于HOG与多实例在线学习的目标跟踪算法

刘 哲,陈 恳,郑紫微

(宁波大学信息科学与工程学院,浙江宁波315211)

为实现在局部遮挡、光线变化等复杂背景下的目标跟踪,提出一种基于梯度方向直方图(HOG)与多实例在线学习的目标跟踪算法。利用已标定目标图像的HOG特征空间,结合局部二值模式(LBP)描述方法获取特征向量,构建初始随机蕨检测算子,采用随机多尺度采样方法跟踪每一帧的目标位置和尺寸,并基于多实例在线学习框架,通过检测到的目标样本以及附近的背景样本在线更新检测算子。将该算法与 OnlineBoostingTracker, MILTracker等在线学习目标跟踪算法在多个标准视频序列中进行比较,实验结果表明,该算法在局部遮挡和光照变化的环境下具有较好的跟踪稳定性,但在抗目标旋转方面有待优化。

随机蕨;梯度方向直方图;局部二值模式;多实例学习;在线学习;目标检测;目标跟踪

1 概述

基于检测的目标跟踪算法侧重于目标表面模型的建立,利用表观模型检测目标位置、尺度以及旋转等。通常目标跟踪初期没有很多训练样本,只有在跟踪期间,才会不断产生新的目标样本。针对这些情况,研究者提出了一些在线学习目标跟踪算法。文献[1]提出在线随机森林分类模型,文献[2-3]通过实验展示了随机蕨丛与随机森林在分类性能上效果相近,且由于随机森林在节点分支计算上时间消耗较高,而随机蕨采用LBP[4]特征,计算速度相对理想,符合目标跟踪需求。文献[5-7]利用Adaboost学习方法构建了一种在线学习方法,利用新的样本以批处理的方式更新分类器特征库,并结合半监督学习与Adaboost提出了SemiBoost目标跟踪学习框架,但这些方法在目标模型更新时,对新样本标定的容错能力有限,主要是因为在这些方法中,Adaboost学习框架所使用的样本属于单实例,算法很难保证样本标定的正确导致容错能力受限。为解决这种问题,研究者试图通过结合online boosting学习框架以及多实例采样学习方法[8-9]处理该问题,文献[10-11]提出MILBoost在线学习框架构建了跟踪算法,但只利用了目标图像块的Haar-Like[8-9]特征构建模型,对目标特征描述不够充分,对于复杂背景的目标跟踪不稳定。

综上所述,基于MILBoost在线学习框架,本文采用HOG[4,9,12]特征空间获取HOG-LBP特征向量,构建一种随机蕨[2-4]检测的目标跟踪算法,介绍了算法中HOG-LBP特征构建、目标模型更新以及搜索匹配策略,并将算法与 OnlineBoostingTracker[5],Semi Tracker[6],BeyondSemiTracker[7],MILTracker[10-11], Compressive Tracker[13]等目标跟踪算法进行分析与比较。

2 随机蕨检测

随机蕨主要是利用朴素贝叶斯概率模型评估特征点的类别。类别集用ci,i=1,2,…,H表示(跟踪任务中H为2,目标为一类,非目标为一类),fj,j=1,2,…,N为在图像中提取的需要分类的二进制特征集。分类器的作用是求取图像块最大条件概率估计的类别:

其中,c是表示类别的随机变量,通过朴素贝叶斯公式得到:

假设存在先验均匀分布P(c),由于分母与类别无关,问题可以简化为:

通常随机蕨特征主要是指由图像像素大小比较获得的LBP特征,这种特征易受噪声影响。因此,本文提出基于样本的HOG特征空间的LBP特征,即HOG-LBP特征。

其中,Ω代表图像块的HOG特征空间;u,v表示图像平面坐标;o表示梯度方向角度。由于建立所有二进制特征的联合概率分布工作量巨大,因此需要根据特征独立性将所有特征划分为K组,每组大小为S=N/K,每组LBP特征构建一个蕨。随机蕨的联合概率分布可用式(5)表示:

其中,Fk={fδ(k,1),fδ(k,2),…,fδ(k,S)},k=1,2,…,K表示第k个蕨;δ(k,j)为随机排序函数。图1展示了单个蕨的构建,蕨的每层使用一个特征进行分支,到叶子节点可以得到一个条件概率向量P(Fk|c=ci)。由于目标模型采用MILBoosting在线学习框架,目标模型需要构建随机蕨池,从中提取K个用于目标检测,由此可知,K要远小于随机蕨池中蕨的数目M。

图1 单个随机蕨模型

3 基于HOG和多实例在线学习的目标跟踪

本节介绍了算法中HOG-LBP特征向量构建、目标模型更新策略以及目标搜索匹配策略。

3.1 HOG-LBP特征

由于关键特征点[2-4]提取耗时,本文算法采用一种HOG-LBP特征,即通过目标图像块获取HOG特征空间Ω(u,v,o),u,v代表图像平面坐标,o代表方向坐标,在此三维空间随机选取2个特征点比较它们的大小,从而获取目标的LBP特征向量。为了保证特征的局部特性,在选取采样点时,先随机选取一个小的图像块,如图2虚框所示,然后在这个图像块选取采样点经过 HOG计算和比较后构成单个蕨的HOG-LBP。

图2 HOG-LBP特征提取

图2展示了目标图像块一个比特特征提取的过程,首先根据灰度图像获取HOG特征空间,然后随机取2个三维坐标点(u,v,o)和(u′,v′,o′)比较它们HOG特征值大小,从而获取一个比特特征。本文算法将梯度方向个数分为8个。

3.2 目标模型更新策略

在目标跟踪前,基于初始标定图像块,采用多实例采样方法选取正样本包和负样本包,每个样本实例经过加噪和形变扩展为20个正样本实例组成正样本包,但初始标定图像块扩展为100个正样本实例,然后用正负样本包初始化随机蕨池。在目标跟踪过程中,不断选取新的正样本和负样本,利用这些在线样本更新单个蕨的概率模型。本文算法用目标模型更新因子λ(0≤λ≤1)即式(7)来控制模型更新速率,式(6)描述了单个随机蕨概率模型的更新。

其中,p(t+1)(Fk|c)表示类别c条件下,第k蕨的特征值为i的概率;表示在t帧前类别为c的样本中,第k蕨的特征为i的数目;表示关于i的总和;表示第t帧、第k蕨类别c的新样本包中特征值为i的实例数目。式(7)中类别关于样本包的概率可通过式(8)和式(9)计算得到:

每个蕨更新后,采用批处理的方法提取K个最优蕨。以批处理方式获取最优蕨如式(10)所示:

本文算法主要分2个类别:目标与非目标,所以,h用计算,α表示随机蕨权重,利用log函数似然最大化从候选池中依次选取K个最优蕨。完成特征点概率模型选择后,将式(11)作为下一帧的检测算子:

其中,K表示构建检测算子的最优蕨数目。

图3展示了多实例在线学习过程,第t帧完成目标检测后首先提取新的正负样本,然后利用新的样本对随机蕨池一一更新,最后从这些随机蕨中以Adaboost方法提取最优蕨来构建第t+1帧的检测算子。

图3 目标跟踪中的多实例在线学习

3.3 目标搜索匹配策略

利用目标模型在指定区域对目标进行跟踪是目标跟踪算法中关键的环节。本文根据前一帧目标位置基于随机多尺度采样方法提取若干样本。在搜索窗内,首先随机选取多个位置,然后以每个位置为采样点,以不同尺度提取图像块样本用于目标检测,在提取Hog-LBP特征之前,将所有检测样本变换为与初始帧图像块相同大小。最后算法利用Sigmoid函数模型计算每个样本的H(x)并映射到0～1内,利用此值近似描述单样本分类的条件概率值:

比较样本包中每个样本的概率值以此获取新的目标图像块:

其中,X表示目标跟踪过程中采集的测试样本包;i表示具有最大概率值的检测样本索引。

4 实验结果与分析

本文实验采用Macbook Pro平台运行,处理器为2.3 GHz Intel Core i7,内存为8 GB,C++编译环境为LLVM 5.0,Matlab为2012b。算法在多个视频序列进行实验,包括Car4,David,Lemming,Trellis,这些视频序列包含多种变化因素,如表1所示。

表1 序列属性说明

同时也在相同视频下实验比较不同跟踪算法的性能,包括OnlineBoostingTracker[5](OAB,C++,这里采用OAB(5)比较),SemiTracker[6](SBT,C++), BeyondSemi Tracker[7](BSBT,C++),MILTracker[10-11](MIL,C++),Compressive Tracker[13](CT,Matlab和 C++)。比较算法实现参数采用算法标注文献提供的参数。随机蕨池蕨的个数M为200,最优蕨个数K为50。本文算法正学习样本采用半径为5,样本个数为45,负样本半径为50,样本个数为65,这里半径单位为像素,不包含图像块半径。在搜索阶段,随机采样位置为15个,每个位置取5个不同尺度的样本,中间尺度与初始化样本块大小相同。单个蕨的特征数S为8。

表1说明了实验所采用的视频序列的各种干扰特征,其中包括光照变化、局部遮挡、背景与目标相近、目标旋转以及尺度变换。图4展示了该跟踪算法对4个序列的跟踪效果。

图4 本文算法跟踪效果

在图4中,第一行表示Car4;第二行表示David;第三行表示Lemming;第四行表示Trellis,并且白线框表示本文算法跟踪效果,黑线框表示标定线框。4个序列都有光照变化干扰和局部遮挡,本文算法在这些序列表现出其优势,这主要是由于目标跟踪过程中采用HOGLBP特征,弱化了光照变化以及其局部遮挡对检测的影响;Lemming与Trellis背景相对复杂,并且目标旋转较多,本文算法跟踪时部分帧发生较大偏移,这是由于目标移动含有较大旋转以及背景相近,但仍表现较好;最后,由于目标采用多尺度随机采样方式,具备一定尺度跟踪特征,可由Trellis跟踪效果说明。

为充分分析算法性能,图5展示了本文算法与其他算法对不同序列的目标跟踪偏移距离精度分析。横坐标表示跟踪中心位置偏移阈值,单位为像素,纵坐标表示跟踪精度(这里只评估像素距离50以内的,50以外算作未跟踪到,曲线表示检测到的目标偏移距离小于不同偏移阈值占总帧数的比例)。可见,本文算法在Car4,David以及Lemming中表现优异。由于Trellis序列背景相对昏暗,并且目标带有较多旋转,性能相对较低。

图5 目标跟踪精度评估

算法采用文献[14]提出的成功率评估方法,如图6所示,横坐标表示目标矩形与理想标定矩形的交叉比阈值(rt表示跟踪矩形框,ra表示理想矩形框),纵坐标表示跟踪成功率,曲线表示所有检测目标的交叉大于不同阈值占总帧数的比率,实线代表本文算法。不同算法曲线与纵坐标的交叉数值展示了目标在整个序列跟踪到的比率,曲线的面积积分说明了算法跟踪成功的整体性能。可见,本文算法在 Car4,Lemming中性能较好,在 David中,可以保证所有帧基本能跟踪目标,但跟踪精度不高,在Trellis中,目标跟踪有部分图像帧失踪,整体性能略差。

图6 目标跟踪成功率

5 结束语

本文提出一种基于HOG-LBP的目标跟踪算法,使用随机蕨分类模型并结合多实例在线学习框架,更新检测算法,实现目标跟踪。实验通过多个序列分析了算法性能,与多个目标跟踪算法进行比较,并采用跟踪偏移精度以及成功率评估方法进行量化分析,从结果可看出,本文算法在抗遮挡以及光照变化上表现较好,同时,算法具备一定尺度跟踪能力,但在抗旋转方面有待优化,今后将对此做深入研究。

[1] Saffari A,Leistner C,Santner J,et al.Online Random Forests[C]//Proceedings of the 12th International Conference on Computer Vision Workshops.Kyoto, Japan:[s.n.],2009:1393-1400.

[2] Ozuysal M,Calonder M,Lepetit V,et al.Fast Keypoint Recognition Using Random Ferns[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010, 32(3):448-461.

[3] Ozuysal M,Fua P,Lepetit V.Fast Keypoint Recognition in Ten Lines of Code[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis,USA:IEEE Press,2007:1-8.

[4] Villamizar M,Moreno-Noguer F,Andrade-Cetto J,et al. Efficient Rotation Invariant Object Detection Using Boosted Random Ferns[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.San Francisco, USA:IEEE Press,2010:1038-1045.

[5] Grabner H,Grabner M,Bischof H.Real-time Tracking via On-line Boosting[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. New York,USA:IEEE Press,2006.

[6] Grabner H,Leistner C,Bischof H.Semi-supervised Online Boosting for Robust Tracking[C]//Proceedings of European Conference on Computer Vision.Marseille, France:[s.n.],2008:234-247.

[7] Stalder S,GrabnerH,vanGoolL.BeyondSemisupervised Tracking:Tracking Should Be as Simple as Detection,But not Simpler than Recognition[C]// Proceedings of International Conference on Computer Vision.Kyoto,Japan:[s.n.],2009:1409-1416.

[8] 苏巧平,刘 原,卜英乔,等.基于稀疏表达的多示例学习目标追踪算法[J].计算机工程,2013,39(3): 213-217,222.

[9] 刘华军,王玉坤.基于HOG及在线多实例学习的目标跟踪算法[J].现代电子技术,2013,36(9):116-120.

[10] Babenko B,Yang M H,Belongie S.Robust Object Tracking with Online Multiple Instance Learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1619-1632.

[11] Babenko B,Yang M H,Belongie S.Visual Tracking with Online Multiple Instance Learning[C]//Proceedings of IEEE ConferenceonComputerVision and Pattern Recognition.Miami,USA:IEEE Press,2009:983-990.

[12] Dalal N,Triggs B.Histograms of Oriented Gradients for Human Detection[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.San Diego, USA:IEEE Press,2005:886-893.

[13] Zhang Kaihua,Zhang Lei,Yang M H.Real-time Compressive Tracking[C]//Proceedings of European Conference on Computer Vision.Florence,Italy:[s.n.],2012.

[14] Wu Y,Lim J,Yang M H.Online Object Tracking:A Benchmark[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Portland, USA:IEEE Press,2013:2411-2418.

编辑 陆燕菲

Object Tracking Algorithm Based on HOG and Multiple-instance Online Learning

LIU Zhe,CHEN Ken,ZHENG Ziwei
(College of Information Science and Engineering,Ningbo University,Ningbo 315211,China)

In order to achieve effectively stabilized target tracking within partial occlusion,illumination changes and complex background environment,this paper presents an object tracking algorithm based on Histogram of Oriented Gradients(HOG)and Multiple-instance Learning(MIL).Using the HOG feature space of the target block and the background in the first frame with Local Binary Pattern(LBP)descriptor to initialize the initial random ferns,it detects the target location and the objective scale of each frame with random multiple-scale sampling and uses the new target samples and the nearby background samples to update the appearance model within multi-instance learning after each detection.Through the experiments,the algorithm with multiple online tracking algorithms such as OnlineBoostingTracker and MILTracker are compared and analyzed in a number of video sequences.The results show that it has a good target tracking stability under the complex environment,especially with partial occlusion and illumination changes,but in the anti-rotation of target,the algorithm has yet to be optimized.

random ferns;Histogram of Oriented Gradient(HOG);Local Binary Pattem(LBP);Multiple-instance Learning(MIL);online learning;object detection;object tracking

1000-3428(2015)01-0158-06

A

TP311

10.3969/j.issn.1000-3428.2015.01.029

国家科技重大专项基金资助项目(2011ZX03002-004-02);教育部高等学校博士学科点专项科研基金资助项目(20113305110002);浙江省重点科技创新团队基金资助项目(2012R10009-04);浙江省杰出青年科学基金资助项目(R1110416)。

刘 哲(1988-),男,硕士研究生,主研方向:计算机视觉,流媒体技术;陈 恳,副教授;郑紫微,教授、博士。

2014-01-20

2014-02-23 E-mail:isadliu229@gmail.com

中文引用格式:刘 哲,陈 恳,郑紫微.基于HOG与多实例在线学习的目标跟踪算法[J].计算机工程,2015,41(1):158-163.

英文引用格式:Liu Zhe,Chen Ken,Zheng Ziwei.Object Tracking Algorithm Based on HOG and Multiple-instance Online Learning[J].Computer Engineering,2015,41(1):158-163.