李 婷，趙文杰，楊 帥

?

基于多區(qū)域的隨機(jī)蕨在線目標(biāo)跟蹤算法

李 婷，趙文杰，楊 帥

（空軍航空大學(xué)，吉林 長(zhǎng)春 130000）

原始的隨機(jī)森林跟蹤算法，是以像素點(diǎn)的灰度值作為檢測(cè)特征，在目標(biāo)發(fā)生遮擋和旋轉(zhuǎn)時(shí)，容易產(chǎn)生跟蹤漂移，為此本文提出了一種基于多區(qū)域融合的隨機(jī)蕨在線目標(biāo)跟蹤算法。首先將目標(biāo)候選區(qū)域劃分為多個(gè)子區(qū)域，然后采用基于積分圖的隨機(jī)蕨分類器對(duì)每個(gè)子區(qū)域的候選圖像塊進(jìn)行分類，在跟蹤過(guò)程中自適應(yīng)地融合子區(qū)域分類結(jié)果以剔除被遮擋子區(qū)域?qū)δ繕?biāo)跟蹤結(jié)果的影響，同時(shí)更新隨機(jī)蕨特征和子區(qū)域圖像塊的選擇。結(jié)合對(duì)TLD算法部分模塊的改進(jìn)，通過(guò)對(duì)不同視頻序列進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果顯示本文算法在跟蹤大小320pixel×240pixel的視頻序列時(shí)，跟蹤速度達(dá)到20～30frame/s左右，目標(biāo)中心位置誤差在30pixels時(shí)，算法準(zhǔn)確率可達(dá)到80%以上。

目標(biāo)跟蹤，隨機(jī)蕨算法，多區(qū)域融合，目標(biāo)在線模型

0 引言

視頻目標(biāo)跟蹤是計(jì)算機(jī)視覺(jué)領(lǐng)域中一個(gè)重要的研究方向。近20年來(lái)，關(guān)于視頻目標(biāo)跟蹤算法的研究得到了飛速的發(fā)展。視頻目標(biāo)跟蹤算法從早期的離線跟蹤[1-3]發(fā)展到在線跟蹤[4-10]。從對(duì)單目標(biāo)的跟蹤[1-6]發(fā)展到對(duì)多目標(biāo)的跟蹤[11-14]。研究者們一直在努力尋找一種實(shí)時(shí)性高魯棒性強(qiáng)的跟蹤算法，Collin[4]首次提出將跟蹤視為二分類問(wèn)題，強(qiáng)調(diào)了背景對(duì)目標(biāo)跟蹤的作用；隨后Grabner[5]提出了在線Boosting跟蹤算法，實(shí)現(xiàn)了對(duì)目標(biāo)模型的在線更新，可是如果模板存在誤差，就非常容易導(dǎo)致跟蹤漂移。2009年，Saffari[6]首先將隨機(jī)森林用于在線學(xué)習(xí)領(lǐng)域，提高了算法的運(yùn)算效率和魯棒性。2010年Kalal等[7]將在線隨機(jī)森林檢測(cè)與光流跟蹤相結(jié)合提出了目標(biāo)長(zhǎng)時(shí)跟蹤的TLD算法。之后隨機(jī)森林算法在目標(biāo)跟蹤領(lǐng)域得到了廣泛的應(yīng)用。

隨機(jī)森林算法是Leo Breiman于2001年提出的，該算法將特征識(shí)別問(wèn)題轉(zhuǎn)化為分類問(wèn)題，采用二值決策樹(shù)作為分類器，利用樸素貝葉斯算法輔助決策，在保證算法準(zhǔn)確性的同時(shí)，提高了算法的實(shí)時(shí)性[15]。盡管傳統(tǒng)的隨機(jī)森林分類器具有計(jì)算速度快，能夠到達(dá)實(shí)時(shí)性的要求，但是還是存在兩個(gè)缺點(diǎn)：一是基于某兩點(diǎn)的灰度值比較構(gòu)造二值判斷函數(shù)，忽略了像素點(diǎn)的位置信息。因?yàn)橄袼攸c(diǎn)位置一旦確定，就不發(fā)生變化；二是并未考慮像素點(diǎn)周圍的圖像塊信息，這樣的構(gòu)造方法無(wú)法很好地描述目標(biāo)的外觀模型，特別是當(dāng)目標(biāo)發(fā)生遮擋、形變時(shí)，會(huì)產(chǎn)生跟蹤漂移現(xiàn)象。針對(duì)上述問(wèn)題，文獻(xiàn)[16]提出了基于積分圖的隨機(jī)蕨特征點(diǎn)識(shí)別算法，通過(guò)獲取特征點(diǎn)周圍圖像塊的積分圖來(lái)豐富特征點(diǎn)的位置信息及其周圍圖像信息，提高了算法的特征識(shí)別率。但是該算法在跟蹤存在遮擋和形變較大的目標(biāo)時(shí)，跟蹤效果有所下降。

本文在文獻(xiàn)[16]的基礎(chǔ)上提出了基于多區(qū)域融合的隨機(jī)蕨跟蹤算法，在跟蹤初始階段對(duì)目標(biāo)區(qū)域進(jìn)行分塊，分區(qū)域采用二值隨機(jī)蕨算法對(duì)目標(biāo)進(jìn)行檢測(cè)，自適應(yīng)地融合每個(gè)區(qū)域的檢測(cè)結(jié)果，進(jìn)而確定目標(biāo)位置并更新外觀特征。同時(shí)結(jié)合改進(jìn)后的TLD算法提高算法跟蹤遮擋目標(biāo)的魯棒性和實(shí)時(shí)性。

1 基于積分圖的隨機(jī)蕨

隨機(jī)蕨算法是隨機(jī)樹(shù)算法的改進(jìn)，通過(guò)隨機(jī)化的方式在特征點(diǎn)的鄰域圖像塊中獲得二值特征集合，使用非層次化的蕨結(jié)構(gòu)代替基于樹(shù)的層次化結(jié)構(gòu)，利用樸素貝葉斯模型代替決策樹(shù)模型來(lái)構(gòu)建分類器，以此獲得更好的結(jié)果[9]。本文算法將特征點(diǎn)的鄰域圖塊中的兩個(gè)像素灰度值的比較，用兩個(gè)子窗口的積分圖的比較來(lái)代替。

1.1 隨機(jī)蕨的構(gòu)造

F＝{(k,1),(k,2),…,(k,S)},＝1,…,(1)

1.2 基于積分圖的二值判別函數(shù)

圖1 本文算法的二值特征函數(shù)示意圖

此時(shí)，定義每對(duì)圖像塊的二值描述為：

對(duì)發(fā)文機(jī)構(gòu)進(jìn)行統(tǒng)計(jì)分析，可以得到某一領(lǐng)域的主要研究機(jī)構(gòu)及機(jī)構(gòu)之間的合作關(guān)系。網(wǎng)絡(luò)信息行為領(lǐng)域發(fā)文機(jī)構(gòu)的合作網(wǎng)絡(luò)如圖3所示。圖中節(jié)點(diǎn)的大小代表機(jī)構(gòu)發(fā)文量的多少，節(jié)點(diǎn)之間的連線代表機(jī)構(gòu)之間的合作關(guān)系。從圖3可以看出發(fā)文量最多的機(jī)構(gòu)是武漢大學(xué)（8篇），其次為安徽大學(xué)（5篇）、北京理工大學(xué)（2篇）、武漢科技大學(xué)（2篇）、中山大學(xué)（2篇），這4個(gè)機(jī)構(gòu)發(fā)文量≥2篇，只有武漢大學(xué)、安徽大學(xué)等少量機(jī)構(gòu)之間存在合作，機(jī)構(gòu)之間聯(lián)系比較分散，缺乏合作交流?？傮w來(lái)說(shuō)，研究機(jī)構(gòu)的科研力量薄弱，學(xué)術(shù)團(tuán)體間合作不多且較為分散，缺乏有代表性的科研機(jī)構(gòu)。

2 子區(qū)域的劃分與目標(biāo)檢測(cè)

2.1 子區(qū)域的劃分

為了減少遮擋對(duì)目標(biāo)特征更新的影響，本文在算法初始化時(shí)對(duì)目標(biāo)進(jìn)行區(qū)域的劃分。區(qū)域的數(shù)量是影響分類結(jié)果的關(guān)鍵因素，子區(qū)域數(shù)量過(guò)多，會(huì)增加計(jì)算量，影響算法的實(shí)時(shí)性，數(shù)量過(guò)少，則達(dá)不到分類效果，本文在充分考慮各方面影響因素的基礎(chǔ)上，將目標(biāo)分為4個(gè)子區(qū)域，即橫向和縱向分別平均劃分為兩部分。見(jiàn)圖2。

2.2 子區(qū)域的目標(biāo)檢測(cè)

對(duì)每個(gè)子區(qū)域采用基于積分圖的隨機(jī)蕨分類器進(jìn)行目標(biāo)的檢測(cè)，并記下每個(gè)圖像塊的綜合信息P＝(c,d)，d表示圖像塊所在子區(qū)域的標(biāo)號(hào)。當(dāng)圖像塊被判定為正樣本，c＝1；當(dāng)圖像塊被判定為負(fù)樣本時(shí)，c＝0。利用下式計(jì)算出每個(gè)子區(qū)域正樣本的比例：

2.3 子區(qū)域檢測(cè)結(jié)果融合

在多區(qū)域的檢測(cè)結(jié)果融合上，算法通過(guò)兩個(gè)步驟實(shí)現(xiàn)，一是區(qū)域內(nèi)圖像塊的選擇，二是區(qū)域間檢測(cè)結(jié)果的融合。第一步選用歐式距離作為判斷準(zhǔn)則對(duì)子區(qū)域內(nèi)的正樣本圖像塊進(jìn)行選擇，得到每個(gè)子區(qū)域內(nèi)最佳的跟蹤圖像塊。歐氏距離匹配過(guò)程：首先計(jì)算樣本圖像塊與目標(biāo)模板圖像塊之間的歐式距離，歐式距離的計(jì)算可以通過(guò)運(yùn)算式(6)實(shí)現(xiàn)；然后取歐式距離最小的樣本作為當(dāng)前幀的目標(biāo)框。這樣就可以初步篩選出每個(gè)區(qū)域的最佳跟蹤結(jié)果：

()＝sqrt[(x－0)2＋(y－0)2] (6)

3 基于TLD框架的在線跟蹤

TLD算法是Kalal等在2010年提出的融合跟蹤-學(xué)習(xí)-檢測(cè)3個(gè)模塊的長(zhǎng)時(shí)跟蹤算法框架，該算法在應(yīng)對(duì)目標(biāo)形變和防止誤差累積之間找到了折衷的辦法，并提供了跟蹤丟失的判斷依據(jù)和重新檢測(cè)的可能性，具有較高的實(shí)用價(jià)值。因此本文選擇TLD算法作為跟蹤框架，跟蹤模塊仍采用基于前后向錯(cuò)誤檢測(cè)的光流法，檢測(cè)模塊則選擇本文的算法作為分類器，學(xué)習(xí)模塊選用檢測(cè)結(jié)果優(yōu)先策略，利用檢測(cè)結(jié)果去更新跟蹤結(jié)果，進(jìn)一步提高算法的準(zhǔn)確性。整個(gè)算法的跟蹤流程框架如圖3所示。

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

本文選用了5組不同場(chǎng)景下具有代表性的測(cè)試視頻Coke、Faceocc2、Suv、sylvester、tiger2，包括了遮擋、形變和光照變化等情況，各視頻的具體屬性見(jiàn)表1。將本文算法與原始TLD[7]、CT跟蹤算法[9]、MIL[10]和Meanshift算法（MS-V）進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)在Intel Core(TM)2 Duo CPU主頻2.5GHz的臺(tái)式機(jī)上實(shí)現(xiàn)，利用OpenCV2.4.9在VS2010上進(jìn)行調(diào)試。

4.1 評(píng)估方法

本文從定性和定量?jī)蓚€(gè)方面評(píng)估算法的性能，在進(jìn)行定量分析時(shí)采用精度和成功率作為評(píng)價(jià)指標(biāo)。另外，采用文獻(xiàn)[17]提出的時(shí)間魯棒性和空間魯棒性評(píng)估跟蹤算法的魯棒性。

1）精確度圖

采用精確度圖[10,18]對(duì)算法的整體跟蹤精度進(jìn)行評(píng)估，其能夠顯示跟蹤的目標(biāo)位置在給定的實(shí)際目標(biāo)位置的某一閾值范圍之內(nèi)的幀數(shù)占總幀數(shù)的百分比。

圖2 子區(qū)域劃分示意圖

圖3 算法流程圖

表1 測(cè)試視頻的詳細(xì)描述

為了對(duì)每個(gè)跟蹤器進(jìn)行具有代表性的精度評(píng)分，本文選用閾值等于20pixels時(shí)每個(gè)跟蹤器的精度值進(jìn)行比較。

2）成功率圖

3）魯棒性評(píng)估

在對(duì)跟蹤算法進(jìn)行魯棒性評(píng)估時(shí)，本文使用了文獻(xiàn)[10]提出的時(shí)間魯棒性評(píng)估（Temporal Robustness Evaluation，TRE）和空間魯棒性評(píng)估（Spatial Robustness Evaluation，SRE）兩種方式來(lái)評(píng)估跟蹤器對(duì)初始化的魯棒性，即在時(shí)間上（即在不同幀開(kāi)始跟蹤）和空間上（即以不同的邊界框開(kāi)始跟蹤）擾亂初始化。

4.2 結(jié)果分析

本文算法的實(shí)驗(yàn)參數(shù)設(shè)置為：子區(qū)域數(shù)量＝4，每個(gè)子區(qū)域的特征數(shù)目＝30，隨機(jī)蕨分類器中蕨的數(shù)目＝10，每個(gè)蕨包含的特征數(shù)目＝13，特征點(diǎn)鄰域塊的大小×＝5×5，子窗口的大小為×＝31×31，遮擋判斷閾值為0.6，其他參數(shù)與TLD算法相同。對(duì)于其他4種跟蹤算法均采用原文中的參數(shù)設(shè)置。

4.2.1 整體性能

每一個(gè)跟蹤算法的整體性能以成功率圖和精確度圖的形式展示在圖4中。右上角為排序結(jié)果。通過(guò)圖4可以發(fā)現(xiàn)，不管是在成功率圖還是在精確度圖中，本文提出的算法整體性能較優(yōu)異，這說(shuō)明本文算法具有較強(qiáng)的魯棒性。比如在空間魯棒性精確度圖中，本文算法比排名第二的TLD算法的性能高7.1%，比排名最后的MS-V算法的性能高48.1%。而在時(shí)間魯棒性成功率圖中，本文算法比排名第二的TLD算法的性能高5.3%，比排名最后的MS-V算法的性能高29.7%。

4.2.2 基于跟蹤序列特性的性能分析

1）抗遮擋能力

本文所選擇的測(cè)試視頻中有4個(gè)視頻存在遮擋的情況。圖5為各跟蹤算法在存在遮擋的視頻中的跟蹤效果截圖。圖6為各跟蹤算法在所有遮擋視頻的SRE、TRE圖。從整體跟蹤效果來(lái)看，由于MS-V算法是離線跟蹤算法，對(duì)目標(biāo)的外觀模型不進(jìn)行在線學(xué)習(xí)更新，所以一旦目標(biāo)的外觀發(fā)生變化，容易產(chǎn)生跟蹤漂移。而其他4種算法能夠在線學(xué)習(xí)更新目標(biāo)的外觀模型，表現(xiàn)出了比MS-V算法更強(qiáng)的魯棒性，圖6也證明了這一點(diǎn)。另一方面，從單個(gè)測(cè)試視頻來(lái)看，本文算法的多區(qū)域隨機(jī)蕨分類器在進(jìn)行多區(qū)域融合的同時(shí)，采用了遮擋判斷機(jī)制，所以當(dāng)圖中的目標(biāo)出現(xiàn)不同程度的遮擋時(shí)，本文算法仍能較準(zhǔn)確地跟蹤目標(biāo)，而其他4種算法缺乏遮擋判斷機(jī)制，所以當(dāng)圖5(a)#41、#188，(c)#549、#564和(d)#118、#151中的目標(biāo)被遮擋，跟蹤框發(fā)生嚴(yán)重漂移。

圖4 SRE、TRE圖，圖中給出了每個(gè)跟蹤算法的性能評(píng)分

2）處理二維、三維旋轉(zhuǎn)和光照變化的能力

圖7為各算法跟蹤效果截圖。在圖7(a)中，coke目標(biāo)的光照變化由弱到強(qiáng)再到弱，目標(biāo)在第101幀時(shí)發(fā)生了旋轉(zhuǎn)，此時(shí)除了本文算法其他各跟蹤算法的跟蹤框都產(chǎn)生了漂移。在圖7(b)sylvester中，目標(biāo)在#612幀中發(fā)生了三維旋轉(zhuǎn)并伴有較大的形變，此時(shí)，本文算法較其他4種算法而言跟蹤效果較好。同樣在圖7(c) tiger2的跟蹤效果截圖中，本文算法的跟蹤框能夠始終穩(wěn)定的框定目標(biāo)。這是由于本文算法選用的目標(biāo)特征，能夠充分考慮特征點(diǎn)周圍的圖像塊的信息，通過(guò)不斷地學(xué)習(xí)目標(biāo)形變光照變化并將其加入到目標(biāo)在線模型中，因此在整個(gè)跟蹤過(guò)程中能穩(wěn)定跟蹤目標(biāo)。圖8進(jìn)一步顯示了本文算法在處理二維、三維旋轉(zhuǎn)和光照變化情況的魯棒性。

圖5 各算法跟蹤效果截圖，其中(a)為Coke；(b)為Faceocc2；(c)為Suv；(d)為tiger2

圖6 遮擋情況下的性能評(píng)分圖

圖7 各算法跟蹤效果截圖，其中(a)為Coke序列；(b)為Sylvester序列；(c)為tiger2序列

(a) 為光照變化子集圖；(b)為二維旋轉(zhuǎn)子集圖；(c)為三維旋轉(zhuǎn)子集圖

5 結(jié)論

為了實(shí)現(xiàn)算法對(duì)目標(biāo)長(zhǎng)時(shí)穩(wěn)定的跟蹤，有效應(yīng)對(duì)跟蹤過(guò)程中的目標(biāo)遮擋、姿態(tài)變化，光照變化等情況，本文提出了基于多區(qū)域的隨機(jī)蕨在線跟蹤算法。一方面，基于積分圖的隨機(jī)蕨分類器計(jì)算速度快，能夠滿足實(shí)時(shí)性的要求；而多區(qū)域融合則能夠充分考慮目標(biāo)的不同區(qū)域的特征信息，具有較強(qiáng)的魯棒性。因此本文將兩者進(jìn)行有效地結(jié)合，并應(yīng)用到TLD在線跟蹤框架中，然后通過(guò)在5組具有代表性的測(cè)試序列上進(jìn)行了驗(yàn)證，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了定性和定量的分析，結(jié)果顯示，本文提出的算法在目標(biāo)發(fā)生遮擋、光照變化等現(xiàn)象時(shí)，仍能持續(xù)穩(wěn)定地跟蹤目標(biāo)。但是多區(qū)域融合也使得算法的處理速度有所降低，未來(lái)將進(jìn)一步改進(jìn)。另外本文算法只能實(shí)現(xiàn)對(duì)單目標(biāo)的跟蹤，未來(lái)將加強(qiáng)對(duì)多目標(biāo)跟蹤算法的研究。

[1] 賈松敏, 王爽, 王麗佳, 等. 多特征自適應(yīng)均值漂移算法的目標(biāo)跟蹤[J]. 光電子激光, 2014, 25(10): 2018-2024. JIA Songmin, WANG Shuang, WANG Jiali, et al. Human tracking based on adoptive multi-feature mean-shift Humalgorithm[J]., 2014, 25(10): 2018-2024.

[2] 胡波, 陳懇, 徐建瑜, 等. 基于Kalman預(yù)測(cè)和Mean-shift算法的視頻目標(biāo)跟蹤[J]. 光電子激光, 2009, 20(11): 1517-1522. HU Bo, CHEN Ken, XU Jianyu, et al. Video object tracking based on Mean-shift with self-adaptability search window and Kalman prediction[J]., 2009, 20(11): 1517-1522.

[3] 趙鵬, 沈庭芝, 單寶堂.一種基于粒子濾波的無(wú)人機(jī)電視導(dǎo)引系統(tǒng)目標(biāo)跟蹤算法[J]. 光學(xué)精密工程, 2008, 16(11): 134-140. ZHAO Peng, SHEN Tingzhi, SHAN Baotang. An object tracking algorithm for TV guiding system of UAV based on particle filter[J]., 2008, 6(11): 134-140.

[4] Collins T R, LIU Y, Leordeanu M. Online selection of discriminative tracking features[J]., 2005, 27(10): 1631-1643

[5] Grabner H, Sochman J, Bischof H, et al. Training sequential on-line boosting classifier for visual tracking[C]//(ICPR), 2008: 1-4.

[6] Saffari A, Leistner C, Santner J, et al. On-line random forests[C]//, 2009: 1393 -1400.

[7] Kalal Z, Matas J, Mikolajczyk K. Tracking-learning-detection[J]., 2012: 1409-1422.

[8] Grabner H, Leistner C, Bischof H. Semi-supervised on-line boosting for robust tracking[C]//, 2008: 234-247.

[9] ZHANG K, ZHANG L, YANG M H. Real-time compressive tracking[C]/, Springer-Verlag, 2012, 7574(1): 864-877.

[10] Babenko B, YANG M H, Belongie S. Robust object tracking with online multiple instance learning[J]., 2011, 33(8): 1619-1632.

[11] Possegger H, Mauthner T, Roth P M, et al. Occlusion geodesics for online multi-object tracking[C]//, 2014: 1306-1313.

[12] 萬(wàn)琴, 王耀南, 袁小芳. 改進(jìn)聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)的視頻多目標(biāo)快速跟蹤[J]. 控制理論與應(yīng)用, 2011, 28(10): 1421-1430. WAN Qin, WANG Yaonan, YUAN Xiaofang. Tracking multiple video objects based on improved joint probabilistic data association[J]., 2011, 28(10): 1421-1430.

[13] Andriyenko A, Schindler K. Multi-target tracking by continuous energy minimization[C]//, 2011: 1265-1272.

[14] Bae S H, Yoon K J. Robust Online Multi-object Tracking Based on Tracklet Confidence and Online Discriminative Appearance Learning[C]//, 2014: 1218-1225.

[15] Breiman L. Random forests[J]., 2001, 45: 5-32.

[16] 郭玉杰, 周海英, 武敬民. 基于積分圖的隨機(jī)蕨特征點(diǎn)識(shí)別算法[J]. 科學(xué)技術(shù)與工程, 2014, 14(4): 260-264. GUO Yujie, ZHOU Haiying, WU Jingmin. Keypoint recognition algorithm using random ferns based on integral image[J]., 2014, 14(4): 260-264.

[17] WU Y, Lim J, YANG M H. Online object tracking: a benchmark[C]//, 2013: 2411-2418.

[18] Henriques J F, Rui C, Martins P, et al. Exploiting the circulant structure of tracking-by-detection with Kernels[C]//, 2012, 7575(1): 702-715.

An Online Object Tracking Algorithm Using Random Ferns Based on Multi-regions

LI Ting，ZHAO Wenjie，YANG Shuai

（Aviation University of Air Force, Changchun 130000, China）

The random forest algorithm which uses gray value of pixel-pair to construct the binary features is apt to lead to the tracking failure (drift), especially the appearance change caused by occlusion, fast motion, and illumination variation. In this paper, an online tracking algorithm using the random ferns based on multi-region is proposed. First, the candidate area is divided into different sub-areas, then the random ferns based on the integral images is used to classify the patches, and the detection result being adaptively fused in order to decrease the influence of the occluded sub-regions. Combined with the improvement of TLD algorithm, the experiment is made on four different videos. The results show that this proposed algorithm performed better on some complex scenes. In the video sequence of 320×240pixels, the speed can keep on 20～30 frame/s or so, and the object center position error is in 30 pixels, while the accuracy can reach above 80%.

object tracking，random ferns，multi-region fusion，online object model

TP391

A

1001-8891(2016)12-0953-07

2016-05-27；

2016-06-24.

李婷（1991-），女，江蘇省，碩士生，主要從事視頻目標(biāo)跟蹤方面的研究。

國(guó)家自然科學(xué)基金：霧視錯(cuò)覺(jué)理論及應(yīng)用研究（61301233）。