利用八元数矢量积改进三维区域生长算法

吴明珠WU Mingzhu

王晓蝉2WANG Xiaochan

李兴民3LI Xingmin

利用八元数矢量积改进三维区域生长算法

吴明珠1WU Mingzhu

王晓蝉2WANG Xiaochan

李兴民3LI Xingmin

作者单位
1.广州商学院计算机系 广东广州 511363
2.南方医科大学图书馆 广东广州 510515
3. 华南师范大学计算机学院 广东广州510631

Department of Computer， Guangzhou College of Commerce， Guangzhou 511363， China

Address Correspondence to： WU Mingzhu

E-mail： wmz419@126.com

2016-02-23

中国医学影像学杂志

2016年 第24卷 第7期：549-552，556

Chinese Journal of Medical Imaging

2016 Volume 24 （7）： 549-552， 556

针对传统区域生长算法不能在有断点的血管区域继续生长的问题，本文提出一种新的基于八元数矢量积的三维区域生长算法，首先使用传统的区域生长算法，分割出连续的血管，通过梯度计算，找到血管的边缘，将其作为八元数区域生长的初始种子点，然后用种子点6个邻域的灰度构造八元数来表示种子点的特征，运用八元数的矢量积运算，进一步对于噪声等影响下的断裂血管进行有效的连接。对肝脏血管分割的结果表明，相对于传统的区域生长算法，该算法能够快速有效地分割出更多更精细的血管。

图像处理，计算机辅助；算法；体层摄影术，X线计算机；肝静脉；主动脉，腹

【Abstract】Because traditional regional growing algorithm can not continue to grow in the blood vessels which have breakpoints， we propose a new three-dimensional region growing algorithm based on octonion vector product. First， traditional regional growing algorithm is used to segment continuous blood vessels. The edges of the vessel are found by gradient calculation and used as initial seeds in the octonion growing regions. Then the six neighborhood of seeds' gray are used to construct octionions which represents the characteristics of seeds. The octonion vector product operation is used to connect the rupture vascular interfered by noise. Experimental results of the liver vessel segmentation show that the algorithm can quickly and efficiently segment more vessels compared with the traditional regional growing algorithm.

【Key words】Image processing， computer-assisted； Algorithms； Tomography， X-ray computed； Hepatic veins； Aorta， abdominal

准确精细的血管分割是医学图像三维重建与可视化及疾病诊断和手术导航的关键技术［1］。目前常用的医学图像分割方法主要分为基于区域的方法［2］、基于边缘的方法［3-7］、基于模糊连接的方法［8-10］、基于人工神经网络的方法［11-12］及基于活动轮廓的方法［13-14］。

其中基于区域的方法主要利用统一区域内的相似性识别区域。Adams等［2］首先提出种子区域生长算法，该算法基于局部像素的相似性，分割出种子点邻域中满足某些条件的像素点，是分割连通区域的常用方法，其计算简单，运算速度快，在血管连续的区域能够得到较好的分割结果。但是分割结果对种子点的选择有很大的依赖性，而且区域生长算法在有很多断点或者噪声点的血管区域可能不能继续生长，从而得不到好的分割效果。大量的研究人员致力于改进区域生长算法［15-16］。程明等［15］根据区域生长的历史数据以及血管方向信息，提出一种定向区域生长算法，用于肝脏血管的分割。由于医学图像的复杂性，单一的分割算法往往不能取得理想的分割结果。许修等［16］基于血管增强滤波联合动态阈值分割和动态阈值区域生长的血管提取方法，取得了较好的分割效果。但此方法计算比较复杂，且对图像质量的要求较高。近年来，很多研究人员将区域生长与其他分割方法相结合取得不错的结果［17-19］。Del Fresno等［17］首先采用区域生长分割出粗略的血管，然后使用粗略的血管模型作为构造可形变模型的初始几何形状，得到较精细的分割结果。Palomera-Pérez等［18］基于医学影像分割与配准算法的研发平台（ITK）的并行运算，采用多尺度特征与区域生长相结合的方法，提取视网膜血管，在精度和速度上均有很大的改进。Cseh［19］采用神经网络和区域生长结合的方法，在肿瘤分割中取得不错的效果。现有的区域生长算法大多未考虑医学图像的相邻切片之间的相关性特点，致使算法的抗噪性较低。

由于医学影像设备电子器件的噪声、容积效应、场偏移效应等的影响，生成的医学图像往往含有噪声污染，图像信息缺失，尤其是半径较小的血管在噪声影响下容易出现断裂。使用常规的区域生长算法，在血管断裂的位置会停止生长，不能得到理想的分割结果。近年，高维代数理论八元数分析［20］在图像处理中得到了重要的应用［21-22］。刘伟［21］提出了一种基于八元数乘法几何意义的边缘检测滤波器，该方法能够提取出丰富的彩色图像的边缘以及特定的颜色区域，在色彩较鲜艳的彩色图像中，取得非常好的效果。黄国恒等［22］提出一种基于八元数的彩色掌纹特征提取与识别算法，对图像进行二维小波分解后，在频率域中利用八元数构造七维向量，在掌纹提取与识别方面获得良好的效果。本文综合考虑CT序列中相邻切片图像的相关性，在空间域中利用八元数构造种子点的六维特征向量，使用八元数的矢量积性质，结合区域生长算法的思想，提出一种新的基于八元数矢量积的三维区域生长算法。

1　基于八元数矢量积的三维区域生长算法

本文提出的基于八元数矢量积的三维区域生长算法流程见图1。

1.1 区域生长 区域生长的基本方法是：从一组“种子点”开始，对其邻域进行搜索，将其中具有与种子点性质相似的像素合并成生长区域，直到所有邻域点都不符合生长规则［23］。区域生长的研究重点，一方面是初始种子点的选取，另一方面是区域合并规则的设计。在医学图像的分割中，区域生长的常用合并准则是基于种子点的灰度值，用来判断其邻域像素值是否在设定的波动范围内。如果是，则将其添加到生长区域中；否则不添加。灰度波动范围通过上下阈值设定，在CT图像中，血管的灰度值一般在180～450。区域生长算法计算简单，运算速度较快，通常可以将连通的血管树从CT图像中分割出来。

1.2 八元数乘法的矢量积表示定理 实数域上交错的有限维可除代数只有4种：实数R、复数C、四元数H、八元数O。八元数O是由Graves和Cayley于1844—1845年发现的，是一种非交换、非结合的八维代数［20］。八元数又称Cayley数。八元数形如：x=x0e0+x1e1+x2e2+ x3e3+x4e4+x5e5+x6e6+x7e7，其中e0、e1、e2、e3、e4、e5、e6、e7是八元数的一组基，满足：=－1， i=1，2，...7。令W=｛（1，2，3），（1，4，5），（2，4，6），（3，4，7），（2，5，7），（6，1，7），（5，3，6）｝。则对，有：

图1　基于八元数矢量积的三维区域生长算法

1.3 基于八元数矢量积的三维区域生长算法 传统的区域生长算法一般只考虑种子点本身的灰度信息。算法运行过程中，根据相似性准则对种子点周边的像素进行相似性判断，如果相似就加入到分割区域中，最终的算法结果是一个或多个由相似像素组成的连通区域。因此，对于因噪声而断裂的血管不能合并进来，导致分割的精细程度不够高。另外，生长过程本身也未考虑到血管结构及走向，因此有一定的弊端。而将八元数与区域生长的思想结合起来能克服上述缺点，并能分割出更细小的、不连续的血管。本文针对血管可能不连续的区域，使用种子点邻域的灰度信息表示种子点的特征，运用八元数的矢量积表示定理，判断该点是否为血管上的点。具体做法是：选择种子点的上、下、左、右、前、后6个邻域的像素值，构造一个纯八元数，并将其单位化，作为该种子点的特征向量。即一个点对应于一个六维的特征向量。6个邻域定义见图2，对于第N张切片中的点P，取与其相邻切片中的上、下2个点和当前切片中的前、后、左、右4个点的灰度值，构成纯八元数，每一分量除以八元数自身的模，得到单位纯八元数。

图2　种子点6个邻域

设当前点的坐标值为为（x，y，z），其像素值用f （x，y，z）表示。构造的纯八元数Oseed如下所示：

Oseed= f （x，y， z-1）e1+ f （x， y， z+1）e2+ f （x-1，y， z）e3+ f （x+1，y， z）e4+ f （x， y-1， z）e5+ f （x， y+1， z）e6

对其进行单位化得到种子点的特征向量O如下，用f1， f2，…，f6 表示Oseed的每一分量。

选择初始种子点后，对种子点的邻域进行搜索，如果搜索点的6个邻域组成的单位纯八元数特征向量与当前种子点特征向量的内积等于或接近1，则将该点添加到种子点区域，直到所有的点都不满足条件。

由上述描述可知，对于每个点的判断，都需要计算其6个邻域的像素值，并构造八元数，进行八元数的单位化。另外由于医学图像本身就有很大的数据量，算法的运算时间会很长，不能满足实际的应用需要，尤其是实时的手术导航。考虑到常规区域生长法在血管连续区域的分割效果较好，基于八元数矢量积的区域生长在血管断裂的位置能够发挥较大功效，所以本文首先使用1.1节介绍的常规区域生长算法，分割出连续的血管，通过梯度计算，找到血管的边缘，即有可能存在血管断裂的位置，作为八元数矢量积区域生长的初始种子点，进一步分割可能断裂的血管。具体算法流程如下：

记L（seeds）为区域生长算法的种子点列表，L （octseeds）为基于八元数矢量积表示的区域生长算法的种子点列表，R（output）为分割区域。首先初始化L（seeds），L（octseeds）和R（output）为空。①输入DICOM格式的K张M×N的CT序列图像，体数据大小为 M×N×K；在血管区域交互式选择一个种子点，并添加到L（seeds）中。②从L（seeds）中取出一个种子点作为当前种子点，搜索当前种子点的26邻域，判断像素值是否在血管的灰度值范围内。如果在，则将其添加到L（seeds）中，并将分割区域R（output）中的相应位置的像素值置为255。③循环执行②，直到L（seeds）为空。④通过梯度计算，找出当前分割区域R（output）中的血管边缘，添加到L（octseeds）中。⑤从L（octseeds）中取出一个种子点作为当前种子点，取当前种子点的6个邻域像素值，构造单位纯八元数。搜索当前种子点的26邻域作为当前分割点，计算当前分割点的八元数特征向量，并与种子点的特征向量做内积。判断内积值与1的差值是否在给定范围内。如果是，则将当前分割点添加到L（octseeds）中，并将分割区域R（output）中的相应位置的像素值置为255。⑥循环执行⑤，直到L（octseeds）为空。输出的R（output）则为最终的分割结果。

2　实验结果与分析

本算法是在Windows7 操作系统上，使用Visual Studio编程工具来实现。为了分析算法对医学图像的分割效果，验证是否能够达到血管分割的目的，取南方医科大学珠江医院提供的2套腹部CT序列作为测试图像。第一套数据S70是对肝静脉的造影数据，大小为512×512×336。第二套数据S50是对主动脉的造影数据，大小为512×512×365。对于S70，在体数据的其中一张切片中选择种子点，见图3，红色标记点为种子点，其像素值为284，并设置血管的上下阈值为［180，380］。种子点特征向量与分割点特征向量的内积与1的差的绝对值小于0.005。分别使用本文算法与区域生长算法分割后，取选择种子点的切片结果见图4，绿色部分为分割结果。

对分割结果进行三维重建得到的血管模型见图5。为了说明算法的优势，在相同的阈值条件，与文献［3］中常规的区域生长算法进行对比，区域生长的结果见图6。

图3　S70种子点选择

图4　S70二维切片的分割结果

图5　本文算法对S70肝血管分割结果

图6　区域生长算法对S70肝血管分割结果

以同样的方法对S50数据进行分割。在图7所示的切片中选择种子点，种子点的像素值为364：血管的阈值范围设置为［180，450］。种子点所在切片的分割结果见图8。对其进行三维重建后如图9所示，使用同样的阈值进行区域生长分割，三维重建后的模型见图10。

图7　S50种子点选择

图8　S50二维切片的分割结果

图9　本文算法对S50肝血管的分割结果

图10　区域生长算法对S50肝血管的分割结果

为了进一步验证本文所提出算法的分割效果，本研究将医师手工分割结果作为评价的“金标准”［24］，将上面两组实验数据S70和S50运用本文算法和传统区域生长算法进行血管分割的敏感度和特异度测试，结果见表1。

表1　两种算法的分割效果评价

由上述实验结果可见，本文提出的基于八元数矢量积的三维区域生长算法对CT序列图像的分割敏感度和特异度均相对较高，说明有较好的效果，特别适用于肝脏中血管的分割，相对于区域生长算法，能够分割出更多更精细的血管。而在运算时间上，相同的机器配置环境下对于S70数据，区域生长算法的运算时间为25 s，本文算法时间为40 s，时间消耗不大，能够满足实际应用需求。故基于八元数矢量积的三维区域生长算法在CT图像的肝脏血管分割中具有较大的优势。

本文使用八元数这一高维的数学工具，在计算过程中综合考虑多个特性，与少量特性进行处理的结果相比有明显的优势，相对于传统的血管分割算法，提高了三维重建图像的精度，运算时间也较短。种子点特征向量的构造结合了血管的结构特征，对于断裂或噪声污染的血管具有很好的适用性。

［1］ 林强， 董平， 林嘉宇. 图割方法综述. 微处理机， 2015，36（1）： 35-39.

［2］ Adams R， Bischof L. Seeded region growing. Pattern Analysis and Machine Intelligence， IEEE Transactions on Pattern Analysis and Machine Intelligence， 1994， 16（6）： 641-647.

［3］ Zanaty EA， Asaad A. Probabilistic region growing method for improving magnetic resonance image segmentation. Conn Sci，2013， 25（4）： 179-196.

［4］ 段先知， 丁亚军， 钱盛友， 等. 改进型快速ICA算法与数学形态学结合的图像分割方法. 微电子学与计算机， 2015， （2）：80-83.

［5］ 夏菁， 张彩明， 张小峰， 等. 结合边缘局部信息的FCM抗噪图像分割算法. 计算机辅助设计与图形学学报， 2014，26（12）： 2203-2213.

［6］ 王斌， 李洁， 高新波. 一种基于边缘与区域信息的先验水平集图像分割方法. 计算机学报， 2012， 35（5）： 1067-1072.

［7］ 吕晓琪， 范运洲， 谷宇， 等. 基于人工交互分水岭区域合并的医学图像分割研究. 中国医学影像学杂志， 2010， 18（6）：516-520.

［8］ 杜艳新， 葛洪伟， 肖志勇. 基于模糊连接度的近邻传播聚类图像分割方法. 计算机应用， 2014， 34（11）： 3309-3313.

［9］ 周子又， 刘奇， 任静. 基于MRI脑肿瘤的滤波方法与分割技术对比研究. 中国医学影像学杂志， 2015， 23（7）： 553-556， 560.

［10］ 张玲. 基于模糊理论及其扩展的图像分割研究及应用. 济南： 山东大学， 2012.

［11］ 安琦， 李敏， 何玉杰， 等. 一种优化脉冲耦合神经网络模型及在图像分割中的应用. 计算机科学， 2014， 41（S1）： 215-217.

［12］ 周东国， 高潮， 郭永彩. 一种参数自适应的简化 PCNN 图像分割方法. 自动化学报， 2013， 40（6）： 1191-1197.

［13］ 孟红波， 王昌明， 包建东. 用于图像分割的鲁棒的区域活动轮廓模型. 计算机科学， 2014， 41（6A）： 207-210.

［14］ 杨东亮， 邓廷权， 戴家树. 基于模糊连接度的交互式活动轮廓模型. 计算机应用研究， 2014， 31（10）： 3181-3183， 3195.

［15］ 程明， 黄晓阳， 黄绍辉， 等. 定向区域生长算法及其在血管分割中的应用. 中国图象图形学报， 2011， 16（1）： 44-49.

［16］ 许修， 郑彩仙， 王成， 等. 基于血管增强滤波的脑部静脉分割新方法. 中国医疗器械杂志， 2013， 37（4）： 240-243， 247.

［17］ Del Fresno M， Vénere M， Clausse A. A combined region growing and deformable model method for extraction of closed surfaces in 3D CT and MRI scans. Comput Med Imaging Graph， 2009， 33（5）： 369-376.

［18］ Palomera-Pérez MA， Martinez-Perez ME， Benítez-Pérez H， et al. Parallel multi-scale feature extraction and region growing：application in retinal blood vessel detection. IEEE Trans Inf Technol Biomed， 2010， 14（2）： 500-506.

［19］ Cseh Z. Neural networks combined with region growing techniques for tumor detection in ［18F］-fluorothymidine dynamic positron emission tomography breast cancer studie. SPIE， 2013： 8670.

［20］ 李兴民. 八元数分析. 北京： 北京大学， 1998.

［21］ 刘伟. 八元数及Clifford 代数在数字图像处理中的应用. 广州华南师范大学， 2010.

［22］ 黄国恒， 李兴民. 基于八元数的彩色掌纹特征提取与识别算法. 计算机工程， 2012， 38（22）： 28-33.

［23］ 宋余庆， 陈健美， 朱峰， 等. 数字医学图像. 北京： 清华大学出版社， 2008： 99.

［24］ Hooshyar S， Khayati R. Retina vessel detection using fuzzy ant colony algorithm. Canadian Conference Computer and Robot Vison， 2010： 239-244.

（本文编辑 张建军）

Improvement of Three-dimensional Region Growing Algorithm Using Octonion Vector Product

10.3969/j.issn.1005-5185.2016.07.020

吴明珠

2015-12-13

国家高技术研究发展计划863计划（2012AA 021105）；2016年广东省创新强校工程教学改革项目（GDJG2016001）；广州商学院应用型人才培养示范基地（zlgc2015005）。

TP391.4；R816.2