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

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

基于稀疏表示的目標(biāo)跟蹤算法

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

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

為了解決目標(biāo)跟蹤忽視背景信息的問(wèn)題,運(yùn)用非常稀疏的矩陣對(duì)目標(biāo)與背景樣本提取低維Haar特征,并將候選目標(biāo)在過(guò)完備字典中進(jìn)行稀疏表示,用塊正交匹配追蹤的方式對(duì)稀疏表示進(jìn)行求解,通過(guò)殘差對(duì)目標(biāo)作最大似然估計(jì),提高跟蹤效果。實(shí)驗(yàn)結(jié)果表明,在光照變化、遮擋、復(fù)雜背景等情況下,基于稀疏表示的目標(biāo)跟蹤算法具有較高的魯棒性,且在跟蹤速度上有所提升。

Haar特征;背景信息;稀疏表示;塊正交匹配

稀疏表示是將信號(hào)分解到一個(gè)過(guò)完備字典的線性表示過(guò)程。在機(jī)器視覺(jué)中,由于稀疏表示在應(yīng)對(duì)遮擋和光照變化方面的良好表現(xiàn),近幾年被廣泛應(yīng)用。在人臉識(shí)別領(lǐng)域,文獻(xiàn)[1]的稀疏表示人臉識(shí)別算法為今后的稀疏表示視覺(jué)處理打開(kāi)了一扇大門(mén)。文獻(xiàn)[2]提出基于稀疏表示的L1 tracker算法,將跟蹤問(wèn)題看作求解稀疏解的過(guò)程,其主要思想是在粒子濾波框架下,提取候選目標(biāo),為解決遮擋問(wèn)題增加正負(fù)冗余模板,并計(jì)算重構(gòu)殘差,選擇殘差最小的候選目標(biāo)作為跟蹤結(jié)果,最后根據(jù)跟蹤結(jié)果對(duì)目標(biāo)模板和粒子的權(quán)重進(jìn)行更新。文獻(xiàn)[3]將稀疏表示壓縮感知原理運(yùn)用到目標(biāo)跟蹤,通過(guò)正交匹配追蹤(orthogonal match pursuit,簡(jiǎn)稱OMP)加速跟蹤。文獻(xiàn)[4]通過(guò)設(shè)定L1正則范數(shù)的錯(cuò)誤邊界,減少了求稀疏解的待選目標(biāo)個(gè)數(shù),一定程度上提高了跟蹤速度。文獻(xiàn)[5]從重構(gòu)算法入手,對(duì)L1 tracker算法加以改進(jìn),采用加速近端梯度(accelerated proximal gradient,簡(jiǎn)稱APG)重構(gòu)算法,提高了L1的求解速度和跟蹤效率。

上述方法雖然能有效地對(duì)目標(biāo)進(jìn)行跟蹤,但其生成模型的方法存在以下不足:1)外觀模型基于整體特征,在增加冗余模板后,使得計(jì)算量增加;2)忽視了背景與目標(biāo)的關(guān)系,不能有效利用背景篩選目標(biāo)。鑒于此,運(yùn)用滿足有限等距性質(zhì)(restricted isometry property,簡(jiǎn)稱RIP)的隨機(jī)稀疏矩陣投影壓縮Haar特征,將背景信息融入目標(biāo)的過(guò)完備字典中,并利用塊正交匹配追蹤(block orthogonal match pursuit,簡(jiǎn)稱BOMP)算法求解稀疏表示L1范數(shù)最小化,實(shí)現(xiàn)對(duì)目標(biāo)的穩(wěn)定跟蹤。

1 稀疏表示與過(guò)完備字典

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

目標(biāo)的稀疏表示是對(duì)原始信號(hào)的分解過(guò)程,該過(guò)程借助一個(gè)事先得到的字典D=[s1,s2,…,sn](也叫過(guò)完備基),將輸入信號(hào)表示為字典的線性近似過(guò)程。對(duì)于一個(gè)待檢測(cè)的目標(biāo)y,通過(guò)模板集向量線性組合n重構(gòu),y=∑aisi=Dα,其中α=[α1,α2,…,αn]T為i=1系數(shù)向量。考慮干擾情況,目標(biāo)重構(gòu)為:

其中A=[D,Dε]為含遮擋字典Dε的目標(biāo)的過(guò)完備基。信號(hào)y在過(guò)完備字典A通過(guò)系數(shù)向量ω的線性組合進(jìn)行表示。由于式(1)是欠定的,系數(shù)向量ω有無(wú)窮個(gè)解,可通過(guò)求解0范數(shù)來(lái)求解稀疏信號(hào),

但式(2)是一個(gè)NP-hard問(wèn)題,很難計(jì)算。對(duì)于某些測(cè)量矩陣,此問(wèn)題可等價(jià)于1范數(shù)的求解形式[6]:

1.2 特征的提取

Haar特征及其積分圖的求解由美國(guó)麻省理工學(xué)院的Viola博士提出,它是對(duì)目標(biāo)不同區(qū)域的像素灰度進(jìn)行有機(jī)組合,屬于一種綜合性特征,具有穩(wěn)定表達(dá)目標(biāo)的效果。另外,Haar特征可用積分圖的方法,一次性掃描各點(diǎn)到起點(diǎn)組成的矩形空間的像素并靜態(tài)保存在計(jì)算機(jī)內(nèi)存中,當(dāng)需要計(jì)算某個(gè)區(qū)域特征時(shí),可直接讀取數(shù)組的元素,運(yùn)用簡(jiǎn)單的加減運(yùn)算得出結(jié)果,以提高計(jì)算速度。

為了說(shuō)明矩形特征的海量問(wèn)題,對(duì)每個(gè)樣本Z∈Rw×h,用多尺度矩形濾波器與Z作卷積,得到樣本的所有矩形特征。濾波器集合H={h1,1,h1,2,…,hw,h}定義如下:

其中i、j分別為矩形濾波器的長(zhǎng)和寬。

設(shè)定X=[x1,x2,…,xm]T∈Rm為樣本Z的所有矩形特征,其中X=ZH,引入一個(gè)滿足RIP的非常稀疏的隨機(jī)矩陣Sn×m,且n?m。該矩陣為一個(gè)扁矩陣,通過(guò)投影可將特征向量降維壓縮。矩陣Sn×m的元素定義為:

其中p為設(shè)定數(shù)值,設(shè)定p=m/4產(chǎn)生一個(gè)非常稀疏的測(cè)量矩陣,該測(cè)量矩陣S的每一行只需計(jì)算4個(gè)非零元素,計(jì)算量非常低。將高維度特征空間X投影到低維空間:

其中V為壓縮后的特征,即通過(guò)測(cè)量矩陣提取的Harr類特征組,其提取過(guò)程如圖1所示。

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

采用滿足RIP的測(cè)量矩陣提取Harr類特征,得到的特征不僅幾乎保留了原始圖像的所有信息[6-7],保證了特征的有效性,而且在目標(biāo)模板出現(xiàn)部分遮擋時(shí),部分異常像素對(duì)于目標(biāo)將不會(huì)產(chǎn)生影響,增強(qiáng)了特征的穩(wěn)定性。

1.3 過(guò)完備字典組建

由于目標(biāo)存在于背景中,目標(biāo)與背景總是具有相關(guān)性,運(yùn)用其相關(guān)性,可更好地確定目標(biāo)的位置。因此,構(gòu)建過(guò)完備字典時(shí)在模板中增加背景模板信息,一方面,可更好地運(yùn)用目標(biāo)與背景的關(guān)系來(lái)穩(wěn)定跟蹤,另一方面,若下一幀候選粒子存在背景,其仍可在過(guò)完備字典中稀疏表示。提取目標(biāo)模板中背景模板的壓縮Haar特征組,分別記為:

為了減少光照和遮擋對(duì)跟蹤結(jié)果的擾動(dòng),在瑣碎模板中加入正瑣碎模板,即非負(fù)單位矩陣,則融合背景模板的目標(biāo)特征模板為:

其中I=[i1,i2,…,in]∈Rn×n為單位矩陣。

2 融合背景信息的跟蹤

2.1 觀測(cè)模型

將第i個(gè)候選目標(biāo)的特征Viy用融合背景模板的特征稀疏表示:

其中:af、ab為候選目標(biāo)特征組的表示系數(shù);ef為正瑣碎模板的表示系數(shù)。

對(duì)候選目標(biāo)采用重構(gòu)算法求其在目標(biāo)字典中的稀疏表示,并分別求候選目標(biāo)特征在目標(biāo)模板特征和背景模板特征下的重構(gòu)誤差:

準(zhǔn)確的目標(biāo)特征在目標(biāo)模板特征下的重構(gòu)誤差很小,而在背景模板特征下的重構(gòu)誤差很大;不準(zhǔn)確的目標(biāo)(無(wú)需跟蹤的目標(biāo))特征在背景模板特征下的重構(gòu)誤差很小,而在目標(biāo)模板特征下的重構(gòu)誤差很大。綜合這2方面的考慮,最佳候選目標(biāo)的觀測(cè)器為:

2.2 BOMP重構(gòu)算法

重構(gòu)算法的目的是求解式(8)中的稀疏表示系數(shù)。重構(gòu)算法的好壞直接影響跟蹤結(jié)果,OMP作為經(jīng)典的重構(gòu)算法,已被廣泛應(yīng)用,而在實(shí)際情況中,這種迭代的重構(gòu)算法非常耗時(shí)。目標(biāo)系數(shù)出現(xiàn)不為零的情況是成塊出現(xiàn)的,且塊稀疏信號(hào)中不為零的系數(shù)也成塊隨機(jī)出現(xiàn),而非雜亂無(wú)規(guī)律分布[8],因此利用BOMP算法成塊重構(gòu),既提高速度又保證與OMP幾乎同樣的精度。

BOMP算法流程:

1)初始化。設(shè)定初始化殘差r0=y,初始化測(cè)量矩陣Φ,初始化塊稀疏度K。

2)感知。進(jìn)行第k步迭代,計(jì)算殘差rk―1,并選擇與殘差rk―1最匹配的塊:

3)殘差更新。令Ek=Ek―1∪ik,對(duì)殘差進(jìn)行更新:rk=(ik―ΦEkΦETk)y。

4)收斂條件。判斷k與K的大小關(guān)系,若k＜K,則返回步驟2)繼續(xù)迭代,否則停止迭代。

2.3 目標(biāo)模板更新

由于跟蹤過(guò)程中目標(biāo)會(huì)發(fā)生姿態(tài)、光照等變化,需及時(shí)更新目標(biāo)模板。設(shè)定跟蹤結(jié)果的特征與最優(yōu)目標(biāo)模板特征的相似度小于某個(gè)閾值,將相似度最低的目標(biāo)模板特征更新為當(dāng)前跟蹤結(jié)果特征,其權(quán)重初始化為所有權(quán)重的中值。更新主要包括模板替代、模板更新和權(quán)重更新3個(gè)步驟。用跟蹤結(jié)果的特征代替目標(biāo)模板特征中權(quán)重最小的模板,其權(quán)重設(shè)為目標(biāo)模板權(quán)重的中值。權(quán)重的計(jì)算采用文獻(xiàn)[3]的計(jì)算公式。

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

1)實(shí)驗(yàn)設(shè)置。候選目標(biāo)的搜索半徑r=20,針對(duì)前20幀手動(dòng)取樣,目標(biāo)模板個(gè)數(shù)Nf=20,采樣的候選目標(biāo)數(shù)N=500,目標(biāo)模板更新的閾值設(shè)置為τ= 40,在CPU i5-3230M、內(nèi)存4 GB的計(jì)算機(jī)上用Matlab 2010仿真。

2)評(píng)價(jià)指標(biāo)。若一個(gè)視頻序列幀數(shù)為n,第i幀跟蹤到的目標(biāo)中心坐標(biāo)為(xi,yi),目標(biāo)中心坐標(biāo)為(^xi,^yi),則定義該幀的跟蹤誤差為:

該幀的跟蹤誤差越小,表明跟蹤精度越高。視頻序列的平均誤差為:

視頻序列的平均誤差越小,則表明整個(gè)視頻序列的跟蹤精度越高。

為了驗(yàn)證跟蹤效果,將評(píng)價(jià)指標(biāo)用于跟蹤David indoor、girl、coke三種視頻序列,這些視頻序列包含了目標(biāo)跟蹤過(guò)程中常出現(xiàn)的情形,如視角變化、光照變化、遮擋等,如表1所示。

表1 各視頻幀特征

為了凸顯算法的有效性,選取2種流行的跟蹤算法L1-APG[5]算法、CT[9]算法與本算法作比較,其中CT算法為基于壓縮感知原理的判決型跟蹤算法。3種跟蹤算法在3組視頻幀的實(shí)際跟蹤情況如圖2所示。從圖2可看出,本算法在跟蹤的過(guò)程中借助背景信息而使得跟蹤變得更加準(zhǔn)確,魯棒性更強(qiáng)。

圖2 各視頻幀的跟蹤結(jié)果Fig.2 Tracking results of each video

通過(guò)對(duì)比各個(gè)時(shí)刻的跟蹤誤差,分析各跟蹤算法在目標(biāo)跟蹤中的穩(wěn)定性與準(zhǔn)確性,以中心誤差作為衡量跟蹤誤差的指標(biāo),不同跟蹤算法在不同視頻上的跟蹤誤差如圖3所示。從圖3可看出,本算法的跟蹤精度更高,在各個(gè)時(shí)刻更加穩(wěn)定,魯棒性更強(qiáng)。

各個(gè)跟蹤算法在不同視頻幀的跟蹤誤差數(shù)據(jù)如表2所示。由表2可算出本算法、CT算法、L1-APG算法的平均跟蹤誤差分別為18.630 6、42.857 7、 56.503 3,因此本算法在3組測(cè)試視頻幀中的平均跟蹤誤差最小,表明跟蹤精度最高。

圖3 各視頻上的跟蹤誤差Fig.3 Tracking errors on the videos

表2 跟蹤誤差Tab.2 The tracking errors

通過(guò)記錄跟蹤算法處理全部視頻幀的時(shí)間,計(jì)算本算法與L1-APG算法的平均幀率,結(jié)果如表3所示。從表3可看出,本算法的跟蹤速率約為L(zhǎng)1-APG算法的3倍,平均幀率達(dá)到12 frame/s,基本達(dá)到了實(shí)時(shí)性的要求。

表3 平均幀率比較Tab.3 The comparison of average frame rate frame/s

4 結(jié)束語(yǔ)

基于壓縮特征提出了一種稀疏表示跟蹤算法,該算法在粒子濾波框架下,運(yùn)用積分圖快速計(jì)算跟蹤目標(biāo)的Haar特征,并將特征投影到滿足RIP的高斯矩陣上,實(shí)現(xiàn)對(duì)特征的壓縮,達(dá)到降維的目的;在過(guò)完備字典中融合背景信息特征,用BOMP實(shí)現(xiàn)對(duì)候選目標(biāo)特征的重建,利用重構(gòu)誤差比值構(gòu)建最優(yōu)觀測(cè)模型,達(dá)到對(duì)目標(biāo)的估計(jì)與跟蹤,且能根據(jù)跟蹤結(jié)果實(shí)時(shí)更新目標(biāo)特征模板。實(shí)驗(yàn)結(jié)果表明,該跟蹤方法達(dá)到了穩(wěn)定跟蹤目標(biāo)的目的,在速度方面相比L1-APG算法有所提升。

[1] Wright J,Yang A Y,Ganesh A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31 (1):210-227.

[2] Mei Xue,Ling Haibin.Robust visual tracking and vehicle classification via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(11):2259-2272.

[3] Li Haixi,Shen Chunhua,Shi Qinfeng.Real-time visual tracking using compressive sensing[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2011:1305-1312.

[4] Mei Xue,Ling Haibin,Wu Yi,et al.Minimum error bounded efficient l1 tracker with occlusion detection [C]//IEEE Conference on Computer Vision and Pattern Recognition,2011:1257-1264.

[5] Bao Chenglong,Wu Yi,Ling Haibin,et al.Real time robust l1 tracker using accelerated proximal gradient approach[C]//IEEE Conference on Computer Vision and Pattern Recognition,2012:1830-1837.

[6] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[7] 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.

[8] Eldar Y C,Kuppinger P,Bolcskei H.Block-sparsesignals:uncertainty relations and efficient recovery[J]. IEEE Transactions on Signal Processing,2010,58(6): 3042-3054.

[9] Zhang Kaihua,Zhang Lei,Yang M H.Real-time Compressive Tracking[M]//Fitzgibbon A,Lazebnik S,Perona P,et al.Computer Vision-ECCV 2012.[S.l.]: Springer Berlin Heidelberg,2012:864-877.

[10] Gonzlez R C,Woods R E.數(shù)字圖像處理[M].阮秋琦,阮宇智,譯.2版.北京:電子工業(yè)出版社,2007,236-257.

編輯:張所濱

Target tracking algorithm based on sparse representation

Wen Huiran,Zhang Hongmei,Zhang Xiangli,Li Pengfei
(School of Information and Communication Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

In order to solve the defects of tracking algorithm which ignores the background information,a very sparse matrix is used to get low dimensional Haar feature of target and background,and the candidate target can be sparse representation in the over complete dictionary.Block orthogonal matching pursuit method is used to solve the sparse representation and get residual,then the maximum likelihood estimation is achieved.Experimental results show that the tracking method based on sparse representation still has very high robustness in illumination,occlusion and complex background conditions,and the tracking speed is improved.

Haar feature;background information;sparse representation;block orthogonal match

TP391

:A

:1673-808X(2015)04-0305-05

2015-03-13

國(guó)家自然科學(xué)基金(61461010);桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃(GDYCSZ201413)

張紅梅(1970―),女,廣西桂林人,教授,博士,研究方向?yàn)榫W(wǎng)絡(luò)安全、嵌入式系統(tǒng)。E-mail:hmzh630@gmail.com

溫薈然,張紅梅,張向利,等.基于稀疏表示的目標(biāo)跟蹤算法[J].桂林電子科技大學(xué)學(xué)報(bào),2015,35(4):305-309.