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

張耀楠 吳秋實 何穎 安曉莉

摘要：針對從CT圖像中提取心臟結構信息還是一個尚未解決的問題，本文利用超像素思想對CT圖像進行分割。本文利用4種方法（N-cut算法、熵率、簡單線性迭代、均值漂移）進行超像素過分割，并進行了量化比較。進一步通過動態融合方法和譜聚類方法得到分割結果。在動態融合方法中設計了一種相似性度量的計算方法，并對兩種合并方法進行了比較。實驗表明本文提出的方法用于CT心臟圖像的分割是可行的。在四種超像素過分割方法中，簡單線性迭代運行速度較快，在各項評價指標中都比較不錯。動態融合方法和譜聚類的合并準確性都較高，但譜聚類的運算速度遠快于超像素的動態合并。

關鍵詞：CT;醫學圖像;Adaboost;圖像分割;超像素

中圖分類號：R445.1? ? 文獻標識碼：A? ? ?文章編號：1007-9416（2018）10-0000-00

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

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

1 方法

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

1.1動態融合流程

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

假設圖中有個超像素塊，則需建立的超像素矩陣。的一個元素代表超像素塊與超像素塊之間的代價函數，的具體計算公式如下：

? ? ? ? ? ? ? （1）

在此公式中，、是常數，需要手動設置。可以看出，上述公式有三部分組成。其分別代表超像素塊間的相似度距離、相鄰超像素塊公共邊界與超像素塊的相似度距離、以及合并后的超像素塊與現有超像素塊之間的相似度距離。下面分別介紹這三部分。

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

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

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

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

? ? ? ? ? ? ? ?（3）

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

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

（4）

對每兩個相鄰超像素塊通過上述公式進行代價函數的計算，不相鄰的超像素塊的代價函數設為無窮大，并用矩陣記錄下來。合并時，將矩陣內代價函數最小的兩塊超像素合并為一塊，并重新更新建立的矩陣，不斷重復此過程。直到新的超像素塊數達到先前預設的塊數。

1.2譜聚類

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

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

（1）設計超像素塊之間的維連接矩陣。

（2）根據連接矩陣計算連接矩陣的拉普拉斯矩陣以及度矩陣。

（3）計算的特征值，選取特征值最小的個特征向量，建立的特征矩陣。

（4）對特征矩陣進行k-means聚類。

（5）得到最后的劃分結果。

本文利用的圖像區域特征為灰度直方圖，同時本文又加入了坐標信息。本文所用的連接矩陣中元素的計算公式為：

? ? ? ? ? ? ?（5）

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

1.3融合數目的確定

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

2 實驗結果

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

2.1四種超像素過分割方法對比

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

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

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

2.2超像素塊合并結果比較

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

從表2和3分別表示了動態融合和譜聚類超像素塊合并的準確性。可以看出，兩者的準確程度都比較高，可以用于心臟的分割。譜聚類的超像素合并的時間比動態合并超像素的時間要少，這是因為動態合并需要不斷生成新的相似度距離矩陣，不斷的判斷不同超像素之間的相鄰關系，而譜聚類只需建立一次鄰接矩陣，所以譜聚類的運算速度遠快于超像素的動態合并。

3 結語

本文利用超像素思想對CT心臟圖像進行分割。整個方法有兩大步驟：過分割和塊合并。本文通過4種方法進行超像素過分割（N-cut算法、熵率、簡單線性迭代、均值漂移），并進行了量化比較。塊合并也采用了兩種不同的方法：動態融合方法和譜聚類方法。在動態融合方法中設計了一種相似性度量的計算方法，利用了譜聚類實現超像素塊的分類，并設計了自動確定最終聚類的個數。實驗表明本文提出的方法用于CT心臟圖像的分割是可行的。在四種超像素過分割方法中，簡單線性迭代運行速度較快，在各項評價指標中都比較不錯。動態融合方法和譜聚類的合并準確性都較高，但譜聚類的運算速度遠快于超像素的動態合并。

4 感謝語

本文實驗中的一些醫學圖像由中國醫科大學研究生醫工結合創新實踐基地提供。

參考文獻

[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]蘇坡.癌癥診療中的醫學圖像配準和分割算法研究[D].西北工業大學，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算法.計算機研究與發展，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