區間模糊譜聚類圖像分割方法*

劉漢強，張 青

(陜西師范大學計算機科學學院,陜西 西安 710119)

1 引言

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

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

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

2 譜聚類理論

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

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

(1)

其中,σ為尺度參數。

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

(2)

(3)計算L的前k個特征值對應的特征向量vi(必要時進行正交化)，構造矩陣：

V=[v1,v2,…,vk]

(3)

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

(4)

(5)把Y中的每行當做k維空間中的點，用聚類算法進行聚類，所對應的每一行的分類就是原始數據的劃分。

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

譜聚類應用于圖像分割時，相似性矩陣的存儲和有效性是一個非常關鍵的問題。此外，如果能夠更好地利用圖像的灰度信息以及區間模糊的細節信息，則能夠提高譜聚類的分割性能。鑒于此，本文提出一種基于區間模糊相似性的譜聚類圖像分割方法。

3.1 區間模糊聚類理論知識

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

3.2 基于灰度的區間模糊相似性測度的構造

在利用譜聚類進行圖像分割時不可避免需要構造像素間的相似性測度，此時計算時間復雜度高，容易降低運算效率。一幅圖像至多有256個灰度，灰度直方圖是關于灰度級分布的函數，是對圖像中灰度級分布的統計。因此，圖像中灰度的數量總是遠遠小于圖像的大小，本文利用圖像的灰度直方圖，通過統計灰度的模糊隸屬度來構造基于灰度的區間模糊相似性測度。

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

(5)

(6)

通過對模糊C均值目標函數的優化方法，可以得到與兩個模糊指數對應的隸屬度更新公式，依據此更新公式，我們構造了基于灰度的上下模糊隸屬度函數，即:

(7)

(8)

(9)

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

(10)

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

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

(11)

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

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

通過本節對相關技術的分析，本文算法步驟如下：

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

輸出：圖像的分割結果。

步驟1讀入圖像I，計算灰度直方圖，直方圖中用γl表示出每個灰度出現的頻率。

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

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

步驟5將F的每一行看成是Rk空間中的一個點，使用k均值聚類算法或其它聚類算法將其聚為C類，所對應的每一行的分類就是原始數據的劃分。

步驟6根據上一步的劃分結果得到輸入圖像最終的分割結果。

4 實驗分析

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

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

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

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

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

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

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

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

5 結束語

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