基于局部稀疏表示的目標跟蹤算法

程中建 李康 徐龍香

摘要：目標跟蹤是計算機視覺領域重要的研究方向之一。基于l1最小化稀疏表示的目標跟蹤算法跟蹤精度高，但是在跟蹤部分遮擋目標或當背景中存在與目標相似的干擾物時會發生漂移。這主要是因為算法僅關注目標的整體特征，而忽略了目標局部特征的變化情況。為了解決該問題，提出基于目標外觀局部稀疏表示的跟蹤算法。首先，對待選樣本進行分塊，然后利用采集得到的模板對各分塊進行稀疏表示并計算重構誤差，最后選取累積誤差最小的待選樣本作為跟蹤目標。實驗結果表明，該算法在跟蹤被部分遮擋的目標時相比l1跟蹤算法有更高的準確度。

關鍵詞：目標跟蹤；稀疏表示；l1算法；分塊策略；生成模型

DOIDOI：10.11907/rjdk.181568

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2018）008-0106-04

英文摘要Abstract：Object tracking is one of the most important research areas in computer vision.The object tracking algorithm based on l1 sparse representation minimization has high tracking accuracy.However，when the object is partially occluded or the environment is similar to the object，the tracker may drift.This is mainly because the algorithm only focuses on the overall characteristics of the object and ignores the changes of the local characteristics of the object.In order to solve this problem，we propose a tracking algorithm based on the local sparse representation.Firstly，the candidate sample is divided into several overlaped blocks.Then，we employ each block using the collected templates to calculate reconstructive error.Finally，the candidate sample with the smallest reconstructive error is selected as the target.Experimental results show that our algorithm has higher accuracy than l1 tracker when tracking partially occluded objects.

英文關鍵詞Key Words：object tracking； sparse representation； l1algorithm； block strategy； generative model

0 引言

目標跟蹤是計算機視覺領域重要研究課題之一。在交通導航、虛擬現實、視頻監控、無人機飛行等領域應用廣泛。近年來，國內外大量跟蹤算法被開發出來[1-6]。但由于受到目標外觀變化、目標局部遮擋和目標信息缺失等眾多干擾因素影響，開發出魯棒性的跟蹤算法仍然面臨巨大挑戰。

按照外觀模型的不同，現有目標跟蹤算法可以分為兩類：生成式模型和判別式模型。判別式算法模型[7-11]將目標跟蹤視為二值分類問題，通過使用采樣得到的正樣本和負樣本訓練分類器分離目標與背景，然后選擇具有最大分類響應值的待選樣本作為跟蹤結果。文獻[8]提出了一種基于在線增強方法更新判別特征的目標跟蹤算法。在此基礎上，文獻[9]提出一種半在線算法處理跟蹤漂移問題。多實例目標跟蹤（MIL）[10]使用在線Boosting算法訓練分類器處理非線性分類問題。邸男等[11]利用棱錐面方程的單峰特性并結合似然相似度函數提高目標與背景的區分度。判別式算法在跟蹤復雜環境中的目標時會得到魯棒性結果，但在處理外觀變化不大的目標時往往會丟失目標。

生成式算法模型[12-17]通過訓練樣本學習目標外觀模型，然后在候選樣本中選擇重構誤差最小的樣本作為跟蹤結果。Adam等[12]提出使用多尺度灰度直方圖表示目標特征。Mei等[13-14]利用目標整體特征建模外觀模型，通過求解l1最小化問題選擇具有最小重構誤差的候選樣本作為跟蹤目標。Liu等[15]結合稀疏表示思想和均值漂移模型，提出了一種基于局部稀疏表示的目標跟蹤算法。周等[16]提出了幀間差分與局部Camshift的跟蹤算法解決運動目標提取后存在的”空洞”現象。Zhang等[17]通過將跟蹤過程建模為多任務稀疏學習問題，提出了一種協同跟蹤算法。與判別式跟蹤算法不同，基于生成式模型的算法具有較高的跟蹤精確度，但是在目標環境較為復雜時跟蹤結果不夠魯棒。

基于l1最小化稀疏表示的目標跟蹤算法[13]跟蹤精度高、跟蹤速度快，但是該算法在跟蹤被遮擋的目標時容易發生漂移，主要因為該算法僅考慮了目標的整體外觀而忽略了目標被遮擋部分的外觀。為解決該問題，本文提出一種基于局部稀疏表示的目標跟蹤算法。首先，將目標樣本分割成多個有部分重疊的局部區域；然后針對每個局部區域分別進行稀疏表示，計算重構誤差；最后選擇累積誤差最小的候選樣本作為跟蹤結果。算法在考慮目標整體外觀特征的同時，結合目標局部信息，解決被遮擋目標的跟蹤問題，提高跟蹤的魯棒性。

1 局部稀疏表示跟蹤算法實現

近年來，基于生成式模型的稀疏表示方法被應用于目標跟蹤，取得了魯棒的跟蹤效果[13-15，18]。該算法使用模板稀疏表示目標的整體外觀模型，并根據最小化l1選取具有最小重構誤差的待選樣本作為跟蹤結果。但是，這類算法僅考慮了目標整體的外觀模型，忽略跟蹤目標的局部結構信息，因此在利用l1最小化計算被部分遮擋的待選樣本時會產生較大的重構誤差，導致這類算法在跟蹤被部分遮擋的目標時容易丟失目標。

為了改進稀疏表示算法（簡稱L1算法）存在的問題，提出一種局部分塊稀疏表示的跟蹤策略。如圖1所示，首先對所有樣本進行分塊處理，然后使用稀疏表示計算每一個分塊的重構誤差，最后選擇具有最小累積誤差的待選樣本作為跟蹤結果。分塊稀疏表示的策略綜合考慮了目標整體外觀和局部外觀信息，相較于L1算法在處理目標部分遮擋等問題時具有更高精準度。

1.2 模板更新

為了適應目標背景受非確定因素影響發生的變化，算法應及時更新各分塊區域對應的模板集。如果模板更新過快，模板的重構誤差將會不斷積累，進而導致跟蹤結果發生偏移，與此相反，如果模板更新太慢或模板固定不變，將不能準確表達目標外觀模型，最終丟失目標。

2.3 實驗結果分析

從表1、表2（最好結果由粗體標出）可以看出，本文提出的算法與其它經典算法相比具有較好的跟蹤效果。結合圖2，根據所選測試跟蹤序列特點進行具體分析。

（1）Basketball。該測試跟蹤序列中由于目標區域存在大面積背景區域，如目標頭部兩側及腿部之間的區域，目標整體外觀模型隨背景變化，造成跟蹤困難。跟蹤過程中，VTD、L1分別在第33、351幀丟失目標，MIL在第351幀時偏移到非目標上，只有本文算法能夠準確跟蹤目標。測試結果表明，本文算法在光照變化和背景復雜的跟蹤環境中能夠準確跟蹤。

（2）Dudek。該測試視頻序列為室內環境，由于目標姿勢和運動變化，目標外觀模型劇烈改變，造成跟蹤困難。跟蹤過程中，MIL在第214幀發生漂移，L1、VTD、Ours均能夠準確跟蹤到目標。

（3）Woman。該測試視頻在目標經過汽車時，目標遮擋面積約為其總面積的2/3，遮擋過程持續時間近60幀。由于無法處理目標被部分遮擋的區域，第126幀時，L1漂移到車輛上，MIL與VTD丟失跟蹤目標。本文算法由于運用分塊策略，能夠對目標分塊區域分別處理，再由稀疏表示計算出的重構誤差從局部角度分析目標是否存在遮擋，避免L1算法中整體外觀模型產生的不足。本算法不更新存在嚴重遮擋的分塊對應的模板集，最大限度上降低了由于更新產生的誤差累積，使算法能夠準確針對目標的各塊外觀建模。跟蹤結果驗證了本算法能夠準確跟蹤部分遮擋的目標。

（4）David2。在該視頻中，跟蹤目標區域較小、目標與背景區域局部相似造成跟蹤難點。L1、MIL分別在第28、198幀時發生漂移，并在第537幀完全丟失目標，僅VTD與本文算法能夠較準確跟蹤到目標。

（5）David3。該測試視頻中，目標被樹木大面積遮擋。L1，MIL均在第90幀丟失目標，VTD在103幀丟失目標，而由于本文算法采用了分塊策略處理目標存在的部分遮擋問題，因此能夠準確地跟蹤到目標。

3 結語

本文通過分析傳統L1算法中目標整體稀疏表示存在忽略跟蹤區域局部信息的缺陷，提出了一種基于局部分塊稀疏表示的目標跟蹤算法。通過對目標區域進行分塊處理，可以對各分塊單獨運用稀疏表示求解重構誤差，并以此判斷目標當前是否處于被遮擋狀態。在模板更新時，提出不更新重構誤差較大的分塊，避免被遮擋的目標模板污染模板集，提高了算法的魯棒性。利用分塊思想對L1算法忽略的局部信息加以利用，使算法能夠處理更加復雜的跟蹤環境。本文算法將分塊稀疏表示理論應用于目標跟蹤，探討了局部重構誤差對跟蹤結果的影響，加深了對多模塊聯合稀疏表示方法的認識，豐富了稀疏表示在目標跟蹤中的理論應用。實驗結果表明，該算法在跟蹤被部分遮擋的目標時，相比其它經典跟蹤算法有更高的準確度。在未來工作中，將在現有研究基礎上結合深度特征對目標進行跟蹤。

參考文獻：

[1] DANELLJAN M，SHAHBAZ KHAN F，FELSBERG M，et al.Adaptive color attributes for real-time visual tracking[C].IEEE Conference on Computer Vision and Pattern Recognition，2014：1090-1097.

[2] ZHANG T，JIA K，XU C，et al.Partial occlusion handling for visual tracking via robust part matching[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition，2014：1258-1265.

[3] 王宇霞，趙清杰，蔡藝明，等.基于自重構粒子濾波算法的目標跟蹤[J].計算機學報，2016，39（7）：1294-1306.

[4] 姜文濤，劉萬軍，袁姮，等.視覺量子目標跟蹤方法[J].軟件學報，2016，27（11）：2961-2984.

[5] 黃慶俊，何儒漢.基于協方差矩陣的壓縮感知跟蹤算法[J].軟件導刊，2017，16（4）：31-35.

[6] LIU Q，YANG J，ZHANG K，et al.Adaptive compressive tracking via online vector boosting feature selection[J].IEEE Transactions on Cybernetics，2017，47（12）：4289-4301.

[7] AVIDAN S.Ensemble tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29 （2）：261-271.

[8] GRABNER H，BISCHOF H.On-line boosting and vision[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006，1：260-267.

[9] GRABNER H，LEISTNER C，BISCHOF H.Semi-supervised on-line boosting for robust tracking[C].European Conference on Computer Vision，2008：234-247.

[10] BABENKO B，YANG M H，BELONGIE S.Visual tracking with online multiple instance learning[C].IEEE Conference on Computer Vision and Pattern Recognition，2009：983-990.

[11] 邸男，朱明，韓廣良.似然相似度函數在目標跟蹤中的魯棒機理研究[J].軟件學報，2015，26（1）：52-61.

[12] ADAM A，RIVLIN E，SHIMSHONI I.Robust fragments-based tracking using the integral histogram[C].2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006，1：798-805.

[13] MEI X，LING H.Robust visual tracking using 1 minimization[C].2009 IEEE 12th International Conference on Computer Vision，2009：1436-1443.

[14] MEI X，LING H，WU Y，et al.Minimum error bounded efficient 1 tracker with occlusion detection[C].2011 IEEE Conference on Computer Vision and Pattern Recognition，2011：1257-1264.

[15] LIU B，HUANG J，YANG L，et al.Robust tracking using local sparse appearance model and k-selection[C].2011 IEEE Conference on Computer Vision and Pattern Recognition，2011：1313-1320.

[16] 周文靜，陳瑋.基于改進幀間差分與局部Camshiift相結合的目標跟蹤算法[J].軟件導刊，2018，17（3）：68-70.

[17] ZHANG T，GHANEM B，LIU S，et al.Robust visual tracking via multi-task sparse learning[C].2012 IEEE Conference on Computer Vision and Pattern Recognition，2012：2042-2049.

[18] LIU B，YANG L，HUANG J，et al.Robust and fast collaborative tracking with two stage sparse optimization[C].European Conference on Computer Vision，2010：624-637.

[19] KWON J，LEE K M.Visual tracking decomposition[C].2010 IEEE Conference on Computer Vision and Pattern Recognition，2010：1269-1276.

[20] WU Y，LIM J，YANG M H.Online object tracking：a benchmark[C].2013 IEEE Conference on Computer Vision and Pattern Recognition，2013：2411-2418.

（責任編輯：江 艷）