基于在線半監督boosting的協同訓練目標跟蹤算法

陳 思 蘇松志 李紹滋呂艷萍 曹冬林

(廈門大學信息科學與技術學院 廈門 361005)(福建省仿腦智能系統重點實驗室(廈門大學) 廈門 361005)

1 引言

目標跟蹤是人工智能和計算機視覺的重要研究課題[1]。然而，由于受到場景中各種復雜因素的影響，如光照、旋轉、移動和遮擋等，目標跟蹤已成為一項極具挑戰的任務[2]。目前研究者已經提出諸多目標跟蹤算法[312]-，大致分為生成式算法[35]-和判別式算法[612]-。判別式目標跟蹤算法[612]-將跟蹤視為目標和背景的2類分類問題，受到學者的廣泛關注。現有的大多數判別式目標跟蹤算法[68]-，例如在線boosting[6,7]和在線半監督 boosting算法[8]，利用分類器的預測結果更新分類器自身，即稱為自訓練(self-training)[13,14]。此類方法對類別噪聲比較敏感，容易累積分類錯誤。

為了克服自訓練目標跟蹤算法的不足，本文提出一種基于在線半監督boosting的協同訓練目標跟蹤算法(Co-training based on online Semisupervised Boosting，簡稱Co-SemiBoost)。本文的主要創新點如下：(1)提出了一種新的在線協同訓練框架，利用未標記樣本協同訓練不同視圖中的弱分類器，能夠在克服目標漂移的同時保持對目標外觀的自適應更新；(2)基于半監督技術，結合目標先驗模型和在線分類器迭代預測未標記樣本的偽類別標記和權重。本文算法能夠魯棒地處理目標遮擋、光照變化、快速運動和復雜背景等問題。若干具有挑戰性的視頻序列實驗結果表明，本文提出的算法具有良好的目標跟蹤性能。

2 基于在線半監督 boosting的協同訓練目標跟蹤算法

2.1 目標跟蹤流程

Co-SemiBoost算法是一種基于檢測的跟蹤算法(tracking-by-detection)[10]。Co-SemiBoost目標跟蹤算法的具體流程如圖1所示。

跟蹤過程中，Co-SemiBoost算法迭代執行以下兩個步驟：(1)分類器更新：在第t幀目標位置周圍區域內獲取若干圖像塊作為未標記樣本，并依次利用在線協同訓練框架更新強分類器；(2)目標檢測：利用更新后的強分類器預測第t+1幀中搜索區域內各個圖像塊的置信度，置信度最高的圖像塊被視為新的目標位置。其中，分類器更新是目標跟蹤算法的關鍵步驟。Co-SemiBoost算法采用一種有效的基于在線半監督boosting的協同訓練框架來更新強分類器，從而克服自訓練跟蹤算法的不足。

2.2 在線協同訓練

協同訓練算法[15,16]首先利用少量有標記樣本訓練兩個初始分類器，然后在學習過程中，這些分類器挑選若干個置信度高的未標記樣本進行標記并用于更新對方分類器，此過程不斷迭代，從而有效提高分類性能。理論已證明[16]，當數據集有兩個充分冗余的視圖，即兩個滿足下述條件的特征集：(1)如果訓練樣本足夠，在每個特征集上都足以學到一個強分類器；(2)在給定類別標記時，每個特征集都條件獨立于另一個特征集，那么協同訓練算法可以有效地利用未標記樣本提升分類器的性能。本文利用Haar[17]特征和LBP[18]特征分別描述灰度圖像，獲得兩個充分冗余的視圖，并在這兩個視圖上進行協同訓練，從而有效提高分類性能。Haar和LBP特征具有不同的目標辨別能力。Haar特征主要關注局部紋理變化信息(即對目標的姿態、形變等變化比較魯棒)，而LBP特征更多關注邊緣變化信息(即對光照等變化比較魯棒)。因此，對Haar特征難以區分的樣本，LBP特征可能擁有較好的區分能力，反之亦然。

Co-SemiBoost算法所采用的在線協同訓練框架如圖2所示，其中視圖1和視圖2分別表示Haar和LBP特征視圖。本文使用了“選擇器”[6]的概念，其定義如下：給定一個M個弱分類器的集合，一個選擇器根據某一優化準則從中選出一個最優弱分類器。訓練一個選擇器意味著M個弱分類器被更新并從中選出一個最優弱分類器。假設每個特征視圖包含N個選擇器，每個選擇器包含M個弱分類器，則第j個視圖中第n個選擇器包含的M個弱分類器記為，其中每個弱分類器對應該特征視圖下的一個隨機特征。

圖1 Co-SemiBoost目標跟蹤算法流程圖

圖2 Co-SemiBoost算法的在線協同訓練框架

如圖2所示，Co-SemiBoost算法采用在線學習方式[6]將當前幀目標周圍區域的未標記樣本依次作為協同訓練的輸入樣本，即每次利用一個未標記樣本更新所有選擇器。該算法的在線協同訓練過程具體描述如下：首先，隨機初始化每個特征視圖的 N個選擇器。假設第1幀的目標位置已知，則從第1幀中獲取有標記數據，即目標區域作為正樣本，非目標區域作為負樣本。初始時，在兩個特征視圖上分別利用有標記數據訓練先驗分類器和，這里采用boosting方法進行訓練。其次，在兩個視圖中分別利用先驗模型預測未標記樣本的類別和權重，并用于更新對方視圖的選擇器1, 2)中的M個弱分類器。然后，當選擇器中的M個弱分類器被更新后，利用半監督技術預測該未標記樣本的偽類別標記和權重，并用于更新對方視圖的下一個選擇器中的M個弱分類器，此步驟不斷迭代，直到更新完第N個選擇器為止。同時在上述步驟中，兩個視圖中的每個選擇器依次選出最優弱分類器并計算相應的投票權重。最后將各最優弱分類器及其權重集成為最終的強分類器。

2.3 類別預測與權重估計

基于在線半監督 boosting算法[8]，Co-SemiBoost算法通過衡量未標記樣本與有標記樣本的相似度來判斷未標記樣本的類別標記。為了更新第j個特征視圖(j = 1, 2)中的每個選擇器，該算法首先利用第3 j- 個特征視圖的分類信息來預測未標記樣本x屬于正類和負類的置信度，具體計算如下：

2.4 不同視圖的弱分類器構建

本文使用閾值法[6]構建Haar特征對應的弱分類器。將每個樣本上隨機位置和大小的Haar值作為一個特征值，并構建對應的弱分類器：

本文使用最近鄰方法[6]構建LBP特征對應的弱分類器。對隨機圖像區域里的每個像素點計算其4個鄰點的LBP值，并對該圖像區域生成16-bin的LBP直方圖特征，然后構建該特征 ,()jn mf x對應的弱分類器：

Co-SemiBoost算法的偽代碼描述如表1所示。

3 實驗結果與分析

本文實驗分為兩部分：(1)對比在線半監督boosting算法分別在Haar和LBP特征視圖進行自訓練，以及本文提出的Co-SemiBoost算法在Haar和LBP特征視圖上進行協同訓練的跟蹤性能。(2)對比Co-SemiBoost算法和3種新近跟蹤算法的性能。3種跟蹤算法分別為在線半監督b o o s t i n g算法(SemiBoost)[8]，在線boosting算法(OAB)[6]和在線多示例跟蹤器(MIL)[10]。4種方法均使用Haar和LBP兩種特征進行訓練。本文選擇4個具有挑戰性的公共視頻序列[20]進行實驗，分別為Coupon Book,Cola Can,Tiger 1和Tiger 2。實驗使用統一的參數設置。選擇器的個數N設為25。對于Haar特征和LBP特征，弱分類器的個數M均設為100。搜索區域為上一幀目標窗口區域的2倍。SemiBoost[8],OAB[6]和MIL算法[10]的其余參數均使用默認參數設置。所有視頻序列僅僅已知第1幀中目標位置。實驗平臺為Windows XP系統，3.01 GHz處理器和3.25 GB內存的個人計算機。

表1 Co-SemiBoost算法的偽代碼

實驗記錄了視頻序列的目標中心位置的平均誤差值，即所有幀的目標中心位置誤差值之和與視頻幀數的比值。此外，實驗也采用了“目標跟蹤精確度圖”[10]來驗證跟蹤性能。該圖記錄了隨著閾值的變化，算法跟蹤到的目標中心和實際目標中心之間距離小于給定閾值的幀數百分比。本文閾值區間定為[0,100]。本文還給出閾值為20時目標跟蹤的精確度，其相當于算法跟蹤到的目標窗口和實際目標窗口有至少50%覆蓋面積的幀數百分比[10]。此外，實驗還對比了各算法的運行速度，即在4個視頻序列上每秒平均運行的幀數。

表2列出了對比算法的目標中心位置的平均誤差值和運行速度(平均幀數/s)，其中最小平均誤差值用粗體字表示。由表2可知，本文的Co-SemiBoost算法的平均誤差值明顯低于SemiBoost(Haar)和SemiBoost(LBP)算法。由于SemiBoost(Haar)和SemiBoost(LBP)包含的弱分類器個數是Co-SemiBoost算法的一半，故其運行速度略快于Co-SemiBoost算法。但SemiBoost(Haar)和SemiBoost(LBP)容易累積分類錯誤，其目標位置誤差值遠大于Co-SemiBoost算法。可見，本文的在線協同訓練機制是有效的，克服了自訓練的不足。

表2 SemiBoost(Haar), SemiBoost(LBP)與本文算法的目標中心位置平均誤差值(像素)和運行速度(平均幀數/s)

本實驗對比了Co-SemiBoost算法與SemiBoost算法(同時使用Haar和LBP特征視圖)，OAB算法和MIL算法的跟蹤性能。表3給出了SemiBoost, OAB,MIL和Co-SemiBoost算法的平均誤差值和運行速度(平均幀數/s)，表3表明Co-SemiBoost算法的平均誤差值明顯低于其它3種對比算法。從運行速度看，當同時使用Haar和LBP特征且弱分類器個數相同時，OAB算法運行速度最快，MIL算法次之，SemiBoost和Co-SemiBoost算法的運行速度相當。由于SemiBoost和Co-SemiBoost算法需要迭代地更新弱分類器，因此增加了時間復雜度。可見，Co-SemiBoost算法具有魯棒的跟蹤性能和良好的跟蹤速度。

圖3所示為對比算法在閾值區間[0,100]的目標跟蹤精確度。從圖3可知，Co-SemiBoost算法在較低閾值處具有較高的精確度。表4具體給出了閾值為20時的目標跟蹤精確度，其中最高精確度用粗體字表示。例如Coupon Book視頻有約90%視頻幀的目標中心位置距離實際中心位置在20個像素以內。然而當閾值為20時，其它3種算法在4個視頻中的精確度均明顯低于Co-SemiBoost算法。因此，實驗結果表明Co-SemiBoost算法采用的協同訓練機制是有效可行的，能夠自適應目標外觀的變化，同時較好地克服目標漂移問題。

表3 4種對比算法的目標中心位置平均誤差值(像素)和運行速度(平均幀數/s)

圖4給出了4個視頻中有代表性的目標跟蹤效果圖。如圖4(a)所示，Coupon Book視頻在第52幀時被跟蹤的票券被折起，從而目標外觀發生變化。在第133幀和第303幀，被跟蹤的票券不斷受到旁邊一張假票券的影響。OAB算法由于沒有保存先驗模型，發生了嚴重的目標漂移。SemiBoost算法由于迭代過程中分類錯誤不斷加強，也慢慢地漂離跟蹤目標。而MIL算法由于在學習過程中沒有區分正包中不同樣本的重要性，因此MIL算法的跟蹤性能不穩定。Co-SemiBoost算法由于在協同訓練過程中不斷提升分類器的判別能力，并且融入了目標先驗知識，因此能夠較好地區分相似對象，更穩定地跟蹤到目標。

表4 閾值為20時的目標跟蹤精確度(%)

圖3 4種對比算法的目標跟蹤精確度圖

圖4 4個視頻中4種對比算法的目標跟蹤結果示例圖

圖4(b)給出了Cola Can視頻中第13，第81和第245幀的目標跟蹤結果。受到光照、快速移動和旋轉的影響，SemiBoost和MIL算法在迭代過程中的分類錯誤不斷累積，分類器性能下降，均發生目標漂移。OAB算法跟蹤到的目標位置不精確，導致獲取到的正樣本不準確。Co-SemiBoost算法能夠更準確地跟蹤到目標，因為其利用未標記樣本協同訓練分類器，克服了自訓練的不足，提高了分類器的性能。

如圖4(c)所示，在Tiger 1視頻中，玩具老虎在光照變化和復雜背景下被旋轉和快速移動。例如第121幀目標被快速移動并且出現部分遮擋。在第215幀時，目標被快速移動而使圖片中目標區域變得模糊，并且出現較嚴重的遮擋現象。第282幀老虎面部外觀發生明顯變化。在這些幀中，Co-SemiBoost算法均能夠準確地跟蹤到目標，而其它算法都漂移到了周圍的物品。

圖4(d)給出了Tiger 2視頻在光照條件和復雜背景下第77，第126和第270幀的跟蹤結果，例如第77幀目標被快速移動出現模糊，第126幀目標外觀出現顯著變化，以及第270幀目標被旋轉和部分遮擋。Co- SemiBoost算法能夠穩定地跟蹤到玩具老虎，而其它算法都出現漂移問題。

綜上所述，Co-SemiBoost算法采用的在線協同訓練框架是有效可行的，明顯優于基于自訓練的在線boosting和在線半監督boosting算法。并且與新近提出的在線多示例跟蹤器相比，Co-SemiBoost算法總體上具有更優的跟蹤性能。因此，在復雜的跟蹤環境下，Co-SemiBoost算法既具有自適應能力，又在一定程度上有效地抑制了目標漂移問題。

4 結束語

本文提出了一種魯棒的基于在線半監督boosting的協同訓練目標跟蹤算法(Co-SemiBoost)。該算法采用一種有效的在線協同訓練框架，利用未標記樣本協同訓練不同視圖中的弱分類器，克服了自訓練目標跟蹤算法的不足，從而提高了分類器的判別能力。同時，Co-SemiBoost算法保持了在線半監督boosting算法的優勢，結合目標先驗模型和在線分類器來預測未標記樣本的偽類別標記和權重，能夠有效處理目標遮擋和光照變化等問題。實驗結果表明，Co-SemiBoost算法具有魯棒的跟蹤性能。另外，由于該算法主要解決單目標的在線跟蹤問題，沒有考慮多目標之間的關聯性以及多目標運動軌跡估計等問題，因此不適用于多目標跟蹤問題；如何擴展本文算法用以解決多目標跟蹤將是我們重點研究的方向。此外，由于不同的特征視圖可能適合于不同的跟蹤場景，因而我們將進一步研究在各種場景下不同特征視圖的適用性問題。

[1] Yang Han-xuan, Shao Ling, Zheng Feng, et al.. Recent advances and trends in visual tracking: a review[J].Neurocomputing, 2011, 74(18): 3823-3831.

[2] Yilmaz A, Javed O, and Shah M. Object tracking: a survey[J].ACM Computing Surveys, 2006, 38(4): 1-45.

[3] 孫景樂, 唐林波, 趙保軍, 等. 基于瑞利分布的粒子濾波跟蹤算法[J]. 電子與信息學報, 2013, 35(4): 763-769.Sun Jing-le, Tang Lin-bo, Zhao Bao-jun, et al.. A new particle filter tracking algorithm based on Rayleigh distribution[J]. Journal of Electronics ＆amp; Information Technology, 2013, 35(4): 763-769.

[4] 董文會, 常發亮, 李天平. 融合顏色直方圖及 SIFT特征的自適應分塊目標跟蹤方法[J]. 電子與信息學報, 2013, 35(4):770-776.Dong Wen-hui, Chang Fa-liang, and Li Tian-ping. Adaptive fragments-based target tracking method fusing color histogram and SIFT features[J]. Journal of Electronics ＆amp;Information Technology, 2013, 35(4): 770-776.

[5] Jia Xu, Lu Hu-chuan, and Yang Ming-hsuan. Visual tracking via adaptive structural local sparse appearance model[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Rhode Island, 2012: 1822-1829.

[6] Grabner H and Bischof H. On-line boosting and vision[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, New York, 2006: 260-267.

[7] Grabner H, Grabner M, and Bischof H. Real-time tracking via on-line boosting[C]. Proceedings of British Machine Vision Conference, Edinburgh, 2006: 47-56.

[8] Grabner H, Leistner C, and Bischof H. Semi-supervised on-line boosting for robust tracking[C]. Proceedings of European Conference on Computer Vision, Marseille, 2008:234-247.

[9] Tang Feng, Brennan S, Zhao Qi, et al.. Co-tracking using semi-supervised support vector machines[C]. Proceedings of the IEEE International Conference on Computer Vision,Brazil, 2007: 1-8.

[10] Babenko B, Yang Ming-hsuan, and 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] Zhang Kai-hua, Zhang Lei, and Yang Ming-hsuan. Real-time compressive tracking[C]. Proceedings of European Conference on Computer Vision, Florence, 2012: 866-879.

[12] Yu Qian, Dinh T B, and Medioni G. Online tracking and reacquisition using co-trained generative and discriminative trackers[C]. Proceedings of European Conference on Computer Vision, Marseille, 2008: 678-691.

[13] Zhu Xiao-jin. Semi-supervised learning literature survey[R].Computer Sciences TR-1530, USA: University of Wisconsin-Madison, 2007.

[14] Mallapragada P K, Jin Rong, Jain A K, et al.. SemiBoost:Boosting for semi-supervised learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(11):2000-2014.

[15] Lewandowski M and Orwell J. Co-training on multi-view unlabelled data[C]. Proceedings of the 27th Conference on Image and Vision Computing, New Zealand, 2012: 423-428.

[16] Blum A and Mitchell T. Combining labeled and unlabeled data with co-training[C]. Proceedings of the Eleventh Annual Conference on Computational Learning Theory, Madison,1998: 92-100.

[17] Viola P and Jones M. Rapid object detection using a boosted cascade of simple features[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,Kauai, 2001: 511-518.

[18] Ahonen T, Hadid A, and Pietikainen M. Face description with local binary patterns: application to face recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(12): 2037-2041.

[19] Oza N. Online ensemble learning[D]. [Ph.D. dissertation],University of California, 2001.

[20] Babenko B, Yang Ming-hsuan, and Belongie S. Visual tracking with online multiple instance learming[OL]. http://vision.ucsd.edu/~bbabenko/project_miltrack.shtml. 2009.