基于改進譜聚類的圖像分割算法

關昕，周積林

1.遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105

2.遼寧工程技術大學研究生學院，遼寧葫蘆島 125105

基于改進譜聚類的圖像分割算法

關昕1，周積林2

1.遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105

2.遼寧工程技術大學研究生學院，遼寧葫蘆島 125105

針對傳統譜聚類算法應用于圖像分割時僅采用特征相似性信息構造相似性矩陣，而忽略了像素分布的空間臨近信息的缺陷，提出一種新的相似性度量公式——加權歐氏距離的高斯核函數，充分利用圖像特征相似性信息和空間臨近信息構造相似性矩陣。在譜映射過程中，采用Nystrom逼近策略近似估計相似性矩陣及其特征向量，大大減少了求解相似性矩陣的運算復雜度，降低了內存消耗。對得到的低維向量子空間采用一種新型的聚類算法——近鄰傳播聚類算法進行聚類，避免了傳統譜聚類采用K-means算法對初始值敏感，易陷入局部最優的缺陷。實驗表明該算法獲得了比傳統譜聚類算法更好的分割效果。

譜聚類；空間臨近信息；相似性矩陣；Nystrom逼近策略；近鄰傳播聚類算法

1 引言

在計算機視覺理論中，圖像分割與特征提取，目標識別構成了計算機視覺領域從低到高的三個層次，特征提取與目標識別都以圖像分割為基礎，分割的好壞直接影響到后續特征提取和目標識別的質量[1]。由于圖像的復雜多變性，目前還沒有一種算法能夠通用于所有的圖像，都是針對具體問題采用具體的算法[2]。因此，圖像分割算法的研究越來越受到人們的重視。傳統的圖像分割方法可以分為三類：基于區域的分割、基于邊界的分割和基于紋理的分割。近幾十年來，隨著一些新理論和新方法的提出和應用，圖像分割方法層出不窮，其中比較有代表性的是基于聚類、遺傳算法、神經網絡、支持向量機、水平集和數學形態學的分割方法。近年來，基于圖論的譜聚類算法由于其良好的特性，已得到越來越多的關注，成為一個新的研究熱點。

譜聚類是基于譜圖劃分理論[3-6]的一種新型的聚類算法，它是一種點對聚類算法，其本質是將聚類問題轉化為圖的最優劃分問題。該算法能在任意形狀的樣本空間進行聚類，能快速收斂到全局最優解，避免了傳統的聚類如K-means算法只能在凸球形樣本空間進行聚類而在非凸球形樣本空間容易陷入局部最優解的缺點。具有識別非高斯分布的能力，較其他聚類算法具有明顯的優勢，目前已經廣泛應用于文本挖掘、網頁劃分、語音識別、VLSI設計等領域。譜聚類應用于圖像分割，通常能取得很好的分割效果，但同時它也有著自身的缺陷——相似性矩陣構造的局限性，存儲和計算相似性矩陣的高復雜度，以及子空間聚類不穩定。文獻[7]中提出基于路徑的相似性度量，但對邊界點過于敏感，效果不理想；文獻[8]提出基于密度敏感的相似性度量，但當位于高密度區的兩個樣本數據點穿過的路徑很長時，效果不明顯，并且最終采用K-means聚類簡化后的向量空間，造成聚類結果不穩定。本文以譜聚類算法為基礎，考慮上述缺陷，通過三方面對譜聚類進行了改進，并應用于圖像分割。

2 譜聚類算法

譜聚類算法將圖像看成是一種基于某種相似性的無向加權圖G=(V，E)，其中V代表一個數據樣本在無向加權圖中的頂點，E為頂點間的邊，基于某種相似性對其賦予權值w。由于相似性矩陣包含了圖像所有的數據結構信息，基于某種劃分準則來進行聚類劃分，使得劃分的子類之間具有較高的相似性，不同子類之間具有較低的相似性。一般的，劃分準則可分為二路劃分準則和多路劃分準則。文獻[9]中簡單介紹了常見的二路劃分準則有最小劃分準則（Minimum cut），規范割集準則（Normalized cut），比例割集準則（Ratio cut），平均割集準則（Average cut），最大最小劃分準則（Min-max cut）。基于二路劃分準則的譜聚類算法一般通過迭代對樣本數據進行聚類。文獻[5]通過研究證明，使用更多的特征向量，直接計算多路分割將會得到更好的分割效果。其中比較經典的是由Meila和Shi提出的MS算法[10]以及Ng等人提出的NJW算法[11]。本文便是采用多路規范割集準則[12]（Multi way Normalized cut）對圖像進行分割。由于不同準則函數的選取和不同的譜映射方法，譜聚類算法又有著不同的實現方法，但基本框架都是一致的，以NJW算法為例，其步驟如下：

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

其中σ為尺度參數。

（2）構造拉普拉斯矩陣L=D-1/2WD-1/2，其中D是對角矩陣，對角元素為d：

計算拉普拉斯矩陣L的前k個最大特征向量xi，構造一個低維向量子空間X：

（3）將矩陣X的行向量轉化成單位向量構造矩陣Y。

（4）將矩陣Y中的每一行看作是子空間中的一個點，對其應用K均值聚類進行劃分。

（5）如果矩陣Y第y行被劃分到第j類，則對應的像素點也被劃分到第j類。

3 改進的譜聚類算法

由于譜聚類能在任意樣本空間進行聚類并能很好地收斂到全局最優解，目前已廣泛應用于圖像分割領域。伴隨著這些優點的同時，譜聚類的缺陷也制約著它的發展。本文根據傳統譜聚類的缺陷，提出了三點改進，彌補了傳統譜聚類的不足，經實驗驗證，得到了比傳統譜聚類更好的分割效果。

3.1 加權歐氏距離構建相似性矩陣

傳統譜聚類利用高斯核函數來構建樣本數據點之間的相似性，具體構建方法見第2章步驟（1），公式（1）僅僅考慮了圖像的特征相似性信息，用像素值之間歐式距離的大小來度量相似性，距離越大相似性越小，距離越小相似性越大，忽略了樣本數據點之間的空間鄰近信息，并且可能會夸大某些較大像素值的作用。由于空間鄰近信息和圖像像素值信息具有不同的量綱，對于不同性質的指標直接相加不能正確反映不同作用的綜合結果，而直接相乘無疑是加大了計算的復雜度，如文獻[13]提出的同時兼顧空間鄰近信息和圖像特征相似性信息的相似性度量公式：

X=(x1,x2,…,xn)為圖像像素值信息，Y=(y1,y2,…,yn)代表樣本的空間位置信息。該公式引入了一個新的尺度參數σv，不僅增加了算法對初始參數的敏感性，而且計算機計算一次指數運算所運用的時間是乘積運算的30倍多，運算時間消耗巨大。為了能同時利用樣本像素信息和空間鄰近信息，本文定義加權歐氏距離的相似性度量函數為：

其中ak為權重，d維向量z表征每一個樣本點的信息，假設有n個樣本點：z1=(z11,z12,…,z1d)，z2=(z21,z22,…,z2d)，…，zn=(zn1，zn2，…，znd)，向量中包括其像素值信息和空間位置信息。如何構造這個權重才能達到理想的效果，本文考慮到同時消除量綱和變量自身較大值所起作用的影響，對所有樣本數據點相同維數的同屬性分量進行標準化，即對z11，z21，…，zn1標準化得到其平均值e1和方差s1，對z12，z22，…，zn2標準化得到其平均值e2和方差s2，依照同樣方法，共得到d個平均值ek(k=1，2，…，d)和d個方差sk(k=1，2，…，d)，定義相似性矩陣度量公式為：

其中zik表示第i個樣本點第k維屬性，簡化可得：

σ為尺度參數，將方差的倒數看作是一個權重，便得到本文所定義的一個加權歐氏距離的相似性度量公式。

3.2 Nystrom逼近策略

由于圖像數據的復雜龐大性，計算和存儲相似性矩陣給計算機運算帶來了極大的困擾。對于一個有n個像素點的圖像來說，其相似性矩陣異常龐大，空間復雜度是O(n2)，并且計算相似性矩陣的特征向量又進一步增加了運算量，根據文獻[14]，引入了Nystrom逼近策略來間接求解相似性矩陣的特征向量，降低譜聚類算法的計算復雜度和計算機內存消耗。

其基本思想是用隨機采樣的方式獲得一定的采樣點，用采樣點與未采樣點之間的相似性來近似估計未采樣點之間的相似性。當采樣點的規模能足以反應圖像內在特征時，隨機采樣隨機性的負面影響便可得到有效的抑制，此時算法穩定并且能取得較好的效果。本文隨機選取圖像像素點的1%作為采樣點。當采樣點低于1%時，不能很好地代表圖像的內在特征，圖像最后的分割效果一般；當采樣點高于1%時，能取得更好的分割效果，但空間和時間復雜度的增加相對于分割效果的增加來說，顯得有點得不償失。

設原始圖像像素個數為n，從原始圖像中隨機采樣m個像素點(m?n)，則相似性矩陣W可分解為：其中A是用公式（8）計算的m個采樣點之間的相似性矩陣，B是m個采樣點與剩下的(n-m)個像素點之間的相似性矩陣。C代表剩余的(n-m)個像素點之間的相似性矩陣，由于剩余像素點數非常繁多，計算矩陣C的運算量相當大。現將矩陣A對角化得A=UΛUT，利用矩陣A和矩陣B來近似逼近相似性矩陣W和其特征向量：

為了使Nystrom逼近策略能夠用于求解基于多路規范割集準則的相似性矩陣，受文獻[15]啟發，先采用Nystrom逼近策略計算相似性矩陣A和B，利用矩陣A和矩陣B計算W每行元素的和：

其中I為一個單位列矩陣。采用如下公式逼近D-1/2WD-1/2的值：

3.3 近鄰傳播聚類算法（Affinity Propagation）

傳統譜聚類算法利用相似性矩陣的特征向量構造一個低維向量子空間，這個子空間結構更加明顯。將這個子空間，也就是第2章步驟（4）得到的矩陣Y的每一行看成是一個樣本點，一般利用K-means算法對這個子空間進行聚類。由于K-means算法事先不能確定聚類數目，需要人為初始化，對初始值敏感，不同的初始值可能會得到不同的聚類效果，且容易陷入局部最優，分割效果不穩定。針對這些問題，本文使用了一種快速高效的新型聚類算法——AP算法[16]。它是Frey和Dueck于2007年提出的一種新的聚類算法，以樣本之間的相似性矩陣為輸入，輸出的是聚類中心和樣本與聚類中心的所屬度關系，能夠很好地解決非歐空間和大規模稀疏矩陣計算問題，快速高效[17]。

本文中將得到的矩陣Y的每一行看作一個數據點，AP算法中相似度采用歐氏距離來度量：

自相似性一般取一個常數，本文取相似性矩陣的均值：

近鄰傳播算法在起始階段將所有的樣本點都看作潛在的聚類中心，并在數據點之間傳遞兩種不同的消息：r(i，j)（responsibility）是從樣本點yi發送到候選聚類中心yj的數值，用來表示yj作為yi聚類中心的代表程度，a(i，j)（availability）是從候選聚類中心yj發送到樣本點yi的數值，用來表示樣本yi選擇yj作為聚類中心的合適程度。算法迭代過程中，這兩個消息交替更新，且迭代初始化時，a(i，j)=0，更新公式為：

進行一次消息更新，也就是算法的一次迭代過程。為了避免AP算法發生大幅度震蕩，引入阻尼系數λ∈[0，1)，當取不同的阻尼系數時，迭代次數和迭代過程中數值的波動都會有很大不同。當選取的阻尼系數越小時，迭代次數會減少，但是迭代過程中數值的波動會很大，當圖像較大時，難于收斂。當阻尼系數取值較大時，迭代次數會增加，但總體會平穩收斂，不會有較大波動，本文取值為0.9。代表矩陣R(r(i，j))和適選矩陣A(a(i，j))計算如下：

t代表迭代次數，使r(i，j)+a(i，j)取得最大值的樣本yj即是樣本yi的聚類中心。

基于上述改進，本文設計的算法步驟如下：

（1）隨機抽取1%的樣本，利用公式（8）計算相似性矩陣A和B，利用公式（15）逼近相似性矩陣W的特征向量。

（2）取k個最大特征值對應的特征向量，構造矩陣X。

（3）將矩陣X的行向量轉化成單位向量構造矩陣Y。

（4）將矩陣Y中的每一行看作是子空間中的一個點，對其應用近鄰傳播聚類算法進行劃分。

（5）如果矩陣Y第y行被劃分到第j類，則對應的像素點也被劃分到第j類。

4 實驗與分析

本文是對傳統譜聚類算法的改進，為了驗證本文算法的有效性，分別應用本文算法與傳統譜聚類算法對圖像進行分割，比較分割效果和分割性能。實驗中，尺度參數設置為σ=100，AP算法中阻尼系數λ取值為0.9，迭代次數t為40。圖像方面，均選擇分辨率為255×255的常用分割圖像：第一組選取背景較簡單的Lena圖像，第二組選取前景較清晰，目標明確的Cameraman圖像，第三組選取目標與背景對比不強烈的Snake圖像。分割后的圖像效果如圖1（a）～（c）所示，其中第一列是原始圖像，第二列是采用傳統譜聚類算法進行分割后的圖像，第三列是采用本文改進后的譜聚類算法進行分割后的圖像。

圖1 圖像分割效果

主觀上，從分割效果上來看，對于背景較簡單的Lena圖像，兩種方法的分割效果差不多，但本文的改進算法由于加入了空間鄰近信息，對于頭發，帽子等紋理較復雜的區域取得了更加細膩的分割效果，而傳統譜聚類算法對此方面的分割比較粗糙；對于前景較清晰，目標明確的Cameraman圖像和背景與目標對比不強烈的Snake圖像，由于傳統的譜聚類最終采用K-means算法對簡化了的向量子空間進行聚類，對初始值較敏感，產生了較多的噪點，在Cameraman圖像中背景的天空和Snake圖像中的石塊均出現模糊現象，甚至在Snake圖像中出現錯分割，分割效果不理想，而使用本文改進譜聚類算法進行分割，區域一致性和邊界的準確性方面得到了很大提高。

客觀定量分析上，依據算法性能方面考慮，本文從兩方面來評估算法性能。

（1）從運行時間方面評估：分別對比傳統譜聚類和本文算法的運行時間，對每幅圖像分別實驗20次，記錄兩種算法對上述三幅圖像的平均分割時間。運行時間如表1所示。

表1 兩種分割算法運行時間對比s

從表1中的數據可以看出，本文算法相比傳統譜聚類在運行時間上大大縮短。

（2）為了定量地評估本文算法在圖像分割方面的性能優勢，參考文獻[1]中圖像分割評價準則，本文從區域內部均勻性、區域間對比度這兩方面來進行客觀定量的評價。其中區域內部均勻性是指分割后的圖像各個區域內部元素之間相似性，區域間對比度是指分割后圖像各區域之間的相異性，這兩個函數指標均是數值越大，代表的分割效果越好。指標數據如表2所示。

表2 兩種算法對分割后圖像的定量對比

從表2中數據可以看出，相比傳統算法，本文算法分割后的圖像，在區域內部均勻性和區域間對比度均得到了提高，取得了更好的分割效果。

就總體而言，本文算法在分割效果和算法性能方面都有了提升，分割效果更好，算法實用性更強。

5 結束語

本文根據傳統譜聚類的不足，綜合考慮了像素的空間鄰近信息和特征相似性信息，定義了一個新的相似性矩陣的計算公式，在譜映射過程采用Nystrom逼近策略，大大減少了譜聚類的運算復雜度，最后對得到的低維向量子空間采用最新提出的近鄰傳播聚類算法進行分類，避免了K-means算法對初始值敏感和分割效果不穩定的缺陷。實驗表明，新算法不僅分割效果穩定精確，而且運行時間短，性能優越。

由于本文算法仍然采用高斯核函數來度量樣本點之間的相似性，尺度參數σ為實驗選取，如何消除人為因素，自動確定σ或者探索一種新的構建相似性矩陣的方法將是以后研究的重點。

[1]章毓晉.圖像分割[M].北京：科學出版社，2001.

[2]Zhang Tianxu，Peng Jiaxiong，Li Zongjie.An adaptive image segmentation method with visual nonlinearity characteristics[J].IEEE Trans on Systems，Man，and Cybernetics，1996，26（4）：619-627.

[3]Shi Jianbo，Malik J.Normalized cut and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888-905.

[4]Odobez J M，Gatica-perez D，Guillemot M.Video shot clustering using spectral methods[C]//Workshop on Content Based Multimedia Indexing（CBMI），Rennes，2003.

[5]Malik J，Belongie S，Leung T，et al.Contour and texture analysis for image segmentation[J].International Journal of Computer Vision，2001，43（1）：7-27.

[6]Chung F R K.Spectral graph theory[M].[S.l.]：American Mathematical Society，1997：227-275.

[7]Chang H，Yeung D Y.Robust path-based spectral clustering[J].Pattern Recognition，2008，41（1）：191-203.

[8]王玲，薄列峰，焦李成.密度敏感的譜聚類[J].電子學報，2007，35（8）：1577-1581.

[9]蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計算機科學，2008，35（7）：14-18.

[10]Meila M，Shi J.Learning segmentation by random walks[C]// Advances in Neural Information Processing Systems，Vancouver，Canada，2001：873-879.

[11]Ng A Y，Jordan M I，Weiss Y.On spectral clustering：analysis and an algorithm[C]//dietterich T G，Becker S，Ghahramani.Advances in Neural Information Processing Systems.Cambridge，MA：MIT Press，2002：849-856.

[12]Liang Xu.Multi way cuts and spectral clustering[R].2003.

[13]Chen Jiawei，Chen Kuanhung，Wang Jinnshyan，et al.A performance aware IP core design for multimode transform coding using scalable-DA algorithm[C]//Proceedings of International Symposium on Circuits and Systems（ISCAS），2006：21-24.

[14]Fowlkes C，Belongie S，Fan Chung，et al.Spectral grouping using the Nystrom method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（2）：214-225.

[15]楊學鑫.改進的譜聚類圖像分割方法研究[D].西安：西安電子科技大學，2010．

[16]Frey B J，Dueck D.Clustering by passing messages between data points[J].Science，2007，315（5814）：972-976.

[17]管仁初，裴志利，時小虎，等.權吸引子傳播算法及其在文本聚類中的應用[J].計算機研究與發展，2010，47（10）：1733-1740.

GUAN Xin1,ZHOU Jilin2

1.School of Electronics and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China
2.Institute of Graduate,Liaoning Technical University,Huludao,Liaoning 125105,China

Aiming at the default that when the traditional spectral clustering algorithm is applied to image segmentation, it only uses the feature similarity information to construct similarity matrix and ignores the spatial adjacency information defect of spatial distribution of pixels,this paper presents a new similarity measure formula—weighted euclidean distance of the Gaussian kernel function,making full use of image feature similarity information and spatial adjacency information to structure similarity matrix.In the spectral mapping process,using Nystrom approximation strategy to approximate similarity matrix and eigenvectors,it greatly reduces the computational complexity to solve similarity matrix and reduces the memory consumption.This paper applies a new clustering algorithm—Affinity Propagation to the low-dimensional subspace.It avoids the defect that traditional spectral clustering using K-means algorithm can not automatically determine the number of clusters and it is sensitive to initial value and easy to fall into local optimum.The experiments prove that the proposed algorithm obtains better segmentation results than the traditional spectral clustering algorithm.

spectral clustering;spatial adjacency information;similarity matrix;Nystrom approximation;Affinity Propagation（AP）algorithm

A

TP391

10.3778/j.issn.1002-8331.1311-0473

GUAN Xin,ZHOU Jilin.Image segmentation based on improved spectral clustering algorithm.Computer Engineering and Applications,2014,50（21）：184-188.

關昕（1967—），男，副教授，碩士生導師，主要研究方向：網絡安全，圖像處理；周積林（1990—），男，碩士研究生，主要研究方向：圖像處理，模式識別。E-mail：zjl694059781@163.com

2013-12-02

2014-01-23

1002-8331（2014）21-0184-05

CNKI出版日期：2014-07-02，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0473.html