漂移系數(shù)優(yōu)化顏色直方圖的Mean Shift算法

宋康康，陳懇，郭運(yùn)艷

寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江寧波315211

1 引言

近年來，M ean-Shift算法以其無參數(shù)、快速模式匹配的特性被廣泛應(yīng)用到目標(biāo)跟蹤領(lǐng)域[1-3]。經(jīng)典M ean Shift算法利用空間核加權(quán)顏色直方圖作為模板，通過搜索局部巴氏系數(shù)最大值，實(shí)現(xiàn)目標(biāo)跟蹤定位。顏色直方圖是對(duì)圖像在顏色空間中分布的一種簡(jiǎn)單的非參數(shù)估計(jì)，描述了圖像的全局統(tǒng)計(jì)特征，具有旋轉(zhuǎn)和平移不變性，而且特征提取方便，因此常常作為特征模型廣泛應(yīng)用于圖像檢索和目標(biāo)跟蹤之中。另一方面顏色特征容易受光照條件變化的影響，因此利用顏色特征的M ean Shift算法的一個(gè)挑戰(zhàn)是如何提高跟蹤的魯棒性。

為克服上述顏色直方圖的弱點(diǎn)，許多學(xué)者提出了許多改進(jìn)方法。例如，用背景像素與目標(biāo)像素定義加權(quán)系數(shù)，以此計(jì)算空間直方圖，實(shí)施目標(biāo)跟蹤定位，主要存在的問題是如何魯棒的區(qū)分背景與目標(biāo)[4]。文獻(xiàn)[5-6]利用目標(biāo)顏色空間和紋理特征，構(gòu)建邊緣直方圖，用以區(qū)分目標(biāo)與背景信息，提升顏色直方圖的魯棒性。

利用加權(quán)求取顏色特征和邊緣特征的巴氏系數(shù)，進(jìn)行目標(biāo)特征匹配和跟蹤，彌補(bǔ)了單一顏色特征不穩(wěn)定的弱點(diǎn)，但未涉及模板更新問題[7]。利用可見光和紅外雙通道做目標(biāo)多特征信息融合，克服了可見光條件下，顏色直方圖對(duì)光照條件敏感的問題，但是也進(jìn)行模板更新[8]。采用目標(biāo)先驗(yàn)知識(shí)創(chuàng)建了多個(gè)顏色直方圖模板，增強(qiáng)了顏色直方圖模板描述目標(biāo)特征的能力，并能實(shí)時(shí)選取最優(yōu)模型，但是計(jì)算稍微復(fù)雜[9-10]。

上述研究者主要利用多特征或多模型來增強(qiáng)顏色特征刻畫目標(biāo)的強(qiáng)度，取得了不錯(cuò)的效果，但也產(chǎn)生了計(jì)算比較復(fù)雜，設(shè)備多等問題。本文試圖直接從均值漂移的漂移系數(shù)出發(fā)，提升顏色直方圖中目標(biāo)的信息特征，同時(shí)分析論證了屬于目標(biāo)顏色的特征對(duì)漂移貢獻(xiàn)較多，依據(jù)這個(gè)特點(diǎn)，對(duì)漂移系數(shù)較大的特征點(diǎn)進(jìn)行目標(biāo)特征的強(qiáng)化，進(jìn)而減少了收斂迭代次數(shù)。經(jīng)多次強(qiáng)化后，顏色直方圖中的目標(biāo)特征會(huì)凸顯，若不能夠及時(shí)引入因目標(biāo)特征改變而產(chǎn)生的新特征，會(huì)使算法失效，對(duì)此又提出了模板更新機(jī)制，將新的目標(biāo)特征信息加入到直方圖中，從而增強(qiáng)了顏色特征的魯棒性，最終實(shí)現(xiàn)了算法快速穩(wěn)定的跟蹤效果。

2 基于漂移系數(shù)的加權(quán)顏色直方圖

2.1 目標(biāo)信息表示

在M ean Shift算法中，跟蹤目標(biāo)通常定義為一個(gè)橢圓或者矩形的跟蹤窗口內(nèi)，用顏色直方圖描述目標(biāo)的顏色特征信息，則目標(biāo)參考模型可以表示為其中

Ch是歸一化系數(shù)，h是核帶寬，x0是中心像素坐標(biāo)，u是顏色特征值，xi是跟蹤窗口中第i個(gè)像素，共有n個(gè)像素，k(x)是非增、連續(xù)的核函數(shù)，b(xi)將顏色特征映射到對(duì)應(yīng)的直方圖空間。當(dāng)以y為中心時(shí)，候選目標(biāo)模型則按如下的式子建立，={u}u=1,2,…,m，其中

同樣Cc為歸一化系數(shù)。

2.2 Mean Shift跟蹤算法

采用Bhattacharyya系數(shù)度量候選模型與參考模型之間的相似性。通過Mean Shift算法迭代，迭代過程如下：

其中y1為新的目標(biāo)中心坐標(biāo)，

y0是當(dāng)前候選目標(biāo)區(qū)域的中心位置，則基于Mean Shift算法的目標(biāo)跟蹤通過反復(fù)的迭代式（4），使目標(biāo)從當(dāng)前y0不斷的移到新位置y1，直至Bhattacharyya系數(shù)最大或者達(dá)到規(guī)定的迭代次數(shù)為止，得到的y1即M ean Shift

偏移得到的跟蹤窗口的新的中心坐標(biāo)。

2.3 基于背景的加權(quán)顏色直方圖

為削弱目標(biāo)周圍背景信息對(duì)核窗口內(nèi)目標(biāo)信息的干擾，Comaniciu[11]等人提出了基于背景直方圖加權(quán)的M ean Shift算法，即：

2.4 基于漂移系數(shù)優(yōu)化的加權(quán)顏色直方圖

M ean Shift算法在求取漂移系數(shù)時(shí)，將每個(gè)當(dāng)前的點(diǎn)對(duì)應(yīng)到參考的特征空間中，與參考模板相比較而獲得。對(duì)于那些屬于目標(biāo)顏色特征空間中的點(diǎn)，其權(quán)值要較大，這樣算法就能快速收斂到目標(biāo)中心。權(quán)值的大小與對(duì)應(yīng)顏色特征出現(xiàn)在顏色直方圖中的概率大小成正相關(guān)，因此如果目標(biāo)參考模板中混入較多背景信息，反過來沖淡了目標(biāo)本身特征信息，從直方圖上看，對(duì)應(yīng)目標(biāo)特征的bin的高度會(huì)降低，即其概率變小，導(dǎo)致屬于目標(biāo)的漂移系數(shù)下降，從而導(dǎo)致算法收斂產(chǎn)生偏差，出現(xiàn)跟蹤效果差甚至丟失目標(biāo)等情形。

Cheng[13]定義了一族核函數(shù)，使得隨著樣本與被偏移點(diǎn)的距離不同，其偏移量對(duì)均值偏移向量的貢獻(xiàn)也不同，其次還設(shè)定了一個(gè)漂移系數(shù)，使得不同的樣本點(diǎn)重要性不一樣，這大大擴(kuò)大了M ean Shift的適用范圍。這里漂移系數(shù)是指式（5），若將系數(shù)全部設(shè)為1，核函數(shù)取Epanechnikov[13]，其影子函數(shù)為常數(shù)，式（4）就退化為M(x)=，即為一般的均值函數(shù)，此時(shí)核窗口中心的每個(gè)點(diǎn)對(duì)均值偏移的貢獻(xiàn)都是相同的，而M ean Shift算法賦予每個(gè)點(diǎn)不同的系數(shù)，最終收斂于加權(quán)中心處。

針對(duì)背景加權(quán)算法中存在的缺陷，根據(jù)漂移系數(shù)在均值漂移算法中的特點(diǎn)，本文提出了基于漂移系數(shù)優(yōu)化的顏色直方圖的M ean Shift算法。某像素點(diǎn)的漂移系數(shù)反應(yīng)了該點(diǎn)對(duì)漂移的貢獻(xiàn)，漂移系數(shù)越大貢獻(xiàn)也就越大，收斂速度越快，同時(shí)表明屬于目標(biāo)的像素點(diǎn)擁有較大的貢獻(xiàn)。

如圖1顯示的是將核窗口內(nèi)較大的漂移系數(shù)點(diǎn)映射到一幅與核窗口等大的二值圖中，白色點(diǎn)表示該點(diǎn)具有較大的漂移系數(shù)，黑色點(diǎn)的漂移系數(shù)則較小?？梢郧宄吹?，屬于目標(biāo)顏色特征確實(shí)擁有較大漂移系數(shù)，因此跟蹤效果也十分理想。

圖1 漂移系數(shù)分布圖

2.5 漂移系數(shù)優(yōu)化的顏色直方圖

由于目標(biāo)的顏色直方圖容易受到外界的影響，使得顏色直方圖會(huì)混入早上，而通過漂移系數(shù)可以有效去除其中的噪聲。對(duì)于跟蹤中的每一幀，逐個(gè)檢測(cè)核窗口內(nèi)像素點(diǎn)的貢獻(xiàn)值，按貢獻(xiàn)大小，調(diào)整參考顏色直方圖，使目標(biāo)模板能夠刻畫目標(biāo)特征，增強(qiáng)目標(biāo)與背景的區(qū)分度。對(duì)每個(gè)核窗口內(nèi)的像素點(diǎn)，做如下的運(yùn)算：

u′是核窗口內(nèi)的某一像素點(diǎn)對(duì)應(yīng)到顏色特征空間的特征值，U是目標(biāo)的顏色特征空間中擁有較大漂移系數(shù)的特征值的集合，M是核窗口內(nèi)所有像素點(diǎn)的漂移系數(shù)的平均值，為避免漂移系數(shù)等于0，算法會(huì)設(shè)定一個(gè)最小下限ε（一般取0.01），p是核窗口內(nèi)的某個(gè)像素點(diǎn)，b(p)將像素點(diǎn)映射到顏色特征空間，w(b(p))為顏色特征空間的某個(gè)特征值對(duì)應(yīng)的漂移系數(shù)，顏色特征空間一般設(shè)為16×16×16 bin，即將R、G、B量化到一個(gè)三維數(shù)組中。這樣經(jīng)式（7）處理后，系數(shù)較大的顏色特征被保留了下來，小系數(shù)的顏色噪聲去除了。歸一化后得到新的參考目標(biāo)模型newq′={newq′u′}，即更新后的參考目標(biāo)模型，其不僅具備了目標(biāo)的應(yīng)有的特征信息，而且大大抑制了背景的信息。

圖2是第1、291幀的跟蹤結(jié)果。圖3中的左圖是第一幀的目標(biāo)參考模型，右圖是第291幀時(shí)目標(biāo)的參考模型。從實(shí)驗(yàn)結(jié)果看，在第一幀中，雖然使用了背景顏色直方圖加權(quán)，抑制了部分信息，但是顏色直方圖信息比較雜亂，零星分布著一些噪聲信息，這些信息削弱了目標(biāo)特征的表達(dá)。本文算法通過對(duì)目標(biāo)模型中漂移系數(shù)較小加以抑制，從而突出了目標(biāo)的特征信息，從右邊參考模型上可以看到，顏色直方圖中的有效信息被放大了，噪聲也被充分抑制了，并且整個(gè)跟蹤效果十分好。圖4是算法迭代次數(shù)圖，圓圈標(biāo)記的曲線是本文算法的迭代次數(shù)，十字標(biāo)記的是對(duì)比算法的。從圖4迭代次數(shù)上看，本文算法的迭代次數(shù)更少，圖5顯示了各個(gè)特征值對(duì)應(yīng)的漂移系數(shù)值。從圖5上看，本文算法的系數(shù)大而集中，因而迭代次數(shù)就少，收斂更快。

本文算法能夠按照當(dāng)前幀中目標(biāo)的特征，優(yōu)化目標(biāo)參考模型的建立，使得每次漂移權(quán)值都能夠取得較大，克服了過時(shí)的目標(biāo)參考模型引起的目標(biāo)特征描述落后的缺點(diǎn)。雖然在每幀中能夠逐步降低背景成分信息，但是存在一個(gè)不能夠引入新的目標(biāo)特征信息的缺點(diǎn)，對(duì)目標(biāo)變化中引入的有效目標(biāo)信息要在顏色直方圖中及時(shí)體現(xiàn)，因此要進(jìn)行模板更新。

圖2 跟蹤結(jié)果圖

第1幀的目標(biāo)參考模型

圖3 目標(biāo)參考模型

圖4 迭代次數(shù)

圖5 漂移系數(shù)

2.6 基于漂移系數(shù)的模板更新算法

模板更新算法是目標(biāo)匹配算法的關(guān)鍵所在，若不及時(shí)更新模板，會(huì)導(dǎo)致匹配失敗，從而導(dǎo)致跟蹤失敗。更重要的是，采用顏色特征的M ean Shift算法更容易受到外界信息的干擾，主要原因是顏色信息受光照條件影響比較大，光照變化引起的目標(biāo)顏色的輕微變化也會(huì)導(dǎo)致顏色直方圖的劇烈變化。因此模板更新是關(guān)系算法穩(wěn)定性的關(guān)鍵問題。許多學(xué)者也提出了很多模板更新方法[14-15]。

模板更新主要涉及三個(gè)問題，一是背景信息的抑制問題，二是新目標(biāo)信息的引入問題，三是更新時(shí)機(jī)的問題，當(dāng)然還有許多其他問題[16-17]。第一個(gè)問題已經(jīng)在前面一節(jié)中解決，此節(jié)主要論述后兩個(gè)問題。時(shí)機(jī)的選擇很重要，選的太早，就浪費(fèi)寶貴的處理時(shí)間；若過晚，則更新后的模板可靠性很低。因此必須時(shí)時(shí)檢測(cè)目標(biāo)顏色特征的變化情況，在變化還不是太明顯的時(shí)候，便逐步更新。對(duì)于更新條件，本文按如下的公式計(jì)算：

則更新條件為sumq＜0.8。sumq是對(duì)所有較大系數(shù)所占顏色直方圖中的比率，如果比率小于0.8，認(rèn)為當(dāng)前參考模型對(duì)漂移貢獻(xiàn)開始減少，需引進(jìn)新的顏色特征，因而進(jìn)行信息引入式的模板更正。首先建立目標(biāo)周圍2倍區(qū)域背景的顏色直方圖={u}u=1,2,…，k，其共有k個(gè)特征值，參考模板更新公式為：

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

為驗(yàn)證本文算法的有效性，根據(jù)不同的要求，取了標(biāo)準(zhǔn)測(cè)試視頻中的三個(gè)典型序列，每個(gè)序列中跟蹤目標(biāo)的速度和背景復(fù)雜度各不相同，與背景加權(quán)直方圖的M ean Shift算法比較，主要比較內(nèi)容為跟蹤算法的迭代次數(shù)和跟蹤定位效果，以及模板更新。

3.1 實(shí)驗(yàn)1

場(chǎng)景是由運(yùn)動(dòng)相機(jī)拍攝的，而且背景隨著相機(jī)的移動(dòng)而變化，背景信息嘈雜，跟蹤目標(biāo)的速度不是很快，但具有一定的旋轉(zhuǎn)變化，目標(biāo)顏色特征與背景有一些相似之處。

圖6為跟蹤定位結(jié)果，分別取第1、77、89幀的結(jié)果，上兩行為背景加權(quán)算法的跟蹤結(jié)果，后兩行為本文算法的結(jié)果。首先從取出的幾張典型的跟蹤定位圖中看，背景加權(quán)算法受到了背景信息的干擾，產(chǎn)生了一些偏差，本文算法要優(yōu)于背景加權(quán)算法，特別是第77幀時(shí)，本文算法較精確定位了目標(biāo)，而背景加權(quán)算法偏離目標(biāo)中心較大。主要原因是由于背景加權(quán)的顏色直方圖在背景信息中含有與目標(biāo)顏色特征信息類似的特征時(shí)，反過來會(huì)抑制目標(biāo)信息，而本文算法能夠?qū)?quán)值的分析，恢復(fù)被抑制的有效信息，避免了這一弱點(diǎn)。

圖6 本文算法與背景加權(quán)算法跟蹤結(jié)果比較

圖7顯示了迭代結(jié)果，十字標(biāo)記的曲線是本文算法結(jié)果，方塊標(biāo)記的是背景加權(quán)算法的結(jié)果。從迭代次數(shù)上看，本文算法的結(jié)果要明顯優(yōu)于背景加權(quán)算法。原因是目標(biāo)特性信息的提升，給予漂移時(shí)更大的權(quán)值，從而減少了迭代次數(shù)，平均迭代次數(shù)在4.1左右，效率要高出很多，背景加權(quán)算法要多與5次。

圖7 迭代次數(shù)比較

3.2 實(shí)驗(yàn)2

高速運(yùn)動(dòng)的橄欖球運(yùn)動(dòng)員，其背景要簡(jiǎn)單些，但有部分遮擋情況發(fā)生，伴隨有明顯的旋轉(zhuǎn)等目標(biāo)外型變化，且是在攝像機(jī)運(yùn)動(dòng)情況下拍攝的，并且目標(biāo)運(yùn)動(dòng)快速，但其顏色特征與背景區(qū)別較明顯。

圖8為跟蹤定位結(jié)果，分別取第1、45、66幀的結(jié)果，上兩行為背景加權(quán)算法的跟蹤結(jié)果，后兩行為本文算法的結(jié)果。從跟蹤定位效果看，兩者都能夠成功跟蹤定位目標(biāo)，而且效果好，本文算法要略勝一籌。特別在第66幀時(shí)，背景加權(quán)算法定位的中心在運(yùn)動(dòng)員的腿部區(qū)域，而本文算法則在胸部區(qū)域，這是由于在初始化的目標(biāo)的大部分成分集中在胸部區(qū)域，而此區(qū)域?qū)ζ曝暙I(xiàn)較大，因而這些信息會(huì)被提升，最后的跟蹤定位中心為胸部區(qū)域。

圖8 跟蹤結(jié)果比較

圖9顯示了迭代結(jié)果，十字標(biāo)記的曲線是本文算法結(jié)果，方塊標(biāo)記的是背景加權(quán)算法的結(jié)果。再?gòu)牡螖?shù)上看，本文算法的平均迭代次數(shù)為5.09，而背景加權(quán)算法為6.20，要優(yōu)于后者，同樣是由于目標(biāo)特征信息的提升，從而使屬于目標(biāo)的特征提供了較大的漂移系數(shù)，迭代收斂速度也就更加快。綜合上述實(shí)驗(yàn)結(jié)果，在上述復(fù)雜程度的場(chǎng)景下，與背景加權(quán)算法相比，本文算法不僅跟蹤定位精度高，而且效率高。

圖9 迭代次數(shù)比較

3.3 實(shí)驗(yàn)3

圖10為模板更新結(jié)果，分別取第1、88、199幀的結(jié)果，上兩行為背景加權(quán)算法的跟蹤結(jié)果，后兩行為本文算法的結(jié)果。選取目標(biāo)的頭部，頭部選擇后，臉部特征無法捕捉，此時(shí)大權(quán)值所占直方圖比率下降，達(dá)到模板更新條件，進(jìn)行模板更新。第一行為背景加權(quán)算法，沒有及時(shí)采取模板更新，在第88幀開始，跟蹤定位產(chǎn)生偏差，隨后就丟失跟蹤目標(biāo)。而第二行為本文跟蹤結(jié)果，當(dāng)目標(biāo)旋轉(zhuǎn)后，采取了模板更新策略，改變了目標(biāo)參考的特征信息分布，使得在整個(gè)跟蹤過程中依然具有良好的跟蹤定位效果。

圖10 模板更新結(jié)果

4 總結(jié)

本文主要分析了均值漂移算法中漂移系數(shù)的特性，即屬于目標(biāo)特征的漂移系數(shù)相對(duì)較大，依據(jù)此特性將漂移系數(shù)引入到顏色直方圖的計(jì)算中去，有利于目標(biāo)特征的提升，并且能夠區(qū)分出核窗口內(nèi)的背景等其他信息，通過抑制核窗口內(nèi)的噪聲，從而增強(qiáng)了目標(biāo)特征信息的刻畫，使得迭代速度加快。再通過模板更新反映目標(biāo)當(dāng)前特征，使得顏色直方圖得到更新，魯棒性得到增強(qiáng)。最后從兩個(gè)不同復(fù)雜度的標(biāo)準(zhǔn)測(cè)試序列，以及不同的目標(biāo)速度，驗(yàn)證了本文算法執(zhí)行效率高，穩(wěn)定性好。

[1]Shah K A，Kapadia H K，Shah V A，et al.Application of Mean-Shift algorithm for license plate localization[C]//Proceedings of 2011 Nirma University International Conference on Engineering（NUiCONE），2011：8-10.

[2]Zhou Huiyu，Yuan Yuan，Shi Chunmei.Object tracking using SIFT features and mean shift[J].Computer Vision and Image Understanding，2009，113（3）：345-352.

[3]王相海，方玲玲，叢志環(huán).基于MSPF的實(shí)時(shí)監(jiān)控多目標(biāo)跟蹤算法研究[J].自動(dòng)化學(xué)報(bào)，2012，38（1）：139-144.

[4]李小和，張?zhí)?，沈曉東，等.基于加權(quán)空間直方圖的均值漂移目標(biāo)跟蹤[J].光電子·激光，2010，21（5）：767-771.

[5]王新紅，王晶田，敏楊，等.基于空間邊緣方向直方圖的Mean Shift跟蹤算法[J].中國(guó)圖象圖形學(xué)報(bào)，2008，13（3）：586-592.

[6]戴淵明，韋巍，林亦寧.基于顏色紋理特征的均值漂移目標(biāo)跟蹤算法[J].浙江大學(xué)學(xué)報(bào)，2012，46（2）：212-217.

[7]鄭玉鳳，馬秀榮，趙曉琳，等.基于顏色和邊緣特征的均值遷移目標(biāo)跟蹤算法[J].光電子·激光，2011，22（8）：1231-1235.

[8]程詠梅，王進(jìn)行，魏坤，等.基于加權(quán)Mean—Shift可見光/紅外雙通道目標(biāo)跟蹤[J].光子學(xué)報(bào)，2010，39（2）：357-363.

[9]左軍毅，梁彥，潘泉，等.基于多個(gè)顏色分布模型的Camshift跟蹤算法[J].自動(dòng)化學(xué)報(bào)，2008，34（7）：736-742.

[10]袁廣林，薛模根，謝愷，等.多顏色直方圖自適應(yīng)組合Mean Shift跟蹤[J].中國(guó)圖象圖形學(xué)報(bào)，2011，16（10）：1832-1839.

[11]Comaniciu D，Ramesh V，Meer P.Kernel based objecttracking[J].IEEE Transactions on Pattern Analysis and--M achine Intelligence，2003，25（5）：564-577.

[12]Ning J，Zhang L，Zhang D，et al.Robust mean-shift trackingwith corrected background-weighted histogram[J].Com-puter Vision，IET，2012，6（1）：62-69.

[13]Cheng Y.Mean shift，mode seeking and clustering[J].IEEETrans on Pattern Analysis and M achine Intelligence，1995，17（8）：790-799.

[14]彭寧嵩，楊杰，周大可，等.Mean-Shift跟蹤算法中目標(biāo)模型的自適應(yīng)更新[J].數(shù)據(jù)采集與處理，2005，20（2）：125-129.

[15]朱勝利，朱善安.基于卡爾曼濾波器組的Mean Shift模板更新算法[J].中國(guó)圖象圖形學(xué)報(bào)，2007（3）：460-465.

[16]潘吉彥，胡波，張建秋.抑制模板漂移的目標(biāo)跟蹤算法[J].電子學(xué)報(bào)，2009，37（3）：622-627.

[17]Jia Z，Balasuriya A，Challa S.Target tracking with Bayesianfusion based template matching[C]//Proc of IEEE IntConf on Image Processing.[S.l.]：IEEE，2005：2826-2829.