基于壓縮特征的稀疏表示運動目標跟蹤

張紅梅， 溫薈然， 張向利， 李鵬飛

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

?

基于壓縮特征的稀疏表示運動目標跟蹤

張紅梅， 溫薈然， 張向利， 李鵬飛

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

摘要：為了應(yīng)對目標跟蹤中光照、遮擋、以及自身運動等因素的影響，采用積分圖方法提取目標模板的haar-like特征，用滿足有限等距條件(RIP)的隨機稀疏矩陣對特征投影壓縮，簡化目標特征字典的構(gòu)建；同時，在字典中融入背景信息，利用目標與背景的簡單關(guān)系提高跟蹤的精度;最后，利用塊正交匹配追蹤(BOMP)算法進行成塊重構(gòu)目標，加快了對稀疏表示的求解，增強了跟蹤的實時性.通過實驗發(fā)現(xiàn)，使用基于壓縮特征的塊正交匹配跟蹤算法(CF-BOMP)能構(gòu)建一個有效的目標外觀模型，增強跟蹤的穩(wěn)定性，提高跟蹤的實時性.

關(guān)鍵詞：特征壓縮；稀疏表示；粒子濾波；塊正交匹配

0引言

稀疏表示是近年來信號處理領(lǐng)域的熱點之一，為一種對原始信號的分解過程，該分解過程借助一個事先得到的字典，將輸入信號表示為字典的線性近似.文獻[1]首次在人臉識別中運用稀疏表示的方法;文獻[2]則利用線性表示特征構(gòu)建模板，結(jié)合稀疏表示理論，成功進行目標識別.隨著稀疏表示運用領(lǐng)域的推廣，在ICCV 2009上L1 tracker算法被首次提出來，文獻[3]提出L1 tracker算法是將跟蹤問題看成稀疏求解的過程,結(jié)合粒子濾波和稀疏表示思想，通過構(gòu)建含有瑣碎模板的目標外觀模型，將跟蹤問題轉(zhuǎn)化為求解稀疏表示的問題；文獻[4]將壓縮感知理論應(yīng)用到跟蹤算法中，目的在于解決實時性問題；文獻[5]通過設(shè)定L1正則范數(shù)的錯誤邊界，減少求解稀疏表示待選目標個數(shù)，一定程度上提高了跟蹤速度；文獻[6]從重構(gòu)算法入手對L1 tracker進行改進，采用APG(Accelerated Proximal Gradient algorithm)重構(gòu)算法，加快了L1求解的速度，提高了跟蹤的效率.但以上方法在跟蹤的實時性、準確性、穩(wěn)定性方面仍面臨著巨大挑戰(zhàn).

因此，筆者提出了一種利用壓縮特征進行稀疏表示的目標跟蹤方法——CF-BMOP算法.該算法基于壓縮感知理論[7-8]降維后的特征能夠有效表征目標，簡化目標特征模板的構(gòu)建，并引入背景信息從而增強跟蹤的準確性與穩(wěn)定性；同時，根據(jù)結(jié)構(gòu)關(guān)系采用了塊正交匹配追蹤(BOMP)重構(gòu)算法優(yōu)化了稀疏表示求解，實現(xiàn)對目標跟蹤準確性與實時性的提升，通過實驗證明了CF-BOMP算法在實時性和準確性方面得到提升.

1字典構(gòu)建與稀疏求解

1.1目標的稀疏表示

目標的稀疏表示是對原始信號的分解過程，該分解過程借助事先得到的目標字典D=[s1,s2…,sn]，將輸入信號表示為字典的線性近似的過程.對于一個待檢測的目標y，能夠通過模板及向量線性組合重構(gòu)，即

(1)

式中：α=[α1,α2,…,αn]T是系數(shù)向量.考慮到干擾情況的存在，目標的重構(gòu)情況為

(2)

式中：A=[D,Dε]含有遮擋字典Dε的目標的過完備基.利用A來線性組合表示目標，主要目標就是求出系數(shù)向量ω.由于式(2)是欠定的，有無窮多個解，而求解該方程可以通過求解0范數(shù)來求解稀疏信號，但0范數(shù)問題是一個NP-hard問題，很難計算.Donoho等人提出，對于某些測量矩陣，這個問題可以等價于1范數(shù)求解形式:

(3)

1.2壓縮特征提取

haar-like特征是將目標物不同位置的像素灰度特征建模成不同的區(qū)域時具有較好的表征能力，并且能夠利用積分圖來對haar-like特征進行加速計算.

另外，對于提取每個樣本，z∈Rw×h，為了表明矩形特征海量問題，用多尺度的矩形濾波器跟z做卷積，得到樣本的所有矩形特征，濾波器集合H={h1,1,h1,2,…,hw,h}，定義如下：

(4)

式中：w、h分別是矩形濾波器的長與寬.

(5)

其中，1/p為稀疏矩陣中不為零元素出現(xiàn)的概率，本文中設(shè)置1/p=4/m.

將高維度特征空間X投影到低維空間中，即

V=(v1,…,vn)=RX .

(6)

Haar-like類特征投影如圖1所示，采用滿足有限等距條件RIP的測量矩陣Rn×m提取目標的haar類特征，不僅保留了原始圖像的大量信息，保證了特征的有效性，而且在目標模版出現(xiàn)部分遮擋時候，減少了異常像素對于目標將產(chǎn)生的影響，增強了特征的穩(wěn)定性.

1.3含有背景信息的字典構(gòu)造

筆者在提取目標模板Nf的同時，在其周圍位置提取背景Nb，利用1.2節(jié)的特征提取壓縮方法,得到目標模板與背景模板對應(yīng)的特征Vf與Vb；同時，為了減少光照和遮擋帶來的影響，在目標模板中加入單位矩陣I=(i1,i2,…,in)∈Rn×n,構(gòu)成含有背景信息的目標過完備字典A：

A=[Vf,Vb,I].

(7)

圖1　haar-like類特征投影Fig.1　Haar-like feature projection

1.4塊正交匹配重構(gòu)

在實際情況中，稀疏信號出現(xiàn)的非零元素是具有一定的相關(guān)性，在位置上表現(xiàn)出一定的結(jié)構(gòu)性，表現(xiàn)出成塊出現(xiàn)非零元素的情況.因此，筆者使用塊正交匹配追蹤(BOMP)，利用信號過完備字典的塊稀疏結(jié)構(gòu)，選擇殘差最配子塊進行更新，提高了重構(gòu)的速度.塊正交匹配追蹤算法的步驟如下.

(1)初始化步驟.設(shè)定初始化殘差r0=y，測量矩陣為Φ，初始化塊稀疏度為K.

(2)感知步驟.進行第k步迭代，計算殘差rk-1，并選擇與殘差rk-1最匹配的塊：

(8)

(3)殘差更新步驟.令Ek=Ek-1∪ik，然后對殘差進行更新:

(9)

(4)收斂條件.判斷k與K的大小關(guān)系，如果k小于K，返回步驟2繼續(xù)迭代;否則停止迭代.

2稀疏表示目標跟蹤

2.1粒子濾波

粒子濾波主要由預(yù)測和更新遞推得到：

(10)

(11)

(12)

權(quán)重更新方法為

(13)

其中上式分母為采樣粒子的建議分布.

2.2基于稀疏表示的觀測

基于稀疏表示的系數(shù)向量α，筆者用組建的目標壓縮特征字典A對候選目標的壓縮特征進行重構(gòu)，根據(jù)候選樣本的目標觀測計算重構(gòu)殘差:

‖y-Aα‖2=‖y-(Vf,VB,I)(αf,αb,αi)T‖2.

(14)

式中：αf、αb分別為目標模板部分與背景模板部分的稀疏系數(shù)向量.如果候選目標為跟蹤目標，那么候選目標對應(yīng)于目標模板部分的重構(gòu)誤差會很小，而在背景模板中的重構(gòu)誤差會很大，反之亦然.因此，定義基于重構(gòu)誤差比的觀測值為

(15)

基于重構(gòu)誤差比的觀測似然函數(shù)為

(16)

式中：λ是控制參數(shù).當(dāng)目標的重構(gòu)誤差越小的時候，式(13)所表示的權(quán)重就會越大，也就證明候選樣本與目標樣本越相似.

2.3字典模板更新

目標的外觀以及背景關(guān)系會隨著自身運動或者環(huán)境的變化而發(fā)生改變，為了保證跟蹤的穩(wěn)定性，需要對目標及背景模板進行實時更新.針對背景模板在短時間內(nèi)變化小的情況，采用間隔n幀進行重新采樣更新的方法，設(shè)置n=5.同時，采用文獻[3]的方法進行目標模板更新，步驟如下.

(1)記vy代表跟蹤的結(jié)果所對應(yīng)的haar-like特征;a是vy在目標模板特征下的稀疏表示系數(shù);τ是設(shè)定的閾值.

(3)根據(jù)vy在目標模板特征下的稀疏表示系數(shù)對板重w進行更新，即wi=wi·exp(ai).

當(dāng)跟蹤結(jié)果的特征vy與最優(yōu)目標模板特征的相似度小于給出的閾值，則用跟蹤結(jié)果的特征vy代替目標模板特征中權(quán)重最小的模板.為了防止偏移，其權(quán)重設(shè)為目標模板權(quán)重的中值.

2.4算法流程

筆者提出的CF-BOMP算法流程如下：

(1)前M幀時，快速提取目標模板與背景模板的壓縮haar-like特征，添加單位矩陣I，構(gòu)建融入背景信息的目標特征過完備字典.

(2)下一幀時，在上一幀目標中心附近采樣候選目標，并提取候選目標的壓縮haar-like特征.

(3)利用過完備字典對候選目標特征進行稀疏表示，采用BOMP重構(gòu)算法來快速精確重構(gòu)，計算重構(gòu)殘差并引入觀測似然函數(shù)對目標進行最大似然估計，求出最佳候選目標.

(4)根據(jù)跟蹤結(jié)果，計算模板與最新結(jié)果相似度，替換相似度最小模板，更新目標過完備字典.

(5)返回繼續(xù)執(zhí)行第2步操作，實現(xiàn)對目標下一幀的跟蹤，直到視頻序列結(jié)束.

3實驗結(jié)果

實驗設(shè)置：候選目標的搜索半徑為r=15，對前20幀取樣構(gòu)建初始目標模板，目標模板個數(shù)為nf=20，背景目標模板數(shù)nb=10，采樣的候選目標數(shù)是n=600，目標模板更新的閾值設(shè)置為τ=40，所有實驗都是在CPU為i5-3230M、內(nèi)存2GB的計算機上運用Matlab 2010b進行仿真.

為了檢驗多種干擾情況下的跟蹤效果，實驗選用公認測試幀：David indoor、Girl、Coke，其特性如表1所示.選用CT算法[10]、L1-APG算法[6]和MIL算法[11]進行對比實驗，文獻[10]提出的CT算法是基于haar壓縮特征的二分類判別式跟蹤方法.而L1-APG算法是一種基于L1 tracker，采用加速逼近梯度重構(gòu)算法(APG)優(yōu)化求解速度，但其含有仿射模型來應(yīng)對目標尺度變化的問題.MIL算法將多示例學(xué)習(xí)方法加入到Online Boosting中，進而利用具有學(xué)習(xí)能力分類判決器跟蹤目標.

稀疏求解的重構(gòu)算法直接影響了跟蹤的效果[12](準確度與速度)，為充分驗證塊正交匹配算法(BOMP)能夠提高目標跟蹤的準確性與實時性，本文在相同情況下，對算法的重構(gòu)精度和運行速度進行比較，對比了正交匹配追蹤算法(OMP)、增廣拉格朗日算法(ALM)、加速共軛梯度算法(APG)，表2顯示了各重構(gòu)算法在3種視頻幀中的平均重構(gòu)誤差，可以看出，BOMP誤差最小.

表1　測試視頻幀特性

表2　平均重構(gòu)誤差

表3顯示了各重構(gòu)算法的重構(gòu)平均幀率，由于BOMP利用重構(gòu)系數(shù)的結(jié)構(gòu)關(guān)系，能夠成塊地對目標進行重構(gòu)，提高了重構(gòu)速度.綜合表2與表3的結(jié)果可以看出，塊正交匹配算法(BOMP)在稀疏表示重構(gòu)中能夠提高重構(gòu)的效率.

表3　平均重構(gòu)幀率

圖2～圖4分別顯示了4種算法在測試幀David indoor、Girl、Coke中的跟蹤情況.綜合分析可知，CT算法和MIL算法在跟蹤的過程中易受光照變化與目標旋轉(zhuǎn)的干擾，一旦發(fā)生偏移，會使目標模板更新并引入錯誤信息，逐漸遠離目標.L1-APG算法雖然能夠在目標變小時利用仿射模型準確跟蹤目標，但在快速運動與目標旋轉(zhuǎn)的過程中易受到干擾，引起跟蹤失敗.CF-BOMP算法在整個過程中能夠有效跟蹤目標，應(yīng)對光照變化、目標旋轉(zhuǎn)、快速運動、遮擋等干擾.

表4記錄了CF-BOMP算法、CT算法和L1-APG算法、MIL算法所對應(yīng)的3套測試幀的跟蹤中心誤差數(shù)值范圍，而該誤差能夠有效表征跟蹤算法的穩(wěn)定性.通過實驗對比發(fā)現(xiàn)，CF-BOMP算法誤差浮動范圍小，跟蹤更加穩(wěn)定.

圖2　David indoor 跟蹤結(jié)果Fig.2　Tracking result for David indoor

圖3　Girl 跟蹤結(jié)果Fig.3　Tracking result for Girl

圖4　Coke 跟蹤結(jié)果Fig.4　Tracking result for Coke表4　跟蹤誤差范圍Tab.4　Tracking error

視頻幀CF-BOMPMinMaxL1-APGMinMaxCTMinMaxMILMinMaxDavidindoor0.541.71.654.691.185.82.2139.7Girl2.156.32.164.90.5111.01.594.4Coke1.062.61.1275.91.481.02.2154.6平均值1.253.51.6131.81.092.62.0129.6

表5顯示了4種種算法在跟蹤過程中的平均中心誤差.從表5可以看出，CF-BOMP算法中心誤差在3組測試幀中均是最小，說明跟蹤精度最高，跟蹤更加精確.

圖5為4種算法的每幀跟蹤中心誤差連接成的平滑曲線.從圖5可以直觀看出，CF-BOMP算法在4種算法中跟蹤精度最高，跟蹤的穩(wěn)定性最好.

表5　跟蹤中心誤差

圖5　4種算法的中心誤差曲線Fig.5　Tracking error on the videos

表6為4種算法的平均幀率.表6中的CF-BOMP跟蹤算法由于構(gòu)建了簡單的外觀特征字典，而且使用BOMP算法加速重構(gòu)計算速度，使得跟蹤速度提高到同為稀疏表示跟蹤的L1-APG算法速度的2倍左右，是多示例學(xué)習(xí)的MIL算速度的3倍左右，但與判決式的CT算法相比，速度還是遜色不少.但是，判決式的跟蹤會因為一旦判決失誤，目標模板大面積更新后，就不能反映出目標本身的特性，跟蹤結(jié)果的偏離會更大.而CF-BOMP算法可以利用過完備字典中的背景信息提高跟蹤精度，同時在產(chǎn)生新結(jié)果后，能夠把重構(gòu)貢獻最小的粒子更新掉，但之前其他粒子模板仍會保留，也就保留了跟蹤目標多個時態(tài)特征，保證跟蹤效果的穩(wěn)定.

表6　平均幀率

4結(jié)論

筆者提出了一種基于壓縮特征的塊正交匹配跟蹤算法即CF-BOMP算法.該算法在粒子濾波框架下，運用積分圖加速計算跟蹤目標haar-like特征，并將特征投影到滿足有限等距條件RIP的隨機稀疏矩陣上，以實現(xiàn)對特征的壓縮，達到降維的目的，簡化目標特征的過完備字典.同時，在過完備字典中融入背景信息，利用目標與背景存在的簡單關(guān)系提高跟蹤的精確度.最后，在稀疏表示求解過程中，根據(jù)實際情況利用塊正交匹配追蹤(BOMP)提高求解L1-min的速度，引入基于重構(gòu)誤差比的觀測模型，實現(xiàn)對目標的快速預(yù)測與跟蹤，并根據(jù)跟蹤結(jié)果實時更新目標特征模版.通過實驗發(fā)現(xiàn)，該跟蹤方法簡化了過完備字典，構(gòu)建了有效的外觀模型，提升了跟蹤的實時性，并能夠穩(wěn)定跟蹤目標.

參考文獻：

[1]WRIGHT J, YANG A, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on pattern analysis and machine intelligence, 2009, 31(2)：2368-2378.

[2]張勇,黨蘭學(xué).線性判別分析特征提取稀疏表示人面識別方法[J].鄭州大學(xué)學(xué)報(工學(xué)版),2015,36(2):94-98.

[3]MEI Xue, LING Haibin. Robust visual tracking and vehicle classification via sparse representation[J]. IEEE Transactions on software engineering, 2011, 33(11): 2259-2272.

[4]LI Haixi, SHEN Chunhua, SHI Qinfeng. Real-time visual tracking using compressive sensing[C]∥2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Colorado Springs, CO, USA: IEEE Press, 2011: 1305-1312.

[5]Mei Xue, Ling Haibin, Wu Yi, et al. Minimum error bounded efficient1 tracker with occlusion detection[C]∥2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Washton DC,USA:IEEE Press, 2011: 1257-1264.

[6]BAO Chenglong, WU Yi, LING Haibin, et al. Real time robust l1 tracker using accelerated proximal gradient approach[C]∥2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, Rhode Island:IEEE Press, 2012: 1830-1837.

[7]DONOHO D L. Compressed sensing[J]. IEEE Transactions on information theory, 2006, 52(4): 1289-1306.

[8]CANDES E J, TAO T. Near-optimal signal recovery from random projections: Universal encoding strategies[J].IEEE Transactions on information theory, 2006, 52(12): 5406-5425.

[9]ELDAR Y C,KUPPINGER P,BOLCSKEI H.Block-sparsesignals:uncertainty relations and efficient recov-ery[J]. IEEE Transactions on signal processing, 2010 ,58(6):3042-3054.

[10]ZHANG Kaihua, ZHANG Lei, YANG Ming-Hsuan. Real-time compressive tracking[C]∥Computer Vision-ECCV 2012.Berlin,Heidelberg:Springer, 2012: 864-877.

[11]BABENKO B, YANG, M H , BELONGIE, S. Robust object tracking with online multiple instance learning[J].IEEE Transactions on pattern analysis and machine intelligence, 2011, 33(8)：1619-1632.

[12]GONZLEZ R C,WOODS R E.數(shù)字圖像處理[M].阮秋琦，阮宇智，譯.2版.北京:電子工業(yè)出版社，2007.

Sparse Representation Tracking Based on Compressed Features

ZHANG Hongmei， WEN Huiran， ZHANG Xiangli， LI Pengfei

(School of Information and Communication Engineering, Guilin University of Electronic Technology,Guilin 541004,China)

Abstract:In order to deal with the influence of the factors such as light, shade,movement of object and etc.,the integral graph method is used to extract the Haar-like features of the target template, and the features are compressed by a random sparse matrix which meets the limited equidistant conditions(RIP), then the construction of the target features dictionary is simplified .Meanwhile,the background information is added in the dictionary,and the simple relationship between the target and the background is used to improve the accuracy of tracking. At last, the target can be reconstructed in block by using the block orthogonal matching pursuit (BOMP) reconstruction algorithm, through which can enhances tracking speed. The experimental results show that, the block orthogonal matching pursuit tracking algorithm based on compression feature is powerful in valid target appearance model construction.And it also enhances the tracking stability and improves tracking speed.

Key words:features compression; sparse representation; particle filter; block orthogonal matching

收稿日期:2015-10-10；

修訂日期：2016-01-20

基金項目：國家自然科學(xué)基金資助項目(61461010,61363031)；桂林電子科技大學(xué)研究生教育創(chuàng)新計劃資助項目(GDYCSZ201413)

作者簡介:張紅梅(1970—)，女，廣西桂林人，桂林電子科技大學(xué)教授，主要從事嵌入式、信息安全及機器視覺等研究，E-mail：hmzh630@gmail.com.

文章編號:1671-6833(2016)03-0021-06

中圖分類號：TP391

文獻標志碼：A

doi:10.13705/j.issn.1671-6833.2016.03.005