帶寬自適應的Mean Shift目標跟蹤算法*

王年 丁業兵 唐俊 鮑文霞

(安徽大學電子信息工程學院，安徽合肥230039)

運動目標跟蹤廣泛應用于智能人機交互、視頻監控等，在生產生活、工程科學中有重要的研究價值.基于Mean Shift的目標跟蹤算法具有實時性、魯棒性.文獻［1］中將Mean Shift算法應用于圖像平滑和分割.文獻［2］中將Mean Shift算法應用于人臉跟蹤.文獻［3-4］中將Mean Shift算法應用于目標跟蹤領域，通過目標模型和候選模型間的Bhattacharyya系數來度量相似性，最終迭代至極值點.

基于Mean Shift的目標跟蹤算法中，核函數帶寬(即跟蹤窗口大小)決定了參與迭代的樣本數.在跟蹤過程中，如果窗口大小始終不變，那么當目標存在明顯的尺度變化時，就會導致跟蹤產生偏差甚至使目標丟失，因此，自適應調整窗口大小具有重要的意義.文獻［4］中對帶寬進行±10%的增量修正，當Bhattacharyya系數最大時，確定當前幀的帶寬，然而此相似性度量會在小窗口中達到局部最大，因此該方法適用于目標尺寸縮小的情況.文獻［5］中基于尺度空間理論使目標跟蹤的核函數帶寬可以實時變化，但與文獻［4］中方法有類似缺陷，而且計算量大.文獻［6］中提出了一種基于后向跟蹤、形心配準的核窗半徑自動選取算法，但該算法要求運動目標的變化滿足仿射模型，并需要進行形心配準和特征點對的回歸計算.文獻［7］中針對固有的小尺度游蕩和尺度跟蹤滯后問題，修改最優帶寬判別條件，給出了自適應濾波器參數的設計方法.文獻［8］中提出了一種改進的用于更新核函數帶寬的SMD Shift算法.文獻［9］中利用推導的核函數帶寬自動選擇公式進行目標尺度定位.文獻［10］中采用跟蹤窗口內協方差矩陣主分量分析法來計算目標方向和尺寸大小.文獻［11］中根據尺度空間理論提出一種尺度方向自適應Mean Shift跟蹤算法，此算法因計算量大而不能滿足實時性要求，且復雜背景下的目標跟蹤效果不理想.為此，文中提出了自適應調整核函數帶寬的Mean Shift目標跟蹤算法.首先利用目標特征概率投影來創建目標概率密度分布圖，計算其零階矩，再根據零階矩值自適應調整核函數帶寬，經矩運算后用橢圓來鎖定目標.最后通過實驗驗證了算法的有效性和魯棒性.

1 Mean Shift目標跟蹤算法

在視頻起始幀選取感興趣目標進行初始化跟蹤，設目標中心為 x0，像素值為 xi(i=1，2，…，n)，目標特征值為uj(j=1，2，…，m)，目標特征值基于核函數的概率密度為

式中:h為核函數帶寬;δ(xi－uj)用于判斷目標區域中像素值xi是否屬于特征值uj;k(x)為核函數K(x)的剖面函數，距離目標中心越近，像素權值越大.文中采用如下核函數:

假設當前幀以xc為中心，則候選目標特征值基于核函數的概率密度為

相似性函數給出了目標模型和候選模型間的相似程度.理想狀況下兩種模型的概率分布完全一樣.目標跟蹤轉化為在當前幀尋找最優位置點，使得目標模型與候選模型的相似度最大.選擇 Bhattacharyya系數來度量候選模型與目標模型的相似性，定義為

ρ(xc)值越大，模型的相似度越大.在當前幀中ρ(xc)取得最大的候選目標區域就是目標位置.設上一幀目標中心點為x0，將ρ(xc)在x0位置進行泰勒展開:

將式(3)代入式(5)，得

根據核函數密度梯度推導Mean Shift向量，當ρ(xc)取得最大值時，中心點xa為

式中，g(x)是k(x)的負導函數，即g(x)=－k'(x)，其對應的核函數G(x)=g(x2).

最后，通過Mean Shift算法不斷迭代得到最優目標位置點.

2 改進的Mean Shift目標跟蹤算法

2.1 目標概率密度分布

文中采用HSV顏色空間，Cam Shift算法使用HSV顏色空間的H分量創建直方圖目標模型，建立目標概率密度分布圖.Mean Shift目標跟蹤算法將RGB顏色空間均勻剖分為16×16×16直方圖區間［12］.由目標特征值概率在每幀最優位置區域投影創建概率密度分布圖，并將分布點像素值轉換為1～255之間.分布點特征值為

目標概率密度分布圖確定了目標的幾何形狀特性，密度分布塊隨著目標大小、形狀的變化而變化.

2.2 核函數帶寬自適應調整

由Mean Shift算法迭代尋找到最優位置區域，然后計算該區域內的密度零階矩 M00.I(x，y)為(x，y)位置處的概率密度估計值，x和y的變化范圍為搜索窗區域.，窗口寬度為 s=，窗口長度 v=ts，t為初始化跟蹤窗口長寬之比.因而核函數帶寬h為

當目標丟失或完全遮擋后，調整搜索區域為整幅圖像.

用橢圓鎖定待跟蹤目標，橢圓的長軸、短軸及方向角由零階矩、一階矩和二階矩計算獲得.一階矩為

二階矩為

令a=M20/M00－ˉx2，b=2(M11/M00－ˉxˉy)，e=2(M02/M00－ˉy2)，目標方向角θ為長軸與水平方向的夾角，θ=2－1arctan(b/(a－e))，長軸 l和短軸 d分別為

2.3 目標跟蹤算法的步驟

帶寬自適應調整的Mean Shift目標跟蹤算法步驟如下:

1)初始化搜索窗口的大小和位置;

2)計算初始化窗口內目標特征的概率密度估計值;

3)以前一幀中心點x0為中心，計算候選目標特征概率密度估計值;

4)計算權重wi，根據式(7)估計目標的新位置中心點xa;

5)以新位置中心點xa為中心，更新候選目標特征值基于核函數的概率密度估計值;

7)由初始目標特征值概率在最優目標位置區域的投影創建概率密度分布圖;

8)計算概率密度分布圖零階矩M00，調整搜索窗口大小，核函數帶寬h隨之更新，并計算橢圓長軸、短軸和方向角，鎖定目標，轉步驟3).

3 實驗及結果分析

程序在Matlab編程環境下調試.人臉圖像序列為人臉跟蹤專用測試序列圖像，大小為96×128，共500幀.初始化是在第一幀中手工完成的.

圖1 兩種算法對人臉圖像序列的跟蹤結果比較Fig.1 Comparison of tracking results for face image sequence using two algorithms

圖1(a)給出了核函數帶寬自適應調整算法在距離遠近、轉身、旋轉、背景色干擾和外部人臉干擾下的目標人臉跟蹤效果.典型的人臉目標跟蹤幀圖像第30～78幀的測試者由近及遠，人臉窗口大小自適應調整;第80～122幀和第160～260幀的測試者轉身側對和背對攝像機，人臉并不失鎖;第280～360幀有類膚色干擾，且人臉旋轉，光照變化大，橢圓仍然能夠準確鎖定人臉，并隨著人臉的旋轉而相應偏轉;第420～470幀中有另外一位測試者逐漸遮擋了被跟蹤的人臉，橢圓仍能夠準確鎖定人臉.

圖1(b)給出了傳統Mean Shift目標跟蹤算法［2］在相同環境下的跟蹤結果.從圖1可以看出:當目標逐漸縮小時，傳統Mean Shift目標跟蹤算法的跟蹤結果較好，但當目標逐漸增大時，核函數帶寬很難再擴大，因為相似性度量Bhattacharyya系數往往會在較小的跟蹤窗口中達到局部最大;文中算法不僅能夠準確跟蹤目標，而且能夠隨著目標縮放、旋轉自適應調整跟蹤窗口的大小、方向.

圖2給出了傳統Mean Shift目標跟蹤算法和文中算法的跟蹤誤差曲線.從圖2中可見:文中算法的跟蹤誤差較傳統Mean Shift目標跟蹤算法小;統計誤差近似呈高斯分布，故用其作為實驗數據值與真實值之間誤差的參考評估標準.表1給出了這兩種算法的中心點x坐標、y坐標和核函數帶寬的均值及標準差的統計誤差值.從表1中可見，文中算法的跟蹤效果較好.

下面分析兩種算法的計算量.傳統Mean Shift目標跟蹤算法在每幀用3個不同大小的核函數帶寬進行計算，取Bhattacharyya系數最大時對應的核函數帶寬為最佳核函數帶寬，比文中算法多3次Bhattacharyya系數、2次不同大小核窗內像素直方圖的計算，使用了2次雙循環運算.文中算法與傳統Mean Shift目標跟蹤算法相比，在每幀多計算了1次核窗內的概率密度分布，且計算了零階矩、一階矩和二階矩，同樣運用了2次雙循環運算.所以理論上文中算法與傳統Mean Shift目標跟蹤算法的運算量基本相同.

Cam Shift算法使用HSV顏色模型中的H分量直方圖投影創建概率密度分布圖，通過計算概率密度分布質心來定位目標中心點.圖3給出了Cam Shift算法與文中算法對類膚色干擾下的人臉圖像序列的跟蹤結果，由圖3可以看出，整個跟蹤過程中文中算法在類膚色干擾下仍能夠穩定跟蹤人臉，而Cam Shift算法則容易受到相似顏色影響而丟失目標.

圖2 兩種算法對人臉圖像序列的跟蹤誤差曲線Fig.2 Tracking error curves for face image sequence using two algorithms

表1 文中算法與傳統Mean Shift算法對人臉圖像序列的跟蹤誤差比較Table 1 Comparison of tracking errors for face image sequence using the proposed algorithm and the traditional Mean Shift algorithm

圖4顯示了Cam Shift算法和文中算法的跟蹤誤差曲線.從圖4中可見，文中算法的相對誤差較小，跟蹤效果更好.

圖3 兩種算法對類膚色干擾下的人臉圖像序列的跟蹤結果比較Fig.3 Comparison of tracking results for face image sequence in similar color using two algorithms

圖4 文中算法和Cam Shift算法對類膚色干擾下的人臉圖像序列的跟蹤誤差曲線Fig.4 Tracking error curves for face image sequence in similar color using the proposed algorithm and the Cam Shift algorithm

表2給出了兩種算法的中心點坐標和核函數帶寬的算術平均誤差.從表2中可見，文中算法在相似顏色干擾和光照變化等復雜環境下的跟蹤性能要優于Cam Shift算法.

表2 文中算法與Cam Shift算法對人臉圖像序列的跟蹤誤差比較Table 2 Comparison of tracking errors for face image sequence using the proposed algorithm and the Cam Shift algorithm 像素

4 結語

核函數帶寬在Mean Shift目標跟蹤算法中起著至關重要的作用.文中通過計算最優目標位置區域概率密度零階矩來自適應調整核函數帶寬，并經矩運算用橢圓鎖定實時變化的目標.人臉跟蹤實驗表明，文中算法不僅能夠準確跟蹤目標，而且能夠隨著目標縮放、旋轉自適應地調整跟蹤窗口的大小、方向.文中算法尤其適用于跟蹤易于分割的分布塊.

［1］Comaniciu D，Meer P.Mean Shift:a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(5):603-619.

［2］Bradski G R.Real time face and object tracking as a component of a perceptual user interface［C］∥Proceedings of IEEE Workshop on Applications of Computer Vision.Berlin:IEEE，1998:214-219.

［3］Comaniciu D，Ramesh V，Meer P.Real-time tracking of non-rigid objects using Mean Shift［C］∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.SC Hilton Head Island:IEEE，2000:142-149.

［4］Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(5):564-577.

［5］Collins R T.Mean-Shift blob tracking through scale space［C］∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE，2003:234-240.

［6］彭寧嵩，楊杰，劉志，等.Mean-Shift跟蹤算法中核函數窗寬的自動選取［J］.軟件學報，2005，16(9):1542-1550.Peng Ning-song，Yang Jie，Liu Zhi，et al.Automatic selection of kernel-bandwidth for Mean-Shift object tracking［J］.Journal of Software，2005，16(9):1542-1550.

［7］左軍毅，梁彥，趙春暉，等.Mean Shift跟蹤算法中尺度自適應策略的研究［J］.中國圖象圖形學報，2008，13(9):1750-1757.Zuo Jun-yi，Liang Yan，Zhao Chun-hui，et al.Researches on scale adaptation strategy in Mean Shift tracking algorithm ［J］.Journal of Image and Graphics，2008，13(9):1750-1757.

［8］Li Zhi-dong，Chen Jing，Schraudolph N N.An improved Mean-Shift tracker with kernel prediction and scale optimisation targeting for low-frame-rate video tracking［C］∥Proceedings of the 19th International Conference on Pattern Recognition.Florida Tampa:IEEE，2008:1-4.

［9］江焯林，黎紹發，賈西平，等.基于非參數聚類和多尺度圖像的目標跟蹤［J］.華南理工大學學報:自然科學版，2009，37(1):34-41.Jiang Zhuo-lin，Li Shao-fa，Jia Xi-ping，et al.Target tracking based on nonparam etric clustering and multi-scale images［J］.Journal of South China University of Technology:Natural Science Edition，2009，37(1):34-41.

［10］顏佳，吳敏淵，陳淑珍，等.跟蹤窗口自適應的Mean Shift跟蹤 ［J］.光學精密工程，2009，17(10):2606-2610.Yan Jia，Wu Min-yuan，Chen Shu-zhen，et al.Mean Shift tracking with adaptive tracking window ［J］.Optics and Precision Engineering，2009，17(10):2606-2610.

［11］張恒，李立春，于起峰.尺度方向自適應Mean Shift跟蹤算法［J］.光學精密工程，2008，16(6):167-173.Zhang Heng，Li Li-chun，Yu Qi-feng.Scale and direction adaptive Mean Shift tracking algorithm ［J］.Optics and Precision Engineering，2008，16(6):167-173.

［12］李培華.一種改進的Mean Shift跟蹤算法［J］.自動化學報，2007，33(4):347-354.Li Pei-hua.An improved Mean Shift algorithm for object tracking［J］.Acta Automatica Sinica，2007，33(4):347-354.