周燕琴 呂緒洋 田春梅 李超強(qiáng)

（廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，廣西 南寧 530023）

基于改進(jìn)譜聚類的醫(yī)學(xué)圖像分割算法

周燕琴 呂緒洋 田春梅 李超強(qiáng)

（廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，廣西 南寧 530023）

為了解決基于像素難以有效分割的醫(yī)學(xué)圖像問(wèn)題，提出一種改進(jìn)譜聚類方法：一，將全局劃分成具有強(qiáng)關(guān)聯(lián)的子問(wèn)題提高圖像分割精度；二，傳統(tǒng)基于歐氏距離度量的聚類容易陷入局部最優(yōu)，提出流行距離構(gòu)造樣本相似矩陣，從而得到圖像全局上的一致。最后通過(guò)對(duì)腦核磁共振圖像分割驗(yàn)證算法的有效性。

醫(yī)學(xué)圖像；譜聚類；拉普拉斯特征映射；流行距離

1 引言

近年來(lái)，醫(yī)學(xué)圖像分割成為一個(gè)活躍的研究領(lǐng)域。精確的醫(yī)學(xué)圖像分割可為臨床診斷和做病理學(xué)研究等方面提供可靠依據(jù)。這受到國(guó)內(nèi)外研究學(xué)者的廣泛關(guān)注，Lombaert和Ziki等人[1]提出了基于像素建立全局分類模型，對(duì)所有可能的目標(biāo)類圖像以及局部圖像訓(xùn)練。然而，醫(yī)學(xué)圖像含有重現(xiàn)組織構(gòu)造不同、局部限定子問(wèn)題很難并入到全局模式，所以全局分類模型很難解決此類問(wèn)題。局部子問(wèn)題是由大量的子圖組成不是由整體外觀圖像體現(xiàn)，所以解決局部問(wèn)題可以采用全局問(wèn)題域劃分成局部限定的子問(wèn)題針對(duì)性解決。對(duì)于上述問(wèn)題，本文提出并且解決了以下兩方面的問(wèn)題：第一個(gè)問(wèn)題是局部子問(wèn)題。第二個(gè)問(wèn)題是圖像數(shù)據(jù)點(diǎn)相似性問(wèn)題。本文提出一種新的基于譜聚類算法將全局問(wèn)題劃分成局部有限子問(wèn)題。傳統(tǒng)基于歐氏距離度量不能完全反應(yīng)數(shù)據(jù)點(diǎn)在樣本空間的分布特性[2]。受文獻(xiàn)[3]的啟示，提出了一種新的基于流行學(xué)習(xí)距離度量聚類方法，可以增強(qiáng)類內(nèi)間相似度，同時(shí)削弱類間相似度。本文方法通過(guò)對(duì)腦部核磁共振（MR）圖像分割與常用的譜聚類算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明所提方法獲得較好的分割結(jié)果。

2 譜聚類算法

譜聚類是基于譜圖劃分理論[4]的聚類方法，將聚類問(wèn)題看成是一個(gè)帶權(quán)無(wú)向圖的多路最優(yōu)子圖的劃分問(wèn)題。如 Shi 和Malik[5]提出的規(guī)范割集準(zhǔn)則。使得子圖內(nèi)部數(shù)據(jù)點(diǎn)盡可能有較高的相似性，而子圖之間的數(shù)據(jù)點(diǎn)盡可能有較低的相似性，以達(dá)到聚類的目的。一個(gè)好的求解辦法考慮問(wèn)題的連續(xù)放松形式，將問(wèn)題轉(zhuǎn)化成求解相似度矩陣和構(gòu)造拉普拉斯矩陣（Laplacian），并且計(jì)算拉普拉斯矩陣的特征值和特征向量，使得空間里的數(shù)據(jù)分布結(jié)構(gòu)更加明顯。如Ng 等人[6]提出的基于規(guī)范化拉普拉斯矩陣的譜聚類（NJW）算法，稱之為標(biāo)準(zhǔn)譜聚類算法。譜聚類算法[7]的最基本步驟如下：

Step1 根據(jù)某種判定相似性依據(jù)構(gòu)造相似矩陣W；

Step2 構(gòu)造拉普拉斯矩陣 L并求出特征值和對(duì)應(yīng)的特征向量，得到簡(jiǎn)化的數(shù)據(jù)空間；

Step3利用k-means或者聚類算法對(duì)得到特征向量空間進(jìn)行聚類。

3 基于改進(jìn)的譜聚類算法

通過(guò)學(xué)習(xí)分析傳統(tǒng)譜聚類算法可知譜聚類能很好抓住主要的矛盾，比傳統(tǒng)的聚類方法更具魯棒性。伴隨這些優(yōu)點(diǎn)同時(shí)，聚類的缺陷也制約著它的發(fā)展。醫(yī)學(xué)圖像本身普遍存在灰度不均勻性、噪聲、低對(duì)比度等缺陷。本文將針對(duì)以上兩個(gè)方面問(wèn)題給出解決方案：把全局問(wèn)題劃分成局部子問(wèn)題來(lái)解決和選擇好的相似矩陣距離測(cè)量更能體現(xiàn)空間數(shù)據(jù)分布情況，給出一種基于改進(jìn)譜聚類的醫(yī)學(xué)圖像分割算法。

3.1基于分塊提取局部特征方法

由于整圖反映的是整張圖像的特征向量，對(duì)細(xì)節(jié)的描述不完整。如果對(duì)圖像使用分塊算法處理并以每個(gè)子圖的特征向量作為聚類特征向量，將能更好的提取圖像局部特征。針對(duì)性處理，提高圖像的分割精確度。如圖 1所示醫(yī)學(xué)圖像局部分塊圖，把每塊子圖作為單獨(dú)樣本，對(duì)這些新的樣本求類間相似矩陣，采用高斯核函數(shù)來(lái)建立樣本中數(shù)據(jù)點(diǎn)之間的相似性，公式為（1）：

圖1　標(biāo)準(zhǔn)試驗(yàn)系統(tǒng)結(jié)果曲線

用,ija表示子圖數(shù)據(jù)點(diǎn)之間的相似度，MD是兩點(diǎn)間的流行距離（詳見(jiàn)2.2節(jié)），σ尺度參數(shù)，取值參照文獻(xiàn)[8]。然后對(duì)做特征分解，計(jì)算拉普拉斯特征向量L，接著再把所有子圖的前 k個(gè)主特征值對(duì)應(yīng)的特征向量計(jì)算出來(lái)，最后把每個(gè)子圖的特征向量組合起來(lái)就可以得到圖像最終特征向量，以便用于最后的分割。如下為計(jì)算拉普拉斯矩陣公式：

D矩陣為對(duì)角陣，即對(duì)角上的值為A矩陣中對(duì)應(yīng)行或列的和。

3.2基于流行學(xué)習(xí)的相似矩陣構(gòu)造方法

在解決實(shí)際距離測(cè)量問(wèn)題上，歐式距離測(cè)量?jī)H表現(xiàn)出數(shù)據(jù)點(diǎn)的局部一致性，而流行學(xué)習(xí)距離測(cè)量則對(duì)數(shù)據(jù)點(diǎn)表現(xiàn)出全局一致性[9]?？芍獙?duì)于分布復(fù)雜的空間數(shù)據(jù)，在同一流行結(jié)構(gòu)上的數(shù)據(jù)點(diǎn)相似性高。如圖 2所示可看出圖分為兩類，數(shù)據(jù)點(diǎn)b與數(shù)據(jù)點(diǎn)c在同一類，而a單獨(dú)在另一類。根據(jù)歐氏距離測(cè)量數(shù)據(jù)點(diǎn)b與數(shù)據(jù)點(diǎn)c的歐氏測(cè)量距離比數(shù)據(jù)點(diǎn)b到數(shù)據(jù)點(diǎn) a的歐氏距離大一倍多。顯然用簡(jiǎn)單的歐氏距離測(cè)量會(huì)嚴(yán)重影響聚類結(jié)果。

圖2　歐氏距離測(cè)量無(wú)法反應(yīng)全局一致性

公式（4）能加大不同流形結(jié)構(gòu)上數(shù)據(jù)點(diǎn)間的距離，減小同一流形結(jié)構(gòu)上數(shù)據(jù)點(diǎn)間的距離，這充分彌補(bǔ)了歐氏距離測(cè)量的不足，體現(xiàn)了聚類數(shù)據(jù)的空間特性表現(xiàn)出數(shù)據(jù)的全局一致性。

基于上述改進(jìn)，本文設(shè)計(jì)的算法步驟如下：

步驟1：按本文2.1小節(jié)的方法進(jìn)行圖像分塊提取局部特征。

步驟2：按本文2.2小節(jié)的方法構(gòu)成出每個(gè)局部子圖的相似性矩陣iw。

步驟3：求相似矩陣iw的拉普拉斯矩陣il并計(jì)算每個(gè)子圖前k個(gè)最大特征值和對(duì)應(yīng)特征向量。

步驟4：每個(gè)分塊子圖像前k個(gè)最大特征向量組合成矩陣V，將矩陣V的行向量歸一化處理。

步驟5：將矩陣V歸一化處理后的每一行作為空間中的一點(diǎn)，使用k-means聚類。

3.3實(shí)驗(yàn)對(duì)比與分析

實(shí)驗(yàn)中的醫(yī)學(xué)圖像數(shù)據(jù)源于 Medline免費(fèi)數(shù)據(jù)庫(kù)中的測(cè)試集。實(shí)踐平臺(tái)建立在配有雙核，Intel處理器，6G內(nèi)存，Matlab 12a的PC微型計(jì)算機(jī)。實(shí)驗(yàn)采用絕對(duì)誤差作為比較準(zhǔn)則[11]。計(jì)算誤差率公式如下：

其中0n理想目標(biāo)像素個(gè)數(shù)，in實(shí)際測(cè)得目標(biāo)像素個(gè)數(shù)，N總的像素個(gè)數(shù)值。如圖 3所示實(shí)驗(yàn)結(jié)果分割圖，（a）原始大腦MRI圖像，（b）理想聚類圖像，（c）基于歐氏距離譜聚類圖像，（d）本文算法的聚類圖像。實(shí)驗(yàn)結(jié)果圖可看出，本文方法對(duì)MRI圖像都能夠穩(wěn)定有效的聚類，且聚類結(jié)果最接近理想的聚類圖像。

圖3　實(shí)驗(yàn)結(jié)果分割圖

圖4　本文算法與傳統(tǒng)算法誤差率對(duì)比

4 總結(jié)與展望

本文改進(jìn)了傳統(tǒng)譜聚類，提出了分塊與流行距離的方法來(lái)考慮樣本的局部和全局一致性的統(tǒng)一。將算法應(yīng)用于 MIR圖像聚類分割驗(yàn)證了本文算法的有效性。下一步工作將本算法應(yīng)用于大數(shù)據(jù)集中，有待進(jìn)一步研究。

[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].計(jì)算機(jī)科學(xué), 2008,35(7):14-18.

[7] Verma D,Meila M.A comparison of spectral clustering algorithms[M].Technical report,2003.

[8] 楊峰,柴毅.基于改進(jìn)譜聚類與粒子群優(yōu)化的圖像分割算法[J].微電子學(xué)與計(jì)算機(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].計(jì)算機(jī)科學(xué),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-），女，江西吉安人，廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院碩士研究生，研究方向?yàn)榇髷?shù)據(jù)與數(shù)據(jù)挖掘，圖像處理；呂緒洋（1989-）,男，山東聊城人，廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院碩士研究生，研究方向?yàn)橹悄芸刂葡到y(tǒng)及其應(yīng)用。