一種尺度和方向適應性的Mean Shift跟蹤算法

一種尺度和方向適應性的Mean Shift跟蹤算法

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

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

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

關鍵詞mean shift跟蹤算法；矩特征；反向投影圖；目標跟蹤

收稿日期2014-12-19

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

基金項目湖北省自然科學基金資助項目(2012FFA113)；武漢市科技供需對接計劃項目(201051824575)；中南民族大學中央高校基本科研業(yè)務費專項資金資助項目(CZW14057)

中圖分類號TP391文獻標識碼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

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

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

1Mean Shift跟蹤算法

1.1目標描述

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

1.1.1目標模型

(1)

(2)

1.1.2候選目標模型

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

(3)

(4)

(5)

(6)

1.2MeanShift迭代

(7)

其中：

(8)

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

(9)

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

(10)

2尺度、方向適應性Mean Shift

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

2.1尺度變化時目標的反向投影圖

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

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

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

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

2.2目標面積的估計

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

(11)

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

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

A=c(ρ)·M00，

(12)

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

(13)

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

2.3矩特征的應用

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

(14)

(15)

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

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

(16)

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

(17)

其中：

(18)

2.4估計目標的寬、高及方向

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

Cov=U×S×UT=

(19)

其中：

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

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

(20)

(21)

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

(22)

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

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

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

(23)

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

(24)

2.6SOAMST算法實現(xiàn)

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

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

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

(5)應用(10)式計算目標候選模型的新位置y1.

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

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

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

(7)應用(22)式估計目標候選模型的寬、高、方向.

(8)應用(24)式估計下一幀目標候選模型.

3實驗結果

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

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

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

3.1對稱視頻序列上的實驗

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

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

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

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

3.2場景視頻序列上的實驗

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

圖3　3種跟蹤算法在場景序列上的跟蹤結果 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每次迭代會進行一次目標位置和方向的估計，而SOAMST每幀只進行一次目標位置和方向的估計，所以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結語

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

參考文獻

[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.