医学图像三维重建中的关键算法罗东礼，徐大宏，赵于前(中南大学信息物理工程学院生物医学工程研究所，长沙410083)摘要：本文主要讨论了基于序列图像的三维重建中的两个关键算法：特征数据点列的重采样算法与三角化算法。
本文把Douglas-Peucker线性简化算法应用在特征边界的重采样上，数据的压缩比得到了明显的改善，也显著地提高了可视化速度。
并使用一种简单的三角化算法，对重采样后的数据点列进行三角化，实现目标的三维重建。
关键词：图像序列，三维重建，重采样，三角化The Algorithm about 3D Reconstruction of Image SequencesLuo Dongli，Xu Dahong，Zhao Yuqian(Institute of biomedical Engineering, School of Info-Physics Geomatics Engineering, CSU, Changsha 410083) Abstract This paper discusses two important algorithms in 3D reconstruction of image sequences, i.e. re-sampling algorithm and triangulation algorithm. An improved algorithm for Doulas-Peucker Line-Simplification 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 is achieved.Keywords Image Sequence, 3D Reconstruction, re-sampling, Triangulation0 引言随着计算机软硬件技术，以及医学成像技术的日益发展，基于数字图像技术的医学应用系统也逐渐得到了长足的发展。
在这些医学应用系统中，在有效精确地提取出医学图像中相应目标特征量的基础上，进行人体组织或器官的三维重建[1,2]，是很多实用系统的基础，如基于图像的病理分析[3]、基于图像的手术导引与增强[4,5,6,8]、虚拟手术平台[7]等应用系统，因此医学图像的三维重建一直是国内外医学界及图像领域的研究与应用热点之一。
三维重建的目的是从一系列二维切片数据（图像）中得到物体的三维表示，一般使用网格的形式来表示。
目前，三维重建过程中经常延用的一种经典算法是Lorensen等人于1987年提出的Marching Cubes方法[10]，其原理简单，易于实现。
但这种方法计算效率低，输出的三角网格数量巨大。
因此近些年来，仍然有研究者们从不同角度对该算法进行改进[9,11,12]。
本文在文献[13]的基础上提出了一种改进重采样算法结合文献[9]基于轮廓的三维重建方法，运用并改进了相关算法，与直接运用文献[9]所提出的算法相比较，本文所提出并改进的方法处理速度更快，输出的三角网格数量也较少，而且三角网格的形态也比较理想。
在第1小节中对算法作了描述，第2小节总结并分析了本文所提出方法的一些性能。
1 算法描述作者实现基于序列图像三维重建的主要思路如下：(1) 特征提取：在序列图像中提取出需要重建目标的轮廓；(2) 特征点列重采样：将(1)中检测出的边缘按创建polygonal-chain的方法，形成点列，并对此点列进行重采样，以减少后续阶段中处理的数据量；(3) 基于轮廓的空间点三角化：采用一种简单有效的三角化算法，对(2)中重采样后的点列进行三角化，形成三角面片；(4) 三角面片的可视化：使用OpenGL技术，实现重建目标的三维显示。
本文主要讨论了第(2)与第(3)过程中所采用及改进的算法。
特征点列重采样采用文献[13]所描述的算法，但该算法主要线段去近似的逼进曲线，在允许的误差内简化曲线，而应用于重采样时，数据的压缩比并不理想，本文提出了对该算法的改进方法，使得重采样数据的压缩比得到了明显改善。
经过实验测试比较，在提取序列图像中目标的边缘轮廓过程中，使用传统的Robert算子或Canny算子，能较好地保证分割出来的边缘是单像素点。
否则的话，则可使用细化（Thinning）算法作进一步处理。
当得到单像素点的边缘后，按照创建polygonal-chain的方法，扫描检测出的边缘点，由此而形成点序列，便于重采样算法的操作。
1．1特征点列重采样当进行数学仿真或是图像处理时，处理包含数千个点的曲线是很常见的。
通常情况下没有必要处理所有的点，只处理其中的一部分就可以说明问题。
这里在Douglas-Peucker算法的基础上提出一个快速、平面曲线近似算法：即在一个特定公差的规模上计算曲线形状，围绕曲线选取一定的关键点。
该算法有以下几个优点：(1) 计算速度快。
对于一条n点的曲线，计算时间为O(nlog2n)。
(2) 计算前不需要获得曲线的相关信息。
(3) 压缩比率可以很容易的通过公差参数来调整。
1.1.1Douglas-Peucker算法该算法描述如下：逼进V i到V j的曲线部分，从线段V i V j开始。
如果距离线段V i V j最远的顶点到线段V i V j的距离最大为ε则接受这种逼进，不然就以该顶点为中间点分裂线段V i V j 为两部分并分别递归逼进这两条线段。
定义顶点数组V，DPbasic(Douglas-Peucker基本重采样算法)从V i到V j简化子链，DPbasic算法的过程如下：(1) 找出距离有向线段V i V j最远的顶点V f，把距离记做dist；(2) 如果dist>ε，则(a) 执行DPbasic(V,i,f)，在顶点V f分裂并逐段逼进；(b) 执行DPbasic(V,f,j)，递归逼进；(3) 输出V i V j的线性逼进结果来表示V i V j曲线。
1.1.2改进Douglas-Peucker算法Douglas-Peucker算法有很多有点：易编程实现，结构清晰等。
但是当只有一条线段从曲链中分离出来的时候计算时间变成了O(n2)级的，所以要进行改进来提高效率。
定理1：给定一个凸曲线C和一条直线L，则曲线C上到直线L距离最大的点一定在平行L的曲线C的两条切线上。
V i到V j曲链的路径壳由凸点V m和一组对应的凸壳组成，分别用CH(V i,…,V m)和CH(V m,…,V j)来表示。
对路径壳调用三个操作来完成寻找最远点的任务：Build(V,i,j,PH),通过选取中间点作为标记点计算两个分支的最远点来建立V i到V j的路径壳PH；Split(PH,V,k)，给定V i到V j的曲链构成的路径壳，在V k处分裂曲链并返回包含标记点的分支；FindFarthest(PH,L)，找出路径壳上到给定直线L距离最远的点。
假设曲链是以逆时针方向顺序连接的，给定直线L的方向从左向右，如图1所示。
凸壳P的一条切线只和一个凸点相接触，如果以该点为支点逆时针绕转切线，当切线要脱离凸壳的时候切点就转向了下一个凸点。
这表明有平行于曲线L的切线通过的顶点把整个曲链分成了两部分，一部分的正角在1800内，另一部分拥有负角，为了方便下面把对应边分别称作正边和负边。
通过三步来找到最远凸点：第一，找一个正边和一个负边，该边能把曲链分成两分支且每个部分都含有一个最远点；第二，用二分法来定位每个分支中发生边角变化点；第三，计算比较这些最远点，并确定哪个是真正的最远点。
为了完成第一步，我们先任意选取曲链上一边e作为基边，假设e是正边那么剩下的任务就是找一个负边。
选择边e'把曲链分成两部分，如果e'是负边那么就完成了第一步；如果e'是正边，从e的终点到e'的终点构造一条线段s，如果s仍然是正边就可以忽略在e'之前的凸壳边，因为它们都是正边；如果s是负边，就忽略e'之后的部分。
然后在选一个新的e'把余下的部分分成两部分，如此循环下去，在寻找到一个负边e'之前最多要进行二分法运算log2n次。
第二步，有了正边e和负边e'就要在它们之间的部分搜寻与正边和负边都相邻的凸出点。
同前面方法类似，先找到一条中间边e''，如果e''是正边则用e''代替e，如果e''是负边则用e''代替e'。
最多计算过log2n条边就可以找到与切线平行直线L的顶点（即，切点）。
第三步最简单，计算并比较这两个距离，经过O(log2n)次操作就可以找到距离直线L 最远的顶点。
1.1.3 试验对比图2寻找负边图1 从直线L到切线的夹角为正角1．2 简单的三角化算法在这一过程中，对重采样后的轮廓点列采用如下简单的三角化算法：（1） 对所有序列图像中重采样后的轮廓点按同一方向扫描，形成新的点序列；（2） 在相邻两帧图像的轮廓点序列中查找出其空间距离最小的两个点；（3） 将（2）中所选择的两点作为三角形的两个顶点；（4） 如图5所示，第三个顶点有两种选择方案，但选择alpha 角较小者作为最优三角形，形成一个三角面片（网格）。
（5） 选择（4后重复（4），直至（2）所处理的两帧图像中所有轮廓点序列均被处理完毕。
（6） 变换相邻的两帧图像，然后重复（2）-（5），如此反复，直至所有序列图像中的轮廓点列均被处理完毕。
如图6中图所示，该三角化算法所产生的三角网格形态都比较理想，三角网格的内角基本都为锐角，这样可改善可视化过程中计算三角网格法向量的运算速度。
2 结束语本文讨论了基于序列图像三维重建中的关键算法，提出了改进的Douglas-Peucker 算法，应用于特征点列的重采样处理中。
实验结果表明，该算法明显的改善了重采样过程中的数据压缩比，从而使用后续处理（如三角化）的数据大大减少，加速了可视化的处理速度。
在重庆第三军医大学所提供的人体切片图像数据集的基础上，作者采用本文所讨论的算法实现了人体外形轮廓的三维重建及可视化，取得很好的效果。
图6右图显示了运用本文提出的算法进行三维重建的可视化结果，作者将本文算法（记为方法A ）与运用文献[9]所提出的算法（记为方法B ），在可视化处理速度及输出三角网格数量方面进行了比较。