基于GrabCut的三維醫學圖像分割
2016-06-23 08:07:00茹國寶余紹德謝耀欽
電視技術 2016年2期
周 芹，茹國寶，余紹德，謝耀欽
(1. 武漢大學 電子信息學院，湖北 武漢 430072；2. 中國科學院 深圳先進技術研究院，廣東 深圳 518055)
基于GrabCut的三維醫學圖像分割
周芹1，茹國寶1，余紹德2，謝耀欽2
(1. 武漢大學 電子信息學院，湖北武漢430072；2. 中國科學院深圳先進技術研究院，廣東深圳518055)
摘要:為了解決三維醫學分割中手動分割操作復雜，效率低和傳統分割方法速度慢，用戶交互多，效果不理想等問題，將傳統GrabCut算法進行了改進。首先，通過將二維的GrabCut算法擴展到三維，減少了三維分割的交互過程，提高了三維分割的效率；其次，將三維分割的矩形框交互改進為多邊形交互，提高了交互的精度，改善了分割后的結果。通過對兩組數據的分割結果對比表明，改進后的算法相對于置信連接算法不僅交互簡單、速度快，而且分割效果有了很大的改善。最后，通過不同用戶對同一組數據的分割結果對比，證明改進后的三維GrabCut算法穩定性高、速度快，能很好地完成三維醫學圖像的分割。
關鍵詞:GrabCut ；圖像分割；三維；多邊形交互
三維圖像分割是正常組織和病變組織的三維可視化、手術模擬、圖形引導手術等后繼操作的基礎，也是測量標注、結構分析、運動分析等定量分析的前提，分割的準確性對醫生判斷疾病的真實情況并做出相應的診斷計劃至關重要[1]。但是，手動分割操作繁瑣、效率低下。國內外已提出很多三維分割的算法，如閾值分割、區域增長、分裂合并、分類器、聚類等方法[2]，每種方法都有自己的優缺點，閾值分割算法簡單，但依賴于閾值的選擇，且對噪聲和灰度多樣性敏感；區域增長對人工選擇種子點的要求很高，且容易導致區域內有空洞；分裂合并算法不需要選取種子點，但是計算量巨大；分類器算法需要人工獲得訓練數據，耗費時間，且人體的差異將導致使用相同訓練集后分割結果出現誤差；聚類算法不需要訓練數據，但依賴于初始化參數且對噪聲敏感。
本文采用基于圖論的分割方法，通過將GrabCut算法進行改進，得到的三維分割算法相比于傳統的置信連接[3]算法，不僅能大大減少用戶的交互，而且分割速度快，魯棒性高，分割結果也有了很大的改善。
1GrabCut算法原理
1.1Graphcut算法簡介
Graphcut算法由Boykov于2001年提出[4]，這篇文章系統的介紹了如何構造圖和能量函數來解決立體視差、 分割等問題。該算法將最小割算法應用于所建的圖中，將圖分割成前景和背景兩部分。在此基礎上，Boykov提出了交互式Graphcut多維分割的可能性[5]，該文章介紹了Graphcut在視頻序列和三維醫學圖像分割中有著非常好的結果。另外，Boykov于2004年比較了Graphcut同snakes，activecontours，level-sets等方法的優勢[6]，并呈現了對使用Graphcut進行圖像分割的多種建議的一個完整的回顧。自算法提出后，有很多文獻將Graphcut應用到了圖像分割的不同領域[7-8]。一個基于Graphcut算法的重大改進是GrabCut算法的提出[9]，它減少了用戶交互并改善了分割結果。將GrabCut用于人體序列切片分割就是GrabCut應用的一個很好的例子[10]。
Graphcut把圖像分割問題與圖的最小割問題相關聯。近年來，最大流最小割算法廣泛用于能量最小化。這種算法將圖片中的每個像素作為圖論中所建圖的一個節點，并通過有權值的邊與其他節點相連。當圖建成后，通過圖得到一個能量函數，通過最小割算法得到能量的最小值。這個方法由D.Greig[11]于1989年提出，這樣，可以通過最大流算法快速有效的得到圖像的最小割。
Graphcut首先用一個無向圖G=
圖像對應的s-t圖如圖1所示，每個像素對應圖中的一個相應結點，另外還有s和t兩個頂點。圖1有兩種邊，實線的邊稱作n-links，表示每兩個相鄰普通頂點連接的邊(相鄰頂點的個數為8)，虛線的邊稱作t-links，表示每個普通頂點與s和t連接的邊。圖中每條邊都有一個非負的權值we。
圖1 s-t圖
Graphcut中的割是指這樣一個邊的集合，該集合中所有邊的斷開會導致殘留“S”和“T”圖的分開。如果一個割，它的邊的所有權值之和最小，那么這個就稱為最小割，也就是圖割的結果。
Graphcut屬于人工交互分割算法，用戶需要做的就是指定前景和背景點，該算法則根據用戶指定的前背景來完成分割。
1.2GrabCut算法簡介
GrabCut[9]通過迭代的Graphcut對Graphcut進行改進。該算法利用了圖像中的紋理(顏色)信息和邊界(反差)信息，只要一個矩形框即可得到比較好的分割結果。
GrabCut能量函數[9]公式為
E(α,k,θ,z)=U(α,k,θ,z)+V(α,z)
(1)式中：k=(k1,…，kn,…，kN)作為每個像素高斯混合模型參數，kN就是第n個像素對應于哪個高斯分量，且kN∈{1,2,…,K}；U為區域項；V為邊界能量項；θ為圖像前景與背景的高斯混合模型參數；α=(α1,α2,…,αn)，αn∈(0,1)，為不透明度，0為背景，1為前景。
1.2.1n-links的計算
N(m,n)=k×e-B‖Cm-Cn‖
(2)
式中：‖Cm-Cn‖代表像素點m和n在RGB顏色空間內的歐幾里得距離；k為常值50[13]。而B的值由式(3)給出[5]
(3)
式中：P為像素點的個數；V代表每個像素點的鄰域點個數。
1.2.2t-links的計算
用戶選擇感興趣區域后，矩形框內為可能前景，框外為背景，對于框內未知的像素，需要計算該像素的混合高斯模型的值來決定該像素屬于前景還是背景。假設每個像素與源點連接的t-link值為T1，與匯點連接的t-link值為T2，若一個像素確定為前景，則賦值T1=K，T2=0(K為每條邊權值的最大可能值，在程序中取為450)，類似，若一個像素確定為背景，則賦值T1=0， T2=K。若一個像素不確定為前景還是背景，需要通過式(4)[14]來分別計算該像素屬于前景高斯模型和背景高斯模型的概率
(4)
式中：k代表高斯分量的個數(一般為5)；P(m,i)是該像素屬于高斯分量i的概率。
1.3GrabCut操作
如圖2所示，對于任意一幅二維圖像，如圖2a，只需在所需要的部分外畫上一個矩形框，則可以得出比較好的分割結果，如圖2b。
a 原圖 b 分割后的結果圖2 GrabCut操作示意圖
2GrabCut算法的改進
2.1GrabCut二維擴展到三維
GrabCut對于二維分割具有時間短、交互少、效果好等特點，本文將原始的二維算法擴展到三維。
本文對原始的二維算法進行了如下幾個改進：
1)將s-t圖中二維圖像像素點對應的平面圖改為立體圖。將三維數據中的每一個像素點對應于立體圖中的一個頂點，同樣，在網絡圖中還有兩個特殊的節點：源點s和匯點t。源點s連接了用戶選擇區域的各個體數據構成前景，而匯點t連接了用戶未選擇區域構成背景。所有節點與源點匯點連接的邊叫t-links。這些邊的權值通過高斯混合模型計算。前景和背景均由5個高斯分量組成。每個高斯分量屬于一個高斯混合模型。
2)將原始算法中n-links中的8鄰域改為26鄰域。同時，n-links相鄰兩點之間的距離變為1(體對角線)。相應地，建圖時每個頂點由之前所需的8條邊變為26條邊。
3)考慮到醫學圖像都是黑白的灰度圖像，原GrabCut算法利用彩色圖像的三通道來對圖像進行處理，筆者將原始算法中處理彩色的三通道改進為單通道，同時，原三通道算法中高斯模型對應的3個均值，9個方差和1個權值變為1個均值，1個方差和1個權值，經過改進后的算法大大節省了內存和程序的運行時間。
4)在用戶交互方面，考慮到用戶指定感興趣的立方體比較麻煩，筆者選取其中的一層，對這一層通過用戶畫矩形框來指定該層的感興趣區域，其余各層的矩形框則與該層的矩形框大小和位置相同，這樣，就等同于在三維數據上劃定了一個立方體感興趣區域。在分割完成后，針對分割結果，如果有不滿意的地方，在選取特定的層再進行分割。
同樣，改進后的三維分割算法也需要用戶在原始三維數據的基礎上指定感興趣的三維數據(指定區域內為可能前景點，區域外為背景點)。接著，該算法形成了一個網絡圖，每一個體像素都是該圖的一個節點。一旦圖建成后，由上算出圖中每條邊的權值后就可以使用最大流最小割算法了。當實現了最小割算法后，所建的圖就分為了兩個子圖。其中，與源點s相連的像素構成了前景，而與匯點t相連的像素構成了背景。
2.2GrabCut三維分割算法交互的改進
由于GrabCut算法是讓用戶通過矩形框來指定前景和背景，形狀單一，考慮到邊界不規則的時候，框內還有很多背景成分，大大地影響了交互的精度。為了提高分割結果的精確度，需要盡量將用戶交互貼近待分割物體的邊界，因此，將原算法中矩形框的交互改進為多邊形的方式，通過用戶指定邊界外的幾個點，算法將自動連接這些點形成一個多邊形，多邊形的形狀取決于用戶指定的點，點越多，用戶的交互多邊形越接近邊界，交互結果如圖3所示。
由圖3可以看出，改進后的多邊形能更好地貼近待分割物體的表面(圖3b)，且原矩形框分割結果(圖3c)的周圍還有一些細小的噪聲，邊界也比較粗糙，而多邊形分割結果(圖3d)完全消除了噪聲，邊界也非常平滑，由此看出，將交互改進為多邊形后能更好的進行分割。
a 矩形框 b 多邊形框
c 矩形框分割結果 d 多邊形框分割結果圖3 改進后的多邊形分割方法與原矩形分割方法的比較
3實驗結果及分析
3.1數據
本文測試了兩組臨床醫學數據。一組是像素點為800×800×36，物理分辨率為0.25mm×0.25mm×3mm的乳房數據。另一組是像素點為384×512×96，物理分辨率為0.5mm×0.5mm×1.0mm大腦數據。將本文改進的算法與文獻[3]提到的置信連接的分割方法進行分析比較。
3.2結果分析
3.2.1乳房數據測試
三維乳房的分割結果如圖4所示，從圖4a可以看出該乳房周圍存在很多陰影，需要通過有效的分割方法去除陰影，為后期的配準等工作做準備。
圖4a為原始數據，圖4c為置信連接方法分割的結果，圖4e為改進后的算法分割的結果。而圖4b，4d，4f分別為圖4a，4c，4d第18層的平面圖。
通過圖4的對比可以看出，原始數據存在很多噪聲，平面圖周圍存在很多黑色的陰影。置信連接方法雖然很好地去除了陰影，但是將很大一部分前景當成背景被分割，平面圖邊界變得很不清晰，內部也損失了很多內容。改進后的算法不僅很好地完成了分割，保持了平滑的輪廓，前景部分也沒有受到損失。該實驗證明改進后的三維分割算法對軟組織有很好的分割效果。
a 原始數據三維圖 b 原始數據平面圖
c 置信連接分割結果三維圖 d 置信連接分割結果平面圖
e 本文分割結果三維圖 f 本文分割結果平面圖圖4 三維乳房分割結果
3.2.2大腦數據測試
三維大腦的分割結果如圖5所示，圖5a可看出大腦周圍同樣存在很多陰影，需要進行有效的分割。圖5b為置信連接算法分割后的結果，圖5c為本文提出的算法分割后的結果。
a 原始數據三維圖
b 置信連接分割結果三維圖
c 本文分割結果三維圖圖5 三維大腦分割結果
通過圖5的比較可以看出，在分割之前，大腦周圍有很明顯的噪聲，且大腦的邊界比較模糊，置信連接方法雖然能抑制掉大部分的噪聲，但是邊界仍不清晰且周圍存在少量背景。本文提出的算法分割后的結果幾乎不存在噪聲，大腦的邊界也變得更加清晰。因此可以得出，改進的算法對大腦也有很好的分割效果。
由表1可以看出，本文算法相對于置信連接算法時間大大減少。
表1兩種算法對比
圖像大小分割時間/min置信連接本文算法乳房800×800×366.293.51大腦384×512×967.933.72
綜上所述，從主觀和客觀的角度均可以看出，本文提出的算法不僅能更好的完成分割，而且更高效，省時。
3.2.3算法穩定性測試
筆者選取了一組乳房超聲斷層掃描數據(30張，每張的大小為512×512×30)，分別對這組數據進行交互分割，隨機選取的一組分割結果如圖6所示。
圖6 分割結果示例
圖6中3個不同用戶對同一張數據分割后的結果(分割結果從左到右分別對應ZQ，RGB，YSD)，由圖中可以看出，分割后乳房幾乎不存在陰影，表面也非常圓滑，而且3個用戶分割后的結果無差異。
用Dice[15]系數來評估結果的好壞，其值由式(5)給出
(5)
式中：i取1，2，3(分別表示不同的3個人)；Vi則是每次分割后的結果。同時，每組結果的差異由單因素方差分析的方法來比較。3個用戶分別分割后的結果如表2所示。
其中，用戶1，2，3分別對ZQ，RGB，YSD。在這里采用MedCalc[16]軟件對數據進行分析，得出P值為0.194 8(1組和2組)，0.320 0(1組和3組)，0.850 9(2組和3組)，可以看到，得出的3個P值均大于0.05，
表2分割后的結果
組別均值方差1(n=30)0.9950.0062(n=30)0.9900.0203(n=30)0.9910.021
3組數據無顯著性差異，由此可看出，不同用戶的不同交互對結果沒有影響，因此可以得出，該算法具有很強的穩定性。
在這里筆者也對分割的時間進行了統計(該時間包括用戶交互時間和算法運行時間)，統計結果如表3所示。
表3分割時間的對比
組別均值/s方差/s1(n=30)61.08.102(n=30)63.19.533(n=30)65.18.23
同樣，用戶1，2，3分別對應ZQ，RGB，YSD。由于在交互過程中存在用戶對一次交互不滿意而多次交互的情況，因此，分割時間的范圍如表3所示。從該表中可以看出，即使存在著多次交互的情況，每次分割的時間也不超過73.33s，除去交互時間，該算法運行時間基本可以控制在60s以下，因此可得出改進后的算法已經基本可以滿足實時的要求。
4結束語
本文首先介紹了GrabCut算法的發展及其原理，接著對該算法作了兩個改進，即將算法從二維擴展到三維，以及將矩形框交互改進為多邊形交互，然后通過兩組數據將本文所改進算法與傳統的置信連接算法進行對比，從結果可以看出，本文改進的算法運行速度更快，分割結果更好。該算法對乳房、大腦的三維圖像均有非常好的分割效果，證明該算法對于三維醫學圖像的分割效果顯著。最后，通過3個不同的用戶對同一組數據進行分割，得出該算法還具有穩定、快速等特點。
同時，本文提出的三維分割算法也存在改進的地方，三維醫學分割算法最終需要應用于臨床，可以進一步加快算法的速度，通過加入加速模塊、利用并行處理來提高算法的速度，使該算法能更好地應用于臨床。
參考文獻：
[1]潘錦程.醫學圖像分割技術研究[D].上海：上海交通大學，2004.
[2]何曉乾， 陳雷霆， 沈彬斌，等. 醫學圖像三維分割技術[J].計算機應用研究，2007，2(13)：13-16.
[3]宋曉，程明，王博亮，等.置信連接的自動肝臟分割方法[J].計算機輔助設計與圖形學學報，2012，24(9)：1187-1192.
[4]BOYKOVY，VEKSLERO，ZABIHR.Fastapproximateenergyminimizationviagraphcuts[J].IEEEtransactionsonpatternanalysisandmachineintelligence， 2001， 23(11)： 1222-1239.
[5]BOYKOVYY，JOLLYMP.Interactivegraphcutsforoptimalboundary®ionsegmentationofobjectsinNDimages[C]//Proc.EighthIEEEInternationalConferenceonComputerVision. [S.l.]：IEEEPress，2001：105-112.
[6]BOYKOVY，FUNKA-LEAG.GraphcutsandefficientNDimagesegmentation[J].Internationaljournalofcomputervision， 2006， 70(2)： 109-131.
[7]MINGJTC，NOORNM，RIJALOM，etal.EnhancedautomaticlungsegmentationusinggraphcutforInterstitialLungDisease[C]//Proc.2014IEEEConferenceonBiomedicalEngineeringandSciences. [S.l.]：IEEEPress， 2014： 17-21.
[8]YINS，ZHAOX，WANGW，etal.Efficientmultilevelimagesegmentationthroughfuzzyentropymaximizationandgraphcutoptimization[J].Patternrecognition， 2014， 47(9)： 2894-2907.
[9]ROTHERC，KOLMOGOROVV，BLAKEA.Grabcut：interactiveforegroundextractionusingiteratedgraphcuts[J].ACMtransactionsongraphics(TOG)， 2004， 23(3)： 309-314.
[10]李嘉剛， 李小寧， 石杰， 等.GrabCut在人體序列切片
圖像分割中的應用[J]. 計算機技術與發展， 2012， 21(12)： 246-249.
[11]GREIGDM，PORTEOUSBT，SEHEULTAH.Exactmaximumaposterioriestimationforbinaryimages[J].JournaloftheroyalstatisticalsocietyseriesB(Methodological)， 1989，51(2)： 271-279.
[12]MORTENSENEN，BARRETTWA.Intelligentscissorsforimagecomposition[C]//Proc. 22ndAnnualConferenceonComputerGraphicsandInteractiveTechniques. [S.l.]：ACM，1995： 191-198.
[13]BLAKEA，ROTHERC，BROWNM，etal.InteractiveimagesegmentationusinganadaptiveGMMRFmodel[M].BerlinHeidelberg：Springer，2004.
[14]RAMíREZJ，TEMOCHEP，CARMONAR.AvolumesegmentationapproachbasedonGrabCut[J].CLEIelectronicjournal， 2013， 16(2)： 4.
[15]楊素華， 陳瓊， 羅艷芬. 基于Graph-Cuts的腦部MRI圖像腦組織提取方法[J]. 中國生物醫學工程學報， 2014， 31(5)： 525-531.
[16]HAFFEYF，BRADYRRW，MAXWELLS.Smartphoneappstosupporthospitalprescribingandpharmacologyeducation：areviewofcurrentprovision[J].Britishjournalofclinicalpharmacology， 2014， 77(1)： 31-38.
周芹(1990— )，女，碩士，主要研究領域為圖像處理；
茹國寶(1965— )，博士，教授，主要研究方向為圖像處理；
余紹德(1984— )，博士生，主要研究領域為醫學圖像處理和模式識別；
謝耀欽(1972— )，研究員，博導，主要研究領域為圖像引導放射治療、醫學影像處理和分析。
責任編輯：時雯
MedicalvolumesegmentationapproachbasedonGrabCut
ZHOUQin1，RUGuobao1，YUShaode2，XIEYaoqin2
(1.College of Electronic and Information，Wuhan University， Wuhan 430072，China；2.Shenzhen Institute of Advanced Technology，Chinese Academy of Sciences，Guangdong Shenzhen 518055， China)
Abstract:The improved GrabCut medical image segmentation algorithm is applied to solve the manual segmentation which is complex，inefficient，and traditional segmentation method which is slow，multi-user interactions，and had poor results. Firstly，by extending the two-dimensional GrabCut algorithm to three-dimensional，the GrabCut algorithm reduces the interaction of the three-dimensional segmentation and increases the efficiency of the three-dimensional segmentation. Secondly，by changing the rectangle interaction to polygonal interaction，the algorithm increases the accuracy of interaction，greatly improves the results of the segmentation. By contrast two sets of data segmentation results show that the improved algorithm is simple，fast，and segmentation results has been greatly improved compared with confidence connection algorithm. Finally，by comparing the different users of the same set of data segmentation results shows that the improved three-dimensional GrabCut algorithm not only has the advantages of simple operation，less interaction，good segmentation results，but also has high stability，high speed. It can be very good to complete the three-dimensional medical image segmentation.
Key words:GrabCut；segmentation；three-dimensional；polygonal interaction
中圖分類號:TP391
文獻標志碼：A
DOI：10.16280/j.videoe.2016.02.005
基金項目：國家“863”計劃項目(2015AA043203)；廣東省引進創新科研團隊項目(2011S013)
作者簡介：
收稿日期：2015-07-21
文獻引用格式：周芹，茹國寶，余紹德，等.基于GrabCut的三維醫學圖像分割[J].電視技術,2016，40(2):27-32.
ZHOUQ，RUGB，YUSD，etal.AmedicalvolumesegmentationapproachbasedonGrabCut[J].Videoengineering,2016,40(2)：27-32.
