基于三維直方圖的改進Camshift目標跟蹤算法

摘 要： 經典的連續自適應均值漂移算法Camshift通過HSV空間的色調Hue分量建立一維直方圖，在有光照變化及有相似顏色目標或背景的干擾下，跟蹤效果不好。提出一種融合HSV空間中色調、飽和度以及反應物體形狀信息的邊緣梯度的三維直方圖特征，并基于背景模型自適應調整特征直方圖三種分量的權重值，提高了算法的跟蹤準確度。通過與傳統Camshift跟蹤實驗比較，提出的改進算法在光照變化及相似顏色目標/背景干擾下具有更好的魯棒性，同樣也滿足跟蹤系統的實時性要求。

關鍵詞： 目標跟蹤； Camshift算法； 邊緣梯度； 三維直方圖

中圖分類號： TN919?34； TP391.4 文獻標識碼： A 文章編號： 1004?373X（2014）02?0029?05

0 引 言

目標的檢測與跟蹤是計算機視覺與模式識別領域一個非?；钴S的課題，也是智能視頻監控及機器人自動導航等領域的核心問題。在目前已經提出的各種目標跟蹤算法中，Meanshift算法由于其計算簡單以及良好的實時性而得到廣泛的應用。

Camshift跟蹤算法是對Meanshift的改進，它是由Gray R.Bradski等提出的自適應縮放跟蹤模板尺寸的算法[1]。兩種算法本質上都是爬山算法，即在一種數據的密度分布中通過反復迭代而尋找出局部極值穩定的方法。

傳統的Camshift算法對于光照的變化以及在前景與背景顏色相似的條件下，跟蹤效果并不理想。對此不少學者在Camshift算法中引入其他特征目標模型，如貝葉斯概率框架[2?4]，但由于貝葉斯概率框架等模型固有的計算復雜度，難以實現跟蹤的實時性。

考慮到傳統的Camshift算法僅引入了HSV空間中的色調Hue分量來建立直方圖，從而導致顏色背景相似情形下跟蹤效果變差這一事實，本文提出增加顏色空間的S分量以及邊緣輪廓的形狀信息建立三維聯合直方圖，以彌補在某些情況下只依靠色調來描述目標特征的不足。

由于該算法主要在目標的直方圖統計特征上進行改進，沒有涉及到復雜的計算操作，所以效率較高，在穩定性提高的同時易滿足實時性的要求。

1 三維特征分量提取

1.1 Hue與Saturation分量

傳統Camshift使用HSV空間中的色調Hue通道建立直方圖，以致在飽和度S或亮度V變化較大的情形下，其跟蹤靈敏度明顯降低[5]。本實驗首先把RGB顏色空間圖像轉換為HSV顏色空間圖像，如圖1（a），（b）所示，并提取H與S兩個通道的分量[6]：[H=0， if max=min（60°×g-bmax-min+360°）mod360°， if max=r60°×b-rmax-min+120°， if max=g60°×r-gmax-min+240°， if max=b] （1）

[S=0， if max=0max-minmax=1-minmax， otherwise] （2）

[V=max] （3）

式中：設max等于r， g和b中的最大者；min等于這些值中的最小者。所提取的H與S兩個通道的分量如圖1（c），（d）所示。

在傳統的Camshift算法中，對于Hue通道采用均勻量化以建立直方圖模型。計算初始化的搜索窗口內H分量的直方圖，對初始搜索窗口中每個像素的H通道值進行采樣（如圖2（a）藍色方框所示），從而得到待跟蹤目標的色調（Hue）直方圖，將該直方圖保存下來作為目標的顏色直方圖模型，如圖2（b）所示。本文提取H與S兩通道，在量化HSV圖像各通道的位數深度時，類似3通道8位的RGB圖像每通道均占8 b為 0～255共256等級，H和S通道也都分配為8位深度。H分量的值域范圍是[[0，360°]]，S分量的值域范圍是[0，1]，本實驗中將H分量的值域范圍量化為30個bin （量化長度為[12°]），將S分量的值域范圍量化為16個bin （其中量化長度為[116）]。

圖2 色調H分量的一維直方圖

對于初始化窗口區域的二維直方圖的構成，可以看作由H分量與S分量聯合而成的二維分布函數，如圖3所示。

圖4的示意說明了一維直方圖與二維直方圖之間的關系，其中一維H直方圖量化為6個bin，二維H?S聯合直方圖量化為6×5共30個bin，并且一維Hue通道直方圖相當于其邊緣分布函數。在本文實驗中，實際采用的H?S二維直方圖共30（色調）×16（飽和度）=480個bin。

1.2 邊緣梯度方向分量

對于框定的初始化目標跟蹤區域進行RGB到灰度圖轉化，然后對該灰度圖進行Canny邊緣檢測。再利用形態學方法先腐蝕后膨脹處理，將圖中細小瑣碎的邊緣點與噪聲刪除，找到最主要的顯著邊緣輪廓。假設待跟蹤目標的檢測結果較為準確，采用Canny算子即可提取到較連續的顯著輪廓邊緣，如圖5所示。

對于所有的邊緣像素點，其梯度向量的定義為：

[G（i，j）=GxGy=?x?f?y?f] （4）

利用邊緣像素點的梯度方向統計信息，可建立基于邊緣梯度方向直方圖[7]。實驗中計算梯度向量時選用Sobel算子，其可采用如下兩個方向模板卷積計算得到：

[Mx=-101-202-101， My=121000-1-2-1] （5）

式中Mx與My為Sobel算子的水平與豎直模板矩陣，分別用于檢測水平邊緣與豎直邊緣。若邊緣上位于（i，j）處的像素點P的鄰域灰度矩陣標記為：

[P=a0a1a2a3（i，j）a4a5a6a7] （6）

則該點的梯度向量G的水平與豎直分量值Gx和Gy分別為：

[Gx=（a2+2a4+a7）-（a0+2a3+a5）Gy=（a0+2a1+a2）-（a5+2a6+a7）] （7）

該點梯度向量的方向z由水平方向梯度分量值與豎直方向梯度分量值的反正切函數表示為：

[z=arctanGxGy] （8）

對目標邊緣的所有的像素點的梯度方向進行統計，可建立基于邊緣梯度方向統計分布的目標形狀特征模型。圖6為基于邊緣梯度方向的一維直方圖。其中，梯度方向的值域范圍是[[0，2π）]，將其量化為16個bin（量化長度為[π8]）。

2 基于三維特征直方圖的改進Camshift算法

2.1 權重選擇與直方圖修正

2.1.1 特征權重的選擇

H?S?Grad三維聯合直方圖的構成類似H?S二維直方圖。在初始化區域內統計每個像素點信息，建立一個30（色調）×16（飽和度）×16（邊緣梯度方向）共7 680個bin的三維直方圖。

為了減少背景干擾，本文自適應減少目標特征直方圖中與背景特征直方圖相接近的直方圖分量的權重，采用目標特征直方圖分量自適應加權[8]策略，引入背景直方圖，其定義仍為色調×飽和度×邊緣梯度方向的共7 680個bin的三維直方圖，該背景直方圖每個bin值為：

[b=bi， i=1，2，…，7 680，且i=17 680bi=1] （9）

將背景直方圖的bi集合中最小的非零值記為bmin，則其對應的目標直方圖hi的特征權重為：

[wi=min{bminbi，1}， i=1，2，…，7 680] （10）

考慮到目標窗口的特征直方圖，當其某個bin分量與背景對應的bin分量近似一致時，該bin分量在目標特征直方圖中的使用會造成對目標跟蹤準確性的不良影響，因此應該適當降低其權重值。相應地，對于背景特征直方圖中某個取值較大的bin分量，即bi越大，其在對應目標特征直方圖hi中的權重應較小，即其對應的hi的權重wi越小。以特征權重值wi去加權目標窗口的直方圖hi，從而可進行自適應的調整：

[hi=hiwi， i=1，2，…，7 680] （11）

2.1.2 直方圖的更新修正

目標直方圖由于光照變化影響需要進行修正更新，根據對每次漂移前后窗口的直方圖H1與H2 的Bhattacharyya距離（也稱巴氏距離）[8?9]的比較：

[dBhattacharyya（H1，H2）=1-iH1（i）-H2（i）iH1（i）?2H2（i）] （12）

若巴氏距離d=0表示直方圖完全相同，d=1表示完全不相同。如果漂移前后H1與H2巴氏距離小于0.4，則動態修正H2如下：

[H2=H1α1+H2α2+H3α3] （13）

式中：H1表示漂移前直方圖；H2表示漂移后直方圖；H3表示初始化窗口的直方圖，系數權重按照統計實驗經驗取值為：

[α1=0.022 5， α2=0.95， α3=0.027 5] （14）

由此，每次漂移后的直方圖H2會受到漂移前和最初始的直方圖兩者的約束修正?？梢钥闯觯思s束主要由漂移后直方圖H2決定，其貢獻為95%。通過此修正更新的方式可以保證跟蹤所用直方圖在光照突變時不至于發生劇烈的偏離改變。

2.2 概率反向投影與均值漂移

反向投影過程先利用第2.1節得到的直方圖計算整張圖像關于該搜索窗口內三種特征出現的概率分布。例如，在整幅圖中某個像素點[H，S，Grad]分量值為[32，36，0.1]，而在上面所得到直方圖中查詢到該bin所占的比例為4%，那么就將該像素點的值置為0.04。這樣對于整幅圖像所有像素一一對應查詢賦值，便得到了整張圖像的反向投影圖，即二維的概率分布圖。

然后把反向投影圖轉為用8位灰度圖表示。概率為1的位置值為255，概率為0的灰度值為0，概率介于1和0之間的灰度值介于255和0之間，如圖7所示。經過反向投影，圖像中每一個像素的值就變成了三種特征信息出現在此處的離散化概率度量：出現的可能性越大，像素的值就越大，反之就越小。相應地，投影圖中對應為：越亮的像素表明該像素為目標像素的概率越大。這樣就為下一步的質心計算提供了依據。

計算搜索窗口的質心時，其“質心”就類似物理計算質量分布不均勻的二維平板的重心，只不過這里各點的“面密度” 就是灰度圖中各像素點的概率取值。設（x，y）為搜索窗口中的像素點，I（x，y）是反向投影圖中對應（x，y）點的像素值。定義搜索窗口的零階矩[M00]和一階矩[M10]，[M01]如下[10]：

[M00=xyI（x，y）] （15）

[M10=xyxI（x，y）] （16）

[M01=xyyI（x，y）] （17）

則當前搜索窗口的質心位置為：

[（xC，yC）=M10M00，M01M00] （18）

接下來，將搜索窗口的中心移動到質心。顯然，隨著窗口的移動，窗口的內容也發生了變化。于是取移動窗口反復迭代計算質心，直到窗口中心與質心間的移動距離小于預設的固定閾值或迭代次數達到某一上限值時，認為質心坐標滿足收斂條件。

2.3 Camshift窗口縮放

在做均值漂移之后，再進行Camshift窗口大小縮放。由于窗口中心已經移到了正確的質心位置。此時，對該窗口采取如下縮放策略：

首先，將窗口朝上下左右四個方向各擴增10個像素，得到一個新窗口。

然后，計算該新窗口的零階矩[M00]，一階矩[M10，][M01]，二階矩[M20]，[M02]，[M11]。記：

[a=M20M00] （19）

[b=M11M00] （20）

[c=M02M00] （21）

則旋轉角度為：

[θ=arctan2ba-c+4b2+（a-c）2] （22）

下一幀所用新的搜索窗口的長和寬分別為：

[length=4cos2θM20+2cosθsinθM11+sin2θM02M00] （23）

[width=4sin2θM20-2cosθsinθM11+cos2θM02M00] （24）

如果length

3 實驗結果分析

本文實驗采用VisualStudio 2010及OpenCV 2.3開發軟件平臺。實驗1的場景較為簡單，背景顏色與目標區分明顯。主要測試在光照改變及有相似顏色干擾目標或背景的條件下，只基于色調分量的經典Camshift算法與改進后的基于多特征直方圖的Camshift的性能比較。實驗中待跟蹤目標逐漸接近顏色相近的干擾目標，且在最后光照強度發生突變。

在圖8（a）與圖9（a）中顯示了經典Camshift算法的跟蹤效果，從左至右可見，當目標與背景顏色對比度較高時其跟蹤效果還不錯，但是當目標接近顏色相似的干擾目標時，Camshift窗口擴大至包含非目標的錯誤區域，準確性偏低。這正是由于其僅依靠色調Hue單個信息通道導致無法準確描述目標特征。

圖8（b）與圖9（b）為使用添加飽和度S分量后的二維特征直方圖的跟蹤效果?？梢钥闯?，其對于不同的色調與飽和度顏色信息有一定的區分度。但是當最后改變光照時，其仍然受到顯著影響而出現誤跟蹤現象。這主要是由于H分量與S分量均屬顏色空間信息，對光照條件的改變較為敏感以及易受相似顏色干擾物的影響。

圖8（c）與圖9（c）是進一步添加了目標的邊緣梯度方向而改進的三維特征Camshift跟蹤效果。由于邊緣梯度方向的統計分布實質描述了目標的形狀信息，在最后光照強度改變時，形狀信息的權重值會因與背景形狀信息差別顯著而相應增加，提高了跟蹤算法在光照變化下的抗干擾性。在整個算法的運行過程中，目標物始終被準確跟蹤，如圖8（c）與圖9（c）所示。

這主要得益于其引入的形狀信息及增強的顏色描述信息，使得跟蹤算法對于有相似顏色物干擾及光照改變都具有較好的魯棒性。由圖10可見，傳統的僅基于Hue通道的Camshift對于低對比度背景、背景與目標顏色非常接近的環境幾乎無能為力，跟蹤無法穩定進行。從反向投影圖可以明顯地看出，Camshift認為幾乎整個背景都是前景目標，這主要是由于前景背景顏色非常接近，僅依靠色調單通道信息無法區分背景與目標。

圖11中，改進的Camshift基本保持了穩定的跟蹤，尤其從圖11（b）的反向投影圖中可以看出，此時并未出現Camshift誤認為整個背景都是目標的情況發生。此時，由于背景與目標顏色比較接近，所以顏色特征直方圖的權重值被抑制得比較小，跟蹤的實現主要依靠于邊緣梯度方向直方圖提供的目標形狀信息。

4 結 語

Camshift算法的核心是利用建立的目標統計特征直方圖進行反向投影，從而均值漂移以跟蹤上目標。傳統的Camshift僅依靠單一的色調Hue通道建立一維直方圖，對于光照改變及常見的相近顏色背景或干擾目標往往跟蹤效果不理想。為此本文引入了飽和度與邊緣梯度方向兩個特征，建立了可同時描述目標顏色信息與形狀信息的三維特征直方圖，以處理背景顏色、形狀信息與目標不同的各種環境，提高跟蹤的準確性。此外，對三維直方圖的這三個特征分量采取自適應加權選擇，以進一步抑制背景干擾目標，增強了復雜環境下的跟蹤魯棒性。由于文中保持均值漂移定位局部極值的步驟，僅通過直方圖的改進及自適應加權來改進跟蹤算法，未涉及較高計算復雜度的處理過程，因此，仍能滿足跟蹤系統的實時性與穩定性要求。

參考文獻

[1] BRADSKI G R. Computer vision face tracking for use in a perceptual user interface [J]. Intel Technology Journal， 1998， 2（2）： 1?15.

[2] HAUG A J. Bayesian estimation for target tracking： part I， general concepts [J]. WIREs Comp Stat， 2012， 4（06）： 375?383.

[3] HAUG A J. Bayesian estimation for target tracking： part II， the Gaussian sigma?point Kalman filters [J]. WIREs Comp Stat， 2012， 4（06）： 489?497.

[4] BUDIHARTO W， PURWANTO D， JAZIDIE A. A robust obstacle avoidance for service robot using Bayesian approach [J]. International Journal of Advanced Robotic Systems， 2011， 8（01）： 52?60.

[5] SANTIAGO R， PILAR S， EDUARD M. Variability estimation of hue and saturation compoents in the HSV space [J]. Color Research and Application， 2011， 37（06）： 261?271.

[6] 趙紅雨，吳樂華，史燕軍，等.基于HSV顏色空間的運動目標檢測方法[J].現代電子技術，2013，36（12）：45?48.

[7] 林建華，劉黨輝，邵顯奎.多特征融合的Camshift算法及其進一步改進[J].計算機應用，2012，32（10）：2814?2816.

[8] WILKASON T J. Robust video tracking through multiple occlusions [D]. GA： Mount de Sales Academy of Warner Robins， 2009.

[9] KHALID M S， ILYAS M U， SARFARAZ M S， et al. Bhatta?charyya coefficient in correlation of gray scale objects [J]. Journal of Multimedia， 2006， 1（06）： 56?61.

[10] CHU Hong?xia， YE Shu?jiang， GUO Qin?chang， et al. Object tracking algorithm based on Camshift algorithm combinating with difference in frame [C]// Proceedings of the IEEE International Conference on Automation and Logistics. Jinan， China： IEEE， 2007： 51?55.