一種基于空間直方圖的Mean-Shift跟蹤算法

摘 要:經典的MeanShift跟蹤算法以顏色直方圖為特征對目標進行跟蹤。顏色直方圖反映的是圖像中顏色的組成情況，即出現了哪些顏色以及各種顏色出現的次數。顏色直方圖具有旋轉不變性、縮放不變性等優點，經常用于圖像檢索，即通過比較顏色直方圖的差異來衡量兩幅圖像在顏色全局分布上的差異。但是顏色直方圖不能反映顏色的空間分布特征，當跟蹤目標與背景色顏色相近時可能造成錯誤跟蹤，導致跟蹤失敗?？紤]目標顏色空間分布特征，將空間分布信息融入顏色直方圖中，提出了基于空間顏色直方圖的MeanShift跟蹤方法，全面地反映了顏色的整體分布信息和空間分布信息。在VC 6.0上利用新方法和經典MeanShift跟蹤方法分別對發生遮擋的視頻和快速運動的視頻進行跟蹤，實驗結果表明，提出的新方法能夠更好地對目標進行跟蹤，避免跟蹤過程中的目標丟失。

關鍵詞:目標跟蹤; MeanShift跟蹤; 顏色直方圖; 空間顏色直方圖; 相似性度量

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

文章編號:1001-3695(2010)06-2394-04

doi:10.3969/j.issn.10013695.2010.06.114

Improved MeanShift tacking algorithm based on spatial histogram

HU Bin， ZHAO Huang， ZHENG Min

(School of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:The colorhistogram indicates the color components of the target objectthe sorts of color and the number of every kind of color. The global color histogram method has some excellenciesthe rotation inflexibility and scale inflexibility and so on， so it is often used in the image retrievingcomparing two images through computing the difference of the color histogram of the two images. But the color histogram does not involve the spatial distributing information of the color .It may bring on failed tracking while the colors of target object is similar with the background colors.This paper proposed an improved tracking mehod which based on spatial color histogram， which involved both the colors number information and the spatial distribution information of the colors information. This paper applied new method and the classic MeanShift tracking method on the object occlusion of video and fastmotion video using VC 6.0. The experiment shows that the new method can tacking the target object better than the classic MeanShift tracking algorithm.

Key words:object tracking; MeanShift tracking; color histogram; spatial color histogram; similarity match

0 引言

目標跟蹤一直是計算機視覺研究領域的熱點問題，其應用領域有視頻監控、人機用戶接口、虛擬現實等。如何對視頻序列中的目標進行穩健、有效的跟蹤是目標跟蹤的研究重點。顏色信息由于對目標的平移、旋轉和尺度變化具有不變性以及對遮擋和姿態變化不敏感的特點而成為圖像處理中的一種重要特征。因此，基于顏色信息的目標跟蹤方法引起了許多研究者的關注[1~8]， 在視頻監控、智能人機交互、圖像和視頻編碼以及智能機器人等許多研究領域得到了廣泛的應用。

均值漂移(MeanShift)是Fukanaga等人[1]提出的一種非參數概率密度梯度估計算法，在統計相似性計算與連續優化方法之間建立了一座橋梁。Cheng[2]發展了這一理論，將其運用到模式分類與圖像分割中，此后，均值漂移被廣泛用于模式分類、圖像分割以及目標跟蹤等方面。Comaniciu 等人[3，4]提出了一種加權直方圖(weighted histogram)建模目標的顏色概率分布 (又稱為基于核的概率密度表達)，該方法統計落入每一個直方圖區間像素的加權個數，其中權重是落入該區間的像素二維空間坐標和目標中心的距離函數，距離越小權重越大。這種方法用Bhattacharrya 距離來度量顏色模型之間的相似度，通過一階梯度下降算法將該距離測度極小化，從而在搜索范圍內得到目標的位置。 該方法被稱之為MeanShift (MS) 算法，能夠通過較少的幾次迭代收斂到目標的真實位置，由于MS算法速度快，適用于實時視頻跟蹤中對目標進行跟蹤而受到了研究者的重視。Collins 借鑒Lindeberg 的尺度空間理論，將其融入MeanShift 算法中用來解決其不能很好地跟蹤尺度變化的目標的缺點[5]。實驗結果表明該算法實時性很強，可以實現對運動人臉的快速跟蹤， 同時對目標遮擋也有很好的魯棒性。

顏色直方圖只包含了該圖像中某一顏色值出現的頻數，僅僅反映了物體的全局色彩信息，不能反映顏色的空間分布特征。任一幅圖像都能惟一地給出一幅與它對應的直方圖，但不同的圖像可能有相同的顏色分布，從而就具有相同的直方圖，因此直方圖與圖像是一對多的關系，僅僅以目標的顏色直方圖為模型進行MeanShift迭代跟蹤不能全面地反映目標顏色的空間分布信息，在跟蹤過程中有可能發生跟蹤失敗。

1 經典MeanShift跟蹤方法

1.1 目標模型描述

視頻目標跟蹤是MeanShift算法的一個重要應用方面，大多數文獻都沿用Comaniciu的方法[3， 4]，采用Bhattacharyya系數作為相似性度量標準，然后利用MeanShift算法來確定最佳目標位置。MeanShift跟蹤算法以目標的顏色直方圖作為目標特征的描述模型。如果目標特征和候選目標特征分別表示為

q={qu}u=1，…，m，p(y)={pu(y)}u=1，…，m其中:y表示的是候選目標區域的中心位置，滿足∑mu=1qu=1，∑mu=1pu=1;m為特征值bin的個數。采用Bhattacharyya系數來衡量目標模型與候選目標的相似性，即ρ(y)u≡ρ[p(y)，q]。目標模型的特征分布表示為

qu=C∑ni=1k(‖x*i‖2)δ[b(x*i)-u]其中:δ(#8226;)是Kronecker delta函數;{x*i}i=1，…，n表示的是目標區域里面的像素位置，歸一化后目標模型中心像素的位置為0;b∶R2→{1，…，m}是像素點到像素特征bin的映射函數，C為歸一化常數。

相應的候選目標模型的特征分布表示為

pu=Ch∑nhi=1k(‖y-xih‖2)δ[b(x*i)-u]

其中:Ch是歸一化常數;nh為候選目標區域中的像素總數;k(#8226;)為核函數;h為帶寬。

1.2 基于相似度量函數的目標跟蹤

相似函數定義了兩個模型之間的相似程度，在MeanShift跟蹤算法中，為了得到目標與候選目標相似度，定義目標模型與候選模型的計算公式為

d(y)=1-ρ[p(y)，q](1)

其中:ρ[p(y)，q]=∑mu=1pu(y)qu為q和p(y)之間的Bhattacharyya系數。

要使得式(1)取得最小值就必須保證Bhattacharyya系數ρ[p(y)，q]取最大值。在pu(y0)處進行一階Taylor式展開，忽略一些極小項，可以得到ρ[p(y)，q]的線性近似式如下:

ρapprax[p(y)，q]≈12∑mu=1pu(y0)qu+12∑mu=1pu(y)qupu(y0)

假設pu(y0)>0，對于所有的u=1，…，m成立，則有

ρapprax[p(y)，q]≈12∑mu=1pu(y0)qu+Ch2∑nhi=1wik‖y-xih‖2(2)

其中:wi=∑mu=1qupu(y0)δ[b(xi)-u]。式中第一部分為常量，要使得ρ[p(y)，q]最大，式(2)的第二部分就得取最大值。結合均值漂移算法計算步驟，可得MeanShift算法的迭代公式如下:

y1=∑nhi=1xiwig‖y0-xih‖2∑nhi=1wig‖y0-xih‖2(3)

其中:g(x)= -k′(x)。如果使用Epanechniko核，那么式(3)可進一步化簡為

y1=∑nhi=1xiwi∑nhi=1wi(4)

首先初始化y0，計算wi，并重復式(4)的計算，直到‖yi+1-yi‖<ε或大于預定的最大迭代次數(一般設置為5次)，迭代結束，ε為預先設定的大于0的正數(一般取值為1個像素)，得到的最終位置yi+1即為目標中心所在的位置。

2改進的MeanShift算法

2.1 空間顏色直方圖

2.1.1 考慮圖像的邊緣特征

圖像的邊緣信息是圖像一個重要特征，是人眼識別圖像的一個重要因素，但是顏色直方圖并沒有考慮圖像的邊緣信息。本文將屬于邊緣點的顏色和其他不屬于邊緣點的同類顏色區別對待，對顏色直方圖進行擴展。

設M為定義的顏色數目，加入邊緣點特征后將顏色特征點擴展到2M個，本文定義從圖像像素這2M個特征空間的函數如下:

設x為圖像中的一個像素，分別定義其RGB顏色空間值為Rx、Gx、Bx，則映射函數為

K=Hx×M+Rx×L1+Gx×L2+Bx(5)

其中:Hx取值為0或者1(當該像素點為邊緣像素點時Hx取值為1，否則Hx取值為0);L1、L2為量化值。通過上述公式，將圖像顏色特征空間從M擴展到2M空間。

2.1.2 考慮像素坐標位置

顏色直方圖是圖像的一種重要特征，然而其完全丟棄了圖像顏色的空間分布信息。為了有效利用圖像顏色的空間分布信息，Rao等人[7]提出采用環形顏色直方圖來描述顏色的空間分布特征，Clique等人[8]提出采用SCH 來描述具有相同顏色的像素在圖像空間的分布特征。借鑒Rao和Clique 等人提出的像素在圖像空間的分布特征，針對MeanShift跟蹤算法固有的缺點，將像素分布的坐標信息考慮到直方圖中。

首先本文給出同一種顏色像素質心的定義:

定義1 設I表示任意一幅圖像，I(x，y)為像素(x， y)處的值:

Ai={(x，y)|(x，y)∈I，I(x，y)=i，1≤i≤m}

為圖像中顏色為i的所有像素的集合，其中m表示圖像顏色總的數目，|Ai| 表示集合Ai中像素的數目， 為圖像中顏色為i的所有像素的質心。xi 和yi 定義為

xi=1Ai∑(x，y)∈Aix， yi=1Ai∑(x，y)∈Aiy(6) 

定義2 設p為(x，y)處的顏色為i的一個像素點，該點到顏色i的質心距離以及到質心的均值分別定義為

dn(p，Ci)=(x-xi)2+(y-yi)2，μi=∑n=|Ai|n=1dn(p，Ci)|Ai|(7)

定義3 定義顏色i的像素到質心的距離方差為σ2i則

σ2i=∑n=|Ai|n=1(ui-dn(p，Ci))2|Ai|(8)

本文定義新的直方圖模型為〈bi，ui，σ2i〉，計算公式為

q(y)=bi(y)G(ui，σ2i)

融入顏色的空間分布信息到新的直方圖模型中。

如下兩幅圖像，圖2(a)為圖1(a)交換兩個像素塊的位置而得到的。兩幅圖像的像素顏色的類型與相同特征顏色的個數完全一樣，只是在空間分布上發生了變化。首先計算原圖像的顏色直方圖和改進過后的空間顏色直方圖(圖1)。

下面計算交換像素塊后的圖像顏色直方圖和改進過后的空間顏色直方圖(圖2)。比較圖1和2可以發現，圖1(a)和圖2(a)的顏色直方圖是一樣的，但是圖1(a)和圖2(a)的空間直方圖卻有著明顯的區別。由此可見，空間顏色直方圖能夠體現出像素的空間分布信息，能夠更全面地表征圖像。

2.2 色模型及相似性度量

基于上述空間—顏色直方圖模型，給定由N個像素組成的目標參考圖像， 其中xi是第i 個像素的空間坐標，這個像素在圖像中的位置可以用這個像素到其顏色質心的距離即dn(xi，Cu)來體現，更新過后的pu按如下方式定義

pu(t(x);bu，μu，σu2)=buG(μu，σu2)(9)

其中:G(μu，σu2)是均值向量為ui、方差矩陣為σu2的高斯分布，μu，σu2的定義見定義1和2;bu(y)為色彩特征分布計算表達式。

考慮一個由N′個像素組成的中心坐標為y的候選圖像區域的顏色分布:

p(y)=bu′(y)G(μ′u，σ′u2)(10)

其中:μ′u、σ′u2與式(9) 中的μu、σu2具有相似的形式，而bu′(y)為經典MeanShift算法的目標色彩直方圖。

qu(t(x);bu，μu，σu2)與pu(y)之間的相似性根據Bhattacharrya 距離來度量ρ[qu，pu(y)]=∑mu=1qu，pu(y)。通過積分得到

ρ[qu，pu(y)]=Cu(bub′u)12(11)

其中:

Cu=(2|Ru‖R′u‖|Ru+R′u|)12exp(-14(μu-μ′u)2(Ru+R′u)-1)

所以定義目標模型和候選模型的相似度為

ρ[q，p(y)]=∑du=1ρ(qu，pu(y))(12)

直方圖只包含了該圖像中某一顏色值出現的頻數，而丟失了某像素所在的空間位置信息。本文提出的新的顏色直方圖模型考慮了顏色的空間分布信息，能夠更好地反映圖像的特征。

2.3 改進后的算法

設在前一幀中目標的中心位于y0，在當前幀中，MeanShift 算法基于梯度下降方法尋找式(12)的極值。類似于經典MeanShift算法將式(12) 在p(y0) 進行一階泰勒展開，相對于y求偏導數并令其為零，得到如下迭代等式:

y1=∑nhi=1xiwig‖y0-xih‖2∑nhi=1wig‖y0-xih‖2(13)

wi=∑mu=1Cububu(y0)δ[b(xi)-u]

其中: Cu與上面定義相同。如果使用Epanechniko核，那么式(13)可進一步化簡為同式(4)的形式。整個跟蹤流程如下:

a)逐幀采集視頻，若為第一幀則轉到步驟b)，否則轉到步驟c)。

b)選定跟蹤目標，通過2.2節描述的模型計算其空間—顏色直方圖M，轉到步驟c)。

c)取初始目標中心為上一幀確定的目標中心，設為y0。轉到步驟d)。

d)通過2.2節描述的模型，計算中心為y0的候選目標的空間—顏色歸一化直方圖p(y0)。計算M與p(y0)的匹配系數。轉到步驟e)。

e)利用MeanShift迭代公式，計算得到候選目標的中心位置y1。通過2.2節描述的模型，計算中心為y1的候選目標的空間—顏色歸一化直方圖p(y1)。計算M與p(y1)的匹配系數。轉到步驟f)。

f)判斷‖y1-y0‖是否小于閾值，是的話停止迭代，y1即為要找的最優目標中心點，轉到步驟a);否則，比較ρ[p(y0)，M]與ρ[p(y1)，M]。若ρ[p(y0)，M]≤ρ[p(p1)，M]，則設y0=0.5(y1+y0)，否則y0=y1。轉到步驟d)。

經典的MeanShift算法的主要時間消耗在計算選定區域和候選區域的顏色直方圖計算式(4)，時間復雜度為O(MN)，其中M、N為選定區域的長度和寬度。算法改進后，式(4)并沒有變復雜，主要是在計算直方圖的時候需要額外計算像素點的顏色均值和方差，均值需要MN次計算，方差需要MN次計算，總共增加2MN次計算時間，總的時間復雜度可以用O(MN)+2MN表示，其中O(MN)+2MN的時間復雜度即為O(MN)。所以雖然稍微增加了計算量，但是并沒有增加算法的時間復雜度，滿足實時性要求。

3 實驗

圖像的采樣速率為30 fps，RGB顏色空間為512。機器配置為Pentium 4 3.0 GHz，512 MB內存，在Windows XP系統下Visual C++編程實現。

實驗1 相似背景下發生遮擋的視頻目標跟蹤

該視頻為一組行人行走視頻序列，視頻中目標與背景顏色十分相似。在第128幀時目標被對面而來的行人遮擋，跟蹤的難度較大。實驗表明，經典MeanShift算法在發生遮擋后( 第140幀)導致目標跟蹤失敗，而改進后的算法卻能很好地抵抗遮擋導致的跟蹤失敗，具有良好的跟蹤效果(圖3)。

視頻序列中，第128幀發生遮擋，到146幀結束。發生遮擋的時候BH系數會降低，在遮擋效果達到最大化的時候BH最小。根據目標模板與跟蹤模板之間的距離定義:d(y)=1-ρ[p(y)，q]，在BH系數達到最小的時候，模板之間的距離最大。當遮擋結束的時候，隨著BH系數的增大，模板之間距離逐漸變小，回到遮擋之前的水平。模板距離如圖4所示。

實驗2 相似背景下發生快速運動的目標跟蹤

該視頻為狼追逐羚羊的一個視頻，視頻中目標與背景顏色十分相似，羚羊的運動速度較快，在第10~101幀的時候，經典MeanShift算法還能夠比較好地跟蹤羚羊，但是到了第104幀，就逐漸出現跟蹤定位不準，最終導致跟蹤丟失，到第106幀的時候已經完全丟失了。改進后的基于空間直方圖的跟蹤算法在第101幀以后也能較好地對目標進行跟蹤，如圖5所示。

該視頻目標跟蹤中的目標與模板的距離參數在0.5上下波動，如圖6所示。

4 結束語

本文提出的基于改進后的顏色直方圖的MeanShift跟蹤方法，考慮了目標邊緣特征點的信息以及像素的空間位置分布信息，相比原來的經典MeanShift跟蹤算法，能夠在比較苛刻的條件下對目標進行更加穩定的跟蹤，能夠滿足實時性的要求。下一步研究的重點是如何對目標顏色進行聚簇分類以忽略小比例顏色對目標直方圖的影響以及如何對多目標進行有效跟蹤。

參考文獻:

[1]FUKANAGA 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[C]//Proc of IEEE International Conference on Computer Vision and Pattern Recognition. Stoughton: Printing House， 2000:142-149.

[4]COMANICIU D， RAMESH V， MEER P. Kernelbased object tracking[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，2003，25(5):564-577.

[5]夏長俊，李翊，顧文錦，等.基于Canny邊緣檢測的MeanShift跟蹤核窗寬確定方法[J]. 海軍航空工程學院學報，2008，23(3):308-314.

[6]文志強，蔡自興.目標跟蹤中巴氏系數誤差的分析及其消除方法[J]. 計算機學報，2008，31(7):1165-1174.

[7]RAO A， SRIHARI R， ZHANG Z. Spatial color histogram for content based retrieval [ C ]//Proc of the 11th IEEE International Conference on Tools with AI.1999:183-186.

[8]CINQUE L， LEVIALDI S， OLSEN K， et al. Colorbased image retrieval using spatialchromatic histogram[C]//Proc of IEEE International Conference on Multimedia Computing and System.1999:969-973.

[9]李培華.一種改進的MeanShift 跟蹤算法[J].自動化學報，2007，33(4):316-348.