序列图像三维重建中的关键算法

方 欣, 郭观七, 沈中阳

(1. 湖南理工学院 信息与通讯工程学院, 湖南 岳阳 414000; 2. 资兴市青少年活动中心, 湖南 郴州 423400)

序列图像三维重建中的关键算法

方 欣1, 郭观七1, 沈中阳2

(1. 湖南理工学院 信息与通讯工程学院, 湖南 岳阳 414000; 2. 资兴市青少年活动中心, 湖南 郴州 423400)

主要讨论了基于序列图像的三维重建中的两个关键算法: 特征数据点列的重采样算法与三角化算法. 本文改进了Chetverikov等提出的轮廓曲线中高曲率点的检测算法, 使在重采样时, 数据的压缩比得到了明显的改善, 也显著地提高了可视化速度. 并使用一种简单的三角化算法, 对重采样后的数据点列进行三角化, 实现目标的三维重建.

图像序列; 三维重建; 高曲率; 重采样; 三角化

Abstract:Two important algorithm in 3D reconstruction of image sequences are studied, i.e. re-sampling algorithm and triangulation algorithm. An improved algorithm for detection of high curvature points in planar curves is presented. This algorithm can improve the performance of re-sampling and 3D data field visualization. Triangulation is implemented by using a simple triangulation algorithm. Sequentially, 3D object reconstruction was achieved.

Key words:image sequence; 3D reconstruction; High Curvature; re-sampling; triangulation

引言

随着计算机软硬件技术和医学成像技术的日益发展, 基于数字图像技术的医学应用系统也得到了长足的发展. 在这些医学应用系统中, 在有效精确地提取出医学图像中相应目标特征量的基础上, 进行人体组织或器官的三维重建[1], 是很多实用系统的基础, 如基于图像的病理分析[2]、基于图像的手术导引与增强[3]、虚拟手术平台[4]等应用系统, 因此医学图像的三维重建一直是国内外医学界及图像处理领域的研究与应用热点之一.

三维重建的目的是从一系列二维切片数据(图像)中得到物体的三维表示, 一般使用网格的形式来表示. 目前, 三维重建过程中经常沿用的一种经典算法是Lorensen等人于1987年提出的Marching Cubes方法[6], 其原理简单, 易于实现. 但这种方法计算效率低, 输出的三角网格数量巨大. 因此近些年来, 研究者们从不同角度对该算法进行改进[5,7,8]. 本文在文献[5]的基础上提出了一种基于轮廓的三维重建方法, 运用并改进了相关算法, 与直接运用文献[5]所提出的算法相比较, 本文所提出并改进的方法处理速度更快,输出的三角网格数量也较少, 而且三角网格的形态也比较理想.

1 算法描述

作者实现基于序列图像三维重建的主要思路如下:

(1) 特征提取: 在序列图像中提取出需要重建目标的轮廓;

(2) 特征点列重采样: 将(1)中检测出的边缘按创建Chain-code的方法, 形成点列, 并对此点列进行重采样, 以减少后续阶段中处理的数据量;

(3) 基于轮廓的空间点三角化: 采用一种简单有效的三角化算法, 对(2)中重采样后的点列进行三角化, 形成三角面片;

(4) 三角面片的可视化: 使用OpenGL技术, 实现重建目标的三维显示.

本文主要讨论了第(2)与第(3)过程中所采用及改进的算法. 特征点列重采样采用文献[5]所描述的算法,但该算法主要应用于轮廓曲线上高曲率点的检测, 而应用于重采样时, 数据的压缩比并不理想, 本文提出了对该算法的改进方法, 使得重采样数据的压缩比得到了明显改善.

经过实验测试比较, 在提取序列图像中目标的边缘轮廓过程中, 使用传统的Robert算子或Canny算子,能较好地保证分割出来的边缘是单像素点. 否则的话, 则可使用细化(Thinning)算法作进一步处理. 当得到单像素点的边缘后, 按照创建Chain-code的方法, 扫描检测出的边缘点, 由此而形成点序列, 便于重采样算法的操作.

1.1 特征点列重采样

文献[5]提出了一种两次扫描算法: 对获得的特征点列进行两次扫描. 第一次扫描, 选择出可能的高曲率点, 作为重采样点列的候选点; 第二次扫描, 根据特定的条件, 在第一次扫描所产生的候选点中进一步剔除一些点, 形成最终的重采样点列结果.

(1) 第一次扫描

在本次扫描中, 文献[5]中采用一种非严格数学意义上的高曲率定义. 如图1所示, 在当前所处理的点P两侧, 分别找出满足表达式(1)与(2)的点对与P+, 并计算出由此三点所构成三角形的一个内角α, 如果角α满足表达式(3), 则称P为高曲率点, 将其作为重采样点列的候选点. 继续处理轮廓点列中的下一个点, 如此反复, 直到所有轮廓点处理完毕. 记录所有候选点的坐标值及其一个内角α.

(2) 第二次扫描

如图2所示, 在第一次扫描所产生的候选点列中选择一个初始处理点P, 在其一侧查找满足表达式(4)或(5)的所有点Pv, 如果有任意一个点Pv使表达式(6)成立, 则P点被剔除. 继续处理下一个候选点, 如此反复直至处理所有候选点, 最后所剩下的点就是重采样点列.

式中: α(P)表示在第一次扫描过程所记录下来的P 点所对应的三角形内角.

图1

图2

(3) 算法中的参数

算法在上述表达式(1)～ (5)中使用了三个可调参数: dmax, dmin,αmax, 分别表示距离的最大、最小值与角度的最大值. 文献[5]中设定 dmax= dmin+ 2. 如图3中(a)～(d)分别是dmin与αmax取不同值时的实验结果.

(4) 算法改进

作者在自己实现的上述算法测试程序中, 以及在文献[5]所提供的网站上进行实验比较, 在两次扫描过程中设定参数为 dmax= 5, dmin= 3, αmax= 170时得到了该算法的最佳效果, 如图4(b)所示, 从图中可以很明显地看到, 还可以剔除大量的点, 但文献[5]所提出的算法对此已无能为力了. 经实验测试, 本文提出了如下改进方法:

增加第四个参数. 在原算法第二次扫描中, 表达式(4)与(5)中所使用参数仍然与第一次扫描中参数一致, 本文经测试, 如果增加一个与第一次扫描中无任何关系的新参数, 则重采样数据的压缩比有明显改善,即本文将式(4)与(5)中参数dmax的值设置为10, 与式(1)与(2) 中参数dmax无约束关系. 如图4所示, (a)是用来处理的原始切片图像, (b)是使用文献[5]的算法处理结果图, (c)是改进算法处理结果图.

图4 特征点列重采样结果

原始算法的检测结果, (c)是使用改进算法的检测结果. 显然(c)所示结果图中产生的点数量比(b)要少得多, 也即重采样的压缩比高, 同时仍然可以逼真的拟合原始轮廓曲线.

1.2 简单的三角化算法

在这一过程中, 对重采样后的轮廓点列采用如下简单的三角化算法:

(1) 对所有序列图像中重采样后的轮廓点按同一方向扫描, 形成新的点序列;

(2) 在相邻两帧图像的轮廓点序列中查找出其空间距离最小的两个点;

(3) 将(2)中所选择的两点作为三角形的两个顶点;

(4) 如图5所示, 第三个顶点有两种选择方案, 但选择α角较小者作为最优三角形, 形成一个三角面片(网格).

图5 三角形的第三个顶点选择原理示意图

(5) 选择(4)生成的三角形第三边的两个顶点, 作为下一个三角形的两个顶点, 然后重复(4), 直至(2)所处理的两帧图像中所有轮廓点序列均被处理完毕.

(6) 变换相邻的两帧图像, 然后重复(2)～(5), 如此反复, 直至所有序列图像中的轮廓点列均被处理完毕.如图6中图所示, 该三角化算法所产生的三角网格形态都比较理想, 三角网格的内角基本都为锐角, 这样可改善可视化过程中计算三角网格法向量的运算速度(左图为原始切片图像, 中图为三角化后的部分三角网格, 右图为三维重建后的可视化结果).

图6

2 结束语

本文讨论了基于序列图像三维重建中的关键算法, 提出了一种改进的轮廓曲线上高曲率点检测算法,并应用于特征点列的重采样处理中. 实验结果表明, 该算法明显的改善了重采样过程中的数据压缩比, 从而使用后续处理(如三角化)的数据大大减少, 加速了可视化的处理速度. 在重庆第三军医大学所提供的人体切片图像数据集的基础上, 采用本文所讨论的算法实现了人体外形轮廓的三维重建及可视化, 取得很好的效果. 图6右图显示了运用本文提出的算法进行三维重建的可视化结果, 将本文算法(记为方法A)与运用文献[5]所提出的算法(记为方法B), 在可视化处理速度及输出三角网格数量方面进行了比较. 方法B是在提取二维图像中外轮廓后, 运用文献[5]的原始算法进行特征点重采样, 然后进行三角化及可视化处理. 在IBM ThinkPad R50(CPU为迅驰1.6G, 内存512M)计算机上测试, 仅显示图6右图所示的人体肩部以上部分, 基于面绘制的可视化处理平均时间分别为: 方法A为0.9秒, 方法B为6分. 对图6右图处理的部分, 方法A最终输出的三角网格数目为110520个, 而方法B输出三角网格数目已超过300000多个.

[1] 中国可视化人体: http://www.chinesevisiblehuman.com/

[2] 金丰华, 朱 斌, 周光泉, 等. 一个基于内容检索的医学图像数据库[J]. 山东生物医学工程, 2003(3)

[3] Grimson, W. E. L., Ettinger, G. J., Kapur, T., Leventon, M. E., Wells III, W. M., Kikinis, R.,Utilizing SegmentedMRIData in Image Guided Surgery[J], Inter. Journal of Pattern Recognition and Artificial Intelligence, 1998,11(8).

[4] Virtual Reality,Visualization and Imaging Research Centre: http://www.cse.cuhk.edu.hk/～crc/

[5] Dmitry Chetverikov and Zsolt Szabo.A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves[C]. //Proc. of 4 (k=4) the 23rd Workshop of the Austrian Pattern Recognition Group. [S. l]: ACM Press, 1999: 175～184

[6] W.Loresen and H.Cline.Marching Cubes:A high resolution 3D Surface Construction Algorithm. ACM Computer Graphics, 1987, 31(4): 163～170.

[7] R.Shekhar, E.Fayyad, R.Yagel and J.Cornhill.Octree-based Decimation of Marching Cubes Surfaces[J]. In IEEE Visualization’96 Proceedings, 1996, 335-342.

[8] Shu, R.Chen, Z.Kankanhalli.Adaptive Marching Cubes[J]. The Visual Computer, 1995, 11: 202～217

The Algorithm about 3D Reconstruction of Image Sequences

FANG Xin1, GUO Guan-qi1, SHEN Zhong-yang2
(1. College of Information & Communication Engineering, Hunan Institute of Science and Technology, Yueyang 414006, China; 2. Zixing Activity Centre for Teenagers, Chenzhou 423400, China )

TP317.4

A

1672-5298(2010)01-0035-04

2009-09-29

方 欣(1971- ), 男, 湖南岳阳人, 硕士, 湖南理工学院信息与通讯工程学院讲师. 主要研究方向: 计算机网络、图像处理