基于稀疏稠密結構表示與在線魯棒字典學習的視覺跟蹤

袁廣林薛模根

①(解放軍陸軍軍官學院十一系 合肥 230031)

②(解放軍陸軍軍官學院科研部 合肥 230031)

③(合肥工業大學計算機與信息學院 合肥 230009)

基于稀疏稠密結構表示與在線魯棒字典學習的視覺跟蹤

袁廣林*①薛模根②③

①(解放軍陸軍軍官學院十一系 合肥 230031)

②(解放軍陸軍軍官學院科研部 合肥 230031)

③(合肥工業大學計算機與信息學院 合肥 230009)

L1跟蹤對適度的遮擋具有魯棒性，但是存在速度慢和易產生模型漂移的不足。為了解決上述兩個問題，該文首先提出一種基于稀疏稠密結構的魯棒表示模型。該模型對目標模板系數和小模板系數分別進行L2范數和L1范數正則化增強了對離群模板的魯棒性。為了提高目標跟蹤速度，基于塊坐標優化原理，用嶺回歸和軟閾值操作建立了該模型的快速算法。其次，為降低模型漂移的發生，該文提出一種在線魯棒的字典學習算法用于模板更新。在粒子濾波框架下，用該表示模型和字典學習算法實現了魯棒快速的跟蹤方法。在多個具有挑戰性的圖像序列上的實驗結果表明：與現有跟蹤方法相比，所提跟蹤方法具有較優的跟蹤性能。

視覺跟蹤；稀疏表示；稠密表示；字典學習

1 引言

視覺跟蹤是計算機視覺中的基本問題之一，其目的是利用圖像序列自動估計目標狀態。視覺跟蹤在運動分析、視頻監控、車輛導航和人機交互等方面具有重要的應用價值。經過三十多年的研究，已經提出了一些跟蹤方法[1-3]，但是目標遮擋、目標變化、復雜背景和快速性要求等難題使得視覺跟蹤仍是計算機視覺領域的研究熱點，魯棒快速的視覺跟蹤方法還沒有解決。

近年來，基于稀疏表示的視覺跟蹤得到了廣泛關注[4]。受稀疏表示在人臉識別[5]中應用的啟發，2009年，文獻[6]首次將稀疏表示應用到視覺跟蹤中，提出了L1跟蹤。L1跟蹤利用候選目標表示系數的稀疏性提升了子空間跟蹤對目標遮擋的魯棒性，因而受到了廣泛的關注。但是表示系數的稀疏性也導致L1跟蹤的速度較慢，并且易產生模型漂移，尤其是當模板中引入離群數據時會導致跟蹤失敗。針對L1跟蹤的速度問題，文獻[7]利用動態組稀疏提出一種兩階段稀疏優化視覺跟蹤方法，該方法通過降低粒子特征的維數來提高L1跟蹤的效率。文獻[8]提出一種最小化誤差界采樣方法，通過減少L1最小化的求解次數提高L1跟蹤的速度。文獻[9]在L1最小化模型上增加小模板系數的L2范數正則化項，并設計了其快速算法，進一步提升了L1跟蹤的速度與魯棒性，但是它沒有考慮視覺跟蹤中表示系數的特殊稀疏結構。根據粒子在同一模板集上表示系數的相似性，文獻[10]利用多任務稀疏學習聯合求解粒子的表示系數，提高了L1跟蹤的速度。為了適應目標表觀的變化，在跟蹤過程中要更新目標模板。文獻[6,7,10]直接利用跟蹤結果更新目標模板，使得離群數據引入到目標模板中，從而引起跟蹤失敗。針對L1跟蹤的模型漂移問題，文獻[11,12]用正交完備基代替L1跟蹤中的過完備非正交基，提出一種基于小模板系數稀疏性約束的表示模型跟蹤目標，提高了L1跟蹤的魯棒性。文獻[8,9,11]利用小模板系數檢測遮擋，根據檢測結果更新目標模板。文獻[12]根據小模板系數重建目標圖像，利用重建圖像更新目標模板。文獻[8,9,11,12]中模板更新方法的問題在于小模板也能表示跟蹤目標[9]，這時會導致遮擋檢測失敗。文獻[13]利用塊坐標下降優化原理提出了在線字典學習算法。為了解決離群數據對字典學習的影響，文獻[14]提出一種在線魯棒字典學習算法。從字典學習的角度看，模板更新是在線的字典學習問題，所以在線魯棒字典學習為魯棒模板更新提供了思路。

為了提高L1跟蹤的速度，降低模型漂移的發生，本文首先提出一種基于稀疏稠密結構的魯棒表示模型。該模型對小模板系數和目標模板系數分別進行L1范數和L2范數正則化，保證對遮擋目標跟蹤的魯棒性，同時又增強了對離群模板的魯棒性。其次，基于塊坐標優化原理，利用嶺回歸和軟閾值操作快速求解候選目標的表示系數，提高了目標跟蹤的速度。最后，在文獻[13,14]的啟發下，本文提出一種魯棒字典學習算法用于模板更新，進一步降低了模型漂移的發生。在這3個方面的基礎上，本文實現了基于稀疏稠密結構表示與在線魯棒字典學習的快速魯棒跟蹤方法，用多個具有挑戰性的圖像序列驗證了本文跟蹤方法的時效性。

2 稀疏稠密結構魯棒表示模型

L1跟蹤用L1范數正則化最小二乘模型求解候選目標的稀疏表示系數，在粒子濾波框架下，以候選目標在目標模板上的重建誤差作為觀測似然跟蹤目標。L1跟蹤對目標遮擋具有魯棒性的原因在于對表示系數的稀疏性約束。然而表示系數的稀疏性約束給L1跟蹤帶來了兩個不足[4]：一方面，由于一次跟蹤要求解較多L1最小問題，使得L1跟蹤的速度較慢。為了提高L1跟蹤的速度，現有方法[7-10]用低分辨圖像跟蹤目標，降低了目標跟蹤的精度；另一方面，表示系數的稀疏性約束使得L1跟蹤對模板中的離群數據較敏感，當目標模板中引入離群數據時，易發生跟蹤失敗。文獻[15]的研究結果表明：表示系數的稀疏性不是提高人臉識別性能的真正原因，在使用過完備非正交字典表示人臉時，編碼系數的L2范數約束也能保證較好的人臉識別性能。從上述分析可知：為了保證L1跟蹤對目標遮擋的魯棒性，要對小模板系數施加L1范數約束，為了保證L1跟蹤對離群模板的魯棒性，要對目標模板系數進行L2范數約束。據此，本文提出稀疏稠密結構魯棒表示模型，如式(1)所示。

其中y∈Rd是候選目標，T=[t1,t2,…,tn]∈Rd×n是目標模板，I∈Rd×d稱為小模板，是一個單位陣，a稱為目標模板系數，是候選目標y在目標模板T上的表示系數，e稱為小模板系數，是候選目標y在小模板I上的表示系數，||?||1和||?||2分別表示L1范數和L2范數，1λ和2λ是正則化參數。

稀疏稠密結構魯棒表示模型式(1)有以下優點：首先，模型式(1)對小模板系數e進行L1范數約束，使得e具有稀疏性，這保證了對遮擋目標跟蹤的魯棒性。其次，對目標模板系數a進行L2范數約束，使得目標模板系數a具有稠密性，這樣目標跟蹤不依賴于少數幾個模板，而是所有模板共同作用的結果，這提高了跟蹤方法對模板中離群數據的魯棒性，即使模板中存在離群數據仍能穩定跟蹤目標。最后，基于塊坐標優化原理[16]，利用嶺回歸和軟閾值操作可以建立模型式(1)的快速求解算法，從而提高目標跟蹤的速度。

3 稀疏稠密結構魯棒表示快速算法

引理1 給定eopt，則

證明 假如已知eopt，則優化問題式(1)等價于。此問題是L范數2正則化最小二乘問題，目標函數對a求導數并令其等于零，即可得到aopt=(TTT+λ1I)-1TT(y-eopt)。

證畢

引理2 給定aopt，則eopt=Sλ2(y-Taopt)，其中Sτ(x)是軟閾值操作，定義為Sτ(xi)?sgn(xi)?max{|xi|-τ,0}, sgn(?)是符號函數。

證明 假如已知opta，則優化問題式(1)等價于此問題是凸優化問題，由文獻[17]可知，其全局最優解可以通過軟閾值操作Sτ(x)得到，即eopt=Sλ2(y-Taopt) 證畢

由引理1和引理2，并結合塊坐標優化原理[17]可建立如表1所示的迭代算法求解優化問題式(1)的最優解。

我地的畜牧養殖業多集中在農村地區，基層養殖場、養殖戶越來越多，交通的發展幫助養殖戶更好的獲取養殖利潤，但也使得原本局限于某些地區的動物疫病還是蔓延和傳播，甚至在傳播過程中出現突變，為我地基層養殖業造成更大的傷害。農村基層動物防疫部門長期存在經費短缺問題，在動物疫病傳播和突變頻繁的當代，經費短缺問題更加突出，沒有充足的設備、藥品及防疫設施，為農村基層養殖業防疫工作造成極大的負面影響。

表1 稀疏稠密結構魯棒表示快速算法

4 在線魯棒字典學習

其中W是一個對角陣，其值,jjW是y?i的第j個像素的權值，其它符號與式(1)相同。式(2)的求解包括編碼和字典更新兩個階段。在編碼階段，固定字典T求解編碼系數a?i。字典T已知，式(2)是L2范數正則化最小二乘問題，用IR3C(Iteratively Reweighted Regularized Robust Coding)算法[18]求解a?i。在字典更新階段，固定編碼系數a?i更新字典T。由文獻[14]知，可用塊坐標共軛梯度下降算法逐行求解式(3)得到字典T。

表2 在線魯棒字典學習算法

表2 在線魯棒字典學習算法

5 目標跟蹤

5.1 粒子濾波

粒子濾波包括預測和更新兩個步驟。假設y1:k-1={y1,y2,…,yk-1}為1到k-1時刻的所有圖像觀測，xk表示k時刻的目標狀態，則預測過程為

其中p(xk|xk-1)是動態模型。本文采用的動態模型為

其中p(yk|xk)為觀測模型。給定第i個粒子的圖像觀測，本文用算法1求解式(7)。

在此基礎上，定義觀測模型為

5.2 跟蹤方法

以粒子濾波為框架，將動態模型、觀測模型和在線魯棒字典學習相結合建立跟蹤方法如表3所示。

表3 跟蹤方法

6 實驗結果與分析

6.1 實驗說明

以Matlab R2011b為開發工具，在Inter(R) Forth-Core 2.50 GHz CPU, 4G內存的臺式機上，實現了本文提出的跟蹤方法(簡稱L1L2跟蹤)。用4個具有挑戰性的圖像序列[3]對本文L1L2跟蹤進行了實驗驗證，并與IVT跟蹤[1]，L1跟蹤[6]和SP跟蹤[11]進行了比較。實驗中，目標的真實狀態和其它4個跟蹤方法在這4個測試序列上的跟蹤結果由標準測試數據庫得到[3]。本文L1L2跟蹤的粒子數為600，正則化參數λ1和λ2分別是0.001和0.100，模板大小和個數分別為32×32和16，每隔5幀進行一次模板更新。

6.2 實驗結果

圖1給出了4個跟蹤方法對4組測試序列的跟蹤結果。faceocc1序列存在較大的目標遮擋，由于圖1(a)可以看出，對于faceocc1序列，本文L1L2跟蹤和L1跟蹤的結果較優。david序列存在光照變化、out-plane旋轉和尺度變化等諸多挑戰，從圖1(b)可以看出，對于david序列，本文L1L2跟蹤和SP跟蹤的結果優于其它兩種跟蹤方法。car4序列存在較大光照和尺度變化，由圖1(c)可以看出，對于car4序列，本文L1L2跟蹤、IVT跟蹤和SP跟蹤能夠穩定跟蹤目標，但是L1跟蹤發生了跟蹤漂移。jogging序列存在運動模糊、遮擋和變形等困難，從圖1(d)可以看出，對于jumping序列，本文L1L2跟蹤能夠穩定地跟蹤目標，其它跟蹤方法均發生了失敗。

本文利用跟蹤成功率曲線下面積和成功率均值定量評價跟蹤方法的性能[3]。假設目標的真實矩形區域和目標的跟蹤結果矩形區域分別是ra和rt，則重疊得分定義為：，其中∩和∪分別表示區域的交集和并集。如果跟蹤方法在一幀圖像上的重疊得分S大于重疊閾值t0時，則認為該跟蹤方法在這一幀圖像上跟蹤成功。據此定義跟蹤方法在一個圖像序列上的跟蹤成功率為成功跟蹤的圖像幀數與序列圖像總幀數的比值。給定一系列重疊閾值即可得到跟蹤成功率曲線和成功率均值。圖2和表4分別給出了4種跟蹤方法在4個圖像序列上的跟蹤成功率曲線和成功率均值，由圖2和表4可以看出，本文提出的L1L2跟蹤方法優于其它3個跟蹤方法。

表4 跟蹤成功率均值

假設U∈Rd×n是IVT跟蹤和SP跟蹤使用的特征基，T∈Rd×n是L1跟蹤使用的目標模板，P∈Rd×n是算法1中的投影矩陣，k1是文獻[11]中算

6.3 復雜性分析法1的迭代次數。由文獻[1,6,11]可知，IVT跟蹤，L1跟蹤和SP跟蹤的計算復雜度如表5所示。本文L1L2跟蹤最耗時部分是用投影矩陣計算表示系數(算法1中的步驟3)，該計算是矩陣向量乘，其時間復雜度是O(k2dn)，其中，k2是算法1中的迭代次數。由上述分析可知：這4個跟蹤方法的計算復雜度級別相同，都是變量多項式的復雜度。表5中第3和4列分別給出了在相同軟硬件環境下，d=16×16和d=32×32，n=16時，求解一個樣本表示系數的計算時間，可以看出，本文L1L2跟蹤的速度比IVT跟蹤慢，但是快于SP跟蹤和L1跟蹤。

圖1 目標跟蹤結果

表5 計算復雜度與計算時間(ms)

6.4 討論

與本文最相近的方法是SP跟蹤[11]，它們均繼承了L1跟蹤[6]對小模板系數的稀疏性約束，這保證了對遮擋目標跟蹤的魯棒性。但是本文方法與SP跟蹤有以下不同。第一是使用的模板基不同，本文方法用過完備基表示目標，SP跟蹤用正交基表示目標。過完備基比正交基具有更優的表示能力已在人臉識別中[4]得到證實。第二是模板更新方法不同，本文方法用過完備基表示目標，可以用在線魯棒字典學習算法更新模板，這抑制了離群數據對模板更新的影響，從而降低“模型漂移”的發生。SP跟蹤用正交基表示目標并用增量主分量分析[1]更新特征基，不可避免地會引起“模型漂移”，從而降低目標跟蹤的精度，甚至導致跟蹤失敗。圖3和圖4分別給出了SP跟蹤的模板更新方法與本文模板更新方法對faceocc1序列跟蹤在第600幀時的模板更新結果，可以看出，與SP跟蹤的模板更新方法相比，本文模板更新方法的結果受離群數據的影響較小。第三是本文方法對目標模板系數進行L2范數約束，提高了對模板中離群數據的魯棒性，即使模板中存在離群數據仍能穩定跟蹤目標。正是由于上述3個方面的原因，使得本文方法的跟蹤精度優于SP跟蹤。

圖2 跟蹤成功率曲線

圖3 SP模板更新結果

圖4 本文方法模板更新結果

7 結論

本文提出一種稀疏與稠密結構表示模型，用于解決L1跟蹤存在的速度慢和易受離群數據干擾的不足。對小模板系數進行L1范數約束保證了對遮擋目標跟蹤的魯棒性，對目標模板系數進行L2范數約束解決了L1跟蹤易于受離群數據干擾的問題。基于塊坐標優化原理，利用嶺回歸和軟閾值操作設計了稀疏與稠密結構表示快速求解算法，提高了目標跟蹤的速度。本文提出在線魯棒字典學習算法實現模板更新，減小了離群數據對模板更新的影響，降低了模型漂移的發生。以粒子濾波為框架實現了基于稀疏稠密結構表示與在線魯棒字典學習的的跟蹤方法，在多個圖像序列上的實驗結果表明，本文跟蹤方法優于現有跟蹤方法。

[1] Ross D, Lim J, Lin R S, et al.. Incremental learning for robust visual tracking[J]. International Journal of Computer Vision, 2008, 77(1/2/3): 125-141.

[2] Kwon J and Lee K M. Visual tracking decomposition[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, 2010: 1269-1276.

[3] Wu Yi, Lim Jongwoo, and Yang Ming-hsuan. Online object tracking: a benchmark[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Portland, 2013: 2411-2418.

[4] Zhang Sheng-ping, Yao Hong-xun, Sun Xin, et al.. Sparse coding based visual tracking: review and experimental comparison[J]. Pattern Recognition, 2013, 46(7): 1772-1788.

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

[6] Mei X and Ling H B. Robust visual tracking using L1minimization[C]. Proceedings of IEEE InternationalConference on Computer Vision, Kyoto, 2009: 1436-1443.

[7] Liu Bai-yang, Yang Lin, Huang Jun-zhou, et al.. Robust and fast collaborative tracking with two stage sparse optimization[C]. Proceedings of Europe Conference on Computer Vision, Crete, 2010, Part IV: 624-637.

[8] Mei X, Ling H B, Wu Y, et al.. Minimum error bounded efficient L1tracker with occlusion detection[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Colorado, 2011: 1257-1264.

[9] Bao Cheng-long, Wu Yi, Ling Hai-bin, et al.. Real time robust L1tracker using accelerated proximal gradient approach[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Rhode Island, 2012: 1830-1837.

[10] Zhang Tian-zhu, Bernard Ghanem, Liu Si, et al.. Robust visual tracking via multi-task sparse learning[J]. International Journal of Computer Vision, 2013, 101(2): 367-383.

[11] Wang Dong, Lu Hu-chuan, and Yang Ming-hsuan. Online object tracking with sparse prototypes[J]. IEEE Transactions on Image Processing, 2013, 22(1): 314-325.

[12] Wang Dong, Lu Hu-chuan, and Yang Ming-hsuan. Least soft-thresold squares tracking[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Portland, 2013: 2371-2378.

[13] Mairal J, Bach F, Ponce J, et al.. Online learning for matrix factorization and sparse coding [J]. Journal of Machine Learning Research, 2010(11): 19-60.

[14] Lu Ce-wu, Shi Jian-ping, and Jia Jia-ya. Online robust dictionary learning[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Portland, 2013: 415-422.

[15] Zhang Lei, Yang Meng, and Feng Xiang-chu. Sparse representation or collaborative representation: which helps face recognition?[C]. Proceedings of IEEE International Conference on Computer Vision, Colorado, 2011: 471-487.

[16] Tseng Paul and Yun Sangwoon. A block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization[J]. Optimization Theory Application, 2009, 140(3): 513-535.

[17] Yang A Y, Ganesh A, Zhou Zi-han, et al.. A review of fast L1-minimization algorithms for robust face recognition[J]. IEEE Transactions on Image Processing, 2013, 22(8): 3234-3246.

[18] Yang Meng, Zhang Lei, Yang Jian, et al.. Regularized robust coding for face recognition[J]. IEEE Transactions on Image Processing, 2013, 22(5): 1753-1766.

袁廣林： 男，1973年生，博士，講師，主要研究方向為圖像處理、計算機視覺、機器學習及其應用等.

薛模根： 男，1964年生，博士，教授，博士生導師，主要研究方向為圖像處理、計算機視覺、光電防御等.

Visual Tracking Based on Sparse Dense Structure Representation and Online Robust Dictionary Learning

Yuan Guang-lin①Xue Mo-gen②③①(Eleventh Department, Army Officer Academy of PLA, Hefei 230031, China)
②(Department of Scientific Research, Army Officer Academy of PLA, Hefei 230031, China)
③(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

The L1trackers are robust to moderate occlusion. However, the L1trackers are very computationally expensive and prone to model drift. To deal with these problems, firstly, a robust representation model is proposed based on sparse dense structure. The tracking robustness is improved by adding an L2norm regularization on the coefficients associated with the target templates and L1norm regularization on the coefficients associated with the trivial templates. To accelerate object tracking, a block coordinate optimization theory based fast numerical algorithm for the proposed representation model is designed via the ridge regression and the soft shrinkage operator. Secondly, to avoid model drift, an online robust dictionary learning algorithm is proposed for template update. Robust fast visual tracker is achieved via the proposed representation model and dictionary learning algorithm in particle filter framework. The experimental results on several challenging image sequences show that the proposed method has better performance than the state-of-the-art tracker.

Visual tracking; Sparse representation; Dense representation; Dictionary learning

TP391.4

A

1009-5896(2015)03-0536-07

10.11999/JEIT140507

2014-04-17收到，2014-06-30改回

國家自然科學基金(61175035, 61379105)資助課題

*通信作者：袁廣林 yuanguanglin1008@sina.com