譜聚類圖像分割中相似度矩陣構造研究

李 揚,陸 璐,崔紅霞

(渤海大學 信息科學與技術學院，遼寧 錦州 121000)

譜聚類圖像分割中相似度矩陣構造研究

李 揚,陸 璐,崔紅霞

(渤海大學 信息科學與技術學院，遼寧 錦州 121000)

近年來譜聚類算法廣泛應用于圖像分割領域，而相似度矩陣的構造是譜聚類算法的關鍵。通常傳統的譜聚類算法分割彩色圖像時，僅采用一種顏色空間和距離計算公式構造相似度矩陣，而忽略了不同的顏色空間和距離計算公式構造的相似度矩陣對分割結果的影響，導致譜聚類算法有諸多的局限性。針對這個問題，文中分別采用RGB和HSV顏色空間，以及分別在兩種顏色空間下使用歐氏距離、余弦距離和卡方距離公式，建立不同的相似度矩陣。分析比較不同構造方法的分割效果，得出了最優分割效果的相似度矩陣構造方法，提高了應用譜聚類算法分割彩色圖像的有效性。通過計算性能評價指標查準率和查全率以及分割結果的準確率，驗證了實驗的可靠性和準確性。

圖像分割;譜聚類;相似度矩陣;顏色空間;距離公式

1 概 述

圖像分割是把圖像分成若干個特定的、具有獨特性質的區域并提取出感興趣目標的技術和過程，是由圖像處理轉到圖像分析的關鍵[1]。圖像分割的研究可以追溯到20世紀70年代。截至目前，人們已經提出了許多種不同的圖像分割方法，主要有基于區域的分割方法、基于邊界的分割方法、基于閾值的分割方法、基于水平集的分割方法、基于聚類的分割方法等。其中，基于聚類的圖像分割方法已經被廣泛研究，取得了豐富的研究成果，而譜聚類是一種特殊的聚類方法，在2000年左右被引入到圖像分割領域成為一個有力的分割工具。譜聚類算法以相似度矩陣為基礎，將普通聚類問題轉化為圖的劃分問題。譜聚類算法在聚類時不受樣本空間形狀的限制，在這一點上，譜聚類要優于K-means算法[2]、水平集算法[3]等傳統聚類方法。譜聚類算法在求解時從全局出發，不會陷入局部最優解，同時可以保證不同類間的相似度最小，同一類內的相似度最大。

近年來，譜聚類算法在圖像分割領域取得了廣泛的研究成果，包括彩色圖像分割[4-6]、紋理圖像分割[7-9]、醫學圖像分割[10-11]等，都有譜聚類算法的應用。文獻[12]提出了一種自適應譜聚類算法用于彩色圖像的分割，該算法主要針對自調節譜聚類算法的缺陷，在確定最佳分組數K時，利用本征矢差異來計算，獲得了較好的分割效果。文獻[13]提出了一種新的非局部空間譜聚類的圖像分割算法。在該算法中，首先將非局部空間約束條件下的加權核K均值算法的目標函數進行修正，然后進行歸一化，給出一種新的非局部空間矩陣的構建，以取代正規拉普拉斯矩陣。實驗結果表明，該算法能很好地分割真實圖像，尤其是核磁共振圖像，同時，對圖像中的噪聲具有很好的魯棒性。文獻[14]提出將改進的SLIC的分割方法和基于譜聚類的Nystr?m方法相結合，在分割的第一階段利用改進的SLIC進行分割，然后再利用Nystr?m逼近，使得分割對計算機的內存需求降低，計算復雜度也減小。實驗結果證明了該算法的有效性和魯棒性。

在譜聚類圖像分割算法中，影響譜聚類圖像分割結果的因素有很多，如分割數量、求解過程等，但相似度矩陣是影響分割結果的一個重要因素，相似度矩陣作為譜聚類算法的輸入項，不同的構造方法導致分割的結果也不同，直接影響分割結果的準確性。文中主要利用多種顏色空間和距離計算公式分別構造相似度矩陣，對彩色圖像進行分割，比較和分析分割的效果。

2 算法介紹

2.1 譜聚類圖像分割算法

譜聚類圖像分割算法的本質是將圖像轉化為圖的矩陣表示,使聚類問題轉化為圖的最優劃分問題，是一種點對聚類算法。該算法在構造相似度矩陣W時直接利用原圖像中的像素信息，通過求解矩陣的特征值和特征向量對圖進行劃分，得到分割結果[15]。譜聚類圖像分割算法將圖像中的每個像素看作圖中的各個頂點V，像素之間的相鄰關系作為圖中連接各頂點的邊E，邊E上的權重值W代表像素間的相似度，由此構造一個基于像素相似度的帶權無向圖G=(V,E,W)，并以此進行分割。過程大體分為以下四個步驟：

(1)將待分割圖像映射為一幅無向帶權圖G=(V,E)；

(2)計算相似度矩陣W；

(3)對W進行特征分解，求出特征值和特征向量，構造特征向量空間；

(4)將特征向量利用已知的聚類方法進行聚類，得出分割結果。

在上述步驟中，相似度矩陣的構造是整個算法的關鍵。相似度矩陣由圖像各像素之間的相似性測度構成，對于彩色圖像來說，相似性測度通常由圖像的顏色特征和空間距離信息求解得到，從而得到一個基于聚類樣本數量的相似度矩陣Sn*n作為譜聚類算法的輸入。其中，n表示樣本數目。矩陣中的每個元素sij∈[0,1]表示樣本i與樣本j的相似程度，sij的值越大表示樣本i和樣本j之間的相似程度越高。在相似度矩陣構造完成后，通過求解相似度矩陣的拉普拉斯矩陣的特征值和特征向量來指導圖像的分割[16]。

2.2 相似度矩陣的構造

相似度矩陣由圖像中各像素之間的相似度構成，在計算彩色圖像像素之間的相似度時，通常將圖像的顏色特征與空間距離相結合求出各像素之間的相似度[17]，從而得到一個相似度矩陣。然而不同的顏色空間和不同的距離計算公式構造出的相似度矩陣不同，造成譜聚類算法的分割效果也不同。在選擇顏色空間時，最常用到的是RGB顏色空間，而HSV顏色空間也經常用于圖像分割，因此文中在比較相似度矩陣的構造方法對圖像分割結果的影響時，分別采用RGB和HSV兩種不同的顏色空間。從RGB到HSV的轉換公式為：

(1)

圖像的顏色特征還不足以表示像素之間的相似度，需要與像素之間的距離相結合。傳統的距離計算公式有歐氏距離，然而歐氏距離的度量方式往往只考慮絕對距離，忽視了各點之間的相對距離[18]，而通常在分類中相對距離更加具有實際意義。余弦距離和卡方距離更能體現特征量之間的相對關系，有效地反映各特征量的相對距離變化。因此，除歐氏距離外，文中還采用余弦距離和卡方距離來構造相似度矩陣，從而比較不同方式構造的相似度矩陣對分割結果的影響。三種距離計算公式如下：

歐式距離：

(2)

余弦距離：

(3)

卡方距離：

(4)

基于以上顏色空間和距離公式構造相似度矩陣后，將其作為譜聚類算法的輸入進行分割，比較不同分割效果，具體算法流程圖如圖1所示。

圖1 算法流程圖

從圖中可以看到，文中在構造相似度矩陣時分兩種不同的顏色空間計算像素之間的相似度，同時結合像素的空間距離信息。在分割過程中由于計算機內存限制，需要對圖像進行縮放，提高算法運行效率。算法具體流程如下：

(1)對原始圖像采用雙三次插值方法縮放，至與原圖像同等比例的100左右大小，同時對縮放后的圖像進行高斯低通濾波，消除圖像的噪聲；

(2)對RGB顏色空間的顏色分量進行特征提取，構成基于r值,g值和b值的特征分量；

(3)對所提取的顏色特征分別調用式(2)、(3)、(4)進行距離度量，得到三個基于不同距離的像素相似度矩陣S1、S2、S3；

(4)分別將上述三個相似度矩陣作為譜聚類算法的輸入項，調用譜聚類算法得到分割結果；

(5)對于HSV顏色空間，首先利用式(1)將RGB顏色空間轉換到HSV顏色空間，然后對HSV顏色空間的顏色分量進行特征提取，余下的步驟同步驟(3)、(4)。

3 實驗結果分析及比較

文中實驗硬件環境采用IntelPentiumCPUG3240 3.10GHz,4GB內存，Windows7操作系統；軟件環境采用MatlabR2012a和VisualStadio2010。實驗圖像均來自Berkeley大學的BSDS300圖像數據庫中的訓練集和測試集，在其中選取了大量的不同類型的圖像進行分割。依據不同的顏色空間和距離計算公式構造6個不同的相似度矩陣，得到6種不同的分割結果。

從大量實驗圖像中選取以下圖像進行分析，實驗原始圖像如圖2所示，RGB顏色空間下的分割結果圖像如圖3所示，HSV顏色空間下的分割結果圖像如圖4所示。

圖2 原始圖像

圖3 基于RGB顏色空間的分割結果圖

圖4 基于HSV顏色空間的分割結果圖

從圖3可以看出，在RGB顏色空間下，其分割效果的優異程度為：余弦距離好于卡方距離，卡方距離好于歐氏距離。其中，采用余弦距離公式得到的分割結果是最好的，而采用卡方距離和歐氏距離得到的分割結果相差不是很大，但總體上利用卡方距離得到的分割區域比利用歐氏距離得到的分割區域更加平滑一些。

從圖4可以看出，在HSV顏色空間下，其分割效果的優異程度為：余弦距離好于卡方距離，卡方距離好于歐氏距離，且HSV顏色空間與歐氏距離結合的分割效果不是很理想。同時，針對同一余弦距離公式，在不同的顏色空間下分割的效果也不盡相同，在RGB顏色空間下的分割效果明顯好于HSV顏色空間下的分割效果。

為驗證上述結論的可靠性，文中將經典的性能評價指標—查準率和查全率引入到圖像分割效果的性能評價過程中。查準率及查全率(precision&recall)是一對評估信息處理領域相關技術的經典評價指標。在圖像分割領域，查準率說明分割算法排除干擾、減少噪聲的能力，查全率說明分割算法避免漏分的能力[19]。以Berkeley圖像數據庫中的人工基準分割圖像為依據，計算六種不同相似度矩陣構造方法得出的分割結果的查準率和查全率，如表1和表2所示。

表1RGB顏色空間下構造的相似度矩陣在Berkeley圖像數據庫上的查準率和查全率

表2 HSV顏色空間下構造的相似度矩陣在Berkeley圖像數據庫上的查準率和查全率

同時，為驗證這六種不同相似度矩陣構造方法所得出的圖像分割結果的準確性，使用基于像素錯分個數的圖像分割質量評價指標，通過統計分割后圖像錯分像素個數，從而計算分割準確率評價圖像分割效果。其具體步驟如下：

(1)對分割后的圖像的每一個像素點進行標記，每個像素點對應的像素值為所屬類的類號；

(2)計算原圖像的每一像素點與分割后的圖像的所有類之間的歐氏距離，得出距離最小類的類號，比較此類號與此像素在標記圖像中的類號是否一致，若相等則表明此像素正確分類，否則為錯分像素；

(3)再對原圖像中的所有像素點進行遍歷，統計錯分像素個數C，按式(5)計算分割正確率P。

(5)

式中，M，N分別為圖像的行數和列數。

通過上述評價方法對實驗圖像和分割圖進行計算，其分割正確率如表3所示。

表3 各種分割方法的準確率 %

通過表1，表2和表3的計算結果可以直觀看出，無論從查準率、查全率還是分割算法準確率，RGB顏色空間與余弦距離構造的相似度矩陣的分割效果在六種方法中最好，該構造方法的分割結果對測試庫中的圖像是準確可靠的。在同一顏色空間下，針對不同的距離計算公式得出的分割結果也不相同，而針對同一距離計算公式，在不同顏色空間下的分割結果也不盡相同。無論在RGB顏色空間還是在HSV顏色空間下，采用余弦距離公式得到的分割效果是最優的，卡方距離次之，由于歐氏距離本身往往只考慮絕對距離的缺點，導致其無論是在RGB顏色空間還是HSV顏色空間，得到的分割效果都沒有前兩種距離計算公式得到的分割效果好。

4 結束語

文中對譜聚類算法中基于不同顏色空間和不同距離計算公式構造的相似度矩陣對圖像分割的效果進行了分析研究。結果表明，在相同的顏色空間下，圖像分割效果由高到低的順序依次為余弦距離、卡方距離、歐氏距離。采用RGB顏色空間和余弦距離公式構造的相似度矩陣，圖像分割效果最優；采用HSV顏色空間和余弦距離公式構造的相似度矩陣，圖像分割效果次之；HSV顏色空間與歐氏距離公式構造的相似度矩陣，圖像分割效果最不理想。

同時通過查準率和查全率以及分割準確率驗證了結論的可靠性和準確性。

在未來的研究中，為了使圖像分割結果更加精準，如何對上述幾種相似度矩陣進行進一步優化和融合，尋找一種最優的相似度矩陣融合方法，是文中接下來要解決的問題。

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

[2]KanungoT,MountD,NetanyahuN,etal.Anefficientk-meansclusteringalgorithm:analysisandimplementation[J].IEEETransactionsonPatternAnalysisonMachineIntelligence,2002,24(7):881-892.

[3]BaillardC,HellierP,BarillotC.Segmentationofbrain3DMRimagesusinglevelsetsanddenseregistration[J].MedicalImageAnalysis,2001,5(3):185-194.

[4] 桂 陽,苑 云,杜 晶.融合均值漂移和加權譜聚類的彩色圖像分割[J].計算機應用研究,2012,29(9):3528-3530.

[5] 張 琦,盧志茂,徐 森,等.基于相似度矩陣的譜聚類集成圖像分割[J].傳感器與微系統,2013,32(10):21-23.

[6] 朱 峰,宋余慶,朱玉全，等.基于多階抽樣譜圖聚類彩色圖像分割[J].計算機科學,2010,37(7):264-266.

[7] 張向榮,騫曉雪,焦李成.基于免疫譜聚類的圖像分割[J].軟件學報,2010,21(9):2196-2205.

[8] 賈建華,焦李成.空間一致性約束譜聚類算法用于圖像分割[J].紅外與毫米波學報,2010,29(1):69-74.

[9] 李俊英,汪西莉.一種新的大規模復雜圖像分割的譜聚類方法[J].計算機應用研究,2011,28(5):1994-1997.

[10] 朱長明,李 晶,顧國昌，等.譜聚類集成的淋巴結超聲圖像分割算法[J].計算機輔助設計與圖形學學報,2009,21(10):1480-1486.

[11] 丁 陽,錢鵬江.醫學圖像分割中基于數據濃縮的譜聚類算法[J].計算機工程,2012,38(12):17-21.

[12] 鐘清流，蔡自興.用于彩圖分割的自適應譜聚類算法[J].計算機應用研究,2008,25(12):3697-3699.

[13]LiuHQ,JiaoLC,ZhaoF.Non-localspatialspectralclusteringforimagesegmentation[J].Neurocomputing,2010,74(3):461-471.

[14]BaiXD,CaoZG,WangY,etal.ImagesegmentationusingmodifiedSLICandNystr?mbasedspectralclustering[J].Optik-InternationalJournalforLightandElectronOptics,2014,125(16):4302-4307.

[15]FilipponeM,CamastraF,MasulliF,etal.Asurveyofkernelandspectralmethodsforclustering[J].PatternRecognition,2008,41(1):176-190.

[16] 蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機科學,2008,35(7):14-18.

[17] 納躍躍,于 劍.一種用于譜聚類圖像分割的像素相似度計算方法[J].南京大學學報:自然科學版,2013,49(2):159-168.

[18] 謝 紅,趙洪野.基于卡方距離度量的改進KNN算法[J].應用科技,2015,42(1):10-14.

[19] 徐 瑞.圖像分割方法及性能評價綜述[J].寧波工程學院學報,2011,23(3):76-79.

Research on Similarity Matrix Structure in Spectral Clustering Image Segmentation

LI Yang，LU Lu，CUI Hong-xia

(College of Information Science and Technology,Bohai University,Jinzhou 121000,China)

In recent years,spectral clustering algorithm is widely used in the field of image segmentation,and the structure of the similarity matrix is the key of it.When the color images are segmented by traditional spectral clustering algorithm,the only one of color space and distance calculation formula is usually used to construct similarity matrix.The influence of the segmentation results established on the different color space and distance calculation formula is neglected,which leads to many limitations of spectral clustering algorithm.To solve this problem,using the formula of Euclidean distance,cosine distance and chi square distance,the different similarity matrices are established on RGB and HSV color space.The best segmentation construction method of the similarity matrix is obtained by analysis and comparison of the effect of different construction methods.The effectiveness of spectral clustering algorithm for segmenting color images is improved.By calculating the accuracy of image segmentation results and the performance evaluation index of precision and recall,the reliability and accuracy of the experiment are verified.

image segmentation;spectral clustering;similarity matrix;color space;distance formula

2015-10-20

2016-01-21

時間：2016-06-22

國家自然科學基金資助項目(41371425);遼寧省自然科學基金(2013020048)

李 揚(1991-),女,碩士研究生,研究方向為圖像處理;陸 璐,博士,副教授，通訊作者，研究方向為計算機應用;崔紅霞,博士,教授，研究方向為圖像處理、計算機應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0842.012.html

TP391

A

1673-629X(2016)07-0055-04

10.3969/j.issn.1673-629X.2016.07.012