谱聚类图像分割中相似度矩阵构造研究

李 扬,陆 璐,崔红霞

(渤海大学 信息科学与技术学院，辽宁 锦州 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