基于稀疏表示和粒子濾波的在線目標(biāo)跟蹤算法

王海羅， 汪渤， 高志峰， 周志強(qiáng)， 李筍

(北京理工大學(xué) 自動(dòng)化學(xué)院，北京 100081)

?

基于稀疏表示和粒子濾波的在線目標(biāo)跟蹤算法

王海羅， 汪渤， 高志峰， 周志強(qiáng)， 李筍

(北京理工大學(xué) 自動(dòng)化學(xué)院，北京 100081)

針對(duì)目標(biāo)跟蹤過程中由于外形變化或者遮擋所造成的跟蹤效果下降或?qū)е缕频膯栴}，提出一種粒子濾波框架下基于稀疏表示的在線目標(biāo)跟蹤算法. 采用分層梯度方向直方圖(PHOG)特征對(duì)目標(biāo)模板進(jìn)行描述，并且每一個(gè)候選模板都可以通過PHOG基向量和瑣碎模板進(jìn)行稀疏表示，進(jìn)而利用L1范數(shù)最小化方法進(jìn)行最優(yōu)求解. 為保證在遮擋的情況下目標(biāo)跟蹤的精度，對(duì)目標(biāo)遮擋部分和非遮擋部分進(jìn)行拆分建模，并利用PCA子空間增量學(xué)習(xí)的方式不斷更新目標(biāo)跟蹤模型. 通過對(duì)具有挑戰(zhàn)性的跟蹤視頻進(jìn)行定性和定量分析，實(shí)驗(yàn)證明該方法在跟蹤精度上要優(yōu)于傳統(tǒng)的跟蹤方法.

稀疏表示；PCA增量學(xué)習(xí)；PHOG特征；在線目標(biāo)跟蹤

視頻目標(biāo)跟蹤是計(jì)算機(jī)視覺領(lǐng)域中的經(jīng)典問題，融合了圖像處理、模式識(shí)別、機(jī)器學(xué)習(xí)等多種技術(shù)，在跟蹤過程中，由于光照變化、目標(biāo)形變以及遮擋等因素存在，給跟蹤造成很大困難，研究精度高而且魯棒的目標(biāo)跟蹤方法仍是一項(xiàng)挑戰(zhàn).

為了克服這些困難，學(xué)者們提出了大量的跟蹤方法，根據(jù)實(shí)現(xiàn)方式的不同，主要分為基于辨別模型的目標(biāo)跟蹤和基于產(chǎn)生模型的目標(biāo)跟蹤. 在辨別模型中，目標(biāo)跟蹤被歸類為一種二進(jìn)制分類問題，通過分類器的學(xué)習(xí)將目標(biāo)從背景中分離出來，如Ensemble tracker[1]，在線多目標(biāo)跟蹤[2]、壓縮跟蹤[3]. 產(chǎn)生模型是通過對(duì)目標(biāo)外觀進(jìn)行建模，將目標(biāo)跟蹤問題轉(zhuǎn)化為尋找具有最小重構(gòu)誤差的目標(biāo)觀測(cè)值，如Eigentracker[4]，Mean-shift跟蹤[5]，增量跟蹤[6]以及協(xié)方差跟蹤[7].

近幾年來，稀疏表示逐漸被用于目標(biāo)跟蹤[8-9]. 稀疏表示的最大優(yōu)勢(shì)在于對(duì)圖像目標(biāo)變化和遮擋情況具有很好的魯棒性. Mei等[10]提出一種基于L1范數(shù)最小化的跟蹤方法，將稀疏表示引入粒子濾波的框架，取得了很好的跟蹤結(jié)果，不過這種方法每幀圖像都要處理上百次的L1最小化過程，計(jì)算復(fù)雜度高，處理速度較慢，為了平衡跟蹤速度，只能降低模板的分辨率，而低分辨率的模板并不能提供足夠的跟蹤信息來表示目標(biāo). 另外，L1跟蹤不像子空間表示方法那樣能夠利用豐富的圖像屬性，例如目標(biāo)本身的結(jié)構(gòu)信息來進(jìn)行判斷. 針對(duì)以上問題，本文對(duì)其進(jìn)行了兩部分改進(jìn)，一是對(duì)目標(biāo)模板的描述不再采用模板本身，而是采用分層梯度方向直方圖特征(PHOG)對(duì)目標(biāo)模板進(jìn)行表示，PHOG特征具備空間結(jié)構(gòu)性，對(duì)目標(biāo)類別有很強(qiáng)的辨別力，能夠提供更好的分類性能，而且該特征維數(shù)少，可加快處理速度. 二是對(duì)稀疏表示的數(shù)學(xué)模型進(jìn)行優(yōu)化，將目標(biāo)外觀部分和其他噪聲部分進(jìn)行拆分建模，并利用PCA增量學(xué)習(xí)的方式不斷更新目標(biāo)跟蹤模型來適應(yīng)跟蹤過程中的目標(biāo)變化.

1 L1范數(shù)跟蹤

1.1 粒子濾波框架

粒子濾波是估計(jì)隨機(jī)變量后驗(yàn)概率分布的工具，通常包括兩個(gè)部分：預(yù)測(cè)和更新. 假設(shè)t幀時(shí)刻，定義xt為目標(biāo)位置信息的狀態(tài)值，定義z1:t={z1，z2，…，zt-1}為從第一幀到t-1幀的觀察值，則粒子濾波通過下面兩個(gè)步驟計(jì)算t幀時(shí)刻的目標(biāo)信息

(1)

(2)

(3)

為了避免退化情況，樣本要根據(jù)其權(quán)值大小進(jìn)行重采樣，即以權(quán)值較大粒子進(jìn)行復(fù)制來代替權(quán)值較小的粒子.

1.2 稀疏表示

在L1跟蹤中，候選目標(biāo)采樣都可以用字典模板T=[t1t2…tn]∈Rd×n(d?n)稀疏的線性表示，其中n為目標(biāo)模板個(gè)數(shù)，d為模板維數(shù)，每一個(gè)目標(biāo)模板都會(huì)以一維列向量進(jìn)行存儲(chǔ). 目標(biāo)模板中經(jīng)常摻雜了一些噪聲或者遭遇遮擋的情況，因此候選跟蹤目標(biāo)y∈Rd可以由字典模板T近似表示為

(4)

式中：a=[a1a2… an]T∈Rn為候選目標(biāo)系數(shù)向量；ε為含有非0值的誤差向量；非0值所對(duì)應(yīng)y中的位置表示被噪聲干擾或者被遮擋. 由于噪聲干擾具有隨機(jī)性，無法進(jìn)行量化描述，但對(duì)于遮擋情況，可以采用瑣碎模板I=[i1i2…id]∈Rd×d進(jìn)行描述為

(5)

式中：瑣碎模板ii∈Rd為只包含一個(gè)非0值的向量；e=[e1e2…ed]T∈Rd為瑣碎模板的系數(shù)向量. 假設(shè)每一個(gè)候選目標(biāo)可以用目標(biāo)模板和瑣碎模板稀疏表示，則上式可以通過L1最小化求解

(6)

由于誤差向量e可以表示任意稀疏噪聲，所以可以處理各種目標(biāo)外觀變化的情況.

2 目標(biāo)跟蹤算法

2.1 分層梯度方向直方圖(PHOG)特征

分層梯度方向直方圖(pyramid histogram of oriented gradients，PHOG)是一種描述空間形狀的特征向量，具有較強(qiáng)的抗噪性能，廣泛應(yīng)用于圖像檢索等模式識(shí)別工作中，并已取得穩(wěn)定、良好的效果. 本文采用該特征作為跟蹤目標(biāo)的向量化表示.

PHOG特征提取方法如下：

① 獲取圖像邊緣. 利用Canny邊界檢測(cè)算法提取目標(biāo)模板的邊緣，而PHOG特征就是在目標(biāo)邊緣的位置進(jìn)行提取. PHOG描述的是目標(biāo)形狀特征.

② 塔式分層結(jié)構(gòu). 將目標(biāo)模板分為L(zhǎng)層，第0層為目標(biāo)模板本身，第i層則將目標(biāo)模板沿行列兩個(gè)方向均分割成2i個(gè)單元，共形成4i個(gè)區(qū)域來進(jìn)行直方圖統(tǒng)計(jì)，這樣每一層的子區(qū)域都是前一層子區(qū)域的1/4.

③ 梯度方向直方圖統(tǒng)計(jì). 將[0，180°]平均分為K個(gè)區(qū)間，在目標(biāo)模板中檢測(cè)到邊緣的位置進(jìn)行HOG特征提取，并在所有層的所有子區(qū)域進(jìn)行梯度直方圖統(tǒng)計(jì).

④ PHOG特征獲取. 將所有層所得的向量串聯(lián)起來得到一個(gè)K∑4i維的列向量，即作為該目標(biāo)模板的PHOG特征，并對(duì)其進(jìn)行歸一化處理.

圖1為PHOG特征示意圖，第1行為目標(biāo)模板和不同塔層的區(qū)域劃分，第2行為各個(gè)塔層所對(duì)應(yīng)的梯度方向直方圖統(tǒng)計(jì). 從圖1中可以看出，同一類別的物體，具有相似的PHOG分布特征，而非同類別的物體，其PHOG分布特征差異很大.

2.2 跟蹤目標(biāo)模型

在跟蹤過程中，根據(jù)圖像仿射變換對(duì)相鄰幀間的目標(biāo)運(yùn)動(dòng)進(jìn)行建模. 設(shè)狀態(tài)變量xt由6個(gè)仿射參數(shù)構(gòu)成：xt={xt，yt，θt，st，αt，φt}，其中xt，yt，θt，st，αt，φt分別定義坐標(biāo)x，y變換、旋轉(zhuǎn)角度、尺度、長(zhǎng)寬比和歪斜變化. 通過使用xt作為仿射變換的參數(shù)，可以從圖像zt中獲得興趣區(qū)域并統(tǒng)一歸一化為目標(biāo)模板的大小. 使用高斯分布對(duì)狀態(tài)變化分布p(xt|xt-1)進(jìn)行建模，且假設(shè)6個(gè)仿射參數(shù)相互獨(dú)立. 觀察模型p(zt|xt)反映了候選目標(biāo)與目標(biāo)模板的接近程度，通過使用L1最小化方法進(jìn)行求解.

L1跟蹤通過解方程(6)來求取候選目標(biāo)的最佳位置，但是由于表征目標(biāo)模板的向量維數(shù)很高，所以計(jì)算復(fù)雜耗時(shí)明顯. 為了更加有效地描述目標(biāo)模板和進(jìn)行稀疏求解，本文采用子空間學(xué)習(xí)和稀疏表示的方法對(duì)目標(biāo)模型進(jìn)行建模，也可以理解為通過PCA方法將子空間學(xué)習(xí)引入到L1跟蹤的框架里. 對(duì)跟蹤目標(biāo)進(jìn)行如下建模

(7)

式中：y為觀察向量；U為PHOG特征經(jīng)PCA處理后得到的基向量矩陣；z為基向量系數(shù)；e為誤差項(xiàng)也即瑣碎模板系數(shù). 相區(qū)別于L1跟蹤框架中的模板項(xiàng)，不再由目標(biāo)模板和瑣碎模板組成，而是由PCA基向量和瑣碎模板組成. 可以通過下式對(duì)式(7)進(jìn)行求解

(8)

與式(6)不同的是，L1跟蹤中不論是目標(biāo)模板還是瑣碎模板其模板系數(shù)都應(yīng)該是稀疏的，而式(8)中PHOG特征的PCA基向量系數(shù)并不是稀疏的，只有瑣碎模板的系數(shù)才是稀疏的(當(dāng)瑣碎模板的數(shù)量遠(yuǎn)大于基向量個(gè)數(shù)的時(shí)候，這個(gè)模型仍然可以是一個(gè)稀疏表示).

在預(yù)測(cè)階段，在第i個(gè)采樣狀態(tài)xi下，每一個(gè)候選模板的觀測(cè)似然概率可以用下面的公式表示為

(9)

然而，式(9)是在沒有發(fā)生遮擋的情況下的概率，當(dāng)遮擋發(fā)生時(shí)，這里采用將遮擋部分和非遮擋部分分開處理的方式，按照式(10)來表示觀測(cè)概率

(10)

2.3 更新目標(biāo)模型

在跟蹤過程中，更新目標(biāo)跟蹤模型對(duì)處理目標(biāo)外觀變化起很重要的作用. 如果不更新模板，模板就不能適應(yīng)因光照或者姿態(tài)改變而發(fā)生的外觀變化；如果更新模板過于頻繁，由于每次更新都會(huì)引入小的誤差，這些誤差會(huì)隨著頻繁更新而被積累最終產(chǎn)生漂移問題導(dǎo)致跟蹤失敗. 為此，由于瑣碎模板的稀疏系數(shù)可以用來檢測(cè)遮擋，可根據(jù)遮擋情況選擇更新時(shí)機(jī). 首先，根據(jù)瑣碎模板系數(shù)，將其映射為2D圖，圖中非零像素就表示該位置被遮擋. 其次，根據(jù)下式計(jì)算遮擋比率

(11)

設(shè)定兩個(gè)閾值T1與T2來描述遮擋的程度(例如T1=0.1，T2=0.6). 最后，根據(jù)η的取值范圍判定遮擋程度. 如果ηT2說明目標(biāo)有大部分遭遇遮擋，這種情況下則放棄使用該采樣模板進(jìn)行更新. 當(dāng)積累了足夠的樣本模板以后，采用增量PCA的方法對(duì)目標(biāo)跟蹤模型進(jìn)行更新.

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

本文算法的實(shí)驗(yàn)硬件平臺(tái)為Intel (R) Core i3 3.4 GHz處理器，內(nèi)存4 GB的PC機(jī)，在Matlab 環(huán)境下進(jìn)行實(shí)現(xiàn). 至于PHOG特征，為了防止過擬合的問題，取L=3，K=20，這樣每一個(gè)目標(biāo)模版可以用420維向量進(jìn)行表征. 式(8)中的正則化常量λ設(shè)為0.05，為平衡算法的效率和精度，在所有實(shí)驗(yàn)中取粒子數(shù)為600并且每5幀進(jìn)行一次更新. 為了驗(yàn)證算法的有效性，將本文算法與4種經(jīng)典傳統(tǒng)算法進(jìn)行比較，包括L1[10]，MIL[11]，VTD[12]，F(xiàn)ragTrack[13]，通過實(shí)驗(yàn)給出了定性和定量的比較結(jié)果.

3.1 定性分析

實(shí)驗(yàn)中選取了3段有挑戰(zhàn)的視頻序列作為測(cè)試視頻(Occlusion2，Car11，Jumping)，所選用的視頻中包含了目標(biāo)遮擋、光線變化以及目標(biāo)快速運(yùn)動(dòng)等具有代表性的目標(biāo)跟蹤難題. 為更好地比較幾種算法的跟蹤精度，將實(shí)驗(yàn)結(jié)果同時(shí)標(biāo)注在同一視頻幀上，其中L1對(duì)應(yīng)黑色框，MIL對(duì)應(yīng)藍(lán)色框，VTD對(duì)應(yīng)綠色框，F(xiàn)ragTrack對(duì)應(yīng)黃色框，本文算法對(duì)應(yīng)紅色框，如下文所示.

① 目標(biāo)遮擋. 在Occlusion2的視頻序列中，目標(biāo)被嚴(yán)重遮擋，當(dāng)在目標(biāo)伴有歪頭等仿射變化的時(shí)候，由于本算法將目標(biāo)形變參數(shù)納入目標(biāo)估計(jì)的考量范疇，所以在處理350幀和470幀的時(shí)候能夠很好的隨目標(biāo)歪頭而跟著旋轉(zhuǎn)，并且在遮擋情況下仍保持很好的精度，其他幾種算法雖也能成功跟蹤目標(biāo)，但精度卻不及本文算法，并且在第700幀時(shí)候目標(biāo)被嚴(yán)重遮擋，通過圖2可以看出本文算法較其他幾種算法能夠獲得更好的跟蹤結(jié)果.

② 光線變化. Car11序列中目標(biāo)車輛在夜間行駛，光線條件差，而且周圍光源對(duì)跟蹤任務(wù)也有干擾，跟蹤難度大. 圖3是各個(gè)算法的跟蹤效果展示，從跟蹤結(jié)果可以看出，F(xiàn)ragTrack在第150幀的時(shí)候開始發(fā)生漂移，一直到視頻結(jié)束，未能再次捕獲目標(biāo)，跟蹤失?。欢鳯1、MIL和VTD在第250幀之前一直能夠跟蹤目標(biāo)車輛，雖然有跟蹤偏移但是并沒有丟失跟蹤目標(biāo)，到250幀之后，對(duì)面有車輛靠近的時(shí)候，這3種算法轉(zhuǎn)而跟蹤到了對(duì)面的車輛上面，未能成功跟蹤到最后；但是本文提出的算法能夠從始至終很穩(wěn)定的跟蹤目標(biāo)，即使在光線變化，相似目標(biāo)干擾的情況下均保持了很好的跟蹤性能.

③ 快速運(yùn)動(dòng). 由于傳統(tǒng)算法通常是基于相鄰幀目標(biāo)變化微弱的假設(shè)進(jìn)行建模，故在應(yīng)對(duì)快速變化的運(yùn)動(dòng)目標(biāo)時(shí)容易發(fā)生丟失跟蹤. 圖4為Jumping視頻序列，目標(biāo)一直處于運(yùn)動(dòng)過程中，這為跟蹤增加了很大的難度. 不適應(yīng)這種快速變化的VTD算法很快就丟失跟蹤目標(biāo)；而L1和FragTrack在第100幀的時(shí)候也已經(jīng)發(fā)生漂移，只有MIL和本文算法能夠成功穩(wěn)定地跟蹤處于快速運(yùn)動(dòng)的目標(biāo)，從第150及第200幀可以看出，在跟蹤精度上本文算法要明顯優(yōu)于MIL算法.

3.2 定量分析

跟蹤誤差定量分析中，本文采用常用的中心誤差準(zhǔn)則，定義為目標(biāo)實(shí)際位置與手動(dòng)標(biāo)注位置之間的均方根. 如圖5所示，其中橫坐標(biāo)為圖像幀序號(hào)(frame number)，縱坐標(biāo)為以像素為單位的跟蹤誤差(tracking error). 從跟蹤誤差曲線可以看出，在Occlusion2、Car11和Jumping 3個(gè)視頻序列的實(shí)驗(yàn)中，本文算法(紅色實(shí)線)都以最小的跟蹤誤差明顯優(yōu)于目前幾種主流的目標(biāo)跟蹤算法.

跟蹤算法中最耗時(shí)的部分為模板系數(shù)的計(jì)算過程，L1跟蹤是通過LASSO方法進(jìn)行系數(shù)求解，其算法復(fù)雜度為O(d2+dk)，其中d為目標(biāo)模板的向量維數(shù)，k為模板個(gè)數(shù)，通常d?k. 本文算法在L1跟蹤基礎(chǔ)上進(jìn)行改進(jìn)，復(fù)雜度降為O(ndk)，其中n為算法執(zhí)行迭代次數(shù)，有效提升了算法效率.

4 結(jié) 論

提出了一種基于稀疏表示和粒子濾波的在線目標(biāo)跟蹤算法，通過采用具有強(qiáng)區(qū)分度的分層梯度方向直方圖(PHOG)特征作為目標(biāo)模版的基向量，加上瑣碎模板一起作為稀疏表示的字典來對(duì)跟蹤目標(biāo)進(jìn)行建模. 對(duì)目標(biāo)狀態(tài)進(jìn)行建模的時(shí)候，將目標(biāo)遮擋部分與非遮擋部分進(jìn)行拆分，加強(qiáng)了對(duì)遮擋情況的檢測(cè)，并利用PCA增量學(xué)習(xí)方式來更新目標(biāo)跟蹤模型，很好地克服了在跟蹤過程中由于目標(biāo)形變和遮擋所帶來的跟蹤困難，并通過實(shí)驗(yàn)驗(yàn)證了該算法的有效性和魯棒性.

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

[2] Babenko B， Yang M H， Belongie S. Visual tracking with online multiple instance learning[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.[S.l.]: IEEE， 2009:983-990.

[3] Zhang K， Zhang L， Yang M H. Real-time compressive tracking[M]. Berlin, Heidelberg: Springer, 2012.

[4] Black M J， Jepson A D. Eigentracking: robust matching and tracking of articulated objects using a view-based representation[J]. International Journal of Computer Vision， 1998，26(1):63-84.

[5] Comaniciu D， Ramesh V， Meer P. Kernel-based object tracking[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2003，25(5):564-577.

[6] Ross D A， Lim J， Lin R S， et al. Incremental learning for robust visual tracking[J]. International Journal of Computer Vision， 2008，77(1-3):125-141.

[7] Porikli F， Tuzel O， Meer P. Covariance tracking using model update based on lie algebra[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]: IEEE， 2006:728-735.

[8] Li H， Shen C， Shi Q. Real-time visual tracking using compressive sensing[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]: IEEE，2011:1305-1312.

[9] Mei X， Ling H. Robust visual tracking and vehicle classification via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011，33(11):2259-2272.

[10] Mei X， Ling H. Robust visual tracking using L1 minimization[C]∥Proceedings of IEEE 12th International Conference on Computer Vision. [S.l.]: IEEE，2009:1436-1443.

[11] Jia X， Lu H， Yang M H. Visual tracking via adaptive structural local sparse appearance model[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR).[S.l.]: IEEE， 2012:1822-1829.

[12] Kwon J， Lee K M. Visual tracking decomposition[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR). [S.l.]: IEEE，2010:1269-1276.

[13] Adam A， Rivlin E， Shimshoni I. Robust fragments-based tracking using the integral histogram[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. [S.l.]: IEEE， 2006:798-805.

(責(zé)任編輯：李兵)

Sparse Representation and Particle Filter Based Online Object Tracking Algorithm

WANG Hai-luo， WANG Bo， GAO Zhi-feng， ZHOU Zhi-qiang， LI Sun

(School of Automation， Beijing Institute of Technology， Beijing 100081， China)

Changes of object appearance and occlusion always lead to tracking performance degradation or drift problem during tracking. To solve these problems， a sparse representation and particles filter based online tracking algorithm was proposed which used pyramid histogram of oriented gradients (PHOG) to describe the object template. In the framework， the candidate template can be represented by object templates and trivial templates sparsely， and then L1 minimization was exploited to find the optimal solution. To ensure the accuracy of tracking， the object function was divided into two parts to model the occlusion part and non-occlusion part separately. Both qualitative and quantitative evaluations on challenging image sequences demonstrate that the proposed algorithm performs favorably against several state-of-the-art methods.

sparse representation; PCA incremental learning; PHOG feature; on-line object tracking

2015-01-07

王海羅(1985—)，男，博士生，E-mail：hailuo0112@163.com；汪勃(1963—)，男，教授，博士生導(dǎo)師，E-mail:wangbobit.edu.cn.

TP 391

A

1001-0645(2016)06-0635-06

10.15918/j.tbit1001-0645.2016.06.016