基于目标检测和区域生长的断层图像自动分割

杜建军,陆建荣,乔爱科,刘有军

(北京工业大学生命科学与生物工程学院,北京 100124)

基于目标检测和区域生长的断层图像自动分割

杜建军,陆建荣,乔爱科,刘有军

(北京工业大学生命科学与生物工程学院,北京 100124)

为了实现对序列断层图像的自动分割,提出了基于目标检测和区域生长的自动分割方法.基于待分割目标在相邻层上的相关图和相关度的定义,相关图用于表达目标在相邻断层之间的延续关系.采用目标检测算法计算出当前层上已分割图像和相关图中目标的形状参数,包括目标质心和最小外包矩形等,根据相关度为在相邻层上应用区域生长算法提供有效种子点.实验结果表明,该方法能达到序列断层图像自动分割的目的,而且其效率比基于体素的三维区域生长分割方法提高了近 50%.

目标检测;图像分割;区域生长

在医学图像处理中,自动或者半自动的图像分割方法一直是研究的难点和重点[1].目前,对断层图像的分割主要还是采用一些主流的二维分割方法,但二维分割方法在处理大量断层图像时,工作过程过于烦琐,因为大部分二维分割方法都是“有监督”的分割方法,需要人工交互来引导分割.比如:基于边界的主动轮廓图像分割方法中,需要用户提供一个理想的初始轮廓来引导算法查找目标的真实边缘[2];在水平集分割中,也需要构造初始水平集曲线或者指定种子点来构造距离图[3].对于区域生长分割方法而言,对断层图像的分割首先需要提供种子点来标定待分割目标.由于分割目标的形状和位置在不同断层图像上总是不断改变,这就需要人工为每一层或者某些关键层定义分割引导规则,一旦断层图像过多,人力工作就容易出错.目前,基于体素的区域生长分割算法已经被用于实际的图像处理中[4],但是在实际应用中有一些局限.首先,基于体素的三维分割方法处理的是大量断层图像组装成的体数据,在分割过程中这些数据需要载入内存,对计算机性能提出更高的要求;其次,分割后输出的结果一般是体数据,难以对其进行局部改进,在二维图像上可以轻易实现的裁剪等局部操作在处理体数据时难度增加;另外,基于体素的区域生长分割方法效率较低、灵活性差.

为了实现对大量断层图像的自动分割,同时克服基于体素的区域生长方法存在的问题,作者提出基于目标检测和区域生长的自动分割方法.该方法利用待分割目标在相邻断层间的相关性,提出了相关图和相关度的概念.基于相关图,针对区域生长实现了 2种自动生成种子点的方法:基于目标检测的方法和完全种子点方法.

1 区域生长算法

在医学图像中,具有强度一致性和连通性的区域分别表示不同的器官组织.区域生长算法通过选取种子点,依次将与种子点具有相似性质的像素合并到种子点所在的区域.该算法的关键是选择合适的生长准则,这些准则可以分为:简单区域生长(像素与像素)、质心型(像素与区域)以及混合型(区域与区域)[5].本文采用以像素灰度为特征的生长准则,用 f(x,y)表示二维断层图像,f′(x,y)表示分割后的结果图像,其中 x,y是二维图像的坐标.在区域生长过程中,所有满足

并且与种子点具有连通关系的像素都被合并为同一区域.式中,背景像素标记为 0;lower和 upper是由用户设置的阈值;tag为分割标记值.

由于区域生长方法仅仅利用了图像上像素的位置信息和像素本身的灰度信息,所以噪声对分割的结果影响较为严重.在应用此方法前,需要对图像进行各向异性平滑滤波,以便在稳定区域内部灰度差的情况下尽量保持目标的边缘信息[6].

2 目标检测算法

图像分割后得到的结果图像是标记图像,为了计算标记图像上区别于背景的目标个数以及每个目标的形状参数,需要利用目标检测算法.目前,用于检测图像上目标的算法有扫描线填充法、种子填充法、特殊目标的填充法和迭代填充法[7].本文采用扫描线填充法计算在分割后的二值图像上目标的个数.

基于扫描线的填充方法对图像进行从左到右、从上往下扫描(假定图像的坐标原点位于左上角)[8-9],基本操作包括求交、排序、配对和填充等.在程序中植入相应代码,一旦统计出二值图像上目标的个数,就可以计算出每个目标的有关形状参数,比如最小外包矩形区域以及质心位置等.

3 本文提出的算法

在区域生长算法中往往需要人工确定待分割目标的个数,也就是需要人工提供一系列种子点作为分割目标的生长点,自动化程度低,而采用基于体素的区域生长算法又面临计算机内存限制和灵活性问题,因此,本文利用目标检测和区域生长算法相结合的方法实现对大量断层图像的自动分割.首先根据待分割目标在断层序列图像间存在的延续性,提出了相关图和相关度的概念.利用目标检测算法计算当前层上已分割目标的信息,并构建出每个目标在相邻层上的相关图.通过计算相关度来检测每个目标在相邻层上的分叉情况,从而为在相邻断层上应用区域生长算法提供有效种子点.该方法每次仅处理 2张图像,因而不受断层图像数量的限制,对计算机性能要求低.另外,利用相关图简化断层图像在纵向的访问方式,实现了分割过程的自动化.

3.1 相关图的定义

在讨论目标检测方法与区域生长方法结合之前,首先定义待分割目标在相邻断层之间的相关性.根据序列断层图像在纵向的连续性,同一目标在相邻断层图像中如果存在,则一定具有连续性,也就是目标的像素强度和形状等特征存在相关性.断层图像中上下层相关图的生成过程如图 1所示.设上层图像为 A图,下层图像为 B图.对 A图应用区域生长分割算法后得到的结果是二值图像,图像上每个目标像素都在其最小外包矩形之中.从 A图的分割结果中按照最小外包矩形提取出该目标就得到 A1图,将其表示为 fA1(x,y).然后,将该矩形垂直投影到 B图,可得到 B1图,将其表示为 fB1(x,y).如果使用 A1图来约束目标在 B图的形状,用 B1图判定目标像素,即可得到 B2图,称 B2图是目标在上下层间的相关图.实际上,该目标在 B图上的最后分割结果是 B3图,将其表示为 fB3(x,y).

图1 目标在上下层图像的相关图Fig.1 The relation graph of objectbetween two sequential images

基于上面的定义,目标在相邻层图像上的相关图表示为

式中,相关图 B2的生成需要经过 2层筛选,即在 B2图上的每个标记为目标的像素都需要满足阈值条件,而且在上层图像对应位置的像素也必须已经被标记为目标.不难发现,相关图 B2可能是该目标在下层图像上分割的最终结果 B3,但也可能是 B3的一个子集.

提出目标在相邻层图像的相关度为

其中,COUNT为通过目标检测算法返回图像上目标个数.如果 ρ=0,表示该目标在断层间不相关,也就是在下层图像中已经不存在上层图像所描述的目标;如果 ρ＞0,则在上层图像中的目标在下层图像中存在延续.

需要指出的是,相关图和相关度的定义都是针对上层图像中单个目标而言的,如果上层图像中存在多个目标,则存在相同数目的相关图.

3.2 分叉合并检测

一般待分割的器官组织在断层图像之间形态不断变化,存在着复杂的分叉合并情况,因而对分叉合并的检测是个重要的问题.尤其是在血管的分割中,如果上层图像的分割目标在下层分解为 2个或者多个目标,就需要为下层目标的分割提供相同数目的种子点.另外,上层图像的多个目标在下层图像中也可能合并,这时需要合并表示同一目标的种子点,以提高分割效率.

根据上面的定义,相关度可以用来检测目标在下层图像上是否存在分叉以及分叉的具体情况,从而为每个分叉自动生成一个有效种子点.相关度与区域生长算法所需有效种子点的关系表示为

3.3 几何参数计算

在目标检测算法中,不仅需要求出图像上目标的个数,而且需要求出一些有用的特征量.其中每个目标的质心位置和最小外包矩形是本方法中所需要的重要参数.假设目标所在的区域 R中的目标像素个数为 N,目标的质心坐标 X(xg,yg)以及最小外包矩形区(xmin,xmax,ymin,ymax)的计算公式分别为

但是,式(5)计算出的目标质心坐标并不一定能直接作为下层图像的种子点,因为分割目标的形状可能会非常复杂,比如非凸闭包或者存在孔洞情况,都可能导致目标质心落在目标外面,或者落于目标中的孔洞,如图 2所示.根据基于阈值控制的区域生长算法的特点,如果种子点所携带的像素强度不在用户设置阈值范围内,区域将无法生长,导致分割失败,因此需要对种子点的坐标进行重新调整.

设 X点是初次求得目标的质心位置(见图 2).通过在 4个方向同步查找,将找到的第 1个满足阈值条件的像素(X')取代质心作为新的种子点.这种方法的搜索范围是目标的最小外包区.对于简单形状的目标采用图示的搜索半径 r就可以找到,而对于某些特殊形状,还需要扩展搜索半径.相对而言,这种搜索方法要比基于区域的查找适应性更强并且效率更高.

3.4 算法实现流程

图2 有效种子点Fig.2 The effective seed point

基于相关图的定义,本文将目标检测和区域生长算法结合起来实现对大量断层图像的自动分割,如图 3所示.该算法的主要步骤如下:

1)载入第 1张图像,确定需要分割的目标,提供相应的种子点和阈值范围.初始化种子点集,进入自动分割模块.

2)循环图像序列.

3)对输入图像进行区域生长分割,得到分割后的结果为 A1图.

4)将 A1图输入目标检测 1模块,计算目标个数以及每个目标的最小外包矩形.

5)检测目标的个数.如果目标个数为 0,也就是在目前的整个分割结果中已经不存在目标,后继图像也不必分割,结束整个循环.

6)如果目标个数大于 0,则循环每个目标.

7)根据式(2)求得该目标的相关图,然后将相关图输入到目标检测 2模块中计算.

8)在目标检测 2模块中求得该目标在上下层图像的相关度,根据式(4)进行分叉检测,并为每个分叉生成一个有效种子点,删除失效种子点.

9)所有目标循环完毕后,更新种子点集.

10)用新生成的种子点集作为下层图像(B图)区域生长分割方法的参数,回到步骤 3).

在算法流程中,基本每次循环中都调用了 2次目标检测算法.其中,目标检测 1模块是检测当前图像的分割结果,求出目标的个数,并确定每个目标的最小外包矩形.目标检测 2模块处理的是每个目标的相关图,目的是检测是否分叉从而生成有效种子点.一般来说,第 2次检测的范围要比第 1次小得多,所以在设计上采用种子点携带相关图的方法.这样,保证相关图在种子点创建时初始化,在种子点失效时自动销毁.

图3 算法流程图Fig.3 Flow chart of the algorithm

4 计算效率评估

根据相关图的定义,实际上还有另外一种种子点生成方法,本文称之为完全种子点方法.这种方法是将生成的相关图 B2上所有标记为目标的像素点作为种子点初始化下层图像的区域生长分割方法.这种方法也能自动检测分叉模型,但是由于每次生成的种子点过多,所以对区域生长的效率影响较大.

在相同的软硬件条件下,本文对所提到的 2种种子点生成算法与基于体素的三维区域生长算法进行比较.采用的实验数据是一名患者的腹部 CT图像(512×512),其中像素的实际大小为 0.625mm×0.625 mm,层间距 1mm.由于基于体素的分割方法在处理体数据时受到计算机内存的限制,本文仅选择 201张图像,分别用 3种方法分割出其中的腹主动脉,比较分割的效率.

由于分割的效率不仅与算法的设计有关,而且与计算机硬件的性能、图像的大小也相关(即使在同台计算机上,有其他进程抢占计算资源,最后的分割执行的时间也会有所差异),因此在尽量减少这些干扰的情况下,针对同一组图像使用这 3种分割方法各自计算 3次,取其平均值列于表 1中.

表 1 3种区域生长分割方法效率对比表Table 1 Efficiency com parison of three algorithms based on region grow ing

从表 1可以发现,本文提出的基于目标的区域生长自动分割方法在效率和内存资源的消耗上都要优于另外 2种方法.其分割效率比完全种子点方法提高了近 1/3,比三维分割方法提高了近 1/2.在201张图像的分割中,调用目标检测模块累计耗时(33.97 s),与整个分割时间(1 697.39 s)相比,仅仅占其2%.这 3种方法最后的分割结果基本一致,将采用目标检测方法得到的分割结果利用 Marching Cube算法[10]绘制出表面模型,再进行适当的平滑,最后结果如图 4所示.

完全种子点方法相对简单,但是由于生成了过多种子点,影响了区域生长算法的效率.在程序中种子点基本上都是采用栈来维护,每次种子点的入栈和出栈操作都需要消耗一定的时间[11].基于体素的区域生长分割消耗了最长的时间,原因可能是:1)系统资源的需求最大(消耗大量内存);2)维护种子点的堆栈深度以及对连通邻域的访问次数大大高于二维分割算法.基于目标检测的算法,通过构建相关图的方法简化了断层图像在纵向的访问方式,具有较好的稳定性和灵活性,而且效率比基于体素的三维区域生长分割方法提高了近 50%.

图4 分割结果的表面模型Fig.4 Surfacemodelof the segmented results

5 结束语

本文的算法是在所提出的相关图概念的基础上,利用相关图表达待分割目标在相邻断层之间的延续关系,采用目标检测算法分别计算出分割结果图像和相关图中目标的特征量,为处理后续断层图像的区域生长方法提供有效种子点.实验结果证明,该方法有效实现了序列断层图像的自动序贯分割,而且在分割效率上、灵活性以及对计算机性能的要求上都要优于基于体素的区域生长分割方法.由于目标检测算法本身的计算速度比区域生长方法快得多,因而在效率上明显优于完全种子点算法.另外,作者提出的基于目标检测的方法有较强的扩展性.针对具体的分割算法的要求定义出不同的上下层相关性公式,可以使那些难以推广到三维的二维分割方法也能达到序列断层图像的自动分割的目的.

[1]OLABARRIAGA SD,SMEULDERS AW.Interaction in the segmentation of medical images:a survey[J].Medical Image Analysis,2001,5(2):127-142.

[2]罗希平,田捷.一种改进的交互式医学图像序列分割方法[J].电子学报,2003,31(1):29-32.LUO Xi-ping,TIAN Jie.A modified interactive segmentation of medical image series[J].Acta Electronica Sinica,2003,31(1):29-32.(in Chinese)

[3]陈波,赖剑煌.用于图像分割的活动轮廓模型综述[J].中国图像图形学报,2007,12(1):11-20.CHEN Bo,LAI Jian-huang.Active contour models on image segmentation:a survey[J].Journal of Image and Graphics,2007,12(1):11-20.(in Chinese)

[4]HE X,CHEN L,SHEN B,et al.Survey of 3D segmentation algorithms for medical images[J].App lication Research of Computers,2007,24(2):13-16.

[5]WAN S,HIGGINSW E.Symmetric region growing[J].IEEE Transactions on Image Processing,2003,12(9):1007-1015.

[6]MANNIESING R,VIERGEVER M A,NIESSEN W J.Vessel enhancing diffusion:a scale space representation of vessel structures[J].Medical Image Analysis,2006,10(6):815-825.

[7]GERAETSW G,van DAATSELAAR A N,VERHEIJ JG.An efficient filling algorithm for counting regions[J].Computer Methods and Programs in Biomedicine,2004,76(1):1-11.

[8]SUZUKI K,HORIBA I,SUGIE N.Linear-time connected-component labeling based on sequential local operations[J].Computer Vision and Image Understanding,2003,89(1):1-23.

[9]HE Li-feng,CHAO Yu-yan,SUZUKI K.A run-based two-scan labeling algorithm[C]∥ICIAR 2007.Montreal:Springer-Verlag,2007:131-142.

[10]NEWMAN T S,YIH.A survey of the marching cubes algorithm[J].Computers＆Graphics,2006,30(5):854-879.

[11]倪玉山,林德生.扩充堆栈结构的种子点区域填充算法[J].复旦学报:自然科学版,2000,39(1):99-103.NIYu-shan,LIN De-sheng.A new seed fill algorithm with extending the structure stack[J].Journal of Fudan University:Natural Science,2000,39(1):99-103.(in Chinese)

(责任编辑 梁 洁)

Automatic Segmentation of Tomographic Images Based on Object Detecting and Region Growing Algorithms

DU Jian-jun,LU Jian-rong,QIAO Ai-ke,LIU You-jun
(College of Life Science and Bioengineering,Beijing University of Technology,Beijing 100124,China)

The authors put forward an automatic segmentation algorithm for tomographic images based on the combination of object detecting and region growing algorithms.The relation graph and correlation degree are firstly defined by the strict rules based on the continuity of the object to be segmented between two sequential images.Then several useful shape parameters of the ob ject in the previous segmented image and relation graph,including the center and the least surrounding boxes,are obtained by objectdetecting algorithm.Finally effective seed points,which are generated according to the correlation degree,is used to initialize the parameters of region growing algorithm for the latter slice.The experimental results show that the new algorithm can automatically segment serial images,and improve efficiency by factor of about 50%compared to the algorithm of voxel-based region growing.

object detecting;image segmentation;region growing

TP 301.6

A

0254-0037(2010)04-0566-06

2008-04-11.

国家自然科学基金资助项目(10772010,30470450,10872013);北京市自然科学基金资助项目(3062003,3092005).

杜建军(1976—),男,四川仁寿人,博士研究生.

刘有军(1965—),男,山西繁峙人,教授,博士生导师.

book=64,ebook=64