基于改进凸包算法的肺区域分割

张圣璞

摘 要 当存在边缘型肺结节的时候，常规的肺区域分割方法难以准确地完成分割。本文针对这一问题进行了研究，提出了基于改进凸包算法的肺区域分割方法，实验结果证明本文方法能够较好地分割肺区域。

关键词 肺区域分割 边界修补 凸包算法

0 序言

现有针对肺部疾病的CAD系统的主要功能包括：肺区域分割、肺部气肿的检测、肺部血管及血管的分割、肺结节的检测与分割及肺结节良恶性的判别等。[1]在有限的计算资源内如何提高计算速度及准确度，确定肺区域并精确地分割提取就显得十分重要，所以肺部区域的分割是所有的肺部CAD系统的必要步骤。作为后续检测的基础，肺区域分割的速度及准确度对于整个CAD系统的运行速度以及检测准确度具有十分重要的影响。[2]以肺结节检测为例，Armato和Sensakovic[3]研究了肺区域分割对于整个CAD系统的重要性，实验结果显示错误的肺区域分割结果将会引起5%到17%的肺结节漏检测。

针对这一问题，研究者们提出了一些边界修补方法。如Armato等[4]提出的滚球法，但是修补结果对于圆球半径十分敏感，降低了算法的通用性；王晶[5]利用端点检测的方法，但是对于过大或者过小的结节的修补结果不好；袁克虹等[6]提出的基于局部凸包的修补方法，但是需要较多的参数设置。本文针对以上方法的不足之处，提出了改进的二维凸包算法进行肺区域边界修补，能够取得较好的分割结果。

1 二维凸包算法

最早的凸包算法由Graham[7]在1972年提出，主要通过计算点集中各个点之间的夹角以及斜率的大小来判断各个点是否是凸包上的点。如图1所示，存在一组二维点集，包含了所有点的最小凸多边形就是这个点集的凸包。

Graham算法主要包含3个主要步骤：

步骤1：预处理。如图2所示，图（a）是原始点集，处理的第一步就是将其中的n个点进行排序，排序规则为：首先选择横坐标最小的点（如果有多个，则选取纵坐标最小的那个）记为，该点一定会在凸包上，连接该点与其他所有点组成n-1个向量。我们只需要分别计算每个向量与y轴的负方向之间的夹角，按照夹角的大小由小到大对所对应的点进行排序并标记，排序结果如图（b）所示。同时当存在方向相同的向量（即两个点与在同一条直线上）的情况时，根据模的大小由小到大进行排序，最终n个点分别记为，……，，如图2（b）所示。

步骤2：建立边缘堆栈。由几何学知识可以知道步骤1中得到的点和最后一个点一定在凸包上。所以首先将一定在凸包上的三点、和依次压入栈re，然后考虑下一个点，首先把点入栈，构成栈的栈顶top处为，top-1处为，此时需要利用到下一个点即的信息。利用以上信息判断和在处旋转关系，判断左转还是右转的公式如下：

（1）

如果构成左转关系，则栈顶的点也在凸包上，此时入栈，接着判断下一个元素；如果不构成左转关系，则说明栈顶元素不是凸包内的点，此时栈顶元素出栈，入栈，继续判断是否是凸包内的点，直到最后一个元素点。

步骤3：根据以上步骤得到的凸包边缘堆栈，按照顺序连接线段，即可组成点集的二维凸包，如图2（c）所示。

图3是肺区域初分割的结果示意图，可以看出当存在边缘型肺结节的时候分割出的结果并不准确。本文在初步分割的基础上，使用二维凸包算法对初分割结果进行肺轮廓细化修补，最终得到完整的肺区域图像。可以直观地发现图4（d）所示的结果与图3（c）的结果相比，右上角的病灶区域也被正确的分割出。

但是在实际的实验中我们发现，在利用常规的二维凸包算法进行肺区域边界修补的时候，虽然对于肺叶外边缘的凹陷情况有了较大改善，但是会对肺叶内边缘的轮廓造成一定的破坏，如图5中箭头所指的位置，利用本方法边界修补处理对与肺叶内边缘轮廓正常的凹陷进行了错误的修补，这不是希望看到的结果。

2 改进的二维凸包算法

统计结果表明，边缘型肺结节多数存在于肺叶外侧。针对这一特点本文改进二维凸包算法，对肺叶外侧边界进行修补。具体步骤如下：

步骤一：与常规凸包算法类似，为了减少边界修补的计算量，首先对得到的二值掩模图进行边缘检测得到其边缘轮廓，以横坐标最小的点为开始扫描，得到了肺区域边界点集。如图6（a）所示。

步骤二：利用常规二维凸包算法Graham算法步骤一对得到的边缘轮廓进行一次修补过程。首先把步骤一得到的肺区域边界点集作为凸包算法处理的点集，然后按照节中步骤二中相关规则求出这组点集合的边缘堆栈{，……，}，最后同样根据左转规则公式（2）逐一判断出边缘堆栈中的点是否是凸包点。

（p3-p1）？p2-p1）=（x3-x1）*（y2-y1）-（x2-x1）*（y3-y1） （2）

步骤三：经过以上两个步骤，我们得到了两组边缘点集S1和S3，且S3∈S1，分别是初分割结果的肺区域边界点集和凸包算法计算出的凸包点集。找出集合S3中纵坐标最大和最小的两个点qmax和qmin，且qmax，qmin∈S1。

以右肺为例，我们按照一定的规则合并点集S1和S3就可以得到一个全新的点集，其中和是凸包点，而是未修补的边界点。这样按顺序连接新的点集就得到了如图6（c）所示的修补结果，其中肺叶外边缘是凸包计算修补之后的结果，而肺叶内边界则是未修补的肺区域边界。这样在一定程度上既修补了肺叶外边界上的凹陷，又避免了因为修补而对肺叶内边界的过度修补。

3 实验结果分析

本文在公开的LIDC数据集上进行实验，选择了其中存在边缘型肺结节的图像进行具体对比实验。结果如图7所示。

图7（a）是原图像，肺部边缘存在肺结节，图7（b）是医生手工分割的金标准结果，图7（c）是经过阈值法分割后的肺区域结果，可以发现由于存在边缘型肺结节，仅利用阈值法分割出的肺部边缘上存在明显的凹陷，把肺结节分割到了肺区域以外，不利于后续的疾病诊断。图7（d）是本文方法分割结果。实验结果显示本文方法对于边缘型肺结节引起的肺区域边界凹陷具有较好的修补效果。

4 总结

本文针对因边缘型肺结节造成的肺区域边界分割不准确的情况，使用改进的二维凸包算法进行肺区域边界修补，在传统的二维凸包算法的基础上，根据人体肺部生理解剖结构对凸包算法进行约束，避免了传统二维凸包修补方法造成过度修补的情况。

参考文献

[1] Armato Iii S G， Giger M L， Macmahon H. Method and system for the segmentation of lung regions in lateral chest radiographs： US， US6335980[P].2002.

[2] 聶生东，李雯，许建荣，等.自动分割CT图像中肺实质的方法[J].中国医学影像技术，2006.22（9）：1428-1431.

[3] 杨聃.三维肺部CT图像中的结节自动识别[D].华中科技大学，2007.

[4] 3Rd A S， Sensakovic W F. Automated lung segmentation for thoracic CT impact on computer-aided diagnosis[J]. Academic Radiology，2004.11（9）：1011-21.

[5] 王晶.基于CT图像的肺实质分割算法研究[D].沈阳大学，2010.

[6] 袁克虹，向兰茜.用于计算机辅助诊断的肺实质自动分割方法[J].清华大学学报（自然科学版），2011（1）：90-95.

[7] Graham R L. An efficient algorith for determining the convex hull of a finite planar set[J]. Information Processing Letters，1972.1（4）：132-133.