一種快速譜聚類醫學圖像分割算法

褚徐濤，王亞楠，梁木玲

（廣西師范學院計算機與信息工程學院，南寧 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