基于GrabCut的三维医学图像分割
2016-06-23茹国宝余绍德谢耀钦
周 芹，茹国宝，余绍德，谢耀钦
(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.
