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

張 英，樊亞翔，孫 浩，計科峰

(國防科技大學(xué)電子科學(xué)與工程學(xué)院，長沙 410073)

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

張 英，樊亞翔，孫 浩，計科峰

(國防科技大學(xué)電子科學(xué)與工程學(xué)院，長沙 410073)

近年來，稀疏表示被引入視頻目標(biāo)跟蹤問題中。在粒子濾波框架下，視頻跟蹤問題被看作是使用若干個目標(biāo)模板來稀疏化線性表示候選區(qū)域的過程，并使用“小模板”來處理目標(biāo)物在視頻場景中出現(xiàn)的各種復(fù)雜變化。但算法沒能利用模板的本質(zhì)特性，復(fù)雜度高。基于元樣本稀疏表示提出一種目標(biāo)跟蹤算法，提取目標(biāo)模板的元樣本建立目標(biāo)詞典，再針對目標(biāo)遮擋情況引入遮擋詞典，進(jìn)而構(gòu)造超完備詞典;在跟蹤階段，采用了一種迭代的方法解決l1最小范數(shù)問題，計算稀疏表示系數(shù)。實驗結(jié)果表明：提出的算法比文獻(xiàn)中現(xiàn)有的基于l1范數(shù)最小化的跟蹤方法性能更穩(wěn)定、計算效率更高。

目標(biāo)跟蹤;稀疏表示;l1最小范數(shù);元樣本;主成分分析

視覺目標(biāo)跟蹤是計算機(jī)視覺研究領(lǐng)域的一個重要的研究方向，被廣泛應(yīng)用于智能視頻監(jiān)控、運(yùn)動分析、運(yùn)動識別以及人機(jī)交互等領(lǐng)域。目前已有大量學(xué)者對視頻跟蹤算法進(jìn)行了廣泛研究，提出了多種類型的跟蹤算法，包括基于模板［1］、基于子空間分析［2］、在線分類［3］的跟蹤算法等。最近，MEI等［4－5］將稀疏表示技術(shù)引入到視頻目標(biāo)跟蹤任務(wù)中，將跟蹤問題視為粒子濾波框架下的稀疏編碼問題，提出了l1－跟蹤子;同時，通過引入一組“小模板”(正模板和負(fù)模板)，使得算法能夠魯棒地處理目標(biāo)物的形變、遮擋以及場景光照變化等一系列富有挑戰(zhàn)性的問題，取得了良好的效果。但是該方法直接使用圖像模板作為詞典，且目標(biāo)模板較多，導(dǎo)致算法的復(fù)雜度高、計算量大。此外，這種方法沒有注意到圖像本質(zhì)上稀疏冗余的特點(diǎn)，利用目標(biāo)模板的本質(zhì)信息來表示目標(biāo)，導(dǎo)致當(dāng)目標(biāo)姿態(tài)發(fā)生變化時，跟蹤不夠穩(wěn)定。

元樣本可以看作樣本基因表達(dá)的線性組合，并且包含數(shù)據(jù)的本征結(jié)構(gòu)［6］。所有的樣本都可以由元樣本來進(jìn)行線性表示。對于跟蹤問題，待跟蹤目標(biāo)可以看作它的目標(biāo)模板元樣本的線性表示。

根據(jù)上述情況，本文提出了一種基于元樣本稀疏表示的目標(biāo)跟蹤算法。通過大量比較實驗，驗證了該方法的跟蹤精度比原始l1－跟蹤子好，跟蹤效率也有了一定的提升，對于分辨率較高的視頻跟蹤效果更好。

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

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

稀疏表示理論有其認(rèn)知學(xué)背景，并被應(yīng)用于字典構(gòu)建、圖像分類等領(lǐng)域［7］。理論和實驗表明，基于稀疏表示的樣本相似性度量具有判別性，一個樣本通常僅由其同類樣本線性加權(quán)獲得，從而更好地刻畫樣本間的相似度信息。

稀疏表示模型認(rèn)為自然信號能夠被簡潔地表示，或逼近成預(yù)先定義的原子信號的線性組合，而且這些組合系數(shù)是稀疏的，即只有少數(shù)不為零的系數(shù)。直觀地，稀疏性可以由稀疏向量非零的個數(shù)來表示，也就是用l0范數(shù)來測量，形式描述如下：假設(shè)存在一個過完備的字典A∈Rm×n，則樣本y∈Rm被表示為：

式(1)中：ε是誤差容限，‖·‖0代表l0范數(shù)，向量中非零元素的個數(shù)。l0范數(shù)最小化問題是一個NP難題。如果問題的解足夠稀疏，l1范數(shù)最小化，由于其與l0范數(shù)最小化的凸函數(shù)最接近，兩者是等價的，即也可以表示如下：

對于上述最優(yōu)化問題，有許多方法能夠有效地求解，包括匹配追蹤算法(MP)、正交匹配追蹤算法(OMP)等方法［8］。

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

MEI等提出基于稀疏表示的目標(biāo)跟蹤，其基本思想是：不同視角、不同光照條件下的目標(biāo)圖像，可以近似地認(rèn)為是處在一個低維的子空間中，該子空間可由一系列的目標(biāo)模板構(gòu)成。為了跟蹤一個目標(biāo)，首先需要通過l1范數(shù)最小化對每一個候選目標(biāo)(粒子濾波產(chǎn)生的粒子)用瑣碎模板和目標(biāo)模板進(jìn)行稀疏表示計算，然后在所有的候選目標(biāo)當(dāng)中選擇具有最大概率的候選目標(biāo)(粒子)作為當(dāng)前幀跟蹤結(jié)果，再在下一幀中繼續(xù)采用粒子濾波器來產(chǎn)生候選目標(biāo)(粒子)，并重復(fù)進(jìn)行。

簡要過程如下：首先定義一個目標(biāo)模板集合T=［t1，t2，…，tn］∈Rm×n。這個目標(biāo)模板集合包含了n個目標(biāo)模板(通過將目標(biāo)模板灰度圖像變化成一個m維列向量)。跟蹤結(jié)果y就可以通過目標(biāo)模板集合的線性約束來逼近，如下公式所示：

其中，a= [a1，a2，…，an]T∈Rn即為目標(biāo)物的稀疏表示系數(shù)。考慮到目標(biāo)被遮擋的情況，引入誤差向量e來描述圖像中的遮擋部分，則目標(biāo)圖像可以按下式估計得到：

其中：I∈Rn×n是單位矩陣，為處理噪聲的小的模板集。若記 D=[T，E]，c=[a，e]T，式(4)可以改寫為一個l1范數(shù)最小化問題：

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

2.1 目標(biāo)模板的元樣本

元樣本的概念是從生物學(xué)基因表達(dá)的角度提出的。元樣本可以看作它基因表達(dá)數(shù)據(jù)的線性組合，能俘獲數(shù)據(jù)的本質(zhì)信息。所有的樣本都可以由元樣本來進(jìn)行線性表示。對于維數(shù)較高的樣本數(shù)據(jù)，通過計算其元樣本來表示數(shù)據(jù)，不僅能夠獲取數(shù)據(jù)的本質(zhì)結(jié)構(gòu)，還起到數(shù)據(jù)降維的作用，加快后續(xù)計算速度。

數(shù)學(xué)上，將數(shù)據(jù)矩陣T分解為2個矩陣：

其中：矩陣T表示m×n的原始數(shù)據(jù)集，每列為一個樣本的數(shù)據(jù)，每行表示數(shù)據(jù)的特征;矩陣W大小為m×p，其中每一列定義為一個元樣本;矩陣H大小為p×n，其中每一行的n個系數(shù)代表了相應(yīng)樣本在元樣本上的表達(dá)模式，如圖1所示。

圖1 目標(biāo)模板數(shù)據(jù)的元樣本

用于元樣本提取的方法有很多，如主分量分析(PCA)、奇異值分解(SVD)、非負(fù)矩陣因式分解(NMF)以及獨(dú)立分量分析(ICA)等。

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

元樣本包含了目標(biāo)模板樣本的內(nèi)在結(jié)構(gòu)，可以采用元樣本代替訓(xùn)練數(shù)據(jù)中的目標(biāo)模板來表示目標(biāo)。分別從目標(biāo)模板數(shù)據(jù)中提取元樣本，為此將目標(biāo)模板數(shù)據(jù)集矩陣T分解為2個矩陣：T～WH。其中：W是一個m×p的矩陣;H是一個p×n的矩陣;p是元樣本的數(shù)目，在實驗部分被確定。由于目標(biāo)模板的PCA基具有仿射不變、尺度不變、對光照變化和姿態(tài)變化魯棒性好的特點(diǎn)，能夠獲得目標(biāo)模板的本質(zhì)信息，因此選取PCA方法進(jìn)行元樣本提取。

圖2 兩種方法的區(qū)別

其中：I∈Rn×n是單位矩陣，為處理噪聲的小的模板集;若記 D=[T，E]，c=[a，e]T，y=Dc。同樣，類似式(5)、(7)可以轉(zhuǎn)換為：

同樣，目標(biāo)圖像可以通過下式估計得到：

因此，目標(biāo)跟蹤問題同樣轉(zhuǎn)換為一個求解l1最小范數(shù)問題，如圖2所示。

在這里，首先說明式(5)和式(8)的區(qū)別：對于式(5)，目標(biāo)模板和“小模板”的系數(shù)應(yīng)該是稀疏的;對于式(8)，小模板是稀疏的，但是目標(biāo)模板的元樣本不是稀疏的。由于“小模板”的數(shù)量遠(yuǎn)大于目標(biāo)模板的元樣本數(shù)量，目標(biāo)能夠被目標(biāo)模板和“小模板”一起稀疏表示，因此需要尋找新的算法來解等式(8)。

其中：y∈Rd×1表示目標(biāo)向量;W∈Rd×k表示目標(biāo)模板的元樣本向量;a∈Rk×1表示稀疏表示系數(shù);e∈Rd×1表示誤差向量;λ為參數(shù)。由于式(9)沒有封閉解法，采用一個迭代的方法來計算aopt和eopt：

①如果給定 eopt，式(9)就等于J( a)的最小值，其中J( a)=‖ ( y－eopt)－Wa。這是個最小二乘問題，aopt能夠通過aopt=WT( y－eopt)獲得。

②給定aopt，式(9)就等于G( e)的最小值，其中

通過步驟①和步驟②，式(9)的優(yōu)化問題能夠有效解決。

本文算法總結(jié)如下：

輸入：某幀視頻It，上一幀目標(biāo)位置 Xt－1，目標(biāo)模板T，粒子數(shù)量N

輸出：每幀跟蹤到的目標(biāo)位置Xt及更新后的目標(biāo)物模板T。

①初始化：以Xt－1為均值Σ為方差的高斯先驗分布生成N個粒子 {：i=1，2，…n}，并設(shè)置各粒子的權(quán)值為=1/n;

③對于目標(biāo)模板T，通過式(6)提取其元樣本W(wǎng);

⑦ 獲取當(dāng)前幀目標(biāo)位置Xt=Σi，i=1，2，…，n;

⑧獲取Xt對應(yīng)的目標(biāo)物特征yt，并計算其在過完備字典D上的稀疏系數(shù)ct;

⑨更新目標(biāo)模板T。

對于上述算法中第⑨步的模板更新問題，采用一種基于誤差門限的升級方法。在每幀跟蹤目標(biāo)獲得最優(yōu)的匹配模板后，抽取相應(yīng)的圖像基和誤差矩陣;基于誤差矩陣，計算它其中的非零系數(shù)比例η;然后根據(jù)η采用3種升級策略：完全升級、部分升級以及不升級。

3 實驗結(jié)果與分析

為了驗證算法的有效性，對一些標(biāo)準(zhǔn)的視頻數(shù)據(jù)集進(jìn)行了測試。算法在Matlab7.1下編程實現(xiàn)，實驗的硬件平臺為 3.3GHz Core2，內(nèi)存為3GB。對于每個視頻序列，手工標(biāo)記了初始幀的目標(biāo)位置。對于目標(biāo)模板元樣本提取，選擇了PCA的方法，模板圖像裁剪成32×32的大小，并且提取16個元樣本作為目標(biāo)模板。此外，選取了1 024個小模板。粒子數(shù)設(shè)置為N=600，跟蹤器每隔5幀升級一次。整個實驗中λ設(shè)置為0.05。

本文算法在3個公開的視頻數(shù)據(jù)進(jìn)行了一系列的實驗，3個視頻分別涉及到目標(biāo)部分遮擋、光照變化、姿態(tài)的變化等挑戰(zhàn)性的問題。本文實驗使用的追蹤視頻如表1所示。本文算法與最近提出的目標(biāo)追蹤算法(多實例學(xué)習(xí)跟蹤算法MIL［3］、增量學(xué)習(xí)跟蹤算法IVT、基于稀疏表示的追蹤算法L1［4］)進(jìn)行比較。

表1 實驗采用的跟蹤視頻

圖3分別是在Car 4、singers以及Occlusion2視頻序列上實施上述4個實驗的部分跟蹤結(jié)果。由圖中可以看出：對于遮擋、光照變化、旋轉(zhuǎn)、尺度變化等問題，IVT算法、MIL算法以及L1算法都出現(xiàn)了不同程度的追蹤目標(biāo)漂移現(xiàn)象，比較得出本文算法跟蹤效果較好、漂移較少、穩(wěn)定性優(yōu)于其他3類算法。

在定量分析方面，通過追蹤目標(biāo)中心位置與手動標(biāo)記的真實中心位置，利用歐式距離進(jìn)行對比，距離越大說明越偏移目標(biāo)。對每隔5幀圖像取一個手動標(biāo)記的5幀圖像中心的平均值與4個算法的實驗結(jié)果進(jìn)行比較，中心位置誤差比較如表2所示。由表2可知：本文方法中心位置誤差率與其他算法相比普遍減少20%以上，進(jìn)一步說明了本文算法的穩(wěn)定性。表3是3種算法的平均幀率比較?？梢钥吹剑罕疚姆椒ㄐ矢哂贚1算法。與其他3種方法相對比，本文算法在singers數(shù)據(jù)庫上漂移最少、效率較高，證明了本文算法對于分辨率較高的視頻跟蹤有較好的效果。

圖3 部分跟蹤結(jié)果比較

表2 算法平均中心位置誤差(像素)

表3 跟蹤平均幀率比較(幀/s)

4 結(jié)束語

本文針對原始l1－跟蹤子效率低下的缺點(diǎn)，提取目標(biāo)模板的元樣本來代替目標(biāo)模板表示目標(biāo)，進(jìn)行稀疏表示跟蹤。該算法利用了目標(biāo)模板的元樣本信息，用目標(biāo)模板的本質(zhì)信息來表示目標(biāo)，從而提高了算法的效率。在求解稀疏表示系數(shù)階段，采用一種反復(fù)迭代的方法來解決l1最小范數(shù)問題。對標(biāo)準(zhǔn)的視頻數(shù)據(jù)集進(jìn)行了測試，結(jié)果證明該方法的魯棒性和有效性。采用其他的元樣本提取方法(如NMF)來代替目標(biāo)模板以及進(jìn)一步提升算法效率，將是我們下一步研究的重點(diǎn)。

［1］ Adam A，Rivlin E，and Shimshoni I.Robust fragments －based tracking using the integral histogram［J］.Proc.IEEE Conf.Comput.Vision Pattern Recognition，2006：798－805.

［2］ Wang T，Gu I Y H，Shi P.Object tracking using incremental 2d－pca learning and ml estimation［C］.Acoustics，Speech and Signal Processing 2007.In ICASSP，2007：933 －936.

［3］ Babenko B，Yang M H，Belongie S.Visual tracking with online multiple instance learning［C］.Proc.IEEE Conf.Comput.Vision Pattern Recognition，2009：983-990.

［4］ MEI Xue，LING Haibin.Robust visual tracking using L1 minimization［C］.Proceedings of the IEEE 12th International Conference on Computer Vision(ICCV 2009)，Kyoto，Japan：1436 －1443.

［5］ 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.

［6］ Brunet J P，Tamayo P，Golun T R，et al.Metagenes and molecular pattern discovery using matrix factorization［J］.National Academy of Sciences，2004，101(12)：4164－4169.

［7］ 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(2)：210－227.

［8］ 戴瓊海，付長軍，季向陽.壓縮感知研究［J］.計算機(jī)學(xué)報，2011，34(3)：425 －434.

Object Tracking Algorithm Based on Sparse Representation for Meta-sample

ZHANG Ying，F(xiàn)AN Ya-xiang，SUN Hao，JI Ke-feng
(School of Electronic Science and Engineering，National University of Defense Technology，Changsha 410073，China)

The research on sparse coding has been introduced into the issue of video object tracking recently.Under particle filter framework，the target template is represented by a set of all target candidates.Trivial templates are used to deal with complex changes of objects in video scenes.In this paper，however，the algorithm ignores the intrinsic information of the target candidates，so the cost is very expensive.This paper proposes an object tracking algorithm based sparse representation for metasample.A set of meta-samples were firstly extracted from all target candidates，then the trivial template were added into building the over complete dictionary.For tracking，an iterative algorithm was proposed to solve l1-norm minimization.Experimental results indicate that the proposed method is more effective and robust than the existing methods based on l1norm minimization.

object tracking;sparse representation;l1minimization;meta-sample;principal component analysis

format：ZHANG Ying，F(xiàn)AN Ya-xiang，SUN Hao，et al.Object Tracking Algorithm Based on Sparse Representation for Meta-sample［J］.Journal of Chongqing University of Technology：Natural Science，2014(1)：91 －95.

TP391

A

1674－8425(2014)01－0091－05

10.3969/j.issn.1674－8425(z).2014.01.018

2013－07－20

國防科學(xué)技術(shù)大學(xué)優(yōu)秀學(xué)位論文選題資助項目

張英(1984—)，男，陜西彬縣人，碩士研究生，主要從事計算機(jī)視覺與智能信息處理研究。

張英，樊亞翔，孫浩，等.基于元樣本稀疏表示的目標(biāo)跟蹤算法［J］.重慶理工大學(xué)學(xué)報：自然科學(xué)版，2014(1)：91 －95.

(責(zé)任編輯 楊黎麗)