郁道銀 王悅行 陳曉冬 汪 毅

?

基于隨機投影和稀疏表示的跟蹤算法

郁道銀 王悅行 陳曉冬*汪 毅

(天津大學精密儀器與光電子工程學院 天津 300072),(天津大學光電信息技術(shù)教育部重點實驗室 天津 300072)

針對目標跟蹤過程中存在的諸多技術(shù)問題，該文提出一種魯棒的目標跟蹤方法。首先，該文采用基于稀疏表示的全局模板描述目標的表觀狀態(tài)，通過構(gòu)造正負模板以區(qū)分目標和背景；然后采用隨機投影法對表示模板和候選目標進行降維，以降低算法的時間復雜度；采用粒子濾波法作為目標的運動模型，通過多項式重采樣方法進行粒子重采樣，以保持粒子的多樣性；設計了正負模板更新策略，將正模板分為固定集和更新集，對這兩部分在相似度計算和正模板更新時采取不同的處理方法，并且在其中加入目標遮擋的判決機制，從而可以有效避免遮擋的影響；實驗結(jié)果表明，該算法能夠準確跟蹤受遮擋、運動模糊等多種復雜場景的目標，與現(xiàn)有跟蹤方法相比，所提算法具有更好的準確性和穩(wěn)定性。

目標跟蹤；稀疏表示；隨機投影；模板更新；重采樣策略

1 引言

目標跟蹤技術(shù)屬于計算機視覺領域的研究范疇。它廣泛應用于安全監(jiān)控、交通監(jiān)測、人機交互、軍事以及醫(yī)療等諸多領域，已經(jīng)成為計算機領域最熱門的課題之一。研究人員對視覺跟蹤課題研究已有30多年，但是目標跟蹤仍然存在很多技術(shù)難點，主要包括：多目標同時跟蹤、場景光照變化、目標尺度變化、目標受遮擋、目標旋轉(zhuǎn)以及運動模糊等[1]。

選擇合適的目標特征是決定目標跟蹤性能的關鍵因素。目前，由稀疏表示理論[2]構(gòu)造的目標特征已經(jīng)成功應用到了人臉識別[3]、圖像重建[4]以及圖像去噪[5]等領域。文獻[6,7]將稀疏表示理論應用到目標跟蹤領域，取得了優(yōu)于其他算法的跟蹤效果。相關文獻圍繞目標模板構(gòu)造字典，而不考慮背景信息對目標的影響。當目標與背景本身的相似度較高，或者由于目標被遮擋造成兩者的相似度較高時，跟蹤的目標位置易發(fā)生漂移。為了更好地區(qū)分跟蹤過程中的前景目標和背景，文獻[8]提出訓練表示目標的正模板和表示背景的負模板，該方法減小了發(fā)生跟蹤漂移的可能性，但是該方法的實時性很差。為了提高計算的速度，文獻[9,10]提出了基于稀疏表示的改進算法。

上述基于稀疏表示理論的跟蹤算法沒有采用降維方法對字典模板和目標進行降維，因此算法的時間復雜度隨著圖像維度的增加而增加，當圖像維數(shù)較大時，算法的時間復雜度很高。文獻[11,12]等采用主成分分析(Principal Components Analysis, PCA)方法進行降維，但是由于降維矩陣隨著模板的變化而改變，因此，每幀圖像都需要對降維矩陣進行更新。針對目標跟蹤過程中存在的諸多技術(shù)問題，本文提出了基于隨機投影和稀疏表示的目標跟蹤方法。本文基于稀疏表示的全局判決分類器建立外觀模型，并且采用隨機投影法對數(shù)據(jù)進行降維；運動模型則采用改進的粒子濾波方法，并且在算法中加入了具有遮擋判決功能的模板更新機制。

2 建立狀態(tài)模型

目標跟蹤系統(tǒng)主要由兩方面要素構(gòu)成，一個要素是建立目標的狀態(tài)模型，它通過觀測特定的目標特征計算候選目標與待跟蹤目標的相似度，選取相似度最大的候選目標作為當前幀的跟蹤目標。另一個要素是建立目標的運動模型，它通過預測目標的運動狀態(tài)為跟蹤器提供足夠多的候選目標。本文采用稀疏表示方法建立狀態(tài)模型，重點步驟是構(gòu)造超完備字典、字典降維和計算候選目標的相似度。

2.1 構(gòu)造超完備字典

稀疏表達的基本思想是在合適的超完備字典下尋找信號盡可能稀疏而準確的表示。假設,為樣本數(shù)量，為樣本維度，這樣的個樣本構(gòu)成一個超完備字典。假設測試圖像為,為測試圖像在超完備字典的表示系數(shù)。在使盡量稀疏的條件下，考慮到樣本中通常含有噪聲，通常用式(1)對求解。

本文采用文獻[8]的方法構(gòu)造正負字典：在初始幀目標附近選擇若干個與目標尺寸相同的圖像，構(gòu)成正模板集；在遠離目標中心一定距離的回形區(qū)域選擇若干個與目標尺寸相同的圖像，構(gòu)成負模板集；正負模板集共同構(gòu)成了實驗的字典。

2.2 圖像降維

由于歸一化后的模板列向量維度很大，將原始信號作為字典進行稀疏表示會造成計算量過大，因此在目標跟蹤過程中有必要對圖像進行降維處理。降維方法的構(gòu)造可分為兩類，一類方法是由樣本訓練產(chǎn)生，例如PCA[12]等，另一類是通過獨立于樣本的規(guī)則產(chǎn)生，如均值取樣法(downsample)[13]、隨機投影法(Random Projection, RP)等。第1類方法容易受到樣本變化的影響，因此局限性較大。隨機投影是屬于第2類的有效數(shù)據(jù)降維技術(shù)，它通過將原始數(shù)據(jù)投影到給定隨機矩陣進行數(shù)據(jù)降維，用于降維的投影矩陣是獨立于訓練樣本產(chǎn)生的，計算簡單而且高效。

在隨機投影的研究中，文獻[14]提出了一種產(chǎn)生隨機投影矩陣的快速算法。該算法的具體思路是：對任意由的個點構(gòu)成的集合，其維度為，令是一個維的隨機矩陣，其中是服從下列概率分布的獨立隨機變量，矩陣元素的表達式為

本文采用上述隨機投影方法對訓練得到的模板列向量進行降維處理，然后將粒子濾波器得到的候選圖像塊按照同樣的方法進行降維處理。

2.3 候選目標相似度計算

由于正模板表征目標特征，而負模板表征目標附近的背景特征，因此，將候選目標用正負模板集字典進行稀疏表示時，當候選目標用正模板集表示得到的重構(gòu)誤差較小時，說明候選目標是跟蹤目標的可能性較大；當候選目標用負模板集表示得到的重構(gòu)誤差較小時，說明候選目標是背景的可能性較大。由于初始幀圖像的正模板一般是最準確的而且在目標被遮擋等情況下具有很好的參考效果，因此，本文將正模板集分為固定正模板集和更新正模板集，將前5個正模板不參與更新，它們組成固定正模板集，將剩余正模板參與正模板的更新，它們組成更新正模板集。

因此，本文狀態(tài)模型構(gòu)造分為字典構(gòu)造、圖像降維和候選目標的相似度計算3部分，狀態(tài)模型部分的具體流程如圖1所示。

圖1 狀態(tài)模型流程圖

3 建立運動模型

本文采用粒子濾波方法建立運動模型，另外，粒子濾波法容易出現(xiàn)粒子退化的問題，因此需要采取合適的重采樣策略。

3.1 粒子濾波框架

粒子濾波法是在線視頻跟蹤理論的基礎。本文采用基于6維仿射參數(shù)[11]的向量描述目標的狀態(tài)，，其中，,分別表示方向和方向的位移、為旋轉(zhuǎn)角度、描述尺度變化、為目標的寬高比、是斜切度。假定目標狀態(tài)的運動模型符合獨立的高斯分布，運動模型可以表示為

3.2 粒子重采樣策略

在粒子濾波算法中，當經(jīng)過若干次遞推后，除少數(shù)粒子外，其余粒子的權(quán)值可忽略不計，從而使得大量計算浪費在幾乎不起任何作用的粒子更新上，這就是粒子退化(particle degeneracy)[15]。采用粒子重采樣策略可以解決粒子退化問題。

圖2 多項式重采樣方法示意圖

4 模板更新策略

由于目標在跟蹤過程中可能會不斷發(fā)生變化，所以有必要適時更新正模板。而背景的變化往往比前景變化要大，因此，同樣需要不斷更新負模板。

4.1 正模板更新

在跟蹤過程中當目標發(fā)生較大的遮擋時如果持續(xù)更新正模板，在正模板中會包含部分背景信息，易發(fā)生模板漂移。為解決這個問題，本文通過建立目標重構(gòu)誤差的監(jiān)督機制來判斷目標是否發(fā)生較大的遮擋。通過實驗發(fā)現(xiàn)，在同一場景中，當目標受遮擋時，目標的重構(gòu)誤差較未受遮擋時有明顯增加，因此，本文采用相對重構(gòu)誤差作為判斷依據(jù)。由于目標的初始幀狀態(tài)由手動標定，因此，前5幀圖像的重構(gòu)誤差一般很小，所以取前5幀目標重構(gòu)誤差的平均值作為參考誤差值，將之后每幀跟蹤目標的重構(gòu)誤差值與作差求出，本文根據(jù)實驗設定閾值，當大于則認為目標受到較大的遮擋，此時不對正模板進行更新，否則，對正模板更新。

正模板更新的方法：實驗中每隔20幀更新正模板，將更新正模板集參與更新，更新前先判斷當前幀目標是否滿足更新閾值條件。若滿足閾值條件，首先將當前幀跟蹤到的目標用更新正模板集進行稀疏表示，將當前幀跟蹤到的目標加入更新正模板集，來替換更新正模板集中表示系數(shù)最小的模板，然后將更新正模板集與固定正模板集組成新的正模板集進行下一幀跟蹤。

4.2 負模板更新

本文按照文獻[8]的方法更新負模板，每隔5幀更新負模板集，更新時將負模板全部更新到最新的狀態(tài)，負模板的獲取方法與之前介紹的方法一致，更新的圖像來自當前幀跟蹤目標附近的區(qū)域。

5 跟蹤算法流程及框架

本文實驗的算法流程及框架如圖3所示。

圖3 算法框架及流程示意圖

6 實驗結(jié)果與分析

本文提出了一種基于隨機投影和稀疏表示的目標跟蹤方法，為了證明本文算法的性能，本節(jié)設計了目標跟蹤實驗。

本文算法采用Matlab軟件編寫，計算機平臺配置為Intel I3-3220(CPU 3.3 GHz，內(nèi)存為4 GB)。在跟蹤實驗中，需要設定下列參數(shù)。本文選取50個正模板和100個負模板。將稀疏表示的平衡參數(shù)值設置為0.04，將固定正模板集的權(quán)重系數(shù)設置為0.6，正模板每隔20幀更新一次，負模板每隔5幀更新一次，正模板更新的閾值設置為2。粒子的數(shù)目和幀轉(zhuǎn)移協(xié)方差矩陣都是根據(jù)跟蹤圖像的具體情況進行調(diào)整；實驗中候選目標圖像和正負模板圖像大小都為像素，用隨機矩陣將其投影到低維空間，變換維度取。

6.1 定性實驗

在Caviar 1視頻中，如圖4所示，目標經(jīng)歷了嚴重地遮擋和尺度變化，另外，場景中存在與目標顏色和形狀十分相似的其他物體對目標產(chǎn)生干擾。在第112幀，當目標被大部分遮擋時，MIL算法發(fā)生跟蹤偏移。在第126幀和第141幀，目標不再受到遮擋， 但是IVT和跟蹤器跟蹤到遮擋物。在第189幀，F(xiàn)rag跟蹤器的尺寸發(fā)生了較大變化。在第354幀，PN跟蹤器錯誤地跟蹤到目標周圍的物體，這是因為PN算法的檢測器只能檢測到與目標外觀相似的其他物體。在跟蹤過程中，只有本文算法和OSPT算法保持了較高的準確性。

圖4 Caviar1跟蹤效果

對于Occlusion1視頻，如圖5所示，目標被一本書分別從左測、右側(cè)、下方等方向嚴重地遮擋。在第540幀時，當目標被嚴重遮擋時，只有本文算法和OSPT算法保持了跟蹤的準確性，其他算法都發(fā)生了不同程度的跟蹤偏移和尺度變化。在接下來的嚴重遮擋情況出現(xiàn)時，只有, Frag, OSPT和本文算法的跟蹤效果較好。Frag跟蹤器利用局部分塊直方圖來處理遮擋問題，跟蹤器利用瑣碎模板對遮擋物體進行建模。本文算法由于采用全局模板描述目標外觀狀態(tài)，正負模板能夠很好地區(qū)分目標和背景，當目標被遮擋時本文算法能夠根據(jù)背景情況區(qū)分目標，而且在更新過程加入了遮擋的判決機制，因此，算法對目標遮擋有較好的魯棒性。

圖5 Occlusion1跟蹤效果

通過上述實驗可以看出，本文算法與OSPT算法的誤差接近，而且這兩個算法在7個算法中誤差最小，較其他跟蹤器的誤差有明顯地降低。為比較這兩個算法跟蹤性能的好壞，本文用更具挑戰(zhàn)性的視頻評估兩個算法的性能。

圖6是Sylvester2008b的部分跟蹤圖片，該圖像序列存在部分遮擋，光照變化和平面外旋轉(zhuǎn)等跟蹤難點。在Sylvester2008b中，前42幀兩種算法的跟蹤效果較好。在第63幀目標經(jīng)歷了平面外旋轉(zhuǎn)和光照變化，而且目標與背景的對比度較低，OSPT算法跟蹤框偏離了目標，而本文算法由于加入了正負模板構(gòu)造方法，對目標和背景有良好的區(qū)分能力，因此取得了較好的跟蹤效果。在之后的跟蹤過程中，OSPT跟蹤器沒能從之前的跟蹤偏移中恢復，由于本文算法采用了能夠區(qū)分目標和背景的全局判決模型，在運動模糊情況下仍能通過區(qū)分背景而得到前景目標。

圖6 Sylvester2008b跟蹤效果

6.2 定量實驗

將本文算法與上述7個跟蹤算法進行定量比較。本文通過計算跟蹤結(jié)果與真實值之間的中心點位置誤差來定量比較算法的準確性。中心點位置誤差是指跟蹤結(jié)果與真實值在方向和方向上坐標的均方根誤差，見式(11)。

表1中，前5行分別是各種算法對特定視頻序列的中心點跟蹤誤差，最后兩行分別是各種算法的平均中心點誤差以及平均跟蹤速度。通過表1可以看出，雖然OSPT算法在3個視頻中跟蹤誤差最小，但是它在另外兩個視頻中跟蹤誤差很大，因此OSPT跟蹤器對不同視頻的跟蹤穩(wěn)定性較差。本文算法在所有測試視頻中的跟蹤誤差都很小，而且本文算法的平均跟蹤誤差是最小的，算法具有較高的跟蹤準確性和穩(wěn)定性。最后一行是對不同算法跟蹤速度的比較，由結(jié)果可以看出，采用稀疏表示的算法(OSPT和本文算法)跟蹤速度小于不采用稀疏表示的算法(IVT和MIL等)，這是因為稀疏表示方法需要計算多次優(yōu)化問題。本文算法的跟蹤速度與OSPT基本相同，但是本文算法在應對不同的跟蹤難點時跟蹤穩(wěn)定性明顯更好。表1中最后3列分別是本文算法與只加正模板更新算法(OWP)和只加負模板更新算法(OWN)的跟蹤中心點誤差結(jié)果比較。可以看出，本文算法由于同時加入正負模板更新策略，較只加入正模板或者負模板更新策略的方法在跟蹤準確性上有明顯的提高，特別是當目標姿態(tài)變化、旋轉(zhuǎn)、背景變化以及目標遮擋等復雜情況(Sylvester2008b, Woman)出現(xiàn)時。

表1 各算法平均目標中心點誤差

7 結(jié)論

本文通過對稀疏表示方法和粒子濾波法進行結(jié)合，提出了一種基于隨機投影和稀疏表示的目標跟蹤方法。本文算法利用正負模板構(gòu)造方法和隨機投影法有效地學習外觀模型，運動模型則采用粒子濾波方法，并且使用多項式粒子重采樣策略提高粒子跟蹤效率，從而增加了粒子的多樣性；而且在算法中加入了具有遮擋判決功能的模板更新機制，該方法有效地避免了模板漂移的影響，提高了算法的魯棒性。實驗結(jié)果表明，當目標發(fā)生旋轉(zhuǎn)、遮擋、尺度變化以及運動模糊等情況時，本文算法相比于其他跟蹤算法具有更高的跟蹤準確性和穩(wěn)定性。

[1] ZHUANG B H, LU H C, XIAO Z Y, . Visual tracking via discriminative sparse similarity map[J]. , 2014, 23(4): 1872-1881.

[2] DONOHO D. Compressed sensing[J]., 2006, 52(4): 1289-1306.

[3] MA C F, JUNG Juneyoung, KIM Seungwook, .Random projection-based partial feature extraction for robust face recognition[J]. , 2015, 149C: 1232-1244. doi: 10.1016/J.neucom.2014.09.004.

[4] 鄧承志, 田偉, 陳盼, 等. 基于局部約束群稀疏的紅外圖像超分辨率重建[J]. 物理學報, 2014, 63(4): 044202-044208. doi: 10.7498/aps.63.044202.

DENG Chengzhi, TIAN Wei, CHEN Pan, .Infrared image super-resolution via locality-constrained group sparse model[J]. , 2014, 63(4): 044202-044208. doi: 10.7498/aps.63.044202.

[5] 霍雷剛, 馮象初. 基于主成分分析和字典學習的高光譜遙感圖像去噪方法[J]. 電子與信息學報, 2014, 36(11): 2723-2729. doi: 10.3724/SP.J.1146.2013.01840.

HUO Leigang and FENG Xiangchu. Denoising of hyperspectral remote sensing image based on principal component analysis and dictionary learning[J]. &, 2014, 36(11): 2723-2729. doi: 10.3724/SP.J.1146.2013.01840.

[6] XUE M and LING H. Robust visual tracking using L1 minimization[C]. IEEE International Conference on Computer Vision, Kyoto, Japan, 2009: 1436-1443.

[7] BAO C L, WU Y, LING H B,. Real time robust L1 tracker using accelerated proximal gradient approach[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, Providence, USA, 2012: 1830-1837.

[8] ZHONG W, LU H C, and YANG M-H. Robust object tracking via sparsity-based collaborative model[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, Providence, USA, 2012: 1838-1845.

[9] 袁廣林, 薛模根. 基于稀疏稠密結(jié)構(gòu)表示與在線魯棒字典學習的視覺跟蹤[J]. 電子與信息學報, 2015, 37(3): 536-542. doi: 10.11999/JEIT140507.

YUAN Guanglin and XUE Mogen. Visual tracking based on sparse dense structure representation and online robust

dictionary learning[J]. & , 2015, 37(3): 536-542. doi: 10.11999/JEIT140507.

[10] 齊苑辰, 吳成東, 陳東岳, 等. 基于稀疏表達的超像素跟蹤算法[J]. 電子與信息學報, 2015, 37(3): 529-535. doi: 10.11999 /JEIT140374.

QI Yuanchen, WU Chengdong, CHEN Dongyue,.Superpixel tracking based on sparse representation[J]. &, 2015, 37(3): 529-535. doi: 10.11999/JEIT140374.

[11] ROSS David A, LIM Jongwoo, LIN Rueisung, .Incremental learning for robust visual tracking[J]., 2008, 77(1/3): 125-141.

[12] TURK M and PENTLAND A. Eigenfaces for recognition[J]. , 1991, 3(1): 71-86.

[13] WRIGHT J, YANG A Y, GANESH A,. Robust face recognition via sparse representation[J]., 2009, 31(2): 210-227.

[14] ACHLIOPTAS D. Database-friendly random projections: Johnson-Lindenstrauss with binary coins[J]. , 2003, 66(4): 671-687.

[15] LI T, SATTAR T P, and SUN S. Deterministic resampling: unbiased sampling to avoid sample impoverishment in particle filters[J]. , 2012, 92(7): 1637-1645.

[16] GORDON N J, SALMOND D J, and SMITH A F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J]. -, 1993, 140(2): 107-113.

[17] KALAL Z, MATAS J, and MIKOLAJCZYK K. P-N learning: bootstrapping binary classifiers by structural constraints[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, San Francisco, USA, 2010: 49-56.

[18] BABENKO B, YANG M H, and BELONGIE S. Visual tracking with online multiple instance learning[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, Miami, USA, 2009: 983-990.

[19] ADAM A, RIVLIN E, and SHIMSHONI I. Robust fragments- based tracking using the integral histogram[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, New York, USA, 2006: 798-805.

[20] KWON J and LEE K M. Visual tracking decomposition[C]. Proceedings of the International Conference on Computer Vision and Pattern Recognition, San Francisco, USA, 2010: 1269-1276.

[21] WANG D, LU H, and YANG M H. Online object tracking with sparse prototypes[J]. , 2013, 22(1): 314-325.

YU Daoyin WANG Yuexing CHEN Xiaodong WANG Yi

(-,,300072,) ,(-, ,300072,)

A robust object tracking method is proposed to deal with technical issues during tracking. Firstly, the global template based on sparse representation is used to describe object appearance, while positive and negative modules are built to separate the object from the background. Then, Random Projection (RP) is used to reduce the dimension of modules and candidate objects, which could release the calculation burden. Furthermore, the Particle Filter (PF) is used as the object motion model, and the multi-normal resample method is used to maintain the diversity of particles. To alleviate module drift problem, the positive module is divided into static module and changeable module, while different modules are dealt with different ways, and sparse reconstruction error is used to determine whether the object is occluded. Experiment results on numerous challenging videos show that the proposed method has better performance in accuracy and stability in comparison with state-of-the-art tracking methods.

Object tracking; Sparse representation; Random Projection (RP); Template updating; Resample method

TP391.4

A

1009-5896(2016)07-1602-07

10.11999/JEIT151064

2015-09-21；改回日期：2016-04-01；網(wǎng)絡出版：2016-05-24

陳曉冬 xdchen@tju.edu.cn

郁道銀： 男，1945年生，教授，主要研究方向為圖像處理和目標跟蹤.

王悅行： 男，1990年生，碩士生，研究方向為圖像處理和目標跟蹤.

陳曉冬： 男，1975年生，教授，主要研究方向為光電檢測和圖像處理.

汪 毅： 女，1981年生，講師，主要研究方向為光電檢測和圖像處理.