用于CT心臟分割的幾種超像素過分割和塊合并的方法比較

張耀楠 吳秋實(shí) 何穎 安曉莉

摘要：針對(duì)從CT圖像中提取心臟結(jié)構(gòu)信息還是一個(gè)尚未解決的問題，本文利用超像素思想對(duì)CT圖像進(jìn)行分割。本文利用4種方法（N-cut算法、熵率、簡單線性迭代、均值漂移）進(jìn)行超像素過分割，并進(jìn)行了量化比較。進(jìn)一步通過動(dòng)態(tài)融合方法和譜聚類方法得到分割結(jié)果。在動(dòng)態(tài)融合方法中設(shè)計(jì)了一種相似性度量的計(jì)算方法，并對(duì)兩種合并方法進(jìn)行了比較。實(shí)驗(yàn)表明本文提出的方法用于CT心臟圖像的分割是可行的。在四種超像素過分割方法中，簡單線性迭代運(yùn)行速度較快，在各項(xiàng)評(píng)價(jià)指標(biāo)中都比較不錯(cuò)。動(dòng)態(tài)融合方法和譜聚類的合并準(zhǔn)確性都較高，但譜聚類的運(yùn)算速度遠(yuǎn)快于超像素的動(dòng)態(tài)合并。

關(guān)鍵詞：CT;醫(yī)學(xué)圖像;Adaboost;圖像分割;超像素

中圖分類號(hào)：R445.1? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：1007-9416（2018）10-0000-00

任曉峰等人在2003年最早提出超像素分割的思想[1]。圖像中單個(gè)像素對(duì)人和計(jì)算機(jī)認(rèn)識(shí)圖片都無太大意義，而超像素分割將圖像分割成有某種相同圖像語義的超像素塊，保留了邊緣信息，能為后續(xù)圖像分析減少很大的計(jì)算量。已有學(xué)者將此思想應(yīng)用到醫(yī)學(xué)圖像分析領(lǐng)域中。比如定位癌癥病灶、定位內(nèi)出血位置、體內(nèi)異物檢查等諸多方面[2][3]。本文將超像素分割應(yīng)用于CT心臟圖像的分割，對(duì)一些過分割和塊合并的方法進(jìn)行比較。

超像素分割有很多具體實(shí)現(xiàn)的算法，大體可分為兩類：第一種是基于圖論的分割方法[4]，例如N-cut算法[5]，熵率（Entropy Rate） 算法[6]。 第二種是基于梯度下降的方法[7]，例如均值漂移（Mean Shift）算法[8]，簡單線性迭代（SLIC， Simple Linear Iterative Clustering） 算法[9]。本文設(shè)計(jì)超像素動(dòng)態(tài)融合算法實(shí)現(xiàn)超像素塊的合并，并設(shè)計(jì)了一種相似性度量的計(jì)算方法。還利用譜聚類實(shí)現(xiàn)超像素塊的分類，最后設(shè)計(jì)了自動(dòng)確定最終聚類的個(gè)數(shù)。

1 方法

基于超像素的圖像分割有兩大步驟：過分割和塊合并。本文通過4種方法進(jìn)行超像素過分割（N-cut算法、熵率（Entropy Rate）、簡單線性迭代（Slic）、均值漂移（Mean Shift）），得到一個(gè)過分割的圖像。再將過分割的圖像進(jìn)行塊合并工作。這部分合并也采用了兩種不同的方法：動(dòng)態(tài)融合方法和譜聚類方法。超像素塊合并后的圖像即為分割圖像。關(guān)于4種超像素過分割，已有大量文獻(xiàn)描述，本文不再重復(fù)。針對(duì)本文的應(yīng)用特性，下面對(duì)塊合并的兩種方法進(jìn)行描述。

1.1動(dòng)態(tài)融合流程

超像素塊合并，就是將圖像特征接近的超像素塊進(jìn)行合并，成為新的超像素塊。本文提出了一種代價(jià)函數(shù)的計(jì)算方法來計(jì)算相鄰超像素之間的代價(jià)函數(shù)，并將代價(jià)函數(shù)最小的超像素塊進(jìn)行合并。本文建立超像素的代價(jià)函數(shù)矩陣來記錄相鄰的超像素塊之間的代價(jià)函數(shù)值，融合代價(jià)函數(shù)值小的超像素塊，隨后更新該矩陣，并不斷重復(fù)上述步驟，得到最終結(jié)果。

假設(shè)圖中有個(gè)超像素塊，則需建立的超像素矩陣。的一個(gè)元素代表超像素塊與超像素塊之間的代價(jià)函數(shù)，的具體計(jì)算公式如下：

? ? ? ? ? ? ? （1）

在此公式中，、是常數(shù)，需要手動(dòng)設(shè)置?？梢钥闯?，上述公式有三部分組成。其分別代表超像素塊間的相似度距離、相鄰超像素塊公共邊界與超像素塊的相似度距離、以及合并后的超像素塊與現(xiàn)有超像素塊之間的相似度距離。下面分別介紹這三部分。

代表超像素塊與超像素塊的相似度距離。本文的研究對(duì)象為CT圖像，為灰白圖像，而且超像素過分割后的每塊超像素塊相對(duì)較小，且形狀不規(guī)則。因此本文計(jì)算相似度距離是利用相鄰兩超像素塊的灰度分布計(jì)算的。具體定義為：

? ? ? ? ? ? ? ? ? ?（2）

其中表示超像素塊的灰度直方圖。可以從公式中看出當(dāng)和的灰度直方圖越接近時(shí)，的值越小。

經(jīng)過過分割得到的超像素塊還保留了原始圖像的邊界信息。想要得到好的合并結(jié)果，我們需要利用這些邊界信息。若兩個(gè)相鄰超像素塊可以合并，則表明兩個(gè)超像素塊公共邊緣的灰度分布應(yīng)該和這兩個(gè)超像素塊的灰度分布都相近。我們將兩個(gè)相鄰超像素塊的共同邊界記為。那么（1）中的計(jì)算如公式（3）所示。

? ? ? ? ? ? ? ?（3）

的值越小，代表邊界與這兩個(gè)超像素塊越接近，這兩塊越有可能合并為一個(gè)新超像素塊。

另外，若兩個(gè)相鄰超像素塊可以合并，每一塊的超像素與合并后的新超像素塊的灰度分布應(yīng)該接近。將合并后的超像素塊記為，按下列公式計(jì)算

（4）

對(duì)每兩個(gè)相鄰超像素塊通過上述公式進(jìn)行代價(jià)函數(shù)的計(jì)算，不相鄰的超像素塊的代價(jià)函數(shù)設(shè)為無窮大，并用矩陣記錄下來。合并時(shí)，將矩陣內(nèi)代價(jià)函數(shù)最小的兩塊超像素合并為一塊，并重新更新建立的矩陣，不斷重復(fù)此過程。直到新的超像素塊數(shù)達(dá)到先前預(yù)設(shè)的塊數(shù)。

1.2譜聚類

上面介紹的超像素塊合并方法每一次進(jìn)行合并時(shí)，都需要重新建立代價(jià)函數(shù)矩陣，并且重新判斷超像素塊之間是否相鄰。無論是時(shí)間復(fù)雜度還是空間復(fù)雜度都比較大。這一節(jié)我們利用譜聚類的方法來對(duì)超像素塊進(jìn)行分類[10-12]。譜聚類是一種基于圖論的聚類方法，它能夠識(shí)別任意形狀的樣本空間且收斂于全局最有解，其基本思想是利用樣本數(shù)據(jù)的相似矩陣進(jìn)行特征分解后得到的特征向量進(jìn)行聚類[21]。

本文中譜聚類的主要步驟為：

（1）設(shè)計(jì)超像素塊之間的維連接矩陣。

（2）根據(jù)連接矩陣計(jì)算連接矩陣的拉普拉斯矩陣以及度矩陣。

（3）計(jì)算的特征值，選取特征值最小的個(gè)特征向量，建立的特征矩陣。

（4）對(duì)特征矩陣進(jìn)行k-means聚類。

（5）得到最后的劃分結(jié)果。

本文利用的圖像區(qū)域特征為灰度直方圖，同時(shí)本文又加入了坐標(biāo)信息。本文所用的連接矩陣中元素的計(jì)算公式為：

? ? ? ? ? ? ?（5）

其中、分別為灰度直方圖和坐標(biāo)信息的均方差。

1.3融合數(shù)目的確定

超像素塊合并最終聚類個(gè)數(shù)需要事先指定。 本文利用Gap Statistic方法對(duì)最終的聚類個(gè)數(shù)進(jìn)行預(yù)測。 Gap statistic方法是通過對(duì)平均分布參考數(shù)據(jù)集的期望值和觀測數(shù)據(jù)集的進(jìn)行比較，查找下降最快的值為最優(yōu)聚類數(shù)，具體方法描述可參見文獻(xiàn)[13]。

2 實(shí)驗(yàn)結(jié)果

本文利用Microsoft Visual Studio 2013軟件平臺(tái)、Opencv計(jì)算機(jī)視覺庫以及Matlab 2014軟件對(duì)上文描述的方法進(jìn)行實(shí)驗(yàn)。 圖像采集設(shè)備為西門子CT，CT圖像的大小為512*512。共有42名病人的CT影像，每名病人的數(shù)據(jù)含有200-300張圖像。

2.1四種超像素過分割方法對(duì)比

表1是四個(gè)超像素過分割算法復(fù)雜度的比較。從表中看出，只有簡單線性迭代算法的時(shí)間復(fù)雜度是線性的，其他算法的計(jì)算量隨像素個(gè)數(shù)的增加而大幅提高。

下面本文對(duì)四種超像素過分割結(jié)果進(jìn)行分析比較。衡量超像素分割效果主要關(guān)注超像素邊界邊緣與目標(biāo)邊緣是否精確貼合，以及超像素形狀和大小規(guī)則情況。本文以下面幾個(gè)指標(biāo)對(duì)上述超像素過分割算法進(jìn)行定性的評(píng)價(jià)：（1）欠分割錯(cuò)誤率，該指標(biāo)表示超像素區(qū)域超出人工分割邊界的比例，該值越小，超像素的邊緣貼合度越小;（2）邊緣召回率，用于度量超像素邊緣與原始圖像邊緣重疊比例，該值越高，超像素邊緣貼合度越好;（3）面積方差，度量超像素面積的差異大小;（4）圓度率（CM， Circle Measurement），衡量超像素整體形狀逼近園的程度。

這幾個(gè)指標(biāo)的實(shí)驗(yàn)結(jié)果如圖1-4所示。熵率算法在邊緣處理上表現(xiàn)最好，分割出的邊緣與原邊緣貼合的越密切， 但是在圖像的規(guī)則程度上較差。而均值漂移的形狀相對(duì)緊湊規(guī)則，但是在邊緣處理上較差。而且上述兩種算法在計(jì)算量大，運(yùn)行慢，不能實(shí)現(xiàn)連續(xù)斷層圖片的超像素分割的要求。相比之下，簡單線性迭代的速度要快的多，而且在上述評(píng)價(jià)指標(biāo)中都比較不錯(cuò)，而且分割的超像素塊可用。因此，本文選用簡單線性迭代算法作為后面超像素合并的預(yù)處理算法。

2.2超像素塊合并結(jié)果比較

超像素譜聚類結(jié)果如表2、表3所示。

從表2和3分別表示了動(dòng)態(tài)融合和譜聚類超像素塊合并的準(zhǔn)確性。可以看出，兩者的準(zhǔn)確程度都比較高，可以用于心臟的分割。譜聚類的超像素合并的時(shí)間比動(dòng)態(tài)合并超像素的時(shí)間要少，這是因?yàn)閯?dòng)態(tài)合并需要不斷生成新的相似度距離矩陣，不斷的判斷不同超像素之間的相鄰關(guān)系，而譜聚類只需建立一次鄰接矩陣，所以譜聚類的運(yùn)算速度遠(yuǎn)快于超像素的動(dòng)態(tài)合并。

3 結(jié)語

本文利用超像素思想對(duì)CT心臟圖像進(jìn)行分割。整個(gè)方法有兩大步驟：過分割和塊合并。本文通過4種方法進(jìn)行超像素過分割（N-cut算法、熵率、簡單線性迭代、均值漂移），并進(jìn)行了量化比較。塊合并也采用了兩種不同的方法：動(dòng)態(tài)融合方法和譜聚類方法。在動(dòng)態(tài)融合方法中設(shè)計(jì)了一種相似性度量的計(jì)算方法，利用了譜聚類實(shí)現(xiàn)超像素塊的分類，并設(shè)計(jì)了自動(dòng)確定最終聚類的個(gè)數(shù)。實(shí)驗(yàn)表明本文提出的方法用于CT心臟圖像的分割是可行的。在四種超像素過分割方法中，簡單線性迭代運(yùn)行速度較快，在各項(xiàng)評(píng)價(jià)指標(biāo)中都比較不錯(cuò)。動(dòng)態(tài)融合方法和譜聚類的合并準(zhǔn)確性都較高，但譜聚類的運(yùn)算速度遠(yuǎn)快于超像素的動(dòng)態(tài)合并。

4 感謝語

本文實(shí)驗(yàn)中的一些醫(yī)學(xué)圖像由中國醫(yī)科大學(xué)研究生醫(yī)工結(jié)合創(chuàng)新實(shí)踐基地提供。

參考文獻(xiàn)

[1]Malik J.Learning a classification model for segmentation[J].Proc.int.conf.computer Vision，2003（1）：10-17 vol.1.

[2]Achanta R，Shaji A，Smith K， et al. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2012，34（11）：2274.

[3]蘇坡.癌癥診療中的醫(yī)學(xué)圖像配準(zhǔn)和分割算法研究[D].西北工業(yè)大學(xué)，2014.

[4]Zhang Z，Xing F & Wang H， et al.（2018）. Revisiting Graph Construction for Fast Image Segmentation[J].Pattern Recognition，2018，（78）：344-357.

[5]Fu K，Gu Y H，Yang J.Spectral Salient Object Detection[J].Neurocomputing，2017：1-6..

[6]Liu M Y，Tuzel O，Ramalingam S，et al. Entropy rate superpixel segmentation[C]// Computer Vision and Pattern Recognition.IEEE，2011：2097-2104.

[7]Levinshtein A，Stere A， Kutulakos K N，et al. Turbopixels： Fast superpixels using geometric flows[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（12）： 2290-2297.

[8]Shih HC，Liu ER，Automatic Reference Color Selection for Adaptive Mathematical Morphology and Application in Image Segmentation[J].IEEE Transactions on Image Processing，2016（25）：4665-4676.

[9]Achanta R，Shaji A，Smith K，et al.SLIC superpixels[J].Epfl，2010.

[10]Yang Y，Wang Y，Xue X.A novel spectral clustering method with superpixels for image segmentation[J].Optik - International Journal for Light and Electron Optics，2016，127（1）：161-167.

[11]Zou X，Xiaodong Y E，Tan Z，et al. Image segmentation method based on improved similarity measure of spectral clustering[J].Computer Engineering & Applications，2017.

[12]Zelnik-Manor L， Perona P. Self-Tuning Spectral Clustering[C]// Advances in Neural Information Processing Systems.2004：1601--1608.

[13]肖 宇，于 劍.Gap statistic與k-means算法.計(jì)算機(jī)研究與發(fā)展，2007，44（Suppl.）：176-180.

Comparison of Several Methods of Superpixel-Based over-Segmentation

and Region Merging for Cardiac CT Segmentation

ZHANG Yao-nan1，2，WU Qiu-shi2 ，HE Ying1 ，AN Xiao-li1

（1.College of Electronics and Information Engineering， Siyuan University， Xian Shanxi 710038;

2.Sino-Dutch Biomedical and Information Engineering School，Northeastern University，Shenyang Liaoning 110169）

Abstract： To tackle the unresolved problem of extracting cardiac structure information from CT images， this paper uses superpixel paradigm to segment CT images. In this paper， four methods （N-cut algorithm， entropy rate， simple linear iterative clustering， mean shift） are used to perform superpixel-based over-segmentation and their quantitative comparison is performed. The segmentation results are obtained by further dynamic fusion method and spectral clustering method. A calculation method of similarity measure is designed in the dynamic fusion method， and the two region merging methods are compared. Experiments show that the proposed method is feasible for segmentation of CT cardiac images. Among the four superpixel-based over-segmentation methods， the simple linear iterative clsutering runs faster and is perfoming well in all evaluation indicators. The accuracy of both dynamic fusion method and spectral clustering is good， but the spectral clustering operation speed is much faster than the dynamic fusion.

Key words： CT; medical images; Adaboost; image segmentation; superpixels