基于改進(jìn)譜聚類的圖像分割算法

關(guān)昕，周積林

1.遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧葫蘆島 125105

2.遼寧工程技術(shù)大學(xué)研究生學(xué)院，遼寧葫蘆島 125105

基于改進(jìn)譜聚類的圖像分割算法

關(guān)昕1，周積林2

1.遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧葫蘆島 125105

2.遼寧工程技術(shù)大學(xué)研究生學(xué)院，遼寧葫蘆島 125105

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

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

1 引言

在計(jì)算機(jī)視覺理論中，圖像分割與特征提取，目標(biāo)識(shí)別構(gòu)成了計(jì)算機(jī)視覺領(lǐng)域從低到高的三個(gè)層次，特征提取與目標(biāo)識(shí)別都以圖像分割為基礎(chǔ)，分割的好壞直接影響到后續(xù)特征提取和目標(biāo)識(shí)別的質(zhì)量[1]。由于圖像的復(fù)雜多變性，目前還沒有一種算法能夠通用于所有的圖像，都是針對(duì)具體問題采用具體的算法[2]。因此，圖像分割算法的研究越來越受到人們的重視。傳統(tǒng)的圖像分割方法可以分為三類：基于區(qū)域的分割、基于邊界的分割和基于紋理的分割。近幾十年來，隨著一些新理論和新方法的提出和應(yīng)用，圖像分割方法層出不窮，其中比較有代表性的是基于聚類、遺傳算法、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、水平集和數(shù)學(xué)形態(tài)學(xué)的分割方法。近年來，基于圖論的譜聚類算法由于其良好的特性，已得到越來越多的關(guān)注，成為一個(gè)新的研究熱點(diǎn)。

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

2 譜聚類算法

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

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

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

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

計(jì)算拉普拉斯矩陣L的前k個(gè)最大特征向量xi，構(gòu)造一個(gè)低維向量子空間X：

（3）將矩陣X的行向量轉(zhuǎn)化成單位向量構(gòu)造矩陣Y。

（4）將矩陣Y中的每一行看作是子空間中的一個(gè)點(diǎn)，對(duì)其應(yīng)用K均值聚類進(jìn)行劃分。

（5）如果矩陣Y第y行被劃分到第j類，則對(duì)應(yīng)的像素點(diǎn)也被劃分到第j類。

3 改進(jìn)的譜聚類算法

由于譜聚類能在任意樣本空間進(jìn)行聚類并能很好地收斂到全局最優(yōu)解，目前已廣泛應(yīng)用于圖像分割領(lǐng)域。伴隨著這些優(yōu)點(diǎn)的同時(shí)，譜聚類的缺陷也制約著它的發(fā)展。本文根據(jù)傳統(tǒng)譜聚類的缺陷，提出了三點(diǎn)改進(jìn)，彌補(bǔ)了傳統(tǒng)譜聚類的不足，經(jīng)實(shí)驗(yàn)驗(yàn)證，得到了比傳統(tǒng)譜聚類更好的分割效果。

3.1 加權(quán)歐氏距離構(gòu)建相似性矩陣

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

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

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

其中zik表示第i個(gè)樣本點(diǎn)第k維屬性，簡(jiǎn)化可得：

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

3.2 Nystrom逼近策略

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

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

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

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

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

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

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

本文中將得到的矩陣Y的每一行看作一個(gè)數(shù)據(jù)點(diǎn)，AP算法中相似度采用歐氏距離來度量：

自相似性一般取一個(gè)常數(shù)，本文取相似性矩陣的均值：

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

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

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

基于上述改進(jìn)，本文設(shè)計(jì)的算法步驟如下：

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

（2）取k個(gè)最大特征值對(duì)應(yīng)的特征向量，構(gòu)造矩陣X。

（3）將矩陣X的行向量轉(zhuǎn)化成單位向量構(gòu)造矩陣Y。

（4）將矩陣Y中的每一行看作是子空間中的一個(gè)點(diǎn)，對(duì)其應(yīng)用近鄰傳播聚類算法進(jìn)行劃分。

（5）如果矩陣Y第y行被劃分到第j類，則對(duì)應(yīng)的像素點(diǎn)也被劃分到第j類。

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

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

圖1 圖像分割效果

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

客觀定量分析上，依據(jù)算法性能方面考慮，本文從兩方面來評(píng)估算法性能。

（1）從運(yùn)行時(shí)間方面評(píng)估：分別對(duì)比傳統(tǒng)譜聚類和本文算法的運(yùn)行時(shí)間，對(duì)每幅圖像分別實(shí)驗(yàn)20次，記錄兩種算法對(duì)上述三幅圖像的平均分割時(shí)間。運(yùn)行時(shí)間如表1所示。

表1 兩種分割算法運(yùn)行時(shí)間對(duì)比s

從表1中的數(shù)據(jù)可以看出，本文算法相比傳統(tǒng)譜聚類在運(yùn)行時(shí)間上大大縮短。

（2）為了定量地評(píng)估本文算法在圖像分割方面的性能優(yōu)勢(shì)，參考文獻(xiàn)[1]中圖像分割評(píng)價(jià)準(zhǔn)則，本文從區(qū)域內(nèi)部均勻性、區(qū)域間對(duì)比度這兩方面來進(jìn)行客觀定量的評(píng)價(jià)。其中區(qū)域內(nèi)部均勻性是指分割后的圖像各個(gè)區(qū)域內(nèi)部元素之間相似性，區(qū)域間對(duì)比度是指分割后圖像各區(qū)域之間的相異性，這兩個(gè)函數(shù)指標(biāo)均是數(shù)值越大，代表的分割效果越好。指標(biāo)數(shù)據(jù)如表2所示。

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

從表2中數(shù)據(jù)可以看出，相比傳統(tǒng)算法，本文算法分割后的圖像，在區(qū)域內(nèi)部均勻性和區(qū)域間對(duì)比度均得到了提高，取得了更好的分割效果。

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

5 結(jié)束語

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

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

[1]章毓晉.圖像分割[M].北京：科學(xué)出版社，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].電子學(xué)報(bào)，2007，35（8）：1577-1581.

[9]蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計(jì)算機(jī)科學(xué)，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，F(xiàn)an Chung，et al.Spectral grouping using the Nystrom method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（2）：214-225.

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

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

[17]管仁初，裴志利，時(shí)小虎，等.權(quán)吸引子傳播算法及其在文本聚類中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展，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.

關(guān)昕（1967—），男，副教授，碩士生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)安全，圖像處理；周積林（1990—），男，碩士研究生，主要研究方向：圖像處理，模式識(shí)別。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