摘 要：視頻監(jiān)控是安全防范系統(tǒng)的重要組成部分，而視頻運動目標檢測和跟蹤技術則是智能視頻監(jiān)控的關鍵技術。Mean Shift算法是一種在一組數(shù)據(jù)的密度分布中尋找局部極值的穩(wěn)定的方法，并因其它計算量小，簡單易實現(xiàn)而廣泛應用于實時跟蹤場合。在離散的數(shù)據(jù)集上，Mean Shift能很快的找到數(shù)據(jù)分布最密集的點，本文介紹了使用OpenCV實現(xiàn)Mean Shift的方法，分析其在跟蹤方向的優(yōu)勢與不足。

關鍵詞：目標跟蹤；OpenCV；Mean；Shift；顏色直方圖

中圖分類號：TP391.41

視覺是人類從外界獲取信息的主要途徑。運用攝影機和電腦代替人眼對目標進行識別、跟蹤和測量，將三維環(huán)境信息儲存為二維信息，并進一步做圖像處理，合成為更適合人眼觀察或傳送給儀器檢測的圖像。計算機視覺試圖建立能夠從圖像或者多維數(shù)據(jù)中獲取‘信息’的人工智能系統(tǒng)。在這些應用領域中，如何利用計算機把運動目標從有干擾的背景中檢測出來并對其進行識別、跟蹤、管理等處理是需要研究的關鍵技術。

1 視頻運動目標跟蹤

20世紀60年代后期，蒙特卡羅方法被引入自動控制領域。1975年，F(xiàn)ukmaga等人在一篇關于概率密度梯度函數(shù)的估計中提出Mean shift。1995年，Yizong Cheng在“Mean shift mode seeking and clustering”中定義了一族核函數(shù)，設定了一個權重系數(shù)，擴充了基本Mean Shift算法，擴大了其適用范圍。1999年，Intel公司在均值偏移理論的基礎上建立了CAMSHIb'T算法，以及基于此算法的人臉跟蹤系統(tǒng)，將均值偏移算法擴展到運動目標跟蹤領域中?；贛ean shift的研究有許多成果發(fā)表[1-3]。

2000年，Comaniciu[4-5]等人將Mean Shift作用于非剛性物體的實施跟蹤。他們用顏色直方圖作為目標特征，使用Bhattacharyya系數(shù)來判別概率分布相似程度，利用均值遷移方法作為模式搜索方法。2005年，S.T Birchfield在Mean Shift算法中引入包含空間信息的空間顏色直方圖，增加了目標描述信息并增強跟蹤的魯棒性。同年，Collins等人采用多特征選擇機制用以提升目標與背景分離度從而改善跟蹤效果。2010年，王方林等人在文獻提出有效融合多種空間分布片段的融合方案以解適應目標遮擋情況。同年，李書曉等人提出的自適應pyramid Mean Shift 算法，改善了Mean Shift跟蹤對于相鄰幀目標位移過大時不靈敏的問題。

2 Meanshift算法

2.1 用于跟蹤的Mean Shift算法

Mean-Shift算法是一種半自動跟蹤算法.在跟蹤序列的初始幀，通過人工或其他識別算法確定目標窗并構建目標模型；然后，在序列第N幀對應位置計算候選目標模型；比較兩個模型的相似度，以相似度最大化為原則移動跟蹤窗，從而定位目標的真實位置。文獻[6]中介紹其算法。

目標定位問題轉化為最大化相似度函數(shù)ρ（Y）的問題.以前一幀的搜索窗中心Y0為起始點，將ρ（Y）在Y0附近Taylor展開，取前兩項。即：

（1）

因此要使得r（Y）向最大值迭代，只要Y的搜索方向與梯度方向一致即可，通過求導可得到Y0的梯度方向。從而可以推導出Mean-Shift向量：

（2）

其中，Y1是目標的新中心坐標；g（x）=?k′（x），是函數(shù)k（x）的影子核。通過反復迭代，當Mean-Shift向量mHh，g（Y0）的模值小于給定常量ε時，則認為完成了目標定位。

3 核函數(shù)帶寬的作用及選擇

核函數(shù)帶寬與跟蹤目標空間尺度基本吻合，由此產(chǎn)生的Bhattacharyya系數(shù)在目標點附近基本上呈單峰模式，經(jīng)Mean-Shift迭代后可以準確定位。采用2倍帶寬，引入了多余噪聲，當目標附近存在具有相似特征的物體時，定位會偏向干擾物體。采用0.5倍帶寬，導致定位時會在該區(qū)域內“漫游”，具有很大的隨機性。

Mean Shift算法使用核直方圖描述目標，對目標的形變和旋轉變化、部分遮擋等具有較強的魯棒性，而且計算簡單、速度快。但是，算法假設了目標和背景各自對應的顏色非零部分的顏色直方圖不相同，因此，在目標與背景顏色相近的情況下容易導致跟蹤失敗。另外，Mean Shift算法的核函數(shù)窗口寬度固定，使得當目標的尺度變大超出搜索窗大小時，算法的效果同樣受到影響。

核函數(shù)帶寬在Mean-Shift算法中起著非常重要的作用，它決定了參與迭代的樣本數(shù)量，反映了搜索窗的形狀和大小.對同一個矩形目標，用不同帶寬的同一核函數(shù)進行定位。

4 Mean Shift跟蹤與OpenCV實現(xiàn)

4.1 運行環(huán)境介紹

OpenCV的全稱是Open Source Computer Vision Library，是一個跨平臺的開源計算機視覺庫。最早由英特爾公司于1999年啟動并參與開發(fā)，OpenCV的一個目標是構建一個簡單易用的計算機視覺框架，以幫助開發(fā)人員更便捷的設計更復雜的計算機視覺相關應用程序，例如實時的圖像處理、計算機視覺以及模式識別程序。該程序庫也可以使用英特爾公司的IPP進行加速處理。

OpenCV的1.0版本于2006年發(fā)布。2.0版本于2009年10月發(fā)布，該版本的主要更新在于其采用C++語言編寫，它的主要接口也是C++語言，但是依然保留了大量的C語言接口。

4.2 顏色直方圖

HSV（Hue，Saturation，Value）色彩空間也稱為色相、飽和度、亮度模型。H表示色相，是色彩的基本屬性；S表示飽和度，指色彩的純度；V表示亮度。這種色彩空間反應了人類觀察色彩的方式，同時也有利于圖像處理。

基于這一特性，Mean shift算法在候選目標的建模中，將采集的RGB彩色圖像轉換到HSV空間，采用HSV模型中的Hue分量進行跟蹤，從而克服一部分的光照影響。Mean Shift基于模式匹配的機理建立顏色直方圖。

反向投影圖實際上是一張概率密度圖。輸入一個目標圖像的直方圖，用某一位置上像素值（多維或灰度）對應在直方圖的一個bin上的值來代替該像素值，輸出圖像象素點的值是觀測數(shù)組在某個分布（直方圖）下的概率，整個圖像為單通道。如果輸入圖像上的點越亮，就說明這個點屬于物體的概率越大。輸出的反向投影圖作為Mean Shift輸入進行跟蹤。

4.3 Mean Shift迭代

OpenCV中提供的Mean Shift算法函數(shù)沒有引入核函數(shù)與巴氏系數(shù)，只計算輸入圖像窗口的重心，通過不斷迭代調整中心直到重心匯聚以實現(xiàn)跟蹤。具體實現(xiàn)如下。（1）選擇窗的大小和初始位置。（2）計算此時窗口內的Mass Center。（3）調整窗口的中心到Mass Center。（4）重復2和3，直到窗口中心\"會聚\"，即每次窗口移動的距離小于一定的閾值。

4.4 實驗結果分析

Mean Shift算法對目標變形魯棒性好，在跟蹤目標發(fā)生形變時，不容易出現(xiàn)跟丟現(xiàn)象。跟蹤目標與背景顏色對比度大時，跟蹤效果較好。如果跟蹤對象在跟蹤過程中出現(xiàn)消失，跟蹤窗口則停留在上一幀附近位置，在跟蹤對象再次出現(xiàn)時，則繼續(xù)跟蹤Mean Shift算法采用顏色作為目標特征值的局限。當目標與背景顏色相近時，無論是與移動物體還是靜態(tài)背景相似，都容易在二者重疊時發(fā)生選擇框跟隨其他物體移動，從而導致跟丟現(xiàn)象。

a b

圖1

圖1所示跟蹤目標因被遮擋而導致目標丟失現(xiàn)象，這也是算法需要改進之處。

5 總結與展望

Mean Shift算法在跟蹤領域有很多優(yōu)點，比如：實時性好，對遮擋、目標變形魯棒性好。雖然Mean Shift算法不能跟蹤快速目標，但相比那些和濾波以及數(shù)據(jù)關聯(lián)度的跟蹤算法，Meanshift算法的計算量已經(jīng)大大降低了。算法跟蹤的準確度依然有待提高。建立一個魯棒性好的算法無論對于目標檢測，還是目標跟蹤的建立模型都大有裨益。增加構建直方圖的目標特征的個數(shù)，即在顏色特征以外加上空間信息描述或者對被跟蹤目標的形狀特征，有助于提高目標描述的準確性。作為一個優(yōu)化的算法，跟蹤算法可能在計算過程中收斂到局部極值。對于這個問題，最好的辦法是盡量避免圖像出現(xiàn)多個極值，也就是說最后只有一個最大值，這樣就可以保證收斂總是處于正確位置。

跟蹤算法應用廣泛，無論在軍事還是民用，經(jīng)濟生活還是社會公共安全方面都是有重要作用及巨大的商業(yè)潛力的。如果有更多精確的跟蹤算法問世，將使得虛擬與現(xiàn)實之間的距離進一步縮小。

參考文獻：

[1]Gary Bradski，Adrian Kaehler，學習OpenCV[M].北京：清華大學出版社，2009.

[2]中文維基百科，2013.

[3]劉毅.局部CamShift跟蹤算法[D].武漢理工大學，2011.

[4]Dorin Comaniciu，Visvanathan Ramesh，Peter Meer.Real-Time Tracking of Non-Rigid Objects Using Mean Shift.CVPR，2000.

[5]Ido.Leichter.Mean Shift Trackers with Cross-Bin Metrics.TPAMI，2012.

[6]袁廣林，薛模根，韓裕生.基于自適應多特征融合的Mean Shift目標跟蹤[J].計算機研究與發(fā)展，2010.

作者簡介：魏保華（1965-），男，山西人，工學博士，副教授，計算機應用方向。

作者單位：廣東省農(nóng)工商職業(yè)技術學院計算機系，廣州 510507