利用全局約束霍夫模型的目標跟蹤算法

賀文驊,劉志鏡,屈鑒銘

(西安電子科技大學計算機學院, 710071, 西安)

利用全局約束霍夫模型的目標跟蹤算法

賀文驊,劉志鏡,屈鑒銘

(西安電子科技大學計算機學院, 710071, 西安)

針對目標跟蹤中局部特征模型容易受到形變和誤匹配等影響造成漂移的問題,提出了一種利用全局特征對霍夫局部模型進行約束的目標跟蹤算法。該算法通過檢測和提取目標的局部特征,構(gòu)建了一個基于局部特征投票的概率模型。該模型以局部特征為基本元素,利用廣義霍夫變換對局部特征的穩(wěn)定性進行加權(quán),通過對局部特征的增減維護實現(xiàn)模型的在線更新;將穩(wěn)定的局部特征作為前景,計算目標全局顏色特征的概率分布,實現(xiàn)簡單的柔性目標分割,用于調(diào)整局部特征模型并對跟蹤進行優(yōu)化,從而減少形變等問題產(chǎn)生的跟蹤誤差;局部特征和全局特征相互約束補充,共同完成在線自適應更新。實驗結(jié)果表明,該算法有效提高了局部特征模型的準確率和穩(wěn)定性,對部分遮擋和復雜形變的情況表現(xiàn)良好。

目標跟蹤;局部特征;霍夫變換;目標分割

視頻序列中的目標跟蹤是計算機視覺領域一個長期的研究熱點,被廣泛地應用于人機交互、安防監(jiān)控、模式識別等領域,同時也是行為分析和場景理解等進一步研究的關(guān)鍵基礎。跟蹤過程中會遇到各種各樣的問題,例如目標自身發(fā)生的尺度變化、旋轉(zhuǎn)、遮擋以及攝像頭的運動等。建立可靠的特征模型對目標進行描述,同時采用合理有效的在線學習策略對目標模型進行更新是保證跟蹤穩(wěn)定性和準確性的關(guān)鍵。經(jīng)典的在線目標跟蹤算法[1-3]將跟蹤結(jié)果作為訓練樣本,對目標模型進行在線更新,使其能夠較好地適應目標的外觀變化。這些方法以目標整體作為模型,當目標發(fā)生劇烈形變或者被遮擋時,整體模型難以處理,更新過程會引入大量的背景噪聲,最終導致跟蹤失敗。

一些學者提出了使用較低層次特征來建立目標模型的方法。文獻[4-5]采用像素信息作為特征,通過霍夫投票估計目標的位置,最后通過前后景分割獲取目標的最終狀態(tài)。這兩種方法主要采用了像素的顏色特征,對于非剛性目標的跟蹤和部分遮擋有較好的表現(xiàn),但在背景復雜或像素特征不明顯時不夠穩(wěn)定。仿射不變的局部特征[6-7]的相繼提出被廣泛應用于圖像配準以及目標的檢測和跟蹤[8-11]。文獻[8]提出利用局部特征點霍夫投票實現(xiàn)目標跟蹤來處理遮擋。文獻[9]利用運動顯著性對特征點進行約束,提高了跟蹤的穩(wěn)定性。文獻[10-11]采用了尺度不變特征轉(zhuǎn)換(scale-invariant feature transform, SIFT)特征來實現(xiàn)跟蹤。文獻[10]通過對特征點的大量仿射變換采樣和增量式主成分分析建立局部特征模型集合,提高了特征點的匹配準確率,但是這些方法沒有考慮目標結(jié)構(gòu)形變的問題,而且運算量較大。文獻[12]提出利用超像素分割對圖像進行處理,以超像素為單位通過聚類對顏色進行統(tǒng)計,生成判別式模型。該方法由于僅采用了顏色特征,因此對于形變的魯棒性非常強,但也容易受到近似顏色和遮擋的干擾,而且反復的聚類運算也大大增加了運算量。

本文提出一種綜合考慮前后景分割和局部特征投票的在線跟蹤算法。算法檢測和提取目標的局部特征點,并結(jié)合局部特征與目標的相對關(guān)系構(gòu)建基于局部特征的目標模型。利用廣義霍夫變換作為投票機制,通過局部特征的投票估計出目標的中心位置,同時獲得每個局部特征的穩(wěn)定性權(quán)值。利用全局顏色特征計算前景和背景的概率分布,優(yōu)化跟蹤結(jié)果并對局部特征進行約束。局部特征投票和全局概率分布在跟蹤上相互補充,在更新過程中相互約束,對于目標的嚴重形變和部分遮擋有很強的適應性。

1 算法介紹

設t時刻目標的狀態(tài)由其位置坐標x和區(qū)域R表示,記作Xt=(xt,Rt)。設t時刻之前觀測狀態(tài)為Z1:t,由貝葉斯概率理論得到目標狀態(tài)的后驗概率為

p(Xt|Z1:t)=p(Zt|Xt)·

(1)

式中:p(Zt|Xt)是目標的觀測概率模型;p(Xt|Xt-1)是運動概率模型。本文的觀測模型由兩部分組成,基于局部特征的霍夫投票模型和基于全局特征的顏色概率模型。對于新一幀的圖像,檢測目標所在區(qū)域的局部特征,并與局部特征模型進行匹配。利用匹配到的局部特征對目標的中心進行投票,所有投票結(jié)果的線性加權(quán)作為目標當前位置的概率,投票空間的反向投影作為局部特征的穩(wěn)定性權(quán)值。同時,利用全局顏色特征計算每個像素屬于前景目標的概率。對目標區(qū)域內(nèi)所有像素屬于前景的概率求和,即為目標的全局顏色特征概率。融合兩種模型得出的概率分布作為最終的觀測概率模型,結(jié)合運動概率模型,計算出目標狀態(tài)的后驗概率,再通過最大化后驗概率估計(maximum a posteriori, MAP)求出目標的當前位置。更新過程中,以跟蹤結(jié)果為訓練樣本對兩種模型進行更新。通過局部特征區(qū)域的顏色統(tǒng)計對顏色概率模型進行更新,而顏色概率模型又反過來對局部特征集合的更新和維護進行約束。算法的基本流程如圖1所示。

圖1 算法流程示意圖

2 目標模型

2.1 霍夫投票

霍夫投票是利用局部特征對目標的中心進行投票,通過尋找投票空間的最大值,估計目標中心的位置。通過投票空間的反向投影計算局部特征的穩(wěn)定性作為權(quán)值。采用類似文獻[9]的方法構(gòu)建局部特征模版的集合S作為霍夫投票的模型

式中:di是特征描述子;wi是穩(wěn)定性權(quán)值;ri=(dxi,dyi)是局部特征相對于目標中心的位移;ci是局部特征的類型,表示其屬于前景的概率。對于新一幀的圖像,檢測目標及其附近區(qū)域的局部特征。本文采用Harris角點和SIFT特征來檢測特征點,采用SIFT特征描述檢測到的特征點。設當前幀檢測到的局部特征集合為F={fj},將F與模版集合S中的局部特征進行匹配,利用匹配成功的局部特征對目標中心進行投票。局部特征的匹配通過計算特征相似度和特征點跟蹤兩種方式來實現(xiàn)匹配。計算兩個局部特征SIFT特征描述子的距離,距離最小并且小于設定閾值則認為兩者匹配。對于未能匹配的局部特征,使用FB算法[13]對相鄰幀的特征點進行跟蹤,得到的結(jié)果也作為匹配。

設si和fj匹配成功,記作mi,j,l(·)表示局部特征在當前幀的坐標,則該匹配對跟蹤目標中心的投票為l(mi,j)=l(fj)+ri。為了平滑輸出,我們用高斯函數(shù)近似表示采樣X在mi,j投票下的概率

p(X|mi,j)=exp(-‖x-l(mi,j)‖2/2σ2)

(2)

式中:σ是方差,用于控制生成的置信度圖像的平滑程度;x是采樣的中心坐標;‖x-l(mi,j)‖2是采樣中心與投票位置的2范數(shù)距離。定義t時刻檢測到的局部特征F與霍夫投票模型S的所有成功匹配為集合M,則最終的投票結(jié)果為

?Vi,j=wip(X|mi,j),mi,j∈M

(3)

式中:ε是特征類型權(quán)重,用來調(diào)整目標特征和背景特征投票的重要性比例,突出屬于目標特征點的投票,減少背景的干擾。

2.2 全局特征約束

目標發(fā)生持續(xù)形變時,特征點的檢測和匹配都會受到影響,并且會改變特征點與目標的相對關(guān)系,導致投票出現(xiàn)偏差。對于細節(jié)特征不明顯的目標,局部特征也難以檢測和匹配。采用全局顏色特征計算前后景的概率分布,對投票結(jié)果進行優(yōu)化,可以避免因為形變以及有效局部特征過少而產(chǎn)生漂移,降低背景局部特征對投票的干擾。

在HSV顏色空間下,分別統(tǒng)計前景的顏色直方圖hf和背景的顏色直方圖hb。設bin(x)為像素x在顏色直方圖內(nèi)的區(qū)間索引,則該像素對應前景和背景直方圖的值分別為hf(bin(x))、hb(bin(x))。計算像素x屬于前景目標的概率

(4)

式中:δ是懲罰因子常數(shù),作為區(qū)分前后景概率的閾值。當概率為正時,認為像素x屬于前景,反之則屬于背景。對于任意區(qū)域R,其屬于前景目標的概率為其包含所有像素前景概率的均值

(5)

前景和背景顏色直方圖在跟蹤過程結(jié)束后進行在線更新。以所有屬于前景的局部特征的矩形塊所覆蓋的區(qū)域為前景,統(tǒng)計當前幀的前景顏色直方圖hf。以目標矩形周圍的區(qū)域為背景,統(tǒng)計當前幀的背景顏色直方圖hb。通過自回歸的方式對全局前景和背景顏色直方圖進行更新

(6)

式中:ρh是更新速率常數(shù)。顏色概率通過對局部特征區(qū)域的統(tǒng)計進行計算,同時對局部特征進行約束。利用式(5)計算每個局部特征屬于前景目標的概率,從而調(diào)整局部特征的投票貢獻。

3 目標跟蹤

在新一幀圖像中,以上一幀目標位置為中心,設定搜尋窗口進行特征點檢測,利用霍夫投票模型求出目標中心的概率分布,并將投票空間最大概率所在位置的坐標記作xmax,同時利用全局顏色概率模型求出窗口內(nèi)所有像素屬于目標的概率。對于任一采樣X={x,R},計算其似然概率為

(7)

式中:α是線性加權(quán)系數(shù),用于平衡兩種概率模型的關(guān)系。當投票空間上xmax的概率小于設定閾值時,認為投票結(jié)果無效,令α=1。由式(1)根據(jù)最大化后驗概率估計目標當前的位置

(8)

圖2是算法關(guān)鍵步驟的示意圖。圖2a是投票空間得出最大概率的位置;圖2b是全局顏色特征概率分布;圖2c是在投票概率的基礎上根據(jù)顏色概率分布進行優(yōu)化,虛線矩形是投票得出的位置,實線矩形是優(yōu)化后的位置;圖2d是根據(jù)兩種模型的概率分布求出的目標當前位置。

(a)投票結(jié)果 (b)顏色概率分布

(c)位置優(yōu)化 (d)跟蹤結(jié)果

4 模型更新

對于匹配成功的局部特征模版,利用其對應的局部特征信息進行更新,更新方式為

(9)

(10)

(11)

式中:ρ是特征模型的更新速率;dj是當前幀匹配的局部特征的SIFT特征描述子;x*是當前幀跟蹤結(jié)果目標中心的坐標;pc(fi)是特征fi屬于前景目標的概率。由于顏色概率模型對投票結(jié)果得出的目標位置進行了改變,不能直接使用投票空間的反向投影更新局部特征的權(quán)值,需要根據(jù)最終跟蹤結(jié)果的目標中心位置,計算局部特征當前幀的穩(wěn)定性權(quán)值wi,再進行更新,更新方式同式(9)。

wi=exp(-‖l(mi,j)-x*‖2/2σ2)

(12)

對于未能成功匹配的局部特征,將其添加到投票模型的模版集合。為了提高運算效率,保證霍夫投票模型中局部特征模板的有效性,一段時間內(nèi)連續(xù)不被匹配的局部特征模板會被移除。同時,為局部特征模板的數(shù)量設置上限,當模型中的局部特征模板的數(shù)量超過設定的上限閾值時,移除其中權(quán)值較低的模板。

5 實驗結(jié)果

采用C++和OpenCV編寫程序?qū)Ρ疚乃惴ㄟM行了測試實驗。實驗在處理器為酷睿2.93 GHz的個人計算機上執(zhí)行,平均速度可達到13幀/s。實驗采用了9個常用的公共視頻對算法進行了測試,測試視頻來自于文獻[14],其內(nèi)容包括了光照變化、尺度變化、旋轉(zhuǎn)、形變和遮擋等情況。實驗結(jié)果與經(jīng)典的跟蹤算法MIL(multiple instances learning)[1]、TLD(tracking-learning-detection)[3]、SPT(super pixel tracking)[12]進行了對比,圖3給出了實驗結(jié)果的部分截圖。采用正確跟蹤的幀數(shù)和平均中心誤差對跟蹤結(jié)果進行評價,評價標準的具體計算方式同文獻[12]。表1、表2分別給出了兩種評價標準下各算法的對比結(jié)果,粗體表示最優(yōu)的兩項。實驗結(jié)果表明,本文算法在選取的測試視頻上表現(xiàn)良好,能夠穩(wěn)定準確地完成跟蹤。

(a)basketball (b)david_out_door

(c)woman (d)lemming

(e)faceocc (f)david_in_door

在視頻lemming和liquor中,目標經(jīng)歷了大量的尺度變化、遮擋和旋轉(zhuǎn)形變。MIL在liquor中由于尺度變化和遮擋同時發(fā)生導致目標整體變化過大,從而丟失了目標。本文算法利用SIFT特征的尺度旋轉(zhuǎn)不變性,結(jié)合顏色特征的約束,有效地適應了尺度、旋轉(zhuǎn)和遮擋的復合變化。TLD算法由于錯誤的尺度變換導致跟蹤效果不理想。

視頻basketball和david_out_door是兩個相對復雜的場景。目標人物在跟蹤過程中經(jīng)歷了遮擋、快速移動以及轉(zhuǎn)身等嚴重的非剛性形變,這些問題使得局部特征與目標的相對關(guān)系發(fā)生了持續(xù)變化,也造成特征點大量替換,難以檢測和匹配。本文算法利用全局顏色特征分布對投票結(jié)果進行了約束修正,成功完成了對目標的跟蹤。TLD算法由于目標的快速變化和相互遮擋,在這兩個視頻中表現(xiàn)不佳。

表1 跟蹤結(jié)果成功幀數(shù)

表2 跟蹤結(jié)果平均中心誤差

在視頻faceocc中,目標發(fā)生了嚴重的遮擋,并且維持了較長時間。以整體為模型的TLD和MIL算法在目標被遮擋后,在線更新時將遮擋物也視為目標的一部分,導致了跟蹤誤差的產(chǎn)生。TLD算法產(chǎn)生了向上的輕微漂移,MIL算法產(chǎn)生了向下的漂移。SPT算法也在遮擋最嚴重時完全丟失了目標。本文算法通過未被遮擋部分的局部特征對目標中心投票,獲得了更小的誤差。

在視頻woman和tiger中,目標經(jīng)歷了多次遮擋。不同的是,woman中遮擋方式相對簡單,但目標在89幀附近發(fā)生了大幅形變,這使得MIL和TLD都丟失了目標。而在tiger視頻中,遮擋方式相對復雜,導致了顏色分布相對復雜,使得SPT表現(xiàn)不佳。本文算法采用顏色特征分布和局部特征投票相互約束,在這兩個視頻中都取得了很好的表現(xiàn)。

在視頻david和david_in_door中,目標經(jīng)歷了光照變化、尺度變化和旋轉(zhuǎn)。本文算法通過霍夫變換在更新過程中對局部特征權(quán)值的調(diào)整,有效適應了目標的變化,取得了良好的跟蹤效果。SPT算法因為只采用了顏色特征,在背景近似顏色的干擾下丟失了目標。

6 結(jié) 論

針對視頻序列目標跟蹤過程中的形變和遮擋問題,提出了一種全局顏色特征概率約束下局部特征霍夫投票的目標跟蹤算法。算法通過分析局部特征及其與目標的相對關(guān)系,構(gòu)建了一個基于局部特征的霍夫投票模型。利用全局顏色特征計算前后景的概率分布,優(yōu)化投票結(jié)果并對局部特征進行約束。由于采用了局部特征投票和全局概率分布相結(jié)合的方式,算法能夠有效地處理部分遮擋的情況,對目標形變有較強魯棒性,但是本文算法依賴于目標局部特征的豐富和穩(wěn)定,且更側(cè)重于短期連續(xù)的跟蹤,如何處理目標局部特征不明顯以及長期跟蹤中目標丟失找回的問題,是下一步的研究方向。

[1] BABENKO B, YANG M H, BELONGIE S. Visual tracking with online multiple instances learning [C]∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. Piscataway, NJ, USA: IEEE, 2009: 983-990.

[2] ROSS D A, LIM J, LIN R S, et al. Incremental learning for robust visual tracking [J]. International Journal of Computer Vision, 2008, 77(1/2/3): 125-141.

[3] KALAL Z, MIKOLAJCZYK K, MATAS J. Tracking learning detection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1409-1422.

[4] GODEC M, ROTH P M, BISCHOF H. Hough-based tracking of non-rigid objects [J]. Computer Vision and Image Understanding, 2013, 117(10): 1245-1256.

[5] DUFFNER S, GARCIA C. Pixeltrack: a fast adaptive algorithm for tracking non-rigid objects [C]∥Proceedings of the IEEE International Conference on Computer Vision. Los Alamitos, CA, USA: IEEE Computer Society, 2013: 2480-2487.

[6] LOWE D G. Distinctive image features from scale invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[7] BAY H, TUYTELAARS T, VAN G L. Speeded up robust features [J]. Computer Vision and Image Understanding, 2008, 110(3): 346-359.

[8] GRABNER H, MATAS J, VAN GOOL L, et al. Tracking the invisible: learning where the object might be [C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2010: 1285-1292.

[9] YI K M, JEONG H, HEO B. Initialization-insensitive visual tracking through voting with salient local features [C]∥Proceedings of the IEEE International Conference on Computer Vision. Los Alamitos, CA, USA: IEEE Computer Society, 2013: 2912-2919.

[10]GUO Yanwen, CHEN Ye, TANG Feng, et al. Object tracking using learned feature manifolds [J]. Computer Vision and Image Understanding, 2014, 118: 128-139.

[11]藺海峰, 馬宇峰, 宋濤. 基于SIFT特征目標跟蹤算法研究 [J]. 自動化學報, 2010, 36(8): 1204-1208. LIN Haifeng, MA Yufeng, SONG Tao. Research on object tracking algorithm based on SIFT [J]. Acta Automatica Sinica, 2010, 36(8): 1204-1208.

[12]WANG Shu, LU Huchuan, YANG Fan, et al. Superpixel tracking [C]∥Proceedings of the International Conference on Computer Vision. Piscataway, NJ, USA: IEEE, 2011: 1323-1330.

[13]KALAL Z, MIKOLAJCZYK K, MATAS J. Forward-backward error: automatic detection of tracking failures [C]∥Proceedings of the International Conference on Pattern Recognition. Piscataway, NJ, USA: IEEE, 2010: 2756-2759.

[14]WU Yi, LIM J, YANG M H. Online object tracking: a benchmark [C]∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos, CA, USA: IEEE Computer Society, 2013: 2411-2418.

(編輯 武紅江)

AVisualTrackingMethodBasedonGlobalConstrainedHoughModel

HE Wenhua,LIU Zhijing,QU Jianming

(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)

A visual tracking method is proposed to solve the problem that the local feature model is prone to be influenced by the deformation and feature mismatch and leads to drifting. The method constrains the Hough local model by using global features. The Hough model is constructed with a set of local features of an object and estimates the stability of each local feature based on the generalized Hough Transform. Then, the model is updated flexibly through modifying the local feature set to adapt to the object appearance variations. Color cues of the local features are used to calculate the global color probability of being foreground or background. Then the global probability is used to adjust the tracking results and constrains the local features of the model in return. Experimental results on several public video sequences show the robustness of the proposed method in tracking objects with deformation and partial occlusion.

visual tracking; local feature; Hough transform; segmentation

2014-06-06。

賀文驊(1986—),男,博士生;劉志鏡(通信作者),男,教授,博士生導師。

國家自然科學基金資助項目(61173091)。

時間:2014-11-27

10.7652/xjtuxb201412011

TP392

:A

:0253-987X(2014)12-0069-05

網(wǎng)絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20141127.1818.003.html