MeanShift算法相關(guān)應(yīng)用

廖禮

摘 要 MeanShift算法是一種無參數(shù)概率密度估計(jì)的算法。通過概率密度函數(shù)和有限次的迭代，能快速找到數(shù)據(jù)分布的模式。具有原理簡(jiǎn)單、參數(shù)少，無需預(yù)處理等諸多優(yōu)點(diǎn)，被廣泛應(yīng)用于圖像平滑、邊緣檢測(cè)、目標(biāo)跟蹤等領(lǐng)域。本文簡(jiǎn)要介紹了MeanShift算法的幾種應(yīng)用。

關(guān)鍵詞 MeanShift 圖像平滑 邊緣檢測(cè) 目標(biāo)跟蹤

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

MeanShift （均值漂移）是一種非參數(shù)概率密度估計(jì)的方法，一種最優(yōu)的尋找概率密度極大值的梯度上升法，在解決計(jì)算機(jī)視覺底層過程中表現(xiàn)出了良好的魯棒性和較高的處理速度。MeanShift最早于1975 年由Fukunaga等人在關(guān)于概率密度梯度函數(shù)的估計(jì)一文中提出。MeanShift 算法一般指的是一個(gè)迭代的步驟，即先算出當(dāng)前點(diǎn)的漂移均值，移動(dòng)該點(diǎn)到其漂移均值，然后以此為新的起始點(diǎn)，繼續(xù)移動(dòng)，直到滿足一定的條件結(jié)束。隨著時(shí)間的推移，MeanShift也由最基本的形式得到了完善和發(fā)展。首先，Yizong Cheng定義了一族核函數(shù)，使得隨著樣本與被漂移點(diǎn)的不同，其漂移量對(duì)均值漂移向量的貢獻(xiàn)也不同；其次又設(shè)定了一個(gè)權(quán)重系數(shù)，使得不同樣本點(diǎn)的重要性不一樣。因此MeanShift 的適用范圍得到了擴(kuò)大。接著Comaniciu 等人將MeanShift 算法運(yùn)用到了特征空間的分析之中，對(duì)圖像進(jìn)行平滑和分割處理，并把非剛體的跟蹤問題近似為一個(gè)MeanShift 最優(yōu)化問題，使得跟蹤可以實(shí)時(shí)地進(jìn)行。由于MeanShift 算法完全依靠特征空間中的樣本點(diǎn)進(jìn)行分析，不需要任何先驗(yàn)知識(shí)，收斂速度快，近年來在圖像平滑、邊緣檢測(cè)以及目標(biāo)跟蹤等許多計(jì)算機(jī)視覺研究領(lǐng)域開始得到廣泛的關(guān)注和應(yīng)用。

1 MeanShift算法的相關(guān)應(yīng)用

1.1基于MeanShift的圖像平滑

一幅圖像可以表示成一個(gè)二維網(wǎng)格點(diǎn)上p維向量，每一個(gè)網(wǎng)格點(diǎn)代表一個(gè)像素，p=1表示這是一個(gè)灰度圖，p=3表示彩色圖，p>3表示一個(gè)多譜圖，網(wǎng)格點(diǎn)的坐標(biāo)表示圖像的空間信息。統(tǒng)一考慮圖像的空間信息和色彩（或灰度等）信息（這里選擇L*U*V彩色空間），組成一個(gè)p+2維的向量x=（xs，xr），其中xs表示網(wǎng)格點(diǎn)的坐標(biāo)，表示該網(wǎng)格點(diǎn)上p維向量特征。所謂p+2維空間指的是圖像二維坐標(biāo)空間和p維值域空間。用核函數(shù)K來估計(jì)x的分布，K具有如下形式：

其中hs，hr控制著平滑的解析度，C是一個(gè)歸一化常數(shù)。分別用xi和zi，i=1，…，n表示原始和平滑后的圖像。用MeanShift算法進(jìn)行圖像平滑的具體步驟如下：

對(duì)每一個(gè)像素點(diǎn)：

（1）初始化j=1，并且使yi，1=xi；

（2）運(yùn)用MeanShift算法計(jì)算yi，j+1，直到收斂。記收斂后的值為yi，c；

（3）賦值z(mì)i=（x，y）。

1.2基于MeanShift的邊緣檢測(cè)

基于MeanShift的邊緣檢測(cè)同樣是在p+2維空間中，選用YCbCr彩色空間作為算法的彩色度量空間，以像素的MeanShift偏移向量為重要特征，并考慮像素點(diǎn)相互空間關(guān)系的邊緣檢測(cè)算法。首先通過MeanShift算法計(jì)算出圖像中各個(gè)像素的MeanShift最終偏移量，然后根據(jù)MeanShift理論以及該偏移量性質(zhì)，同時(shí)引入MeanShift向量的方向和長(zhǎng)度進(jìn)行邊緣檢測(cè)。

算法步驟：

（1）根據(jù)zi=（x'iMS）=（x'i，y'y'）取得圖像中每一個(gè)像素點(diǎn)的MeanShift偏移量MSvector；

（2）如果像素點(diǎn)對(duì)應(yīng)的MSvector向量同時(shí)滿足如下條件，則該點(diǎn)為邊緣輪廓點(diǎn)： |MSvector|MST； 該點(diǎn)的領(lǐng)域點(diǎn)中，至少有一個(gè)點(diǎn)的MSvector矢量方向和該點(diǎn)的MSvector矢量方向的夾角介于160度到200度之間。

其中，xi和zi（i=1，2，…，n），分別為d維空間中的輸入圖像像素和輸出圖像像素。

MeanShift偏移量表示為MSvector（xi，yi），其中（xi，yi）為圖像中像素坐標(biāo)值，i=1，2，…，n，這樣越靠近邊緣的點(diǎn)，其離圖像聚類中心點(diǎn)就越遠(yuǎn)，相應(yīng)的|MSvector|值越大。

1.3基于MeanShift的目標(biāo)跟蹤

基于Meanshift 的目標(biāo)跟蹤算法是一種半自動(dòng)跟蹤算法，在起始幀需要對(duì)跟蹤目標(biāo)進(jìn)行初始化，首先通過鼠標(biāo)選定要跟蹤的目標(biāo)區(qū)域，這個(gè)目標(biāo)區(qū)域也是核函數(shù)作用的區(qū)域，區(qū)域的大小等于跟蹤窗口半徑h （或稱核函數(shù)帶寬）。對(duì)在目標(biāo)區(qū)域內(nèi)的像素點(diǎn)，計(jì)算特征空間中每個(gè)特征值的概率，即為目標(biāo)模型的描述。在后續(xù)的每幀中可能存在目標(biāo)候選區(qū)域，對(duì)其特征空間每個(gè)特征值的計(jì)算稱為候選模板的描述。利用Bhattacharyya相似函數(shù)（簡(jiǎn)稱BH系數(shù)）度量初始幀目標(biāo)模型和當(dāng)前幀候選模型的相似性，通過求相似函數(shù)最大得到關(guān)于目標(biāo)的MeanShift 向量，這個(gè)向量即是目標(biāo)從初始位置向正確位置移動(dòng)的向量，由MeanShift 算法的收斂性，不斷迭代計(jì)算MeanShift 向量，在當(dāng)前幀中，最終目標(biāo)會(huì)收斂到目（下轉(zhuǎn)第276頁(yè)）（上接第274頁(yè)）標(biāo)的真實(shí)位置，從而達(dá)到跟蹤的目的。

算法步驟：

（1）選中物體，記錄輸入的方框和物體；

（2）求出視頻中有關(guān)物體的反向投影圖；

（3）根據(jù)反向投影圖和輸入方框進(jìn)行MeanShift迭代，由于它是重心移動(dòng)，即向反向投影圖中概率大的地方移動(dòng)，所以始終會(huì)移動(dòng)到目標(biāo)上；

（4）下一幀圖像時(shí)用上一幀輸出地方框來迭代即可。

2總結(jié)

本文簡(jiǎn)要介紹了MeanShift的一些典型應(yīng)用，顯示出了MeanShift的強(qiáng)大功能。當(dāng)然Meanshift算法的應(yīng)用不僅僅局限于此。隨著Meanshift算法的不斷改進(jìn)，其應(yīng)用領(lǐng)域也不斷擴(kuò)展，應(yīng)用前景也會(huì)越來越好。

參考文獻(xiàn)

[1] 宋新，沈振康，王平，王魯平.Mean shift 在目標(biāo)跟蹤中的應(yīng)用[J].系統(tǒng)工程與電子技術(shù)，2007（29）.

[2] Fukunaga，K.&L.D.Hostetler.The Estimation of the Gradient of a Density Function[J].IEEE Trans. Information Theory， 1975（21）： 32-40.

[3] Cheng，Y.Z. MeanShift， Mode seeking， and Clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1995，17（08）： 790-799

[4] Dorin Comaniciu. Mean Shift：A Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002.

[5] 田莘.基于MeanShift算法的目標(biāo)跟蹤問題研究[D].西安：西安科技大學(xué)，2011.

[6] 何恒攀，趙敏，孫棣華.基于meanshift算法的圖像邊緣檢測(cè)[J].重慶工學(xué)院學(xué)報(bào)（自然科學(xué)版），2009，23（08）.

[7] 丁大弸，黃歡，劉輝羅山.基于Mean Shift算法的實(shí)時(shí)運(yùn)動(dòng)目標(biāo)跟蹤[J].山西電子技術(shù)，2008（05）.