基于图论的肝肿瘤CT图像自动分割方法

艾海明,吴水才,高宏建,赵 磊,曾 毅

(北京工业大学生物医学工程中心,北京 100124)

基于图论的肝肿瘤CT图像自动分割方法

艾海明,吴水才,高宏建,赵 磊,曾 毅

(北京工业大学生物医学工程中心,北京 100124)

提出了一种肝肿瘤CT图像自动分割的方法,运用图中最小生成树寻找图像的同质区域,使用按级合并和路径压缩2种试探法,使得分割时程近似线性时间O(n log n).对52幅肝肿瘤CT图像进行分割,结果表明,该方法分割实际图像的平均最小距离为8.7540,面积交迭度为95.15%,分割精确度优于同类自动分割算法.应用该方法能快速、准确地自动分割出肝肿瘤.

图论;CT图像;图像自动分割

利用肝癌微波热疗手术规划系统可在术前对温度场进行规划,这样有助于提高肝癌微波热疗的有效性和安全性.在肝癌微波热疗手术规划系统设计中首先需对肝肿瘤进行分割并三维重建[1],而肝肿瘤分割效果的好坏直接影响肝肿瘤三维重建的准确性.

由于肝脏CT图像中存在随机噪声和伪影,使得传统分割方法在分割过程中面临困难,分割结果易产生虚假边缘[2-3].手动分割和交互式半自动分割工作量大、耗时长、易受人为主观影响且分割结果重复性差,不适合分割对比度低和边界模糊的医学图像[4].因此,合理地选择一种全自动分割肝肿瘤CT图像的方法十分必要.文献[5]提出基于最小生成树的图论分割算法,它使用区域比较准则,极大化区域内部的相似性与区域之间的差异性,随着图像内容的变化能自适应地改变,因此在分割准则和理论上具有明显的优势.作者编程实现了该分割算法,并把它成功地应用到肝肿瘤CT图像的自动分割中.

1 基于最小生成树的图论分割算法

1.1 图像分割准则

图像I被分割为N个区域(Ri)的集合,应满足3个条件[6]:

2)H(Ri)=ture,∀i,H为某种同质性谓词(homogeneity predicate).

1.2 最小生成树(MST)

若V、E分别为图G(V,E)中的顶点集和边集,边(u,v)∈E且权重值为 w(u,v),则图G中生成树(T)上的权重和为

式中w(T)最小的生成树为图G的最小生成树,最小生成树的求解算法主要有Kruskal算法和Prim算法.

1.3 区域比较谓词

区域比较谓词D[5]是在分割过程中用于评价2个邻域是否存在边界的判据.谓词D通过对区域内部差异和区域间差异进行比较,使得分割结果能自适应图像数据的局部特征.

若C是分离集森林中任一集合,其对应的最小生成树为MST(C,E),则集合C的内部差异为最小生成树中最大的权重,即

集合C1、C2之间的差异为连接这2个集合边的最小权重,即

如果C1、C2之间不存在任一边的连接,则定义Dif(C1,C2)=∞.Dif(C1,C2)只考虑C1、C2之间最小权重的边,目的是为了避免NP-hard问题[7].

通过式(1)、(2)的定义,可引出区域比较谓词D,即

1.4 基于最小生成树的图论分割算法流程

若图G(V,E)中存在n个节点和m条边,V的分割结果对应集合S=(C1,…,Cr),则分割算法流程如下[5].

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

1)边集E非递减排序为 π(e1,e2,…,em),其中w(e1)≤w(e2)≤…≤w(em).

2)S0对应初始分割,即图中每个顶点vi对应1个子区域.

3)第4步循环m次,其中q=1,2,…,m.

4)由动态分割集Sq-1构造分割集Sq:已知若,则合并Sq-1中2元素和,子区域合并后Sq-1→Sq;否则 Sq=Sq-1.

5)S←Sm.

输出:分割结果S

区域比较谓词定义之后,分割算法[5]的实质就是利用最小生成树寻找图像同质区域的过程,并且使用按级合并和路径压缩2种试探法[8],使之能在近似线性的时间O(n log n)内完成图像的分割.另外,它使用分离集森林数据结构,数据表达简单,操作方法快速而有效.

2 肝肿瘤CT图像分割实验

2.1 原始肝肿瘤CT图像获取

文中的CT图像来自中国人民解放军总医院提供的临床数据.一组完整的腹部肝肿瘤序列图包含45张DICOM格式的CT图像,像素大小为0.703mm ×0.703mm ×2.5 mm.为增加分割的难度,保证评价具有全面性和客观性,选择序列图中的34#切片作为实验图像(见图1),该图像具有肿瘤边界模糊、肿瘤灰度不均匀和肿瘤不连续等特点.

2.2 肝肿瘤CT图像到图的映射

定义无向加权图G(V,E),肝肿瘤CT图像的像素pi对应图的节点vi,2像素之间的相邻关系对应图的边ei,这里每个像素采用8领域系统.节点属性对应像素的灰度值,边权重函数w((vi,vj))定义为边上2相邻像素灰度值的绝对差值

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

2.3 肝肿瘤CT图像分割流程

图1 肝肿瘤CT图像Fig.1 CT image of liver tumor

技术上的原因造成各种噪声污染肝肿瘤的边缘信号,因此分割前采用高斯滤波器对肝肿瘤CT图像进行光滑处理,并有助于消除伪影,文中高斯分布参数Sigma取为0.8.分割算法[5]的优点是能保留特征变化缓慢区域中的细节,然而这个优点往往导致图像出现过分割的缺点,需使用小区域合并准则以避免过分割.小区域合并参数Minsize取值越大,抑制小区域的效果越明显,通常其取值范围为[100,200].由于人眼对彩色信号的分辨率很强,本文采用伪彩色处理技术,分割结果使用3通道(R,G,B)随机产生的伪彩色标记分割子区域.分割流程图分为预处理模块、核心算法处理模块和后处理模块(见图2).

2.4 肝肿瘤CT图像分割结果

分割算法的实现平台是惠普工作站(HP xw8400),操作系统为Windows XP,算法编程环境为Visual C++6.0.考虑到统计检验对实验样本数量的要求,本文选用6例不同肝癌患者的CT图像序列图,其中肝肿瘤图像共有52张且图像质量好坏不一,对每张图像进行分割实验,肝肿瘤分割结果都令人满意.

为客观评价基于最小生成树的图论分割算法,对52张肝肿瘤CT图像由专业医生手工描记肿瘤边界,以此作为金标准,并采用平均最小距离L和面积交迭度O两个量化指标定量分析算法的精度[9].设算法所提取出的轮廓曲线和金标准对应的边界曲线分别为A={α1,α2,…,αp},B={b1,b2,…,bq},则L和O的定义为

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

式中,L描述2条边界曲线之间的平均差异,取值越小表示分割质量越好;O反映的是分割轮廓围成的区域与真实区域之间的差异,取值越大表示分割质量越好;h(α,B)为

实验参数经多次调整,K和Minsize分别取为400和126,图1中的肝肿瘤分割结果理想(见图3).分割过程由计算机全自动完成,分割时程大约2 s,分割速度快.肝肿瘤分割结果显示为红色区域,与原始CT图像(见图1)对比可以发现,红色肿瘤区域大小、形状与图1的肿瘤区十分接近,并能把图1中断开的相邻肿瘤区连接起来.另外,肝脏分割结果显示为红褐色区域,与图1肝区匹配程度高,分割结果也可用于肝脏三维重建.图3中2个相邻的较大子区域间容易形成细长的冗余区域,这些区域对于图像内容来说毫无意义,可通过修改邻域系统最大程度地消除这些区域[10].

以文献[11]报道的基于图割(graph-cut)的肝肿瘤自动分割算法进行分割精度量化指标比较,对52例肝肿瘤CT图像分别采用专家手动分割方法、本文方法和基于图割的方法进行分割.图4(a)、(b)、(c)分别为图1由3种分割方式得到的分割结果.图4(b)与图4(a)中肿瘤分割区域形状相似,两者对应的区域大小基本相同,但图4(b)在东偏北方向上明显凸出且分割区域面积略大于图4(a)中分割区域面积;图4(c)与图4(a)中分割区域形状差异较大,图4(c)与图4(a)相比在西南方向和正北方向较凸,但两者分割的区域面积基本相等.针对肿瘤边界,本文方法的L指标值为8.754 0,优于基于图割的分割算法(13.2480);针对肿瘤区域,本文方法的O指标值为95.15%,略大1.38%,优势不明显.综合2种分割算法的精度量化指标可知,它们都能有效地分割出肝肿瘤.相比而言,本文方法的分割效果优于基于图割的分割方法.

图3 肝肿瘤CT图像的分割结果Fig.3 Segmentation result for CT image of liver tumor

图4 3种方法的分割结果Fig.4 Segmentation results by threemethods

3 结束语

作者使用基于最小生成树的图论分割算法对肝肿瘤CT图像进行分割实验研究,结果显示该算法具有以下主要优点:

1)分割过程不需要人为干预,它是一种收敛性和健壮性较好的自动分割算法.

2)可分割形状、大小各异的肝肿瘤,包括边界模糊和灰度不均匀的肝肿瘤CT图像,肿瘤边界分割结果清晰.

3)除肝肿瘤的分割外,还可以有效地提取出其他组织(如肝脏),不同腹部组织的分割结果可以表现图像的全局特征,符合人眼的视觉特性.

4)运算效率高,分割速度快.

[1]任新颖.肿瘤热疗中组织温度场测量方法及关键技术研究[D].北京:北京工业大学生命科学与生物工程学院,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]黄荔丽,王博亮,黄晓阳.基于DICOM格式的肝脏肿瘤CT图像分割[J].计算机技术与发展,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]谭志明.基于图论的图像分割及其嵌入式应用研究[D].上海:上海交通大学图像通信与信息处理研究所,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.

(责任编辑 梁 洁)

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.

北京市自然科学基金资助项目(3072004).

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