（计算机应用技术专业论文）基于断层数据的三维重建理论与技术的研究.pdf

摘要、6 3 5 2 8 4摘要基于断层数据的三维重构是三维数据场可视化技术的主要研究内容，重构物体的三维模型也是分析、仿真的前提，本文以此为背景，对断层数据的三维重建及其相关技术进行研究，主要包括轮廓线间的拼接方法、重构中直接影响模型精度和使用价值的对应、分支、光滑等关键问题的解决。运用面绘制算法重构三维模型时，需用三角形或多边形填充在相邻轮廓线间，形成物体表面。本文以三角形形状最优为目标，提出了按照最小内角最大准则进行d e l a u n a y 三角剖分，当可选三角形的最小内角相等时再运用最短路径法进行轮廓线拼接的算法。使用该方法计算复杂度小，易于实现而且构造出的三角形具有较好的形状，但是当断层的上、下两条轮廓线的中心点相差较远时运用该方法会出现锥体现象，本文通过质点对齐的方法解决该问题，克服了使用最大包围盒法运算量大，实现复杂的缺点。由于每一断层轮廓线个数可能不同、存在轮廓线嵌套等现象，在建立实体的几何表示前应先进行拓扑重构，把每一断层轮廓线分类以确定轮廓线所属实体，保证几何重构的正确性。本文通过引入嵌套矩阵构造断层轮廓线所对应的嵌套树，然后再构造两相邻嵌套树中具有相同深度结点的最小生成树的方法来解决轮廓线的对应问题，并且在最小生成树的构造中以两轮廓环相互覆盖区域的大小作为约束条件。该方法通过引入嵌套矩阵使得嵌套树的构造易于实现，然后把基于覆盖的对应方法和全局轮廓对应方法结合起来，既降低了三维重构时轮廓拓扑关系判断的复杂性，又能够比较准确的确定轮廓对应关系。对同一个实体当相邻断层的轮廓线数目不同时需要解决分支问题，针对多个不重叠的轮廓线而产生的分支问题，一个解决办法是把多分支转化成一组单分支问题，由于相邻断层距离较小，上、下轮廓线应该具有定的相似性，本文提出了按照多轮廓线周长的比率把多分支问题转化为若干个单分支问题进行重构三维实体，试验证明该方法是可行的。由于原始数据稀疏，需要通过一定的方法对填充在相邻轮廓线间的三角形或多边形进行拟和，以达到光滑的效果，本文最后在三角格网上构造b e z i e r 三角曲面，从而不仅使构造出来的格网具有较好形状，又提高了表面的光滑程度。实验表明：通过上述方法解决三维重构中出现的问题不仅减少了运算量，而且提高了重构的精度。关键词：可视化面重建三维模型拓扑结构d e l a u n a y 三角剖分曲面拟和茎苎塑至垒坐! ! ! 竺英文摘要a b s t r a c t3 dr e c o n s t r u c t i o nb a s e do ns l i c e i m a g e sd a t ai sam a i nt o p i co fv i s u a l i z a t i o no f3 dd a t as e t s r e c o n s t r u c t i o no f3 dm o d e li st h ep r e m i s eo fa n a l y s i sa n de m u l a t i o n b a s e do nt h i sb a c k g r o u n d ，t h ep a 口e rm a i n l ys t u d i e s3 dr e c o n s t r u c t i o nf r o mc r o s s s e c t i o nd a t aa n dr e l a t e dt e c h n i q u e s t h em e t h o do ft i l l i n gc o n t o u r s ，a n ds o l v i n gt h ek e yp r o b l e m ss u c ha sc o r r e s p o n d e n c e ，b r a n c h i n g ，s m o o t h n e s st h a td i r e c t l ya f f e c tt h ea c c u r a c ya n da p p l i e dv a l u eo f3 dm o d e la r em a i n l yi n c l u d e d w h i l e3 dm o d e l sa r er e c o n s t r u c t e dw i t hs u r f a c er e n d e r i n g ，t r i a n m e so rp o l y g o n sa r en e e d e dt of i l li nt h ea d j a c e n tc o n t o u r ss oa st of o n t lt h es u r f a c eo ft h eo b j e c t w i t ht h eo p t i m i z e ds h a p eo ft f i a n 出e sa so b j e c t i v e ，am e t h o di sp r e s e n t e dt os o l v et i l l i n gp r o b l e mb a s e do nd e l a u n a yt r i a n g u l a t i o na p p r o a c ha c c o r d i n gt ot h ec r i t e r i o no ft h em a x i m u mo ft h es m a l l e s ti n n e ra n 窟l c s w h i l et w os m a l l e s ti n n e ra n m e so fa v a i l a b l et r i a n 醴e sa r ee q u a l ，t h es h o r t e s tp a t hm e t h o dw h i c hi sa d o p t e d t h ec o m p l e x i t yo ft h ep r e s e n t e dm e t h o di sl o w ；i ti se a s i l yi m p l e m e n t e da n dr e c o n s t r u c t e dt r i a n g u l a rg r i d sa r es h a p e l y b u tt h ec o n ea r i s e sw h i l et h ed i s t a n c eo ft h ec e n t e r so fu p p e rc r o s s s e c t i o n a lc o n t o u ra n dl o wc r o s s s e c t i o n a lc o n t o u ra r ef a rf r o me a c ho t h e r i nt h i sp a p e r ，t h ea b o v e m e n t i o n e dp r o b l e mi ss o l v e db ya l i g n i n gt h ec e n t e rp o i n t so fe v e r yc o n t o u r t h es h o r t c o m i n g so ft h ee n v e l o pb o xm e t h o ds u c ha s 盯e a tc a l c u l a t i o na n dc o m p l e xi m p l e m e n t a t i o na r ea l s oo v e r c o m e s i n c ee v e r yc r o s s - s e c t i o n a lc o n t o u r si sl i k e l yt ob en e s t e da n dh a v ed i f f e r e n tn u m b e r ，i no r d e rt oe n s u r et h ec o r r e c t n e s so fg e o m e t r yr e c o n s t r u c t i o n ，t o p o l o g yr e c o n s t r u c t i o ns h o n l db ec a r r i e do u tf i r s t l yb e f o r es o l i dm o d e l sa r eb u i l t ，n a m e l y ,c r o s s s e c t i o n a lc o n t o u r sa r ee l a s s i f i e dt od e t e r m i n et h e i ro b j e c t i nt h i sp a p e l - , n e s t e dt r e e st h a tc o r r e s p o n dw i t hc o n t o u r si ne v e r yc r o s s - s e c t i o na r eb u i l tt h r o u g i lt h ei n t r o d u c t i o no fn e s t e dm a t r i x t h e nt h em i n i m u ms p a n n i n gt r e eo fn o d e sw i t ht h es a m ed e g r e ei nt h en e s t e dt r e e sw h i c hp r e s e n tc o n t o u r si nt w oa d j a c e n tc r o s s s e c t i o n si sc o n s t r u c t e d w h a ti sm o r e ，w h i l ec o n s t r u c t i n gt h em i n i m u ms p a n n i n gt r e e m u t u a lo v e r l a p p i n ga r e ai su s e da sc o n s t r a i n i n gc o n d i t i o n n em e t h o df a c i l i t a t e st h eb u i l d i n go fn e s t e dt r e e sb yt h ei n t r o d u c t i o no fn e s t e dm a t r i x ，a n dt h e n ，t h ec o r r e s p o n d e n c e sb a s e do no v e r l a p p i n ga n dt h a tb a s e do n 殍o b a la r ec o m b i n e d ，w h i c hn o to n l yr e d u c e st h ec o m p l e x i t yo ft o p o l o g yj u d g m e n tb u ta l s od e t e r m i n e st h ec o r r e s p o n d e n c eo fc o n t o u r sa c c u r a t e l y a sf a ra st h es a m eo b j e c ti sc o n c e r n e d ，b r a n c h i n gp r o b l e mn e e dt ob es o l v e dw h i l et h en u m b e r so fc o n t o u r si na d i a c e n tc r o s s s e c t i o n sa r ed i f f e r e n t o n eo ft h es o l u t i o n st ot h ep r o b l e mr e s u l t i n gf r o mn o n - o v e r l a pm u l t i c o n t o u r si st ot r a n s f o r mm u l t i p l eb r a n c h i n gp r o b l e m si n t oag r o u po fs i n g l eb r a n c h i n go n e s s i n c et h ed i s t a n c eb e t w e e nt h ea d j a c e n tc r o s s - s e c t i o n si sv e r yc l o s e u p p e rc o n t o u r sa n dl o wc o n t o u r sb e a rs o m es i m i l a r i t i e s 嘣sp a p e rp u t sf o i - w a r dam e t h o dt h a tt r a n s f o f f f l sm u l t i p l eb r a n c h i n gp r o b l e m si n t os o m es i n g l eb r a n c h i n go n e sa c c o r d i n gt ot h er a t eo fp e r i m e t e ro fm u l t i p l ec o n t o u r s t h em e t h o dt u r n so u tt ob ef e a s i b l et h r o u g he x p e r i m e n t s b e c a u s eo ft h es p a r s i t yo fo r i g i n a ld a t a ，ac e r t a i nm e t h o dt of i tt r i a n g l e so ri i英文摘要a b s t r a c tp o l y g o n st h a tw i l lf i l li na d j a c e n tc o n t o u r si sn e e d e di no r d e rt or e c o n s t r u c ts m o o t hs u r f a c e f i n a l l y , t h et r i a n g u l a rb e z i e rs u r f a c ei sr e c o n s t r u c t e dt of i tt r i a n g u l a rg r i d ，w h i c hr e c o n s t r u c t ss h a p e l yt r i a n g u l a rg r i d sa n di m p r o v e st h es m o o t h n e s so ft h es u r f a c e e x p e r i m e n t sh a v ed e m o n s t r a t e dt h a tt h ea d o p t i o no ft h ea b o v e m e n t i o n e dm e t h o d st os o i v et h ep r o b l e m so f3 dr e c o n s t r u c t i o nr e d u c e st h ec a l c u l a t i o na n di m p r o v e st h ea c c u r a c yo fr e c o n s t r u c t i o na sw e l l k e yw o r d s ：v i s u a l i z a t i o n ，s u r f a c er e n d e r i n g ，3 dm o d e l ，t o p o l o g i c a ls t r u c t u r e ，d e l a n u a yt r i a n g u l a t i o n ，b e z i e rs u r f a c e ，s u r f a c ef i t t i n gi i i1 绪论1 1 研究背景随着科学技术的进步，来自超级计算机、卫星、宇宙飞船、c t 扫描仪、核磁共振仪以及地质勘探等待处理的数据种类越来越多，数据量越来越大。如何采用各种手段和技术从各种各样的海量数据信息中提取其本质、结构和规律，逐渐形成了近几年迅速发展的若干学科如科学计算可视化、模式识别、计算机视觉等。而科学计算可视化指运用计算机图形学和图像处理技术，将科学计算过程中的计算结果数据转换为图形及图像在屏幕上显示出来并进行交互处理的理论、方法和技术。它涉及到计算机图形学、图像处理、计算机辅助设计、计算机视觉及人机交互技术等几个领域。人类在利用计算机对客观事物进行分析和研究时，需要建立相应的模型来表示实际的或抽象的现象或对象，这个过程称为建模。模型是客观事物的抽象表示，它描述对象的结构、属性、变化规律及其各个组成部分之间的关系。建模是用计算机进行分析、模拟、设计、检测的首要任务。客观事物存在多方面、多层次的特征，我们在建立模型时不可能都包括进去，需要我们根据具体应用的要求有选择的从某些侧面来刻画对象。人们在处理所获得的各种海量数据时，通常把它们以图形或者图像的形式显示出来，这样使得抽象的、难以理解的原理和规律变的直观，因此三维重建是科学计算可视化、计算机视觉和模式识别等领域研究的主题。通过各种传感器计算机获得的外部世界中物体的各种信息称为采样数据，三维重建的任务就是从获取的采样数据中恢复物体的三维结构，即物体的原型。不同领域中所用的传感器不同，所得的数据种类也不同并且重建的目标也不一样，因此重建的方法也多种多样。在立体视觉中通过摄像机可以获得周围环境的光强信号，重建的含义是从不同角度拍摄的图像重构三维物体【，重建的关键在于解决好图像匹配问题。从激光扫描测距仪获取的是景物的深度信息【2 】【3 】，从距离图像重建三维物体关键在于确定三维点之间的拓扑关系，然后选择适当的数学描述工具如参数曲面、三角面片、多面体等拟和这组点。在医学领域，通过各种医学设备可以得到人体内部的一组断层图像，其灰度代表生物组织的某种物理属性，不同的生物组织或器官具有不同的物理属性，所以在图像中表现为灰度，因此要从图像重构器官或者生物组织的三维结构首先要确定它们的边界，即对原始图像进行分割【4 】【”，然后用三角形或者多边形来拟和生物组织或者器官的表面 6 1 1 7 引。尽管上述方法各有不同，但是都是试图从有限离散采样点中恢复完整连续的物体模型。只有通过重建物体的三维模型，才能够对它们进行定性或者定量的分析，才能够区别离散数据中的绪论各个物体。因此，三维重建在可视化、计算机视觉、模式识别中占有重要的地位，也是模拟仿真和决策系统中必不可少的组成部分。大多数采集数据可以用体数据来描述，体数据可以表示为：f j ，其中x 是h 维空间的采样点，f 为采样值。目前使用最多、最常见的是三维数据场可视化，如有一系列c t 或者m r i 三维图像数据重构出完整的三维形体，从体数据重构三维物体模型的过程称为体视化，是科学计算可视化的核心。要从三维体数据中重构物体的三维模型，首先要对图像进行处理，根据采样数据的分布变化确定物体的边界，然后用适当的数学表示方法来描述物体。目前主要的三维重建算法有两类：面绘制和体绘制 9 j 前者首先由三维空间数据场构造出中间几何图元如曲面、平面等，然后再由传统的计算机图形学技术实现。这种方法构造出的可视化图形不能反映整个原始数据场的全貌及细节，但是可以产生比较清晰的等值面图像，而且可以利用现有的图形硬件实现绘制功能，使图像生成及变换的速度加快，是一类常用的可视化算法。而后者并不构造中间几何图元，直接由三维数据场产生屏幕上的二维图像，这种算法能产生三维数据场的整体图像，具有图像质量高、便于并行处理等优点，但是其计算量很大并且难于利用传统的图形硬件实现绘制，计算时间较长。本文主要对第一种重建方法进行研究。在实际应用中，我们可能常常面对的不是直接的体数据信息，而是一序列的二维轮廓线数据。例如，在医学数据的可视化中，如果c t 或者m r i 图像两层切片之间的距离远远大于图像的分辨率，也就是z 方向的采样十分稀疏，这时需要在每层图像上就感兴趣的区域勾画出轮廓线，并由一序列的二维轮廓线重构出由面模型表示的三维形体。又如，在医学图像的三维数据场可视化中，尽管相邻断层图像之间的距离很小，但是目前的物质分类技术尚不能将共存的多种不同物质加以分类，需要人工干预由医学专家手工勾划出感兴趣的区域，如在医学的治疗系统中，为了保证治疗的准确性和可靠性，先勾画出器官( 血管、神经等)的轮廓线，再由这些轮廓线重建组织表面。极大限度的辅助医学诊断，为拟定最佳手术方案提供可靠的依据，以提高手术质量，减少医疗事故。再如，在地形数据可视化中，输入的数据经常是一序列的二维等高线，由二维等高线重构出具有光照效果的三维地形图像以对实际地形进行仿真，根据实际的需要进行相应的操作模拟。因此基于以上实际应用的需要，对三维重构的研究有着及其重要的实用价值。在建立实体的几何表示前应先进行拓扑重构，把每一断层轮廓线分类以确定轮廓线所属实体，即重构中对应问题的解决。为了避免出现狭长三角形，在保证运算量小，复杂度相同的条件下，进行轮廓线拼接。运用最短对角线法实现轮廓线拼按时，当上、下断面的轮廓线中点相差较远时会产生圆锥面，所以在连接前绪论需要对轮廓线进行定位。目前多数运用求轮廓线最大包围盒【1 0 】，然后通过平移和旋转操作使包围盒对齐来解决锥体现象，该方法运算量大，实现复杂，需要效率更高的算法解决该问题。当同一实体的相邻断面的轮廓线数目不等时要解决分支问题。由于用三角形面片连接轮廓线时得到的是分片光滑的表面，当三角形面片较大时需要进一步对表面光滑进行处理。要重构出逼真的三维模型，必须对以上问题进行研究，针对现有解决方案存在的缺陷进行改进，尽量减小计算的复杂度，提高效率，使得模型的重构易于实现。本文针对断层轮廓线三维重建的相关技术进行研究，主要包括断层轮廓线间的拼接和三维重构中对应、分支问题的解决以及光滑问题的处理。由于v c + + 有较好的界面设计能力、o p e n g l 在三维图形绘制方面有绝对的优势，本文使用v c + + 和o p e n g l 结合对本文所采用的算法的可行性进行验证。1 2 本文的工作本文的研究目标是：针对有一序列断层轮廓线重建三维实体需要解决的问题，研究三维重建的相关技术，最终通过这些问题的解决，以重构出高效的、具有实用价值的三维模型，供后继交互使用。本文的研究内容包括：( 1 ) 对三维重构中的面绘制算法进行研究，针对用三角形进行轮廓线拼接时存在的问题进行分析和研究，提出一种计算复杂度小，易于实现的轮廓线拼接算法。( 2 ) 不同断层轮廓线可能存在个数不同、轮廓线嵌套等现象，针对该问题对三维重建的对应问题进行探讨，研究相邻具有不同嵌套层次的轮廓线的拓扑关系的判断，如何确定轮廓线所属实体。( 3 ) 针对同一实体，当相邻断面的轮廓线数目不等时要解决分支问题，研究通过何种方法把多分支问题转化为若干个单分支问题进行处理。( 4 ) 采用面绘制算法时，虽然攫取的数据越多物体光滑程度就越高，考虑到存储和重构速度，需要采用一个好的插值方法来近似丢失的数据以达到物体平滑的目的，对三维重构的光滑处理问题进行研究。本文的主要成果包括：( 1 ) 在使用面绘制算法构建三维实体模型时，为了使填充在轮廓线问的三角形格网整体上尽量均匀，避免出现狭长三角形，本文按照最小内角最大的准则在相邻轮廓线间构造d e l a u n a y 三角形来拟和物体表面，当可选三角形的最小内角相等时再运用最短路径法f 1 1 】构造三角形，采用该方法不仅具有最短路径法计算复杂度小的优点，而且构造出的三角形形状较好。绪论( 2 ) 采用d e l a u n a v 三角形进行轮廓线拼接时，该方法同使用最短路径法一样在相邻轮廓线的中心距离较远时会出现锥体现象，对该现象的解决大多采用为每一轮廓线定义一个最大包围盒，然后通过平移和放大等操作使各层轮廓线的包围盒中心位置对齐，然后再进行轮廓线的拼接。此方法运算量大，实现复杂。本文运用求出各轮廓线的质点，通过平移和旋转使各轮廓线的质点都与第一层质点对齐的方法，很好的克服了上述方法的缺陷。( 3 ) 针对相邻具有不同嵌套层次的轮廓线，需要确定其拓扑关系以确定轮廓线所属实体。本文通过引入嵌套矩阵构造断层轮廓线所对应的嵌套树，然后再构造代表两相邻断层轮廓环的嵌套树中具有相同深度结点的最小生成树的方法来解决轮廓线的对应问题，著且在最小生成树的构造中以两轮廓线相互覆盖的区域的大小作为约束条件。该方法通过引入嵌套矩阵使得嵌套树的构造易于实现，把基于覆盖的对应方法和基于全局轮廓对应方法结合起来，既降低了三维重构时轮廓拓扑关系判断的复杂性，又能够比较准确的确定轮廓对应关系。( 4 ) 对于同一实体，当相邻断面的轮廓线数目不等时要解决分支问题，对于分支问题的解决方法之一是轮廓线分裂，本文提出了按照多轮廓线的周长的比率把多分支问题转化若干个单分支问题，试验证明该方法解决分支问题是可行的。( 5 ) 用d e l a u n a y 三角剖分来完成轮廓线间的表面重建时，得到的三角形格网是分片光滑的，要想得到整体光滑的曲面，总要通过一定的方法进行平滑处理，本文通过在三角域上定义b e z i e r 曲面，通过对内部控制点加以约束使曲面之间光滑过渡，以达到整体光滑的效果。1 3 本文的组织本文共分为五部分。第二部分首先介绍三维重构、断层图像的重构及其技术，然后对面绘制算法及其研究现状与发展进行介绍，对于单轮廓线的三维重构理论和常用的轮廓线拼接算法进行探讨，然后给出了本文提出的基于d c l a u n a y 三角剖分的轮廓线拼接算法的思想和实现步骤，最后对采用该方法进行轮廓线拼接时出现的锥体现象给予解决。最后给出了本文所采用的数学模型。第三部分对三维重构中的关键问题的解决进行了深入的探讨和研究，首先对三维重构中对应和分支问题的产生进行介绍，然后介绍了对应问题现有的处理技术，接着对本文针对具有不同嵌套层次轮廓线的对应问题的解决方案进行阐述，随后对同实体中所要解决的分支问题进行讨论，给出按照多轮廓线的周长绪论的比率把多分支问题转化若干个单分支问题的思想并给出实验结果进行验证。最后对光滑问题的产生和常用的几种处理方法进行分析，给出本文采用的光滑处理方法，并且对几种光滑处理技术进行比较验证本文采用的方法的优越性，最后给出本章的试验结果。第四部分对三维模型的可视化进行介绍，对真实感三维模型的显示和可视化场景的创建以及交互技术进行介绍，主要阐述了本文所用的开发工具o p e n g l显示重构模型的方法。第五部分总结与展望。总结全文的工作，对下一步的研究给出展望。三丝塑兰塑2 三维面重构本章首先介绍三维重构及断层图像的重构及其技术，然后对面绘制算法及其研究现状与发展进行介绍，对于单轮廓线的三维重构理论和常用的轮廓线拼接算法进行探讨，然后给出了本文提出的基于d e l a u n a y 三角剖分的轮廓线拼接算法的思想和实现步骤，最后对采用该方法进行轮廓线拼按时出现的锥体现象给予解决。最后给出了本文所采用的数学模型。2 1 三维重构三维重构是计算机视觉、模式识别、可视化技术等领域的研究主题。重构的任务就是从提取到的采样数据中恢复物体的三维结构，即物体的原型。断层图像是一种三维规则标量数据场，是一种无损伤的数据采样方式，如在医学领域，由计算机断层扫描( c t ) ，核磁共振成像( m r i ) ，超声( u s ) 等设备产生的连续二维切片，用工业c t 检测机械零件产生的连续二维切片等。由断层数据重构物体的三维模型是一种常用的数据场可视化技术。其研究目标是把试验或者数值计算获得的大量数据转化为人的视觉可以感受的计算机图像。基于断层数据的三维重构属于体数据的三维重建，是数据场可视化的重要研究内容，对于分布在三维空间的体数据来说，有两类不同的可视化算法：面绘制算法和体绘制算法。面绘制算法首先由三维空间数据场构造出中间几何图元曲面、平面等，然后再由传统的计算机图形学技术实现绘制。常见的中间几何图元就是平面片，主要是按照给定阈值从三维体数据中抽取等值面，然后绘制此等值面。该方法只是将原始数据中的部分属性映射成平面或者曲面，所以使用改方法构造出的可视化图形不能反映整个原始数据场的全貌及细节，但是，可以产生比较清晰的等值面图像，而且可以利用现有的图形硬件实现绘制功能，使图像生成及交换的速度加快。而体绘制算法不构造中间几何图元，以体素( v o x e l ) 集合来表达物体，体素是三维正交网格一个单元，适合于医学图像等生成的规则体数据的建模与可视化，与面绘制法相比，以体元表达的物体模型不仅具有物体的外部信息而且也能表达物体的内部信息，所以可以表现物体的外部形状和内部细节。体素模型可以方便的进行模型间的并、交、差等布尔集合运算，体素模型的构建可以用阂值分割法来区分出物体体素和背景体素，而且表面模型也可以通过体素化过程转化为体素模型。所以用该方法能产生三维数据场的整体图像，并且图像质量高、便于并行处理。但是其计算量很大，难于利用传统的图形硬件实现绘制，计算时间较长。三丝垩垩塑2 2 基于断层图像的重构及其技术基于断层数据的三维表面重建的一般过程【1 2 如下：1 ) 数据获取即从图像获取原始数据；2 ) 数据预处理，将基本的原始数据转化为用户需要的数据格式：3 )等值线提取来获得二维等值轮廓线4 ) 表面模型构造，把上层送来的几何图素用传统图形学的方法生成具有真实感的三维图像。5 ) 后继使用，进行图像处理包括图像的平移、旋转、缩放等交互式的操作或输出到用户需要的数据文件。首先对重构过程中的数据预处理和轮廓线的提取给予简单的介绍，表面模型的重构在2 3 节详细论述。2 2 i 断层图像问插值和轮廓形状插值数据预处理阶段往往需要进行断层图像间插值和轮廓形状插值。由于二维轮廓线获取的一种方式是从断层图像中获得，而从断层扫描设备输出的是一系列平行的二维断层图像，这些二维断层图像间的间距一般远远大于每个断层图像上象素之间的间距，所以需要断层图像插值。一些应用中如医学领域中要重建如血管这样的细小器官，由于相邻断层间同一根血管区域不重和，会直接影响三维重建的正确性，就需要在二维图像之间构造一些新的二维图像，即图像插值【1 3 】，它包括灰度插值和轮廓形状插值。最简单的图像插值方法为线性加权平均法，它只是简单的把两个原始图像的对应象素点加权平均，该方法生成的图像清晰度下降，因为没有进行断层图像之间的匹配并且利用匹配对应关系指导插值。b u n 在研究图像匹配时提出了动态弹性插值的方法 1 4 1 ，由l i n 首先将该思想应用于三维重建【1 5 】【1 6 】，该方法的思想是建立一个作用于起始边界的约束力场，使起始边界在约束力场的作用下发生边界连续变形，逐渐向目标边界逼近。m o s h f e g h i 提出了基于对象的图像匹配方法1 1 4 1 ，图像匹配是一种特殊的灰度插值。管伟光【1 7 1 提出了一种基于简化模型的弹性匹配的断层图像插值方法，该方法克服了加权插值的缺点，但计算量大。m o s h f e g h i又提出一种方向性插值方法i 1 ，该方法不仅用到距离信息、灰度值的相关信息，而且用到树状结构的走向信息，所以限制条件很多，只能处理比较简单的几何结构。有时我们只用到物体的边界，这时只生成中间插值轮廓即可，没有必要产生整幅的插值图像，这种只生成中间轮廓的插值方法称为轮廓插值。h e r m a n 等【1 9 】人提出了形状平均法，该方法利用距离变换和距离图像的加权平均来实现轮廓插值，但该方法在上下轮廓线存在较大差异时会出现错误。为了消除位置差异带来的影响，h i g g i n g s l 2 0 j 先进行位置校准，将两个轮廓位置平移使其质心重合，然后利用h e m a n 的方法进行插值，但该方法不适合于非凸轮廓线。罗斌和郭钧峰f 2 2 】利用数学形态学方法进行形变处理，该方法处理的轮廓线形状比较简单。由于本文是对轮廓线表面重构进行研究，且h i g g i n g s 提出的轮廓插值方法实现比较简单，所以本文在轮廓线稀疏的地方采用该方法进行插值处理，以攫取更多的数据信息。2 2 2 边缘检测和轮廓线提取要重建和分析断层图像中所蕴含的物体的三维结构，必须确定各个物体在图像中所占的区域，因此边缘检测和轮廓线提取也很重要，而轮廓提取是一种图像分割的方法。在c t 、m r i 图像中，不同物质由于其物理属性不同，其灰度值是不同的。目前，轮廓提取主要有三种方法：基于边缘的、基于区域的和利用数学形态学解决区域的分割。前两种轮廓线提取方法是常用的方法，基于边缘检测的分割主要有三种：( 1 )梯度算子法：包括r o b e r t s 算子 2 3 1 ，p r c w i l t 算子【2 4 1 ，s o b e l 算子瞵1 等一次微分算子( 2 ) 拟和算子：对图像作曲面拟和，再使用梯度算子在拟和曲面上做边缘检测，或对拟和曲面求二阶导数的零交叉点，这类算法要求拟和的曲面既要光滑，又要保持原图像的凸凹性，检测的边缘才正确。( 3 ) l o g 算子。m a r r 和h i l d r e t h将高斯滤波和拉普拉斯边缘检测结合在一起，形成l 0 甙l a p l a c i a no fg a u s s i a n )算予。基于边缘检测的分割的主要问题是容易对边缘点产生错误的跟踪，不能保证构成封闭的轮廓线边缘。基于小波变换的边缘检测方法也属于这范畴。基于区域的分割方法以区域为处理对象，考虑区域内部和区域之间的异同性，大体分为两种：区域生长法和分裂合并法。该方法的关键在于定义一个一致性准则，通过判断这个准则来衡量一个区域是否均匀，是否需要分裂，判定两个区域是否一致，是否需要合并。常用的一致性准则是以区域内灰度的均值和方差等统计量来定义的。利用数学形态学解决区域的分割，首先在灰度统计直方图中找出峰谷作为门限，将原始图像分割成若干个区域，然后用膨胀、腐蚀、打开和关闭操作修改分割结果，通过聚类法和形态操作的交替使用，把特定目标分离出来【2 6 1 p 7 1 。提取轮廓线之后，把代表轮廓线的采样点作为输入数据重建面模型。在表面重建之前由于原始的采样点只提供了剖面的离散结点，如果把这些点用直线连接起来作为断层的轮廓线来使用时，会出现不连续的现象。为此需要进一步对轮廓线进行连续性处理，由于b 样条曲线有较好的连续性，所以本文通过引入b 样条曲线来拟和轮廓线以改善其连续性【2 8 】。三维面重构b 样条曲线的方程定义为：p o ) ，孓只汁( f ) ，其中鼻( f 一0 , 1 ，n ) 是控制多箭边形的顶点，。( f ) ( f = 0 ，1 ，n ) 是调和函数，也称为k 阶( k - 1 次) b 样条基函数，其中每一个称为b 样条，它是一个称为节点矢量的非递减的参数t 的序列t ：t 。s t ，s s t 。所决定的k 阶分段多项式，也即为k 阶( k 一1 次) 多项式样条。b 样条曲线不经过控制点，需要根据型值点反求出相应的b 样条曲线的控制顶点1 ，为了保证曲线能首尾相接，并使曲线上结点序号与特征多边形顶点序号相对应，采用封闭周期的三次b 样条曲线。设c f 上有n 个采样点，根据封闭三次b 样条曲线的性质，应有n + 2 个控制点，设q i ( i = 1 , 2 ，m ) 为控制点。其值可由矩阵( 1 ) 求得，其中弓( j - - 1 2 _ n ) 为已知轮廓线的采样点，控制点q 。- a n ，a n 。- o 。由控制点生成的b 样条曲线就是与原轮廓线相拟合的轮廓线。图1 1 为一组轮廓线和用b 样条曲线拟和后的对比图，图( a ) 为用直线直接连接的轮廓线图，( b ) 为用b 样条曲线拟和后的轮廓线图。41141101o14114q 。q 2q 。q 。= 6p 1p !只一，只( a ) 一组用直线连接的轮廓线( b ) b 样条曲线拟和后的轮廓线图图2 1 轮廓线对比图2 3 表面重建由一序列二维轮廓线重建物体的三维表面模型是三维数据场可视化中一种主要的面绘制方法，可以把它看成由一组离散采样数据点重建表面模型问题【1 l 】，三维面重构而这些离散点有规律的分布在各条轮廓线上。2 3 1 表面重构的研究现状与发展表面表示是表示三维物体形状最基本的方法，它可以提供三维物体形状的全面信息，具体形式有两种：边界轮廓线表示和表面曲面表示。最初的表面重建方法采用基于轮廓线的描述方式，即在断层图像中，通过手工或自动方式实现目标轮廓的确定性分割，然后用各层的轮廓线“堆砌”在一起表示感兴趣物体的边界【2 5 】。这种轮廓线表示方法简单、数据量小，但是不很直观。最早的由轮廓重建物体表面的方法是基于多边形技术1 3 ”，主要用平面轮廓的三角形算法，根据在不同切片图像上抽取出的一组轮廓线，用三角片拟合通过这组轮廓线的曲面。该方法属于面向曲面的方法，它通过构造实体表面结合形状来重构实体。b u s s o n n a t ”j 提出了一种基于表面轮廓的d e l a u n a y 三角形方法，解决了系列表面轮廓的三维连通性问题，用三角形或多边形小平面( 或曲面) 在相邻的边界轮廓线间填充形成物体的表面，这种方法所得出的只是分片光滑的表面。l i n 采用从轮廓出发的b 样条插值重建算法【3 3 】，得到了整体光滑的表面。这两种方法属于面向曲面的方法，另一种方法是面向体的重构方法，主要有空间d e l a u n a y 四面体重构，由空间单元重组实体，通过在相邻两断层之间进行三角化然后生成三维情况下的d e l a u n a y 四面体，这种方法可以免去面向曲面重构方法中遇到的约束。l o r e n s e n 等人提出了一种称为“m a r c h i n gc u b e ”的算法f 3 4 j ，这是一种基于体素的表面重建方法，属于等值面技术。它提供了一种精确定义体素及其体素内等值面生成方法，体素被定义为由相邻断层之间8 个网格点组成的数据单元，该方法先确定一个表面阈值，计算每一体素内的梯度值，并与表面阈值进行比较判断，找出那些含有表面的立方体，利用插值的方法求出这些表面。上述方法等值面的生成需要逐个对单元进行检测其是否存在等值面，计算等值面与体素的边的交点，这种算法的效率不高。为此使用八叉树来表示三维实体，这种数据结构的遍历算法和数据的表示都加速了对空间单元的检测和过滤。李清泉、李德仁【3 5 】在线性八叉树编码的基础上，将行程编码技术引入八叉树的数据压缩，形成八叉树的三维行程编码技术，该方法减少了存储空间，提高了运行速度。赵海峰等【3 6 1人通过对八叉树结构和系列断层图像的空间布局的分析，提出了一种通过断层系列图像直接建立八叉树的快速算法。基于表面的方法其主要优点是可以采用比较成熟的计算机图形学方法进行显示( 如裁剪、隐藏面和浓淡计算等，而这些都可以通过o p e n g l 来实现) 。计算量三维面重构小，运行速度快，借助于专用硬件支持，在高性能p c 机上面绘制完全可以实现实时交互显示。2 3 2 表面重建需要解决的主要问题在体视化中，将由一组平面轮廓线重建三维表面的过程称为切片级重建。当原始图像的分辨率很低时，采用切片级重建能构造出比较光滑的物体表面。由轮廓线重建物体表面问题的数学表达为已知层断层平面上的一组闭合曲线 c 。，七= 1 ，2 ， ，其中g = 忙，_ y ) i s ，) ，) = z 。 ，重建表面s o ，y ) 。整个表面重构过程可分为两步：拓扑重构和几何重构，拓扑重构是推导实体的拓扑表示，其目的是对三维断层中每一断层上的轮廓线进行分类，确定各轮廓线所属实体，保证几何重构的正确性，几何重构是用来建立实体的几何表示。表面重建关键是由相邻两层轮廓线重构三维形体的问题，这一问题解决了，由一序列的轮廓线重构三维形体的问题也就不难实现。在进行轮廓线的拼接时遇到的问题表现为轮廓线的拼接问题、对应问题、分支问题以及光滑处理的问题。对应问题，假定给定两个断层，每一断层可能包括任意多个轮廓线，一个断层的轮廓线应和下一断层的哪些轮廓线相对应，即确定轮廓线所属实体。分支问题，假定给定两个断层上，其中的一个断层上的m ( m d ) 条轮廓线对应另一断层上的n ( o ) 条轮廓线，分支问题解决在这种情况下轮廓线间的拼接该如何进行的问题。轮廓线间的拼接问题，该问题是在确定轮廓线之间的对应关系之后如何确定轮廓线上点之间的对应关系，即对应关系确定后用多边形面片拼接表面。光滑处理，虽然攫取的数据越多，重建后物体的光滑程度就越高，然而数据的获得是有限的，无论采用哪种输入方法都会造成一定的信息丢失，所以要采用一定的方法来弥补丢失的数据，从而需要进一步对光滑处理，以得到更逼真的三维形体。以上这些问题都存在弱约束的特点，具有较大的随意性。以下章节对这些问题进行探讨。2 4 单轮廓线的三维重构2 4 1 表面重建理论表面表示是用三角形或多边形小平面在相邻的轮廓线间填充形成物体表面，三角形拼接是使用最为广泛的一种方式，即用一系列相互连接的三角面片将上、三维面重构下两条轮廓线连接起来构造一个可接受表面，从而实现三维面模型的重构。在基于平行轮廓线重建三维表面的研究中，一般只考虑两个相邻断层上的轮廓线重建问题，因为多层轮廓线的重建问题可以简化为多个相邻平行轮廓线重构表面的叠加。假设两相邻平行平面上各有一轮廓线，上、下轮廓线的点列分别为最，只，己一。及q 0 ，q l ，q r 将上述线段依次用直线段连接起来，得到两条轮廓线的多边形近似表示，每一个直线段称为轮廓线段，连接上轮廓线上一点与下轮廓线上一点的线段称为跨距。一条轮廓线段，以及将该线段两端点与相邻轮廓线上的一点相连的两段跨距构成一个三角面片，称为基本三角面片。对于断层轮廓线是单一的凸轮廓线的重构，h f u c h s 对可接受表面的定义如下f 3 1 ：1 ) 每一个轮廓线线段必须在而且只能在一个基本三角面片中出现。如果上、下两条轮廓线各有m 、，1 个轮廓线段，合理的三维表面模型将包含m + n 个基本三角面片。2 ) 如果一个跨距在某一基本三角面中为左跨距，则该跨距是而且仅是另一个基本三角面片的右跨距。3 ) 各面片之间不允许自交。其原理图如图2 2所示。图2 2 表面重建原理图图2 3 表示轮廓线上点列之间连接关系的有向图g设相邻两轮廓线上的逆时针点列分别为最，置，只一。及q 0 ，q 1 ，q 其中m 、n 分别表示轮廓线上采样点的个数。可以用一个优列、l i 行的有向图g 来表示点列及其间的连接关系，如图2 3 所示。其中，顶点y = 帆l i ；o ，1 ，m l ，t