基于L2范數最小化聯合模型的目標跟蹤算法

王蒙，吳毅，鄧健康，劉青山

(南京信息工程大學 信息與控制學院，南京210044)

目標跟蹤是計算機視覺領域的研究熱點之一，在視覺監控、視頻壓縮編碼、醫學診斷、三維重構以及人機交互等方面有著大量的應用［1-2］.目標在運動過程中會受到光照變化、尺度變化、遮擋、旋轉等因素的影響，這些給目標跟蹤帶來了挑戰.針對這些難點，學者們提出了大量的跟蹤算法，也取得了一定的研究進展.目標跟蹤方法一般可以分為2大類:基于判別式模型的跟蹤和基于生成式模型的跟蹤［3］.基于判別式模型的跟蹤算法將跟蹤問題看作一個二分類問題，通過設計一個魯棒的分類器區分出目標和背景.比較典型的算法有在線Boosting跟蹤［4-5］、在線多實例學習跟蹤［6-7］和集成跟蹤［8］等.基于生成式模型的跟蹤算法通過在鄰域中尋找與目標相似度最大的區域作為所要跟蹤的目標，比較主流的方法有增量學習跟蹤算法［9］、均值漂移(mean shift)跟蹤算法［10］和 Eigentracker［11］等.

近年來，稀疏表示被廣泛地應用于計算機視覺領域.受到Wright等提出的基于稀疏表示人臉識別方法的啟發［12-13］，Mei和Ling將稀疏表示運用到目標跟蹤中，在粒子濾波的框架下，對每個候選目標用一組由目標模板和單位模板組成的基向量進行線性表示，并利用L1范數最小化進行求解得到候選目標的稀疏表示，之后利用稀疏表示的重構誤差作為候選目標的權重，將最大權重的候選目標選為跟蹤結果［14］.然而，L1跟蹤器存在一些不足，一個缺點是對線性表示的稀疏性假設并不是在任何情況下都成立，當候選樣本是背景區域或者發生部分遮擋時，因為單位模板可以表示任意塊，候選樣本用目標模板和單位模板線性表示時，單位模板的系數不再為零，從而整個系數不再稀疏，這樣求解L1范數最小化就不合理;另一個缺點是計算復雜度高，L1跟蹤器要對每個候選樣本求解一次L1范數最小化，每一次求解都比較耗時.在粒子濾波中，候選樣本的個數通常比較多，求解大量的L1范數最小化會大大增加算法的計算時間，影響算法的實時性.

針對以上問題，為了提高算法的性能，大量學者探討運用不同的方法把稀疏表示用于目標跟蹤中.Mei等將一種結構化的稀疏表示模型用于視覺跟蹤算法中［15］;Bao等提出將加速近似梯度(APG)方法用于求解 L1范數最小化問題［16］;Zhang等提出一種多任務稀疏學習方法來改進跟蹤算法［17］.在這期間，人臉識別領域的一些研究者用L2范數最小化代替L1范數最小化進行實驗［18］，取得了和原來算法接近或者更高的識別率，同時計算復雜度遠低于L1范數最小化.基于此，2012年，Xiao等提出了一種快速有效的基于L2正則化的目標跟蹤算法，用PCA基向量和分塊模板來建立目標的表觀模型，再通過L2范數最小化來求解，在不損失精度的情況下大大提高了算法的計算速度［19］.但這種方法沒有考慮背景信息，在某些測試視頻上會出現漂移現象，也沒有采取有效的遮擋處理機制，在發生部分遮擋或全部遮擋時會導致跟蹤失敗.

針對該算法存在的問題，本文提出了一種基于L2范數聯合模型的目標跟蹤算法.該聯合模型結合了基于全局模板的判別式模型和基于局部描述子的生成式模型，一方面利用全局模板來區分目標和背景，另一方面利用局部信息來處理遮擋，充分利用這2種模型的優點提高了跟蹤的魯棒性.本文的算法利用L2范數最小化求解目標表觀的系數，計算過程比L1范數最小化簡單，大大降低了計算的復雜度.模型更新上，判別式模型中每隔若干幀更新正負模板集，獲得最新準確的目標和背景信息，使得判別式模型具有適應性和辨別性;生成式模型中通過設定一個遮擋閾值，判斷每幀的遮擋程度來決定是否更新模板的系數向量，從而更新目標的表觀模型，使得跟蹤器能夠適應新的目標狀態.

1 基于L2范數最小化的表觀模型

目標表觀模型是跟蹤器的重要組成部分，用來描述目標表觀的特征.基于判別式模型的表觀模型用來區分目標和背景;基于生成式模型的表觀模型用來描述目標本身，提取出目標的特征.本文合理地融合了判別式模型和生成式模型來對目標進行描述，并利用L2范數最小化對目標表觀系數進行求解，取得了比較好的結果.

1.1 基于L2范數最小化的判別式模型

訓練集 U=［U1，U2，…，Um+n］∈Rd×(m+n)，包括m個正模板U+∈Rd×m和n個負模板U－∈Rd×n.在初始位置周圍手動采集m個圖像，歸一化后按行堆成向量作為正模板;在離初始位置較遠處采集n個圖像，利用同樣的方法得到負模板.其中初始位置是通過在第一幀中手動標注得到的.采集到的候選樣本y∈Rd可以通過訓練集線性表示，即

其中，b=［b1，b2，…，bm+n］T∈R(m+n)×1，為線性表示的系數.b是弱稀疏的，利用這一特征通過L2范數最小化進行求解，其中λ為約束參數.

L2范數約束項的作用有2個:①它使解b具有一定的稀疏度，但是L2范數的稀疏度遠低于L1范數的稀疏度.②它使得最小化的解更加穩定.L2范數最小化很容易求解，令的導數為0，即2(－UT)(y－Ub)+2λb=0，可得出:

其中I∈Rd×d，是一個單位矩陣，用來確保UTU+λI的可逆性.

令 P=(UTU+λI)－1UT，很顯然，P 是獨立于y的，所以對于通過粒子濾波得到的候選樣本只需要計算一次P.如果把所有的候選樣本看作一個向量集Y，則所有候選樣本的表觀系數可以一次性求得:

假設一個候選樣本在前景模板上有比較小的重構誤差就代表該候選樣本有可能是目標，在背景模板上有比較小的重構誤差就代表這個候選樣本有可能是背景，在此基礎上根據候選樣本在前景模板和背景模板上的重構誤差的差異來構造候選樣本的置信值:

其中ρ是一個很小的固定的常數，用來權衡判別分類器的重要性.

1.2 基于L2范數最小化的生成式模型

本文在考慮圖像塊的位置信息和遮擋因素的基礎上，提出了一種生成式模型.對于所有的候選樣本利用分塊的方法形成N個圖像塊，如圖1所示.本文在實驗部分將每個圖像塊變成一個向量yi∈Rd×1，表示圖像塊的大小.利用 L2 范數最小化來求解每個圖像塊的系數向量:

其中，D∈Rp×q，為通過k均值聚類的方法得到的字典;q為聚類中心的個數;p為聚類中心的維數.聚類的圖像塊是在第一幀中通過與yi相同的方法得到的，其中q個聚類中心表示最具有代表性的圖像塊.把所有的系數向量γi串聯在一起得到γ:

其中，γ∈R(q×N)×1，為一個候選樣本的系數向量.通過這種串聯方式，系數向量就包含了圖像塊的空間信息.

圖1 利用分塊得到的圖像塊Fig.1 Image blocks by the sliding window

對于遮擋問題，被遮擋的圖像塊會影響系數向量的比較，因為遮擋部分和模板之間存在很大的差異，這會使得誤差大于候選樣本本身的誤差，所以本文通過設定一個閾值來判斷圖像塊是否被遮擋.當重構誤差比較大時，認為該圖像塊被遮擋，把這個圖像塊的權重設為0;當重構誤差比較小時，認為圖像塊沒有被遮擋，把這個圖像塊的權重設為1.通過去除被遮擋的圖像塊，只對有價值的目標塊比較系數向量，可以避免錯誤的跟蹤結果.這可以通過下式來描述:

其中，σ為系數向量中每個元素的權重，根據σi的值將第i個系數向量的所有元素的權重全部設為0或1.通過比較候選樣本系數向量和模板系數向量的相似性，得出置信值G:

其中，ε，θ分別為候選樣本和模板歸一化到(0，1］的系數向量;G為候選樣本和模板的相似度，其中初始時模板的系數向量是在第一幀中通過和候選樣本系數向量一樣的方法求得.

1.3 聯合模型

在粒子濾波的框架下，本文融合判別式模型和生成式模型構造了一個新的聯合模型，用乘法機制得到一個新的似然函數表達式:

這一似然函數既能夠區分前景和背景，也能夠處理目標遮擋問題.將本節的表觀模型和后文的運動模型結合起來，得到了一個高效、魯棒的跟蹤器.

2 基于L2范數最小化的跟蹤算法

目標跟蹤問題可以看成是運動目標的狀態推斷問題.在貝葉斯理論的框架下，利用狀態的先驗概率和觀測量，構造狀態的后驗概率密度:

2.1 目標運動模型

運動模型是用來描述目標在連續幀之間的運動狀態的改變，本文采用幀間的幾何變換的Xt=(αt，βt，θt，st，εt，φt)來近似表示 t時刻目標的運動狀態，其中 αt，βt，θt，st，εt，φt分別表示 α 方向的平移、β方向的平移、旋轉角、尺度變化、寬高比和斜切角.根據隨機游走模型來描述目標的運動狀態，即當前時刻的目標運動狀態以上一時刻的狀態為中心呈多元正態分布:

2.2 目標觀測模型

觀測模型的目的則是從運動模型得到的大量候選樣本中找到要跟蹤的目標.給定粒子xit，當前時刻的觀測量yit，結合基于L2范數最小化的目標表觀模型，可以得到觀測似然函數:

2.3 模型更新策略

在跟蹤過程中，目標的表觀不斷發生變化，所以適時地更新判別式模型中的正負模板是非常必要的.本文每隔若干幀更新正模板和負模板，更新的圖像是當前跟蹤結果附近的區域，正負模板的獲得方法和2.1節中的方法一樣.這樣得到的模板使得判別式模型具有很強的適應性和辨別度.

對于生成式模型中的模板的系數向量，按照下式進行更新:

其中，η為更新率;θ1為第一幀的系數向量;εi為最新一幀得到的系數向量.當遮擋程度Oi小于設定的閾值O0時，進行更新，反之則不進行更新.這種更新機制考慮了遮擋的同時又更新了目標的表觀模型，跟蹤器能夠適應新的環境和新的目標狀態.總體流程如圖2所示.

圖2 總體流程圖Fig.2 Overall flow chart

3 實驗結果與分析

本文提出的跟蹤方法采用Matlab進行了實現，并且與 Frag［20］，VTD［21］，IVT［9］，MIL［7］這 4 種經典的算法以及L2RLS［19］跟蹤算法進行了比較，在8個具有挑戰性的測試序列［1，22］中對比實驗，并作了定性和定量的分析.實驗過程中，判別式模型中正負模板的個數分別設置為70和250;式(2)和式(6)中的 λ分別設置為 0.001和0.005;式(6)中字典D行數和列數分別設置為25和40;式(8)中的閾值σ0設置為0.03;式(16)中的更新率η和閾值O0分別設為0.9和0.8.

3.1 定性評估

第1個測試序列cardark如圖3(a)所示，存在著前景背景的對比度低、較大的光照變化等干擾，同時目標相對于整個圖像的尺寸是比較小的.Frag跟蹤器一直不穩定，在跟蹤過程中出現了不同程度的漂移，這是因為Frag跟蹤器基于局部信息，沒有維持全局信息.因此，當目標尺度很小且分辨率很低時，很難進行跟蹤.MIL算法在跟蹤開始沒多久就開始發生漂移直至跟蹤失敗.在260幀之前，IVT算法、VTD算法、L2RLS算法和本文算法都能夠跟蹤到目標，但之后IVT跟蹤結果的矩形框不斷變大，無法對準目標，L2RLS算法和VTD算法很快就丟失了目標.本文算法在整個圖像序列中都能夠比較好地進行跟蹤，是因為基于判別式模型的跟蹤器能夠很好地區分前景和背景，再通過更新機制獲得最新的正負樣本構成正負樣本集，這有助于在變化著的凌亂的場景中區分出前景和背景.

第2個測試序列mhyang如圖3(b)所示，存在著光照變化、運動模糊并伴隨著尺度變化等干擾.MIL算法由于沒有考慮尺度變化，跟蹤結果在第369幀時就開始發生漂移.在第420幀受到光照干擾時，L2RLS算法的跟蹤框越來越小，逐漸丟失目標.VTD算法在整個序列中的跟蹤結果不夠穩定，有時出現漂移但后來又會跟蹤上目標.IVT算法能夠比較好地跟蹤到目標，因為子空間的方法對光照和小姿態的變化具有很好的魯棒性.本文的跟蹤器能夠在對比度比較低的情況下保持良好的跟蹤性能，這要歸功于本文的判決模型具有有利于區分前景和背景的特征.

第3個測試序列crossing如圖3(c)所示，存在著部分遮擋、運動模糊和背景復雜等干擾，給跟蹤帶來了困難.IVT算法和L2RLS算法在第47幀時跟蹤框開始縮小直至跟蹤失敗.Frag算法和VTD算法在跟蹤幾十幀以后開始丟失目標.MIL跟蹤器在測試序列中能夠跟蹤到目標，但是跟蹤的精度沒有本文的跟蹤器高.本文的算法能夠成功地對目標進行跟蹤，主要原因是本文的判決模型具有判別力特征，該特征能夠將目標從背景中區分開，即使在目標模糊的狀態下，也能夠準確定位到目標.

第4個測試序列jogging-2如圖3(d)所示，奔跑中的目標經歷了非剛性的形變、嚴重遮擋和運動模糊等干擾.除了本文的跟蹤器和L2RLS跟蹤器，其他跟蹤器在第49幀之后由于嚴重的遮擋丟失了目標.隨著跟蹤的不斷進行，L2RLS跟蹤器表現得不穩定，出現了短暫的漂移現象.本文的算法在整個圖像序列中都能夠較好地進行跟蹤，是因為基于判別式模型的跟蹤器可以通過遮擋處理機制估計可能被遮擋的圖像塊，形成一個魯棒的只含沒有遮擋的圖像塊的系數向量，從而避免了遮擋的影響，再通過更新機制獲得最新的正負樣本集，這有助于在變化著的場景中區分出前景和背景.

第5個測試序列freeman3如圖3(e)所示，目標的快速移動引起了遮擋、尺度變化和旋轉等干擾.MIL算法無法處理尺度變化和旋轉問題，在跟蹤的前幾幀就丟失了目標.在第300幀時，Frag跟蹤器不能克服跟蹤目標頭部大角度旋轉導致的嚴重遮擋，跟蹤失敗，IVT算法、VTD算法和L2RLS算法也開始發生漂移，目標框越來越小直至完全丟失目標.本文的跟蹤算法由于將背景候選賦予比較小的權重，所以當目標旋轉時，跟蹤結果不會漂移到背景中，且本文的跟蹤器能夠自適應地調整跟蹤框的大小，在整個序列中穩定地跟蹤到目標.

第6個測試序列singer2如圖3(f)所示，存在著光照變化、尺度變化、遮擋、非剛性變形、運動模糊和背景混雜等諸多干擾.除了本文的跟蹤器和VTD跟蹤器，其他跟蹤器在第56幀之后都丟失了目標.這是因為對于大部分基于模板的跟蹤器而言，簡單地利用跟蹤結果更新模板集通常會導致漂移.本文的跟蹤器能夠在整個視頻中保持良好的跟蹤性能，這要歸功于本文的跟蹤器在基于維持全局特征模板的基礎上，運用判決模型從凌亂的背景中區分出前景.

第7個測試序列emilio如圖3(g)所示，目標移動過程中存在著尺度變化，光照變化和旋轉等干擾.MIL算法不能處理尺度變化和旋轉問題，很快丟失了目標.在第142幀時，IVT算法、VTD算法和L2RLS算法開始發生漂移直至完全丟失目標.本文的跟蹤器能夠自適應地調整跟蹤框的大小，在整個序列中穩定地跟蹤到目標.

圖3 不同算法在不同測試序列上的跟蹤結果Fig.3 Tracking results with different algorithms on different videos

第8個測試序列toni如圖3(h)所示，存在尺度變化和旋轉等干擾.MIL算法無法旋轉問題，在跟蹤的前幾幀就丟失了目標.在第224幀時，Frag跟蹤器由于不能克服跟蹤目標頭部大角度旋轉導致的嚴重遮擋跟蹤失敗，IVT算法、VTD算法和L2RLS算法也發生漂移.而本文的跟蹤算法在目標旋轉時，跟蹤結果不會漂移到背景中，在整個序列都能跟蹤到目標.

3.2 定量評估

為了進一步分析本文算法的性能，分別在前6個視頻序列上繪制了中心點誤差曲線和重疊率曲線.中心點位置誤差是指某幀跟蹤結果的中心位置與該幀目標的標準中心位置之間的誤差;重疊率的計算方法是overlap rate=area(Rt∩Rg)/area(Rt∪Rg)，其中，Rt為某幀跟蹤框覆蓋的區域;Rg為該幀目標所在的真實區域.針對不同測試視頻的跟蹤誤差曲線結果對比和重疊率曲線結果對比如圖4和圖5所示，從中可見，本節提出的基于L2范數的聯合模型的目標跟蹤算法比其他算法具有更加魯棒的跟蹤效果.

圖4 針對不同的測試視頻的跟蹤誤差曲線結果對比Fig.4 Tracking error curve result according to different test videos

圖5 針對不同的測試視頻的重疊率曲線結果對比Fig.5 Overlap rate curve result according to different test videos

4 結論

在大量的實驗序列中，本文算法與4種先進的跟蹤算法以及L2正則化的跟蹤算法作比較，得出以下結論:①本文算法融合了基于全局模板的判別分類器和基于局部描述子的生成式模型，具有較強的魯棒性.②本文采用的遮擋處理機制能夠有效地處理遮擋.③本文的模型更新機制使模型具有適應性和辨別性.

References)

［1］ Wu Y，Lim J，Yang M H.Online object tracking:a benchmark［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington，DC:IEEE Computer Society，2013:2411-2418.

［2］ 邵文坤，黃愛民，韋慶.目標跟蹤方法綜述［J］.影像技術，2006(1):17-20.Shao W K，Huang A M，Wei Q.Target tracking method review［J］.Image Technology，2006(1):17-20(in Chinese).

［3］ Zhong W，Lu H，Yang M H.Robust object tracking via sparsitybased collaborative model［C］//Proc IEEE Comput Soc Conf Comput Vision Pattern Recognition.Washington，DC:IEEE Computer Society，2012:1838-1845.

［4］ 沈丁成，薛彥兵，張樺，等.一種魯棒的基于在線 boosting目標跟蹤算法研究［J］.光電子·激光，2013，24(11):30.Shen D C，Xue Y B，Zhang H，et al.A robust online boosting target tracking algorithm based on the research［J］.Journal of Photoelectron·Laser，2013，24(11):30(in Chinese).

［5］ Grabner H，Grabner M，Bischof H.Real-time tracking via on-line boosting［C］//BMVC 2006-Proceedings of the British Machine Vision Conference 2006.Edinburgh:British Machine Vision Association，2006:47-56.

［6］ 張穎穎，王紅娟，黃義定.基于在線多實例學習的跟蹤研究［J］.南陽師范學院學報，2012，10(12):35-37.Zhang Y Y，Wang H J，Huang Y D.Based on multiple instance learning online tracking study［J］.Journal of Nanyang Normal University，2012，10(12):35-37(in Chinese).

［7］ Babenko B，Belongie S，Yang M H.Visual tracking with online multiple instance learning［C］//2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops.Piscataway，NJ:IEEE Computer Society，2009:983-990.

［8］ Avidan S.Ensemble tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(2):261-271.

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

［10］ 齊飛，羅予頻，胡東成.基于均值漂移的視覺目標跟蹤方法綜述［J］.計算機工程，2007，33(21):24-27.Qi F，Luo Y P，Hu D C.Visual target tracking method based on mean shift review［J］.Computer Engineering，2007，33(21):24-27(in Chinese).

［11］ Black M，Jepson A.Eigentracking:robust maching and tracking of articulated objects using a view based representation［J］.International Journal of Computer Vision，1998，26(1):63-84.

［12］ Yang A Y，Sastry S S，Ganesh A，et al.Fast-minimization algorithms and an application in robust face recognition:a review［C］//Image Processing.Hong Kong:IEEE，2010:1849-1852.

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

［14］ Mei X，Ling H.Robust visual tracking using L1 minimization［C］//Computer Vision.Anchorage，Alaska:IEEE，2009:1436-1443.

［15］ Mei X，Ling H，Wu Y，et al.Minimum error bounded efficienttracker with occlusion detection［C］//Computer Vision and Pattern Recognition.Colorado Springs:IEEE，2011:1257-1264.

［16］ Bao C L，Wu Y，Ling H，et al.Real time robust l1 tracker using accelerated proximal gradient approach［C］//Proc IEEE Comput Soc Conf Comput Vision Pattern Recognition.Washington，DC:IEEE Computer Society，2012:1830-1837.

［17］ Zhang T Z，Ghanem B，Liu S，et al.Robust visual tracking via multi-task sparse learning［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington，DC:IEEE Computer Society，2012:2042-2049.

［18］ Zhang D，Yang M，Feng X.Sparse representation or collaborative representation:which helps face recognition?［C］//Computer Vision，2011:471-478.

［19］ Xiao Z Y，Lu H，Wang D.Object tracking with L2-RLS［C］//Proceedings-International Conference on Pattern Recognition.Piscataway，NJ:Institute of Electrical and Electronics Engineers Inc，2012:1351-1354.

［20］ Adam A，Rivlin E，Shimshoni I.Robust fragments-based tracking using the integral histogram［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.New York:Electronics Engineers Computer Society，2006:798-805.

［21］ Kwon J，Lee K M.Visual tracking decomposition［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE Computer Society，2010:1269-1276.

［22］ Maggio E，Cavallaro A.Hybrid particle filter and mean shift tracker with adaptive transition model［C］//ICASSP，IEEE International Conference on Acoustics，Speech and Signal Processing-Proceedings.Philadelphia，PA:Institute of Electrical and Electronics Engineers Inc，2005:221-224.