基于改进谱聚类的医学图像分割算法
2015-11-24周燕琴吕绪洋田春梅李超强
周燕琴 吕绪洋 田春梅 李超强
(广西师范学院计算机与信息工程学院,广西 南宁 530023)
基于改进谱聚类的医学图像分割算法
周燕琴 吕绪洋 田春梅 李超强
(广西师范学院计算机与信息工程学院,广西 南宁 530023)
为了解决基于像素难以有效分割的医学图像问题,提出一种改进谱聚类方法:一,将全局划分成具有强关联的子问题提高图像分割精度;二,传统基于欧氏距离度量的聚类容易陷入局部最优,提出流行距离构造样本相似矩阵,从而得到图像全局上的一致。最后通过对脑核磁共振图像分割验证算法的有效性。
医学图像;谱聚类;拉普拉斯特征映射;流行距离
1 引言
近年来,医学图像分割成为一个活跃的研究领域。精确的医学图像分割可为临床诊断和做病理学研究等方面提供可靠依据。这受到国内外研究学者的广泛关注,Lombaert和Ziki等人[1]提出了基于像素建立全局分类模型,对所有可能的目标类图像以及局部图像训练。然而,医学图像含有重现组织构造不同、局部限定子问题很难并入到全局模式,所以全局分类模型很难解决此类问题。局部子问题是由大量的子图组成不是由整体外观图像体现,所以解决局部问题可以采用全局问题域划分成局部限定的子问题针对性解决。对于上述问题,本文提出并且解决了以下两方面的问题:第一个问题是局部子问题。第二个问题是图像数据点相似性问题。本文提出一种新的基于谱聚类算法将全局问题划分成局部有限子问题。传统基于欧氏距离度量不能完全反应数据点在样本空间的分布特性[2]。受文献[3]的启示,提出了一种新的基于流行学习距离度量聚类方法,可以增强类内间相似度,同时削弱类间相似度。本文方法通过对脑部核磁共振(MR)图像分割与常用的谱聚类算法进行比较,实验结果表明所提方法获得较好的分割结果。
2 谱聚类算法
谱聚类是基于谱图划分理论[4]的聚类方法,将聚类问题看成是一个带权无向图的多路最优子图的划分问题。如 Shi 和Malik[5]提出的规范割集准则。使得子图内部数据点尽可能有较高的相似性,而子图之间的数据点尽可能有较低的相似性,以达到聚类的目的。一个好的求解办法考虑问题的连续放松形式,将问题转化成求解相似度矩阵和构造拉普拉斯矩阵(Laplacian),并且计算拉普拉斯矩阵的特征值和特征向量,使得空间里的数据分布结构更加明显。如Ng 等人[6]提出的基于规范化拉普拉斯矩阵的谱聚类(NJW)算法,称之为标准谱聚类算法。谱聚类算法[7]的最基本步骤如下:
Step1 根据某种判定相似性依据构造相似矩阵W;
Step2 构造拉普拉斯矩阵 L并求出特征值和对应的特征向量,得到简化的数据空间;
Step3利用k-means或者聚类算法对得到特征向量空间进行聚类。
3 基于改进的谱聚类算法
通过学习分析传统谱聚类算法可知谱聚类能很好抓住主要的矛盾,比传统的聚类方法更具鲁棒性。伴随这些优点同时,聚类的缺陷也制约着它的发展。医学图像本身普遍存在灰度不均匀性、噪声、低对比度等缺陷。本文将针对以上两个方面问题给出解决方案:把全局问题划分成局部子问题来解决和选择好的相似矩阵距离测量更能体现空间数据分布情况,给出一种基于改进谱聚类的医学图像分割算法。
3.1基于分块提取局部特征方法
由于整图反映的是整张图像的特征向量,对细节的描述不完整。如果对图像使用分块算法处理并以每个子图的特征向量作为聚类特征向量,将能更好的提取图像局部特征。针对性处理,提高图像的分割精确度。如图 1所示医学图像局部分块图,把每块子图作为单独样本,对这些新的样本求类间相似矩阵,采用高斯核函数来建立样本中数据点之间的相似性,公式为(1):
图1 标准试验系统结果曲线
用,ija表示子图数据点之间的相似度,MD是两点间的流行距离(详见2.2节),σ尺度参数,取值参照文献[8]。然后对做特征分解,计算拉普拉斯特征向量L,接着再把所有子图的前 k个主特征值对应的特征向量计算出来,最后把每个子图的特征向量组合起来就可以得到图像最终特征向量,以便用于最后的分割。如下为计算拉普拉斯矩阵公式:
D矩阵为对角阵,即对角上的值为A矩阵中对应行或列的和。
3.2基于流行学习的相似矩阵构造方法
在解决实际距离测量问题上,欧式距离测量仅表现出数据点的局部一致性,而流行学习距离测量则对数据点表现出全局一致性[9]。可知对于分布复杂的空间数据,在同一流行结构上的数据点相似性高。如图 2所示可看出图分为两类,数据点b与数据点c在同一类,而a单独在另一类。根据欧氏距离测量数据点b与数据点c的欧氏测量距离比数据点b到数据点 a的欧氏距离大一倍多。显然用简单的欧氏距离测量会严重影响聚类结果。
图2 欧氏距离测量无法反应全局一致性
公式(4)能加大不同流形结构上数据点间的距离,减小同一流形结构上数据点间的距离,这充分弥补了欧氏距离测量的不足,体现了聚类数据的空间特性表现出数据的全局一致性。
基于上述改进,本文设计的算法步骤如下:
步骤1:按本文2.1小节的方法进行图像分块提取局部特征。
步骤2:按本文2.2小节的方法构成出每个局部子图的相似性矩阵iw。
步骤3:求相似矩阵iw的拉普拉斯矩阵il并计算每个子图前k个最大特征值和对应特征向量。
步骤4:每个分块子图像前k个最大特征向量组合成矩阵V,将矩阵V的行向量归一化处理。
步骤5:将矩阵V归一化处理后的每一行作为空间中的一点,使用k-means聚类。
3.3实验对比与分析
实验中的医学图像数据源于 Medline免费数据库中的测试集。实践平台建立在配有双核,Intel处理器,6G内存,Matlab 12a的PC微型计算机。实验采用绝对误差作为比较准则[11]。计算误差率公式如下:
其中0n理想目标像素个数,in实际测得目标像素个数,N总的像素个数值。如图 3所示实验结果分割图,(a)原始大脑MRI图像,(b)理想聚类图像,(c)基于欧氏距离谱聚类图像,(d)本文算法的聚类图像。实验结果图可看出,本文方法对MRI图像都能够稳定有效的聚类,且聚类结果最接近理想的聚类图像。
图3 实验结果分割图
图4 本文算法与传统算法误差率对比
4 总结与展望
本文改进了传统谱聚类,提出了分块与流行距离的方法来考虑样本的局部和全局一致性的统一。将算法应用于 MIR图像聚类分割验证了本文算法的有效性。下一步工作将本算法应用于大数据集中,有待进一步研究。
[1] Herve, Lombaert, Darko et al.Laplacian Forests: Semantic Image Segmentation by Guided Bagging[J].in MICCAI, 2014,(8674):496–504.
[2] 陶新民,宋少宇,曹盼东,等.一种基于流形距离核的谱聚类算法[J].信息与控制,2012,(6):308-313.
[3] Fiedler M,et al.Algebraic connectivity of graphs[J].Czech, Math, J,1973, (23):298-305.
[4] Shi J,Malik J,et al.Normalized cuts and image segmentation. [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.
[5] Ng A Y,Jordan M I,Weiss Y.On spectral clustering: Analysis and an algorithm[C]//T.G..Dietterich,S.Becker,and Ghahramni, eds.Advances in Neural Information ProcessingSystems, Cam-bridge,MA,MITPress,2002,(14):849-856.
[6] 蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学, 2008,35(7):14-18.
[7] Verma D,Meila M.A comparison of spectral clustering algorithms[M].Technical report,2003.
[8] 杨峰,柴毅.基于改进谱聚类与粒子群优化的图像分割算法[J].微电子学与计算机,2013,30(7):52-59.
[9] ZHOU D Y,BOUSQUET O,LAL T N,et al.Learning with local and global consistency[C]//Proceedings of Advances in Neural Information Processing Systems 16.Cambridge: MIT Press, 2004:321-328.
[10] Zhang Junping.Manifold learning and its applications:[Ph. D.dissertation][D].Beijing: Institute of Automation,Chinese Academy of Sciences,2003.
[11] 邹小林,陈伟福.基于谱聚类的多阈值图像分割方法[J].计算机科学,2012,39(3):246,25.
A new medical image segmentation algorithm based on improved spectral clustering
To solve the problem of difficult to effective segmentation of medical images based on pixel, an improved spectral clustering method is proposed. Firstly, the global divide into sub-problems associated with a strong correlation to improve accuracy of image segmentation; Secondly, based on the traditional Euclidean distance metric easily fall into local optimum, proposed manifold distance constructed sample similar matrix, resulting in a consistent global image on. Finally, through by segmented the brain magnetic resonance image to validate the effectiveness of the algorithm.
Medical image; spectral clustering; Laplace feature map; manifold distance
R445
A
1008-1151(2015)12-0006-03
2015-11-12
周燕琴(1987-),女,江西吉安人,广西师范学院计算机与信息工程学院硕士研究生,研究方向为大数据与数据挖掘,图像处理;吕绪洋(1989-),男,山东聊城人,广西师范学院计算机与信息工程学院硕士研究生,研究方向为智能控制系统及其应用。