一種改進的長時間壓縮感知跟蹤算法

李宏波，鄭世寶，周　芹

(上海交通大學 圖像通信與網絡工程研究所，上海 200240)

一種改進的長時間壓縮感知跟蹤算法

李宏波，鄭世寶，周芹

(上海交通大學 圖像通信與網絡工程研究所，上海 200240)

摘要:壓縮感知跟蹤(CT)算法具有簡單、高效、實時的優點，但是卻存在著跟蹤窗口尺寸不能自適應變化，無法有效處理遮擋以及跟蹤失敗后的目標再發現等問題。為了解決上述問題，提出了一種改進的長時間壓縮感知跟蹤算法。所提出的算法采用多尺度的目標外觀再匹配方法，使得跟蹤窗口大小能夠適應目標尺寸變化。此外，通過分析滑動窗口內跟蹤窗口圖像的整體特征變化來判定目標是否發生遮擋。為了解決跟蹤器漂移問題，采用Haar特征在線生成檢測器，實現目標的再發現。實驗結果表明提出的算法相比原CT算法具有更好的魯棒性和準確性。

關鍵詞:目標跟蹤；壓縮感知跟蹤；尺寸自適應；長時間跟蹤

1目標跟蹤

目標跟蹤一直是計算機視覺領域重要研究課題之一，廣泛應用于智能視頻監控、人機交互、增強現實等領域。盡管許多新穎的跟蹤算法相繼被提出，但是由于存在著光照變化、背景干擾、遮擋等問題，設計出高效魯棒的跟蹤算法依然是個難點。

一個良好的目標外觀模型是跟蹤算法成功的關鍵，近些年，以在線方式更新目標外觀模型的在線視覺跟蹤成為主流。在線視覺跟蹤本質上可以看作是一個序列化的貝葉斯濾波過程，它主要包括3個部分：外觀模型、狀態轉移模型和觀測模型。

Zhang等提出的實時壓縮感知跟蹤(CT)算法[1]，由于其簡單、高效，快速的特點，引起了很多學者的關注。CT算法是典型的遵循tracking-by-detection思路的跟蹤算法，它采用在壓縮子空間中得到的特征向量來描述目標，并利用樸素貝葉斯分類器進行判決。但是，CT算法本身存在著一些缺陷：第一，由于其所采集的樣本大小相同，從而跟蹤窗口不能夠隨目標尺寸變化自適應縮放；第二，CT算法采用固定學習速率在線更新分類器參數，在目標發生遮擋時，分類器參數被錯誤更新，導致跟蹤漂移或失敗。第三，CT算法無法在目標重現時將其識別出來，因此不能長時間鎖定跟蹤目標。

本文針對CT算法的上述缺陷做出相應的改進。第一，選取經過分類器判定后置信度最大的前10個樣本作為候選樣本，并在各個樣本附近選取多種尺度的樣本組成新一幀的候選樣本集。然后將樣本集中的所有樣本分別與前一幀跟蹤結果進行比較，選取置信度最高的樣本作為跟蹤結果。這種做法不僅減輕了跟蹤器的漂移問題，而且使得跟蹤窗口尺寸能夠自適應變化。第二，通過滑窗的方式選取連續N幀目標圖像，表示為X={xt+1,xt+2,…,xt+N}，采用歸一化顏色直方圖作為整體特征，分別計算xi(i=t+2,t+3,…,t+N)與xt+1相應顏色直方圖的巴氏距離，通過分析巴氏距離的變化可以判定跟蹤目標是否發生了遮擋。第三，利用遮擋前的目標圖像以及背景圖像，采用Hr特征訓練分類器(即檢測器)，在目標跟丟后啟動檢測器，實現對目標的再發現。

2壓縮感知跟蹤算法

壓縮感知跟蹤(CT)算法是由Zhang等人提出的簡單高效的跟蹤算法。它采用從壓縮子空間提取的特征向量作為外觀模型。在對CT算法的特征向量做降維時，采用具有嚴格正交變換性質的稀疏矩陣，將圖像的特征空間降為低維的壓縮子空間。在跟蹤過程中，正負樣本也是利用相同的稀疏投影矩陣進行壓縮并由簡單的樸素貝葉斯分類器進行區分。CT算法一定程度上可以減輕因姿態或者光照變化造成的跟蹤漂移。

壓縮感知理論是CT算法特征降維的基本原理。對于圖像高維特征向量空間(x∈Rm)，利用滿足有限等距(RIP)性質的隨機矩陣R(R∈Rn×m)，其中n<

v=Rx

(1)

CT算法中采用的稀疏矩陣R，不僅滿足RIP性質，而且便于計算。其定義如下

(2)

具體實現時，參數s定為m/4，即只需從m維的向量中隨機選取2～3個值做加權求和得到新的特征值。

在目標跟蹤過程中，分類器輸入是降維后的低維特征向量，記作v=(v1,…,vn)T，向量v中各元素被認為是相互獨立的，則樸素貝葉斯分類器的輸出公式為

(3)

假定先驗概率p(y=1)=p(y=0)，其中y=1表示正樣本，y=0表示負樣本，同時假定條件概率密度函數符合高斯分布

(4)

式(4)中的標量參數是被增量更新的，如式(5)所示(以y=1為例)

(5)

式中：參數λ是學習速率；μ1和σ1分別表示正樣本第i個特征的均值和標準差。定義如式(6)(n是樣本個數)

(6)

CT算法的基本算法流程如下，對于每一幀圖像：

1)提取相應的正負樣本用于更新分類器：在上一幀跟蹤目標的位置附近選取若干個正樣本圖像塊，在遠離跟蹤目標的位置選取若干個負樣本圖像塊。根據選取的正負樣本提取特征向量，并利用稀疏矩陣對特征作降維，輸出低維特征以更新貝葉斯分類器參數。

2)利用更新后的分類器確定當前幀中目標的新位置：為了確定當前幀中目標的新位置坐標，在上一幀跟蹤目標的位置附近選取若干個樣本圖像塊，采用同樣方法得到相應的低維向量特征，輸入分類器后得到的概率最大的候選樣本即為當前幀中目標位置。

3壓縮感知跟蹤算法的改進

本文針對壓縮感知跟蹤算法存在的缺陷提出相應的改進策略，使得改進后的算法能夠有效處理遮擋和尺度變化問題，并能在目標消失后重現時再發現目標，從而實現對目標的長時間鎖定跟蹤。

3.1增加尺度變化

利用CT算法對場景內的目標進行跟蹤時，由于當前幀的候選樣本是在上一幀跟蹤結果周圍一定半徑范圍內選取的若干尺寸相同的矩形框中的圖像，然后對所有的候選樣本提取相應的特征向量并輸入分類器，最終選取置信度最大的樣本作為當前幀的跟蹤結果。CT算法采集的樣本的尺寸始終和初始目標框一致，不能夠進行自適應的縮放。但是在實際視頻中，目標尺寸可能會在運動過程中放大或者縮小，這就導致CT算法分類器參數被錯誤更新，最終導致跟蹤失敗。

CT算法從當前幀候選樣本中選取置信度最大的樣本作為跟蹤結果，然而噪聲和誤差使得置信度最大的候選樣本往往不能最接近目標的真實位置。因此，本文選取置信度最大的前10個樣本作為初始的候選樣本，并在每個樣本附近一定半徑范圍內采用三種尺度的矩形框采樣產生更多的候選樣本。最后，采用歸一化相關系數(NCC)算法計算每個候選樣本與上一幀跟蹤結果的相關系數，選取最大相關系數對應的候選樣本作為跟蹤結果。假設上一幀的目標尺度是s0=1，則當前幀的三種尺度分別是s1=1-σ，s2=1和s3=1+σ，分別對應于目標尺寸縮小，不變和放大三種情況。在文獻[1]中，作者通過卷積的性質推導證明了利用尺度變化的特征模板可以對不同大小的目標進行特征提取，并使最終得到的樣本特征值依然滿足一定的統計規律，即具有尺度不變性。假定當前幀跟蹤結果與目標真實位置吻合，則分類器參數的更新沒有引入噪聲和誤差。與傳統的在上一幀跟蹤結果周圍采用不同尺度的矩形框進行搜索的方法相比，該方法不僅減少了待匹配樣本的數量，降低了計算量，而且減輕了累積誤差帶來的跟蹤漂移問題。

3.2引入遮擋判定

由式(5)可知CT算法的分類器參數的更新是以恒定的學習速率逐幀進行的。它基于這樣的假設：每一幀的跟蹤結果都是和目標真實位置相吻合且沒有被遮擋。但是當遇到目標被遮擋或者目標尺寸發生變化時，這樣的假設就不成立了。當前跟蹤結果的外觀模型和目標的外觀模型之間的誤差會導致分類器參數被錯誤更新。同時，分類器參數將進一步影響下一幀的跟蹤結果。這樣，誤差逐步積累，最終將導致跟蹤漂移甚至跟蹤失敗。針對這一問題，本文提出了一種遮擋判定策略，在判定目標被遮擋時，分類器參數停止更新，并保存此時學到的外觀模型，用于目標的再發現。

在目標由未被遮擋到完全被遮擋的過程中，跟蹤窗口圖像逐漸發生變化。跟蹤窗口圖像和真實目標圖像的相似度越來越小，因此，通過觀察相似度的變化可以判斷目標是否發生遮擋。具體的實施方法如下：

本文采用滑動窗口的方式從第一幀開始選取連續N幀跟蹤窗口圖像，表示為X={xt+1,xt+2,…,xt+N}。其中，xt+1代表未發生遮擋的目標圖像，N是一個根據實際情景設置的經驗值。由于目標由未被遮擋到被完全遮擋的過程中，整體特征發生很大的變化，因此本文采用歸一化的顏色直方圖作為跟蹤結果圖像的外觀表達，并通過計算顏色直方圖之間的巴氏距離得到兩幅圖像之間的相似性。令Ht+i代表xt+i的歸一化顏色直方圖，xt+i與xt+j之間的相似度ρi,j表示為

(7)

式中：ρi,j越大表示兩幅圖像相似度越高。依次計算xt+i(i=2,…,N)與xt+1之間的相似度ρ1,i。通過分析ρ1,i的變化來判斷目標是否發生遮擋。如果ρ1,i整體趨于減小，并且ρ1,N小于閾值Tmin，則跟蹤結果圖像發生了比較大的變化，可以認為存在目標被遮擋的情況，如圖1所示。此時，停止CT跟蹤器，并保存xt+1時學到的目標外觀模型，由檢測器開始檢測目標；如果ρ1,N大于閾值Tmax，則判定不存在目標被遮擋的情況；如果ρ1,N介于Tmin與Tmax之間，則情況待定，下一滑動窗口的起始位置為max{i:ρ1,i>Tmax}(i=2,…,N)。該方法對遮擋的判定雖然存在一定的滯后，但是因為保存了遮擋發生前學到的目標外觀模型，因此并沒有因為遮擋而引入誤差和噪聲。

a　跟蹤結果

b　相似度變化圖1　進入遮擋過程跟蹤結果圖像及相似度變化

3.3目標的再發現

從目標被判定遮擋時起，CT算法停止跟蹤，為了實現長時間的目標鎖定跟蹤，本文啟動在線生成的檢測器尋找再次出現的目標。

從保存的目標圖像與背景圖像中提取Hr特征，并利用該特征在線訓練得到SVM分類器，并用它來實現目標的再發現。本文認為目標再次出現時，外觀模型和遮擋前相比較并沒有發生大的變化。該方法主要包括以下兩個階段。

1)訓練階段：假設在遮擋發生前跟蹤結果是準確的，正樣本就是每一幀的跟蹤結果，負樣本則是在遮擋前跟蹤結果周圍較遠的位置隨機選取的矩形圖像片，如圖2所示。

圖2　正負樣本的選取(黑線代表正樣本，白線代表負樣本)

2)搜索階段：在判定目標被遮擋后，檢測器開始檢測被遮擋的目標。采用與目標初始尺寸大小一樣的滑動矩形窗口全圖搜索目標。由于檢測窗口尺寸是固定的，所以在檢測到目標后，為了獲取更精確的目標位置，利用保存的目標外觀模型(即分類器參數)，在目標周圍選取多種尺寸的模板，提取特征向量，輸入分類器，選取置信度最大的窗口作為目標的起始位置。

4實驗結果與分析

為了驗證本文提出的算法的有效性，選取一些存在尺度變化和遮擋情況的公共數據集和本實驗室的數據集做了一系列測試，并與CT算法進行了比較。重要參數設置如下：尺度變化因子σ=0.05，遮擋判定的滑動窗口大小N=8～15，閾值Tmin=0.35，Tmax=0.65。

在圖3a和圖3b中，目標在運動過程中尺寸分別放大和縮小，由于原CT算法跟蹤窗口尺寸固定不變，影響了正負樣本的采集，目標外觀模型更新錯誤，使得跟蹤的準確性和覆蓋率較低，更壞的情況會導致跟蹤漂移甚至失敗。本文提出的算法使得跟蹤窗口大小自適應目標尺寸變化，無論在準確性還是覆蓋率上都優于原CT算法，目標外觀模型也得到更加準確的更新。

a　CarScale

b　Caviar圖3　尺度變化對跟蹤結果的影響(深色代表CT算法，淺色代表本文算法)

在圖4a和圖4b中，目標在運動過程中分別被不同物體遮擋，原CT算法以固定的學習速率在線逐幀更新目標外觀模型，因此在發生遮擋時，背景信息被錯誤的引入，從而產生錯誤的外觀模型，導致跟蹤逐漸漂移并最終失敗。本文提出的算法引入遮擋判定機制，在判定目標發生遮擋時，停止跟蹤并保存遮擋前學到的目標外觀模型，啟動在線生成的目標檢測器，在再次發現目標時利用保存的目標外觀模型確定精確位置，繼續跟蹤目標。和原CT算法相比，改進后的算法可以更好地處理遮擋問題，能夠實現長時間鎖定跟蹤。

a　David

b　Our Video Test圖4　遮擋對跟蹤結果的影響(深色代表CT算法，淺色代表本文算法)

5小結

本文針對原CT算法存在的跟蹤窗口尺寸不自適應變化，無法有效處理遮擋和跟蹤失敗后目標再發現等情況的缺陷，提出了相應的改進策略。首先，選取置信度大小前十的候選樣本，通過多尺度外觀模型再匹配的方法，實現了跟蹤窗口隨著目標尺寸自適應變化，提高了跟蹤的精度；此外，通過分析滑動窗口內跟蹤窗口圖像的歸一化顏色直方圖的變化，判定目標是否發生遮擋。在發生遮擋時停止跟蹤并采用Haar特征在線訓練得到SVM分類器，通過SVM分類器和保存的目標外觀模型由粗到細搜索，再次發現目標并確定目標的精確位置，這樣就解決了因目標遮擋導致的跟蹤失敗問題，實現了對目標的長時間鎖定跟蹤。本文提出的改進策略具有普適性，對不同的跟蹤算法均適合。實驗結果表明，本文提出的算法在目標尺寸發生變化和被遮擋的情況下能夠做到長時間鎖定跟蹤。

參考文獻：

[1]ZHANG K H，ZHANG L，YANG M H. Real-time compressive tracking[C]//Proc. 12th European Conference on Computer Vision. Florence， Italy：IEEE， 2012：864-877.

[2]BABENKO B， YANG M H， BELONGIE S. Visual tracking with online multiple instance learning[C]//Proc.IEEE Conference on Computer Vision and Pattern Recognition. Miami， FL：IEEE， 2006：983-990.

[3]LI H X， SHEN C H， SHI Q F. Real-time visual tracking using compressive sensing[C]//Proc. IEEE Conference on Computer Vision and Pattern Recognition. Providence， RI：IEEE， 2011：1305-1312.

[4]COLLINS R T， LIU Y X， LEORDEANU M. Online selection of discriminative tracking features[J]. IEEE transations on pattern analysis and machine intelligence， 2005， 27(10)：1631-1643.

[5]KALAL Z， MIKOLAJCZYK K， MATAS J. Tracking learning detection[J]. IEEE transactions on pattern analysis and machine intelligence(S0162-8828)， 2011， 6(1)：1-14.

[6]DONOHO D. Compressed sensing[J]. IEEE transactions on information theory(S0018-9448)， 2005， 52(4)：1289-1306.

李宏波，碩士生，主要研究行人跟蹤；

鄭世寶，教授，主要研究網絡多媒體通信、智能視頻監控以及老人健康信息技術；

周芹，博士生，主要研究行人重識別。

責任編輯：時雯

Improved long-time compressive tracker

LI Hongbo，ZHENG Shibao，ZHOU Qin

(InstituteofImageCommunicationandNetworkEngineering，ShanghaiJiaotongUniversity，Shanghai200240，China)

Abstract:Compressive tracker is famous for its simplification and efficiency. However，there still exists a few problems to be solved. For example， only fixed-size tracking windows can be generated，besides，the problem of occlusion as well as re-identification of the target after a track failure is not well handled. To address the issues mentioned above， an improved long-time compressive tracker is proposed. Through multi-scale appearance matching of the target，tracking windows adaptive to the object size are generated. Besides，the change of the global feature of consecutive frames in a sliding window is analyzed to see if an occlusion occurs. Finally，to solve the problem of drift，an online detector using Haar features is learned to re-identify the lost object. The experimental results demonstrate that our algorithm performs better than the CT algorithm in robustness and precision.

Key words:object tracking； compressive tracking； adaptive size； long-time tracking

中圖分類號：TN919.8

文獻標志碼:A

DOI：10.16280/j.videoe.2016.04.005

作者簡介：

收稿日期：2015-11-04

文獻引用格式：李宏波，鄭世寶，周芹. 一種改進的長時間壓縮感知跟蹤算法[J].電視技術，2016，40(4)：22-26.

LI H B，ZHENG S B，ZHOU Q. Improved long-time compressive tracker [J].Video engineering，2016，40(4)：22-26.