细小器官分割的可回溯三维种子填充新算法

许苗村，蒋先刚，李 林

(华东交通大学基础科学学院，江西南昌330013)

目前把二维种子填充推广到三维来进行人体器官组织的填充分割是最常见的，这种方法不但容易实现而且速度较快，但由于算法本身存在一些缺陷，如填充时在z向会进行图像层间的向前向后填充，即反复跳跃填充，而不是由前向后填充或由后向前填充，这就大大增加了不必要的回溯和像素的判读，降低了填充效率，同时现有的改进方法对于提高算法速度不能起到有效作用。因此本文考虑从建立交叉堆栈入手，利用填充区域像素点之间的相关性来减少组织切片间层与层之间像素点的反复跳跃填充，从而大大提高了算法的填充速度[1-5]。

为验证本文种子填充算法的可回溯性，将对人脑中较为细小的血管进行填充提取。如选取一头部的二维数字图像断层序列(共137张切片)，从中提取出血管图像以方便分析，提取后发现由于血管分支较多，每层切片上的血管数目不同，并且存在毛细血管等细小组织以及由灰度值定义血管区域存在的二义性问题，这些无疑为带回溯的种子填充带来了极大的困难。为解决这些问题，在对血管特性进行仔细研究后，采用图1中(a)，(b)分别对第44，45号原始切片图像进行分析，图1中(c)，(d)第44，45号切片上的血管图像。

图1 不同切片层面上血管的数目

1 多堆栈种子填充技术思路

由三维血管组织的拓扑关系来看，血管存在向上及向下分支而分支上又有子分支的情况，按此特性把血管分为当前填充的血管区域和分支向上的血管区域和分支向下的血管区域这3类，与此对应决定建立3个作用互补的交叉堆栈，程序设计中选取红色为填充色。

堆栈1用于单根血管的填充。问题在于仅用灰度值定义的填充区域存在二义性，即同一灰度值可能对应于多种物质，而同一物质也可能包含不同的灰度值。这就有可能在找种子点时找到的是杂质而并非真正的种子点，所以第一个种子点将由用户对感兴趣的区域来决定。鼠标点击切片上的血管区域来给出，如果此点在前一和后一切片上仍然满足填充要求就继续作为种子点或填充点，否则考虑到同一种物质一般在空间上是互相连通的，认为连通的血管每层之间必有公共点，对相邻两张切片上的像素进行对比。如果上一张中点(x，y)为已填充的红色点，而在下一切片中此点为满足填充要求的点，则把此点置为下一张切片的种子点。这样就既考虑了连通区域像素点的相关性，又消除了填充区域的二义性问题。

堆栈2将以堆栈1弹出的最后一个点作为新的种子点，对血管向下的分支进行填充。如图1(c)中血管1与图1(d)中血管2，3有公共重影点，因此是互相连通的;而堆栈1只能达到对血管1，2或1，3的填充，要使所有连通区域都能被完全填充就需要继续判断相邻两张切片像素点的相关性。如果前一张上的点(x，y)为已填充过的点，而在后一张切片中此点为满足填充要求的点，则把此点置为后一张切片的种子点压入堆栈。由此便可完成对血管2或3及类似血管分支的填充。

堆栈3适用于对血管向上分支的填充。将图1(c)与(d)顺序交换后正好体现了这种情况，即前一切片中包含血管的分支，而后一切片中是分支融合了的血管。它以前一堆栈弹出的最后一个点作为种子点，其余种子点的寻找方法与堆栈2中相反，即如果后一切片上的点(x，y)为已填充过的点，而在前一切片中此点为满足填充要求的点，则把此点置为前一张切片的种子点压入堆栈，这样便能完成对此类分支的填充。

算法对堆栈1使用一次，对堆栈2，3将多次使用，由于新种子点的选取是通过判断相邻两张切片上的像素分布情况来实现的。因此当同一位置像素点在相邻两张切片上都已填充过时，便可有效地跳过，减少了种子点的重复压栈及不必要的回溯。

2 算法步骤

(1)鼠标点击处为第一个切片上的种子点(seedpos.x，seedpos.y)。

(2)种子点压入堆栈1，结合扫描线种子填充算法。以种子点的y坐标为分界线，把填充区域分为上、下两部分，分别对这两部分沿扫描线对种子点的左、右两侧进行填充，直到边界为止，记录填充下半区域时弹出的最后一个点(x1，y1)。

(3)(x1，y1)压入堆栈2，堆栈为空时，弹出所记录的最后一个种子点(x2i，y2i)。

(4)(x2i，y2i)压入堆栈3，堆栈为空时，弹出所记录的最后一个种子点(x3i，y3i)。

(5)转到(3)运行，用(x3i，y3i)替换(x1，y1)压入堆栈，直到所有连通区域均被填充为止。

其中:i=1，2，3…。

3 实验结果与分析

为验证本文算法在入栈次数和填充时间上所做的改进，在主机主频为2.40GHz、内存为2.0 GHz的Windows XP操作系统中使用Delphi7软件开发平台编程实现了二维种子填充算法、传统三维种子填充算法和本文算法。

由于头部的骨头和血管有着相同或相近的灰度值，因此在没有考虑像素之间相关性及区域连通性的二维种子填充算法和传统三维种子填充算法下，重构出的不但有血管还包括部分骨头和其它杂质，如图2、图3所示。可以看到二维种子填充算法由于没有考虑垂直方向的种子填充问题，因此在z向上的连通性很差，图像出现阶梯状断裂，而传统的串行向两投影方向进行的二维种子填充算法是在水平方向填充的基础上加入了垂直方向的填充，这又难免会造成填充区域某些点的‘膨胀'，因此虽然消除了部分杂质。在z向上也基本无断流，但仍然造成了血管的失真显示。图4为使用本文算法填充后重构出的血管图像。可以看到此法不但在排除像素点填充二义性和连通性上达到了非常好的效果，而且填充后的血管清晰饱满，较为逼真。

图2 二维种子填充算法的填充效果

图3 串行向两投影方向的二维种子填充的填充效果

图4 本文算法的填充效果

表1 种子填充算法中效率对比

同时从表1所给的数据也可以看出，由于减少了不必要的回溯，本文算法在入栈次数上仅为二维种子填充算法的27.6%、传统算法的33%，填充时间上还不到传统算法的二分之一。此外重构时间也大大缩短了，这是因为排除了不相关的杂质而减少了重构三角面片数，从而节省了时间。因此本算法无论是在入栈次数、填充时间、重构时间还是重构质量上都有较大提高，并且达到了从一个种子点出发的空间连通域的血管回溯填充，填充效果、重构效率都比较高。

[1] 陆蓓，濮英，王小华.一种新的扫描线种子填充算法[J].中国水运，2008，8(2):152-154.

[2] 蒋先刚，涂晓斌.三维模型图形接口程序设计[J].微计算机信息，2007，23(12-1):291-293.

[3] 陈多观.一种无重复入栈的种子填充法[J].铁道师院学报，2002，19(2):29-31.

[4] 孙燮华.扫描线种子填充算法的改进[J].计算机工程，2000，26(12):142-143.

[5] 余腊生，沈德耀.扫描线种子填充算法的改进[J].计算机工程，2003，29(10):70-72.