（计算机应用技术专业论文）基于断层轮廓数据的三维形体网格构造方法研究.pdf

浙江大学硕十学位论文 题e l ：基于断层轮廓数据的三维形体网格构造方法研究 摘要 本文主要关注基于轮廓数据的三维物体对象曲面重构问题，轮廓表示着一系列通过 物体对象的断层截面形状。基于轮廓数据的三维物体重构问题有着广泛的应用背景，在 生物医学研究、地质勘探、工业检查、实体建模和快速原型制造等方面是主要的建模手 段。这个问题可以分为四个子问题，即轮廓对应问题、分又问题、拼接问题和曲面拟合 问题。本文主要在对应、分叉和拼接三个基本问题的解决上提出了新方法，并对已有算 法作了重要改进。解决了这三个问题就可以得到基于轮廓数据的三角网格模型，它是原 始轮廓对应的曲面的分片逼近表示。 本文总结了在对应、分叉和拼接三个基本问题上已有的研究成果。研究并改进了一 些轮廓线相关的基础算法，包括平面多边形的方向判别、点在多边形内外位置关系判别、 同平面内两个多边形间的相互位置关系判别、轮廓多边形的特征骨架计算、轮廓线数据 的精简。 轮廓对应问题的解决是基于轮廓数据曲面重构的关键工作，是保证重建网格模型拓 扑关系正确性的基础。由于实际物体的拓扑复杂性，相邻断层轮廓线之问的对应关系有 一对一、一对多、多对多等多种情况。本文全面分析了相邻断层间轮廓对应问题。改进 了两个基本算法，包括相邻两个轮廓对应关系判别算法乖相邻断层问轮廓对应关系的快 速匹配算法。在轮廓对应合法性规则的基础之上提出了四个优化准则，并给出了完整的 建立相邻断层轮廓对应关系的步骤。 骨架线能有效刻画轮廓的特征形状。本文通过引入图象处理技术中提取骨架线的概 念，提出一种基于骨架的拼接方法。这个方法通过插入中间断层，建立轮廓间的一对一 对应关系，可以解决多种分又类型情况下的拼接问题。与先构造复合轮廓再拼接的方法 相比，具有更广的适用性和更令人满意的拼接效果。通常，对末端轮廓都是以平面三角 剖分封闭端面。本文提出的基于骨架的末端封闭方法，可以得到更符合物体自身形状的 三角网格模型。 关键词：逆向工程；断层；轮廓；对应问题；拼接问题；分又问题；多边形；骨架；数 据精简；拓扑重构；三角化；三角网格 塑坚查堂婴主堂垡堡壅 望! ! 茎王堑星丝曼塑塑塑三堡兰竺堕整塑堕查望型! 堑 a b s t r a c t t h i sd i s s e r t a t i o ni sc o n c e m e dw i t ht h ep r o b l e mo fr e c o n s t r u c t i n gt h es u r f a c e so f3 - d o b j e c t sf r o mac o l l e c t i o no fp l a n a rc o n t o u r sr e p r e s e n t i n gc r o s ss e c t i o n st h r o u g h t h eo b j e c t s t h i sp r o b l e mh a si m p o r t a n ta p p l i c a t i o n si nd i v e r s ef i e l d s ，i n c l u d i n gb i o m e d i c a lr e s e a r c h ， g e o l o g y , i n d u s t r i a li n s p e c t i o n ，s o l i dm o d e l i n g ，a n dr a p i dp r o t o t y p i n gm a n u f a c t u r i n g t h e p r o b l e mc a nb ed e c o m p o s e di n t o f o u r s u b - p r o b l e m s ，t h ec o r r e s p o n d e n c ep r o b l e m ，t h e b r a n c h i n gp r o b l e m ，t h et i l i n gp r o b l e ma n dt h es u r f a c ef i t t i n gp r o b l e m t h em a i nw o r k o f t h i s d i s s e r t a t i o ni s d e v e l o p i n g t h en e ws o l u t i o n st ot h et h r e ef i m d a m e n t a l p r o b l e m s o f c o r r e s p o n d e n c e ，b r a n c h i n g ， a n d t i l i n gp r o b l e m s i ns u r f a c e b a s e dr e c o n s t r u c t i o na n d i m p r o v i n g t h e q u a l i t y o fs o m e e x i s t i n ga l g o r i t h m s t h e r e s u l ta f t e rs o l u t i o no ft h e c o r r e s p o n d e n c e ，b r a n c h i n g a n dt i l i n gp r o b l e m si sa t r i a n g u l a rm e s h t h a ti sa p i e c e w i s ep l a n a r a p p r o x i m a t i o n o f as u r f a c ec o n s i s t e n tw i t ht h ec o n t o u r s t h i sd i s s e r t a t i o ng i v e sas u r v e yo f p r e v i o u sr e s e a r c ho n t h ec o r r e s p o n d e n c e ，b r a n c h i n g ， a n d t i l i n gp r o b l e m s t h e n ，s t u d i e s a n d i m p r o v e s s o m eb a s i c a l g o r i t h m s ，i n c l u d i n g d e t e r m i n i n g o r i e n t a t i o no fp l a n a r p o l y g o n , d e t e r m i n i n gp o i n t i n c l u s i o no f p o l y g o n ， d e t e r m i n i n gr e l a t i o n s h i po f l o c a t i o nb e t w e e nc o n t o u r si nt h es a m e p l a n e ，e x t r a c t i n gs k e l e t o n o f c o n t o u r ，r e d u c i n g t h ed a t af o rc o n t o u r s t h es o l u t i o nt ot h ec o r r e s p o n d e n c ep r o b l e mi si m p o r t a n tf o rr e c o n s t r u c t i o no fs u r f a c e f r o mc o n t o u r s ，e s p e c i a l l yf o rv a l i d i t yo ft o p o l o g yo ft h er e c o n s t r u c t e d t r i a n g u l a rm e s h b e c a u s ea na c t u a lo b j e c th a sc o m p l e x t o p o l o g y , i tm a y h a v em a n yc a s e sf o rc o r r e s p o n d e n c e r e l a t i o n s h i po fc o n t o u r sb e t w e e na d j a c e n ts e c t i o n s ，f o re x a m p l eo n e t o o n e ，o n e t o m a n y , m a n y t o - m a n y t h i sd i s s e r t a t i o nm a k e s ac o m p l e t ea n a l y s i so ft h ec o r r e s p o n d e n c ep r o b l e m t h et w ob a s i ca l g o r i t h m sa r ei m p r o v e df o rd e t e r m i n i n gd i r e c tc o r r e s p o n d e n c er e l a t i o n s h i p b e t w e e nt w oc o n t o u r sa n d m a t c h i n g c o n t o u r sb e t w e e n a d j a c e n ts e c t i o n s t h ef o u rc r i t e r i aa n d t h ed e t a i l e ds t e p sf o re s t a b l i s h m e n to fe n t i r ec o r r e s p o n d e n c er e l a t i o n s h i pb e t w e e na d j a c e n t s e c t i o n sa l ep r o p o s e do nt h eb a s eo f t h e e l i g i b i l i t yr u l e s t h es k e l e t o ni sa ne f f e c t i v er e p r e s e n t a t i o no f o b j e c ts h a p e s t h i sd i s s e r t a t i o ni n t r o d u c e s t h ei d e ao fe x t r a c t i n gs k e l e t o ni n d i g i t a li m a g ep r o c e s s i n g ，d e v e l o p s as k e l e t o n b a s e d a p p r o a c hf o rs o l v i n gt h et i l i n gp r o b l e mt h a ti n s e r t si n t e r m e d i a t es e c t i o na n de s t a b l i s h e sa 浙江大学硕士学位论文 题目：基于断层轮廓数据的三维形体网格构造方法研究 o n e - t o - o n e c o r r e s p o n d e n c eo fc o m o u r sb e t w e e ns e c t i o n s t h i sa p p r o a c ha p p l i e s t om a n y t y p e so f b r a n c h e s i th a se x t e n s i v ea p p l i c a b i l i t ya n dp r o d u c e sab e t t e rr e s u l tt h a np r e v i o u s a p p r o a c ho fc o n s t r u c t i n gac o m p o s i t ec o n t o u r g e n e r a l l y , ap l a n a rt r i a n g u l a t i o nm e t h o di s u s e dt oe n c l o s et h eu n m a t c h e dc o n t o u r s ，an e ws k e l e t o n b a s e dm e t h o df o r t i l i n g t h e u n m a t c h e dc o n t o u r si sd e v e l o p e dt h a tw i l lp r o d u c eam o r en a t u r a lp h y s i c a lm o d e l k e yw o r d s ：r e v e r s ee n g i n e e r i n g ；c r o s ss e c t i o n ；c o n t o u r ；s u r f a c er e c o n s t r u c t i o n ； c o r r e s p o n d e n c ep r o b l e m ；t i l i n gp r o b l e m ；b r a n c h i n gp r o b l e m ；p o l y g o n ；s k e l e t o n ；d a t a r e d u c t i o n ；t o p o l o g i c a lr e c o n s t r u c t i o n ；t r i a n g u l a t i o n ；t r i a n g u l a t e dm e s h i i i 浙江大学硕士学位论文 题目：基于断层轮廓数据的三维形体网格构造方法研究 第一章概述 众多学科领域都需要收集和使用物体的表面数据信息，如生物学家使用显微镜观察 并拍照组织的切片，古生物学家把化石切片获取化石的外形图象，地质学家使用地音探 听器获取地质结构的密度信息等。目前在很多领域使用更广泛的是计算机断层扫描 ( c t ) 、超声波、磁共振( m r i ) 、激光等测量方法以获得物体表面数据信息。通常，都期 望从测量的数据重构出物体的表面特征。 随着应用领域的扩大，三维重构的方法也有很多种，例如直接体视化、构造等值面 的曲面重构等。其中基于二维轮廓数据的曲面重构是当前研究的一大方向，轮廓线代表 着一个物体对象表面与一系列切平面的交线，该方法首先获取轮廓线数据，然后再进行 3 d 曲面重构，见图1 1 。本文主要的研究内容是，由二维断层轮廓线数据构造三角网 格的方法。 本章首先分析了基于医学断层数据可视化技术的发展，以及当前逆向工程建模技术 和快速原型制造技术的发展。基于这两大方面的分析阐明了本文的研究意义。然后简要 说明了基于轮廓数据的曲面重构所集中关注的几个问题。最后给出了本文的主要研究内 容。 图1 - 1 基于二维断层轮廓数据的曲面重构 1 1 选题背景及研究意义 本节主要分析了基于医学断层数据可视化技术、逆向工程与快速原型制造技术两大 领域的发展，并给出了本文的研究意义。 1 1 1 基于医学断层数据的可视化技术的发展 从1 9 7 3 年第一台医用c t 机的问世及应用开始 庄天戈9 3 ，由此发展起来了基于 断层图象的三维重构理论，这些方法都是面向物体模型的底层构造，并以视觉效果可视 一 l一 浙江大学硕士学位论文 第一章概述 化为最终目的，没有考虑物体的形状特征识别和重建。这是科学计算可视化的一大应用 领域，目前绝大多数医学领域的研究属于这种类型 - f 宗彦0 2 。 科学计算可视化是指运用计算机图形学和图象处理技术，将科学计算过程中及计算 结果的数据转换为图形及图象在屏幕上显示出来并进行交互处理的理论、方法和技术。 它的应用领域十分广泛，几乎涉及自然科学及工程技术的一切领域。在医学上，可以由 一系y d - 维图象重构出三维形体，并在计算机上显示出来，在此基础之上可以实现矫形 手术、放射治疗等的计算机模拟及手术规划。 在医学上对c t 图象进行三维重构，再现感兴趣人体部分的形貌，极大限度地辅 助医学诊断，为拟定最佳手术方案提供可靠的依据，以提高手术质量，减少医疗事故。 医学断层扫描数据可视化方法可以分成两类 b a r e 9 6 a | ( 见图1 2 ) ：( 1 ) 直接体视化，直 接体视化的特点是将体素直接映射到图象空间进行显示，这种方法适用于包含不规则特 征的数据，能够显示对象体的内部细节。( 2 ) 基于曲面重构的可视化，基于曲面重构的 可视化首先将断层扫描数据分层转化成图形数据，即多边形网格，然后采用传统的曲面 渲染方法进行显示。从绘制方法上也相应的分为体绘制和面绘制【石教英9 6 1 。 图1 2 医学断层扫描数据可视化的处理过程( 出自李维诗0 1 】 曲面表示是表示三维物体形状最基本的方法，可以获得三维物体形状的全面信息。 从断层图象中通过自动或手动方式应用数字图象处理技术提取轮廓，再由轮廓线重构物 体表面。最早的方法是基于多边形技术 f u c h 7 7 ，根据一组从不同断层提取的轮廓线， 用三角片拟合通过这组轮廓线曲面。b o i s s o n n a t 提出了一种基于表面轮廓的d e l a u n a y 三角化方法 b o i s 8 8 ，解决了系列表面轮廓的三维连通性问题，用三角形或多边形的小 平面( 或曲面) 在相邻的边界轮廓线间填充形成物体的表面，但是这种方法所得出的只是 分片光滑的表面。l i n 采用从轮廓线出发的b 样条插值重建算法 l i n 8 9 ，得到了整体 光滑的表面。l o r e n s e n 等人提出了m a r c h i n gc u b e 算法 l o r e 8 7 ，这是一种基于体素通 过构造等值面技术的表面重建方法。基于曲面的方法主要优点是可以利用现有的图形硬 件实现绘制功能，使图象生成及变换的速度加快。 一2 浙江大学硕士学位论文 第一章概述 基于曲面重构的可视化可以分成三类：( a ) 基于三维体数据的方法。主要是指 m a r c h i n gc u b e 方法 l o r e 8 7 ，m o n t 9 4 ，这种方法不需提取二维轮廓，但三角形数量 比较大，抽取的等值面常常包含着非流形结构。( b ) 基于二维轮廓的方法。首先提取每 层上封闭多边形轮廓，由轮廓线构造曲面。这种方法得到的曲面的顶点、边和面片的数 量较少。( c 1 基于散乱点的方法。目前主要有a l p h a 形方法 b a j a 9 5 b 干f 10 - 集方法 h o p p 9 8 ，基于断层扫描数据的曲面重构中，可利用的信息少于需要的信息，采用散 乱点的处理方法将加大问题的难度。 基于面的三维重构在绘制上属于面绘制，有其存在的缺点。面绘制要构造中间曲面 表示就必须通过分割，但由于目前的分割技术所限，缺少准确有效的方法。通过分割， 许多细节信息被丢失，具体的体光照模型有些分割面被扩大，结果是保真性较差i t 宗 彦0 2 1 ，不能反映整个原始数据场的全貌及细节。体绘制与面绘制不同，并不构造中间 几何图元，而是直接由三维数据场产生屏幕上的二维图象。这是近年来得以迅速发展的 一种三维数据场可视化方法，能产生三维数据场的整体图象，包括每一个细节，并具有 图象质量高、便于并行处理等优点。其重要问题是，计算机量很大，且难以利用传统的 图形硬件实现绘制，因而计算时间较长。体绘制算法有光线投射法和体元投射法等。 1 1 2 逆向工程与快速原型制造技术的发展 2 0 世纪9 0 年代以来，随着激烈的市场竞争，对产品研发的时间和产品的更新换代 速度提出了越来越高的要求，因此必须运用新的设计制造技术来满足市场需求。在产品 设计制造领域广泛采用了逆向工程( r e v e r s ee n g i n e e r i n g ，r e ) 和快速原型制造( r a p i d p r o t o t y p i n gm a n u f a c t u r i n g ，r p m ) 方法来缩短产品研发周期。逆向工程是一种根据原有物 体表面获取的点云数据来生成该物体的计算机模型的技术。其应用领域主要体现在：工 程图纸丢失而需要制造备件时、艺术模型需要c a d 数据时、在开发周期中设计几经变 更导致初始设计数据作废时等常规c a d 工程无法完成或很难完成的场合 w 0 0 0 2 ， v a r a 9 7 】。 快速原型制造技术是2 0 世纪8 0 年代以来迅速发展起来的一种先进制造技术，它运 用材料叠加方法，直接由c a d 模型快速制造出产品和原型。目前快速原型制造技术普 遍采用s t l 数据文件获取模型数据，由于s t l 文件采用三角面片来表达实体模型，其 数据结构较为简单，使用方便。为了提高产品制造的效率和质量及缩短开发周期，方法 之一就是逆向工程与快速原型制造技术的集成，这也是当前的一个研究热点。 近年来基于医学断层图象的三维重构技术与工业上兴起的快速原型制造技术相结 合，根据重构的结果，辅以特殊材料快速制造出病体的替代品，这在外科手术中取得显 著成效。组织工程是在生命科学、材料科学和先进制造技术等学科深入交叉的基础上发 3一 浙江大学硕士学位论文 第一章概述 展起来的- - n 新兴前沿学科，是生物医学工程中一个快速崛起的新方向 胡江0 0 ，毛天球 9 9 ，吴永辉0 0 。利用组织工程学原理制造的器官植入人体后，移植物的几何形状与内部 结构直接影响受体组织与移植物的相互作用。移植物的几何形状甚至会影响其周边免疫 细胞、免疫因子的活性以及植入人体后患者的舒适度，因此硬组织器官替代物和体外构 建软组织和器官应用的三维骨架需要很好地反映正常人体器官的几何形状，即需要在人 体器官几何原型的基础上进行逆向工程的定 制 v a r a 9 7 1 。 基于医学断层扫描数据的逆向工程c a d 建模主要是在可视化中的基于二维轮廓的 曲面重构方法上发展起来的。医学逆向工程的应用流程如图1 - 3 所示。面向可制造的复 杂实体逆向工程c a d 建模问题的研究，不完全等同于医学图象可视化问题。为了满足 r p 制造的要求，由医学断层扫描数据逆向c a d 建模得到的曲面必须是可定向的封闭 流形曲面。 图1 - 3 医学中的逆向工程的流程 出自李维诗0 1 逆向工程技术作为快速原型制造技术的前端数据处理方法和产品再创新设计的重 要手段，使原来以复制设计制造为主的快速原型制造技术获得了再创新、再设计的能力， 使逆向工程技术与产品数字化设计与制造技术更紧密地结合起来f 李维诗o l ，陈志杨 0 1 ，g a s p 9 9 ，y a n 9 6 ，b e r n 9 9 1 。根据处理对象及采用的测量技术和手段，逆向工程c a d 建模内容可以分为两个方面【柯映林0 1 ：以处理复杂型面为主要特点的表面逆向c a d 建模，和研究整个形体的逆向c a d 建模。通常对于整个形体的逆向c a d 建模都是基 于断层扫描数据。 1 1 3 研究意义 目前的三维重构应用技术主要集中在医学上，另一方面在工业上的应用也越来越广 泛( 如工业检查、实体建模等) ，在逆向工程建模中的应用也是一个新的研究方向。以上 分析了两个领域的应用情况及发展趋势，总的来说，基于断层数据的三维重构技术可以 - - 4 浙江大学硕士学位论文 第一章概述 分为两大类：基于曲面的方法和基于体数据的方法。 本文的研究是基于二维轮廓线的3 d 曲面重构，先由一系列的轮廓线数据构造三角 网格，然后在网格基础上通过曲面拟合方法得到重构曲面。如图1 - 1 所示，是从一系列 轮廓得到的重构曲面的过程。在很多所采集的数据为断层数据的领域都有着广泛的应 用，例如生物材料、m 对、c t 、超声波、共焦显微镜等断层数据以及古文物、地质勘 探、海洋勘探等断层数据。在有些情况下，轮廓所代表的物体对象是抽象的，例如海洋 的等盐度曲面。关于由一个序列的二维轮廓线重构三维形体的问题，这方面的研究 已有近三十年的历史，不时有新的研究成果出现，从简单到复杂，不断深入。 基于二维轮廓数据的三维网格模型构造不仅在可视化方面，而且在逆向工程c a d 建模方面有着重要意义。目前对于断层图象数据的处理，比较通用的方法是基于可视化 研究的体绘制方法、抽取等值面方法等。这些方法可以快速真实地再现客观世界物体地 形状，在医疗领域，特别是病灶成像方面获得了广泛地应用。但是，这些方法应用的重 点是如何将被测物体在屏幕上显示出来，体绘制方法无法提供一个真正意义上的物体的 几何模型，抽取的等值面常常包含着非流形结构。然而，无论在医学或工业应用领域方 面，一个真实的几何模型都有着重要的应用价值。在医学领域中，我们可以依据几何模 型产生用于快速原型制造的s t l 文件，将医疗成像技术与快速成型技术结合起来，在 人工关节置换、整形外科等领域获得了巨大成功。在工业领域中，基于工业c t o c t ) 图象的建模可以为后续的各种分析( 如应力分析、有限元分析) 应用提供基础网格模型。 这些都是体绘制方法、抽取等值面方法无法提供的。 从以上分析可以看出，本文研究的基于断层数据的网格模型重建方法无论在理论上 还是在实际应用方面都有着重要意义。 1 2 基于轮廓的曲面重构的四个基本问题描述 基于三角面片的重构是断层问蓝面重构主要方法之一，对应于平面多边形表示的轮 廓线，所重构的曲面是一系列三角面片的集合，分片逼近真实的曲面。为了得到光滑的 曲面，可以在三角网格的基础上进行曲面拟合。基于轮廓数据曲面重构的目标是，找到 一个最佳的与所给定的轮廓对应的曲面，曲面重构算法应当选择一个与实际对象最 为接近的匹配，要完成这一点，需要给定一些附加约束条件，例如最常用的一个约束条 件f 优化准则) 是使得曲面面积最小。 一个断层截面包含一组轮廓，表示一个平面与一个或多个物体对象的相交集合。一 个断层上的轮廓组可以来自一个物体对象或多个物体对象，一个非凸的物体对象在某个 断层截面上可以有多个轮廓。基于轮廓的三维形体重构过程可以分解为四个子问题：轮 一5 一 浙江大学碰上学位论文第一章概述 廓对应问题、轮廓分叉问题、轮廓拼接问题和曲面拟合问题【m e y e 9 2 】，如图1 4 所示。 把整个问题分解几个子问题有利于模块化开发，可以在不改变其它子问题解决方案的同 时改变某一个子问题的解决方案。有些子问题用计算机自动解决方案实现比较困难，如 果某一步的结果不满意，可以让用户在下一步处理之前进行交互操作。 ( a ) ( 7 。) ( b ) 图1 - 包含四个子问题解决方案的由一组轮廓重构物体曲面【出自m e y e 9 4 ( a ) 输入的轮廓数据；对应问题确定哪些轮廓相互连接；( c ) 分叉问题处理分叉处的特殊情况 ( d 肼接问题完矧耀睛臁间构造三角网格：( e ) 曲面拟合问题完威从轮廓构造撮终的曲面 1 2 1 轮廓对应问题 轮廓对应问题的引发主要有两种情况，一是一个物体对象在某一断层有多于一个的 一6 一 浙江大学硕士学位论文 第一章概述 轮廓表示，二是数据集内有多个物体对象。轮廓对应问题的本质是保证重建物体的拓扑 关系连接的正确性。复杂物体经常出现各种连通形态，通过轮廓对应问题可以恰当 地重建具有各种连通形态的三角网格模型。 轮廓对应问题可以表述为：当一个物体对象在整个数据集内的一些断层或所有断层 存在多个轮廓，则必须确定某一断层上的每一个轮廓与相邻断层上每一个轮廓的连接关 系。一个物体对象在某个断层上有多个轮廓，那么它在某个分叉处就有连接关系，在分 叉处的相邻断层上轮廓数量通常发生变化。另一种可能是，两个相邻断层上的轮廓数相 等，但两断层间也会存在分叉情况。如果一个物体对象在相邻断层上的轮廓数不一致， 那么存在分叉情况，见图1 4 ( b ) 所示的例子。 在许多情况下，可以把相邻断层的轮廓投影到同一个平面检查其搭接程度( 覆盖程 度) 来解决对应问题，这种方法简单，容易实现；但是在断层间距过大并且物体对象外 形大尺寸方向与断层平面夹角较大，使得相邻两层之间的轮廓没有搭接，这样就没办法 使用搭接判断方法来解决对应问题。 如图l 一5 所示，相邻两断层各有两条轮廓线，那么图示的三种对应关系都可能存在， 通常情况下最合理的对应关系是( a ) 。只要相邻两层的间距相对较小，就可以避免( b ) ( c ) 所示的情况出现。 曰曰船赘 co)(曲 图1 _ 5 轮廓对应问题 1 - 2 - 2 轮廓分叉问题 大多数拼接方法只适用两个相邻对应轮廓的拼接，如果物体对象存在分叉，就超出 了这个适用条件。在分叉处，一个单支可能分离成多个分支( 一对多) 或者多个分支通过 分离又合并的形式另一组分支( 多对多) 。图1 - 6 给出了轮廓线间五种不同的基本连接方 式 o l i v 9 6 ：末端连接、一对一连接、一对多连接( 不连通的分叉连接) 、连通分叉连接 和多对多连接。 解决分叉问题的有两种基本思路。一是在分叉处修改轮廓使之转化为一对一连接方 式，假设上下相邻两个轮廓断层，上断层只有一个单支轮廓，下断层有多个分支轮廓， 那么可以由多个分支轮廓形成一个复合轮廓或者分解单支轮廓为几个子轮廓使得在两 个断层之间只有一对一的连接关系。使用这种思路的算法必须能够选择确定形成复合轮 7一 浙江大学硕士学位论文 第一章概述 廓还是分解单支轮廓为子轮廓，如果是形成复合轮廓，那还必须定义连接位置；如果分 解单支轮廓，那就必须定义划分位置。要根据分支轮廓的几何关系来确定轮廓修改位置 是相当困难的。二是直接连接方式，如b o i s s o n n a t 提出的d e l a u n a y 三角化方法 b o i s 8 8 。 厂一一、 厂、i 一叫 l ，) l 一 qf ( ) fl i 、一固荫 图1 - & 基本连接方式 ( a ) 末端；c o ) 对一；( c ) 对多；( d ) 连通分叉；( e ) 多对多 1 2 3 轮廓拼接问题 一对平面轮廓多边形的拼接结果是形成一个以轮廓为边界曲线的带状三角面片集 合。每个三角面片连接一个轮廓上的一条边与另一个轮廓上的一个顶点。因为真实物体 对象的曲面不会自交，所以要求拼接的三角形不能有自交的现象出现。图】一4 f d l 给出了 一个拼接问题的解决方案。 如果上下轮廓有相似的外形、大小和定位，那么拼接问题很容易解决。但在实际问 题中往往会遇到复杂的轮廓对，因此给出一个可接受的拼接方法也是相当困难的。通常 在拼接问题中要使用优化准则，比如面积最小，体积最大等。拼接问题很大一部分也就 是确定优化准则的问题。在复杂的情况下，优化准则很难有足够的信息来形成一个非常 好的解决方案，例如人类的大脑皮层，用简单的优化准则来完成拼接问题是极端困难的， 要建立一个可接受的解决方案，则要从全局来考虑数据信息。在一个从轮廓构造曲面的 实际应用系统中，用户交互操作是必不可少的。 1 2 4 曲面拟合问题 在完成对应问题、分叉问题和拼接问题后，所得的结果是一个三角网格，是相应轮 廓所对应曲面的分片平面逼近表示。在某些应用中，网格可以作为最终的解决方案结果。 在断层切片间距足够小并且沿轮廓周向采样率足够高的情况下，分片曲面是可以接受 的；否则，要求有曲面拟合作为最终步骤以得到满意的结果。即使采样率足够高，也有 可能是先进行数据压缩并最终使用曲面拟合操作，因为这种方法对结果的简化有显著的 改进。曲面拟合算法的目标就是构造一个光滑曲面，方法是插值或者逼近三维空间的网 格顶点。 一8 浙江大学硕士学位论文 第一章概述 1 3 研究内容及论文组织 本文的研究着重于由轮廓线数据构造三角网格的方法，即包括对轮廓对应问题、分 叉问题和拼接问题的解决。本文的主要工作有： 分析了轮廓线重采样问题和简单轮廓拼接的初始跨距选择问题。系统分析了复 杂关系下的轮廓对应问题。 提出组嵌套轮廓多边形的特征骨架算法。给出了基于骨架的分叉问题和末端 拼接问题的解决方案。 有两点需要特别注意的是，( 1 ) 本文中的方法适用于轮廓数据，轮廓数据可由测量 方法直接获得，例如激光扫描线数据；也可以从其它形式转化而来，例如从切片图象抽 取出的。数字图象处理相对来说是- t 7 较为成熟的学科，发展也很快。( 2 ) 本文所处理 的原始轮廓数据是不充足的，例如在断层最小可用间距的限定下。论文的目标就是 在可利用的数据条件下如何获得较高的曲面重构效果。不充足是指在重构较为困难 的区域所能获得的信息量少，并不是指数据量本身小，实际情况往往是要对原始数据进 行精简。 全文共分六章。具体安排如下： 第一章分析了基于医学断层数据的可视化技术、逆向工程与快速原型制造技术两大 领域的发展概况，并在此基础上分析了研究基于二维轮廓数据的网格模型重建方法的意 义。给出了基于二维轮廓数据的曲面重构的四个基本问题描述。最后给出了本文的主要 研究内容。 第二章介绍了轮廓线相关的基础知识，然后对前阶段专家和学者已有工作作了回顾 和总结，包括基于二维轮廓数据进行三维曲面重构的四个基本问题，轮廓对应问题，分 叉问题，拼接问题和曲面拟合问题。 第三章研究了一些基础算法，包括平面多边形方向的判别、点在多边形内外的位置 关系判别、多边形相互位置关系的判别、轮廓多边形的特征骨架计算以及轮廓线数据的 重采样。 第四章分析了复杂情况下的轮廓对应问题，包括内孔、连通分叉等情况。在对应合 法性规则和优化准则的基础上给出了完整的对应关系建立步骤。 第五章分析了简单相邻轮廓的初始跨距选择方法。提出了利用骨架方法解决轮廓分 叉问题及末端的拼接问题。 第六章是结论，包括实验情况、主要工作成果以及对将来工作的一些建议。 一9 一 浙江大学硕上学位论文 题目：基于断层轮廓数据的三维形体网格构造方法研究 第二章基于断层轮廓数据的曲面重构综述 从1 9 7 5 年k e p p e l 提出了一种由轮廓数据重构曲面的方法开始 k e p p 7 5 ，对基于二 维断层轮廓数据的曲面重构研究已有近三十年的历史。随着应用领域越来越广，不时有 新的研究成果出现。根据轮廓的数量、外形、尺寸以及上下轮廓的相似性、定位情况等 不同，有着多种轮廓对应问题、分叉问题和拼接问题的解决处理方法。 本章首先介绍了一些轮廓数据相关的基础知识，然后回顾和总结了对应问题、分叉 问题和拼接问题的研究发展情况。对曲面拟合问题作了简单介绍，本文不对这个问题进 行深入研究。 2 1 基础知识 从二维断层轮廓数据构造三角网格是曲面重构的关键一步。理论上的轮廓线是一条 连续的曲线，表示一个平面与一个曲面的交线。然而在实际应用中，轮廓线用平面多边 形表示，分段线性逼近所表示的真实轮廓线。本节介绍轮廓线数据的获取方法，以及轮 廓拼接相关的基本概念。 2 1 1 数据采集 断层数据的采集方法可分为破坏性测量和非破坏性测量两种，非破坏性测量主要有 c t 测量法、m r i 测量法、超声波测量法等，破坏性测量主要有层切图象法。随着逆向 工程技术的迅速发展，还有多种数据采集方法可以获得所需的形体数据，从另一角度可 基本上分为接触式、非接触式、逐层扫描三大类，见表2 - 1 。 表2 - 1 数据采集方法 接触式非接触式逐层扫描 机c 光学 吉 电 cm层切 器m三角测距离 结构光 干涉 图象分 波磁 tr 图象 手m量 析 i 法 接触式测量方法测量精度高、适应性强，但测量效率低，而且对一些软质表面无法 进行测量；非接触式测量方法测量效率高，近年来在精度上已显著提高；逐层扫描数据 采集方法可对物体表面和内部结构进行精确测量，所测得的数据点密集、完整，并包含 了所测物体的拓扑结构。目前数字化测量设备的发展趋势是向着高速、高精度、系统化、 集成化、智能化的方向发展。但在医学等领域还广泛采用c t 测量法等；在工业领域， 一1 0 浙江大学硕士学位论文第二章基于断层轮廓数据的曲面重构综述 主要有工业c t 、m r l 和层切图象法。层切图象法是快速原型制造的逆过程，可获得完 整的物体内外形数据，其基本原理是，用数控铣床或磨床，按一定的厚度去掉被测零件 的一层，然后在每层上用光电转换装置( c c d 像机) 摄取断层二维图象，通过对断层图象 的处理与分析，提取每层的内、外轮廓数据，经过处理获取三维整体轮廓的边界数据。 此方法测量数据准确，可以测得内部尺寸，缺点是这是一种不可逆的破坏性测量方法。 工业c t 、核磁共振、超声层析成像等方法实现了对被测物体内部结构的无损测量，即 不破坏实物，就可以直接获取物体的截面数据。 通过上述方法获取的数据可以分为三类。( 1 ) 体数据，例如从c t 或m r i 测得的数 据：( 2 ) 不规则的表面数据，由一些没有拓扑结构的物体表面的坐标点表示；( 3 ) 轮廓线 数据，代表着物体表面与一系列切平面的交线。 2 1 2 数据预处理 本文的研究主题是从二维轮廓线数据构造三角网格，这是曲面重构的重要一步。对 一个物体切片并跟踪它的外形就能得到轮廓数据，也可以从体数据中抽取轮廓数据。例 如，m r i 数据以一系列通过物体的断层切片的形式表示，通过比较切片上体素的值与 所选的代表自己关注的曲面的闽值从每个切片中抽取出一组轮廓。某些情况下可以手工 勾划出所关注对象的轮廓。 通常断层切片是2 5 6 灰度等级的光栅图象，在三维空间是平行的。预处理阶段的目 的是生成一系列表示轮廓的数据点，在每层切片上抽取出轮廓。这样就可以利用每个轮 廓的采样点来对相邻两层切片的的轮廓进行三角化。如图2 1 所示，对切片首先进行二 值化处理，然后分割成单个的轮廓，最后生成采样数据点。利用这些采样数据点进行三 角网格构造。图象处理技术为断层数据的三维重构提供底层支持，所用到的图象处理技 术有图象增强技术、特征提取技术和分割技术。 图2 - t - 断层切片预处理基本步骤 出自p a r k 9 9 】 ( a ) c t 切片；( b ) 二值化处理后；( c ) 按相连区域分割；( d 艉取轮廓；( e ) 采样数据点 在逆向工程建模应用中，对原始测量数据通常进行诸如噪声数据去除、数据平滑、 压缩和归并冗余数据等预处理操作以便后序处理使用。在本文中主要用到的数据是指扫 一 l l 浙江大学硕士学位论文 第二章基于断层轮廓数据的曲面重构综述 描线和多边形点云数据等结构化数据。数据平滑通常采用标准高斯、平均和中值滤波算 法。数据精简是减少激光测量数据中存在的大量冗余数据，采用间距缩减、倍率缩减、 等量缩减、弦高差等方法 金涛0 2 】。 2 1 3 轮廓拼接的基本概念 从以上的描述可知，轮廓线就是用一系列有序的采样数据点表示。所有轮廓平面是 平行的或基本上是平行的。首先将注意力集中在由相邻两层切片的轮廓线重构三维形体 的问题上，这一问题解决了，由一个序列的断层重构三维形体的问题也就不难实现。 如图2 2 所示，每层只有一个轮廓，对相邻 两层轮廓线进行拼接。上轮廓c 的数据点序列为 a ，b ，c ，；下轮廓c 饷数据点序列为a ，b ，c 。 数据点序列按逆时针方向排列，在这里要注意在 拼接前应确保上下轮廓数据点序列排列方向是一 致的，这样才能有效的实施拼接方法。如果将数 据点序列依次用直线连接起来，就得到轮廓线的 多边形近似表示，分段线性逼近真实的轮廓，多 边形的边就称为轮廓线段，例如线段a b b c 等。 图2 - 2 相邻两层对应轮廓的拼接 连接上轮廓线上一点和下轮廓线上一点的线段称为跨距，例如线段b b ，e b 等。一条轮 廓线段以及将该线段两端点与相邻轮廓线上的一点相连的两段跨距就构成了一个基本 三角面片。要实现两轮廓线之间的三维形体重构就首先要用一系列相互连接的三角面片 将两轮廓线连接起来。 要形成相连的、不相交的三角面片集合，需满足两个条件 f u c h 7 7 ：( a ) 每一个轮 廓线线段必须在而且只能在一个基本三角形面片中出现：( b ) 如果一个跨距在某个基本 三角形中为左跨距，则该跨距是而且仅是另一个基本三角面片的右跨距。满足上述条件 的可接受的形体表面可以有多种不同的组合，如何确定一种最佳组合，要采取优化 方法。 2 2 对应问题 最简单的轮廓数据集是每个断层上只有一个轮廓，要构造三角网格模型只需对每相 邻两层进行拼接，所表示的是一个简单的没有分叉的物体对象。一旦某一断层有多个轮 廓，就会出现轮廓对应问题有待解决，即判定相邻两层的轮廓线的拓扑连接关系。 在早期研究阶段，所采集的断层间距较大，如果所研究的又是细长的物体对象，除 了轮廓数据外没有其它数据来判定轮廓的拓扑连接关系和物体对象的数目，因此要给出 一1 2 浙江大学硕士学位论文 第二章基于断层轮廓数据的曲面重构综述 解决对应问题的自动算法是极其困难的或者说是不可能的。例如，有一组通过一根缠结 绳子的切片，在切片间距较大的情况下要跟踪一股线是不可能的。由于问题本身欠约束， 不确定性必然存在。为给出一种自动算法，就需要有一些假设来约束问题，以使可以获 得一个合理的结果。 一个对应问题的难度决定于可用数据的分辨率。最简单的情况是，在给定的相邻断 层间距条件下通过判断搭接与否就能明确轮廓间的对应关系。当前众多的研究 o l i v 9 6 ，g a n a 8 2 ，w a n g 8 6 ，e k o u 9 1 ，l o r e 8 7 ，z y d a 8 7 都是基于这个假设。当可用数 据不充足而难以使用搭接判断方法来获得一个明确的轮廓对应关系时，就要考虑使 用一个全局视角的方法来解决。有两种基本的全局方法：( 1 ) 把轮廓集分组到广义圆柱 体( g e n e r a l i z e dc y l i n d e r s ) l 为，然后找到圆柱体的连接关系；( 2 ) 根据基于轮廓尺寸和外形 参数的函数，来构造一棵树或者一个图以描述相邻层上轮廓的连接关系。 2 2 1 广义圆柱体方法 广义圆柱体是指一个用一条三维空间中的轴向曲线和一个断层截面或扫掠函数表 示的实体。其中，扫掠函数是一个沿轴向曲线的位置函数。如果用最普通的形式，那么 轴是任意曲线，扫掠函数也是任意函数，但是这样的形式通常是没有用的，因此需要在 轴和断层截面函数上