一種基于稀疏表示的判別式目標跟蹤算法

戴平陽，洪景新，李翠華，詹小靜

（廈門大學信息科學與技術學院，福建 廈門361005）

目標跟蹤是計算機視覺領域的熱點研究課題，它在智能視頻監控、人機交互、精確制導以及虛擬現實等領域有著廣泛的應用.目標跟蹤的主要難點包括復雜場景下目標平移、旋轉、光照變化、視角變化等目標外觀變化，目標的遮擋與自遮擋，動態場景中嘈雜背景干擾及雨、煙、霧、陰影等因素干擾.視覺目標跟蹤問題近十多年來已經進行了廣泛而又深入的研究，但實踐表明，復雜場景下的運動目標跟蹤算法還遠未成熟.因此在復雜場景下設計一個魯棒、準確地進行視覺目標跟蹤的算法仍然是一項具有挑戰性的課題.

目標跟蹤指的是圖像序列中對目標的運動狀態進行持續估計與預測過程.目標外觀模型的好壞是跟蹤算法的關鍵.根據目標模型建立方法不同，通常將跟蹤方法分為兩類：產生式模型和判別式模型.基于產生式模型的跟蹤方法首先學習一個外觀模型作為目標觀測，然后在目標可能運動的范圍內搜索與該生成模型最相似的區域，從而實現目標的跟蹤.Black［1］等提出了一種子空間學習方法，采用主成分分析方法建立感興趣目標的外觀模型來進行跟蹤；Zhou［2］等則在粒子濾波框架中嵌入自適應的外觀變化模型來處理跟蹤過程中目標外觀變化.Ross等［3］將提出一種增量子空間更新方法，通過漸進獲取子空間的基構建跟蹤框架，以適應目標外觀的動態變化.基于判別式模型的跟蹤方法將目標跟蹤表示成一個分類問題，通過選擇合適的特征及分類器將目標從背景中區分開來.Collins等［4］提出了一種基于判別式在線學習跟蹤算法，該算法在線選擇具有背景和前景區分性的RGB顏色值的線性組合來作為跟蹤特征.Wang等［5］將Haar特征應用于跟蹤領域，通過在特征空間中使用Fisher判別方法，選擇得到有判別力的特征，在粒子濾波框架中提出一種具有判別力的在線跟蹤算法.Avidan［6］利用AdaBoost算法從弱分類器中學習得到一個強分類器來進行目標跟蹤.Grabner等［7］則設計一個在線Boosting分類器，該分類器從候選的特征池中選擇最具有判別力的特征來進行目標跟蹤.

近年來，稀疏表示成為計算機視覺的研究熱點，出現了大量基于稀疏表示的目標跟蹤算法［8－11］.Mei等［12］最早將稀疏表示引入跟蹤領域，提出了L1跟蹤器.該算法在粒子濾波框架下用模板字典對目標建模，通過獨立求解受約束的L1最小化問題得到候選區域在目標字典上的稀疏表示，以重構誤差來判斷當前目標位置.由于L1跟蹤的目標模板是通過對目標區域抖動構建得到，因此其缺點是對于線性表示的稀疏性假設不是在所有情況下都成立.當目標發生較大遮擋或目標快速運動時，候選目標區域在目標字典單位模板對應的系數可能會出現較多的非零元素，目標的整體表示系數將不再稀疏，從而導致目標跟蹤錯誤.

為了在目標遮擋、噪聲干擾及目標快速運動等復雜場景進行魯棒跟蹤，本文將目標的稀疏表示和判別式在線學習相結合，提出了一種基于稀疏表示的判別式目標跟蹤算法.該算法首先采用稀疏表示對目標進行特征提取，得到具有判別力的目標特征表示，然后利用樸素貝葉斯分類器對候選目標進行分類，選取概率最大的樣本作為當前的目標估計.為了適應場景及目標外觀變化，設計動態更新機制對分類器和字典進行了在線更新.和傳統的基于稀疏表示的跟蹤算法相比，本文算法通過目標的稀疏表示獲得具有判別力的目標特征表示，而在線的樸素貝葉斯分類器則確保了目標跟蹤算法的快速有效，克服了基于傳統稀疏表示的跟蹤算法無法在目標發生較大遮擋及快速運動等復雜場景進行魯棒跟蹤的缺點.

1 基于稀疏表示的目標外觀模型

設圖像序列的初始m幀為訓練圖像，T＝［T1，…，Tm］為目標模板集合，其中Ti∈Rd×d.為了構建目標外觀的特征向量，我們采用與文獻［11］類似方法.對于每個目標模板Ti，采用w×w的滑動窗口進行稠密采樣，將得到的所有圖像塊列向量化并進行L2范數歸一化，得到每個目標模板的局部字典Ti＝［t11，…，tM］，聯合所有目標模板，從而得到最終的稀疏編碼字典：

其中，l＝w×w表示圖像塊向量的維度，m表示模板數量，M表示每個模板采樣得到圖像塊的數量.y∈Rd×d是候選目標樣本，那么可以使用上述方法提取該樣本的局部圖像塊，得到候選目標樣本的采樣表示：

根據稀疏表示理論，樣本的局部圖像塊可以由稀疏編碼字典D稀疏表示，可通過求解凸優化問題得到各個圖像塊在字典D中的稀疏編碼：

其中，λ1和λ2為正則化參數.當λ2＝0時，公式（3）為L1范數稀疏編碼，λ2＞0使得公式（3）為嚴格凸優化問題.由公式（3）可得局部圖像塊yi在字典D的稀疏表示：

從而得到候選樣本y∈Rd×d的稀疏編碼為：

通過候選樣本圖像塊與字典中目標模板之間的投票關系，可以獲得候選區域的特征表示.令稀疏字典中每個目標模板對候選樣本的局部圖像塊進行投票，即將局部圖像塊的稀疏系數加權從而得到權重向量，其中為所有目標模板的第j個圖像塊對候選目標的第i個圖像塊的投票權重，C為歸一化參數.因此，可以得到目標模板與候選樣本的投票權重矩陣V＝ ［v1，…，vM］∈RM×M.由于權重矩陣V的對角線表示目標模板圖像塊與對應候選樣本圖像塊之間的投票，因此選取X＝diag（V），X∈RM，為候選樣本的特征向量.

2 基于稀疏表示的判別式目標跟蹤

候選區域中，一個好的候選樣本可以由目標模板字典稀疏表示，其對應的稀疏編碼向量只有幾個大的系數.同樣地，每個局部圖像塊的稀疏編碼向量在其對應位置的目標模板圖像塊上的系數也比較大，那么提取得到的特征向量則對應了這些系數中的大系數，即保留了大部分的能量.而非目標樣本在字典上的表示是稠密的，能量均勻分布在字典空間.因此，目標樣本與非目標樣本在特征向量表示上存在很大差異.在此觀測基礎上，利用判別式在線學習方法，設計分類器在跟蹤過程中將目標與背景區分開來.

2.1 樸素貝葉斯分類器

樸素貝葉斯分類器是一種基于獨立假設貝葉斯定理的簡單概率分類器.樸素貝葉斯分類器假定樣本的各個屬性之間相互獨立，根據少量的訓練數據進行參數估計.盡管變量相互獨立假設現實中難以滿足，但該分類器需要估計的參數少，對缺失數據不敏感，并且有著分類誤差小，簡單高效穩定等特點.

在跟蹤問題中，樣本只有2種類別屬性：目標或背景，是一個二分類問題.假設目標和背景的先驗概率為p（y），y∈｛＋1，－1｝，對于測試樣本X，其類條件概率為p（X｜y），根據貝葉斯公式及最小錯誤率的貝葉斯決策準則可得二元分類器：

若選擇分類器的后驗概率比值作為似然函數可得：

設樣本X包含M 個屬性，即X＝［x1，…，xM］，并且各個屬性之間相互獨立，則有：

若先驗概率p（y＝＋1）＝p（y＝－1），則式（7）可表示為：

利用稀疏表示的外觀模型，目標由特征向量X＝［x1，…，xM］表示.特征向量X＝［x1，…，xM］每個元素代表了目標模板圖像塊與候選樣本對應圖像塊的投票值.假設特征向量各個元素之間相互獨立，且服從高斯分布，則樸素貝葉斯分類器的類條件概率p（X｜y）滿足參數（μ＋i，σ＋i，μ－i，σ－i）高斯分布：

聯合所有特征向量元素的類條件概率得到候選樣本在分類器下的置信值為：

2.2 分類器更新和字典更新

在跟蹤過程中，隨著時間推移以及遮擋、光照、噪聲干擾等因素作用，目標的外觀模型會發生很大變化.因此，為了保證跟蹤的準確性及魯棒性，必須對分類器進行在線更新.對于模板字典更新采用文獻［12］的方法，在跟蹤過程中，使用跟蹤結果圖像塊替換模板字典中重構誤差最大的圖像塊，從而實現字典集合的動態更新.

在t時刻獲得目標位置后，在目標周圍及遠離目標區域分別采樣正負樣本更新分類器.在跟蹤過程中，設置一個動態更新參數δ，采用動態更新機制，每隔δ幀重新訓練分類器.訓練樣本除了來自初始化訓練的靜態訓練樣本庫外，還包括最近δ幀的正負樣本.

2.3 算法步驟

本文的基于稀疏表示的判別式目標跟蹤算法具體描述如下：

輸入：視頻圖像序列 ｛I1，…，In｝，初始目標位置 ｛r1，…，rm｝.

輸出：視頻圖像序列中的跟蹤結果目標矩形框 ｛r1，…，rn｝.

初始化：

1）構造稀疏編碼字典D，

2）獲取訓練樣本｛Xi，yi｝，并將其保留作為靜態訓練樣本.其中Xi∈RM為局部稀疏特征向量，yi∈｛－1，＋1｝為樣本標記，

令 t＝1，…，n，

1）根據設定搜索半徑r采樣目標候選矩形框，稀疏編碼提取得到對應特征向量｛Xi｝，

2）利用樸素貝葉斯分類器L（Xi）計算樣本作為目標置信值li，

4）由當前跟蹤結果獲取動態訓練樣本，判斷是否進行分類器更新.若滿足更新條件，則合并靜態樣本與動態樣本庫，重新訓練分類器，清空動態樣本庫用于收集新的樣本.

3 實驗結果與分析

本文算法在Visual Studio 2010上采用C＋＋和OpenCV實現.跟蹤目標采用矩形框表示，初始狀態在起始幀手動或自動選定.實驗參數設置如下：訓練圖像數量m＝5，目標模板及所有候選樣本均縮放為32×32像素，d＝32，滑動窗口為16×16，w＝16，滑動步長為8個像素；稀疏表示正則化參數λ1＝0.01，目標搜索半徑r＝30，正樣本采樣半徑為2，負樣本圓環為目標矩形框的長邊，樣本數量N＝20，分類器動態更新參數δ＝5.以上參數在實驗過程中對所有視頻序列均固定不變.

實驗在幾組跟蹤領域常用的圖像視頻序列上進行.根據測試視頻的不同挑戰，實驗將測試視頻分為3組，其中：Occlusion1和Girl視頻包含了目標遮擋及外觀變化難點；Animal和Jumping序列挑戰在于目標快速運動及運動模糊；Car4和Car11是汽車尾部跟蹤視頻，其中包含了光照變化、噪聲、外觀變化等挑戰.實驗將本文算法與當前主流的6種算法進行比較：Frag［13］，L1［12］，MIL［14］，PCA［3］，PN［15］，VTD［16］.

3.1 目標遮擋及外觀變化

該組視頻實驗主要針對嚴重遮擋與外觀變化的目標跟蹤.

Occlusion1視頻序列是女子被書本遮擋場景.書本多次從各個不同方向對人臉進行遮擋，遮擋面積最大可達面部可視面積70%.實驗部分結果如圖1（a）所示.其中，第575幀遮擋面積達70%，6種對比算法均出現漂移、被擠壓現象，而本文算法幾乎不受影響.圖2（a）給出7種算法在Occlusion1視頻上的中心誤差.該圖顯示，本文算法的中心誤差是最小的，特別是500～600幀，6種對比算法誤差很大，這一結果顯示本文算法在遮擋條件下的魯棒性.

另一個視頻序列為Girl，該視頻包含女子多次轉動，目標外觀發生巨大變化，同時還包含相似目標遮擋.實驗部分結果如圖1（b）所示.中心誤差分析如圖2（b）所示.實驗結果同樣表明本文算法對比其它6種算法，在目標發生遮擋與外觀變化時具有魯棒性.

圖1 視頻序列跟蹤效果Fig.1 Tracking results of video sequences

3.2 目標快速運動及運動模糊

該組實驗是針對快速運動及運動模糊的目標跟蹤.

Animal視頻序列的主要挑戰在于目標快速運動并且背景中相似目標干擾.實驗部分結果如圖1（c）所示.由42幀實驗結果表明，目標快速跳躍運動時，對比算法明顯漂移甚至丟失目標，而本文算法依然準確跟蹤目標.由圖2（c）的中心誤差分析圖可以看出，6種主流算法中除了VTD算法外均出現較大的中心誤差，跟蹤效果很不理想.而本文算法的中心誤差自始至終都保持在最小，顯示了本文算法對于目標快速運動的魯棒性和準確性.

Jumping視頻序列是男子在室外跳繩，其臉部為跟蹤目標.該視頻的主要難點在于人臉的上下快速運動及其伴隨的運動模糊.實驗部分結果如圖1（d）所示.16幀目標突然跳起，人臉模糊，Frag、L1、VTD均出現漂移.實驗結果顯示，在跟蹤過程中，Frag、L1、VTD和PCA均逐漸丟失目標，而MIL和PN算法則向上或向下漂移，只有本文算法比較準確鎖定目標.中心誤差分析如圖2（d）所示.

3.3 汽車跟蹤視頻

該組實驗是針對汽車尾部進行目標跟蹤.

Car4視頻序列白天車輛跟蹤場景，跟蹤的目標為前方車輛的尾部，其主要挑戰在于目標在行進過程中多次經過路橋陰影區域，帶來光照劇烈變化，同時還存在外觀尺度變化.實驗部分結果如圖1（e）所示.178幀目標第一次進入陰影區域，Frag和MIL出現輕度漂移，194幀目標完全進入陰影區域，PN開始出現漂移，240幀目標離開陰影區域，Frag發生嚴重漂移.304，451和620幀目標發生尺度變化，MIL丟失目標，PN和VTD也出現輕度漂移.整個跟蹤過程中，L1和PCA表現十分穩定，本文算法也取得了相近的跟蹤效果.中心誤差分析如圖2（e）所示.

Car11視頻序列是夜晚車輛跟蹤場景，跟蹤目標也是前方車輛尾部.目標在街道穿行，期間多次發生尺度變化、光照變化及快速運動.同時，跟蹤目標車輛較小，能獲取的信息量較小，跟魯棒跟蹤帶來很大難度.實驗部分結果如圖1（f）所示.目標在60，207幀快速運動，235幀發生尺度變化，MIL發生嚴重漂移，Frag丟失目標，除了本文算法和PCA能穩定跟蹤，其它算法均出現不同程度漂移.目標在300，384幀轉彎快速運動，PCA算法發生漂移，其他5種對比算法均丟失目標，只有本文算法全程準確跟蹤目標.中心誤差分析如圖2（f）所示，與6種流行算法相比，本文算法誤差一直保持最小.

為了更加直觀地對比跟蹤算法的準確性，我們統計了上述7種算法在6個視頻序列上的中心平均誤差，如表1所示.在6個視頻序列測試中，本文算法有3個取得最低評價誤差，2個排在第二以及1個第三，總平均誤差最小.這清楚地表明本文算法在各種挑戰下對目標具有良好的準確性和魯棒性.

圖2 跟蹤結果中心誤差Fig.2 The center position error of sequence

表1 算法平均中心誤差Tab.1 Average center error pixel

4 結 論

本文提出了一種基于稀疏表示的判別式目標跟蹤算法.該算法采用稀疏表示對目標進行特征提取，獲得具有判別力的目標特征表示.在跟蹤過程中利用樸素貝葉斯分類器對候選目標進行分類，選取概率最大的樣本作為當前的目標估計.為了適應場景及目標外觀動態變化，分類器和字典進行了在線更新.該算法將稀疏表示與判別式分類器結合，采用目標的稀疏表示獲得具有判別力的目標特征表示，而在線的樸素貝葉斯分類器則確保了目標跟蹤的快速有效，克服了基于傳統稀疏表示的跟蹤算法無法在目標發生較大遮擋及快速運動等復雜場景進行魯棒跟蹤的缺點.實驗結果表明，與目前流行的多種跟蹤算法相比，本文的算法具有良好的跟蹤魯棒性和準確性.

［1］Black M J，Jepson A D.Eigen tracking：robust matching and tracking of articulated objects using a view－based representation ［J］.International Journal of Computer Vision，1998，26（1）：63－84.

［2］Zhou S K，Chellappa R，Moghaddam B.Visual tracking and recognition using appearance－adaptive models in particle filters［J］.Image Processing，IEEE Transactions on，2004，13（11）：1491－1506.

［3］Ross D，Lim J，Lin R S，et al.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77（1）：125－141.

［4］Collins R T，Liu Y X，Leordeanu M.Online selection of discriminative tracking features［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2005，27（10）：1631－1643.

［5］Wang J Y，Chen X L，Gao W.Online selecting discriminative tracking features using particle filter［J］.IEEE Computer Society Conference on，2005，2：1037－1042.

［6］Avidan S.Ensemble tracking ［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2007，29（2）：261－271.

［7］Grabner H，Bischof H.On－line boosting and vision ［J］.Computer Vision and Pattern Recognition，IEEE Computer Society Conference on，2006，1：260－267.

［8］Bao C L，Wu Y，Ling H B，et al.Real time robust L1 tracker using accelerated proximal gradient approach ［C］∥Computer Vision and Pattern Recognition （CVPR），IEEE Conference on.Providence，RI：IEEE，2012：1830－1837.

［9］Wang Q，Chen F，Xu W L，et al.Online discriminative object tracking with local sparse representation［C］∥Applications of Computer Vision（WACV），2012IEEE Workshop on.Breckenridge，CO：IEEE，2012：425－432.

［10］Zhong W，Lu H C，Yang M H.Robust object tracking via sparsity－based collaborative model［C］∥Computer Vision and Pattern Recognition （CVPR），2012IEEE Conference on.Providence，RI：IEEE，2012：1838－1845.

［11］Jia X，Lu H C，Yang M H.Visual tracking via adaptive structural local sparse appearance model［C］∥Computer Vision and Pattern Recognition（CVPR），2012IEEE Conference on. Providence， RI： IEEE， 2012：1822－1829.

［12］Mei X，Ling H B.Robust visual tracking and vehicle classification via sparse representation ［J］.Pattern A－nalysis and Machine Intelligence，IEEE Transactions on，2011，33（11）：2259－2272.

［13］Adam A，Rivlin E，Shimshoni I.Robust fragments－based tracking using the integral histogram［J］.Computer Vi－sion and Pattern Recognition，2006IEEE Computer Society Conference on，2006，1：798－805.

［14］Babenko B，Yang M，Belongie S.Visual tracking with online multiple instance learning［C］∥Pattern Analysis and Machine Intelligence，IEEE Transactions on.Miami，FL：IEEE，2009：983－990.

［15］Kalal Z，Mikolajczyk K，Matas J.Tracking－learning－de－tection［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2012，34（7）：1409－1422.

［16］Kwon J，Lee K M.Visual tracking decomposition［C］∥Computer Vision and Pattern Recognition （CVPR），2010IEEE Conference on.San Francisco，CA：IEEE，2010：1269－1276.