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

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

關(guān)鍵詞:目標(biāo)跟蹤; MeanShift跟蹤; 顏色直方圖; 空間顏色直方圖; 相似性度量

中圖分類號:TP391文獻(xiàn)標(biāo)志碼: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 引言

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

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

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

1 經(jīng)典MeanShift跟蹤方法

1.1 目標(biāo)模型描述

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

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

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

相應(yīng)的候選目標(biāo)模型的特征分布表示為

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

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

1.2 基于相似度量函數(shù)的目標(biāo)跟蹤

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

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

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

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

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

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

ρa(bǔ)pprax[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)的第二部分就得取最大值。結(jié)合均值漂移算法計(jì)算步驟，可得MeanShift算法的迭代公式如下:

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

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

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

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

2改進(jìn)的MeanShift算法

2.1 空間顏色直方圖

2.1.1 考慮圖像的邊緣特征

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

設(shè)M為定義的顏色數(shù)目，加入邊緣點(diǎn)特征后將顏色特征點(diǎn)擴(kuò)展到2M個，本文定義從圖像像素這2M個特征空間的函數(shù)如下:

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

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

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

2.1.2 考慮像素坐標(biāo)位置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 色模型及相似性度量

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

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

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

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

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

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

qu(t(x);bu，μu，σu2)與pu(y)之間的相似性根據(jù)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)

所以定義目標(biāo)模型和候選模型的相似度為

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

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

2.3 改進(jìn)后的算法

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

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)可進(jìn)一步化簡為同式(4)的形式。整個跟蹤流程如下:

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

b)選定跟蹤目標(biāo)，通過2.2節(jié)描述的模型計(jì)算其空間—顏色直方圖M，轉(zhuǎn)到步驟c)。

c)取初始目標(biāo)中心為上一幀確定的目標(biāo)中心，設(shè)為y0。轉(zhuǎn)到步驟d)。

d)通過2.2節(jié)描述的模型，計(jì)算中心為y0的候選目標(biāo)的空間—顏色歸一化直方圖p(y0)。計(jì)算M與p(y0)的匹配系數(shù)。轉(zhuǎn)到步驟e)。

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

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

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

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

圖像的采樣速率為30 fps，RGB顏色空間為512。機(jī)器配置為Pentium 4 3.0 GHz，512 MB內(nèi)存，在Windows XP系統(tǒng)下Visual C++編程實(shí)現(xiàn)。

實(shí)驗(yàn)1 相似背景下發(fā)生遮擋的視頻目標(biāo)跟蹤

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

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

實(shí)驗(yàn)2 相似背景下發(fā)生快速運(yùn)動的目標(biāo)跟蹤

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

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

4 結(jié)束語

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

參考文獻(xiàn):

[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]. 海軍航空工程學(xué)院學(xué)報，2008，23(3):308-314.

[6]文志強(qiáng)，蔡自興.目標(biāo)跟蹤中巴氏系數(shù)誤差的分析及其消除方法[J]. 計(jì)算機(jī)學(xué)報，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]李培華.一種改進(jìn)的MeanShift 跟蹤算法[J].自動化學(xué)報，2007，33(4):316-348.