劉 哲,陳 懇,鄭紫微

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

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

劉 哲,陳 懇,鄭紫微

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

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

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

1 概述

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

綜上所述,基于MILBoost在線學(xué)習(xí)框架,本文采用HOG[4,9,12]特征空間獲取HOG-LBP特征向量,構(gòu)建一種隨機蕨[2-4]檢測的目標(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 隨機蕨檢測

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

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

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

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

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

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

圖1 單個隨機蕨模型

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

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

3.1 HOG-LBP特征

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

圖2 HOG-LBP特征提取

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

本文實驗采用Macbook Pro平臺運行,處理器為2.3 GHz Intel Core i7,內(nèi)存為8 GB,C++編譯環(huán)境為LLVM 5.0,Matlab為2012b。算法在多個視頻序列進(jìn)行實驗,包括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++)。比較算法實現(xiàn)參數(shù)采用算法標(biāo)注文獻(xiàn)提供的參數(shù)。隨機蕨池蕨的個數(shù)M為200,最優(yōu)蕨個數(shù)K為50。本文算法正學(xué)習(xí)樣本采用半徑為5,樣本個數(shù)為45,負(fù)樣本半徑為50,樣本個數(shù)為65,這里半徑單位為像素,不包含圖像塊半徑。在搜索階段,隨機采樣位置為15個,每個位置取5個不同尺度的樣本,中間尺度與初始化樣本塊大小相同。單個蕨的特征數(shù)S為8。

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

圖4 本文算法跟蹤效果

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

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

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

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

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

5 結(jié)束語

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

[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].計算機工程,2013,39(3): 213-217,222.

[9] 劉華軍,王玉坤.基于HOG及在線多實例學(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

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

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

2014-01-20

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

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