劉翠君，趙才榮，苗奪謙，王學(xué)寬

(同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海 201804)

?

?；腗ean Shift行人跟蹤算法

劉翠君，趙才榮，苗奪謙，王學(xué)寬

(同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海 201804)

Mean Shift行人跟蹤采用顏色特征直方圖作為跟蹤特征，存在易受背景顏色干擾等問(wèn)題?；诖耍趥鹘y(tǒng)的Mean Shift行人跟蹤算法中引入粒計(jì)算的思想，提出?；腗ean Shift行人跟蹤算法，對(duì)圖像目標(biāo)區(qū)域作粒層分塊來(lái)提取塊顏色特征信息，并在顏色特征表示上作不同粒度的?；詈笤贛ean Shift迭代框架下實(shí)現(xiàn)行人跟蹤。該方法相比傳統(tǒng)的跟蹤方法具有計(jì)算復(fù)雜度更低、穩(wěn)健性更好的優(yōu)點(diǎn)。在PETS2009和CAVIAR數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)表明，這種方法跟蹤正確率更高，在顏色干擾下穩(wěn)健性更好，能夠?qū)崟r(shí)有效地跟蹤行人。

信息粒；粒計(jì)算；Mean Shift；特征提取；行人跟蹤

中文引用格式：劉翠君，趙才榮，苗奪謙，等. ?；腗ean Shift行人跟蹤算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(4): 433-441.

英文引用格式：LIU Cuijun， ZHAO Cairong， MIAO Duoqian， et al. Granular mean shift pedestrian tracking algorithm[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 433-441.

行人跟蹤涉及行人檢測(cè)和行人跟蹤兩部分。行人檢測(cè)屬于運(yùn)動(dòng)目標(biāo)檢測(cè)，目的是從圖像序列中將行人目標(biāo)從背景圖像中提取出來(lái)；行人跟蹤則是在視頻圖像序列中檢測(cè)定位出行人，包括目標(biāo)建模、目標(biāo)匹配和目標(biāo)定位[1]。行人跟蹤算法分屬兩大類(lèi)：確定性跟蹤和隨機(jī)跟蹤。確定性跟蹤以Mean Shift (MS)跟蹤為主線，是以相似度度量作為代價(jià)函數(shù)的優(yōu)化問(wèn)題，有一系列基于MS的跟蹤算法[2-9]；隨機(jī)跟蹤將視覺(jué)跟蹤轉(zhuǎn)化為貝葉斯理論框架下的狀態(tài)估計(jì)問(wèn)題，目前典型的隨機(jī)跟蹤算法有Kalman濾波跟蹤[10]和粒子濾波跟蹤[11]。以MS為代表的行人跟蹤算法因其簡(jiǎn)單穩(wěn)健的優(yōu)勢(shì)而廣受研究者青睞。文獻(xiàn)[1]對(duì)MS跟蹤算法的經(jīng)典文獻(xiàn)和研究歷程做了詳細(xì)綜述。2003年D.Comaniciu 等[2]將MS應(yīng)用于視覺(jué)跟蹤領(lǐng)域，首次提出MS跟蹤算法，開(kāi)辟了視覺(jué)跟蹤領(lǐng)域的新方向，自此有大量關(guān)于MS的改進(jìn)算法被提出。為提高M(jìn)S跟蹤算法的適應(yīng)能力，在目標(biāo)模板更新策略上，文獻(xiàn)[3]提出基于線性加權(quán)的模板更新；文獻(xiàn)[4]提出基于濾波的模板更新方法；在目標(biāo)尺度及方向估計(jì)上，文獻(xiàn)[5]提出基于特征點(diǎn)匹配的尺度與方向估計(jì)方法，消除由于尺度變化導(dǎo)致的定位誤差；文獻(xiàn)[6]提出基于權(quán)重圖的尺度與方向估計(jì)方法，能更準(zhǔn)確地反應(yīng)目標(biāo)尺度信息；在抗遮擋跟蹤上，文獻(xiàn)[7]在MS跟蹤算法的基礎(chǔ)上引入Kalman濾波器來(lái)輔助預(yù)測(cè)目標(biāo)位置，增強(qiáng)了穩(wěn)健性；文獻(xiàn)[8]提出目標(biāo)分塊的方法，通過(guò)子塊的跟蹤定位來(lái)獲得目標(biāo)的整體位置；在跟蹤快速目標(biāo)上，MS迭代容易陷入局部最優(yōu)值，使得無(wú)法處理快速運(yùn)動(dòng)的目標(biāo)，文獻(xiàn)[9]引入模擬退火算法，提出退火MS來(lái)逐步平滑代價(jià)函數(shù)，用于全局模式的搜索，跳出局部最優(yōu)值。

MS跟蹤向來(lái)以計(jì)算簡(jiǎn)單、調(diào)節(jié)參數(shù)少為優(yōu)勢(shì)，這些改進(jìn)算法盡管從不同方面改進(jìn)了MS跟蹤算法的缺陷，但是也一定程度上增加了計(jì)算復(fù)雜度和調(diào)節(jié)參數(shù)，無(wú)法很好地保證跟蹤實(shí)時(shí)性。 MS跟蹤存在的挑戰(zhàn)問(wèn)題有許多，本文旨在基本保留MS的跟蹤框架上解決MS跟蹤的基本問(wèn)題：顏色直方圖帶來(lái)的干擾問(wèn)題和計(jì)算復(fù)雜度問(wèn)題。考慮到顏色直方圖對(duì)于目標(biāo)形狀、姿態(tài)、旋轉(zhuǎn)等變化及遮擋都具有一定的魯棒性，但是由于攝像機(jī)的視頻圖像質(zhì)量普遍較差，分辨率普遍較低，易受背景顏色干擾，使得采集到的目標(biāo)顏色特征存在較大的噪聲冗余信息，然而粒計(jì)算方法恰巧能有效地處理視頻圖像大數(shù)據(jù)冗余信息。

粒計(jì)算方法由Zadeh[12]和Lin[13]首次提出，是人工智能領(lǐng)域中的一種新理念和新方法，它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，主要用于對(duì)不確定、不精確、不完整信息的處理，對(duì)大規(guī)模海量數(shù)據(jù)的挖掘和對(duì)復(fù)雜問(wèn)題的求解[14]。粒計(jì)算的實(shí)質(zhì)是通過(guò)選擇合適的粒度，來(lái)尋找一種較好的、近似的解決方案，避免復(fù)雜的計(jì)算，從而降低問(wèn)題求解的難度。文獻(xiàn)[15]歸納了粒計(jì)算方法在大數(shù)據(jù)處理中的3種基本模式并討論了粒計(jì)算方法應(yīng)用于大數(shù)據(jù)的可行性及優(yōu)勢(shì)?？紤]到攝像機(jī)視頻圖像中的海量數(shù)據(jù)挖掘和行人跟蹤問(wèn)題的復(fù)雜計(jì)算，試圖通過(guò)粒計(jì)算方法找到降低計(jì)算代價(jià)并有效改進(jìn)跟蹤效果的方法。

本文提出?；腗S行人跟蹤算法，基本保留MS跟蹤算法框架，引入粒計(jì)算方法來(lái)優(yōu)化顏色特征表示，在顏色特征的采集和處理上都采用粒計(jì)算方法表示，得到?；蟮暮撕瘮?shù)加權(quán)顏色直方圖作為顏色特征表示，通過(guò)MS迭代實(shí)現(xiàn)行人跟蹤，一定程度上削弱了圖像噪聲干擾，不僅降低了計(jì)算代價(jià)，而且提高了跟蹤實(shí)時(shí)性。

1　顏色特征?；?/h2>

將大量的復(fù)雜特征及信息按其各自的特征及性能劃分為若干個(gè)較簡(jiǎn)單的塊，每一塊看作是一個(gè)信息粒，這些信息粒具有相似的特征及性能，這個(gè)劃分過(guò)程就是信息?；倪^(guò)程。

定義1用一個(gè)三元組來(lái)描述信息粒G=(IG,EG,FG)，其中IG稱(chēng)為信息粒G的內(nèi)涵，EG稱(chēng)為信息粒G的外延；FG稱(chēng)為內(nèi)涵和外延之間的轉(zhuǎn)換函數(shù)。

信息粒的內(nèi)涵IG是信息粒在特定環(huán)境下的表現(xiàn)知識(shí)，表示在一個(gè)特定的任務(wù)下信息粒中所有元素的一般性特征、規(guī)則、共同性等，可以定義一個(gè)語(yǔ)言，由這個(gè)語(yǔ)言的公式來(lái)表示；信息粒的外延EG是滿(mǎn)足這個(gè)公式的所有對(duì)象的集合；信息粒的轉(zhuǎn)換函數(shù)FG是EG到IG的泛化轉(zhuǎn)換函數(shù)。對(duì)于信息粒G=(IG,EG,FG)，X為對(duì)于信息粒G所有可能外延EG的對(duì)象的集合，即外延的論域；Y為對(duì)于信息粒G所有可能內(nèi)涵IG的集合，即內(nèi)涵的論域。下面給出轉(zhuǎn)換函數(shù)FG的形式化定義。

定義2從X到Y(jié)的信息粒的泛化轉(zhuǎn)換函數(shù)是笛卡爾積X×Y的一個(gè)子集FG，對(duì)于每個(gè)屬于X的EG都存在唯一的Y中的元素IG使得(EG,IG)屬于FG。

傳統(tǒng)的MS行人跟蹤算法采集行人目標(biāo)區(qū)域的顏色特征信息，粒化的MS行人跟蹤算法引入粒計(jì)算的思想對(duì)顏色特征信息進(jìn)行?；瑑蓚€(gè)信息?；^(guò)程：圖像?；皖伾ǖ懒；?。

1.1圖像粒化

行人目標(biāo)區(qū)域存在背景顏色干擾，為了減弱背景顏色干擾和降低計(jì)算代價(jià)，將圖像行人目標(biāo)區(qū)域進(jìn)行不同粒度的粒層分塊，并采集每一粒塊的R、G、B顏色均值，得到圖像特征信息粒格，簡(jiǎn)稱(chēng)圖像粒，該過(guò)程為圖像?；?。用三元組GI=(IGI,EGI,FGI)表示圖像粒，內(nèi)涵IGI是由外延EGI集合中的每個(gè)對(duì)象通過(guò)轉(zhuǎn)換關(guān)系FGI計(jì)算出的R、G、B顏色均值集合。外延EGI的論域XI={M×NM,N∈}，其中M×N表示大小為M×N的圖像粒塊，∈XI,i=1,2,…,nRI，表示圖像粒度為RI時(shí)的第i個(gè)圖像粒塊，其中RI={1,2,…}表示圖像粒層分塊的粒度。相同粒度下的圖像粒塊大小一致，令原始圖像塊大小為m×n，圖像粒度為RI時(shí)的圖像粒塊的大小為mRI×nRI，nRI表示粒度為RI時(shí)的圖像粒塊總數(shù)，有

(1)

(2)

轉(zhuǎn)換函數(shù)對(duì)外延集合中的每個(gè)圖像粒塊求R、G、B三通道的顏色特征均值，得到圖像粒的內(nèi)涵集合，外延集合中的粒塊對(duì)象和內(nèi)涵集合中顏色特征向量對(duì)象一一對(duì)應(yīng)，內(nèi)涵集合中的所有顏色特征向量對(duì)象構(gòu)成該圖像目標(biāo)區(qū)域的顏色特征矩陣。

圖1為?；腗S行人跟蹤算法的圖像?；^(guò)程示意圖。

圖1　圖像?；^(guò)程Fig.1　Image granulation

1.2顏色通道?；?/p>

行人跟蹤的視頻圖像往往分辨率較低，存在一定程度的顏色噪聲干擾。顏色級(jí)數(shù)越多，表示的顏色信息就越多，但是相應(yīng)的顏色干擾信息也越多，且運(yùn)算代價(jià)也越大，通過(guò)顏色特征計(jì)算相似性度量參數(shù)(巴氏系數(shù))的速度也越慢，這對(duì)行人跟蹤需要高實(shí)時(shí)性的要求具有很大挑戰(zhàn)，因此不利于實(shí)時(shí)的行人跟蹤。粒計(jì)算的思想能有效地對(duì)這種不確定的模糊信息進(jìn)行簡(jiǎn)化處理，因此在顏色特征表示上引入粒計(jì)算的思想：行人目標(biāo)區(qū)域經(jīng)過(guò)圖像粒化和轉(zhuǎn)換函數(shù)處理后得到行人目標(biāo)區(qū)域的顏色特征矩陣，對(duì)顏色特征矩陣做顏色通道?；幚淼玫阶罱K?；蟮念伾卣骶仃?。

分別將R、G、B三通道顏色區(qū)間進(jìn)行不同粒度的量化，每通道的顏色區(qū)間都均勻二分，得到一系列均勻的子顏色區(qū)間，稱(chēng)為顏色區(qū)間信息粒格，簡(jiǎn)稱(chēng)顏色粒，該過(guò)程為顏色通道?；Ｓ萌MGC=(IGC,EGC,FGC)來(lái)表示顏色粒，內(nèi)涵IGC是由外延EGC集合中的每個(gè)顏色區(qū)間通過(guò)轉(zhuǎn)換關(guān)系FGC計(jì)算出的R、G、B顏色量值集合。外延EGC的論域?yàn)閄C={[a,b],0≤a,b≤255,a,b∈}，∈XC,i=1,2,…,nRC表示顏色粒度為RC時(shí)第i個(gè)顏色粒區(qū)間，nRC=2RC-1表示顏色粒度為RC時(shí)的顏色?？倲?shù)，則顏色粒度為RC時(shí)的每一個(gè)顏色粒區(qū)間長(zhǎng)度為

(3)

(4)

(5)

至此可直接通過(guò)轉(zhuǎn)換函數(shù)式(5)計(jì)算出顏色特征值在任一粒度下?；蟮念伾卣髦担^大程度降低計(jì)算量。

計(jì)算經(jīng)過(guò)顏色通道?；蟮?個(gè)顏色通道的直方圖雖然已經(jīng)降低了一定的計(jì)算代價(jià)和存儲(chǔ)代價(jià)，但是為了更進(jìn)一步簡(jiǎn)化計(jì)算量和降低存儲(chǔ)代價(jià)，將顏色?；蟮娜ǖ李伾嫡铣梢痪S顏色值作為該顏色粒的顏色特征值，由于顏色的權(quán)重信息已經(jīng)在顏色?；臅r(shí)候通過(guò)顏色粒度表現(xiàn)，因此整體的轉(zhuǎn)換函數(shù)f(v)直接體現(xiàn)為各顏色通道的轉(zhuǎn)換函數(shù)的疊加，且保證f(v)≥1，表達(dá)為

(6)

未經(jīng)顏色特征粒化(a)和經(jīng)過(guò)顏色特征?；蟮念伾狈綀D(b)如圖2所示。

(a)顏色特征直方圖

(b)?；念伾卣髦狈綀D圖2　顏色直方圖Fig.2　Color histogram

比較兩圖，可看到?；蟮念伾狈綀D在顏色級(jí)數(shù)上降低了大約5倍，曲線與橫軸所圍成的面積是采集的目標(biāo)區(qū)域的像素點(diǎn)數(shù)量，可見(jiàn)?；蟮南袼攸c(diǎn)數(shù)量大約降低了4倍，大大降低了計(jì)算量。這一點(diǎn)將在后續(xù)的實(shí)驗(yàn)中得到進(jìn)一步的驗(yàn)證。

2　?；腗ean Shift行人跟蹤算法

粒化的Mean Shift行人跟蹤算法(GMS)是利用圖像?；邦伾ǖ懒；蟮暮撕瘮?shù)空間加權(quán)的顏色直方圖作為目標(biāo)模型，采用巴氏系數(shù)作為相似度度量，通過(guò)自適應(yīng)步長(zhǎng)的MS迭代來(lái)實(shí)時(shí)跟蹤行人目標(biāo)的位置。

2.1算法描述

(7)

(8)

(9)

(10)

同理，設(shè)在跟蹤過(guò)程中行人目標(biāo)候選區(qū)域的顏色直方圖經(jīng)過(guò)圖像?；皖伾ǖ懒；蟊硎緸閜(y0)={pu(y0)}u=1,2,…,mRC，其中y0為目標(biāo)候選區(qū)域的中心位置，同樣有

(11)

基于巴氏系數(shù)，求得目標(biāo)區(qū)域的參考顏色直方圖q和目標(biāo)候選區(qū)域的顏色直方圖p(y0)的相似度為

(12)

至此，?；腗S行人跟蹤算法的MS跟蹤迭代步驟可以總結(jié)為算法1。

算法1粒化的Mean Shift行人跟蹤算法(GMS)

輸入行人跟蹤視頻圖像序列。

跟蹤過(guò)程

3)計(jì)算行人目標(biāo)新位置y1：

4)計(jì)算新位置的顏色直方圖{pu(y1)}u=1,2,…,mRC。

7)若‖y1-y0‖<ε，則本輪迭代結(jié)束；否則y0←y1返回1)繼續(xù)迭代更新行人目標(biāo)位置。

輸出當(dāng)前幀行人目標(biāo)區(qū)域?qū)崟r(shí)最優(yōu)位置。

2.2算法計(jì)算復(fù)雜度

表1　MS和GMS的運(yùn)算代價(jià)

表中Cw、Cp、Cm、Ca、Cr、Cd、Cs分別表示核函數(shù)加權(quán)、獲取像素值、浮點(diǎn)數(shù)乘法、加法、移位運(yùn)算、除法運(yùn)算和開(kāi)方的計(jì)算代價(jià)；R、u分別表示MS算法中的行人目標(biāo)區(qū)域大小及顏色直方圖的級(jí)數(shù)；R′、u′分別表示GMS算法中的行人目標(biāo)區(qū)域大小及顏色直方圖的級(jí)數(shù)；滿(mǎn)足近似關(guān)系R/R′=4，u/u′≈5，Cm和Cr的關(guān)系無(wú)法準(zhǔn)確比較，但是Cm?Cr一定成立。至此可近似估計(jì)出MS和GMS的每次迭代的計(jì)算代價(jià)關(guān)系，為式(13)。理論計(jì)算得出，僅考慮各運(yùn)算代價(jià)時(shí)，GMS算法比MS算法的計(jì)算代價(jià)至少快4倍，是個(gè)可觀的結(jié)果。在實(shí)際實(shí)驗(yàn)中，由于圖像分塊函數(shù)消耗、硬件等原因會(huì)使得真正計(jì)算效率低于4倍。

(13)

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

在CPU2.6 GHz、內(nèi)存4 GB的PC機(jī)、MATLAB (R2013b)的環(huán)境下進(jìn)行實(shí)驗(yàn)，實(shí)現(xiàn)本文的改進(jìn)算法GMS跟蹤算法，并實(shí)現(xiàn)傳統(tǒng)MS跟蹤算法、Kalman濾波跟蹤算法和粒子濾波跟蹤算法與之比較。

采用4組視頻圖像序列進(jìn)行實(shí)驗(yàn)，圖像序列選自PETS2009和CAVIAR視頻圖像庫(kù)，涵蓋了行人跟蹤的主要場(chǎng)景及挑戰(zhàn)場(chǎng)景，包括簡(jiǎn)單背景、復(fù)雜背景、目標(biāo)遮擋、形變及光照變化等。為檢測(cè)本文方法的性能，將與傳統(tǒng)MS跟蹤算法、Kalman濾波跟蹤算法和粒子濾波跟蹤算法進(jìn)行比較分析。

3.1與傳統(tǒng)MS跟蹤的比較

圖3選取的視頻圖像是S2_L1項(xiàng)目中View_005中的部分序列，序列中紅衣女子從視頻窗口右端水平穿過(guò)走向視頻窗口左端，期間活動(dòng)窗口只有紅衣女子一人，跟蹤圖像背景較簡(jiǎn)單。其中圖3(a)是MS的跟蹤結(jié)果，圖3(b)是GMS的跟蹤結(jié)果。從跟蹤結(jié)果可發(fā)現(xiàn)該序列MS和GMS的跟蹤效果都較好，在整個(gè)行人跟蹤過(guò)程中都有正確跟蹤到目標(biāo)行人，但是觀察表2發(fā)現(xiàn)該序列MS算法的平均迭代次數(shù)接近5，而GMS算法的平均迭代次數(shù)3.5左右，跟蹤實(shí)時(shí)性提高了30%。可見(jiàn)在跟蹤背景比較簡(jiǎn)單，行人目標(biāo)顏色特征較為明顯時(shí)，雖然MS算法和GMS算法的跟蹤準(zhǔn)確率相差無(wú)幾，但是GMS算法由于引入了粒計(jì)算，降低了計(jì)算復(fù)雜度，因此一定程度上提高了跟蹤實(shí)時(shí)性。

(a)MS跟蹤結(jié)果

(b)GMS跟蹤結(jié)果圖3　Image I 跟蹤結(jié)果比較Fig.3　Comparison of tracking results of image I

圖4選取的視頻圖像是S2_L1項(xiàng)目中View_005中的部分序列，序列中藍(lán)衣女子從視頻窗口右端水平穿過(guò)走向視頻窗口左端，走到視頻窗口中央時(shí)與兩名黑衣男子發(fā)生遮擋隨后分離。由于有行人遮擋及背景顏色干擾，跟蹤圖像背景略復(fù)雜。其中圖4(a)是MS的跟蹤結(jié)果，圖4(b)是GMS的跟蹤結(jié)果。比較圖4的跟蹤結(jié)果，發(fā)現(xiàn)目標(biāo)行人未發(fā)生碰撞前，MS和GMS都有正確跟蹤到行人，在第144幀目標(biāo)行人與兩個(gè)行人發(fā)生碰撞后(即遮擋后分離)，在第147幀及第148幀MS目標(biāo)跟蹤丟失，發(fā)現(xiàn)跟蹤到干擾行人的藍(lán)色牛仔褲上，與目標(biāo)行人的顏色特征相似度較高，導(dǎo)致誤判，直至最后目標(biāo)徹底丟失。而在整個(gè)行人跟蹤過(guò)程中，GMS跟蹤目標(biāo)未丟失，跟蹤正確率較高，僅在第144幀行人發(fā)生遮擋時(shí)跟蹤略有偏差，遮擋分離后，跟蹤回復(fù)正常?？梢?jiàn)當(dāng)跟蹤場(chǎng)景中存在與行人目標(biāo)的顏色特征相似的候選目標(biāo)與行人目標(biāo)碰撞時(shí)，MS算法跟蹤失效，GMS算法的粒化后顏色直方圖一定程度上降低了背景顏色特征的干擾，使得跟蹤正確保持。該序列MS的平均迭代次數(shù)接近6，GMS的平均迭代次數(shù)約為4.5，跟蹤實(shí)時(shí)性提高了25%，但是相比序列一的GMS平均迭代次數(shù)，每幀圖片平均增加了一次迭代，這是因?yàn)镮mage II跟蹤場(chǎng)景相比Image I更為復(fù)雜。

(a)MS跟蹤結(jié)果

(b)GMS跟蹤結(jié)果圖4　Image II 跟蹤結(jié)果比較Fig.4　Comparison of tracking results of image II

圖5選取的視頻圖像是S2_L1項(xiàng)目中View_001中的部分序列，序列中紅衣女子從視頻窗口右下端斜向上走向視頻窗口左上端，走到視頻窗口中央時(shí)與兩名黑衣男子發(fā)生遮擋隨后分離，緊接著又被電線桿遮擋后又分離。跟蹤圖像背景略復(fù)雜，發(fā)生多次遮擋，包括兩行人的動(dòng)態(tài)遮擋和電線桿的靜態(tài)遮擋，而且背景局部區(qū)域存在光照變化干擾。其中圖5(a)是MS的跟蹤結(jié)果，圖5(b)是GCMS的跟蹤結(jié)果。MS跟蹤在第467幀時(shí)，行人跟蹤丟失，跟蹤結(jié)束；GMS在第467幀時(shí)，行人跟蹤略有偏差，但是仍繼續(xù)正確跟蹤。整個(gè)跟蹤過(guò)程中，行人目標(biāo)的顏色特征與背景顏色特征和遮擋物體的顏色特征能很好地區(qū)分，GMS在目標(biāo)行人發(fā)生遮擋時(shí)，能適當(dāng)減弱背景及遮擋物體的顏色干擾，跟蹤效果很好，而MS算法更多地受背景及遮擋物體的顏色干擾導(dǎo)致多次遮擋之后行人徹底丟失。該序列MS的平均迭代次數(shù)約為5.5，GMS的平均迭代次數(shù)約為4.5，跟蹤實(shí)時(shí)性?xún)H提高了18%，可見(jiàn)GMS算法在跟蹤場(chǎng)景復(fù)雜的情況下，跟蹤效果還有待提升。

(a)MS跟蹤結(jié)果

(b)GMS跟蹤結(jié)果圖5　Image III 跟蹤結(jié)果比較Fig.5　Comparison of tracking results of image III

表2　MS和GMS的平均迭代次數(shù)(次/幀)

(a)MS跟蹤結(jié)果

(b)GMS跟蹤結(jié)果圖6　Image IV跟蹤結(jié)果比較Fig.6　Comparison of tracking results of image IV

圖6選取的視頻圖像是CAVIAR數(shù)據(jù)庫(kù)FRONT VIEW中的部分序列，序列中目標(biāo)行人從視頻窗口右端水平穿過(guò)走向視頻窗口左端，走過(guò)視頻窗口中央時(shí)與多名行人發(fā)生遮擋隨后分離。整個(gè)視頻圖像質(zhì)量較差，行人特征極其不明顯，光照變化很大，加之有行人遮擋及背景顏色干擾，跟蹤圖像背景更為復(fù)雜。其中圖6(a)是MS的跟蹤結(jié)果，圖6(b)是GMS的跟蹤結(jié)果。觀察(a)、(b)的跟蹤結(jié)果，在第493幀發(fā)現(xiàn)MS目標(biāo)跟蹤片刻丟失，GMS目標(biāo)跟蹤僅僅略有偏差，這是因?yàn)镸S需要獲取更多的顏色信息，相對(duì)應(yīng)的對(duì)光照變化會(huì)更加敏感；第549、564、573幀捕捉了目標(biāo)行人碰撞過(guò)程，由于行人特征實(shí)在不明顯使得MS跟蹤失效，而GMS能適當(dāng)?shù)厝萑填伾卣鞲蓴_，使得碰撞過(guò)程行人跟蹤正常。可見(jiàn)當(dāng)跟蹤視頻質(zhì)量較差時(shí)GMS比MS更具有優(yōu)勢(shì)。

3.2與其他類(lèi)跟蹤方法的比較

觀察Image I紅衣女子的跟蹤結(jié)果(圖7)，發(fā)現(xiàn)針對(duì)簡(jiǎn)單背景的行人跟蹤，Kalman濾波和粒子濾波總體上都能較好地跟蹤到目標(biāo)行人，不會(huì)丟失。該序列光照基本無(wú)變化，目標(biāo)行人運(yùn)動(dòng)基本勻速，兩個(gè)算法在第477幀跟蹤位置都有偏差，但是隨后跟蹤正常，這是因?yàn)镵alman濾波預(yù)測(cè)初始參數(shù)的原因，隨著跟蹤狀態(tài)的變化，參數(shù)會(huì)隨時(shí)調(diào)整，這是不可避免的；粒子濾波的粒子采樣初始是無(wú)經(jīng)驗(yàn)無(wú)知識(shí)的，粒子覆蓋整個(gè)跟蹤圖像，伴隨著不斷的重采樣，粒子會(huì)漸漸地集中在行人目標(biāo)上，跟蹤位置也不斷精確。

(a)Kalman 濾波跟蹤結(jié)果

(b)Particle 濾波跟蹤結(jié)果圖7　Image I 跟蹤結(jié)果比較Fig.7　Comparison of tracking results of image I

觀察Image III紅衣女子的跟蹤結(jié)果(圖8)，發(fā)現(xiàn)復(fù)雜背景下且存在行人互遮擋、光照變化等挑戰(zhàn)因素時(shí)，Kalman濾波和粒子濾波跟蹤都失效，行人目標(biāo)極易丟失，這是因?yàn)閭鹘y(tǒng)Kalman濾波和粒子濾波跟蹤都是利用狀態(tài)估計(jì)來(lái)預(yù)測(cè)行人目標(biāo)的位置，而光照變化等因素極易干擾粒子采樣，可見(jiàn)MS跟蹤采取顏色直方圖作為跟蹤特征具有一定的優(yōu)勢(shì)。

(a)Kalman 濾波跟蹤結(jié)果

(b)Particle 濾波跟蹤結(jié)果圖8　Image III跟蹤結(jié)果比較Fig.8　Comparison of tracking results of image III

3.3跟蹤效率分析

表3展示了不同方法在不同圖像序列中的平均跟蹤效率(s/幀)，發(fā)現(xiàn)GMS的跟蹤效率均比MS的跟蹤效率高，說(shuō)明GMS跟蹤算法在實(shí)際跟蹤場(chǎng)景下確實(shí)降低了運(yùn)算代價(jià)，提高了跟蹤實(shí)時(shí)性。同時(shí)發(fā)現(xiàn)相比簡(jiǎn)單場(chǎng)景下，Kalman濾波和粒子濾波的跟蹤效率更勝GMS。觀察序列三各方法的跟蹤效率發(fā)現(xiàn)Kalman濾波和粒子濾波結(jié)果很小，這是因?yàn)镵alman濾波和粒子濾波跟蹤目標(biāo)已經(jīng)徹底丟失，所以該序列數(shù)據(jù)失去參考價(jià)值。

表3　不同跟蹤方法的平均跟蹤效率比較

4　結(jié)論

在跟蹤場(chǎng)景中若存在與行人目標(biāo)顏色特征相似的干擾物體時(shí)，特別是碰撞時(shí)或被遮擋時(shí)，傳統(tǒng)的MS行人跟蹤算法會(huì)使得跟蹤目標(biāo)丟失。因此，本文提出了?；腗S行人跟蹤算法，總結(jié)如下：

1)采用粒計(jì)算的思想對(duì)行人目標(biāo)區(qū)域進(jìn)行?；謮K，并且對(duì)分塊后的塊顏色特征進(jìn)行顏色通道?；?，歸一化后得到?；蟮念伾狈綀D作為跟蹤過(guò)程的行人目標(biāo)顏色特征表示；

2)通過(guò)巴氏系數(shù)衡量行人目標(biāo)區(qū)域和候選區(qū)域的相似度，最后通過(guò)MS迭代框架來(lái)實(shí)時(shí)跟蹤目標(biāo)行人的位置；

3)算法保持了傳統(tǒng)MS跟蹤算法的基本框架，因此也延續(xù)了傳統(tǒng)MS跟蹤算法的優(yōu)勢(shì)，且使得算法的計(jì)算復(fù)雜度更低，跟蹤更快；

4)通過(guò)實(shí)驗(yàn)分析得出，本算法減弱了跟蹤場(chǎng)景的背景顏色干擾，同時(shí)提高了跟蹤實(shí)時(shí)性。

[1]顧幸方, 茅耀斌, 李秋潔. 基于Mean Shift的視覺(jué)目標(biāo)跟蹤算法綜述[J]. 計(jì)算機(jī)科學(xué), 2012, 39(12): 16-24.

GU Xingfang, MAO Yaobin, LI Qiujie. Survey on visual tracking algorithms based on mean shift[J]. Computer science, 2012, 39(12): 16-24.

[2]COMANICIU D, RAMESH V, MEER P. Kernel-based object tracking[J]. IEEE transactions on pattern analysis and machine intelligence, 2003, 25(5): 564-577.

[3]KHAN Z H, GU Yuhua, BACKHOUSE A G. Robust visual object tracking using multi-mode anisotropic mean shift and particle filters[J]. IEEE transactions on circuits and systems for video technology, 2011, 21(1): 74-87.

[4]PENG Ningsong, YANG Jie, LIU Zhi. Mean shift blob tracking with kernel histogram filtering and hypothesis testing[J]. Pattern recognition letters, 2005, 26(5): 605-614.

[5]CHEN Aihua, ZHU Ming, WANG Yanhua, et al. Mean shift tracking combining SIFT[C]//Proceedings of the 9th International Conference on Signal Processing. Beijing: IEEE, 2008: 1532-1535.

[6]NING Jifeng, ZHANG Lei, ZHANG D, et al. Scale and orientation adaptive mean shift tracking[J]. IET computer vision, 2012, 6(1): 52-61.

[7]CHEN Kangli, GE Wancheng. Pedestrian tracking algorithm based on kalman filter and partial mean-shift tracking[C]//Proceedings of the 2nd International Conference on Systems and Informatics. Shanghai: IEEE, 2014: 230-235.

[8]FANG Jiangxiong, YANG Jie, LIU Huaxiang. Efficient and robust fragments-based multiple kernels tracking[J]. AEU-international journal of electronics and communications, 2011, 65(11): 915-923.

[9]SHEN Chunhua, BROOKS M J, VAN DEN HENGEL A. Fast global kernel density mode seeking: applications to localization and tracking[J]. IEEE transactions on image processing, 2007, 16(5): 1457-1469.

[10]CHANG S. Stochastic peak tracking and the Kalman filter[J]. IEEE transactions on automatic control, 1968, 13(6): 750.

[11]DOUCET A, GORDON N. Efficient particle filters for tracking manoeuvring targets in clutter[C]//Proceedings of IEE Colloquium on Target Tracking: Algorithms and Applications. London: IEEE, 1999: 4/1-4/5.

[12]ZADEH L A. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J]. Fuzzy sets and systems, 1997, 90(2): 111-127.

[13]LIN T Y. Granular computing: fuzzy logic and rough sets[C]//ZADEH L A, KACPRZYK J. Computing with Words in Information/Intelligent Systems 1. Berlin Heidelberg: Physica-Verlag HD, 1999: 183-200.

[14]苗奪謙, 王國(guó)胤, 劉清, 等. 粒計(jì)算: 過(guò)去、現(xiàn)在與展望[M]. 北京: 科學(xué)出版社, 2007.

MIAO Duoqian, WANG Guoyin, LIU Qing, et al. Granular computing: past, present and future[M]. Beijing: Science Press, 2007.

[15]徐計(jì), 王國(guó)胤, 于洪. 基于粒計(jì)算的大數(shù)據(jù)處理[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(8): 1497-1517.

XU Ji, WANG Guoyin, YU Hong. Review of big data processing based on granular computing[J]. Chinese journal of computers, 2015, 38(8): 1497-1517.

劉翠君,女，1993年生，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)視覺(jué)、粒計(jì)算等。

趙才榮，男，1981年生，副研究員，博士，主要研究方向?yàn)槿四樧R(shí)別、計(jì)算機(jī)視覺(jué)等。

苗奪謙，男，1964年生，教授、博士生導(dǎo)師，博士，主要研究方向?yàn)榱Ｓ?jì)算、粗糙集、中文信息處理等。

Granular mean shift pedestrian tracking algorithm

LIU Cuijun， ZHAO Cairong， MIAO Duoqian， WANG Xuekuan

(College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

Mean shift pedestrian tracking that uses a color histogram as its tracking feature has drawbacks, e.g., performance can easily be affected by the introduction of a background color. To solve this problem, the idea of granular computing was introduced into the traditional mean shift pedestrian tracking algorithm, and a new granular mean shift pedestrian tracking algorithm, based on granular computing, is presented. The algorithm blocks the image’s target area with specific granularity to extract color features, then adopts different color channels of granulation on the feature, and finally realizes target tracking under the framework of the mean shift iteration. Compared with other traditional methods the algorithm displays lower computational complexity and is more robust. Experimental results on PETS2009 and CAVIAR databases show that the algorithm achieves a higher tracking accuracy, better robustness and efficiency under color interference, and can track the target pedestrian in real time.

information granules; granular computing; mean shift; feature extraction; pedestrian tracking

10.11992/tis.201605033

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0831.022.html

2016-05-30. 網(wǎng)絡(luò)出版日期：2016-08-08.

國(guó)家自然科學(xué)基金項(xiàng)目(61273304)；上海市中醫(yī)藥三年行動(dòng)計(jì)劃重點(diǎn)項(xiàng)目(ZY3-CCCX-3-6002)

苗奪謙. E-mail：dqmiao@#edu.cn.

TP391

A

1673-4785(2016)04-0433-09