基于多特征信息和直方圖相交的改進Meanshift算法＊

李暉宙

（海軍工程大學電子工程學院 武漢 430033）

1 引言

近幾年，Mean-Shift算法以其優良的性能在目標跟蹤中得到了很好的應用。然而傳統的Mean-Shift算法存在以下缺點：當目標移動較快時易丟失目標；缺乏目標模型的更新方法；搜索窗口大小固定等等。許多學者和研究人員針對這些缺點進行了許多改進［1，3］。然而無論是最初的Mean-Shift算法還是改進后的 Mean-Shift算法大都采用Bhattacharyya系數或者Ln距離范數作為候選目標模型和目標模型之間的相似性度量。事實上，許多文獻和實踐證明它們并非最有效的比較方法［4］，An［5］證明 Bhattacharyya系數會降低Mean-Shift算法的準確度并建議用直方圖交集（histogram intersection）取代Bhattacharyya系數作為新的相似度度量。然而他并沒有給出優化直方圖交集函數找到最相似的候選目標的方法。

另一方面，大多數基于 Mean-Shift的跟蹤算法僅利用了顏色信息也造成了算法準確度的降低，例如在光照較弱時或者目標和背景顏色接近時等等。眾所周知，人類的視覺系統綜合利用了顏色、紋理、形狀等信息，當某種信息無法單獨完成任務時，其他信息可作為有效的補充。雖然顏色特征在目標跟蹤中起著很重要的作用，但是紋理等其他類型的特征能提供與顏色特征完全不同的信息。將這些信息結合在一起可以提高目標跟蹤的精度，包括顏色與形狀特征的結合［6］，運動信息和顏色信息［7］的結合等等。文獻［8］提出了一種采用聯合直方圖將顏色與紋理特征相結合并融入Mean-Shift算法的目標跟蹤算法，但是他并沒有考慮不同特征之間，甚至同類特征內部不同部分之間對目標和背景不同的區分能力。

本文提出一種自適應地結合顏色和紋理信息，并采用直方圖交集作為相似性度量的目標跟蹤算法。算法首先利用基本的局部二元模式（Local binary pattern，LBP）算子提取目標和候選目標的紋理信息。再用對數比加權直方圖取代傳統直方圖構建目標和候選目標的顏色和紋理模型，以便體現出直方圖中不同bin之間區分目標和背景能力的差異。然后根據場景對兩類不同特征的區分能力進行動態評估，并依據評估結果自適應地融合顏色模型和紋理模型。最后，以直方圖交集作為新的相似性度量并采用Powell方法確定最相似的候選目標的位置作為當前幀中目標位置的估計值。

2 Mean-Shift算法概述

Mean-Shift算法在每一幀中尋找與目標接近且與目標顏色直方圖最相似的區域作為當前幀中目標位置的估計值。它首先在初始幀中通過人工或其他識別算法確定目標窗口并構建目標模型；然后在后續幀中靠近目標窗口的局部鄰域內計算候選目標模型；以Bhattacharyya系數作為度量函數比較兩個模型的相似度，并利用Mean-Shift算法尋找局部鄰域內的最大值點（即最相似點），作為當前幀中目標位置的估計值，同時將該估計值作為下一幀中目標窗口的初始位置開始新一輪的搜索從而實現對目標的連續跟蹤。下面簡要介紹文獻［9］中的算法。

首先，在第一幀中初始化一個包含目標的目標窗口。x0為該窗口的中心，｛xi｝i＝1，…，n表示該窗口中n個像素的位置，則目標模型可表示如下：

其中，q為目標模型，qu為q中第u個特征的概率，m為特征的總數，δ為delta函數，b（xi）的作用是求點xi的特征值，k（x）為核函數，h為核函數的帶寬，C是歸一化常數。

類似地，假設第N幀中候選目標位于以y為中心的搜索窗口內，則候選目標模型可表示為

相似度度量函數ρ［p（y），q］用來衡量候選目標模型與目標模型的相似程度。最常用的相似度度量函數為Bhattacharyya系數：

用y0表示前一幀中目標位置的估計值。將Bhattacharyya系數在y0附近Taylor展開可得：

式中g（x）＝－k′（x），依次迭代，當滿足一定條件時停止迭代，完成目標定位。通過這種方式，候選目標的窗口中心y會逐漸調整到與目標模型最相似的位置。

3 特征提取與目標表示

顏色信息是目前跟蹤算法中最常用的目標特征。傳統的Mean-Shift算法就采用RGB顏色直方圖作為目標的參考模型。Camshift算法則以HSV顏色空間代替RGB空間。本文仍沿用RGB空間，但所描述的算法對顏色空間并沒有特殊要求，可以擴展到其他顏色空間。

許多情況下，僅用顏色信息無法有效地區分背景和目標，例如光照較弱時或者目標和背景顏色接近時等等，這時跟蹤算法的準確度較低甚至丟失目標。如果能結合紋理、形狀等信息可提高目標跟蹤的準確度。常用的紋理算子，如灰度共生矩陣、Gabor濾波器等，由于計算量太大不適宜在實時性要求較高的跟蹤算法中使用。近幾年，LBP算子以其計算簡單，效果好，具有旋轉不變性等優點廣泛應用于紋理特征提取領域。LBP算子通過將局部鄰域內的像素以中心像素為閾值實現二值化，然后將二值化后的像素值乘以相應的像素的權值獲得最后的LBP模式。基本LBP算子的計算方法如下：gc表示鄰域的中心像素（xc，yc）的灰度值，gp表示距離中心半徑為R的圓上P個等間距的像素的灰度值。LBP算子有多種形式，其中一致性模式（Uniform Pattern）應用最廣，它只用少量代表性的模式就可以到達幾乎全部LBP模式集合的描述能力。然而在實驗中，我們發現一致性模式的LBP算子對目標和背景的區分能力并不及原始的LBP算子，因為一致性模式的LBP算子主要考慮信息壓縮的效果，或多或少都喪失了一部分描述物體的能力。

紋理特征提取后，用直方圖來對目標進行建模。傳統的直方圖將特征空間劃分成若干個小的區間（稱為bin），每個bin具有相同的權重，無法反映出不同bin之間不同的區分目標和背景的能力。事實上，那些最能區分目標和背景的bin理所應當被賦予更高的權值。另一方面，許多時候目標和背景混雜在一起無法清晰地分割開來，而 Mean-Shift算法采用矩形窗口對目標和候選目標進行建模，該窗口中不僅包含目標還不可避免地將一部分背景選入其中，導致模型失真。特別是當目標較小時，背景與目標在窗口中所占的比重相當，使得作為目標模型的直方圖中包含大量的背景信息，從而產生錯誤的跟蹤結果。文獻［9］和［12］建議采用比例直方圖，賦予那些主要包含在背景中的bin較低的權值，然而比例直方圖將目標和背景合在一起考慮，并沒有真正反映不同bin區別目標和背景的能力。如圖1所示，虛線框以內為目標，設為100個白色像素，虛線框以外為背景，設為200個白像素和100個黑色像素，根據文獻［9］和［12］，白像素的權值為1／3（即0.25／0.75），而黑像素的權值為1（即0.25／0.25）。因此黑像素在目標模型中的比重提高，事實上恰恰相反黑像素并不屬于目標。

這里我們采用目標背景的對數比來衡量直方圖中各個bin區分目標和背景的能力。顯然，識別一個目標只需要目標與其直接鄰域有較大差別 即 可。設 q＝｛qu｝u＝1，…，m、O＝｛ou｝u＝1，…，m分 別 為 目 標 區 域 和 背 景區域的歸一化直方圖，背景區域一般取目標區域的2～3倍，每個直方圖都包含有m個bin，δ為一個非常小的數，則第u個bin的目標背景對數比為

圖1 比例直方圖錯誤計算權值的實例

4 多特征融合

雖然顏色和紋理信息相結合可以提高算法的準確度，然而許多算法僅僅使用了簡單直接的融合策略。實際上，不同場景中顏色和紋理特征所能具備的區分能力并不相同。因此有必要根據場景自適應地調整它們在融合過程中的比重。

對wC、wT進行歸一化得w′C，w′T。設PT（X）、PC（X）分別為像素X的紋理概率密度函數和顏色概率密度函數，PI（X）為融合后總的概率密度函數，則PI（X）可用PT（X）、PC（X）的加權和來表示：

類似地，基于融合后的概率密度函數的模型相似性度量也可用下式表示：

其中，φ表示候選目標模型與目標模型之間的相似度度量函數，如Bhattacharyya系數，直方圖交集等等，φC，φT分別為從紋理和顏色特征獲得的模型相似度，φI為最終的候選目標模型與目標模型之間的相似度。

5 目標定位

然而，直方圖交集函數與Bhattacharyya系數和Ln范數有很大差別。前者是不可微函數，而后兩者是可微函數，相比而言后者更容易通過求導或求梯度獲得函數的最優值，而獲得直方圖交集的最優值則相對較難一些，這也是許多基于Mean-Shift的算法并沒有選用直方圖交集作為相似度函數的一個重要原因。Powell方法是一種快速有效且無需求導的局部尋優方法，非常適合無法求導的直方圖交集函數。不過Powell方法易受初始點的影響，因此采用兩步求取直方圖交集的極值：首先利用 Mean-Shift算法求取Bhattacharyya系數的局部最優點作為Powell方法的初始點，再用Powell方法求取直方圖交集的最優解作為當前幀中目標位置的估計值。

5.1 確定目標的初略位置

如第4節所述，候選目標模型與目標模型之間最終的相似度可表示為紋理模型相似度和顏色模型相似度的線性組合。將式（3）代入式（11）中的φ，可得：

大多數基于 Mean-Shift的算法都以Bhattacharyya系數或Ln范數作為候選目標模型與目標模型之間的相似性度量函數。然而它們并不是比較兩個直方圖最有效的方法，許多文獻都表明直方圖交集能給出更好的比較結果。假設I、M是兩個含有n個bin的直方圖，則它們之間的相交距離表示為

5.2 最優化直方圖交集

Powell算法實質上是一種不計算導數和梯度的共軛方向法。對于n維極值問題，它首先沿著n個坐標方向求極小，經多n次之后得到n個共軛方向，然后沿n個共軛方向求極小，經過多次迭代后便可求得極小值。將式（12）代入式（14）中的φ，可得融合后的直方圖交集，并以其作為Powell算法的待優化函數：

HIC（p（y），q）是候選目標顏色模型和目標顏色模型的相交距離，HIT（p（y），q）則是相應的紋理模型的相交距離，融合后的相交距離用 HI（p（y），q）表示。同時以5.1節中所求得的y＊作為Powell方法的初始點以減小初始點對Powell方法的影響。可利用Powell方法的迭代尋優過程獲得－HI（p（y），q）的局部極小值，亦即找到最相似的候選目標的位置作為當前幀中目標位置的估計值。

直方圖交集最優化方法

1）初始化i＝0，令搜索方向uk為單位向量，uk＝ekk＝1，…，N。

2）設置L0＝xi。

3）對于k＝1，…，N，尋找最小化－HI（p（Lk－1＋αk），q）的αk，并設置Lk＝Lk－1＋αk。

4）令i＝i＋1。

5）對于j＝1，…，N－1，設置uj＝uj＋1，uN＝LN－L0。

6）尋找最小化－HI（p（L0＋αuN），q）的α，并令xi＝L0＋αuN。

7）重復步驟2）至步驟6）直至算法收斂。

6 實驗結果

本節以三個跟蹤實例展示本文算法的有效性。所得的跟蹤結果將和文獻［9］中基本的 Mean-Shift算法以及文獻［12］中基于比例直方圖的Mean-Shift算法所得的結果進行比較，以下分別稱為方法1和方法2。實驗在AMD Sempren 1.81GHz的CPU，1GB內存配置的電腦上，在 Windows XP系統下用VC6.0編程實現。三個實例中的所有幀都轉換為灰度圖像。

實例1是一段包含一輛運動汽車的視頻。跟蹤的目標是汽車的左前輪。如圖2所示，由于場景比較簡單，三種方法都取得了較好的跟蹤結果。然而與其他兩種方法相比，本文算法的跟蹤準確度更高。

實例2是跟蹤一名穿著白色T恤的行人。與實例1相比，由于目標和周圍環境有一定的相似度使得跟蹤難度加大。如圖3所示，無論是方法1還是方法2從第7幀開始都丟失了目標，主要是因為在目標附近有一輛和目標顏色近似的汽車影響了跟蹤效果，然而本文算法由于引入了紋理特征依然能較好地跟蹤目標。

第3個實例是一段紅外視頻，與可見光圖像相比，紅外圖像中的目標更為模糊，顏色信息的有效性大打折扣。在本實例中是跟蹤一輛運動中的坦克。如圖4所示，由于顏色特征無法提供足夠的信息區分目標和背景致使方法1和方法2都收斂到了一個錯誤的位置。另外，正如第2節所述，該目標體積較小導致目標模型中背景與目標比例相當造成目標模型失真，也是算法準確性降低的原因之一。

圖2 跟蹤汽車左前輪的結果。第一行為文獻［9］的跟蹤結果，第二行為文獻［12］的跟蹤結果，第三行為本算法的跟蹤結果

圖3 跟蹤行人的結果。第一行為文獻［9］的跟蹤結果，第二行為文獻［12］的跟蹤結果，第三行為本算法的跟蹤結果

圖4 紅外圖像序列中跟蹤坦克的結果。第一行為文獻［9］的結果，第二行為文獻［12］的結果，第三行為本算法的結果

表1給出了以像素為單位的各種方法的平均定位誤差和方差，其中目標的真實位置通過手工確定。如表1所示，在三個實例中，本文算法都取得了最小的定位誤差和方差。

表1 三種方法的定位誤差和方差

7 結語

本文提出了一種結合顏色和紋理信息并以直方圖交集為相似性度量的擴展Mean-Shift算法。采用對數比加權直方圖代替傳統直方圖構建目標和候選目標模型有效地體現了直方圖內各bin之間不同的區分能力。通過自適應的方式結合顏色和紋理信息提高了Mean-Shift算法在復雜情況下跟蹤目標的能力。基于Powell方法的兩步直方圖交集優化過程使得算法能更準確的跟蹤目標。實驗證明該算法比基本的Mean-Shift算法和基于比例直方圖的Mean-Shift算法具有更好的準確性和魯棒性。

［1］WANG Jun-qiu，Yasushi Yagi.Adaptive Mean-Shift Tracking with auxiliary Particles［J］.IEEE Transactions on System，Man，and Cybernetics，Part B：Cybernetics，2009，39（6）：1578-1589.

［2］CHEN Xiao-peng，ZHOU you-xue，HUANG Xiao-san，et al.A-daptive Bandwidth Mean Shift Object Tracking［C］／／Proceedings of the 2008IEEE Conference on Robotics，Automation and Mechatronics，2008：1011-1017.

［3］Leichter I，Lindenbaum M，Rivlin E.Mean Shift tracking with multiple reference color histograms［J］.Computer Vision and Image Understanding，2010，114（3）：400-408.

［4］Swain M J，Ballard D H.Color indexing［J］.International Journal of Computer Vision，1991，7（1）：11-32.

［5］AN Guo-cheng，ZHANG Feng－jun，DAI Guo-zhong.Mean Shift using novel weight computation and model update［C］／／Proceedings of the 2010IEEE Conference on Acoustics，Speech，and Signal Processing，2010：706-709.

［6］WANG Jun-qiu，Yasushi Yagi.Integrating Shape and Color Features for Adaptive Real-time Object Tracking［J］.IEEE Transactions on Image Processing，2008，17（2）：235-240.

［7］LIU Hong，Yu Ze，ZHA Hong-bin，et al.Robust human tracking based on multi-cue integration and mean-shift［J］.Pattern Recognition Letters，2009，30（9）：827-837.

［8］NING Ji-feng，ZHANG Lei，ZHANG D.Robust object tracking using joint color-texture histogram［J］.International Journal of Pattern Recognition and Artificial Intelligence，2009，23（7）：1245-1263.

［9］Comaniciu D，RameshV，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-575.

［10］Comaniciu D，Meer P.Mean shift：a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2002，24（5）：603-619.

［11］M?enp??T，Ojala T，Pietik?inen M，et al.Robust texture classification by subsets of local binary patterns［C］／／Proceedings of 15th International Conference on Pattern Recognition，2000：947-950.

［12］Allen J G，Xu R Y D，Jin J S.Object Tracking Using CamShift Algorithm and Multiple Quantized Feature Spaces［C］／／Proceedings of the Pan-Sydney Area Workshop on Visual Information Processing，2004：3-7.