融合背景信息的分塊稀疏表示跟蹤算法*

侯躍恩 李偉光 容愛瓊 葉國強

(華南理工大學機械與汽車工程學院，廣東廣州510640)

視頻目標跟蹤在視覺伺服、視頻監控和人機交互等領域得到了廣泛的應用，許多學者在目標跟蹤領域做了大量的研究，但仍有很多問題沒有得到解決［1］，這些問題主要集中在光照條件劇烈變化、目標形態變化和目標被遮擋的情況下的跟蹤準確性、魯棒性和實時性上．近年來，一種被稱為“稀疏表示”的外觀建模技術在多擾動下目標匹配過程中顯示出了強魯棒性．文獻［2］中應用該技術在灰度圖像中對現實世界的物體進行識別，獲得了極高的識別率．文獻［3-5］中將人臉識別看成是稀疏表示的過程，獲得了良好的識別效果．文獻［6］中將稀疏表示方法用于圖像降噪，取得了理想的效果．為解決復雜條件下跟蹤魯棒性的問題，文獻［7-8］中將稀疏表示引入目標跟蹤領域，采用?1最小化的方法線性表示目標，并用瑣碎模板的方法解決目標被遮擋的問題，但該方法存在計算量大和跟蹤實時性差的問題．文獻［9］中在解稀疏矩陣時采用了分塊正交匹配追蹤(BOMP)算法，提高了算法的運算速度，但由于沒有考慮背景信息，在目標光照條件和形態劇烈變化的時候會出現漂移的現象．文獻［10］中采用新方法使稀疏表示在粒子濾波框架中只需要進行一次稀疏計算，大大減少了算法計算量，但該方法模板單一，失去了稀疏表示的魯棒性．為了提高跟蹤的魯棒性，文獻［11］中采用多種特征對目標進行稀疏表示，但該方法沒有對特征融合深入分析，只是簡單地融合各種特征，同時還存在實時性不高的問題．文獻［12］中采用外觀模型和稀疏表示的方法對目標進行跟蹤，取得了良好的跟蹤效果，但沒有對跟蹤的幀頻展開論述，同樣存在實時性不強的問題．文獻［13］中采用SIFT特征以及 ?1和 ?2最小化提高了跟蹤的魯棒性，卻帶來了額外的計算開銷．

針對上述問題，文中提出一種新的基于稀疏表示的目標跟蹤方法，該方法在提高跟蹤魯棒性的基礎上保證了跟蹤的速度．

1 算法研究

1．1 粒子篩選方法

在粒子濾波框架下，大部分粒子與目標的相似度較低，這些粒子對確定目標的貢獻基本為零，它們可以用快速的計算予以區分．鑒于此，提出了一種快速計算的方法來篩選這些粒子，以減少算法的計算量，這里稱為“方差粒子篩選法”．

設 Y={y1，y2，…，yk}∈m×n為粒子濾波中的候選粒子集，其中m為粒子特征的維數，n為粒子數．?Y∈m為標準模板．將Y的每個列向量與?Y進行歸一化并相除得到 U={u1，u2，…，un}∈m×n，其中中每個列向量包含了候選目標與標準模板的相似度信息，粒子篩選的目的就是根據U中的信息尋找與標準模板相似度高的粒子參與后面的運算．現以ui為例，如果候選目標與模板相似度高，則ui內各元素數值波動小，反之，ui內各元素數值波動大．可以用ui內各元素的波動大小來判斷候選目標與模板的相似度，這里采用方差來定量計算各元素波動的大?。虼?，模板篩選工作的重點就是尋找矩陣U中方差大的列向量．在圖像被遮擋或噪聲比較大的情況下，與模板相似度高的粒子可能會出現方差大的現象．為了解決這個問題，排除ui中部分與其均值差值較大的元素，這些元素可能是由遮擋或噪聲導致，從而避免目標被排除的情況．至于?Y的選取，在初始幀由手動選擇獲得，在跟蹤過程中，由模板更新的方法獲得，關于模板更新將在1．4 節介紹．

1．2 目標與背景聯合稀疏表示算法

為了表述方便，這里先簡要介紹稀疏表示原理．假設有一模板字典T={t1，t2…tk}∈m×k，其中m 為每個模板的維數，k為模板的個數．模板字典如圖1所示．

圖1 模板字典Fig．1 Template dictionary

候選目標特征向量為y∈m，則y可以用模板字典T的各個列向量線性表示:

式中，α∈m，是目標的參數向量，ε是殘差．稀疏表示就是用盡量少的向量線性表示y，即

式中，‖·‖2、‖·‖0分別表示2范數和0范數，為殘差與稀疏性之間的調節系數．文獻［8］中指出，如果解α足夠稀疏，?0最小化問題可以等價于?1最小化問題，即

式中，‖·‖1為1范數．文獻［4］中用實驗證明了用?1或?2對系數α進行稀疏性約束可以得到同樣的識別結果，由此可以得到

用?2對系數α進行稀疏性約束的好處是可以使計算量大大減少．

由式(4)可導出:

設P=(TTT+I)-1TT，則P只與模板字典有關，在目標跟蹤過程中，每幀只需計算一次即可，可以減少運算量．

在目標跟蹤過程中，由于模板數k有限，文中提出一種將背景信息融入模板字典的方法，一方面可以組成較完備的模板字典，另一方面由于融入了背景的信息，可以使跟蹤更具魯棒性．設模板字典T={Ttar，Tbg}，其中 Ttar∈m×k1為目標模板部分，Tbg∈m×k2為背景模板部分，k1為目標模板個數，k2為背景模板個數，且k1+k2=k，模板字典示意見圖1．在?2范數稀疏約束的基礎上，

式中，αtar、αbg分別為目標模板和背景模板對應的系數．目標模板部分的殘差 εtar= ‖y-Ttarαtar‖2，背景部分的殘差 εbg=‖y-Tbgαbg‖2，如果候選目標 y與目標的相似度高，則εtar的值小而εbg的值大，反之則εtar的值大而εbg的值?。钅繕伺c背景殘差比e=εtar/εbg，則

式中，ei為k個粒子中第i個粒子的值，C為最終的確定目標的粒子序號．因此文中判斷候選目標與目標的相似度時不僅考慮到了目標模板的信息，還考慮到了背景模板的信息．

1．3 圖像分塊權重表示

為了解決跟蹤過程中目標被遮擋的問題，使用分塊稀疏表示的方法．該方法將目標圖像分塊，并給每個分塊賦予不同的權重，當目標某個分塊被遮擋或被噪聲干擾時，該分塊被賦予的權重低，對整體稀疏解的貢獻?。?/p>

文獻［5］中指出，在稀疏表示過程中，同一個候選目標的不同分塊有一定的相似性．如果只考慮目標模板，則它們具有相似的參數向量．當目標部分被遮擋或存在噪聲干擾時，該部分與其他部分的相似性將被打破，導致跟蹤任務的失?。疄榱吮苊膺@種情況，可以用下式規范其相似性:

式(8)中，L為圖像的塊數，α為所有分塊系數向量的均值向量，ωl為第l塊圖像的權重，式(9)為權重ω的約束．結合式(4)，權重分塊稀疏解的問題可以用以下方程表示:

式中，yl為候選目標第l個分塊，為調節系數，^Tl為目標模板中第l個分塊．可見該問題可以看成是求解αl和ωl使式(10)取得最小值，這里采用迭代的方法進行求解．

首先，假設所有分塊的權重已知，由式(10)可以得出［5］:

算法1:分塊權重迭代算法

3．根據式(11)更新稀疏解系數αl

4．根據式(12)更新權重系數ωl

5．end while

6．輸出 ωl，l=1，2，…，L

在獲得各個分塊的權重后，加入背景模板組成模板字典，式(5)和(7)可以改寫為

式(14)中，el為第l個分塊的目標與背景殘差比，εtar，l，εbg，l分別是第 l個分塊目標模板部分和背景模板部分殘差．式(15)中，ei，l為第i個粒子中第l個分塊的目標與背景殘差比．

1．4 模板更新

(1)標準模板?Y的更新

在文中算法中，?Y的更新對粒子篩選成敗有著重要的作用．

最直觀的方法是用每幀得到的目標對Y進行更新．如果使用這種方法，當跟蹤出現漂移的時候，會導致更新任務的失?。闹性谑褂妹繋繕藢?Y進行更新的基礎上，保留初始幀產生的標準模板Yinit．這樣就會有兩個標準模板Y和Yinit，再用1．1節的方法篩選粒子，得到與Y和Yinit相似性高的粒子．這樣做的好處是在某幀目標出現漂移的時候，Y篩選掉了與目標相似性高的粒子，Yinit則保留了與目標相似性高的粒子，使跟蹤能夠順利進行．

(2)模板字典T的更新

如2．2節所述，文中的模板字典(T={Ttar，Tbg})包括了兩方面的內容，分別是目標模板字典Ttar和背景模板字典Tbg．

目標模板字典Ttar的更新采用文獻［8］中的方法進行．背景模板字典Tbg則采用1．1節中與目標相似度最低的k2個粒子進行更新．

1．5 算法總結

除了上文討論過的幾個問題，算法采用仿射變換原理［14］將目標區域映射到一個固定維數的矩形框中，無論目標的大小如何變化，算法的計算量都將保持不變．在粒子濾波框架下利用粒子的速度和高斯分布噪聲更新粒子［14］．圖2為算法原理圖，跟蹤算法見算法2，算法的輸入為視頻和首幀的目標狀態，輸出為各幀目標的狀態．

1．6 計算量分析

文中算法主要通過兩部分的算法改進，減輕了計算負擔，分別是粒子篩選和?2最小化的稀疏解．粒子篩選算法通過快速計算可以排除掉大部分與目標相似度低的粒子，在解稀疏方程的過程中，?2最小化的計算量遠遠小于?1最小化．文中主要的計算開銷在于權重求解的迭代，現對其計算量進行分析．假設目標模板字典 Ttar={t1，t2，…，tk1}∈m×k1并將其分為 L 塊，Ttar={T1，T2，…，TL}，其中 Tl∈m/L×n為第l個分塊模板字典．在1．3節中的一次迭代過程中，計算Plyl需要的計算量為O(+(m/L)k1)，所以L個分塊的總計算量為O(+mn)．)總的計算量為 O(2Lk21)，所以每次迭代的總計算量為O(3Lk21+nm)．假設迭代次數為 ite，篩選后的粒子數為 N/6，則計算量為O(ite(3L+k1m)N/6)．

圖2 文中算法原理圖Fig．2 Principle of the proposed algorithm

2 試驗

文中算法在Matlab r2009b上編程實現，運行計算機的主頻為3．0GHz，內存為2 GB．為了說明文中算法的先進性，將文中算法與另外兩個先進的跟蹤算法進行比較，它們分別是 ?1算法［8］和 IVT算法［15］．這兩種算法都基于粒子濾波和仿射變換，目標狀態都有6個維度，分別是尺度倍數、長寬比、旋轉角度、扭曲角度、橫坐標值和縱坐標值，與文中算法具有可比性．文中選取了4個具有挑戰性的視頻對算法進行比較，3種算法均用600個粒子對目標逼近，將目標區域映射到36×36的矩陣上．文中算法采用10個目標模板和200個背景模板，并將每個圖像分成12塊，?1算法使用10個目標模板，IVT算法將模板矩陣的維數限制在m×16范圍內．本文算法如下:

算法2:文中算法

1．輸入:1視頻，2首幀目標狀態

2．獲得初始標準模板和目標模板字典

3．for(f=1:F)，F 為視頻幀數

4．利用粒子的速度和高斯分布噪聲更新粒子［14］

5．利用仿射變換［14］將候選粒子區域映射至固定的矩形中

6．使用“方差粒子篩選法”對粒子進行篩選，并用篩選結果更新背景模板字典

7．對候選目標和目標模板字典進行分塊表示

8．利用式(11)和(12)迭代計算式(10)中的權重

9．用式(13)、(14)和(15)計算出目標粒子的序號

10．更新標準模版

11．if(符合目標模板粒子更新條件)［8］

12．采用文獻［8］方法更新目標模板字典

13．end if

14．重采樣

15．end for

16．輸出:各幀目標狀態

2．1 試驗結果

第1個實驗視頻是“David Indoor”，視頻跟蹤難點主要有3個:①強烈的光照變化;②目標的形態發生改變;③目標尺度的變化．3種算法的結果如圖3所示，?1算法在第110幀因為光照條件的變化和目標的形態變化無法鎖定目標．文中算法和IVT算法在整個視頻中可以準確地跟蹤目標．

圖3 視頻“David Indoor”跟蹤結果Fig．3 Tracking results of“David Indoor”

第2個測試的視頻是“WalkByShop1cor(WBS)”，該視頻的主要難點有2個:①相似物體的干擾;②目標被其他行人遮擋．測試結果如圖4所示．?1算法在第102幀目標出現遮擋時鎖定了與目標相識的物體，在后面的跟蹤過程中，該算法又重新鎖定了目標;IVT算法在第102幀目標出現遮擋時偏離了目標;文中算法在整個視頻中可以準確地跟蹤目標，表現出了強魯棒性．

第3個測試視頻是“Plush Toy”，該視頻的主要挑戰有3點:①光照的變化;②目標形態的變化;③相似物體的干擾．如圖5所示，?1算法在第608幀以前偏離了目標，IVT算法在第608幀由于受相似物體的干擾偏移了目標，文中算法能夠完成整個視頻的跟蹤．

圖4 視頻“WalkByShop1cor”跟蹤結果Fig．4 Tracking results of“WalkByShop1cor”

圖5 視頻“Plush Toy”跟蹤結果Fig．5 Tracking results of“Plush Toy”

第4個測試視頻是“Trellis”，對該視頻進行跟蹤非常具有挑戰性，視頻中目標經歷了目標局部強烈光照變化，目標的形態和尺度也不斷變化．如圖6所示，?1算法在第103幀偏離了目標，IVT算法在第415幀由于光照和目標拍攝角度的變化偏離了目標，文中算法對光照和目標形態的變化表現出高魯棒性，可以成功完成跟蹤任務．

圖6 視頻“Trellis”跟蹤結果Fig．6 Tracking results of“Trellis”

2．2 結果分析

為了定量分析文中算法與其他兩種算法的試驗結果，將各種算法的誤差進行對比．這里定義跟蹤誤差為跟蹤算法得到的目標中點坐標值和實際目標中點坐標值的歐氏距離．從圖7可以看出，文中算法在4個視頻中均取得了較小的跟蹤誤差，而其他兩種算法則誤差較大．

圖7 跟蹤誤差比較Fig．7 Comparison of tracking error

為了更好地統計各跟蹤算法的誤差，文中采用了誤差百分比進行展示．圖8中，橫坐標表示誤差的像素，縱坐標表示百分比．文中采用10個像素為閾值對跟蹤的準確率進行統計．表1為3種算法在4個測試視頻中的跟蹤成功率，帶有下劃線的值為最好結果．從圖8和表1可以看出，除了視頻David Indoor中IVT算法的誤差百分比略高于文中算法外，文中算法均取得了最高的跟蹤成功率．

3種算法的每幀計算時間比較結果如表2所示．文中算法的運算時間最短，可見粒子篩選方法和?1最小化稀疏解算法可以大大縮短計算時間，這與前面計算量分析結果是相符的．

圖8 跟蹤誤差百分比Fig．8 Precision of location error

表1 跟蹤成功率統計Table 1 Statistics of tracking success rate

3 結論

表2 每幀計算時間比較Table 2 Comparison of computation time of one frame

文中提出了一種魯棒性強的目標跟蹤算法，該算法在粒子濾波框架下快速篩選粒子，減少了大量不必要的計算，提高了算法的速度．用目標與背景聯合稀疏表示方法將背景信息融入稀疏表示過程，在提高運算速度的同時提高了跟蹤的魯棒性．利用權重分塊表示的方法減少目標被遮擋或噪聲大的部分對整體結果的影響．試驗結果表明，文中算法無論是在計算速度上還是魯棒性上均取得了良好的效果．

［1］侯志強，韓崇昭．視覺跟蹤技術綜述［J］．自動化學報，2006，32(4):603-617．Hou Zhi-qiang，Han Chong-zhao．A survey of visual tracking［J］．Acta Automatica Sinica，2006，32(4):603-617．

［2］Agarwal S，Roth D．Learning a sparse representation for object detection ［J］．Computer Science，2006，2353:97-101．

［3］Wright J，Yang Allen Y，Ganesh A，et al．Robust face recognition via sparse representation［C］∥Proceedings of the 8th IEEE International Conference on Automatic Face and Gesture Recognition，2008:210-227．

［4］Yang M，Feng X．Sparse representation or collaborative representation:which helps face recognition［C］∥IEEE International Conference on Computer Vision．［S．l．］:ICCV，2011:471-478．

［5］Yang M，Zhang L，Zhang D，et al．Relaxed collaborative representation for pattern classification［C］∥IEEE Conference on Computer Vision and Pattern Recognition．［S．l．］:CVPR，2012:2224-2231．

［6］Elad M，Aharon M．Image denoising via sparse and redundant representations over learned dictionaries［J］．IEEE Transactions on Image Processing，2006，15(12):3736-3745．

［7］Mei X，Ling H B．Robust visual tracking and vehicle classification via sparse representation［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(11):2259-2272．

［8］Mei X，Ling H B．Robust visual tracking using ?1minimization［C］∥Proceedings of the IEEE International Conference on Computer Vision．［S．l．］:ICCV，2009:1436-1443．

［9］Bai T X，Li Y F．Robust visual tracking with structured sparse representation appearance model［J］．Pattern Recognition，2012，45(6):2390-2404．

［10］Liu H P，Sun F C．Visual tracking using sparsity induced similarity［C］∥Proceedings of the 20th International Conference on Pattern Recognition．［S．l．］:ICPR，2010:1702-1705．

［11］Sun F C，Liu H P．Fusion tracking in color and infrared images using joint sparse representation ［J］．Science Chine-Information Sciences，2012，55(3):590-599．

［12］Chen F，Wang Q，Wang S，et al．Object tracking via appearance modeling and sparse representation［J］．Image and Vision Computing，2011，29(11):787-796．

［13］Wang Q，Chen F，Yang J M，et al．Transferring visual prior for online object tracking ［J］．IEEE Transactions on Image Processing，2012，21(7):3296-3305．

［14］Ross D A，Lim J，Lin Ruei-sung，et al．Incremental learning for robust visual tracking［J］．International Journal of Computer Vision，2008，77(1/2/3):125-141．

［15］Li M，Tan T N，Chen W，et al．Efficient object tracking by incremental self-tuning particle filtering on the affine group ［J］．IEEE Transactions on Image Processing，2012，21(3):1298-1313．