基于改進(jìn)On-line Boosting算法的視頻目標(biāo)跟蹤

蔡明瓊，郭太良，姚劍敏

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

基于改進(jìn)On-line Boosting算法的視頻目標(biāo)跟蹤

蔡明瓊，郭太良，姚劍敏

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

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

On-line Boosting；Surf；快速移動；目標(biāo)跟蹤

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

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

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

1 基于On-line Boosting的視頻目標(biāo)跟蹤及其不足

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

1.1 算法的理論介紹

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

(1)

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

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

(2)

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

(3)

en=en,m+

(4)

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

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

2 改進(jìn)的On-line Boosting算法

2.1 改進(jìn)算法流程

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

圖2 改進(jìn)的算法框架

2.2 Surf算法融于On-line Boosting目標(biāo)跟蹤算法

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

1)對匹配模板和跟蹤錯誤幀進(jìn)行特征點(diǎn)提取

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

(5)

(6)

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

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

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

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

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

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

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

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

3)對匹配模板和跟蹤錯誤幀進(jìn)行特征點(diǎn)匹配

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

3 實(shí)驗(yàn)結(jié)果及分析

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

對于快速移動的目標(biāo)，基于運(yùn)動特點(diǎn)的實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 基于運(yùn)動特點(diǎn)的實(shí)驗(yàn)結(jié)果

對于快速移動的目標(biāo)，改進(jìn)后的Surf-Boosting算法實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 改進(jìn)后的Surf-Boosting算法實(shí)驗(yàn)結(jié)果

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

4 小結(jié)

本文所提出的一種新的改進(jìn)On-line Boosting算法，是一種普遍的視頻目標(biāo)跟蹤算法，在保證原有算法的優(yōu)點(diǎn)的同時，彌補(bǔ)了原有算法在快速移動目標(biāo)跟蹤上的不足，減少了原有算法跟蹤漂移的可能，更加適應(yīng)實(shí)際生活中的各種場景，具有廣闊的應(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.

責(zé)任編輯：時 雯

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”重大專項(xiàng)(2013AA030601)；福建省自然科學(xué)基金項(xiàng)目(2011J01347)

TP227

A

10.16280/j.videoe.2015.16.018

2014-11-23

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