一種新的基于分塊直方圖的Mean－Shift跟蹤算法

李群山，張 文

（1.電子科技大學光電信息學院，四川成都610054;2.內江師范學院工程技術學院，四川內江 641112）

目標跟蹤是計算機視覺和圖像處理研究中的一個重要課題，其廣泛應用于智能視頻監控、軍事制導、智能機器人等視覺應用領域［1-2］。目標的顏色直方圖具有特征穩定、抗部分遮擋、計算方法簡單和計算量小的特點，基于Mean-Shift的跟蹤一般采用直方圖對目標進行建模，然后通過相似度度量，最終實現目標的匹配和跟蹤［1］。

均值漂移算法（Mean-Shift）是一種基于密度梯度上升的非參數方法，通過較少的幾次迭代運算就能找到目標位置。這種算法計算量小、計算速度快，體現出良好的實時性和穩定性，適用于實時視頻的目標跟蹤。經典的Mean-Shift跟蹤算法用于目標建模的顏色直方圖只是包含了顏色特征在目標中出現的概率信息，沒有融入目標的空間信息［3-7］。梁靜等人利用kalman濾波器和Mean-Shift相結合的方法跟蹤動態背景下的運動目標，解決了目標被部分遮擋的情況［8-11］。

目標的顏色通常分布在顏色空間的一個子空間，傳統的顏色直方圖通常將顏色空間均勻劃分（例如16×16×16或者32×32×32），這樣容易造成大量的空的顏色直方圖區間，不僅浪費內存空間，而且還增加了計算量。針對傳統顏色直方圖空閑率高，本文提出了簡化顏色直方圖的方法，針對傳統顏色直方圖沒有融入空間信息的缺點，提出了一種新的分塊直方圖構建方法，這種分塊直方圖構建方法簡單，而且保留了顏色直方圖的尺度和旋轉變化的不變性。

1 經典Mean-Shift算法

1.1 目標模型

設{xi}，i=1，2，…，n表示目標區域歸一化的n個像素集，x0為目標區域的中心像素點。將顏色特征空間劃分成u=1，2，…，m個子空間，也就是直方圖上的m個bin。每個特征u=1，2，…，m在目標區域的概率值為

假設候選目標模型的在t時刻的中心位置為y;{xi}，i=1，2，…，Nb表示候選目標區域的像素集，則相應候選目標模型在特征值u=1，2，…，m出現的概率可以表示為

1.2 相似性度量

經典的Mean-Shift使用Bhattacharry系數度量目標模型與候選目標模型（y）之間的相似性。相似性定義為

跟蹤過程就是不斷獲得與目標模型相似性最大的候選模型的過程，即求取式（3）最大值的過程。為求式（3）的最大值，令式（3）在（y0）處進行Taylor式展開，并省略一些極小項，得

將式（2）代入式（4）得

要使式（3）最大也就是要使得式（5）最大，而式（5）的第一項為常量，則第二項最大時式（5）最大。結合Mean-Shift算法，得迭代公式為

式中，g（x）=－K'（x）。如果使用Epanechniko核函數，則（7）式進一步簡化為

Mean-Shift算法的計算步驟:首先初始化y0，可令y0為最初的目標中心;然后用式（6）計算wi，并利用式（7）計算獲得下一次迭代的位置;令y0=y1，進行下一次迭代運算，如此不斷地迭代計算式（6），（7），直到‖yi+1－yi‖ ＜ε，或達到最大迭代次數。最終由式（7）得到的位置就是目標的準確位置。

2 改進的Mean-Shift算法

2.1 目標顏色直方圖的簡化

在建立目標顏色直方圖之前通常需要將顏色空間進行量化，目前一般采用均勻量化顏色空間的方法，這樣可以減少計算量。但是目標顏色通常緊湊分布在顏色空間的一部分子空間中，因而會造成大量空的顏色直方圖區間，或者取值極小的顏色直方圖區間。這樣不僅會浪費大量的內存空間，而且增加計算量。例如:圖1是經常遇到的人臉跟蹤目標，其顏色直方圖在16×16×16均勻量化的RGB顏色空間中，空的直方圖區間達到3 878個，空閑率達3 878/4 096=94.7%。若為這些空的直方圖區間分配內存空間，按存儲類型為雙精度浮點型（8 byte）計算將是31 024 byte。若是在32×32×32量化空間，則空區間為32 550，空閑率達=32 550/32 768=99.3%，浪費的內存空間將是260 400 byte。圖2（圖2～圖11彩色圖見網址:http://blog.sina.com.cn/s/blog_b9be7b8501017gyc.html）色彩如此豐富，其在16×16×16均勻量化的RGB顏色空間中空的直方圖區間也達3 400個，空閑率為3 400/4 096=83%。而且在跟蹤過程中計算Bhattacharry系數時，為其還要付出一定的計算代價。

針對顏色直方圖空閑率非常高的情況，本文提出簡化顏色直方圖的方法，得到沒有空閑區間的直方圖;同時為了應對在計算候選目標顏色直方圖時會出現不同于初始跟蹤目標顏色特征的像素的情況，在簡化的顏色直方圖后增加一個區間用于累積非初始跟蹤目標顏色特征的像素。其計算步驟如下:

1）按照傳統方法統計得到顏色直方圖，并去除空直方圖區間。

2）保存剩下的顏色直方圖區間對應的顏色特征值。

3）在經過上面處理后的直方后增加一個區間，用于累積候選目標中出現的非初始目標顏色特征的像素。在初始目標的直方圖中該區間的值為0，在候選目標的直方圖中該區間的值為所有不屬于初始目標顏色特征的像素總和歸一化后的值。

2.2 空間顏色直方圖的建立

假設某目標Q的大小為N（即總像素點），f（x，y）是該目標中的一點，f（x，y）表示目標在該點的顏色值，（x，y）表示該點的坐標，則其質心為

該目標中離該質心（x0，y0）最大的距離為

圖3 圖像空間劃分示意圖

最后，根據前面顏色空間量化結果得到的m個顏色子特征空間，分別計算每個圓環區域內的傳統顏色直方圖，得到最終的分塊顏色直方圖。其中第v個子空間的第u個顏色特征值為

式中:a（xi）表示該像素距離質心的量化空間距離;δ［a（xi）－v］是Kronecker delta函數，當該像素屬于第v個空間圓環時，函數值為1，否則為0。其他參數與傳統顏色直方圖相同。于是，目標模型可表示為:q={quv}，u=1，2，…，m;v=1，2，…，w 。這樣得到的分塊顏色直方圖具有以往分塊直方圖不具有的尺度、旋轉不變性。

2.3 新分塊直方圖與傳統顏色直方圖的比較

為了驗證新分塊直方圖的優點，下面對兩個顏色分布相似物體的傳統顏色直方圖與新顏色空間直方圖進行比較，來驗證新分塊直方圖具有更好地區分顏色分布相似目標的優點。圖4、圖5表示顏色分布相似的兩個目標;圖6、圖7分別是圖4、圖5的傳統顏色直方圖;圖8、圖9分別是圖4、圖5的分塊顏色直方圖。為了顯示方便，以下的顏色直方圖在HSV顏色空間統計得到，歸一化系數為直方圖中區間值的最大值，分塊顏色直方圖的圓環數僅為3個。

利用Bhattacharry系數度量圖6與圖7之間的相似程度為0.98，而圖8與圖9之間的相似程度僅為0.80。可以看出新顏色直方圖有更好地區分顏色分布相似目標的能力。為了加大區分度可增加分塊的圓環數。

2.4 改進后的Mean-Shift算法

根據分塊直方圖的計算方法不同，改進后的Mean-Shift算法的Bhattacharry系數計算式為

將式（11）代入式（12）整理得

Meanshift算法的其他計算公式不變。

3 實驗結果

本文的所有實驗在VS2008環境下及利用OpenCV完成，主機主頻1.9 GHz，內存1 Gbyte。在RGB顏色空間計算顏色直方圖，顏色空間量化為16×16×16的子空間，目標的初始化手動完成，真值的標注也由手動完成。為了適應尺度的變化，進行增量正負10%的核窗寬調整。

3.1 實驗一

實驗視頻在辦公室環境拍攝，為了構造顏色分布相似的目標，實驗中利用魔方作為跟蹤對象。視頻圖像大小為640×480。實驗視頻拍攝的是魔方的變速運動及尺度變化的情形。實驗結果如圖10所示。跟蹤目標在X，Y坐標軸上的誤差統計結果如圖11所示。實驗畫面中的紅色框為改進后算法跟蹤結果，白色框為經典Mean-Shift算法跟蹤結果。

分析圖10和圖11可看出改進后的Mean-Shift算法比經典算法跟蹤目標更加準確，主要原因是分塊直方圖中融入了空間信息，使其描述目標的能力比傳統顏色直方圖更準確。

3.2 實驗二

實驗所用視頻拍攝的是兩個顏色分布相似魔方存在遮擋的情形。其中一個魔方靜止，另一個魔方運動。圖12的跟蹤試驗中，跟蹤的目標為運動的魔方，運動魔方逐漸運動到靜止魔方背后被遮擋的情形。圖13的跟蹤實驗中，跟蹤目標是靜止魔方，在實驗中逐漸被運動魔方遮擋的情形。實驗畫面中的紅色框為改進Mean-Shift算法跟蹤結果，白色框為經典Mean-Shift算法跟蹤結果。

在圖12實驗中，在運動魔方被靜止魔方遮擋后再從靜止魔方后面運動出來時，白色框（經典Mean-Shift算法跟蹤結果）跟蹤丟失，停留在靜止魔方上;而紅色框（改進Mean-Shift算法跟蹤結果）卻能正確地進行跟蹤。

圖12 運動目標被遮擋跟蹤實驗

圖13 靜止目標被遮擋跟蹤實驗

在圖13實驗中，運動魔方逐漸從靜止魔方前面經過，并完全遮擋了后面靜止的魔方，隨著運動的進行，當被遮擋的靜止魔方逐漸顯現出來時，白色框（經典Mean-Shift算法跟蹤結果）跟蹤丟失，跟蹤到顏色相似的運動魔方上;而紅色框（改進Mean-Shift算法跟蹤結果）卻能停留在了靜止魔方上，表示跟蹤正確。

4 結語

本文針對顏色直方圖空閑率高造成的內存空間的浪費問題提出了一種簡化顏色直方圖的計算方法，并提出了一種新的分塊顏色直方圖的構造方法。實驗結果表明基于新的分塊直方圖的Mean-Shift跟蹤算法比經典的Mean-Shift算法具有更好的跟蹤穩定性，在跟蹤顏色分布相似的目標方面，特別是在相似目標出現大部分遮擋情況下仍能穩定地跟蹤目標，與經典Mean-Shift算法相比具有更穩定的效果。

：

［1］宋新，沈振康，王平，等.Mean-Shift在目標跟蹤中的應用［J］.系統工程與電子技術，2007，29（9）:1405-1409.

［2］李培華.一種改進的Mean-Shift跟蹤算法［J］.自動化學報，2007，33（4）:347-354.

［3］FUKUNAGA K，HOSTETLER L.Estimation of the gradient of a density function and its applications in pattern recognition［J］.IEEE Trans.Information Theory，1975，21（1）:32-40.

［4］CHENG Yizong.Mean shift，mode seeking，and clustering［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，1995，17（8）:790-799.

［5］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2002，24（5）:603-619.

［6］COMANICIU D，RAMESH V，MEER P.Kernel-based object tracking［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2003，25（5）:564-577.

［7］COMANICIU D，RAMESH V，MEET P.Real-time tracking of non-rigid objects using mean shift［C］//Proc.IEEE Conference on Computer Vision and Pattern Recogniton，2000.［S.l.］:IEEE Press，2000:142-149.

［8］YILMAZ A，SHAFIQUE K，SHAH M.Target tracking in airborne forward looking infrared imagery［J］.Image and Vision Computing，2003（21）:623-635.

［9］BIRCHFIELD S T，RANGARAJAN S.Spatiograms versus histograms for region-based tracking［C］//Proc.Computer Vision and Pattern Recognition，2005.［S.l.］:IEEE Press，2005:1158-1163.

［10］袁光林，薛模根，謝愷，等.多顏色直方圖自適應組合mean shift跟蹤［J］.中國圖象圖形學報，2011，16（10）:1832-1840.

［11］梁靜，支琤，周軍.基于mean shift的抗遮擋運動目標跟蹤算法［J］.電視技術，2008，32（12）:82-85.