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

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

?

基于壓縮特征的稀疏表示運(yùn)動(dòng)目標(biāo)跟蹤

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

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

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

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

0引言

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

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

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

1.1目標(biāo)的稀疏表示

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

(1)

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

(2)

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

(3)

1.2壓縮特征提取

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

另外，對于提取每個(gè)樣本，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提取目標(biāo)的haar類特征，不僅保留了原始圖像的大量信息，保證了特征的有效性，而且在目標(biāo)模版出現(xiàn)部分遮擋時(shí)候，減少了異常像素對于目標(biāo)將產(chǎn)生的影響，增強(qiáng)了特征的穩(wěn)定性.

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

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

A=[Vf,Vb,I].

(7)

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

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

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

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

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

(8)

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

(9)

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

2稀疏表示目標(biāo)跟蹤

2.1粒子濾波

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

(10)

(11)

(12)

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

(13)

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

2.2基于稀疏表示的觀測

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

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

(14)

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

(15)

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

(16)

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

2.3字典模板更新

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

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

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

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

2.4算法流程

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

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

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

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

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

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

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

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

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

稀疏求解的重構(gòu)算法直接影響了跟蹤的效果[12](準(zhǔn)確度與速度)，為充分驗(yàn)證塊正交匹配算法(BOMP)能夠提高目標(biāo)跟蹤的準(zhǔn)確性與實(shí)時(shí)性，本文在相同情況下，對算法的重構(gòu)精度和運(yùn)行速度進(jìn)行比較，對比了正交匹配追蹤算法(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)系，能夠成塊地對目標(biāo)進(jì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算法在跟蹤的過程中易受光照變化與目標(biāo)旋轉(zhuǎn)的干擾，一旦發(fā)生偏移，會(huì)使目標(biāo)模板更新并引入錯(cuò)誤信息，逐漸遠(yuǎn)離目標(biāo).L1-APG算法雖然能夠在目標(biāo)變小時(shí)利用仿射模型準(zhǔn)確跟蹤目標(biāo)，但在快速運(yùn)動(dòng)與目標(biāo)旋轉(zhuǎn)的過程中易受到干擾，引起跟蹤失敗.CF-BOMP算法在整個(gè)過程中能夠有效跟蹤目標(biāo)，應(yīng)對光照變化、目標(biāo)旋轉(zhuǎn)、快速運(yùn)動(dòng)、遮擋等干擾.

表4記錄了CF-BOMP算法、CT算法和L1-APG算法、MIL算法所對應(yīng)的3套測試幀的跟蹤中心誤差數(shù)值范圍，而該誤差能夠有效表征跟蹤算法的穩(wěn)定性.通過實(shí)驗(yàn)對比發(fā)現(xiàn)，CF-BOMP算法誤差浮動(dòng)范圍小，跟蹤更加穩(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)計(jì)算速度，使得跟蹤速度提高到同為稀疏表示跟蹤的L1-APG算法速度的2倍左右，是多示例學(xué)習(xí)的MIL算速度的3倍左右，但與判決式的CT算法相比，速度還是遜色不少.但是，判決式的跟蹤會(huì)因?yàn)橐坏┡袥Q失誤，目標(biāo)模板大面積更新后，就不能反映出目標(biāo)本身的特性，跟蹤結(jié)果的偏離會(huì)更大.而CF-BOMP算法可以利用過完備字典中的背景信息提高跟蹤精度，同時(shí)在產(chǎn)生新結(jié)果后，能夠把重構(gòu)貢獻(xiàn)最小的粒子更新掉，但之前其他粒子模板仍會(huì)保留，也就保留了跟蹤目標(biāo)多個(gè)時(shí)態(tài)特征，保證跟蹤效果的穩(wěn)定.

表6　平均幀率

4結(jié)論

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

參考文獻(xià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é).線性判別分析特征提取稀疏表示人面識(shí)別方法[J].鄭州大學(xué)學(xué)報(bào)(工學(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

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

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

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

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

doi:10.13705/j.issn.1671-6833.2016.03.005