基于多區域的隨機蕨在線目標跟蹤算法

李 婷，趙文杰，楊 帥

?

基于多區域的隨機蕨在線目標跟蹤算法

李 婷，趙文杰，楊 帥

（空軍航空大學，吉林 長春 130000）

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

目標跟蹤，隨機蕨算法，多區域融合，目標在線模型

0 引言

視頻目標跟蹤是計算機視覺領域中一個重要的研究方向。近20年來，關于視頻目標跟蹤算法的研究得到了飛速的發展。視頻目標跟蹤算法從早期的離線跟蹤[1-3]發展到在線跟蹤[4-10]。從對單目標的跟蹤[1-6]發展到對多目標的跟蹤[11-14]。研究者們一直在努力尋找一種實時性高魯棒性強的跟蹤算法，Collin[4]首次提出將跟蹤視為二分類問題，強調了背景對目標跟蹤的作用；隨后Grabner[5]提出了在線Boosting跟蹤算法，實現了對目標模型的在線更新，可是如果模板存在誤差，就非常容易導致跟蹤漂移。2009年，Saffari[6]首先將隨機森林用于在線學習領域，提高了算法的運算效率和魯棒性。2010年Kalal等[7]將在線隨機森林檢測與光流跟蹤相結合提出了目標長時跟蹤的TLD算法。之后隨機森林算法在目標跟蹤領域得到了廣泛的應用。

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

本文在文獻[16]的基礎上提出了基于多區域融合的隨機蕨跟蹤算法，在跟蹤初始階段對目標區域進行分塊，分區域采用二值隨機蕨算法對目標進行檢測，自適應地融合每個區域的檢測結果，進而確定目標位置并更新外觀特征。同時結合改進后的TLD算法提高算法跟蹤遮擋目標的魯棒性和實時性。

1 基于積分圖的隨機蕨

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

1.1 隨機蕨的構造

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

1.2 基于積分圖的二值判別函數

圖1 本文算法的二值特征函數示意圖

此時，定義每對圖像塊的二值描述為：

對發文機構進行統計分析，可以得到某一領域的主要研究機構及機構之間的合作關系。網絡信息行為領域發文機構的合作網絡如圖3所示。圖中節點的大小代表機構發文量的多少，節點之間的連線代表機構之間的合作關系。從圖3可以看出發文量最多的機構是武漢大學（8篇），其次為安徽大學（5篇）、北京理工大學（2篇）、武漢科技大學（2篇）、中山大學（2篇），這4個機構發文量≥2篇，只有武漢大學、安徽大學等少量機構之間存在合作，機構之間聯系比較分散，缺乏合作交流。總體來說，研究機構的科研力量薄弱，學術團體間合作不多且較為分散，缺乏有代表性的科研機構。

2 子區域的劃分與目標檢測

2.1 子區域的劃分

為了減少遮擋對目標特征更新的影響，本文在算法初始化時對目標進行區域的劃分。區域的數量是影響分類結果的關鍵因素，子區域數量過多，會增加計算量，影響算法的實時性，數量過少，則達不到分類效果，本文在充分考慮各方面影響因素的基礎上，將目標分為4個子區域，即橫向和縱向分別平均劃分為兩部分。見圖2。

2.2 子區域的目標檢測

對每個子區域采用基于積分圖的隨機蕨分類器進行目標的檢測，并記下每個圖像塊的綜合信息P＝(c,d)，d表示圖像塊所在子區域的標號。當圖像塊被判定為正樣本，c＝1；當圖像塊被判定為負樣本時，c＝0。利用下式計算出每個子區域正樣本的比例：

2.3 子區域檢測結果融合

在多區域的檢測結果融合上，算法通過兩個步驟實現，一是區域內圖像塊的選擇，二是區域間檢測結果的融合。第一步選用歐式距離作為判斷準則對子區域內的正樣本圖像塊進行選擇，得到每個子區域內最佳的跟蹤圖像塊。歐氏距離匹配過程：首先計算樣本圖像塊與目標模板圖像塊之間的歐式距離，歐式距離的計算可以通過運算式(6)實現；然后取歐式距離最小的樣本作為當前幀的目標框。這樣就可以初步篩選出每個區域的最佳跟蹤結果：

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

3 基于TLD框架的在線跟蹤

TLD算法是Kalal等在2010年提出的融合跟蹤-學習-檢測3個模塊的長時跟蹤算法框架，該算法在應對目標形變和防止誤差累積之間找到了折衷的辦法，并提供了跟蹤丟失的判斷依據和重新檢測的可能性，具有較高的實用價值。因此本文選擇TLD算法作為跟蹤框架，跟蹤模塊仍采用基于前后向錯誤檢測的光流法，檢測模塊則選擇本文的算法作為分類器，學習模塊選用檢測結果優先策略，利用檢測結果去更新跟蹤結果，進一步提高算法的準確性。整個算法的跟蹤流程框架如圖3所示。

4 實驗結果與分析

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

4.1 評估方法

本文從定性和定量兩個方面評估算法的性能，在進行定量分析時采用精度和成功率作為評價指標。另外，采用文獻[17]提出的時間魯棒性和空間魯棒性評估跟蹤算法的魯棒性。

1）精確度圖

采用精確度圖[10,18]對算法的整體跟蹤精度進行評估，其能夠顯示跟蹤的目標位置在給定的實際目標位置的某一閾值范圍之內的幀數占總幀數的百分比。

圖2 子區域劃分示意圖

圖3 算法流程圖

表1 測試視頻的詳細描述

為了對每個跟蹤器進行具有代表性的精度評分，本文選用閾值等于20pixels時每個跟蹤器的精度值進行比較。

2）成功率圖

3）魯棒性評估

在對跟蹤算法進行魯棒性評估時，本文使用了文獻[10]提出的時間魯棒性評估（Temporal Robustness Evaluation，TRE）和空間魯棒性評估（Spatial Robustness Evaluation，SRE）兩種方式來評估跟蹤器對初始化的魯棒性，即在時間上（即在不同幀開始跟蹤）和空間上（即以不同的邊界框開始跟蹤）擾亂初始化。

4.2 結果分析

本文算法的實驗參數設置為：子區域數量＝4，每個子區域的特征數目＝30，隨機蕨分類器中蕨的數目＝10，每個蕨包含的特征數目＝13，特征點鄰域塊的大小×＝5×5，子窗口的大小為×＝31×31，遮擋判斷閾值為0.6，其他參數與TLD算法相同。對于其他4種跟蹤算法均采用原文中的參數設置。

4.2.1 整體性能

每一個跟蹤算法的整體性能以成功率圖和精確度圖的形式展示在圖4中。右上角為排序結果。通過圖4可以發現，不管是在成功率圖還是在精確度圖中，本文提出的算法整體性能較優異，這說明本文算法具有較強的魯棒性。比如在空間魯棒性精確度圖中，本文算法比排名第二的TLD算法的性能高7.1%，比排名最后的MS-V算法的性能高48.1%。而在時間魯棒性成功率圖中，本文算法比排名第二的TLD算法的性能高5.3%，比排名最后的MS-V算法的性能高29.7%。

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

1）抗遮擋能力

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

圖4 SRE、TRE圖，圖中給出了每個跟蹤算法的性能評分

2）處理二維、三維旋轉和光照變化的能力

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

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

圖6 遮擋情況下的性能評分圖

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

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

5 結論

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

[1] 賈松敏, 王爽, 王麗佳, 等. 多特征自適應均值漂移算法的目標跟蹤[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預測和Mean-shift算法的視頻目標跟蹤[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] 趙鵬, 沈庭芝, 單寶堂.一種基于粒子濾波的無人機電視導引系統目標跟蹤算法[J]. 光學精密工程, 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] 萬琴, 王耀南, 袁小芳. 改進聯合概率數據關聯的視頻多目標快速跟蹤[J]. 控制理論與應用, 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]. 科學技術與工程, 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-），女，江蘇省，碩士生，主要從事視頻目標跟蹤方面的研究。

國家自然科學基金：霧視錯覺理論及應用研究（61301233）。