基于超像素和判別稀疏的運動目標跟蹤算法

邱曉榮，彭 力，劉全勝2，

1.馬來西亞管理科學(xué)大學(xué) 信息科學(xué)與工程學(xué)院，雪蘭莪 莎阿南 40100

2.無錫職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)技術(shù)學(xué)院，江蘇 無錫 214121

3.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

1 引言

運動目標跟蹤是指在連續(xù)的視頻或圖像序列中運用在線跟蹤算法對運動目標進行狀態(tài)估計和跟蹤的過程。作為機器視覺領(lǐng)域的重要研究方向，運動目標跟蹤已被廣泛應(yīng)用于視頻監(jiān)控、事件檢測、運動分析等領(lǐng)域。近年來，相關(guān)科研人員對常用的運動目標跟蹤算法進行了廣泛而有效的研究，Kristan等人[1]評估了70種有效算法在60個短視頻序列上的跟蹤效果，用以解決跟蹤過程中遇到的目標遮擋、光照變換、運動變換、尺寸變換、攝像機運動等干擾問題。根據(jù)Wu等人[2]所做的研究，一個完整的運動目標跟蹤算法通常由表觀模型、跟蹤策略以及更新策略3部分組成。其中如何構(gòu)建表觀模型是首要考慮的問題，表觀模型必須能夠精確地描述運動目標，可用于評價某一時刻候選目標與模板的相似程度。

根據(jù)表觀模型的不同表示方式，一般可以分為生成式算法和判別式算法兩大類。生成式算法一般基于全局特征模板匹配或基于子空間學(xué)習(xí)方法，前者可區(qū)分度較高，后者不變性較好。經(jīng)典的生成式算法有VTD[3]、L1APG[4]等，但此類算法一般不會考慮運動目標周圍的背景信息，以致在相似混雜背景干擾下運動目標跟蹤效果較差。判別式算法一般基于局部特征把跟蹤問題轉(zhuǎn)換成前景和背景的二元分類問題，經(jīng)典的算法有TLD[5]、ASLA[6]等，此類算法通過分類器分離出目標與背景，同時結(jié)合在線更新策略，取得了較好的跟蹤效果。近年來，Wang等人[7]提出了SPT算法，該算法充分利用了中層視覺線索超像素的特點，能夠較好地利用目標周圍背景信息應(yīng)對重度遮擋、非剛性變換等干擾因素的影響。Zhong等人[8]提出了生成式算法和判別式算法相結(jié)合的稀疏跟蹤模型，目標的表觀模型由稀疏的SGM和SDC兩種模型混合而成。吉訓(xùn)生等人[9]提出了基于HOG特征對目標幾何和光照的不變性，構(gòu)建在線判別稀疏字典，可以精確地區(qū)分目標和背景，降低漂移概率。孫凱等人[10]提出基于空間金字塔、稀疏編碼和多方位均值偏移的運動目標跟蹤算法，通過空間金字塔模型、局部模型和全局模型相結(jié)合抑制噪聲及光照的變化。Fan等人[11]提出基于傳統(tǒng)SPT和BoW算法構(gòu)建BoS表觀模型，取得了較好的跟蹤效果。

受上述相關(guān)研究的啟發(fā)，本文提出了一種超像素與判別稀疏相結(jié)合的運動目標跟蹤算法。該算法在傳統(tǒng)SPT算法的基礎(chǔ)上加入了一個判別稀疏函數(shù)，在由目標和背景信息構(gòu)成的超像素字典上通過?1范數(shù)最小化框架求解候選目標的稀疏系數(shù)，同時結(jié)合粒子濾波框架和在線字典更新策略完成目標跟蹤。實驗結(jié)果表明，本算法構(gòu)建的運動目標表觀模型具有較好的魯棒性，更好地實現(xiàn)了目標和背景的區(qū)分，能夠有效地應(yīng)對目標遮擋、非剛性變換、光照變換等干擾因素的影響。

2 基于超像素構(gòu)建初始表觀模型

2.1 超像素分割

超像素是指由相鄰像素構(gòu)成的像素塊，這些像素塊具有相似的亮度、顏色、紋理等方面的特征。同傳統(tǒng)的形狀固定的像素網(wǎng)格相比，超像素將原始圖像分割成了具有感知意義的中層視覺線索，可作為后續(xù)圖像處理任務(wù)的預(yù)處理步驟，是當前視覺領(lǐng)域的一項關(guān)鍵技術(shù)。

Achanta等[12]對基于超像素的圖像分割做了歸納和對比，其中最為快速高效的算法是SLIC算法，其基本原理如式（1）所示。其中[l,a,b,x,y]表示像素點的LAB顏色模型和二維坐標，[Nc,Ns]表示[dc,ds]的歸一化參數(shù)。

SLIC算法的特點是在不損壞原有圖像目標區(qū)域邊界的前提下，根據(jù)超像素個數(shù)、顏色空間相似度進行圖像分割。超像素個數(shù)越小，分割圖像所得的超像素數(shù)量越少。顏色空間相似度越小，超像素內(nèi)部亮度漸變平緩、突變梯度較小。

2.2 超像素字典的生成

為了能夠在跟蹤起始階段快速有效的建立運動目標的表觀模型，本文選取待測視頻序列的前5幀圖像構(gòu)建初始超像素字典，相關(guān)步驟如下：

（1）在跟蹤的初始階段，運動目標前景和背景一般變化不大，因此可以基于MeanShift算法在前5幀求出最優(yōu)目標區(qū)域，再用白色虛線框標出觀測區(qū)域，用白色實線框標出目標區(qū)域。其中觀測區(qū)域的邊長是目標區(qū)域?qū)蔷€長度的1.5倍，觀測區(qū)域與目標區(qū)域非重疊部分可視為背景區(qū)域，如圖1（a）所示。

（2）如圖1（b）所示，基于SLIC算法對前5幀的觀測區(qū)域分割超像素，設(shè)置每幀超像素個數(shù)為300、緊湊度為10，并用sprn表示第n幀的第r個超像素。

（3）如圖1（c）所示，繼續(xù)對所有超像素進行HIS特征提取，獲得歸一化后的顏色直方圖，并用 frn表示第n幀第r個超像素的特征向量。

（4）如圖1（d）所示，使用K-Means算法對所有超像素的特征向量進行聚類，用 fci表示第i個聚類中心的HIS歸一化特征向量。同時，計算各聚類的目標背景權(quán)值Wi，如式（2）所示：

圖1 超像素字典的生成過程

其中Wi的取值范圍為[0，1]，R+(i)表示第i個聚類區(qū)域與目標區(qū)域的重合面積，R-(i)表示該聚類區(qū)域與背景區(qū)域的重合面積。Wi越大，該聚類屬于目標區(qū)域的幾率越大，反之Wi越小則屬于背景區(qū)域的幾率越大。然后設(shè)定一個用于區(qū)分前景背景的閾值W0，將各聚類權(quán)值Wi的大小降序排列，大于W0的聚類屬于前景超像素字典，小于W0的聚類屬于背景超像素字典，這樣就構(gòu)成了可用于判別稀疏的初始超像素字典Dsp=[,]，如式（3）所示。其中n表示聚類個數(shù)，k表示屬于目標區(qū)域的聚類個數(shù)。

3 基于判別稀疏進行運動目標跟蹤

3.1 粒子濾波框架

運動目標實時在線跟蹤過程中，直接對場景中所有內(nèi)容進行相似度匹配，需要處理大量冗余信息，運算量大且沒有必要。因此利用跟蹤策略搜索算法有選擇地縮小搜索區(qū)域并進行最優(yōu)匹配具有非常重要的意義。常見的跟蹤策略主要有卡爾曼濾波和粒子濾波兩種算法。卡爾曼濾波算法一般只適用于線性高斯系統(tǒng)，而粒子濾波算法是一種基于貝葉斯蒙特卡洛采樣技術(shù)的最優(yōu)估計算法，它無需存儲和再處理先前的測量數(shù)據(jù)，可以直接以遞歸的方式對測量數(shù)據(jù)進行序貫處理，節(jié)省了大量計算和存儲空間，特別適用于非線性非高斯的運動目標跟蹤系統(tǒng)。

粒子濾波算法可以分為預(yù)測和更新兩個階段，分別如式（4）和式（5）所示。定義 xt=[ ]lx,ly,θ,s,α,? 為仿射向量，各仿射參數(shù)相互獨立且呈標準高斯分布，分別表示運動目標在第t幀的水平位移、垂直位移、水平方向尺度、旋轉(zhuǎn)角、高寬比和扭角。zt表示第t幀的觀測值，p(xt|xt-1)為狀態(tài)轉(zhuǎn)移概率，p(zt|xt)為xt的似然函數(shù)。

3.2 判別稀疏函數(shù)的表示

粒子濾波框架下，在當前幀t中一般基于上一幀的最優(yōu)候選粒子，在運動目標中心位置附近基于一個非常小的仿射向量，隨機創(chuàng)建n個候選粒子，然后基于表觀模型字典判定最優(yōu)粒子。傳統(tǒng)?1范數(shù)最小化的稀疏表示如式（6）所示，其中前一項是損失函數(shù)，用于保證訓(xùn)練誤差最小，后一項是正則化函數(shù)，λ非常小，防止過度擬合。

但是傳統(tǒng)的稀疏表示方法不具備判別性，并不適合信號分類問題的求解。為了更好地結(jié)合具有目標背景判別的超像素字典Dsp，本文在傳統(tǒng)稀疏表示算法的基礎(chǔ)上在‖Y - DspX中加入了判別函數(shù)的內(nèi)容，如式（7）所示：

式（7）中除正則化函數(shù)λ‖X ‖1外，其余項均可微且嚴格收斂，可求出相關(guān)最優(yōu)解。其中[||Y-Dsp+||Y-+]是具有判別功能的稀疏函數(shù)，表示候選粒子與整個超像素模板的全局相似度，表示與超像素字典中目標模板的局部相似度，表示與超像素字典中背景模板的局部相似度。從全局角度看，要求Y≈DX。從局部角度看，要求很小，表示目標應(yīng)該能夠被超像素目標模板較好地重構(gòu)，而要求很小，表示目標不能被超像素背景模板較好地重構(gòu)。這樣就可以最大限度地保證跟蹤結(jié)果保留跟蹤目標信息，排斥背景信息。

3.3 最優(yōu)跟蹤目標的確定

為了能夠從粒子濾波框架的眾多候選粒子中選出最優(yōu)粒子作為當前幀的跟蹤結(jié)果，還需通過式（8）計算候選目標和超像素字典Dsp之間的相似性。

其中，ξ1=||Y-表示目標模板的相似度，ξ2=||Y-表示背景模板的相似度，η是一個很小的數(shù)。一般當H值最小時說明對應(yīng)的候選粒子能夠較好地跟蹤運動目標。

3.4 遮擋檢測處理

確定了當前幀的最優(yōu)跟蹤目標之后，還需進一步判定目標在運動過程中是否受到遮擋，以便后期有效地更新表觀模型。如式（9）、式（10）所示，本文依據(jù)重構(gòu)誤差矩陣E計算當前幀最優(yōu)候選目標的遮擋系數(shù)O。

其中，ρ0表示重構(gòu)誤差閾值，當重構(gòu)誤差小于ρ0，表明該部分區(qū)域未發(fā)生遮擋，對應(yīng)的oi設(shè)為0；反之有遮擋時，對應(yīng)的oi設(shè)為1。

4 運動目標表觀模型的在線更新

在實際跟蹤過程中，目標和背景將受到多種因素的影響發(fā)生相關(guān)的變化，特別是背景的變化更為頻繁且無一定的相關(guān)性。為此，需要在線更新運動目標的表觀模型，以便及時修正運動目標的前背景變化，整個更新過程可以參考2.2節(jié)的相關(guān)內(nèi)容，包括樣本選擇和聚類更新兩個步驟。

在樣本選擇階段，需要判定當前幀的最優(yōu)候選粒子是否存在嚴重遮擋。本文算法根據(jù)式（10）計算目標受到遮擋的比率。當實際遮擋系數(shù)O大于指定遮擋閾值O0時，表明存在嚴重遮擋。這時，為了保留未遮擋時運動目標的相關(guān)信息，提高了跟蹤算法的有效性和魯棒性，需要去除表觀模型樣本集中時間最早一幀的超像素信息，在樣本集中保留最后5幀的位置不變，將當前幀的超像素信息存放到倒數(shù)第6幀的位置。而當不存在嚴重遮擋時，剔除最早一幀的超像素信息后，直接把當前幀的相關(guān)信息放在樣本集的末尾即可。

聚類更新階段，本文算法每隔15幀通過K-Means算法更新超像素聚類的相關(guān)信息。由于在實際跟蹤過程中，當運動目標被嚴重遮擋時，聚類結(jié)果仍然保留了未遮擋時運動目標的相關(guān)信息，有效提高了跟蹤算法的魯棒性。

5 實驗結(jié)果分析

為了驗證算法能否在復(fù)雜環(huán)境下進行有效跟蹤，本文按難易程度分別基于bird1、walking2、board、liquor等4個圖像幀序列，將本文算法與SPT[7]、L1APG[4]、SCM[8]、ALSA[6]等4種經(jīng)典算法做了定量和定性兩方面的對比分析。相關(guān)標準圖像幀序列和算法源碼可訪問文獻[2]提供的網(wǎng)址：http：//cvlab.hanyang.ac.kr/tracker_benchmark/index.html。

算法相關(guān)實驗都基于Matlab平臺，本文設(shè)定閾值W0=0.15來劃分超像素字典中的目標和背景，式（6）中防過度擬合參數(shù) λ=0.01，式（8）中η=0.2，式（10）中重構(gòu)誤差閾值ρ0=0.05，遮擋閾值O0=0.2。

5.1 定量分析

本文算法使用以下兩個標準來定量分析跟蹤的精度：

（1）中心距離誤差。如圖2所示，各子圖顯示了5種算法在指定圖像幀序列中實時跟蹤到的目標中心點與初始標定的目標中心點之間的像素距離。

表1顯示了5種算法分別對應(yīng)4個標準圖像幀序列的跟蹤成功率，并用黑色粗體標識了各視頻圖像幀序列的最優(yōu)算法。

圖2 中心距離誤差（像素）

圖3 視頻序列的跟蹤結(jié)果比較

表1 跟蹤成功率

5.2 定性分析

實驗1 bird1圖像幀序列較為復(fù)雜，其中的運動目標在做快速移動的同時，受到非剛性變換、移出視野等內(nèi)外部因素的影響。例如，第25幀處目標處于快速飛行過程中，同時不停地在做非剛性變換，此時ALSA算法發(fā)生了較大的偏移，其余4種算法能夠?qū)崿F(xiàn)較好的跟蹤效果，其中本文算法的跟蹤精度最高。第185幀處目標剛剛從滿屏遮蔽的云層中飛出，SPT算法、ALSA算法和本文算法能夠迅速由一定的漂移狀態(tài)重新精準定位目標。第309幀處目標呈現(xiàn)方式由尾部視圖轉(zhuǎn)到背部視圖，本文算法的跟蹤精度比SPT算法更高。

實驗2 walking2圖像序列中的目標在運動過程中主要受到尺度變化、遮擋等干擾因素的影響。例如，第228幀和第372幀處目標在行進過程中，兩次受到了移動物體的部分遮擋，除本文算法外，相關(guān)算法都開始產(chǎn)生了一定的漂移。第450幀處目標的尺度較初始尺度大幅變小，同時還受到了前向靜止物體的干擾，傳統(tǒng)SPT算法發(fā)生了較大的漂移，本文算法結(jié)合了判別稀疏的相關(guān)信息后，較為精準地跟蹤到了目標。

實驗3 board圖像幀序列中的運動目標受到了尺度變化、運動模糊、移出視野等干擾因素的影響。例如，第32幀處運動目標快速向右移動，本文算法能夠較好地跟蹤目標，其他算法都產(chǎn)生了一定程度的漂移。第120幀處運動目標部分移出了視野范圍，第437幀處目標由于快速運動產(chǎn)生了運動模糊，本文算法都能夠較為精準地跟蹤到目標。

實驗4 liquor圖像幀序列中的運動目標受到了光照變換、尺度變化、遮擋、快速運動等干擾因素的影響。例如，第420幀處運動目標圍繞左邊的酒瓶做了一次逆時針旋轉(zhuǎn)運動，本文算法能夠較好地跟蹤目標，其他算法都產(chǎn)生了一定程度的漂移。第503幀和第1 183幀處運動目標多次受到了較為嚴重的遮擋，本文算法都能夠較為精準地跟蹤到目標。

6 結(jié)束語

本文提出了一種基于超像素和判別稀疏的運動目標跟蹤算法。該算法在傳統(tǒng)SPT算法的基礎(chǔ)上，構(gòu)建了包含目標和背景信息的超像素字典，同時引入判別稀疏函數(shù)以及?1范數(shù)最小化框架，實現(xiàn)了運動目標的在線跟蹤。其優(yōu)點在于當目標處于重度遮擋、非剛性變換、光照變換等嚴重干擾因素的影響下，算法能夠準確地區(qū)分目標和背景，具有較好的穩(wěn)定性和魯棒性。

雖然本文算法能夠在多種復(fù)雜場景的圖像序列中取得較好的跟蹤效果，但由于在初始構(gòu)建和在線更新超像素聚類字典過程中用到了SLIC算法、K-Means算法、判別稀疏算法、粒子濾波算法，這些都提高了本文算法的運算復(fù)雜度。因此后期的研究工作可以著眼于對超像素聚類算法做相應(yīng)的改進，以使現(xiàn)有K-Means算法更快更準地找到超像素聚類的中心，這樣可以使本文算法具有更好的實時性和準確性。