基于元樣本稀疏表示的目標跟蹤算法

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

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

基于元樣本稀疏表示的目標跟蹤算法

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

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

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

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

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

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

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

1 基于稀疏的目標跟蹤算法

1.1 目標的稀疏表示

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

稀疏表示模型認為自然信號能夠被簡潔地表示，或逼近成預先定義的原子信號的線性組合，而且這些組合系數(shù)是稀疏的，即只有少數(shù)不為零的系數(shù)。直觀地，稀疏性可以由稀疏向量非零的個數(shù)來表示，也就是用l0范數(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 基于稀疏表示的目標跟蹤算法

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

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

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

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

2 基于元樣本稀疏表示的目標跟蹤算法

2.1 目標模板的元樣本

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

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

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

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

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

2.2 基于元樣本稀疏表示的目標跟蹤算法

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

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

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

同樣，目標圖像可以通過下式估計得到：

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

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

其中：y∈Rd×1表示目標向量;W∈Rd×k表示目標模板的元樣本向量;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)化問題能夠有效解決。

本文算法總結如下：

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

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

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

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

⑦ 獲取當前幀目標位置Xt=Σi，i=1，2，…，n;

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

⑨更新目標模板T。

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

3 實驗結果與分析

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

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

表1 實驗采用的跟蹤視頻

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

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

圖3 部分跟蹤結果比較

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

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

4 結束語

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

［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］.計算機學報，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

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

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

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

(責任編輯 楊黎麗)