基于HOG與多實例在線學習的目標跟蹤算法

劉 哲,陳 懇,鄭紫微

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

基于HOG與多實例在線學習的目標跟蹤算法

劉 哲,陳 懇,鄭紫微

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

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

隨機蕨;梯度方向直方圖;局部二值模式;多實例學習;在線學習;目標檢測;目標跟蹤

1 概述

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

綜上所述,基于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表示梯度方向角度。由于建立所有二進制特征的聯(lián)合概率分布工作量巨大,因此需要根據特征獨立性將所有特征劃分為K組,每組大小為S=N/K,每組LBP特征構建一個蕨。隨機蕨的聯(lián)合概率分布可用式(5)表示:

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

圖1 單個隨機蕨模型

3 基于HOG和多實例在線學習的目標跟蹤

本節(jié)介紹了算法中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個最優(yōu)蕨。以批處理方式獲取最優(yōu)蕨如式(10)所示:

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

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

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

圖3 目標跟蹤中的多實例在線學習

3.3 目標搜索匹配策略

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

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

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

4 實驗結果與分析

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

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

圖4 本文算法跟蹤效果

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

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

圖5 目標跟蹤精度評估

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

圖6 目標跟蹤成功率

5 結束語

本文提出一種基于HOG-LBP的目標跟蹤算法,使用隨機蕨分類模型并結合多實例在線學習框架,更新檢測算法,實現(xiàn)目標跟蹤。實驗通過多個序列分析了算法性能,與多個目標跟蹤算法進行比較,并采用跟蹤偏移精度以及成功率評估方法進行量化分析,從結果可看出,本文算法在抗遮擋以及光照變化上表現(xià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] 蘇巧平,劉 原,卜英喬,等.基于稀疏表達的多示例學習目標追蹤算法[J].計算機工程,2013,39(3): 213-217,222.

[9] 劉華軍,王玉坤.基于HOG及在線多實例學習的目標跟蹤算法[J].現(xiàn)代電子技術,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);浙江省重點科技創(chuàng)新團隊基金資助項目(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.