馬 瑜，梁慧琳，張艷寧，徐 爽

(1.西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西西安710129;2.寧夏大學(xué)研究生院，寧夏銀川750021)

1 引言

均值漂移聚類是一個(gè)基于Parzen窗的非參數(shù)核密度估計(jì)理論，為尋找局部密度的最大處。在均值漂移過(guò)程中，任何數(shù)據(jù)點(diǎn)都可以作為初始點(diǎn)進(jìn)行均值漂移。將收斂到同一個(gè)點(diǎn)的像素點(diǎn)進(jìn)行聚類，漂移過(guò)程中，由圖像自動(dòng)決定每一類的像素?cái)?shù)，和類的邊界［1］。

Comaniciu和Ramesh基于可變的窗寬密度估計(jì)提出一種自適應(yīng)的均值漂移［2］，并且應(yīng)用于圖像分割和聚類［3］。對(duì)自適應(yīng)算法的提出主要是為下一步圖像處理做基礎(chǔ)。周芳芳、樊曉平采用自適應(yīng)均值漂移聚類算法為三維數(shù)據(jù)場(chǎng)設(shè)計(jì)傳遞函數(shù)［4］。Lei Lin提出一種針對(duì)三維MR圖像的自適應(yīng)分割方法，其主要思想也是采用自適應(yīng)的帶寬設(shè)計(jì)，再加入 K-Means算法［5］。Xinhong Zhang為了圖像處理時(shí)降低計(jì)算時(shí)間和計(jì)算維度，提出自適應(yīng)分割算法，其主要思想是運(yùn)用了對(duì)一幅圖像的概率密度估計(jì)來(lái)計(jì)算進(jìn)行帶寬設(shè)計(jì)，再加入本地特征散列法進(jìn)行圖像分割 。袁勝智、謝曉方提出了一種基于Kalman-mean shift的自適應(yīng)跟蹤算法，在mean shift算法中加入了一個(gè)尺度更新項(xiàng)，通過(guò)尺度更新對(duì)運(yùn)動(dòng)目標(biāo)，特別是目標(biāo)尺寸變化的目標(biāo)進(jìn)行自適應(yīng)跟蹤［7］。

基于圖像處理中對(duì)圖像分割的高效、精確的要求，每一幅圖像帶寬范圍不同，而且，一幅圖像，有的部分需要精細(xì)地分割，有的部分又不需要。本文提出一種自適應(yīng)的窗寬計(jì)算方法。由每個(gè)像素點(diǎn)與周圍點(diǎn)的關(guān)系以及圖像的直方圖來(lái)計(jì)算每個(gè)像素點(diǎn)的窗寬，從而進(jìn)行自適應(yīng)的分割。

2 均值漂移算法簡(jiǎn)介

2.1 均值漂移向量

給定d維空間Rd中的S個(gè)樣本點(diǎn)s。在x∈X處，改進(jìn)的樣本均值公式為［8］:

樣本均值與像素點(diǎn)的偏移量m(x)－x稱為均值漂移向量，記為Mh(x)。其中，K稱為核函數(shù)。核函數(shù)可以控制因距離不同，對(duì)像素點(diǎn)X的均值漂移向量貢獻(xiàn)的重要性不同。K為核函數(shù)的條件為:它存在一個(gè)剖面函數(shù)，即:

并滿足:

(1)k是非負(fù)的;

(2)k為非增，如果 ka＜b，k(a)≥k(b);

一般常用的核函數(shù)有兩種，單位均勻核函數(shù)與單位高斯核函數(shù)。

單位均勻核函數(shù):

w(s)為權(quán)值，權(quán)值用來(lái)控制在核函數(shù)范圍內(nèi)，不同的樣本點(diǎn)，重要性不同。它滿足歸一化條件:

均值漂移向量表示為:

2.2 均值漂移算法

均值漂移算法是尋找局部密度最大值的過(guò)程。

均值漂移迭代算法執(zhí)行過(guò)程如下:

(1)計(jì)算樣本均值m(x)。

(2)計(jì)算樣本均值與像素點(diǎn)之間的偏移量m(x)－x。

(3)判斷如果樣本均值與像素點(diǎn)之間的偏移量小于一個(gè)給定的誤差值，結(jié)束循環(huán)，樣本均值為像素點(diǎn)收斂的模式點(diǎn);否則把m(x)賦給x，執(zhí)行(1)繼續(xù)。

3 自適應(yīng)窗寬

在聚類中，帶寬h決定了核函數(shù)的影響范圍，窗寬h對(duì)核密度函數(shù)估計(jì)過(guò)程以及最終的聚類結(jié)果都有很大影響。如果h取值很小，密度函數(shù)f(x)相當(dāng)于n個(gè)數(shù)據(jù)對(duì)象為中心的函數(shù)的疊加，每個(gè)像素點(diǎn)周圍的密度函數(shù)值很小，聚類結(jié)果會(huì)產(chǎn)生很多類。如果h無(wú)窮小，那么每個(gè)像素的密度等于1/n，并且自成一類;如果h取值很大，f(x)稱為n個(gè)變化緩慢且寬度很大的基函數(shù)的疊加，每個(gè)像素周圍的密度函數(shù)值比較大且近似相等，相距較近的聚類將被合并。如果h無(wú)窮大，所有像素的密度等于1且被聚合為一類。所以，盡可能準(zhǔn)確的密度估計(jì)結(jié)果和聚類結(jié)果來(lái)自于窗寬h的選擇。選擇窗寬h時(shí)應(yīng)盡可能的使密度函數(shù)f(x)體現(xiàn)原始數(shù)據(jù)的分布特性。確定窗寬h后，通過(guò)搜索密度函數(shù)的局部極大值點(diǎn)實(shí)現(xiàn)圖像的分割［9］。

3.1 直方圖

本文使用直方圖對(duì)圖像的像素點(diǎn)的特征進(jìn)行統(tǒng)計(jì)。直方圖是一種統(tǒng)計(jì)圖，對(duì)于一幅圖像來(lái)說(shuō)，通過(guò)統(tǒng)計(jì)圖像中各個(gè)像素點(diǎn)的數(shù)量，從而對(duì)圖像的像素分布有一個(gè)直觀了解。通常，通過(guò)直方圖可以對(duì)圖像進(jìn)行直方圖歸一化，直方圖拉伸，直方圖匹配。

一幅數(shù)字圖像在范圍［0，G］內(nèi)共有L個(gè)灰度級(jí)，其直方圖定義為離散函數(shù)h(rk)=nk，其中rk是區(qū)間［0，G］內(nèi)的第K級(jí)亮度，nk是灰度級(jí)為rk的圖像中的像素?cái)?shù)。

其中，δ是 Kronecher符號(hào)［10］。

3.2 圖像的直方圖獲取

對(duì)于一幅圖像來(lái)說(shuō)，如果它是灰度圖像，則為單通道圖像，如果它為彩色圖像，應(yīng)該包含三個(gè)通道:R(Red)，G(Green)，B(Blue)。彩色圖像和灰度圖像的直方圖獲取步驟是相同的，對(duì)于彩色圖像，計(jì)算其二維直方圖。

對(duì)于RGB圖像，由于其處理時(shí)計(jì)算量較大。先將其轉(zhuǎn)化到HSV空間(色調(diào)、飽和度、數(shù)值)。該顏色系統(tǒng)比RGB系統(tǒng)更接近于人們的經(jīng)驗(yàn)和對(duì)顏色的感知。彩色圖像提取其H、V顏色通道的，統(tǒng)計(jì)每種顏色分量的像素?cái)?shù)占圖像總像素?cái)?shù)的比例，從而得到圖像各種顏色分量的比例分布。

灰度圖像直接計(jì)算其灰度像素值的直方圖，并將其歸一化，進(jìn)行保存。

3.3 自適應(yīng)窗寬h的計(jì)算

目前帶寬的計(jì)算主要有兩類，一類是固定帶寬，一類是自適應(yīng)帶寬。固定帶寬在迭代過(guò)程中，帶寬h保持不變，因此需要計(jì)算相對(duì)于全局的最優(yōu)帶寬，在圖像分割過(guò)程中，效率低，分割效果不好。而且，不同的圖像，最優(yōu)帶寬并不在一個(gè)范圍內(nèi)，圖像分割中參數(shù)的確定是一個(gè)很大的工程。因此，圖像分割中，采用自適應(yīng)帶寬，理論上會(huì)獲得比較好的分割效果。根據(jù)圖像像素點(diǎn)的局部特征，自適應(yīng)的設(shè)計(jì)迭代帶寬，對(duì)密度大的區(qū)域采用小帶寬，對(duì)密度小的區(qū)域則采用大帶寬。

由以上的說(shuō)法，令固定帶寬h=h(xi)，即每個(gè)像素點(diǎn)的帶寬均不一樣。一幅圖像，如果從它的直方圖來(lái)統(tǒng)計(jì)看，這個(gè)統(tǒng)計(jì)思想非常地符合在核函數(shù)中窗寬的選擇思想，即對(duì)密度大的區(qū)域采用小帶寬，對(duì)密度小的區(qū)域則采用大帶寬。像素分布于帶寬成反比關(guān)系。所以，使用二維直方圖對(duì)核函數(shù)的窗寬進(jìn)行計(jì)算，是有用的。根據(jù)直方圖的定義，直方圖也可以看作一個(gè)歸一化的概率密度函數(shù)f(xi)［11］。將每個(gè)樣本點(diǎn)的密度估計(jì)用作選擇h(xi)的特征，取f(xi)倒數(shù)的平方根:

式中，h0是一個(gè)初始的固定帶寬，λ是常數(shù)。

為獲得一個(gè)自適應(yīng)的帶寬，f(xi)，λ必須首先計(jì)算。自適應(yīng)窗寬的均值漂移算法步驟為:

(1)找到一個(gè)對(duì)圖像所有像素點(diǎn)都滿足的估計(jì)f(xi)，在這，f(xi)為我們所取圖像的二維直方圖。

(2)窗寬因子λ的定義為:

(3)對(duì)于每個(gè)像素點(diǎn) xi計(jì)算其自適應(yīng)的窗寬h(xi):

則自適應(yīng)的均值漂移向量可表示為:

將計(jì)算后的每個(gè)點(diǎn)的窗寬在分割中帶入，便可得到自適應(yīng)的分割結(jié)果。

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

本實(shí)驗(yàn)使用 Intel Core2，2.10 GHz，2G內(nèi)存的HP筆記本，軟件使用Matlab 2008版本。與原均值漂移分割算法［7］從分割結(jié)果進(jìn)行對(duì)比。hr為均值漂移算法的值域帶寬，hs值漂移算法的為空域帶寬。分割后圖像聚類區(qū)域像素點(diǎn)最小數(shù)量為500。算法中最大迭代次數(shù)為100，誤差系數(shù)ε=0.01。本文采用圖像大小為256×256或120×90。

圖1 灰度圖像的分割

取一幅灰度圖像，如圖1(a)所示圖1(a)的灰度圖像相對(duì)較為復(fù)雜。圖1(b)為使用本文自適應(yīng)算法進(jìn)行圖像分割的結(jié)果。圖1(d)、(e)、(f)分別為使用固定帶寬的均值漂移算法分割后的結(jié)果。對(duì)于固定帶寬參數(shù)的選擇，值域帶寬選定16。進(jìn)行頻域帶寬的單變量參數(shù)變化。由圖可以看出，在圖1(f)中帶寬選擇小了，分割結(jié)果太過(guò)精細(xì)，無(wú)法很好的將背景和前景分開(kāi)，這就是過(guò)分割問(wèn)題，對(duì)于一些不存在的細(xì)節(jié)也會(huì)分割。圖1(d)和圖1(e)進(jìn)行對(duì)比，圖1(e)能相對(duì)較好地將人的輪廓分割出來(lái)，但是，圖像分割得結(jié)果不完整。而自適應(yīng)的均值漂移算法，不僅很好地將人完整地分割，而且，在相機(jī)的腳架以及相機(jī)部分，都很清晰地分割出來(lái)。我們從圖1(b)中可以看到一幅很完整的圖像，包括圖像的前景、背景以及一些細(xì)節(jié)。

圖2(a)為一幅復(fù)雜的彩色圖像。圖2(b)為使用本文自適應(yīng)算法進(jìn)行圖像分割的結(jié)果。圖2(d)、(e)、(f)分別為使用固定帶寬的均值漂移算法分割后的結(jié)果。對(duì)于固定帶寬參數(shù)的選擇，值域帶寬選定16。進(jìn)行頻域帶寬的單變量參數(shù)變化。圖2(d)中，樹(shù)葉部分好多細(xì)節(jié)沒(méi)有分割出，前景和背景很模糊。圖2(f)較好的分割出了樹(shù)葉的部分，但是相比圖2(e)，在藍(lán)天部分，地面部分又存在過(guò)分割的問(wèn)題。圖2(b)圖使用自適應(yīng)的分割算法。不僅很好地分割出樹(shù)葉，而且對(duì)于地面和藍(lán)天，分割精度又不至于太細(xì)導(dǎo)致過(guò)分割。

圖2 彩色圖像的分割

5 結(jié)論

本文根據(jù)在圖像處理中對(duì)圖像分割前期準(zhǔn)備工作高效、準(zhǔn)確的要求，結(jié)合圖像的直方圖，提出一種自適應(yīng)的均值漂移分割算法。算法首先利用圖像的直方圖估計(jì)出圖像的概率密度。對(duì)每個(gè)像素點(diǎn)根據(jù)其周圍特征以及概率分布計(jì)算它的帶寬值。使得在均值漂移濾波時(shí)可以達(dá)到自適應(yīng)的效果。如果沒(méi)有自適應(yīng)帶寬，那么在確定參數(shù)時(shí)需要大量的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法很好的解決了固定帶寬均值漂移算法在確定帶寬時(shí)效率低，分割效果差的問(wèn)題。自適應(yīng)的均值漂移分割算法可以有很好的分割結(jié)果。

［1］ Zhang Xinhong，Cui Yanbin．An adaptive mean shift clustering algorithm based on locality-sensitive hashing［J］．Optik，2012，123(20):1891 －1894．

［2］ D Comaniciu，V M P Ramesh．The variable bandwidths mean shift and data-driven scale selection［J］．IEEE Int．Conf．Comput．Vis，2001，(1):438 －445．

［3］ H B Helbig，M O Ernst．Optimal integration of shape information from vision and touch［J］．Exp．Brain Res．2007，4(179):595 －606．

［4］ Zhou Fangfang，F(xiàn)an Xiaoping．Designing transfer function based on adaptive bandwidth mean shift clustering algorithm［J］．Information and Control，2007，36(5):585 －591．(in Chinese)周芳芳，樊曉平．基于自適應(yīng)帶寬均值漂移聚類算法設(shè)計(jì)傳遞函數(shù)［J］．信息與控制，2007，36(5):585－591．

［5］ Lei Lin．Adaptive pixon represented segmentation(APRS)for 3D MR brain images based on mean shift and Markov random fields［J］．Pattern Recognition Letters．2011:1036－1043

［6］ Zhang Xinhong．An adaptive mean shift clustering algorithm based on locality-sensitive hashing［J］．Optik．2012:1891－1894．

［7］ Yuan Shengzhi，Xie Xiaofang．Bandwidth-adaptive tracking algorithm based on Kalman-mean shift method［J］．Laser＆ Infraded，2009，39(5):558 －561．(in Chinese)袁勝智，謝曉方．一種基于Kalman-mean shift的自適應(yīng)跟蹤算法［J］．激光與紅外，2009，39(5):558 －561．

［8］ Y Cheng，Mean shift，mode seeking，and clustering［J］．IEEE Trans．Pattern Anal．Machine Intell，1995，17:790－799．

［9］ Gan Wenyan，Li Deyi．Hierarchical clustering based on kernel density estimation［J］．Journal of System Simulation，2004，16(2):302 －307．(in Chinese)淦文燕，李德毅．基于核密度估計(jì)的層次聚類算法［J］．系統(tǒng)仿真學(xué)報(bào)，2004，16(2):302 －307．

［10］ Hong MingJian．Study on the Adaptive Histogram Modification ForImage Enhancement［D］．Chongqing:Chongqing University，2002，4．(in Chinese)洪明堅(jiān)．圖像增強(qiáng)的自適應(yīng)直方圖修正算法研究及其應(yīng)用［D］．重慶:重慶大學(xué)，2002，4．