劉 哲,陳 懇,鄭紫微

(寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江寧波315211)

基于HOG與多實(shí)例在線學(xué)習(xí)的目標(biāo)跟蹤算法

劉 哲,陳 懇,鄭紫微

(寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江寧波315211)

為實(shí)現(xiàn)在局部遮擋、光線變化等復(fù)雜背景下的目標(biāo)跟蹤,提出一種基于梯度方向直方圖(HOG)與多實(shí)例在線學(xué)習(xí)的目標(biāo)跟蹤算法。利用已標(biāo)定目標(biāo)圖像的HOG特征空間,結(jié)合局部二值模式(LBP)描述方法獲取特征向量,構(gòu)建初始隨機(jī)蕨檢測(cè)算子,采用隨機(jī)多尺度采樣方法跟蹤每一幀的目標(biāo)位置和尺寸,并基于多實(shí)例在線學(xué)習(xí)框架,通過(guò)檢測(cè)到的目標(biāo)樣本以及附近的背景樣本在線更新檢測(cè)算子。將該算法與 OnlineBoostingTracker, MILTracker等在線學(xué)習(xí)目標(biāo)跟蹤算法在多個(gè)標(biāo)準(zhǔn)視頻序列中進(jìn)行比較,實(shí)驗(yàn)結(jié)果表明,該算法在局部遮擋和光照變化的環(huán)境下具有較好的跟蹤穩(wěn)定性,但在抗目標(biāo)旋轉(zhuǎn)方面有待優(yōu)化。

隨機(jī)蕨;梯度方向直方圖;局部二值模式;多實(shí)例學(xué)習(xí);在線學(xué)習(xí);目標(biāo)檢測(cè);目標(biāo)跟蹤

1 概述

基于檢測(cè)的目標(biāo)跟蹤算法側(cè)重于目標(biāo)表面模型的建立,利用表觀模型檢測(cè)目標(biāo)位置、尺度以及旋轉(zhuǎn)等。通常目標(biāo)跟蹤初期沒(méi)有很多訓(xùn)練樣本,只有在跟蹤期間,才會(huì)不斷產(chǎn)生新的目標(biāo)樣本。針對(duì)這些情況,研究者提出了一些在線學(xué)習(xí)目標(biāo)跟蹤算法。文獻(xiàn)[1]提出在線隨機(jī)森林分類模型,文獻(xiàn)[2-3]通過(guò)實(shí)驗(yàn)展示了隨機(jī)蕨叢與隨機(jī)森林在分類性能上效果相近,且由于隨機(jī)森林在節(jié)點(diǎn)分支計(jì)算上時(shí)間消耗較高,而隨機(jī)蕨采用LBP[4]特征,計(jì)算速度相對(duì)理想,符合目標(biāo)跟蹤需求。文獻(xiàn)[5-7]利用Adaboost學(xué)習(xí)方法構(gòu)建了一種在線學(xué)習(xí)方法,利用新的樣本以批處理的方式更新分類器特征庫(kù),并結(jié)合半監(jiān)督學(xué)習(xí)與Adaboost提出了SemiBoost目標(biāo)跟蹤學(xué)習(xí)框架,但這些方法在目標(biāo)模型更新時(shí),對(duì)新樣本標(biāo)定的容錯(cuò)能力有限,主要是因?yàn)樵谶@些方法中,Adaboost學(xué)習(xí)框架所使用的樣本屬于單實(shí)例,算法很難保證樣本標(biāo)定的正確導(dǎo)致容錯(cuò)能力受限。為解決這種問(wèn)題,研究者試圖通過(guò)結(jié)合online boosting學(xué)習(xí)框架以及多實(shí)例采樣學(xué)習(xí)方法[8-9]處理該問(wèn)題,文獻(xiàn)[10-11]提出MILBoost在線學(xué)習(xí)框架構(gòu)建了跟蹤算法,但只利用了目標(biāo)圖像塊的Haar-Like[8-9]特征構(gòu)建模型,對(duì)目標(biāo)特征描述不夠充分,對(duì)于復(fù)雜背景的目標(biāo)跟蹤不穩(wěn)定。

綜上所述,基于MILBoost在線學(xué)習(xí)框架,本文采用HOG[4,9,12]特征空間獲取HOG-LBP特征向量,構(gòu)建一種隨機(jī)蕨[2-4]檢測(cè)的目標(biāo)跟蹤算法,介紹了算法中HOG-LBP特征構(gòu)建、目標(biāo)模型更新以及搜索匹配策略,并將算法與 OnlineBoostingTracker[5],Semi Tracker[6],BeyondSemiTracker[7],MILTracker[10-11], Compressive Tracker[13]等目標(biāo)跟蹤算法進(jìn)行分析與比較。

2 隨機(jī)蕨檢測(cè)

隨機(jī)蕨主要是利用樸素貝葉斯概率模型評(píng)估特征點(diǎn)的類別。類別集用ci,i=1,2,…,H表示(跟蹤任務(wù)中H為2,目標(biāo)為一類,非目標(biāo)為一類),fj,j=1,2,…,N為在圖像中提取的需要分類的二進(jìn)制特征集。分類器的作用是求取圖像塊最大條件概率估計(jì)的類別:

其中,c是表示類別的隨機(jī)變量,通過(guò)樸素貝葉斯公式得到:

假設(shè)存在先驗(yàn)均勻分布P(c),由于分母與類別無(wú)關(guān),問(wèn)題可以簡(jiǎn)化為:

通常隨機(jī)蕨特征主要是指由圖像像素大小比較獲得的LBP特征,這種特征易受噪聲影響。因此,本文提出基于樣本的HOG特征空間的LBP特征,即HOG-LBP特征。

其中,Ω代表圖像塊的HOG特征空間;u,v表示圖像平面坐標(biāo);o表示梯度方向角度。由于建立所有二進(jìn)制特征的聯(lián)合概率分布工作量巨大,因此需要根據(jù)特征獨(dú)立性將所有特征劃分為K組,每組大小為S=N/K,每組LBP特征構(gòu)建一個(gè)蕨。隨機(jī)蕨的聯(lián)合概率分布可用式(5)表示:

其中,Fk={fδ(k,1),fδ(k,2),…,fδ(k,S)},k=1,2,…,K表示第k個(gè)蕨;δ(k,j)為隨機(jī)排序函數(shù)。圖1展示了單個(gè)蕨的構(gòu)建,蕨的每層使用一個(gè)特征進(jìn)行分支,到葉子節(jié)點(diǎn)可以得到一個(gè)條件概率向量P(Fk|c=ci)。由于目標(biāo)模型采用MILBoosting在線學(xué)習(xí)框架,目標(biāo)模型需要構(gòu)建隨機(jī)蕨池,從中提取K個(gè)用于目標(biāo)檢測(cè),由此可知,K要遠(yuǎn)小于隨機(jī)蕨池中蕨的數(shù)目M。

圖1 單個(gè)隨機(jī)蕨模型

3 基于HOG和多實(shí)例在線學(xué)習(xí)的目標(biāo)跟蹤

本節(jié)介紹了算法中HOG-LBP特征向量構(gòu)建、目標(biāo)模型更新策略以及目標(biāo)搜索匹配策略。

3.1 HOG-LBP特征

由于關(guān)鍵特征點(diǎn)[2-4]提取耗時(shí),本文算法采用一種HOG-LBP特征,即通過(guò)目標(biāo)圖像塊獲取HOG特征空間Ω(u,v,o),u,v代表圖像平面坐標(biāo),o代表方向坐標(biāo),在此三維空間隨機(jī)選取2個(gè)特征點(diǎn)比較它們的大小,從而獲取目標(biāo)的LBP特征向量。為了保證特征的局部特性,在選取采樣點(diǎn)時(shí),先隨機(jī)選取一個(gè)小的圖像塊,如圖2虛框所示,然后在這個(gè)圖像塊選取采樣點(diǎn)經(jīng)過(guò) HOG計(jì)算和比較后構(gòu)成單個(gè)蕨的HOG-LBP。

圖2 HOG-LBP特征提取

圖2展示了目標(biāo)圖像塊一個(gè)比特特征提取的過(guò)程,首先根據(jù)灰度圖像獲取HOG特征空間,然后隨機(jī)取2個(gè)三維坐標(biāo)點(diǎn)(u,v,o)和(u′,v′,o′)比較它們HOG特征值大小,從而獲取一個(gè)比特特征。本文算法將梯度方向個(gè)數(shù)分為8個(gè)。

3.2 目標(biāo)模型更新策略

在目標(biāo)跟蹤前,基于初始標(biāo)定圖像塊,采用多實(shí)例采樣方法選取正樣本包和負(fù)樣本包,每個(gè)樣本實(shí)例經(jīng)過(guò)加噪和形變擴(kuò)展為20個(gè)正樣本實(shí)例組成正樣本包,但初始標(biāo)定圖像塊擴(kuò)展為100個(gè)正樣本實(shí)例,然后用正負(fù)樣本包初始化隨機(jī)蕨池。在目標(biāo)跟蹤過(guò)程中,不斷選取新的正樣本和負(fù)樣本,利用這些在線樣本更新單個(gè)蕨的概率模型。本文算法用目標(biāo)模型更新因子λ(0≤λ≤1)即式(7)來(lái)控制模型更新速率,式(6)描述了單個(gè)隨機(jī)蕨概率模型的更新。

其中,p(t+1)(Fk|c)表示類別c條件下,第k蕨的特征值為i的概率;表示在t幀前類別為c的樣本中,第k蕨的特征為i的數(shù)目;表示關(guān)于i的總和;表示第t幀、第k蕨類別c的新樣本包中特征值為i的實(shí)例數(shù)目。式(7)中類別關(guān)于樣本包的概率可通過(guò)式(8)和式(9)計(jì)算得到:

每個(gè)蕨更新后,采用批處理的方法提取K個(gè)最優(yōu)蕨。以批處理方式獲取最優(yōu)蕨如式(10)所示:

本文算法主要分2個(gè)類別:目標(biāo)與非目標(biāo),所以,h用計(jì)算,α表示隨機(jī)蕨權(quán)重,利用log函數(shù)似然最大化從候選池中依次選取K個(gè)最優(yōu)蕨。完成特征點(diǎn)概率模型選擇后,將式(11)作為下一幀的檢測(cè)算子:

其中,K表示構(gòu)建檢測(cè)算子的最優(yōu)蕨數(shù)目。

圖3展示了多實(shí)例在線學(xué)習(xí)過(guò)程,第t幀完成目標(biāo)檢測(cè)后首先提取新的正負(fù)樣本,然后利用新的樣本對(duì)隨機(jī)蕨池一一更新,最后從這些隨機(jī)蕨中以Adaboost方法提取最優(yōu)蕨來(lái)構(gòu)建第t+1幀的檢測(cè)算子。

圖3 目標(biāo)跟蹤中的多實(shí)例在線學(xué)習(xí)

3.3 目標(biāo)搜索匹配策略

利用目標(biāo)模型在指定區(qū)域?qū)δ繕?biāo)進(jìn)行跟蹤是目標(biāo)跟蹤算法中關(guān)鍵的環(huán)節(jié)。本文根據(jù)前一幀目標(biāo)位置基于隨機(jī)多尺度采樣方法提取若干樣本。在搜索窗內(nèi),首先隨機(jī)選取多個(gè)位置,然后以每個(gè)位置為采樣點(diǎn),以不同尺度提取圖像塊樣本用于目標(biāo)檢測(cè),在提取Hog-LBP特征之前,將所有檢測(cè)樣本變換為與初始幀圖像塊相同大小。最后算法利用Sigmoid函數(shù)模型計(jì)算每個(gè)樣本的H(x)并映射到0～1內(nèi),利用此值近似描述單樣本分類的條件概率值:

比較樣本包中每個(gè)樣本的概率值以此獲取新的目標(biāo)圖像塊:

其中,X表示目標(biāo)跟蹤過(guò)程中采集的測(cè)試樣本包;i表示具有最大概率值的檢測(cè)樣本索引。

4 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)采用Macbook Pro平臺(tái)運(yùn)行,處理器為2.3 GHz Intel Core i7,內(nèi)存為8 GB,C++編譯環(huán)境為L(zhǎng)LVM 5.0,Matlab為2012b。算法在多個(gè)視頻序列進(jìn)行實(shí)驗(yàn),包括Car4,David,Lemming,Trellis,這些視頻序列包含多種變化因素,如表1所示。

表1 序列屬性說(shuō)明

同時(shí)也在相同視頻下實(shí)驗(yàn)比較不同跟蹤算法的性能,包括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++)。比較算法實(shí)現(xiàn)參數(shù)采用算法標(biāo)注文獻(xiàn)提供的參數(shù)。隨機(jī)蕨池蕨的個(gè)數(shù)M為200,最優(yōu)蕨個(gè)數(shù)K為50。本文算法正學(xué)習(xí)樣本采用半徑為5,樣本個(gè)數(shù)為45,負(fù)樣本半徑為50,樣本個(gè)數(shù)為65,這里半徑單位為像素,不包含圖像塊半徑。在搜索階段,隨機(jī)采樣位置為15個(gè),每個(gè)位置取5個(gè)不同尺度的樣本,中間尺度與初始化樣本塊大小相同。單個(gè)蕨的特征數(shù)S為8。

表1說(shuō)明了實(shí)驗(yàn)所采用的視頻序列的各種干擾特征,其中包括光照變化、局部遮擋、背景與目標(biāo)相近、目標(biāo)旋轉(zhuǎn)以及尺度變換。圖4展示了該跟蹤算法對(duì)4個(gè)序列的跟蹤效果。

圖4 本文算法跟蹤效果

在圖4中,第一行表示Car4;第二行表示David;第三行表示Lemming;第四行表示Trellis,并且白線框表示本文算法跟蹤效果,黑線框表示標(biāo)定線框。4個(gè)序列都有光照變化干擾和局部遮擋,本文算法在這些序列表現(xiàn)出其優(yōu)勢(shì),這主要是由于目標(biāo)跟蹤過(guò)程中采用HOGLBP特征,弱化了光照變化以及其局部遮擋對(duì)檢測(cè)的影響;Lemming與Trellis背景相對(duì)復(fù)雜,并且目標(biāo)旋轉(zhuǎn)較多,本文算法跟蹤時(shí)部分幀發(fā)生較大偏移,這是由于目標(biāo)移動(dòng)含有較大旋轉(zhuǎn)以及背景相近,但仍表現(xiàn)較好;最后,由于目標(biāo)采用多尺度隨機(jī)采樣方式,具備一定尺度跟蹤特征,可由Trellis跟蹤效果說(shuō)明。

為充分分析算法性能,圖5展示了本文算法與其他算法對(duì)不同序列的目標(biāo)跟蹤偏移距離精度分析。橫坐標(biāo)表示跟蹤中心位置偏移閾值,單位為像素,縱坐標(biāo)表示跟蹤精度(這里只評(píng)估像素距離50以內(nèi)的,50以外算作未跟蹤到,曲線表示檢測(cè)到的目標(biāo)偏移距離小于不同偏移閾值占總幀數(shù)的比例)?？梢?jiàn),本文算法在Car4,David以及Lemming中表現(xiàn)優(yōu)異。由于Trellis序列背景相對(duì)昏暗,并且目標(biāo)帶有較多旋轉(zhuǎn),性能相對(duì)較低。

圖5 目標(biāo)跟蹤精度評(píng)估

算法采用文獻(xiàn)[14]提出的成功率評(píng)估方法,如圖6所示,橫坐標(biāo)表示目標(biāo)矩形與理想標(biāo)定矩形的交叉比閾值(rt表示跟蹤矩形框,ra表示理想矩形框),縱坐標(biāo)表示跟蹤成功率,曲線表示所有檢測(cè)目標(biāo)的交叉大于不同閾值占總幀數(shù)的比率,實(shí)線代表本文算法。不同算法曲線與縱坐標(biāo)的交叉數(shù)值展示了目標(biāo)在整個(gè)序列跟蹤到的比率,曲線的面積積分說(shuō)明了算法跟蹤成功的整體性能?？梢?jiàn),本文算法在 Car4,Lemming中性能較好,在 David中,可以保證所有幀基本能跟蹤目標(biāo),但跟蹤精度不高,在Trellis中,目標(biāo)跟蹤有部分圖像幀失蹤,整體性能略差。

圖6 目標(biāo)跟蹤成功率

5 結(jié)束語(yǔ)

本文提出一種基于HOG-LBP的目標(biāo)跟蹤算法,使用隨機(jī)蕨分類模型并結(jié)合多實(shí)例在線學(xué)習(xí)框架,更新檢測(cè)算法,實(shí)現(xiàn)目標(biāo)跟蹤。實(shí)驗(yàn)通過(guò)多個(gè)序列分析了算法性能,與多個(gè)目標(biāo)跟蹤算法進(jìn)行比較,并采用跟蹤偏移精度以及成功率評(píng)估方法進(jìn)行量化分析,從結(jié)果可看出,本文算法在抗遮擋以及光照變化上表現(xiàn)較好,同時(shí),算法具備一定尺度跟蹤能力,但在抗旋轉(zhuǎn)方面有待優(yōu)化,今后將對(duì)此做深入研究。

[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] 蘇巧平,劉 原,卜英喬,等.基于稀疏表達(dá)的多示例學(xué)習(xí)目標(biāo)追蹤算法[J].計(jì)算機(jī)工程,2013,39(3): 213-217,222.

[9] 劉華軍,王玉坤.基于HOG及在線多實(shí)例學(xué)習(xí)的目標(biāo)跟蹤算法[J].現(xiàn)代電子技術(shù),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

國(guó)家科技重大專項(xiàng)基金資助項(xiàng)目(2011ZX03002-004-02);教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20113305110002);浙江省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)基金資助項(xiàng)目(2012R10009-04);浙江省杰出青年科學(xué)基金資助項(xiàng)目(R1110416)。

劉 哲(1988-),男,碩士研究生,主研方向:計(jì)算機(jī)視覺(jué),流媒體技術(shù);陳 懇,副教授;鄭紫微,教授、博士。

2014-01-20

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

中文引用格式:劉 哲,陳 懇,鄭紫微.基于HOG與多實(shí)例在線學(xué)習(xí)的目標(biāo)跟蹤算法[J].計(jì)算機(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.