一種尺度和方向適應(yīng)性的Mean Shift跟蹤算法

侯建華1，黃奇1，項俊2,鄭桂林1

(1 中南民族大學(xué) 智能無線通信湖北省重點實驗室，武漢430074；2 華中科技大學(xué) 自動化學(xué)院，武漢 430074)

摘要針對原始的Mean Shift跟蹤算法雖能準(zhǔn)確地估計目標(biāo)位置，但對目標(biāo)尺度和方向不能實現(xiàn)自適應(yīng)估計，結(jié)合目標(biāo)模型與候選目標(biāo)區(qū)域的候選模型得到了反向投影圖，此反向投影圖可表示圖像中像素點屬于目標(biāo)的概率，將反向投影圖的矩特征應(yīng)用到原始Mean Shift跟蹤算法框架，實現(xiàn)了目標(biāo)尺度和方向適應(yīng)性Mean Shift跟蹤.實驗結(jié)果表明：該算法能有效跟蹤尺度和方向變化的目標(biāo).

關(guān)鍵詞mean shift跟蹤算法；矩特征；反向投影圖；目標(biāo)跟蹤

收稿日期2014-12-19

作者簡介侯建華(1964-)，男，教授，博士，研究方向：圖像處理、模式識別，E-mail：zil@scuec.edu.cn

基金項目湖北省自然科學(xué)基金資助項目(2012FFA113)；武漢市科技供需對接計劃項目(201051824575)；中南民族大學(xué)中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目(CZW14057)

中圖分類號TP391文獻標(biāo)識碼A

Scale and Orientation Adaptive Mean Shift Tracking

HouJianhua1,HuangQi1,XiangJun2，ZhengGuilin1

(1 College of Electronic Information Engineering, South-Central University for Nationalities, Wuhan 430074, China;

2 College of Automation, Huazhong University of Science and Technology, Wuhan 430074, China)

AbstractAlthough the position of target can be well obtained by the original mean shift tracking algorithm, the target’s scale and orientation can not be estimated adaptively. This paper proposed an improved mean shift algorithm to address the issue of how to estimate target’s variation of scale and orientation. Firstly, by combining the target mode and the candidate model, we obtain the weight image which represents the possibility that a pixel belongs to the target. Then the moment features of the weight image are applied in the mean shift tracking framework, so that the scale and orientation changes of the target can be adaptively estimated. The experimental results demonstrate the effectiveness of the proposed algorithm when tracking the target with changes in scale and orientation.

Keywordsmean shift tracking algorithm；moment feature；weight image；object tracking

實時目標(biāo)跟蹤技術(shù)是計算機視覺領(lǐng)域的一個熱點問題，它是根據(jù)先驗條件在實時視頻幀中尋找目標(biāo)的位置及形狀信息.經(jīng)過多年的努力，視覺跟蹤研究已經(jīng)取得了長足的進展，涌現(xiàn)出了很多優(yōu)秀的算法[1].其中基于Mean Shift理論[2]框架的跟蹤算法由于具有簡單、高效、無參的特點，自提出以來就受到了廣泛的關(guān)注.經(jīng)典的Mean Shift跟蹤算法[3]利用核函數(shù)加權(quán)的顏色直方圖作為目標(biāo)模型，用巴氏系數(shù)度量模型間相似性，通過Mean Shift迭代尋找目標(biāo)位置.雖然Comaniciu利用試探法對尺度進行了估計[3],即利用原尺度和變化后的尺度分別進行三次跟蹤，選擇與目標(biāo)參考模型相似度最大的尺度作為估計結(jié)果，但基于巴氏系數(shù)的相似性度量易在較小的尺度中得到局部最優(yōu)，可能導(dǎo)致實際目標(biāo)尺度增大時，估計尺度卻再逐漸減小.在此基礎(chǔ)上，又提出了許多改進的算法[4-7].文獻[4]在目標(biāo)跟蹤時，結(jié)合Lindeberg等人的尺度空間理論[8]進行實時核函數(shù)尺度選擇，但是沒有對目標(biāo)方向變化進行估計；Zivkovic等人提出了EM-shift算法[5]，在定位目標(biāo)位置的同時對目標(biāo)的大概形狀進行描述；Hu等人[6]應(yīng)用顏色空間特征和相似性測度函數(shù)去估計目標(biāo)的尺度和方向.文獻[7]利用非對稱核進行Mean Shift迭代，在目標(biāo)定位、尺度和形狀自適應(yīng)估計方面取得了較好的效果.文獻[9]提出了連續(xù)自適應(yīng)Mean Shift算法(Camshift)，該方法應(yīng)用目標(biāo)模型計算當(dāng)前視頻幀的反向投影圖，并利用反向投影圖的矩特征對當(dāng)前幀目標(biāo)位置、尺度、方向進行估計, Camshift算法對于序列圖像尋優(yōu)速度快、有較強的實時性與魯棒性.

已有研究指出，與Camshift中的反向投影圖相比較，經(jīng)典Mean Shift跟蹤算法中定義的反向投影圖能夠更準(zhǔn)確的反映目標(biāo)尺度信息[10].本文對文獻[10]的研究進行了理論分析，結(jié)合目標(biāo)模型與候選目標(biāo)區(qū)域的候選模型得到反向投影圖，以此估計目標(biāo)的尺度和方向，實現(xiàn)了一種具有尺度、方向自適應(yīng)的跟蹤算法，并與相關(guān)跟蹤算法進行了實驗對比.

1Mean Shift跟蹤算法

1.1目標(biāo)描述

視頻目標(biāo)跟蹤的結(jié)果通常被定義為一個矩形或者橢圓區(qū)域.目標(biāo)的顏色直方圖對目標(biāo)的尺度和旋轉(zhuǎn)是相互獨立的，并且對局部遮擋具有一定的魯棒性[3]，因此顏色直方圖被廣泛應(yīng)用于目標(biāo)的表示.

1.1.1目標(biāo)模型

(1)

(2)

1.1.2候選目標(biāo)模型

設(shè)y為候選目標(biāo)區(qū)域中心，候選目標(biāo)模型可以描述為：

(3)

(4)

(5)

(6)

1.2MeanShift迭代

(7)

其中：

(8)

由于(7)式第一項與y無關(guān)，最大化(7)式就相當(dāng)于最大化(7)式的第二項.經(jīng)過迭代，目標(biāo)區(qū)域的中心位置由y0移動到新的位置y1，迭代函數(shù)為：

(9)

其中g(shù)(x)=-k′(x).當(dāng)核函數(shù)輪廓函數(shù)k(x)為Epanechnikov，有g(shù)(x)=-k(x)=1，所以(9)式可寫為：

(10)

2尺度、方向適應(yīng)性Mean Shift

在視頻序列中，目標(biāo)的縮放是一個緩慢的過程.因此，我們可以假設(shè)目標(biāo)的尺度變化是平滑的，這個假設(shè)在大部分視頻序列是成立的.于是我們可以在原始的Mean Shift跟蹤算法[3]的基礎(chǔ)上提出改進方案.假設(shè)已經(jīng)估計出前一幀目標(biāo)區(qū)域的面積，我們可將當(dāng)前幀候選目標(biāo)區(qū)域面積(尺度)定義為比前一幀目標(biāo)稍大.因此，不管目標(biāo)的尺度和方向怎樣變化(只要幀間變化是緩慢的)，它都不會超出當(dāng)前幀定義的候選目標(biāo)區(qū)域.此時，估計目標(biāo)尺度和方向的問題就轉(zhuǎn)化為對候選目標(biāo)區(qū)域面積、以及候選目標(biāo)方向的確定.

2.1尺度變化時目標(biāo)的反向投影圖

參考文獻本文尺度、方向適應(yīng)性Mean Shift(簡稱SOAMST)方案[9]，通過計算反向投影圖的矩特征[11]來估計目標(biāo)的尺度和方向.然而這些矩特征僅僅依賴反向投影圖，這就要求有一種合理的反向投影圖計算方法，進而得到準(zhǔn)確的矩特征去有效的估計目標(biāo)變化.在Camshift[9]和Mean Shift跟蹤[3]算法中，都利用了反向投影圖[4]來完成目標(biāo)跟蹤.其中，Camshift的反向投影圖是由目標(biāo)區(qū)域的色度(Hue)直方圖反向投影得到；而Mean Shift跟蹤算法的反向投影圖是由(8)式定義得到.在此，我們將通過分析Camshift和Mean Shift跟蹤算法的反向投影圖在不同尺度下的情況，以從中選優(yōu)提升SOAMST算法.

如前所述，我們定義一個比目標(biāo)本身尺寸更大的候選目標(biāo)區(qū)域，以確保在跟蹤過程中目標(biāo)總出現(xiàn)在候選目標(biāo)區(qū)域內(nèi).在該策略下，可以比較目標(biāo)在不同尺度下分別用Camshift和Mean Shift跟蹤方法所得反向投影圖.參考文獻[3,9]可得圖1.其中，圖(m)是一個由三個灰度級組成的合成目標(biāo)；圖(n)為比目標(biāo)更大的候選區(qū)域；圖(a)、(b)、(c)分別為合成目標(biāo)尺度縮小、不變、增大的跟蹤結(jié)果；圖(d)、(e)、(f)分別為對圖(a)、(b)、(c)應(yīng)用Camshift算法計算所得反向投影圖；而圖(g)、(h)、(i)分別為對圖(a)、(b)、(c)應(yīng)用Mean Shift跟蹤算法計算所得反向投影圖.

從圖1中，可以看到Camshift和Mean Shift跟蹤對同一目標(biāo)計算所得反向投影圖的不同.首先，Camshift算法所得反向投影圖像素值為常量，并且該常量僅僅與目標(biāo)模型有關(guān)；而Mean Shift跟蹤算法所得反向投影圖像素值會隨目標(biāo)尺度變化而變化.當(dāng)目標(biāo)的尺度與候選目標(biāo)區(qū)域大小越接近，Mean Shift跟蹤算法所得反向投影圖像素值就越接近常量1.也就是說，Mean Shift跟蹤算法所得反向投影圖能更好的反映目標(biāo)尺度的變化.根據(jù)以上的觀測和分析，我們將采用Mean Shift跟蹤算法所用反向投影圖計算方法.

圖1　目標(biāo)在不同尺度下用Camshift和Mean Shift 跟蹤算法所得反向投影圖 　Fig.1　Weight images in Camshift and Mean Shift tracking algorithms when the object scale changes

2.2目標(biāo)面積的估計

由于候選目標(biāo)區(qū)域的反向投影圖像素值表示像素點屬于目標(biāo)的可能性，所以候選目標(biāo)區(qū)域的權(quán)重面積可以表示成反向投影圖的零階矩：

(11)

在MeanShift跟蹤中，目標(biāo)通常會在一個比自己更大的候選目標(biāo)區(qū)域內(nèi).由于候選目標(biāo)區(qū)域存在背景特征，所以候選目標(biāo)區(qū)域內(nèi)目標(biāo)特征的概率就會比目標(biāo)模型對應(yīng)概率要小.(8)式就會增大目標(biāo)像素的權(quán)重，同時會減小背景像素的權(quán)重.也即在估計目標(biāo)面積上，候選目標(biāo)區(qū)域的目標(biāo)像素比背景像素起更大的作用.這在圖1中圖(g)、(h)、(i)是清晰可見的.

根據(jù)以上分析，可以用巴氏系數(shù)來修正M00，以合理估計目標(biāo)面積A.定義目標(biāo)面積估計函數(shù)：

A=c(ρ)·M00，

(12)

其中c(ρ)是一個關(guān)于巴氏系數(shù)ρ(0≤ρ≤1)單調(diào)遞增函數(shù).結(jié)合圖1中圖(g)、(h)、(i)，通常都大于目標(biāo)面積，并且它隨著ρ增大而單調(diào)地接近目標(biāo)真實面積.因此，我們需要c(ρ)是單調(diào)遞增函數(shù)，并且ρ取1時c(ρ)取得最大值1.通過實驗，結(jié)合指數(shù)函數(shù)與高斯函數(shù)得到的c(ρ)能取得令人滿意的結(jié)果[10]，c(ρ)定義為：

(13)

結(jié)合式(12)、(13)，當(dāng)ρ接近上限1時(目標(biāo)候選模型接近目標(biāo)模型)，c(ρ)也接近1，也即M00作為目標(biāo)面積估計更加可靠.當(dāng)ρ減小時(目標(biāo)候選模型與目標(biāo)模型的差異增大)，M00會大于目標(biāo)面積，但c(ρ)會小于1，以使得A能合理的表示目標(biāo)的真實面積.當(dāng)ρ接近0時，說明目標(biāo)已經(jīng)跟丟，A也將接近零值.

2.3矩特征的應(yīng)用

參考文獻[9]，計算反向投影圖的一階矩M10、M01，二階矩M20、M02、M11：

(14)

(15)

其中，(xi,1，xi,2)為候選目標(biāo)區(qū)域內(nèi)像素點的坐標(biāo).

比較式(10)、(11)、(14)，可以發(fā)現(xiàn)當(dāng)前幀目標(biāo)的所在位置y1為一階矩與零級矩的比：

(16)

參考文獻其中代表目標(biāo)候選區(qū)域的中心坐標(biāo).[11]，結(jié)合式(10)、(11)、(15)和(16)可以定義中間變量μ20、μ11、μ02，并寫成協(xié)方差矩陣形式：

(17)

其中：

(18)

2.4估計目標(biāo)的寬、高及方向

結(jié)合目標(biāo)的面積估計值及目標(biāo)的協(xié)方差矩陣(17)式，可以得到目標(biāo)的寬、高及方向估計.對(17)式協(xié)方差矩陣進行奇異值分解(SVD)：

Cov=U×S×UT=

(19)

其中：

由于利用了反向投影圖來近似目標(biāo)在候選區(qū)域的可靠密度分布函數(shù)，所以利用U對目標(biāo)的方向進行估計就會更加可靠.下面將對目標(biāo)寬和高進行精確的估計.

假設(shè)跟蹤目標(biāo)被表示為一個橢圓，橢圓的長半軸、短半軸分別用a、b表示.文獻[11]證明，λ1與λ2的比約等于a與b的比，即λ1/λ2≈a/b.因此，可以設(shè)a=k·λ1、b=k·λ2，其中k為尺度因子.由于我們已經(jīng)估計得到目標(biāo)面積A，又這里A=π·a·b=π·(kλ1)·(kλ2)，所以有：

(20)

(21)

現(xiàn)在協(xié)方差矩陣可以表示為：

(22)

協(xié)方差矩陣Cov重寫為(22)式形式是本文算法的關(guān)鍵步驟.值得提及的是Zivkovic等人提出的EM-shift算法[5]，它是根據(jù)MeanShift跟蹤算法對視頻幀進行協(xié)方差矩陣的迭代估計.而本文算法是結(jié)合目標(biāo)面積A和協(xié)方差矩陣，對目標(biāo)的寬、高和方向進行估計.

2.5下一幀候選區(qū)域的確定

完成了對當(dāng)前幀目標(biāo)位置、尺度和方向的估計，接下來就需要確定下一幀目標(biāo)的候選區(qū)域.根據(jù)(22)式，我們定義如下協(xié)方差矩陣表示下一幀候選目標(biāo)區(qū)域的尺度：

(23)

其中，Δd是下一幀目標(biāo)候選區(qū)域尺度在前一幀基礎(chǔ)上的增長量.目標(biāo)候選區(qū)域的位置被初始化為(橢圓區(qū)域):

(24)

2.6SOAMST算法實現(xiàn)

根據(jù)前面的分析，SOAMST算法的實現(xiàn)步驟如下：

(2)初始化迭代次數(shù)變量：k=0.

(4)應(yīng)用(8)式計算得到權(quán)重向量{wi}i=1…n.

(5)應(yīng)用(10)式計算目標(biāo)候選模型的新位置y1.

(6)定義d=‖y1-y0‖,y0=y1.并設(shè)置誤差閾值ε，迭代次數(shù)上限N.

if(d<εork≥N：跳到第(7)步執(zhí)行；

else：k=k+1，跳到第(3)步執(zhí)行.

(7)應(yīng)用(22)式估計目標(biāo)候選模型的寬、高、方向.

(8)應(yīng)用(24)式估計下一幀目標(biāo)候選模型.

3實驗結(jié)果

將SOAMST算法與原始Mean Shift跟蹤算法[3]、EM-shift算法[5]進行實驗結(jié)果對比，對SOAMST算法進行客觀評價.Mean Shift跟蹤算法與EM-shift算法是在Mean Shift框架下、在處理目標(biāo)尺度和方向變化領(lǐng)域兩個具有代表性的方案.由于Camshift框架得到的反向投影圖不夠可靠，它在估計目標(biāo)尺度和方向上容易出現(xiàn)錯誤，所以沒有將Camshift加入到實驗對比.

本文采用RGB顏色空間作為特征空間，并且將

顏色空間量化為16×16×16級.我們選擇一個對稱視頻序列和一個場景視頻序列作為實驗對象.

3.1對稱視頻序列上的實驗

我們首先選用一個對稱橢圓視頻序列來測試SOAMST算法的準(zhǔn)確率.如圖2，第1行是Mean Shift跟蹤算法實驗結(jié)果；第2行是EM-shift算法實驗結(jié)果；第3行是SOAMST算法實驗結(jié)果.實驗結(jié)果中，黑色橢圓框表示跟蹤得到的目標(biāo)區(qū)域，灰色橢圓框表示SOAMST算法所述的候選目標(biāo)區(qū)域(本實驗參數(shù)Δd=10).實驗結(jié)果表明，SOAMST算法能可靠的跟蹤尺度及方向同時變化的橢圓.同時，Mean Shift跟蹤算法不能估計目標(biāo)的方向，并且其跟蹤結(jié)果不佳；EM-shift算法未能較準(zhǔn)確的估計對稱橢圓的尺度及方向.

Frame 1 　 Frame 7　　Frame 25　Frame 38　Frame 49 圖2　三種跟蹤算法在對稱橢圓序列上的跟蹤結(jié)果 Fig.2　Tracking results of the synthetic ellipse sequence by three tracking algorithms

表1列出了SOAMST算法對對稱視頻序列中橢圓寬、高和方向的估計.其中方向為橢圓的主軸與x軸的角度.序列的第一幀用于定義目標(biāo)模型，剩下的視頻幀用于算法測試.可見，SOAMST方法在估計目標(biāo)尺度和方向上獲得了準(zhǔn)確的效果.

表1　SOAMST算法對對稱視頻序列中橢圓寬、高和方向的估計結(jié)果及準(zhǔn)確率

3.2場景視頻序列上的實驗

場景視頻序列的目標(biāo)是一個羽毛球拍手膠，該目標(biāo)的尺度、方向變化明顯.見圖3，第1行是Mean Shift跟蹤算法的實驗結(jié)果；第2行是EM-shift算法的實驗結(jié)果；第3行是SOAMST算法的實驗結(jié)果.可見，Mean Shift跟蹤算法沒有獲得好的跟蹤效果；另一方面，雖然EM-shift算法較Mean Shift跟蹤算法獲得了更好的跟蹤效果，但它在目標(biāo)方向快速變化時仍不能及時準(zhǔn)確的跟蹤；而SOAMST算法所得跟蹤結(jié)果是較準(zhǔn)確的.

圖3　3種跟蹤算法在場景序列上的跟蹤結(jié)果 Fig.3　Tracking results of the real-time video sequence by three tracking algorithms

表2列出3種方案分別在兩個視頻序列上跟蹤時的平均迭代次數(shù).由于Mean Shift跟蹤算法會進行3次Mean Shift迭代，所以它的迭代次數(shù)最多.影響EM-shift和SOAMST算法收斂速度的主要因素是協(xié)方差矩陣的計算.由于EM-shift每次迭代會進行一次目標(biāo)位置和方向的估計，而SOAMST每幀只進行一次目標(biāo)位置和方向的估計，所以SOAMST比EM-shift更快.

表2方案在視頻序列上跟蹤時的平均迭代次數(shù)

Tab.2Average number of iterations by different methods

on the two sequences

算法MeanShiftEM-shiftSOAMST對稱橢圓序列29.312.43場景序列28.813.65.08

4結(jié)語

在Mean Shift跟蹤算法框架下，結(jié)合候選目標(biāo)區(qū)域反向投影圖的矩特征，實現(xiàn)了一種對目標(biāo)尺度和方向適應(yīng)性估計的SOAMST跟蹤算法.實驗結(jié)果也表明，SOAMST算法繼承了原始Mean Shift跟蹤算法簡單、高效等優(yōu)良特性.在以后的研究工作中，我們可以通過檢測目標(biāo)的真實形狀來更加準(zhǔn)確的表達目標(biāo)，而不是單純的選取橢圓或矩形模型，以進一步提高跟蹤的準(zhǔn)確性.

參考文獻

[1]Yilmaz A, Javed O, Shah M. Object tracking: a survey [J]. ACM Journal of Computing Surveys, 2006, 38(4): 1-45.

[2]Fukunaga F, Hostetler L D. The estimation of the gradient of a density function, with applications in pattern recognition[J]. IEEE Trans Inf Theory, 1975, 21(1):32-40.

[3]Comaniciu D, Ramesh V, Meer P. Kernel-based object tracking[J]. IEEE Trans Pattern Anal Mach Intell, 2003, 25(5):564-577.

[4]Collins R T. Mean-shift blob tracking through scale space[C]//IEEE. Conference on Computer Vision and Pattern Recognition. Wisconsin:IEEE,2003: 234-240.

[5]Zivkovic Z, Krose B. An EM-like algorithm for color-histogram based object tracking[C]//IEEE. Conference on Computer Vision and Pattern Recognition. Washington DC:IEEE, 2004: 798-803.

[6]Hu J, Juan C, Wang J. A spatial-color mean-shift object tracking algorithm with scale and orientation estimation[J]. Pattern Recognit Lett, 2008, 29(16): 2165-2173.

[7]Quast K, Kaup A. Scale and shape adaptive mean shift object tracking in video sequences[C]//ESPC. European Signal Processing Conf. Glasgow:IEEE, 2009: 1513-1517.

[8]Bretzner L, Lindeberg T. Qualitative multi-scale feature hierarchies for object tracking[J] J Vis Commun Image Represent, 2000, 11(2): 115-129.

[9]Bradski G. Computer vision face tracking for use in a perceptual user interface[J]. Intel Technol J, 1998, 2 (2): 1-15.

[10]Ning J, Zhang L, Zhang D, et al. Scale and orientation adaptive mean shift tracking[J]. IET Computer Vision, 2012,6(1): 52-61.

[11]Mukundan R, Ramakrishnan K R. Moment functions in image analysis: theory and applications[M]. Singapore: World Scientific, 1998.