區(qū)間模糊譜聚類圖像分割方法*

劉漢強(qiáng)，張 青

(陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710119)

1 引言

圖像分割是計(jì)算機(jī)視覺領(lǐng)域的重要組成部分[1,2]。圖像分割算法有很多種，包括基于閾值的分割方法、基于聚類的分割方法和基于區(qū)域的分割方法等。聚類分析是一種將研究對象劃分為相對同質(zhì)的類或者簇的統(tǒng)計(jì)分析方法[3]。由于無監(jiān)督的特性，聚類分析已經(jīng)被廣泛應(yīng)用于模式識別、數(shù)據(jù)挖掘、計(jì)算機(jī)視覺等很多領(lǐng)域[4]。基于聚類的圖像分割是一種常用的圖像分割方法，并已得到廣泛應(yīng)用。譜聚類算法[5,6]是一種更加有效的聚類算法，與傳統(tǒng)的聚類算法相比，它能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解。譜聚類是建立在譜圖理論基礎(chǔ)之上的，首先根據(jù)給定的樣本數(shù)據(jù)集構(gòu)造數(shù)據(jù)間的相似性矩陣，進(jìn)而計(jì)算該矩陣的特征值和特征向量，然后選擇合適的特征向量對不同的數(shù)據(jù)點(diǎn)進(jìn)行聚類。經(jīng)典的譜聚類算法有2000年Shi和Malik[7]提出的SM算法、2001年Zha等人[8]提出的基于二分圖上的譜聚類算法以及2002年Ng等人[9]提出的k-way劃分的NJW算法等。

譜聚類的優(yōu)點(diǎn)是直接對相似性矩陣進(jìn)行計(jì)算，不需要樣本服從特定分布，但是傳統(tǒng)的譜聚類算法仍存在著一些問題。首先，譜聚類算法的關(guān)鍵是構(gòu)造相似性矩陣，傳統(tǒng)的相似性度量采用高斯核函數(shù)，然而這個(gè)度量存在明顯的缺陷，即對高斯核函數(shù)中的尺寸參數(shù)σ的選取非常敏感，該參數(shù)很難選取，并且基于歐幾里得的高斯核相似性度量無法完全反映復(fù)雜數(shù)據(jù)集的空間分布特點(diǎn)[10]。因此，如何選取合適的相似性度量成為譜聚類算法的關(guān)鍵問題，也是一大挑戰(zhàn)。很多人試圖改變相似性測度模型以提高分割精度，Chapelle等人[11]以高斯核函數(shù)為基礎(chǔ)改進(jìn)相似性測度,其中采用了 Dijkstra算法求最短路徑。Kim等人[12]通過引進(jìn)一種半監(jiān)督學(xué)習(xí)技術(shù)改進(jìn)了相似性測度模型。Zhao等人[13]利用模糊C-均值聚類得到的劃分矩陣提出了模糊相似性度量。以上這些算法通過改進(jìn)相似性測度的方法在一定程度上改進(jìn)了分割效果。另外，由于譜聚類算法屬于圖論的范疇，所以不可避免地會存在圖論分割圖像的缺點(diǎn)：圖像分割是基于像素級別的，隨著像素點(diǎn)的增加，計(jì)算復(fù)雜度會越來越高。為了降低時(shí)間復(fù)雜度，提高運(yùn)算效率，F(xiàn)owlkes等人[14]提出了采樣可近似估算鄰接矩陣和特征向量的Nystr?m算法。

由于人的視覺特性和數(shù)字圖像本身所具有的模糊性，使得圖像分割問題呈現(xiàn)出典型的結(jié)構(gòu)不良問題，模糊集理論[15,16]具有描述不良問題的能力，所以將模糊理論引人圖像分割中，可以獲得更好的圖像分割效果。模糊理論通過隸屬度函數(shù)來描述樣本對不同類別的隸屬程度，不但描述了樣本的劃分特性，而且體現(xiàn)出了樣本與各劃分類之間的關(guān)聯(lián)程度。目前比較經(jīng)典的算法是基于目標(biāo)函數(shù)的模糊C均值聚類算法FCM(FuzzyC-Means)。但是FCM在處理噪聲、參數(shù)等不確定因素時(shí)結(jié)果不夠理想，隨后人們引入二型模糊集[17,18]概念。Hwang和Rhee[19]在對二型模糊聚類研究的基礎(chǔ)上，用兩個(gè)不同的模糊指數(shù)構(gòu)造隸屬度區(qū)間，提出了區(qū)間二型模糊C均值聚類IT2FCM(Interval-valued Type-2 FuzzyC-Means clustering)方法。二型模糊集的引入對FCM算法性能有了一定的提升，對模糊聚類在圖像分割中的應(yīng)用也將有進(jìn)一步的提升。針對傳統(tǒng)的譜聚類算法相似性測度不易構(gòu)造和計(jì)算復(fù)雜度高等問題，本文提出了一種區(qū)間模糊譜聚類圖像分割方法，通過引入?yún)^(qū)間模糊集，構(gòu)造有效的區(qū)間模糊相似性測度，提高譜聚類的算法性能。此外，由于圖像中灰度值的變化范圍是有限的，僅在[0,255]，因此區(qū)間模糊相似性測度是建立在圖像的灰度直方圖上，降低了所提方法的時(shí)間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，本文方法既能保證圖像目標(biāo)的完整性，還能體現(xiàn)出圖像中的細(xì)節(jié)信息。

2 譜聚類理論

譜聚類的理論基礎(chǔ)是圖譜理論，將圖像看成是一種基于某種相似性的無向加權(quán)圖G=(V,E)，其中，V代表一個(gè)樣本在圖中的頂點(diǎn)，E為連接頂點(diǎn)的邊，w是邊上的權(quán)值。圖譜理論涉及到圖的相似性矩陣的譜和圖的Laplace矩陣的譜，因此構(gòu)造鄰接矩陣是非常關(guān)鍵的步驟。應(yīng)用譜聚類進(jìn)行圖像分割時(shí)，一般需構(gòu)造圖像中像素之間的相似性矩陣，因此該相似性矩陣的存儲和有效性對最終的分割結(jié)果至關(guān)重要。比較經(jīng)典的譜聚類方法是Shi和Malik[7]提出的SM算法以及Ng等人[9]提出的k-way劃分的NJW算法。不同準(zhǔn)則函數(shù)的選取對應(yīng)于譜聚類有著不同的實(shí)現(xiàn)方法，但是基本框架都是一致的，以NJW算法為例，基本步驟如下：

(1)根據(jù)樣本間的某種相似性測度構(gòu)造相似性矩陣W，傳統(tǒng)譜聚類基本都是基于歐氏距離的高斯核函數(shù)來度量樣本數(shù)據(jù)點(diǎn)之間的相似性，構(gòu)造相似性矩陣W。圖像像素信息為X=(x1,x2,…,xn)，像素間的相似性如下所式：

(1)

其中,σ為尺度參數(shù)。

(2)構(gòu)造拉普拉斯矩陣L=D-1/2WD-1/2，其中D為度矩陣，對角元素為:

(2)

(3)計(jì)算L的前k個(gè)特征值對應(yīng)的特征向量vi(必要時(shí)進(jìn)行正交化)，構(gòu)造矩陣：

V=[v1,v2,…,vk]

(3)

(4)將V的行向量轉(zhuǎn)化為單位向量，得到矩陣Y。

(4)

(5)把Y中的每行當(dāng)做k維空間中的點(diǎn)，用聚類算法進(jìn)行聚類，所對應(yīng)的每一行的分類就是原始數(shù)據(jù)的劃分。

3 基于區(qū)間模糊相似性的譜聚類圖像分割

譜聚類應(yīng)用于圖像分割時(shí)，相似性矩陣的存儲和有效性是一個(gè)非常關(guān)鍵的問題。此外，如果能夠更好地利用圖像的灰度信息以及區(qū)間模糊的細(xì)節(jié)信息，則能夠提高譜聚類的分割性能。鑒于此，本文提出一種基于區(qū)間模糊相似性的譜聚類圖像分割方法。

3.1 區(qū)間模糊聚類理論知識

1975年，Zadeh教授[18]提出了二型及多型模糊集的概念。其中二型模糊集中的元素由[0,1]擴(kuò)展為一型模糊集，取值范圍從二維空間延伸到了三維空間，因此具有更強(qiáng)處理不確定性的能力。區(qū)間二型模糊集合是一類特殊的二型模糊集合，其次隸屬度值都為1。相比一般二型模糊集合，區(qū)間二型模糊集合省略了次隸屬度函數(shù)的選擇與運(yùn)算，減少了因維度增加而導(dǎo)致的復(fù)雜度增加，所以在實(shí)際生活中得到了更加廣泛的應(yīng)用。由于區(qū)間二型模糊集合的運(yùn)算復(fù)雜度小，并且具有二型模糊集處理不確定性的特點(diǎn)。

3.2 基于灰度的區(qū)間模糊相似性測度的構(gòu)造

在利用譜聚類進(jìn)行圖像分割時(shí)不可避免需要構(gòu)造像素間的相似性測度，此時(shí)計(jì)算時(shí)間復(fù)雜度高，容易降低運(yùn)算效率。一幅圖像至多有256個(gè)灰度，灰度直方圖是關(guān)于灰度級分布的函數(shù)，是對圖像中灰度級分布的統(tǒng)計(jì)。因此，圖像中灰度的數(shù)量總是遠(yuǎn)遠(yuǎn)小于圖像的大小，本文利用圖像的灰度直方圖，通過統(tǒng)計(jì)灰度的模糊隸屬度來構(gòu)造基于灰度的區(qū)間模糊相似性測度。

在傳統(tǒng)的模糊聚類算法中，由于單一的模糊加權(quán)指數(shù)m無法針對不同類型的數(shù)據(jù)集得到理想的決策邊界，所以引入多個(gè)模糊加權(quán)指數(shù)的方式構(gòu)造決策邊界。不同的m值對隸屬度函數(shù)的影響不同，同時(shí)也會影響圖像分割的結(jié)果。Hwang等人[19]提出通過兩個(gè)參數(shù)m1和m2來構(gòu)造區(qū)間二型模糊集的主隸屬度函數(shù)，而次隸屬度函數(shù)則通過設(shè)置所有次隸屬度值為1進(jìn)行構(gòu)造。假設(shè)圖像的灰度l屬于[0,255]，該灰度在圖像中出現(xiàn)的頻率用γl來表示，圖像灰度的區(qū)間二型模糊集的上、下模糊隸屬度可以通過不同的m1和m2來得到，將灰度l張成與聚類中心vk同維度的灰度向量l。下面首先介紹m1和m2對應(yīng)的基于灰度的模糊目標(biāo)函數(shù)：

(5)

(6)

通過對模糊C均值目標(biāo)函數(shù)的優(yōu)化方法，可以得到與兩個(gè)模糊指數(shù)對應(yīng)的隸屬度更新公式，依據(jù)此更新公式，我們構(gòu)造了基于灰度的上下模糊隸屬度函數(shù)，即:

(7)

(8)

(9)

最終，降型后的模糊隸屬度為：

(10)

利用式(10)得到隸屬度矩陣uil，可以構(gòu)造基于灰度的區(qū)間模糊相似性測度:

Sll′=max({min(uil,uil′)}i=1,2,…,C)

(11)

3.3 基于區(qū)間模糊相似性測度的譜聚類圖像分割

根據(jù)構(gòu)造的基于區(qū)間模糊相似性測度，可以構(gòu)造圖像灰度值之間的帶權(quán)無向圖，因此可以采用規(guī)范切準(zhǔn)則對該圖進(jìn)行劃分。由于規(guī)范切準(zhǔn)則的譜放松解位于拉普拉斯矩陣(L=D-1/2SD-1/2，D為度矩陣)的前k個(gè)最大特征值對應(yīng)的特征向量張成的子空間上，這樣做將原問題轉(zhuǎn)換為求解矩陣的特征值和特征向量的問題。

通過本節(jié)對相關(guān)技術(shù)的分析，本文算法步驟如下：

輸入：待分割的圖像I，聚類數(shù)目C，模糊系數(shù)m=2，初始化中心，參數(shù)m1和m2。

輸出：圖像的分割結(jié)果。

步驟1讀入圖像I，計(jì)算灰度直方圖，直方圖中用γl表示出每個(gè)灰度出現(xiàn)的頻率。

步驟2利用參數(shù)m1和m2計(jì)算上下隸屬度，并通過KM降型算法[20]迭代計(jì)算聚類中心的區(qū)間值[vL,vR]和模糊隸屬度的區(qū)間值[μL,μR]，并最終得到降型后的區(qū)間模糊隸屬度和聚類中心。

步驟3利用式(11)得到相似性矩陣S并構(gòu)造拉普拉斯矩陣L。

步驟5將F的每一行看成是Rk空間中的一個(gè)點(diǎn)，使用k均值聚類算法或其它聚類算法將其聚為C類，所對應(yīng)的每一行的分類就是原始數(shù)據(jù)的劃分。

步驟6根據(jù)上一步的劃分結(jié)果得到輸入圖像最終的分割結(jié)果。

4 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的區(qū)間模糊譜聚類圖像分割方法的正確性和有效性，選取了Berkeley圖像庫中的5幅圖像(#8068，#2009_005130，#163014，#118035，#24063) 進(jìn)行對比實(shí)驗(yàn)。對比方法包括本文方法、FCM算法、Nystr?m算法。Nystr?m算法的歐氏距離中的參數(shù)σ影響了實(shí)驗(yàn)的穩(wěn)定性。本文方法中不同的參數(shù)(m1,m2)對分割結(jié)果的影響不同，所以在實(shí)驗(yàn)中選取了四組不同的參數(shù)值([1.5,2]，[2,3]，[3,5]，[5,5])來進(jìn)行對比。

從圖1～圖5的分割結(jié)果可以看出，F(xiàn)CM算法和Nystr?m譜聚類算法獲得的分割結(jié)果錯(cuò)分比較多，并且Nystr?m算法在不同的參數(shù)σ下的分割效果差異較大，導(dǎo)致其穩(wěn)定性不好，影響了分割結(jié)果。特別是#8068圖使用Nystr?m譜聚類算法分割得到的結(jié)果背景錯(cuò)分嚴(yán)重，F(xiàn)CM算法沒有分出目標(biāo)倒影在水中的細(xì)節(jié)，而本文方法的第三小組(參數(shù)m1,m2取值[3,5])將細(xì)節(jié)處理得很好；#118035圖使用Nystr?m譜聚類算法分割得到的屋頂十字架有錯(cuò)分；#24063圖使用FCM算法分割得到的背景右上角有明顯的錯(cuò)分，而本文方法的第三小組(參數(shù)m1,m2取值[3，5])背景分割明確，沒有出現(xiàn)錯(cuò)分。本文方法由于引入了區(qū)間模糊隸屬度構(gòu)造相似性測度，更好地處理了圖像細(xì)節(jié)的劃分，從分割結(jié)果的整體性和準(zhǔn)確性上都獲得了比較理想的效果。表1中展示了5幅圖像使用FCM算法、Nystr?m算法以及本文方法(參數(shù)m1,m2取值[3,5])所用時(shí)間對比。

Figure 1 Comparison of segmentation results on #8068(three clusters)圖1 各算法分割#8068圖像結(jié)果對比圖(分3類)

Figure 2 Comparison of segmentation results on #2009_005130(three clusters)圖2 各算法分割#2009_005130圖像結(jié)果對比圖(分3類)

Figure 3 Comparison of segmentation results on #163014(three clusters)圖3 各算法分割#163014圖像結(jié)果對比圖(分3類)

Figure 4 Comparison of segmentation results on #118035(three clusters)圖4 各算法分割#118035圖像結(jié)果對比圖(分3類)

Figure 5 Comparison of segmentation results on #24063(three clusters) 圖5 各算法分割#24063圖像結(jié)果對比圖(分3類)

通過以上各算法的時(shí)間對比可以看出,本文方法要明顯優(yōu)于譜聚類中的Nystr?m算法，由于Nystr?m算法本身就是為了提高譜聚類算法的運(yùn)算速度而提出來的優(yōu)化算法，所以本文方法在運(yùn)算速度方面要優(yōu)于傳統(tǒng)的聚類算法。

5 結(jié)束語

本文提出了一種區(qū)間模糊譜聚類圖像分割方法。首先將輸入的彩色圖像轉(zhuǎn)換成灰度圖像，然后利用區(qū)間模糊理論獲得直方圖的區(qū)間模糊隸屬度，進(jìn)而構(gòu)造相似性測度，最后利用該測度構(gòu)造的拉普拉斯矩陣的特征向量進(jìn)行聚類并獲得最終的分割結(jié)果。實(shí)驗(yàn)結(jié)果表明，本文方法加快了圖像分割的速度并提高了算法的效率，獲得了比較理想的分割結(jié)果。此外，如何快速構(gòu)造相似性測度來糾正一些傳統(tǒng)算法對圖像的錯(cuò)分現(xiàn)象，仍然是下一步研究的重點(diǎn)。