一种快速谱聚类医学图像分割算法

褚徐涛，王亚楠，梁木玲

（广西师范学院计算机与信息工程学院，南宁 530023）

一种快速谱聚类医学图像分割算法

褚徐涛，王亚楠，梁木玲

（广西师范学院计算机与信息工程学院，南宁 530023）

医学图像分割在医学应用中有极其重要的意义。传统的谱聚类图像分割算法虽然能够分割图像，但是计算代价大、分割效率低。使用快速谱聚类图像分割算法，通过降低图像的拉普拉斯矩阵维度来提高谱聚类图像分割算法的效率。实验结果表明，在人脑部MR图像上用改进算法与传统算法比较，获得较好的时间效率并且没有降低图像分割质量。

0 引言

谱聚类算法具有对数据分布的形状不敏感，可以识别任意形状的数据集，不会陷入局部最优，能够将高维数据空间中的数据映射到低维空间中进行处理等优点，其在图像分割领域上有可取之处。但传统的谱聚类图像分割算法，是将图像的每一个像素看成一个数据对象，构造一个全像素连接的相似矩阵。即：对于一个有n个像素的图像而言，它的相似矩阵大小为n×n，如果图片尺寸为480×480，则构造相似矩阵需要计算（480×480）2次像素之间的相似度。庞大的计算量，导致谱聚类算法在图像分割应用上非常低效。如何保留谱聚类对不规则分布数据的聚集能力，又提高其图像分割的效率，是谱聚类算法和图像分割算法研究人员关注的问题。

1 谱聚类算法原理

谱聚类算法的原理是由图像的相似矩阵S，构造S的拉普拉斯矩阵，然后计算拉普拉斯矩阵的特征向量，并在特征向量中完成聚类。而一个图像的拉普拉斯矩阵，其特征向量可以通过其低秩近似子空间的特征向量扩展而得。利用这一特性，可以通过降低图像的拉普拉斯矩阵维度来提高谱聚类图像分割算法的效率，实现快速谱聚类图像分割算法（FSCGS：Fast Spectral Clustering for Graph Segmentation）。

快速谱聚类图像分割算法（FSCGS：Fast Spectral Clustering for Graph Segmentation）。

1.1 构造图像的相似矩阵的低秩子空间

给定一个n×n尺寸的图像I，记I的相似矩阵为S，利用采样技术抽取S的若干列，构造S的子空间。再由子空间进一步得到其低秩子空间。

这里采用迭代的抽样算法（ssm：sample select method）。其算法描述如下：

算法ssm：

输出：S的低秩近似子空间～Sc

步骤：

（1）k=1。以概率 pi随机抽取S的一个初始大小为n*qk的矩阵 Ck，n*qk,其中 qk<

（2）qk+1=(1 +α) qk，以概率 pi随机抽取S的一个子空间Rk+1(qk+1*qk+1)

（3）计算Ck'的的前t个特征根σt(Ck)和对应的特征向量yt

1.2 计算拉普拉斯矩阵 LL的近似子空间

已知图像的相似矩阵为S，根据传统的谱聚类算法，其规范化拉普拉斯矩阵L定义为：

其中，D为相似矩阵S的度矩阵。

于是，

而 D˜-1

综上，L的近似矩阵为：

最后，L的前k个奇异向量能够被近似为：

其中，V包含奇异向量，∑是奇异值，

最后，给出快速普聚类图像分割算法（FSCGS）描述：

算法FSCGS：

输入：图像Image，聚类参数k

输出：聚类标签

步骤：

（1）调用算法ssm，得到图像的近似低秩子空间～Sc

（3）按公式（3）计算前K个奇异向量U

（4）将U的每一行看成一个点，执行K-means聚类，返回聚类标签。

2 FSCGS算法在医学图像分割上的应用

实验使用的图像是成人脑部MR图像，实验目的是使用传统谱聚类图像分割算法和本文的快速谱聚类图像分割算法（FSCGS）对脑部图像进行分割，并对比分割效果和效率。实验环境为Intel Core i5 CPU，Win8操作系统，使用MATLAB 2012a编写代码。图1是脑部原始MR图像。图2为FSCGS的分割结果。实验耗时100秒。

图1 脑部MR原图

图2 FSCGS算法分割结果

实验结果表明，FSCGS算法在对原始图像进行抽样后，仍然能有效分割出脑部的灰质和白质，并且没有降低图像的分割质量。从时间效率上看，FSCGS算法要明显优于传统的谱聚类图像分割算法。

3 结语

本文将对传统谱聚类算法在图像分割应用中计算代价大，效率低的不足进行了有针对性的研究，应用抽样技术对图像的相似矩阵进行了低秩子空间近似，并在低秩子空间基础上应用谱聚类算法的原理，得到的快速谱聚类图像分割算法FSCGS，能够有效分割脑部MR图像，在时间效率上也优于传统谱聚类算法。

[1]Liu HQ,Jiao LC,Zhao F.Non-Local Spatial Spectral Clustering for Imagesegmentation[J].Neurocomputing(2010).74(1-)：461-471.

[2]ZHANG Xiang-Rong,QIAN Xiao-Xue,JIAO Li-Cheng.Immune Spectral Clustering Algorithm for Image Segmentation[J].Journal of Software,Vol.21,No.9,2010,p.2196-2205 http：//www.jos.org.cn.

[3]周林,平西建,徐森,张涛.基于谱聚类的聚类集成算法[J].自动化学报.2012,38(8).1335-1341

[4]Zeng S,Sang N,Tong XJ.Hand-Written Numeral Recognition Based Onspectrum Clustering.In：MIPPR 2011：Pattern Recognition and Computer Vision,Proceedings of SPIE,p8004

[5]蒋盛益,杨博泓,王连喜.一种基于增量式谱聚类的动态社区自适应发现算法[J].自动化学报.2015,41(12).2017-2025

[6]Ding SF,Jia HJ,Shi ZZ.Spectral Clustering Algorithm Based on Adaptive Nyström Sampling for Big Data Analysis.Journal of Software,2014,25(9)：2037-2049(in Chinese).http：//www.jos.org.cn/1000-9825/4643.htm.

[7]Ng AY,Jordan MI,Weiss Y.On Spectral Clustering：Analysis and an Algorithm.In：Becker S,Thrun S,Obermayer K,eds.Advances in Neural Information ProcessingSystems,Vol.14.MIT Press,2002.849-856.

A Fast Spectrum Clustering Medical Image Segmentation Algorithm

CHU Xu-tao，WANG Ya-nan，LIANG Mu-ling
（College of Computer and Information Engineering,Guangxi Teacher Education University,Nanning 530023）

Medical image segmentation is of great importance in medical applications.Although the traditional spectral clustering Graph Segmenta⁃tion algorithm can segment the image,but the calculation cost is large and the efficiency of segmentation is low.Uses Fast Spectral Cluster⁃ing for Graph Segmentation algorithm,improves the efficiency of the spectral clustering image segmentation algorithm by reducing the La⁃placian matrix dimension of the image.The experimental results show that the improved algorithm is compared with the traditional algo⁃rithm on the human brain MR image,and the time efficiency is improved and the image segmentation quality is not reduced.

广西自然科学基金项目（No.2016GXNSFAA380209）

1007-1423（2017）23-0048-03

10.3969/j.issn.1007-1423.2017.23.011

褚徐涛（1993-），男，浙江余姚人，硕士研究生，研究方向为图像处理

2017-05-12

2017-08-10

快速谱聚类；图像分割；医学图像

Fast Spectrum Clustering;Image Segmentation;Medical image