動態融合梯度信息的Camshift算法改進研究

摘 要：將梯度信息引入到Camshift算法之中，定義Camshift算法的梯度模型。依據運動目標和背景圖像直方圖的Bhattacharyya距離來動態決定梯度模型在查找算法中的決定權重，減小加入梯度后對算法時效性的影響；在Camshift算法求運動目標色調分量的過程中，改進由RGB空間到HSV空間轉換計算的方法，減少反余弦和開方運算。在色調分量Hue基礎上定義一種Hue分量，提高顏色空間之間的轉換效率；在對目標跟蹤框內顏色直方圖進行計算時，以選取框重心位置為中心，距離中心越遠的像素在顏色直方圖中的比重越小.減小在選取運動物體初始位置時引入的背景噪聲，提高跟蹤算法的穩定性。實驗證明：經過上述的改進，使得傳統的Camshift算法在背景顏色與運動目標和有相似顏色物體對運動目標造成干擾的情況下的跟蹤魯棒性得到提高。

關鍵詞：Camshfit；梯度模型；動態融合；空間轉換計算簡化；加權像素值

Abstract：Introducing gradient information into the Camshift arithmetic， and defining the model of Camshift algorithm. Based on a moving target and the background image histogram Bhattacharyya distance determine the weight of gradient model in the search algorithm determines dynamically， decreasing bad influence of timeliness after adding gradient information； In the process of Camshift algorithm solve hue component for moving target， improving conversion method of calculation from RGB space to HSV space， reducing anti-cosine and square root operation. Based on the hue component，defining a new hue component to improve the conversion efficiency between color spaces； In the color histogram of the target tracking box to perform a calculation， in the center of gravity center of marquee， the farther from the center of the pixel the smaller in proportion of the color histogram. Reducing the background noise when selecting the moving object and the initial position and improving the stability of the tracking algorithm. Experimental certifies： After the above improvements make the traditional Camshift algorithm tracking robustness improved in the case of color of the background and color on the moving target is similar.

Key words：Gradient model；Dynamic integration；Simplify the calculation of space conversion；Weighted pixel values

1 引言

Camshift算法是一種基于圖像顏色特征的目標跟蹤算法，它是MeanShift算法的改進，Camshift算法的全稱是\"Continuously Adaptive Mean-SHIFT\"，稱為連續自適應的MeanShift算法，它的基本思想是視頻圖像的所有幀作MeanShift運算，并將上一幀的結果（即Search Window的中心和大小）

作為下一幀Meanshift算法的Search Window的初始值，如此迭代下去。由于具有對目標形變不敏感，進過優化后實時性好[1][2]等特點近年來備受親睞。但傳統的Camshift算法是一種半自動算法，算法執行前，需要人工選定跟蹤物體的區域。國內外很多文獻中對Camshift算法的半自動改進做了大量研究，具有典型代表性的有幀差法[3]和背景差分[4]法提取進入視頻監控區域的運動物體。Camshift是基于顏色核的算法，針對運動目標的直方圖進行分析[5]，優點是使得算法對目標形變不敏感，但Camshift算法丟失了運動目標空間以及輪廓信息，使得在光線變化明顯或目標與背景顏色相近的復雜場景下易受干擾[6]。作為跟蹤環境的另一重要部分的背景，對于算法的穩定跟蹤具有重要意義，可以采用動態的更新減少噪聲和光照變化對于跟蹤魯棒性的影響[7]。部分文獻中，采用顏色、邊緣梯度、紋理等多個特征自適應融合的方式改進算法[8]，提高算法應對光線變化的能力； 并通過修正特征直方圖、設置合理搜索范圍對算法進行進一步改進，解決相似背景的干擾問題。有些改進方法，通過將一些成熟的濾波算法引進到Camshift的視頻跟蹤之中，比如卡爾曼濾波，也起到了很好的效果[9]。針對快速運動的目標，由于運動方向的不確定性，Camshift不能準確跟蹤目標，導致跟蹤丟失.有文獻研究將目標運動軌跡預測思想引入Camshift算法，提出了一種能有效跟蹤運動目標的新方法.該方法能準確預測運動目標的位置，減少在算法中搜索目標的次數，進而提高目標跟蹤的準確性和速度[10]。同時，Camshift也是一種能夠擴展跟蹤運動目標數目的算法，進過改進的算法可以同時對多目標進行跟蹤[11]，使其在實際運用中更有意義。

2 Camshift算法的大致實現流程介紹

Camshift利用目標的顏色直方圖模型將圖像轉換為顏色概率分布圖，初始化一個搜索窗的大小和位置，并根據上一幀得到的結果自適應調整搜索窗口的位置和大小，從而定位出當前圖像中目標的中心位置。算法的主要流程分為以下幾大部分：

⑴初始化運動目標模型、候選區域和二維概率分布中心位置。由于Camshift算法是一個半自動算法，無法自動查找到進入視野里的運動目標，需要人工選定運動物體。選擇運動物體的同時確定了候選區域。

目標模型的表示：（公式和過程如果參考了其他文獻，請標注出來，下同。）

其中C位歸一化常數。

選用Bhattacharrya系數相似性函數ρ（y）來表示選定和目標候選模型的相似程度。

則初始窗口到目標模型的移動距離應為：

⑶在視頻相鄰兩幀之間對以上兩個步驟反復迭代，就實現了Camshift算法。

3 動態梯度與色調的融合及Camshift改進研究

3.1 動態梯度與色調信息的融合

傳統的Camshift算法中，對物體進行跟蹤的主要依據是將運動目標的顏色直方圖反向投影到候選區域，按照像素點出現的密度來移動跟蹤框到下一幀圖像中最可能出現的位置。這樣做的好處是算法實時性好，迭代算法輕量而高效。

由于算法是在HSV空間下對顏色信息進行概率計算，相對于RGB空間下的跟蹤，HSV空間的信息和光照沒有直接聯系，因此，Camshift算法對光線變化對跟蹤的影響具有較好的魯棒性。但由于顏色核是算法唯一跟蹤的唯一依據，不足是顯而易見的，論文旨在將梯度模型合理最優的引入到跟蹤算法中，增強算法在有顏色相近物體干擾時跟蹤的魯棒性，不至于對運動物體跟蹤丟失。

論文采用OpenCV2.4.1開源計算機視覺庫在VS2010搭建的平臺進行開發。在新版本的OpenCV中，大量使用了Mat圖像容器類，同時它也是一般矩陣類，因此，利用Mat創建和操作多維矩陣是簡潔高效的[14]。這就為梯度模型和色調模型的融合創造了條件。

在這里，利用圖像容器類Mat構造色調和梯度的二維二通道矩陣：

其中n，m分別是圖像矩陣的行數和列數。j是一個動態值，由選定的目標區域和候選區域的概率模型的巴氏距離大小來動態決定，j在數值上不大于m。j的數值越大，梯度模型在整個二維二通道矩陣中所占的比重越大，改進跟蹤算法的抗顏色相近物體干擾能力越好，同時，計算量也越大。

經過大量實驗統計，將巴氏距離四等分，不同距離下的j/m值為以下值時，跟蹤效果最佳：

然后求混合二通道矩陣的直方圖，將直方圖反向投影，進行迭代計算找出運動目標在下一幀中最有可能出現的位置。這樣就實現了將梯度信息動態的融入到Camshift算法。

3.2 RGB空間到HSV空間轉換色調通道計算的化簡

考慮到引入梯度信息后，會增加算法的復雜度，可能會導致實時性的降低，達不到跟蹤的要求，對Camshift算法中從RGB空間到HSV空間轉換過程進行簡化，減小計算量。

3.2.1 RBG空間到HSV空間的轉換方法

用RGB來表示顏色雖然方便，但是兩個相近的顏色的RGB值可能有很大差別，不利于計算。用HSV（Hue色相、Saturation飽和度、Value（Brightness）明度，也叫HSB）來表示顏色就比較符計算機表達方式，對光線變化的數據穩定性也更好。

Camshift算法就在HSV空間小進行，由RGB到HSV空間的轉化公式如下[15]。

式中R，G，B與H，S，V分別代表個顏色分量的值。

3.2.2 顏色空間模型

由式（1）可以看到，HSV空間中的H分量計算相對復雜，涉及到求算術平方根和反余弦運算，這一部分可以優化以減少跟蹤算法整體運算時間。

在保持H分量色調通道特性的基礎上，取：

，其中H為HSV空間的色調分量值。

繼續化簡可得：

這樣得到的分量 的表達式中，只存在基本的四則運算，縮短了每一幀圖像從RGB空間向 空間轉化所需要的時間。

3.3 基于反距離加權插值的ROI噪聲減除方法

在給Camshift算法初始化要跟蹤的目標時，需要人工選定跟蹤框的位置，在選取的過程中，如果待跟蹤的目標不是規則且平行于坐標軸的矩形，采用的矩形跟蹤框會引入不屬于目標的背景噪聲，背景噪聲會影響迭代計算的穩定性，甚至造成目標的丟失。因此，加入反距離加權插值使得離選定區域重心越遠的像素點值越小的方式，弱化邊緣像素在整個目標區域的權重，盡可能的減少屬于背景像素點對跟蹤的影響。

反距離加權插值以插值點與樣本點間的距離為權重進行加權平均，離插值點越近的樣本點賦予的權重越大。

插值權重系數計算表達式為：

其中，P為指數值；

dio是預測點S0與選擇區域重心Si之間的距離。

計算過程中參數p影響樣點在預測點值所占權重的大小，選擇區域重心與預測點距離影響的權重按指數規律變化，但這些權重值的總和為1。

得出反距離加權插值法的一般公式：

其中，Z（S0）為S0處的加權后的像素值；

λi為預測計算過程中使用的各樣點的權重，Z（S0）是在Si處的像素值；N是預測計算過程中要使用的像素點周圍樣點的數量。

通過插值計算，圖像遠離重心的像素值在整幅圖像像素值得以減小，相對將所有像素點同等看待的方法，對矩形ROI進行反距離加權插值后的數值更加忠于實際情況。

4 實驗結果

為了驗證算法，使用VS2010和OpenCV搭建實驗平臺。在室內日光燈照射下，使用200萬像素的攝像頭進行視頻圖像的采集。主要過程包括：程序編譯，視頻設備硬件初始化，選定目標跟蹤以及后續跟蹤過程。改進的算法在Core I5 M480處理器，4GB內存計算機上達到30幀/秒以上的處理速度。符合實時性的要求。

圖1中.圖1（a）展示了跟蹤算法改進前初始化目標生成的單純色調直方圖圖像，圖1（b）是經過論文中方法改進的Camshift算法得到的初始化目標的梯度和色調混合直方圖圖像。可以明顯看到圖1（b）所得到的信息要比圖1（a）豐富，也就說明了改進方法進行跟蹤依據的要素要比為改進前多，從而提高了算法穩定性。

圖1（a）傳統Camshift算法得到的初始目標色調直方圖X：直方圖bins；Y：相應bins出現頻率

圖1（b） 改進Camshift算法得到的初始目標的梯度和色調混合直方圖X：直方圖bins；Y：相應bins出現頻率

傳統算法在實際的跟蹤效果圖2所示。可以明顯看到，在手掌接近面部的時候，跟蹤框擴大，這是因為手掌顏色與面部顏色相近，影響了算法的穩定跟蹤。動態融合梯度信息的Camshift算法實際跟蹤效果如圖3。圖3中算法在相近顏色物體干擾情況下對運動目標進行跟蹤測試。對于相近色物體的干擾，因為引入了目標的梯度信息，算法增強了跟蹤過程的穩定性，跟蹤框沒有發生跳變和將手掌歸入實際目標的情況。

5 總結

本文重點研究了針對Camshfit算法不足所采取的幾種改進方案，主要有以下幾點：論文中采用的是根據巴氏距離動態地將梯度信息和色調信息融合的方法，使得Camshift算法不再單單依賴顏色信息。為了彌補加入梯度信息的跟蹤以后對原始算法時效性的影響，重新定義算法中每一幀必須使用的RGB空間向HSV空間轉換過程，保持色調特征基礎上優化了得到色調信息的計算步驟。使得再加入梯度信息之后算法依然具有較好的實時性。考慮到手工選定矩形跟蹤框時，會引入背景成為跟蹤的噪聲，論文中從一般情況出發，弱化初始跟蹤框邊緣部分像素值在整個圖像中的比重，得到了很好的效果。

[參考文獻]

[1]Yi-bo Li，Xiao-ling Shen，Shan-shan Bei.Real-time Tracking Method for Moving Target Based on an Improved Camshift Algorithm[D].Shenyang Aerospace University，Shenyang，110000.2011.

[2]張學賀，張學東，丁寧.遼寧鞍山：基于OpenCV的運動目標檢測與跟蹤[J].遼寧科技大學，114051.2010.

[3]趙文倩，匡遜君，李明富.基于改進的Camshift運動目標跟蹤算法的研究[J].湘潭：湘潭大學.411100 2012.

[4]鞏艷華，朱愛紅，代凌云.基于顏色直方圖的顏色特征提取[J]. 1. 山東煙臺：海軍航空工程學院.山東日照：曲阜師范大學日照校區信息技術傳播學院.

[5]Mohd Asyraf Zulkifley，Mohd Marzuki Mustafa and Aini Hussain.Improving CAMSHIFT Performance Through Colour Constancy Approach[D].Universiti Kebangsaan Malaysia， Malaysia 43600.2012.

[6]Gang XU，Dong ZHAO，Qi ZHOU，Ding HUANG.Moving Target Tracking based on Adaptive Background Subtraction and Improved Camshift Algorithm[D].North China Electric PowerUniversity，Beijing，100000.2010.

[7]林建華，劉黨輝.邵顯奎.多特征融合的Camshift算法及其進一步改進[J].北京：裝備學院101416.2012.

[8]張甜，李月娥.一種基于改進卡爾曼濾波的camshift目標跟蹤算法[J]. 太原：山西大學.2012.

[9]王忠義，孫曉靜，周宏.一種基于Camshift的快速目標識別算法[J].鄭州：河南中醫學院，450000.2012.

[10]P.Hidayatullah，H.Konik.Camshift Improvement On Multi-hue Object And Multi-Object Tracking[D].Bandung State Polytechnic，Bandung， Indonesia.Université Jean Monnet， 42000 Saint-Etienne，France.2012.

[11]陳禹，梁寶生.基于改進的CAMSHIFT算法的視頻目標跟蹤系統的研究與設計[D] .山西太原：太原理工大學. 030024 2012.

[10]多特征融合的Camshift算法及其進一步改進[J].裝備學院航天裝備系.北京.

[11]王展青，凡友福，張桂林.跟蹤遮擋目標的一種魯棒算法[J].武漢：華中科技大學圖像信息處理與智能控制教育部重點實驗室.武漢：武漢理工大學理學院，2007.

[12]Robert Laganiere，著，張靜，譯.OpenCV2計算機視覺編程手冊[M].科學出版社.2013.

[13]曹宇，趙杰，閆繼宏.基于自定義顏色空間的快速圖像分割算法[J]. 哈爾濱：哈爾濱工業大學機器人研究所，2009.