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

賀文驊,劉志鏡,屈鑒銘

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

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

賀文驊,劉志鏡,屈鑒銘

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

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

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

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

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

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

1 算法介紹

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

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

(1)

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

圖1 算法流程示意圖

2 目標模型

2.1 霍夫投票

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

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

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

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

(2)

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

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

(3)

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

2.2 全局特征約束

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

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

(4)

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

(5)

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

(6)

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

3 目標跟蹤

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

(7)

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

(8)

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

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

(c)位置優化 (d)跟蹤結果

4 模型更新

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

(9)

(10)

(11)

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

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

(12)

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

5 實驗結果

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

(a)basketball (b)david_out_door

(c)woman (d)lemming

(e)faceocc (f)david_in_door

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

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

表1 跟蹤結果成功幀數

表2 跟蹤結果平均中心誤差

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

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

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

6 結 論

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

[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

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