基于Mean Shift視頻運(yùn)動(dòng)目標(biāo)跟蹤

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

關(guān)鍵詞：目標(biāo)跟蹤；OpenCV；Mean；Shift；顏色直方圖

中圖分類(lèi)號(hào)：TP391.41

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

1 視頻運(yùn)動(dòng)目標(biāo)跟蹤

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

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

2 Meanshift算法

2.1 用于跟蹤的Mean Shift算法

Mean-Shift算法是一種半自動(dòng)跟蹤算法.在跟蹤序列的初始幀，通過(guò)人工或其他識(shí)別算法確定目標(biāo)窗并構(gòu)建目標(biāo)模型；然后，在序列第N幀對(duì)應(yīng)位置計(jì)算候選目標(biāo)模型；比較兩個(gè)模型的相似度，以相似度最大化為原則移動(dòng)跟蹤窗，從而定位目標(biāo)的真實(shí)位置。文獻(xiàn)[6]中介紹其算法。

目標(biāo)定位問(wèn)題轉(zhuǎn)化為最大化相似度函數(shù)ρ（Y）的問(wèn)題.以前一幀的搜索窗中心Y0為起始點(diǎn)，將ρ（Y）在Y0附近Taylor展開(kāi)，取前兩項(xiàng)。即：

（1）

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

（2）

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

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

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

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

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

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

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

OpenCV的全稱(chēng)是Open Source Computer Vision Library，是一個(gè)跨平臺(tái)的開(kāi)源計(jì)算機(jī)視覺(jué)庫(kù)。最早由英特爾公司于1999年啟動(dòng)并參與開(kāi)發(fā)，OpenCV的一個(gè)目標(biāo)是構(gòu)建一個(gè)簡(jiǎn)單易用的計(jì)算機(jī)視覺(jué)框架，以幫助開(kāi)發(fā)人員更便捷的設(shè)計(jì)更復(fù)雜的計(jì)算機(jī)視覺(jué)相關(guān)應(yīng)用程序，例如實(shí)時(shí)的圖像處理、計(jì)算機(jī)視覺(jué)以及模式識(shí)別程序。該程序庫(kù)也可以使用英特爾公司的IPP進(jìn)行加速處理。

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

4.2 顏色直方圖

HSV（Hue，Saturation，Value）色彩空間也稱(chēng)為色相、飽和度、亮度模型。H表示色相，是色彩的基本屬性；S表示飽和度，指色彩的純度；V表示亮度。這種色彩空間反應(yīng)了人類(lèi)觀(guān)察色彩的方式，同時(shí)也有利于圖像處理。

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

反向投影圖實(shí)際上是一張概率密度圖。輸入一個(gè)目標(biāo)圖像的直方圖，用某一位置上像素值（多維或灰度）對(duì)應(yīng)在直方圖的一個(gè)bin上的值來(lái)代替該像素值，輸出圖像象素點(diǎn)的值是觀(guān)測(cè)數(shù)組在某個(gè)分布（直方圖）下的概率，整個(gè)圖像為單通道。如果輸入圖像上的點(diǎn)越亮，就說(shuō)明這個(gè)點(diǎn)屬于物體的概率越大。輸出的反向投影圖作為Mean Shift輸入進(jìn)行跟蹤。

4.3 Mean Shift迭代

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

4.4 實(shí)驗(yàn)結(jié)果分析

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

a b

圖1

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

5 總結(jié)與展望

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

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

參考文獻(xiàn)：

[1]Gary Bradski，Adrian Kaehler，學(xué)習(xí)OpenCV[M].北京：清華大學(xué)出版社，2009.

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

[3]劉毅.局部CamShift跟蹤算法[D].武漢理工大學(xué)，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]袁廣林，薛模根，韓裕生.基于自適應(yīng)多特征融合的Mean Shift目標(biāo)跟蹤[J].計(jì)算機(jī)研究與發(fā)展，2010.

作者簡(jiǎn)介：魏保華（1965-），男，山西人，工學(xué)博士，副教授，計(jì)算機(jī)應(yīng)用方向。

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