漂移系數優化顏色直方圖的Mean Shift算法

宋康康，陳懇，郭運艷

寧波大學信息科學與工程學院，浙江寧波315211

1 引言

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

為克服上述顏色直方圖的弱點，許多學者提出了許多改進方法。例如，用背景像素與目標像素定義加權系數，以此計算空間直方圖，實施目標跟蹤定位，主要存在的問題是如何魯棒的區分背景與目標[4]。文獻[5-6]利用目標顏色空間和紋理特征，構建邊緣直方圖，用以區分目標與背景信息，提升顏色直方圖的魯棒性。

利用加權求取顏色特征和邊緣特征的巴氏系數，進行目標特征匹配和跟蹤，彌補了單一顏色特征不穩定的弱點，但未涉及模板更新問題[7]。利用可見光和紅外雙通道做目標多特征信息融合，克服了可見光條件下，顏色直方圖對光照條件敏感的問題，但是也進行模板更新[8]。采用目標先驗知識創建了多個顏色直方圖模板，增強了顏色直方圖模板描述目標特征的能力，并能實時選取最優模型，但是計算稍微復雜[9-10]。

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

2 基于漂移系數的加權顏色直方圖

2.1 目標信息表示

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

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

同樣Cc為歸一化系數。

2.2 Mean Shift跟蹤算法

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

其中y1為新的目標中心坐標，

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

偏移得到的跟蹤窗口的新的中心坐標。

2.3 基于背景的加權顏色直方圖

為削弱目標周圍背景信息對核窗口內目標信息的干擾，Comaniciu[11]等人提出了基于背景直方圖加權的M ean Shift算法，即：

2.4 基于漂移系數優化的加權顏色直方圖

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

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

針對背景加權算法中存在的缺陷，根據漂移系數在均值漂移算法中的特點，本文提出了基于漂移系數優化的顏色直方圖的M ean Shift算法。某像素點的漂移系數反應了該點對漂移的貢獻，漂移系數越大貢獻也就越大，收斂速度越快，同時表明屬于目標的像素點擁有較大的貢獻。

如圖1顯示的是將核窗口內較大的漂移系數點映射到一幅與核窗口等大的二值圖中，白色點表示該點具有較大的漂移系數，黑色點的漂移系數則較小。可以清楚看到，屬于目標顏色特征確實擁有較大漂移系數，因此跟蹤效果也十分理想。

圖1 漂移系數分布圖

2.5 漂移系數優化的顏色直方圖

由于目標的顏色直方圖容易受到外界的影響，使得顏色直方圖會混入早上，而通過漂移系數可以有效去除其中的噪聲。對于跟蹤中的每一幀，逐個檢測核窗口內像素點的貢獻值，按貢獻大小，調整參考顏色直方圖，使目標模板能夠刻畫目標特征，增強目標與背景的區分度。對每個核窗口內的像素點，做如下的運算：

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

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

本文算法能夠按照當前幀中目標的特征，優化目標參考模型的建立，使得每次漂移權值都能夠取得較大，克服了過時的目標參考模型引起的目標特征描述落后的缺點。雖然在每幀中能夠逐步降低背景成分信息，但是存在一個不能夠引入新的目標特征信息的缺點，對目標變化中引入的有效目標信息要在顏色直方圖中及時體現，因此要進行模板更新。

圖2 跟蹤結果圖

第1幀的目標參考模型

圖3 目標參考模型

圖4 迭代次數

圖5 漂移系數

2.6 基于漂移系數的模板更新算法

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

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

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

3 實驗結果

為驗證本文算法的有效性，根據不同的要求，取了標準測試視頻中的三個典型序列，每個序列中跟蹤目標的速度和背景復雜度各不相同，與背景加權直方圖的M ean Shift算法比較，主要比較內容為跟蹤算法的迭代次數和跟蹤定位效果，以及模板更新。

3.1 實驗1

場景是由運動相機拍攝的，而且背景隨著相機的移動而變化，背景信息嘈雜，跟蹤目標的速度不是很快，但具有一定的旋轉變化，目標顏色特征與背景有一些相似之處。

圖6為跟蹤定位結果，分別取第1、77、89幀的結果，上兩行為背景加權算法的跟蹤結果，后兩行為本文算法的結果。首先從取出的幾張典型的跟蹤定位圖中看，背景加權算法受到了背景信息的干擾，產生了一些偏差，本文算法要優于背景加權算法，特別是第77幀時，本文算法較精確定位了目標，而背景加權算法偏離目標中心較大。主要原因是由于背景加權的顏色直方圖在背景信息中含有與目標顏色特征信息類似的特征時，反過來會抑制目標信息，而本文算法能夠對權值的分析，恢復被抑制的有效信息，避免了這一弱點。

圖6 本文算法與背景加權算法跟蹤結果比較

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

圖7 迭代次數比較

3.2 實驗2

高速運動的橄欖球運動員，其背景要簡單些，但有部分遮擋情況發生，伴隨有明顯的旋轉等目標外型變化，且是在攝像機運動情況下拍攝的，并且目標運動快速，但其顏色特征與背景區別較明顯。

圖8為跟蹤定位結果，分別取第1、45、66幀的結果，上兩行為背景加權算法的跟蹤結果，后兩行為本文算法的結果。從跟蹤定位效果看，兩者都能夠成功跟蹤定位目標，而且效果好，本文算法要略勝一籌。特別在第66幀時，背景加權算法定位的中心在運動員的腿部區域，而本文算法則在胸部區域，這是由于在初始化的目標的大部分成分集中在胸部區域，而此區域對漂移貢獻較大，因而這些信息會被提升，最后的跟蹤定位中心為胸部區域。

圖8 跟蹤結果比較

圖9顯示了迭代結果，十字標記的曲線是本文算法結果，方塊標記的是背景加權算法的結果。再從迭代次數上看，本文算法的平均迭代次數為5.09，而背景加權算法為6.20，要優于后者，同樣是由于目標特征信息的提升，從而使屬于目標的特征提供了較大的漂移系數，迭代收斂速度也就更加快。綜合上述實驗結果，在上述復雜程度的場景下，與背景加權算法相比，本文算法不僅跟蹤定位精度高，而且效率高。

圖9 迭代次數比較

3.3 實驗3

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

圖10 模板更新結果

4 總結

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

[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]王相海，方玲玲，叢志環.基于MSPF的實時監控多目標跟蹤算法研究[J].自動化學報，2012，38（1）：139-144.

[4]李小和，張太鎰，沈曉東，等.基于加權空間直方圖的均值漂移目標跟蹤[J].光電子·激光，2010，21（5）：767-771.

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

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

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

[8]程詠梅，王進行，魏坤，等.基于加權Mean—Shift可見光/紅外雙通道目標跟蹤[J].光子學報，2010，39（2）：357-363.

[9]左軍毅，梁彥，潘泉，等.基于多個顏色分布模型的Camshift跟蹤算法[J].自動化學報，2008，34（7）：736-742.

[10]袁廣林，薛模根，謝愷，等.多顏色直方圖自適應組合Mean Shift跟蹤[J].中國圖象圖形學報，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跟蹤算法中目標模型的自適應更新[J].數據采集與處理，2005，20（2）：125-129.

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

[16]潘吉彥，胡波，張建秋.抑制模板漂移的目標跟蹤算法[J].電子學報，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.