基于圖論的肝腫瘤CT圖像自動(dòng)分割方法

艾海明,吳水才,高宏建,趙 磊,曾 毅

(北京工業(yè)大學(xué)生物醫(yī)學(xué)工程中心,北京 100124)

基于圖論的肝腫瘤CT圖像自動(dòng)分割方法

艾海明,吳水才,高宏建,趙 磊,曾 毅

(北京工業(yè)大學(xué)生物醫(yī)學(xué)工程中心,北京 100124)

提出了一種肝腫瘤CT圖像自動(dòng)分割的方法,運(yùn)用圖中最小生成樹(shù)尋找圖像的同質(zhì)區(qū)域,使用按級(jí)合并和路徑壓縮2種試探法,使得分割時(shí)程近似線性時(shí)間O(n log n).對(duì)52幅肝腫瘤CT圖像進(jìn)行分割,結(jié)果表明,該方法分割實(shí)際圖像的平均最小距離為8.7540,面積交迭度為95.15%,分割精確度優(yōu)于同類自動(dòng)分割算法.應(yīng)用該方法能快速、準(zhǔn)確地自動(dòng)分割出肝腫瘤.

圖論;CT圖像;圖像自動(dòng)分割

利用肝癌微波熱療手術(shù)規(guī)劃系統(tǒng)可在術(shù)前對(duì)溫度場(chǎng)進(jìn)行規(guī)劃,這樣有助于提高肝癌微波熱療的有效性和安全性.在肝癌微波熱療手術(shù)規(guī)劃系統(tǒng)設(shè)計(jì)中首先需對(duì)肝腫瘤進(jìn)行分割并三維重建[1],而肝腫瘤分割效果的好壞直接影響肝腫瘤三維重建的準(zhǔn)確性.

由于肝臟CT圖像中存在隨機(jī)噪聲和偽影,使得傳統(tǒng)分割方法在分割過(guò)程中面臨困難,分割結(jié)果易產(chǎn)生虛假邊緣[2-3].手動(dòng)分割和交互式半自動(dòng)分割工作量大、耗時(shí)長(zhǎng)、易受人為主觀影響且分割結(jié)果重復(fù)性差,不適合分割對(duì)比度低和邊界模糊的醫(yī)學(xué)圖像[4].因此,合理地選擇一種全自動(dòng)分割肝腫瘤CT圖像的方法十分必要.文獻(xiàn)[5]提出基于最小生成樹(shù)的圖論分割算法,它使用區(qū)域比較準(zhǔn)則,極大化區(qū)域內(nèi)部的相似性與區(qū)域之間的差異性,隨著圖像內(nèi)容的變化能自適應(yīng)地改變,因此在分割準(zhǔn)則和理論上具有明顯的優(yōu)勢(shì).作者編程實(shí)現(xiàn)了該分割算法,并把它成功地應(yīng)用到肝腫瘤CT圖像的自動(dòng)分割中.

1 基于最小生成樹(shù)的圖論分割算法

1.1 圖像分割準(zhǔn)則

圖像I被分割為N個(gè)區(qū)域(Ri)的集合,應(yīng)滿足3個(gè)條件[6]:

2)H(Ri)=ture,?i,H為某種同質(zhì)性謂詞(homogeneity predicate).

1.2 最小生成樹(shù)(MST)

若V、E分別為圖G(V,E)中的頂點(diǎn)集和邊集,邊(u,v)∈E且權(quán)重值為 w(u,v),則圖G中生成樹(shù)(T)上的權(quán)重和為

式中w(T)最小的生成樹(shù)為圖G的最小生成樹(shù),最小生成樹(shù)的求解算法主要有Kruskal算法和Prim算法.

1.3 區(qū)域比較謂詞

區(qū)域比較謂詞D[5]是在分割過(guò)程中用于評(píng)價(jià)2個(gè)鄰域是否存在邊界的判據(jù).謂詞D通過(guò)對(duì)區(qū)域內(nèi)部差異和區(qū)域間差異進(jìn)行比較,使得分割結(jié)果能自適應(yīng)圖像數(shù)據(jù)的局部特征.

若C是分離集森林中任一集合,其對(duì)應(yīng)的最小生成樹(shù)為MST(C,E),則集合C的內(nèi)部差異為最小生成樹(shù)中最大的權(quán)重,即

集合C1、C2之間的差異為連接這2個(gè)集合邊的最小權(quán)重,即

如果C1、C2之間不存在任一邊的連接,則定義Dif(C1,C2)=∞.Dif(C1,C2)只考慮C1、C2之間最小權(quán)重的邊,目的是為了避免NP-hard問(wèn)題[7].

通過(guò)式(1)、(2)的定義,可引出區(qū)域比較謂詞D,即

1.4 基于最小生成樹(shù)的圖論分割算法流程

若圖G(V,E)中存在n個(gè)節(jié)點(diǎn)和m條邊,V的分割結(jié)果對(duì)應(yīng)集合S=(C1,…,Cr),則分割算法流程如下[5].

輸入:G(V,E),|V|→n,|E|→m

1)邊集E非遞減排序?yàn)?π(e1,e2,…,em),其中w(e1)≤w(e2)≤…≤w(em).

2)S0對(duì)應(yīng)初始分割,即圖中每個(gè)頂點(diǎn)vi對(duì)應(yīng)1個(gè)子區(qū)域.

3)第4步循環(huán)m次,其中q=1,2,…,m.

4)由動(dòng)態(tài)分割集Sq-1構(gòu)造分割集Sq:已知若,則合并Sq-1中2元素和,子區(qū)域合并后Sq-1→Sq;否則 Sq=Sq-1.

5)S←Sm.

輸出:分割結(jié)果S

區(qū)域比較謂詞定義之后,分割算法[5]的實(shí)質(zhì)就是利用最小生成樹(shù)尋找圖像同質(zhì)區(qū)域的過(guò)程,并且使用按級(jí)合并和路徑壓縮2種試探法[8],使之能在近似線性的時(shí)間O(n log n)內(nèi)完成圖像的分割.另外,它使用分離集森林?jǐn)?shù)據(jù)結(jié)構(gòu),數(shù)據(jù)表達(dá)簡(jiǎn)單,操作方法快速而有效.

2 肝腫瘤CT圖像分割實(shí)驗(yàn)

2.1 原始肝腫瘤CT圖像獲取

文中的CT圖像來(lái)自中國(guó)人民解放軍總醫(yī)院提供的臨床數(shù)據(jù).一組完整的腹部肝腫瘤序列圖包含45張DICOM格式的CT圖像,像素大小為0.703mm ×0.703mm ×2.5 mm.為增加分割的難度,保證評(píng)價(jià)具有全面性和客觀性,選擇序列圖中的34#切片作為實(shí)驗(yàn)圖像(見(jiàn)圖1),該圖像具有腫瘤邊界模糊、腫瘤灰度不均勻和腫瘤不連續(xù)等特點(diǎn).

2.2 肝腫瘤CT圖像到圖的映射

定義無(wú)向加權(quán)圖G(V,E),肝腫瘤CT圖像的像素pi對(duì)應(yīng)圖的節(jié)點(diǎn)vi,2像素之間的相鄰關(guān)系對(duì)應(yīng)圖的邊ei,這里每個(gè)像素采用8領(lǐng)域系統(tǒng).節(jié)點(diǎn)屬性對(duì)應(yīng)像素的灰度值,邊權(quán)重函數(shù)w((vi,vj))定義為邊上2相鄰像素灰度值的絕對(duì)差值

式中I(pi)為像素pi的灰度值.

2.3 肝腫瘤CT圖像分割流程

圖1 肝腫瘤CT圖像Fig.1 CT image of liver tumor

技術(shù)上的原因造成各種噪聲污染肝腫瘤的邊緣信號(hào),因此分割前采用高斯濾波器對(duì)肝腫瘤CT圖像進(jìn)行光滑處理,并有助于消除偽影,文中高斯分布參數(shù)Sigma取為0.8.分割算法[5]的優(yōu)點(diǎn)是能保留特征變化緩慢區(qū)域中的細(xì)節(jié),然而這個(gè)優(yōu)點(diǎn)往往導(dǎo)致圖像出現(xiàn)過(guò)分割的缺點(diǎn),需使用小區(qū)域合并準(zhǔn)則以避免過(guò)分割.小區(qū)域合并參數(shù)Minsize取值越大,抑制小區(qū)域的效果越明顯,通常其取值范圍為[100,200].由于人眼對(duì)彩色信號(hào)的分辨率很強(qiáng),本文采用偽彩色處理技術(shù),分割結(jié)果使用3通道(R,G,B)隨機(jī)產(chǎn)生的偽彩色標(biāo)記分割子區(qū)域.分割流程圖分為預(yù)處理模塊、核心算法處理模塊和后處理模塊(見(jiàn)圖2).

2.4 肝腫瘤CT圖像分割結(jié)果

分割算法的實(shí)現(xiàn)平臺(tái)是惠普工作站(HP xw8400),操作系統(tǒng)為Windows XP,算法編程環(huán)境為Visual C++6.0.考慮到統(tǒng)計(jì)檢驗(yàn)對(duì)實(shí)驗(yàn)樣本數(shù)量的要求,本文選用6例不同肝癌患者的CT圖像序列圖,其中肝腫瘤圖像共有52張且圖像質(zhì)量好壞不一,對(duì)每張圖像進(jìn)行分割實(shí)驗(yàn),肝腫瘤分割結(jié)果都令人滿意.

為客觀評(píng)價(jià)基于最小生成樹(shù)的圖論分割算法,對(duì)52張肝腫瘤CT圖像由專業(yè)醫(yī)生手工描記腫瘤邊界,以此作為金標(biāo)準(zhǔn),并采用平均最小距離L和面積交迭度O兩個(gè)量化指標(biāo)定量分析算法的精度[9].設(shè)算法所提取出的輪廓曲線和金標(biāo)準(zhǔn)對(duì)應(yīng)的邊界曲線分別為A={α1,α2,…,αp},B={b1,b2,…,bq},則L和O的定義為

圖2 肝腫瘤CT圖像的分割流程圖Fig.2 Segmentation flowchart for CT image of liver tumor

式中,L描述2條邊界曲線之間的平均差異,取值越小表示分割質(zhì)量越好;O反映的是分割輪廓圍成的區(qū)域與真實(shí)區(qū)域之間的差異,取值越大表示分割質(zhì)量越好;h(α,B)為

實(shí)驗(yàn)參數(shù)經(jīng)多次調(diào)整,K和Minsize分別取為400和126,圖1中的肝腫瘤分割結(jié)果理想(見(jiàn)圖3).分割過(guò)程由計(jì)算機(jī)全自動(dòng)完成,分割時(shí)程大約2 s,分割速度快.肝腫瘤分割結(jié)果顯示為紅色區(qū)域,與原始CT圖像(見(jiàn)圖1)對(duì)比可以發(fā)現(xiàn),紅色腫瘤區(qū)域大小、形狀與圖1的腫瘤區(qū)十分接近,并能把圖1中斷開(kāi)的相鄰腫瘤區(qū)連接起來(lái).另外,肝臟分割結(jié)果顯示為紅褐色區(qū)域,與圖1肝區(qū)匹配程度高,分割結(jié)果也可用于肝臟三維重建.圖3中2個(gè)相鄰的較大子區(qū)域間容易形成細(xì)長(zhǎng)的冗余區(qū)域,這些區(qū)域?qū)τ趫D像內(nèi)容來(lái)說(shuō)毫無(wú)意義,可通過(guò)修改鄰域系統(tǒng)最大程度地消除這些區(qū)域[10].

以文獻(xiàn)[11]報(bào)道的基于圖割(graph-cut)的肝腫瘤自動(dòng)分割算法進(jìn)行分割精度量化指標(biāo)比較,對(duì)52例肝腫瘤CT圖像分別采用專家手動(dòng)分割方法、本文方法和基于圖割的方法進(jìn)行分割.圖4(a)、(b)、(c)分別為圖1由3種分割方式得到的分割結(jié)果.圖4(b)與圖4(a)中腫瘤分割區(qū)域形狀相似,兩者對(duì)應(yīng)的區(qū)域大小基本相同,但圖4(b)在東偏北方向上明顯凸出且分割區(qū)域面積略大于圖4(a)中分割區(qū)域面積;圖4(c)與圖4(a)中分割區(qū)域形狀差異較大,圖4(c)與圖4(a)相比在西南方向和正北方向較凸,但兩者分割的區(qū)域面積基本相等.針對(duì)腫瘤邊界,本文方法的L指標(biāo)值為8.754 0,優(yōu)于基于圖割的分割算法(13.2480);針對(duì)腫瘤區(qū)域,本文方法的O指標(biāo)值為95.15%,略大1.38%,優(yōu)勢(shì)不明顯.綜合2種分割算法的精度量化指標(biāo)可知,它們都能有效地分割出肝腫瘤.相比而言,本文方法的分割效果優(yōu)于基于圖割的分割方法.

圖3 肝腫瘤CT圖像的分割結(jié)果Fig.3 Segmentation result for CT image of liver tumor

圖4 3種方法的分割結(jié)果Fig.4 Segmentation results by threemethods

3 結(jié)束語(yǔ)

作者使用基于最小生成樹(shù)的圖論分割算法對(duì)肝腫瘤CT圖像進(jìn)行分割實(shí)驗(yàn)研究,結(jié)果顯示該算法具有以下主要優(yōu)點(diǎn):

1)分割過(guò)程不需要人為干預(yù),它是一種收斂性和健壯性較好的自動(dòng)分割算法.

2)可分割形狀、大小各異的肝腫瘤,包括邊界模糊和灰度不均勻的肝腫瘤CT圖像,腫瘤邊界分割結(jié)果清晰.

3)除肝腫瘤的分割外,還可以有效地提取出其他組織(如肝臟),不同腹部組織的分割結(jié)果可以表現(xiàn)圖像的全局特征,符合人眼的視覺(jué)特性.

4)運(yùn)算效率高,分割速度快.

[1]任新穎.腫瘤熱療中組織溫度場(chǎng)測(cè)量方法及關(guān)鍵技術(shù)研究[D].北京:北京工業(yè)大學(xué)生命科學(xué)與生物工程學(xué)院,2008.REN Xin-ying.Study on method and key technique of tissue temperature estimation in hy perthermia[D].Beijing:College of Life Science and Bioengineering,Beijing University of Technology,2008.(in Chinese)

[2]MYUNGEUN L,SOONYOUNG P,WANHYUNC,etal.Segmentation of medical images using a geometric deformable model and its visualization[J].Can JElect Comput Eng,2008,33(1):15-19.

[3]黃荔麗,王博亮,黃曉陽(yáng).基于DICOM格式的肝臟腫瘤CT圖像分割[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(1):48-51.HUANG Li-li,WANG Bo-liang,HUANG Xiao-yang.Segmentation of liver tumor in CT image based on DICOM format[J].Computer Technology and Development,2008,18(1):48-51.(in Chinese)

[4]WITHEY D J,KOLES Z J.Medical image segmentation:methods and software[C]∥2007 Joint Meeting of the 6th International Symposium on Noninvasive Functional Source Imaging of the Brain and Heart and the International Conference on Functional Biomedical Imaging.Piscataway,NJ:Inst of Elec and Elec Eng Computer Society,2007:140-143.

[5]PEDROF F F,HUTTENLOCHER D P.Efficient graph-based image segmentation[J].International Journal of Computer Vision,2004,59(2):167-181.

[6]LUCCHESEYZ L,MITRAY SK.Colour image segmentation:a state-of-the-art survey[C]∥Proceedings of the Indian National Science Academy(INSA-A).Delhi,Indian:Natl SciAcad,2001,67(2):207-221.

[7]DRORIL,PELEG D.Faster exact solutions for some NP-hard problems[J].Theoretical Computer Science,2002,287(2):473-499.

[8]CORMEN T H,LEISERSON CE,RIVESTR L,et al.Introduction to algorithoms[M].Beijing:The MIT Press,1990.

[9]SAHINER B,PETRICK N,HEANGPC,etal.Computer-aided characterization ofmammographicmasses:accuracy ofmass segmentation and its effects on characterization[J].IEEE Transactions on Medical Imaging,2001,20(12):1275-1284.

[10]譚志明.基于圖論的圖像分割及其嵌入式應(yīng)用研究[D].上海:上海交通大學(xué)圖像通信與信息處理研究所,2007.TAN Zhi-ming.Research on graph theory based image segmentation and its embedded application[D].Shanghai:Instituteof Image Communication＆Information Processing,Shanghai Jiao Tong University,2007.(in Chinese)

[11]MASSOPTIER L,CASCIARO S.Fu lly automatic liver segmentation through graph-cut technique[C]∥Annu Int Conf IEEE Eng Med Biol Proc.Piscataway,NJ:Instof Elec and Elec Eng Computer Society,2007:5243-5246.

(責(zé)任編輯 梁 潔)

Graph-based Method for Liver Tumor CT Image Auto-segmentation

AIHai-ming,WU Shui-cai,GAOHong-jian,ZHAO Lei,ZENG Yi
(Biomedical Engineering Center,Beijing University of Technology,Beijing 100124,China)

A novel method for liver tumor CT image auto-segmentation is proposed in this paper.By utilizing minimal spanning tree of graph,the method can search for homogeneous region of image,and image segmentation can be conducted in time with union by rank and path compression.The method is evaluated via52 liver tumor CT images,the results demonstrate that average minimum euclidean distance(AMED)and area overlap measure are 8.754 0 and 95.15%respectively,and segmentation accuracy is optimal.These results show that the proposed method can auto-segment liver tumor quickly and precisely.

graphic theory;CT image;image auto-segmentation

TP391.41

A

0254-0037(2010)04-0572-05

2008-12-03.

北京市自然科學(xué)基金資助項(xiàng)目(3072004).

艾海明(1980—),男,江西九江人,博士研究生.