蔡明瓊，郭太良，姚劍敏

(福州大學(xué) 平板顯示技術(shù)國家地方聯(lián)合工程實驗室，福建 福州 350116)

基于改進On-line Boosting算法的視頻目標跟蹤

蔡明瓊，郭太良，姚劍敏

(福州大學(xué) 平板顯示技術(shù)國家地方聯(lián)合工程實驗室，福建 福州 350116)

針對目前基于在線學(xué)習(xí)的On-line Boosting 算法用于視頻目標跟蹤時對于快速移動的目標，容易引起跟蹤漂移的問題，提出一種將Surf算法融合于On-line Boosting的Surf-Boosting視頻目標跟蹤算法。該算法在原先的On-line Boosting算法的基礎(chǔ)上增加跟蹤漂移判斷，對已跟蹤漂移的視頻幀使用Surf算法進行目標定位，將Surf定位到的目標作為正樣本放到后續(xù)On-line Boosting算法中繼續(xù)跟蹤學(xué)習(xí)。實驗結(jié)果表明，該方法能夠很好地抑制原有算法的跟蹤漂移問題，在跟蹤過程中的正確率達到98%，實現(xiàn)對快速移動目標的正確跟蹤，并具有很好的魯棒性。

On-line Boosting；Surf；快速移動；目標跟蹤

在計算機視覺中，視頻目標跟蹤是一個重要的研究方向，它是后續(xù)更高層次行為理解如：目標行為分析、行為識別、視頻圖像壓縮等的基礎(chǔ)核心技術(shù)之一，廣泛應(yīng)用于公共安全領(lǐng)域、軍事國防領(lǐng)域、醫(yī)學(xué)檢測領(lǐng)域等。On-line Boosting算法應(yīng)用于視頻目標跟蹤，是一種基于在線學(xué)習(xí)的目標跟蹤算法，它把跟蹤問題看做是一個背景和目標的分類問題[1]，得到了廣泛的應(yīng)用。

基于學(xué)習(xí)的目標跟蹤算法，近年來引起了國內(nèi)外學(xué)者的廣泛關(guān)注，在文獻[2-4]中提出的基于在線關(guān)鍵幀的選擇，是一種無結(jié)構(gòu)的最近鄰在線學(xué)習(xí)模型，該方法的優(yōu)點是數(shù)據(jù)簡單，學(xué)習(xí)速度快，可以時時更新，缺點是模板匹配準確度低，容易丟失跟蹤目標；在文獻[5]中Jepson 等人重點研究了3種基周期混合學(xué)習(xí)模型：長期穩(wěn)定模板、短期穩(wěn)定模板和噪聲模板，并認為任何的跟蹤模型都是上述3種模板的線性疊加；Sung， Kim和 Ross等人在文獻[6-7]中提出快速有效的增量學(xué)習(xí)策略，利用新到來的數(shù)據(jù)更新原有的均值向量和特征子空間。

Grabner 從2006年開始對在線學(xué)習(xí)的目標跟蹤算法進行了大量的研究，發(fā)表了眾多的文獻，其經(jīng)典的算法是文獻[8]提出的基于Haar-like 特征的On-line Boosting算法，該算法具有學(xué)習(xí)速度快、無需提前訓(xùn)練分類器以及可實現(xiàn)實時跟蹤的優(yōu)點，2012年其在文獻[9]中提出了一種基于目標的運動特點，并將運動特點考慮到目標跟蹤中的算法，該算法雖然能夠在一定程度上抑制跟蹤漂移，但是對快速移動的目標的跟蹤漂移抑制能力仍然不足。對于快速移動的目標，目前的方法還不能進行正確有效的跟蹤，對于跟蹤過程中引起跟蹤漂移，沒有一個合適的機制，用于恢復(fù)這種漂移，以便進行后續(xù)的跟蹤。針對以上所述的一些不足，本文提出了一種改進的On-line Boosting算法用于視頻目標跟蹤，該算法在跟蹤過程中增加跟蹤漂移的判斷，對跟蹤漂移的視頻幀使用Surf(Speeded up robust features)[10]算法正確定位目標，再把定位到的目標當做正樣本，放到后續(xù)的跟蹤中繼續(xù)學(xué)習(xí)，Surf算法具有快速計算能力，保證了跟蹤的實時性，最終實現(xiàn)對快速移動目標的正確跟蹤，具有良好的魯棒性。

1 基于On-line Boosting的視頻目標跟蹤及其不足

在機器學(xué)習(xí)中，Boosting算法是一種用于提高任意給定學(xué)習(xí)算法準確度的通用方法，其思想是源于Valiant提出的 PAC (Probably Approximately Correct)學(xué)習(xí)模型。Boosting 通過給定的樣本，循環(huán)訓(xùn)練N個弱分類器，再將這些弱分類器按照一定的方式組合成一個強分類器，On-line Boosting 用于視頻目標跟蹤中，弱分類器的訓(xùn)練是在線的，最終的強分類器可用于區(qū)分背景和目標，從而將目標從復(fù)雜的背景中識別出來。

1.1 算法的理論介紹

強分類器：一個強分類器hstrong(x)是由若干個弱分類器線性組合而成的，它的識別誤差率很低，強分類器的識別結(jié)果是由式(1)決定的

(1)

式中：an表示每個弱分類器所對應(yīng)的權(quán)重；N表示所有弱分類器的個數(shù)。

圖1 On-line Boosting算法用于視頻跟蹤流程圖

(2)

按照同樣的方式更新一個特征池中所有的弱分類器，選擇器從中選擇誤差率en最小的弱分類器m+=argminm(en,m)作為當前選擇的結(jié)果

(3)

en=en,m+

(4)

1.2 算法應(yīng)用在視頻目標跟蹤中的不足

由算法的流程描述可知，一個強分類器的形成是由若干的弱分類器組成的。從單個視頻幀中的訓(xùn)練樣本來看，在訓(xùn)練弱分類的過程中，前n個弱分類器訓(xùn)練后得到的樣本權(quán)重值，將影響到第n+1個弱分類器的誤差以及受誤差影響的弱分類器權(quán)重和樣本權(quán)重的更新值，當視頻目標快速移動的時候，可能出現(xiàn)前n個弱分類器更新完畢，但是后面的弱分類器沒有得到訓(xùn)練，也就是目標移動的速度超過了弱分類器的學(xué)習(xí)速度，那么就會造成特征學(xué)習(xí)不充分，形成的強分類器就不會有強的區(qū)分能力。從多個連續(xù)的視頻幀來看，對于快速移動的目標，由于目標移動太快，使得當前幀學(xué)習(xí)到的特征來不及更新到下一幀，那么下一幀學(xué)習(xí)到的特征有可能是錯誤的特征，在后續(xù)的跟蹤中，錯誤特征得到累積，最終就會造成跟蹤的漂移，并且該漂移是不可逆的。

2 改進的On-line Boosting算法

2.1 改進算法流程

改進的On-line Boosting 算法用于視頻跟蹤中，其創(chuàng)新點體現(xiàn)在原有的算法基礎(chǔ)上，增加跟蹤漂移的判斷，并將Surf 算法融入到On-line Boosting中，用于正確定位目標，恢復(fù)漂移，實現(xiàn)實時而準確的跟蹤。通過增加閾值判斷，對算法中的分類器學(xué)習(xí)情況進行判斷，學(xué)習(xí)特征值高于指定閾值，則繼續(xù)跟蹤學(xué)習(xí)，低于指定閾值的則用Surf算法進行二次定位。Surf算法具有尺度和旋轉(zhuǎn)不變的檢測器和特征描述子，最大的優(yōu)點在于計算速度快，可實現(xiàn)實時匹配的效果，因此適于用在視頻目標跟蹤中用于實時對所跟蹤的目標進行匹配。

圖2 改進的算法框架

2.2 Surf算法融于On-line Boosting目標跟蹤算法

Surf算法用于目標跟蹤是一種基于特征的圖像匹配算法，由Herbert Bay等人在2006年提出[10]，其算法原理分為：特征點提取、構(gòu)建特征點描述子以及特征點匹配三部分，其與基于On-line Boosting 視頻目標算法的融合體現(xiàn)在輔助原算法在跟蹤漂移時快速有效地進行模板特征匹配，從而正確地定位到跟蹤目標。在跟蹤漂移時，Surf算法的流程如下。

1)對匹配模板和跟蹤錯誤幀進行特征點提取

在Surf算法中，特征點是指比周圍領(lǐng)域的點更暗或者更亮的點，采用近似Hessian矩陣的行列式值的局部最大值來定位該特征點。高斯濾波后的Hessian矩陣表達式為

(5)

(6)

det(H)=LXX·LYY-(LXY)2

(7)式中：X表示像素點的位置；δ表示尺度；L(X,δ)是圖像在不同尺度下的表示；LXX是高斯模板與圖像的卷積；g(δ)為高斯濾波器；δ是高斯濾波器的方差；det(H)表示該點的特征值。

通過以上的步驟可以分別得到匹配模板和跟蹤錯誤幀的Hessian行列式圖，接下去需要構(gòu)造圖像金字塔，這一步是通過改變?yōu)V波器模板的尺寸大小和高斯模糊尺寸大小來構(gòu)造不同的圖片層的，同一層中的圖片用到的高斯模板尺度也不同。算法允許尺度空間多層圖像同時被處理，不需對圖像進行二次抽樣，從而提高算法性能。

利用非極大值抑制初步確定特征點，方法是通過將金字塔圖像中的每一個像素點與其三維領(lǐng)域的26個點大小比較，如果該像素點為最大值，則初步定為特征點。通過3維線性差值找到亞像素的特征點，實現(xiàn)精準定位特征點，最后去掉一些小于一定閾值的點。

2)構(gòu)建匹配模板和跟蹤錯誤幀特征點描述子

以特征點為中心，在半徑為r領(lǐng)域內(nèi)計算Harr小波特征。在一個60°扇形內(nèi)統(tǒng)計所有點的水平Haar小波特征和垂直Haar小波特征總和。每個扇形得到一個值，然后以一定間隔旋轉(zhuǎn)60°扇形，選出最大值那個扇形的方向作為該特征點的主方向，以達到旋轉(zhuǎn)不變性，選定主方向后，在特征點周圍取一個帶方向的正方形框，方向為特征點的主方向，將該框分為16個子區(qū)域，統(tǒng)計每個子區(qū)域相對于主方向的水平方向和垂直方向的Haar小波特征，計算該Haar小波特征水平方向值之和，水平方向絕對值之和，垂直方向之和，垂直方向絕對值之和，這樣每個小區(qū)域就有4個值，所以每個特征點就是 16×4=64維的向量。

該過程的示意圖如圖3所示。

圖3 構(gòu)建特征點描述子

3)對匹配模板和跟蹤錯誤幀進行特征點匹配

當匹配模板和跟蹤錯誤幀進行特征點匹配時，是計算跟蹤錯誤幀中每個特征點與匹配模板中的所有特征點的歐氏距離，形成一個距離集合，比較距離集合中的最小歐氏距離和次小歐氏距離的比值，如果小于設(shè)定的閾值，則認為該特征點是與最小歐氏距離點匹配，否則該點沒有匹配點，所設(shè)定的閾值越小，匹配就越穩(wěn)定。

3 實驗結(jié)果及分析

本次實驗在Microsoft Visual Studio 2010 的軟件環(huán)境下，針對快速移動的視頻目標，將改進后的Surf-Boosting與Grabner等人在文獻[9]提出的基于運動特點的目標跟蹤算法進行比較，在跟蹤過程對跟蹤結(jié)果取置信值0.5，對Surf算法的匹配結(jié)果取閾值0.2。針對快速移動的目標，在第一幀中框出跟蹤目標，實驗結(jié)果如下。

對于快速移動的目標，基于運動特點的實驗結(jié)果如圖4所示。

圖4 基于運動特點的實驗結(jié)果

對于快速移動的目標，改進后的Surf-Boosting算法實驗結(jié)果如圖5所示。

圖5 改進后的Surf-Boosting算法實驗結(jié)果

從實驗結(jié)果可以看出，原有算法對于快速移動的目標的跟蹤效果不佳，會出現(xiàn)跟蹤的漂移，并且這種漂移是不可逆的，從第139幀后，分類器更新錯誤，這種錯誤會直接傳遞到后續(xù)的跟蹤中，直接影響到后續(xù)的跟蹤結(jié)果。通過改進后的算法，由于結(jié)合了魯棒的Surf 算法，并增加了閾值判斷，對于快速移動的目標有了較好的魯棒性，能很好地適應(yīng)跟蹤過程中目標的快速變化。在所檢測的2 000幀視頻幀中能夠正確檢測到1 960張，正確率達到98%。

4 小結(jié)

本文所提出的一種新的改進On-line Boosting算法，是一種普遍的視頻目標跟蹤算法，在保證原有算法的優(yōu)點的同時，彌補了原有算法在快速移動目標跟蹤上的不足，減少了原有算法跟蹤漂移的可能，更加適應(yīng)實際生活中的各種場景，具有廣闊的應(yīng)用前景。

[1] AVIDAN S. Ensemble tracking[C]//Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]：IEEE Press，2005：494-501.

[2] VACCHETTI L，LEPETIT V，F(xiàn)UA P. Stable real-time 3D tracking using online and offline information[J].IEEE Trans. Pattern Analysis and Machine Intelligence，2004，26(10)，1385-1391.

[3] MORENCY L P，WHITEHILL J，MOVELLAN J. Generalized adaptive view based appearance model：integrated framework for monocular head poseestimation[C]//Proc. 8th IEEE International Conference on Automatic Face and Gesture Recognition(FG 2008).[S.l.]：IEEE Press，2008：1-8.

[4] WANG Q，ZHANG W，TANG X，et al. Real-time Bayesian 3-d pose tracking[J].IEEE Trans. Circuits and Systems for Video Technology，2006，16(12)：1533-1541.

[5] JEPSON A D，F(xiàn)LEET D J，El-MARAGHI T F. Robust online appearancemodels for visual tracking[J]. IEEE Trans. Pattern Analysis and Machine Intelligence，2003，25(10)：1296-1311.

[6] SUNG J，KIM D. Adaptive active appearance model with incremental learning[J].Pattern Recogn. Lett.，2009，30(4)：359-367 .

[7] DAVID R，LIM J，LIN R S，et al. Incremental learning for robust visual tracking[J].International Journal of Computer Vision， 2008，77(1)：125-141.

[8] HELMUT G，BISCHOF H. On-line boosting and vision[C]//Proc. Computer Vision and Pattern Recognition.[S.l]：IEEE Press，2006：260-267.

[9] STALDER S，GRABNER H，VANGOOL L. Dynamic objectness for adaptive tracking[C]//Proc. Asian Conference on Computer Vision.[S.l]：IEEE Press，2012：43-56.

[10]HERBERT B，ANDREAS E，TUYTELAARS T，et al. Speeded-up robust features(SURF)[J]. Computer Vision and Image Understanding，2008，110(3)：349-356.

責任編輯：時 雯

Video Target Tracking Based on Impoved On-line Boosting Algorithm

CAI Mingqiong，GUO Tailiang，YAO Jianmin

(NationalandLocalJointEngineeringLaboratoryofFlatPanelDisplayTechnology，F(xiàn)uzhouUniversity，F(xiàn)uzhou350116，China)

In view of that the present way of On-line Learning video target tracking algorithm based on the On-line Boosting algorithm would cause tracking drift easily， the thesis put forward a kind of new improved algorithm called Surf-Boosting which combine Surf algorithm to the On-line Boosting algorithm in video target tracking .Compared with the original On-line Boosting algorithm，the improved algorithm add the judgment of tracking drift and can locate target by using Surf algorithm when tracking drift.After that the target located by surf algorithm can be learned as a positive sample in follow-up tracking. The experimental result whose accuracy is 98% show that the improved robust method can restrain the tracking drift and realize good tracking on fast moving target effectively.

On-line Boosting；Surf；fast moving；target tracking

國家“863”重大專項(2013AA030601)；福建省自然科學(xué)基金項目(2011J01347)

TP227

A

10.16280/j.videoe.2015.16.018

2014-11-23

【本文獻信息】蔡明瓊，郭太良，姚劍敏.基于改進On-line Boosting算法的視頻目標跟蹤[J].電視技術(shù),2015，39(16).