基于超像素和判別稀疏的運(yùn)動(dòng)目標(biāo)跟蹤算法

邱曉榮，彭 力，劉全勝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 引言

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

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

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

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

2.1 超像素分割

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

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

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

2.2 超像素字典的生成

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

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

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

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

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

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

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

3 基于判別稀疏進(jìn)行運(yùn)動(dòng)目標(biāo)跟蹤

3.1 粒子濾波框架

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

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

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

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

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

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

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

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

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

3.4 遮擋檢測(cè)處理

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

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

4 運(yùn)動(dòng)目標(biāo)表觀模型的在線更新

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

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

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

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

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

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

5.1 定量分析

本文算法使用以下兩個(gè)標(biāo)準(zhǔn)來定量分析跟蹤的精度：

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

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

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

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

表1 跟蹤成功率

5.2 定性分析

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

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

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

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

6 結(jié)束語

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

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