李宏波，鄭世寶，周　芹

(上海交通大學(xué) 圖像通信與網(wǎng)絡(luò)工程研究所，上海 200240)

一種改進(jìn)的長時(shí)間壓縮感知跟蹤算法

李宏波，鄭世寶，周芹

(上海交通大學(xué) 圖像通信與網(wǎng)絡(luò)工程研究所，上海 200240)

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

關(guān)鍵詞:目標(biāo)跟蹤；壓縮感知跟蹤；尺寸自適應(yīng)；長時(shí)間跟蹤

1目標(biāo)跟蹤

目標(biāo)跟蹤一直是計(jì)算機(jī)視覺領(lǐng)域重要研究課題之一，廣泛應(yīng)用于智能視頻監(jiān)控、人機(jī)交互、增強(qiáng)現(xiàn)實(shí)等領(lǐng)域。盡管許多新穎的跟蹤算法相繼被提出，但是由于存在著光照變化、背景干擾、遮擋等問題，設(shè)計(jì)出高效魯棒的跟蹤算法依然是個難點(diǎn)。

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

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

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

2壓縮感知跟蹤算法

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

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

v=Rx

(1)

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

(2)

具體實(shí)現(xiàn)時(shí)，參數(shù)s定為m/4，即只需從m維的向量中隨機(jī)選取2～3個值做加權(quán)求和得到新的特征值。

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

(3)

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

(4)

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

(5)

式中：參數(shù)λ是學(xué)習(xí)速率；μ1和σ1分別表示正樣本第i個特征的均值和標(biāo)準(zhǔn)差。定義如式(6)(n是樣本個數(shù))

(6)

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

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

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

3壓縮感知跟蹤算法的改進(jìn)

本文針對壓縮感知跟蹤算法存在的缺陷提出相應(yīng)的改進(jìn)策略，使得改進(jìn)后的算法能夠有效處理遮擋和尺度變化問題，并能在目標(biāo)消失后重現(xiàn)時(shí)再發(fā)現(xiàn)目標(biāo)，從而實(shí)現(xiàn)對目標(biāo)的長時(shí)間鎖定跟蹤。

3.1增加尺度變化

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

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

3.2引入遮擋判定

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

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

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

(7)

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

a　跟蹤結(jié)果

b　相似度變化圖1　進(jìn)入遮擋過程跟蹤結(jié)果圖像及相似度變化

3.3目標(biāo)的再發(fā)現(xiàn)

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

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

1)訓(xùn)練階段：假設(shè)在遮擋發(fā)生前跟蹤結(jié)果是準(zhǔn)確的，正樣本就是每一幀的跟蹤結(jié)果，負(fù)樣本則是在遮擋前跟蹤結(jié)果周圍較遠(yuǎn)的位置隨機(jī)選取的矩形圖像片，如圖2所示。

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

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

4實(shí)驗(yàn)結(jié)果與分析

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

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

a　CarScale

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

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

a　David

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

5小結(jié)

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

參考文獻(xiàn)：

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

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

鄭世寶，教授，主要研究網(wǎng)絡(luò)多媒體通信、智能視頻監(jiān)控以及老人健康信息技術(shù)；

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

責(zé)任編輯：時(shí)雯

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

文獻(xiàn)標(biāo)志碼:A

DOI：10.16280/j.videoe.2016.04.005

作者簡介：

收稿日期：2015-11-04

文獻(xiàn)引用格式：李宏波，鄭世寶，周芹. 一種改進(jìn)的長時(shí)間壓縮感知跟蹤算法[J].電視技術(shù)，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.