一種自適應色彩融合的Ｍｅａｎ－Ｓｈｉｆｔ跟蹤算法

摘 要：針對現有的MeanShift算法使用單純的顏色特征不能適應光線及背景的變化，易受顏色相近物體干擾的問題，提出了自適應色彩融合方法來提高跟蹤性能。對背景以極坐標的形式進行不等間隔采樣，以融合后的目標直方圖與背景直方圖具有最小相似性為原則搜索色調與飽和度的最佳線性融合系數；考慮背景與目標的漸變，跟蹤過程中在最佳融合系數的自適應調整鄰域內調整融合系數；能夠有效處理相似物體和顏色相近的大背景帶來的干擾。視頻序列跟蹤結果表明，提出的方法能夠實時、穩定地進行跟蹤。

關鍵詞：目標跟蹤； MeanShift跟蹤算法； 自適應色彩融合； 不等間隔采樣； 計算機視覺

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2008)09287503

MeanShift tracking with adaptive combinational color features

WANG Yuquan， XIA Guihua， ZHAO Guoliang

Automation， Harbin Engineering University， Harbin 150001， China)

Abstract:Consider the issue of simple color features which were not robust within the MeanShift framework， an adaptive tracking algorithm using combinational color features was proposed to improve tracking performance. The hypothesis was that the features best discriminate between object and background were also best for tracking the object. Several pixels were sampled in different intervals with polar coordinates in background. A best group of coefficients of hue and saturation was selected by minimizing the similarities between the sampled pixels of background and object. Consider the gradual changing appearance of both tracked object and scene background， a search in a coefficient neighborhood was performed to get the next most adaptive coefficients. Examples are presented that demonstrate that this realtime algorithm can avoid confusion which caused by similar object and background in tracking.

Key words：object tracking; MeanShift tracking algorithm; adaptive combinational color features; different interval sampling; computer vision

MeanShift算法作為一種核直方圖密度估計方法，因算法實時性好，近年來在目標跟蹤領域應用較為廣泛^[1~4]。區別于其他跟蹤方法，MeanShift算法是以顏色分布概率這一統計量為特征的，因此具有對遮擋、旋轉、變形不敏感等優點。目前對MeanShift算法的改進大多集中在目標模型的更新與對快速目標跟蹤的適應性上，而對于如何選擇顏色特征這一重要問題研究較少。在彩色視頻序列的跟蹤問題中，如果繼續采用灰度特征或單一的某個顏色分量作為特征顯然是不合適的。其主要表現為不能適應光線及背景變化，以及在出現遮擋和相似物體靠近時易丟失目標。文獻[5]提出了一種對RGB進行線性融合的方法，由于 RGB色彩空間各分量的耦合度較高，對光線變化較為敏感，對跟蹤效果的改進一般，并且其在考慮目標與背景的區分程度時只選擇了面積較小的區域作為背景，物體極容易運動出這片區域而使融合失效。針對上述問題，提出一種自適應的HIS空間色彩融合方法來改善跟蹤效果。

1 MeanShift跟蹤算法

1.1 MeanShift算法^[6]

MeanShift算法是一種核密度估計方法，算法原理如下：

設d維空間Rd的樣本集合{xi}（i=1，…，n），多維變量的核密度估計由下式計算：

1.2 MeanShift算法在跟蹤中的應用[7，8]

設{x*i}i=1，…，n為目標所在區域的點集，區域坐標已按照區域的大小歸一化。將所有像素的顏色值量化成m個等級，b(x*i)是每個像素的顏色量化值，顏色u=1，…，m在目標模式中出現的概率為

u=C ∑ni=1 k(‖x*i‖2)δ[b(x*i)-u]

在候選模式中出現的概率為

u(y)=CH∑nhi=1k(‖H-1(y-xi)‖2)δ[b(xi)-u](4) 

使用Bhattacharyya(BH)系數^[9]來描述目標與候選目標的相似度

(y)≡ρ[(y)，]=∑mu=1u(y)u(5) 

利用MeanShift算法對BH系數求最大值，則新的目標位置為

2 自適應色彩融合

2.1 色彩融合

由于灰度或單一的某個顏色分量在跟蹤中的不穩定性，筆者采用色彩融合的方法提取顏色特征。目前較為常用的RGB色彩空間中各分量耦合程度較高，且對光線變化敏感，選擇在HIS空間內進行色彩融合。在HIS空間中，H分量代表了色調，I代表了亮度，S代表了飽和度。為使跟蹤穩定，舍棄代表光照影響的I分量，選取H和S兩個分量進行色彩融合。融合的主要目的為選取出一組融合系數ω1、ω2，有線性函數如下：

f(xi)=ω1H(xi)+ω2S(xi)(7)

這樣每一個像素都對應了一個融合特征值f，將此特征值按照1.2節的方法進行量化，得到量化值b(xi)，進而獲得目標與背景的核直方圖。

筆者認為使目標核直方圖與背景核直方圖得到最大程度的區分的一組融合系數為最佳融合系數。因此仍然選擇BH系數作為目標與背景區分程度的度量，只是此時最佳融合系數對應著BH系數的最小值。

21.1 色彩融合特征集

對于每一個像素，能夠直接獲得它的RGB分量的數值，利用轉換公式計算H與S分量^[10]，并將這兩個分量都歸一化到0～1。取融合系數為-1~1的浮點數，以0.1為步長，得到色彩融合特征集

F≡{ω1H+ω2S｜ωi∈[-1，1]，10ωi∈Z，i=1，2} (8)

21.2 色彩融合中的目標與背景核直方圖

按照習慣，記目標色彩融合加權核直方圖為Hobj，背景色彩融合加權核直方圖為Hbg。在初始幀，通過手動選取要跟蹤的目標，Hobj就等同于MeanShift算法中距離加權的目標核直方圖。具體計算方法如下：

如圖1所示，用長軸和短軸分別為a和b的橢圓框住目標物體，將橢圓框內的每一點歸一化到單位圓內

χi=(xi/a，yi/b)(9)

令di表示每一像素到橢圓中心的距離，ωd為權值

ωd(χi)=1-d2i(10)

式(10)對每一個像素點進行中心距離加權，離中心越近，權值越高。這樣做突出了目標中心處的信息，弱化了易出現干擾與遮擋等問題的邊緣處的信息。

Hobj=S-10∑Ni=1ωd(χi)δ[b(χi)-u](11)

其中：S0=∑Ni=1ωd(χi)，它滿足∑Ni=1Hobj=1。

再計算背景直方圖：

2.2 背景的不等間隔采樣

文獻[5]中選取了三倍于目標的區域作為背景區，但是在實際的跟蹤中筆者發現，物體運動速度較快時，這樣的背景選擇方法是不合適的。若每當物體超出此背景范圍時均按照此方法重新選取目標與背景并計算最優的色彩融合特征，將耗時巨大，算法將失去實時性。若不重新計算融合特征，則原特征已失效，失去了融合的意義，反而引入了不穩定性。

針對這種情況，筆者選擇剔除了目標區域的整幅圖像作為背景，考慮到計算量的問題，采取在大背景內進行不等間隔采樣的方法降低計算量。

以目標中心為原點用極坐標來表示這一采樣過程。以三倍的目標區域為界，三倍目標區域以內的區域極坐標半徑以三個像素為步長遞增，三倍目標區域距離以外的區域極坐標半徑以九個像素為步長遞增，角度均以0.1rad為步長進行采樣。圖1為H與S以等權值進行融合后的核直方圖。

了圖像的全局特征。用此方法獲取背景直方圖是合理且有效的。

利用上述背景不等間隔采樣方法進行處理，得到各組系數的BH值。表1為能夠較好地區分圖1 中目標與背景的系數組合，可見最佳組合為（-0.8，0.2）。

23 自適應色彩融合

從上面色彩融合特征的選取過程可以看出，選取的特征在大的背景范圍內能夠最大程度地區分目標和背景。當背景隨時間變化時，先前選取的最佳色彩融合權值不一定適合當前幀，此時需要對權值作出調整。若利用前面講述的方法在當前幀重新計算所有系數組合的BH值，將耗時較長，影響跟蹤算法的實時性。因此，有必要尋找一種既能滿足實時性，又能夠提高跟蹤準確率的系數調整方法。針對此問題本文提出了一種色彩融合系數的自適應調整方法。

23.1 系數的自適應調整鄰域

定義 對于一組色彩融合系數ω1、ω2，均以0.1為步長上下浮動所能構成的所有新的色彩融合系數組合與原組合一起稱為一組融合系數的自適應調整鄰域，記為L。可見L中的元素個數為9。

23.2 自適應色彩融合

在跟蹤初始幀，通過色彩融合的方法選取了一組最大程度上區分目標與背景的融合系數。隨著跟蹤過程中背景的變化，或相似物體的靠近，原融合系數可能不再是當前幀的最佳融合系數。

表2為一個視頻序列中連續10幀圖像的最優色彩融合系數及目標與背景核直方圖的BH系數。

從表2中數據可以看到，同一視頻序列中的連續圖像的最優融合系數是互為鄰域的。這是因為背景變化是緩慢進行的，最優融合系數也不會發生跳變。因此筆者選擇在原融合系數的自適應調整鄰域內搜索當前最優權值。算法如下：

a）選定目標，計算初始幀的最優色彩融合系數，獲得初始幀MeanShift目標核直方圖。b）采集下一幀圖像。

c）用MeanShift方法進行跟蹤，獲得新的目標位置。

d）計算新目標的自適應色彩融合鄰域中各元素的BH系數，更新最優色彩融合系數與目標核直方圖。轉b）。

選擇鄰域作為自適應調整范圍是有其優勢的：（a）目標與背景在跟蹤過程中的變化是連續的不是突然的，選擇前一幀鄰域作為搜索范圍正體現了這種連續性，也在一定程度上抑制了特征的漂移。（b）表2所示的實驗結果也說明了較好的權值組合的分布是連續的。對于連續變化的背景與目標，鄰域內的自適應調整無論從理論還是實驗結果來說都是十分合理的。

3 跟蹤方法舉例比較

下面為一組跟蹤序列，以藍色圓形物體為目標， 目標與大片的背景均為藍色，但是存在著顏色深淺的差異，這代表了大片背景干擾的典型情況。這組序列分別采用顏色特征H、RGB色彩融合以及自適應色彩融合進行跟蹤，量化等級均為256。測試所用的計算機配置為：Pentium D CPU 2.80 GHz 2.81 GHz，2.00 GB內存。

從表格與量化后的圖像中可以看出，利用H分量進行跟蹤時目標與背景極其相似，最終目標丟失在藍色大背景中，如圖2(a)與表3。使用RGB色彩融合跟蹤時，目標與背景間的差別有所增加，但是差值增加有限，跟蹤結果存在誤差，且由于耗時巨大不能做到實時跟蹤，如圖2(b)與表4。自適應色彩融合的方法由于對背景的不等間隔采樣，使跟蹤能夠對大片干擾的靠近做出融合系數的實時調整，目標能夠始終被穩定且準確地跟蹤，耗費時間較少，能夠滿足跟蹤的實時性，如圖2(c)與表5。

圖3所示的人臉序列代表了人臉跟蹤中的交疊問題，這對于跟蹤問題來說是較為嚴峻的情況。可以看出，利用RGB色彩融合特征進行跟蹤的結果是相似物體靠近并交疊時目標丟失，如圖3(a)。利用本文提出的方法則可穩健地進行跟蹤，如圖3(b)。

表3 用H特征進行跟蹤的數據

幀目標平均灰度背景平均灰度目標與背景灰度差耗費時間/s

第一幀12912720.058 526

第二幀12712700.056 269

第三幀12812620.057 531

表4 用RGB融合進行跟蹤的數據

幀目標平均灰度背景平均灰度目標與背景灰度差耗費時間/s

第一幀172150220.210 667

第二幀178147310.211 043

第三幀181146350.209 871

表5 用自適應色彩融合進行跟蹤的數據

幀目標平均灰度背景平均灰度目標與背景灰度差耗費時間/s

第一幀12369540.080 263

第二幀13070600.081 552

第三幀14072680.080 372

從上述實驗結果可以看出，自適應色彩融合的跟蹤效果明顯優于H特征與RGB色彩融合特征的跟蹤效果，在存在交疊與較大背景干擾的情況下仍然能夠準確鎖定目標。由于跟蹤過程中的自適應調整在L鄰域內進行，保證了算法的實時性。

4 結束語

本文研究了MeanShift算法中的顏色特征選取與更新方法，通過實驗證明了時間上連續的兩幀圖像的最優色彩融合系數是互為鄰域的。這樣即可在跟蹤初始幀利用對背景的不等間隔采樣選取出最能區分背景與目標的系數組合，并在跟蹤過程中在上一幀融合系數的鄰域內實時調整，大大改善了MeanShift算法的抗干擾性，并且避免了特征的漂移。對于背景變化緩慢的場合，可以適當降低自適應融合頻率進一步提高快速性。之前的MeanShift算法改進主要集中在模板的更新與對快速目標的適應性上，而忽略了如何選取顏色特征這個最基本的問題，本文的研究恰恰填補了這個缺陷。兩組具有代表性的跟蹤實驗表明，本文提出的算法能夠解決相似物體靠近及交疊所帶來的干擾，并能保證在顏色相近的大背景中穩定跟蹤。除了上面提到的各種改進之外，目前對MeanShift算法的步長問題的研究還不是很清楚，將成為筆者以后研究的重點。

參考文獻：

［1］FUKUNAGE K， HOSTETLER L D. The estimation of the gradient of a density function， with applications in pattern recognition[J]. IEEE Trans on Information Theory，1975，21(1):3240.

[2]CHENG Y. MeanShift， mode seeking， and clustering[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，1995，17(8):790799.

[3]COMANICIU D， RAMESH V， MEER P. Realtime tracking of nonrigid objects using MeanShift[J]. IEEE Computer Vision and Pattern Recognition，2000，4(2):142149.

[4]COMANICIU D， MEER P. MeanShift: a robust approach toward feature space analysis[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2002，24(5):603619.

[5]COLLINS R T， LIU Yanxi ， LEORDEANU M. Online selection of discriminative tracking features[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27(10):16311643.

[6]文志強， 蔡自興. MeanShift算法的收斂性分析[J]. 軟件學報， 2007，18(2): 205212.

[7]COMANICIU D， RAMESH V， MEER P.Kernelbased object tracking[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2003，25(5):564575.

[8]FASHING M， TOMASI C. MeanShift is a bound optimization[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27(3): 471474.

[9]KAILATH T. The divergence and Bhattacharyya distance measures in signal selection[J]. IEEE Trans on Communication Technology，1967，15(1): 5260.

[10]ZHAN Yujin， YAO Yurong， HE Yun. Color image segmentation based on HSI model[J]. High Technology Letters，1998，4(1):2831.

[11]賈靜平， 趙榮椿. 使用MeanShift進行自適應序列圖像目標跟蹤[J]. 計算機應用研究， 2005，22(2):247251.