（计算机科学与技术专业论文）三维表面建模方法研究与实现.pdf

jf = i 、。 r e s e a r c ha n di m p l e m e n t a t i o no f3 ds u r f a c e r e s c o n s t r u c t i o na l g o r i t hm s p e c i a l i t y ：c o m p u t e rs c i e n c e & t e c h n o l o g y m a s t e rd e g r e ec a n d i d a t e ：h 坠垒堕g 翌选i su p e r v is o r ：a s s o c i a t ep r o f c h e nx u e - g o n g s c h o o lo fi n f o r m a t i o ns c i e n c e e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a np r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 华 日期：业年上月笪日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：盟导师签名皇釜丕二日期韭年工月丛日 摘要 三维表面建模技术是科学计算可视化领域中的热点研究问题，在 地质勘探、医学诊断等方面都有着重要的应用。因此，对三维表面建 模技术的研究，具有重要的学术意义和应用价值。本文在分析了三维 表面建模技术的基础上，主要围绕以下两大问题来展开研究：( 1 ) 基 于轮廓线拼接算法过程中所出现的轮廓线分支、对应和重合度问题； ( 2 ) 基于等值面的面绘制算法过程中所出现的逼近精度问题。 针对问题( 1 ) ，本文研究了移动立方体( m a r h c i n gc u b e ，m c ) 表面建模算法，对m c 算法的基本原理和关键步骤进行了分析，并根 据m c 算法的基本原理提出了移动棱台( m a r c h i n gp r i s m o i d ，m p ) 算法。m p 算法首先对轮廓线进行体数据的构造，然后抽取体数据中 等值面，最终实现物体表面的生成。该算法有效地避开了基于轮廓线 拼接所碰到的轮廓线的对应和分支问题，省去了人工干预的步骤。同 时，m p 算法解决了m c 算法在轮廓线重合度较小时表面建模失败的 问题。为了满足用户的不同应用目的以及对绘制质量和绘制速度的要 求，本文从m p 算法的关键步骤入手，提供了多种表面生成模式供用 户选择。 针对问题( 2 ) ，本文提出了一种分类处理轮廓线的渐近算法。该 算法将基于轮廓线拼接算法引入到基于等值面的面绘制算法中，利用 基于轮廓线拼接算法的优点，在等值轮廓线与原轮廓线之间采用一种 轮廓线“分段对应拼接”方法，使重建出的物体表面与轮廓线达到完 全吻合。同时，该算法在投影轮廓线之间采用基于等值面的面绘制算 法进行表面建模，生成整个物体的表面，取得了较好的效果。 关键词三维表面建模，轮廓线，m c 算法，m p 算法，渐近算法 。- _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ - _ - _ - _ _ _ - _ _ _ - - _ _ - _ _ - _ i _ _ _ _ - _ i _ - _ _ - _ _ _ - _ _ - - i - _ _ _ _ - - - ，一 a b s t r a c t t h et e c h n o l o g yo f3 ds u r f a c er e c o n s t r u c t i o ni sah o tt o p i ci nt h e f i e l do fv i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g i th a sb e e nw i d e l yu s e di n g e o l o g i c a le x p l o r a t i o na n dm e d i c i n ed i a g n o s t i c s s t u d yo n3 ds u r f a c e r e c o n s t r u c t i o nh a si m p o r t a n ts i g n i f i c a n c eo ns c i e n c ea n dw o r t h i n e s si n p r a c t i c a la p p l i c a t i o n a f t e r t h e a n a l y s i s o fs u r f a c er e c o n s t r u c t i o n t e c h n o l o g y ，t h et h e s i si sm a i n l yc e n t e r e do nt h ef o l l o w i n gt w oi s s u e s ： f i r s t l y ，t h ep r o b l e m so fb r a n c h i n g ，c o r r e s p o n d e n c ea n dc o i n c i d e n c e d e g r e ew h i c ha r ea p p e a r e di nc o n t o u rt i l i n ga l g o r i t h m s e c o n d l y , t h e a p p r o x i m a t i o nd e g r e ep r o b l e mo fc o n t o u ri nt h ep r o c e s so fv o x e lg r a d e m o d e l i n g a i m i n ga t t h ef i r s t p r o b l e m ，t h i sp a p e rs t u d i e st h ea l g o r i t h mo f m a r c h i n gc u b e ( m c ) ，a n dp r e s e n t sam a r c h i n gp r i s m o i d ( m p ) a l g o r i t h m a c c o r d i n gt ot h eb a s i cp r i n c i p l eo fm c 啤i sd i v i d e di n t ot w os t e p s ： f i r s t l y , t h ea l g o r i t h mc o n s t r u c t st h ev o l u m ed a t af r o mc o n t o u r s s e c o n d l y , i no r d e rt o g e n e r a t e t h e o b je c ts u r f a c e ，t h ea l g o r i t h me x t r a c t st h e i s o - s u r f a c ef r o mv o l u m ed a t a m pa v o i d st h ef i r s tp r o b l e me f f e c t i v e l y , a n di tc a nr u na u t o m a t i c a l l yi n s t e a do fa r t i f i c i a li n t e r v e n t i o n t h en e w m e t h o ds o l v e st h ep r o b l e mo fs u r f a c er e c o n s t r u c t i o nf a i l u r ei nm cw h e n t h ec o i n c i d e n c ed e g r e eb e t w e e nt h e e q u i v a l e n tc o n t o u ra n do r i g i n a l c o n t o u ri sl o w m e a n w h i l e ，i no r d e rt om e e td i f f e r e n ta p p l i c a t i o na n dt h e q u a l i t y o fs u r f a c e r e n d e r i n g ，w ep r o v i d em a n yp a t t e r n so fs u r f a c e c o n s t r u c t i o nt os e l e c tf o ru s e rf o r mt h ek e ys t e p so f 咿a l g o r i t h m a i m i n ga t t h es e c o n dp r o b l e m ，a n a p p r o x i m a t i o na l g o r i t h mo f c o n t o u r sc l a s s i f i c a t i o nd i s p o s i n gi s p r o p o s e d t h ea l g o r i t h ma p p l i e st h e c o n t o u r st i l i n ga l g o r i t h mt ot h es u r f a c e r e n d e r i n ga l g o r i t h mo fi s o s u r f a c e t h ea l g o r i t h mt a k e sa d v a n t a g eo fc o n t o u r st i l l i n ga l g o r i t h m ，a n di tu s e sa n e w t i l i n gm e t h o dn a m e l y “s e g m e n t a t i o nc o r r e s p o n d i n gt i l i n g t of i n i s h s u r f a c er e c o n s t r u c t i o nb e t w e e nt h ei s o c o n t o u r sa n dt h eo r i g i n a lc o n t o u r s i nt h i sw a y , t h eo b j e c ts u r f a c ea n dc o n t o u r sa r ea p p r o x i m a t ec o m p l e t e l y m e a n w h i l e ，t h em e t h o dt a k e st h es u r f a c e r e n d e r i n g a l g o r i t h mo f i s o 。s u r f a c et or e c o n s t r u c tt h ew h o l es u r f a c eb e t w e e nt h e p r o j e c t i o n c o n t o u r s ，a n dw eo b t a i nap r e f e r a b l yr e s u l t i i k e yw o r d s3 ds u r f a c er e c o n s t r u c t i o n ，c o n t o u r s ，m ca l g o r i t h m ，m p a l g o r i t h m ，a p p r o x i m a t i o na l g o r i t h m i i i 目录 第一章绪论。1 1 1 研究背景与意义1 1 2 国内外研究现状和水平2 1 2 1 体绘制方法2 1 2 2 面绘制方法3 1 3 主要研究内容5 1 4 论文的组织结构6 第二章三维表面建模技术7 2 1 基于轮廓线拼接的建模方法7 2 1 1 基本原理7 2 1 2 基于轮廓线拼接的主要难题7 2 2 基于体素级的建模方法1 0 2 2 1 体素模型定义1o 2 2 2 等值面定义1 1 2 2 3 等值面构造1 2 2 3m c 算法1 2 2 3 1 确定体素中等值面的剖分方式1 2 2 3 2 等值面与体素边界的交点1 4 2 3 3 等值面的法向计算1 4 2 4 其他建模技术l5 2 5 本章小结1 5 第三章基于m p 的三维表面建模算法16 3 1m p 算法概述16 3 2 基本定义1 6 3 3 数据结构16 3 4m p 算法基本原理。1 9 3 4 1 体数据的构造。2 0 3 4 2 等值面的生成一2 9 3 4 3m p 算法抽取等值面的算法流程3 0 3 5m p 算法的优缺点3 0 i v 3 6 算法分析与实验效果31 3 7 本章小结3 5 第四章分类处理轮廓线的渐近算法3 6 4 1 问题的描述3 6 4 2 几种解决逼近精度方法介绍3 6 4 3 分类处理轮廓线的渐近算法3 7 4 3 1 算法描述3 7 4 3 2 待重建轮廓线的平移3 8 4 3 3 等值轮廓线的跟踪3 9 4 3 4 轮廓线分段对应拼接。4 0 4 4 算法分析与实验效果4 4 4 5 本章小结4 6 第五章模型可视化与三维表面建模系统的实现4 7 5 1 模型可视化的实现4 7 5 2 三维表面建模系统的实现4 8 5 2 1 系统功能模块划分4 9 5 2 2 系统各功能模块的实现4 9 5 3 本章小结5 2 第六章结论与展望5 3 6 1 研究工作总结5 3 6 2 进一步研究内容5 4 参考文献5 5 致谢6 0 攻读学位期间主要的研究成果6 l v 1 1 研究背景与意义 第一章绪论 随着科技和计算机科学的不断发展，计算机技术已融入到社会生活的各个领 域，给人们的生产生活提供了极大的便利。当人们利用计算机对客观事物进行分 析和研究时，常常在海量的数据面前显得不知所措，更难以把握隐藏在数据中的 本质和规律，这时需要建立相应的模型来表示实际的或抽象的现象或对象，以图 形或者图像的形式显示出来，这样就使得原本抽象的、难以理解的原理和规律变 得直观、形象生动和易于理解。三维表面建模技术是科学计算可视化 ( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ) 的重要研究领域。它是指采用计算机图 形学和图像处理技术，将科学计算过程中的数据和结果通过图形或图像在屏幕上 直观显示出来的方法技术【l 】。科学计算可视化主要涉及的领域有：计算机图形学、 计算机辅助设计、图像处理和视觉等。 随着可视化技术和图形处理技术的不断发展，基于面绘制的可视化技术正在 科研和实际生活中发挥着越来越大的作用。在三维图形可视化中，三维表面建模 是它的关键和核心功能之一。三维表面建模技术在现实生活中的医学、地学、几 何建模以及c a d 等领域中广泛地应用起来。通过三维表面建模，可以还原三维 空间模型，达到观察其原本模型的直观效果。 在地质勘测中，寻找石油矿藏是包括我国在内的许多国家的一项长期的战略 性任务。其主要方式是通过地震勘测了解大范围内的地质结构，发现可能的含油 构造，并通过测井数据了解局部区域的地层结构，探明油藏位置及其分布，估计 蕴藏量及勘探价值。但是地震数据以及钻井数据的数据量极其庞大，单纯靠人工 分析、计算以及通过纸上设计已经不能满足实际需求。利用三维表面建模技术可 以从这些海量数据中进行分析和计算构造出地质原貌，并得到矿藏的实际位置和 储量等信息，这样不但能有效地对矿藏开采进行指导，减少无效作业，节约开发 资金，而且必将大大提高矿藏开采效率，具有重大的经济和社会效益。 在医学领域中，尽管人们可以通过核磁共振图像( m 对) 等技术得到人体内 部器官的二维图像序列等信息，但是仅仅通过二维图像序列不能很好的发现和诊 断“病灶 的大小、位置等具体信息。三维表面建模技术可以通过医学体数据或 二维图像构造出器官的三维表面模型。通过三维表面模型，更能有效地指导医生 发现新的病情，并提出更准确、有效的治疗方案。同时，三维表面建模技术在医 学解剖教育和医学研究中也发挥着重要的作用。 1 2 国内外研究现状和水平 三维建模相关研究主要体现在以下两方面：实体建模和表面建模 2 1 。实体建 模主要侧重于三维空间体的表示。实体建模与表面建模相比，有占用存储空间大、 处理速度慢等缺点，但是它非常适合于数据的空间操作与分析。表面建模侧重于 三维空间目标表面的表示，通过对面的表示实现三维空间物体表面的描述。由于 表面建模是基于面来表示的，所以其内部是空的，只是视觉上的三维实体，可以 说是2 5 维的空间实体。表面建模的优点是占用存储空间小、处理速度快，便于 及时显示和更新，对硬件要求不高，但是不能进行空间分析。实现实体建模和表 面建模的方法分别称为体绘制方法( v o l u m er e n d e r i n g ) 和面绘制方法( s u r f a c e r e n d e r i n g ) 。 1 2 1 体绘制方法 体绘制又称为直接体绘制方法。它是指不重建中间图元，直接以体素集合来 表示实体，将原始数据通过光线传输规律方程投射到二维投影平面进行绘制【3 1 。 体绘制认为每一个体素都具有一定的属性，比如透明度、光亮度，然后根据光照 模型和体素介质属性分配一定的不透明度和光强度，并在视线方向上积分计算， 最后将计算得出的半透明图像在屏幕上显示出来，处理过程如图1 1 所示。 图1 1 体绘制方法处理过程 2 体数据的显示方法，从本质上来说都是利用光线投射的理论，可分为两种显 示过程。第一种体绘制方法以空间图像为序。这种方法以像素顺序进行，即处理 完一个像素后接着处理另一个像素。第二种方法是以空间对象为序。这种方法以 体素顺序进行，即处理完当前体素后接着处理下一个体素。此方法需要考虑体素 遍历时的顺序，从后往前和从前往后的结合顺序是有所不同的1 4 j 。 光线投射算法就是一个典型的以空间图像为序的算法【3 】。该算法的基本思想 是：首先屏幕上的每一个像素点发出一条射线，此射线将横穿三维数据场的体素 矩阵，接着在这条射线上进行等距采样，根据采样点最近数据点的不透明度和颜 色值对采样点进行插值，求解出采样点的不透明度和颜色值；然后，根据不同的 图像合成方式，对采样点的不透明度和颜色值进行合成；最后，对光线上的所有 采样点都插值完后，屏幕对应像素点的颜色值和亮度值就已经计算出来了。根据 上述步骤，当屏幕所有的像素点值都计算完时，就得到了整个体数据的完整图像， 如图1 2 所示。 ( a ) 三维视图( b ) 硕视图 图l - 2 体的光线投射 以空间对象为序进行体绘制的方法叫做单元投影算法【4 】。该方法首先需给出 投影方向和投影平面，然后把所有体素依一定的顺序投影到图像平面，并计算出 每个数据点对屏幕像素点的贡献度，得到最终的图像。目前有多种投影算法，如 s p l a t t i n g 算法【6 】和s h e a r - w a r p 算法等【刀。 在实际应用中，特别是在医学图像诊断中，光线投射算法速度较慢。许多学 者提出了各种加速体绘制方法 8 - 9 1 ，能在较短的时间内得到了较好的体绘制图像 质量。因而到目前为止，该算法仍是一种使用较为广泛的体绘制方法【l o 】。 1 2 2 面绘制方法 面绘制是从原始数据中重建中间的几何图元，然后用真实感图形学技术对几 何图元进行绘制。面绘制可分为两种：( 1 ) 基于轮廓线拼接( 切片级) 的面绘制； ( 2 ) 基于等值面( 体素级) 的面绘制。 l 、基于轮廓线拼接( 切片级) 的面绘制 基于轮廓线拼接的面绘制是最早被用来进行面绘制的方法【1 2 1 。k e p p e l 于 1 9 7 5 年提出了最早的轮廓线法思想。该思想采用三角面片来覆盖物体的表面， 并以面片所围成的最大体积作为约束条件，实现物体的表面建模【1 3 】。该方法成 为了三维表面建模算法的基础，随后许多学者对该方法进行了研究和改进 1 4 - 1 5 】。 由于基于轮廓线拼接的面绘制方法约束性不强，导致它们具有很大的随意 性。在轮廓线形态复杂多变，轮廓线位置、方向和形状差异较大的情况下，重建 的效果不理想，虽然许多学者作了大量的研究，但是仍然没有从根本上得到完全 解决。轮廓对应、拼接和分支问题的具体的原理将在本文第二章进行详细的阐述。 2 、基于等值面( 体素级) 的面绘制 基于等值面的面绘制思想是：首先依次对每个体素进行处理，确定出其所包 含的等值面片：然后将所有的体素的面片连接起来形成整个物体表面。所谓等值 面就是指如果把体数据看成是某个空间区域内关于某种物理属性的采样集合，通 过插值来估计非采样点和邻近采样点上的采样值，则该空间区域内所有具有某一 个属性的点集合定义成为一个或多个曲面，称之为等值面。 近年来，基于等值面的面绘制得到了广泛的关注，并取得了许多重要的成 果。h e r m a n 等1 1 6 j 是最早提出立方体方法的等值面绘制方法。它采用边界体素的 六个面来拟合等值面。c l i n e 等【l 刀提出剖分立方体的等值面构造方法。该方法采 用点来构造等值面，但只有在点比较密集时，才呈现“实体模型。l o r e n s o n 等【l8 j 在1 9 8 7 年提出了一种基于体素的典型面绘制算法m c 算法。目前m c 算法已成为最流行的等值面构造算法，它对科学计算可视化产生了巨大的影响。 但是，m c 算法同样还存在着缺陷，主要表现在等值面的拓扑结构错误【1 9 】、绘制 精度不高【2 0 2 1 1 、占用存储空间大和处理速度较慢【2 2 2 3 】等方面。j d u r s t 首先提出 了m c 算法中的二义性问题。为了克服m c 的二义性问题，人们提出了m a r c h i n g t e t r a h e d r a 算法【2 4 1 。由于m c 算法非常具有代表性，因此在科学计算可视化的各 种杂志和会议上，还经常有关于m c 算法的改进算法1 2 5 1 。 基于体素级和基于切片级的建模方法分别适用于不同的原始数据。体素级面 绘制会产生大量的小面片，占用额外空间，给图形的显示和更新带来麻烦。因此， 如何减少冗余的小面片是一个值得研究的课题1 2 6 j 。切片级建模相对于体素级而 言压缩了大量冗余的数据，但是存在轮廓线拼接的多义性问题。在分支问题上， 该问题尤为明显。 由于切片级的面绘制存在着轮廓对应、轮廓拼接、轮廓分支等问题，其中轮 4 廓对应和分支问题是难点问题。现有的轮廓线拼接算法在分支问题上只侧重于解 决一条轮廓线与多条轮廓线间的正确拼接问题，而在实际应用中往往并不是这么 简单，这使得这些算法在轮廓线的拼接上存在着很大缺陷。为此，m w j o n e s 、 张勇等人将此问题转化为体数据中的等值面构造问题【2 7 2 8 】。 除了上述两种主要方法，有些学者还提出了用数学方法来解决表面重建问题 【2 9 j 。这些方法大多以表面上所有点的曲率之和最小为约束条件，用偏微分方法 来表示表面，并求出微分方程的解。这种方法计算量大，并且最后还是要通过体 数据来进行表面显示。 1 3 主要研究内容 针对研究现状，本文主要研究了基于断层数据序列构建三维几何模型的表面 建模方法及其实现。研究和实验中的数据均为危机矿山项目中的数据。 表面建模算法的研究进展很大程度上决定了三维表面建模系统的发展以及 功能的开发，是实现表面重建的关键。研究选择一种最佳的表面建模算法，对表 面建模有着至关重要的作用。本文通过研究现阶段一些主要的表面建模算法，分 析各算法的优缺点，并根据当前项目以及应用需要，选择最适合的表面建模算法。 m c 算法是被证明了的基于等值面面绘制的经典算法之一。为了实现最好的 面绘制效果，本文通过对m c 算法原理和算法流程的研究，从克服该算法的缺陷 以及提高表面绘制质量和速度着手，提出一种新的表面建模算法一m p 算法， 以实现最佳的绘制效果。m p 算法通过对轮廓线进行体数据的构造，并抽取体数 据中等值面，实现物体表面的生成。同时为了满足用户的不同应用目的，以及对 绘制质量和绘制速度的具体要求，本文从m p 算法的关键步骤入手，提供了多种 表面生成模式供用户选择，以最大程度地满足表面建模的需求。 在等值面与轮廓线的逼近精度问题上，本文提出了一种分类处理轮廓线的渐 近算法。该算法将基于轮廓线拼接算法引入到基于等值面的面绘制算法中，利用 基于轮廓线拼接算法的优点，将原轮廓线进行平移，然后在等值轮廓线与原轮廓 线之间采用一种轮廓线“分段对应拼接”方法，使重建出的物体表面与轮廓线达 到完全吻合。同时，该算法在投影轮廓线之间采用基于等值面的面绘制算法进行 表面建模，实现整个物体的表面生成，取得了较好的效果。 基于上述研究，本文最终实现了一个高质量的表面建模子系统。此表面建模 子系统作为危机矿山三维信息评价系统的一部分，主要实现矿山三维断层数据序 列的读取、剖面编辑、体数据的构造、等值面的生成，以及用户对表面模型进行 5 交互操作等功能。 1 4 论文的组织结构 本文共分为六章，分别为绪论、三维表面建模技术、基于m p 的三维建模方 法、分类处理轮廓线的渐近算法、模型可视化与三维表面建模系统的实现、结论 与展望。 第一章是绪论。该章首先介绍了三维表面建模技术的研究背景和重要意义， 然后分析了三维建模技术在国内外的研究现状与水平，最后给出了本课题的研究 内容和文章的组织结构。 第二章研究了三维表面建模技术。该章详细地研究了两类主要的三维表面建 模方法，即基于轮廓线连接的表面建模方法和基于等值面面绘制的表面建模方 法。文章分别研究了它们的方法思路、优缺点和适用情况，其中对m c 算法进行 了重点研究，包括该算法的基本原理和实现步骤。 第三章介绍本文提出的m p 算法。该章根据m c 算法的基本原理，结合当前 项目中的具体应用要求，提出了基于m p 的三维表面建模算法。本章重点介绍了 m p 算法的基本思想及步骤，并对m p 算法进行了算法分析和实验验证。 第四章研究了分类处理轮廓线的渐近算法。该章在当前项目应用背景的基础 上，提出了分类处理轮廓线的渐近算法，主要介绍了该算法的关键步骤，分析了 算法的时间复杂性，最后本章还对分类处理轮廓线的渐近算法进行了实验验证。 第五章首先简要地研究了o p e n g l 实现模型可视化的基本原理，其次介绍了 本文设计的一个表面建模子系统，并用本文算法实现了某矿体的三维空间模型， 最后给出了效果图。 第六章是全文的最后一章，该章首先对自己的工作进行了全面的总结，然后 对自己将来工作的研究和改进进行了讨论。 6 第二章三维表面建模技术 三维表面建模技术有几种比较典型的方法，通常主要可分为两种：( 1 ) 基于 轮廓线拼接的建模方法；( 2 ) 基于体素级的建模方法。除了这两种方法外，还有 一些其他的建模技术【3 0 。3 ，这些方法适用于不同的应用领域。本章首先介绍了基 于轮廓线拼接的建模方法，分析了该方法的主要难题，然后介绍了基于体素级的 建模方法，并着重研究了m c 的表面建模方法，最后还简单介绍了一些其他建模 技术。 2 1 基于轮廓线拼接的建模方法 2 1 1 基本原理 基于轮廓线拼接的建模方法基本原理是首先找出相邻断层剖面上相应的轮 廓线及其对应点，然后用三角片连接起来，最后绘制出这些三角片。该方法可以 看成是对规则的离散采样点进行表面建模的问题。如图2 1 所示，该算法通常可 分解为四个基本问题：( 1 ) 轮廓对应；( 2 ) 轮廓拼接；( 3 ) 轮廓分支；( 4 ) 表面 拟合。 连接 问题 图2 - 1 基于轮廓线拼接的表面重建问题示意图 2 1 2 基于轮廓线拼接的主要难题 1 、轮廓对应问题 轮廓线对应问题发生在相邻层剖面上或其中一个剖面上有多条轮廓线的场 合。在实际应用中，这是经常会碰到情形。要解决该问题，需解决轮廓线之间的 对应关系问题，也就是要确定一个剖面上的哪条轮廓线与另一个剖面的哪条轮廓 线进行连接。该问题在轮廓线错位严重且形状相似度很小的情况下，更加难以解 7 决。现常用的方法有轮廓覆盖法和基于全局的最小生成树法等。 基于轮廓覆盖法的轮廓对应只是一种局部判断准则，该准则通过对相邻剖面 上轮廓线包围盒重叠大小的计算，来进行轮廓线对应关系的判定【3 2 1 。当轮廓线 间的距离较远或形态差异比较大时，该方法不能可靠、准确地判断轮廓线的对应 关系，这时需要综合考虑整个轮廓线组。 m e y e r s 提出采用外接椭圆近似代表轮廓，用多边形近似表示凹轮廓，由此 建立一个全部轮廓线的无向刚3 3 1 。在无向图中，每条轮廓线用节点来表示，若 两条轮廓线之间是对应的，那么在图中将会有一条对应边。因此，可通过无向图 的最小生成树计算来获得轮廓线之间的对应关系。最小生成树方法考虑了全局信 息，能全面考虑对轮廓线的对应关系，获得了比较准确的结果。 2 、轮廓拼接问题 用三角面片或者多边形构造通过相邻剖面上对应轮廓的表面的过程称为轮 廓拼接瞰】。该问题需要确定轮廓线上点的对应关系，并利用三角面片或多边形 来表示轮廓间的物体表面。常用的拼接方法有：圆环图方法的轮廓拼接和轮廓匹 配方法的轮廓拼接。 假设c l 、c 2 为两个待进行拼接的对应轮廓，其中c 1 、c 2 上的点序列分别为： p l ，p 2 ，p m ，q l , 9 2 ，q 。，其中m 0 ，聆 0 。图2 2 ( a ) 为m = 6 ，n = 7 个顶 点的轮廓。连接同一轮廓上的两个相邻点所得到的边称作轮廓段，而连接不同轮 廓上的两个点所得到的边称作跨段。建立一个图，用结点表示跨段，当两个跨段 有一个公共点时，用弧把这两个跨段所对应的结点连接起来，这样所得到的图称 之为圆环图，如图2 2 ( b ) 。 q 3 ( a ) 轮廓拼接图( b ) 圆环图 图2 - 2 基于圆环图的轮廓拼接 h f u c h s 提出了一个可接受表面的定义形式【3 5 】： 8 n 耽 以 m 如 肌 ( 1 ) 任意一条轮廓段能且仅能存在于一个三角面片中。因此，可以得出结 论：若两轮廓线的轮廓段数分别为m 、刀，那么正确的三维物体表面应该有，蝴 个三角面片组成； ( 2 ) 如果一条跨段为某一个三角面片的左跨段，那么该跨段只能作为另一 个三角面片的右跨段。 对于图2 2 中的圆环图，如果没有任何条件加以约束，圆环图中将存在着很 多通路。如果给圆环图的每条弧赋予一个权值( 其中权值是对弧所表示的三角面 片的某个度量，如跨段长度、面积等) ，那么一个环的费用就可以用该环上的所 有弧的权值之和来表示。寻找一个环在某个度量下的最优解就是要在圆环图中搜 索出某个环，并使它的费用最大或最小。目前，已有的准则有体积最大【1 3 】、表 面积最小【3 6 1 、跨度长度之和最小【3 7 1 或者方向一致【3 引，即轮廓点匹配方向最大程 度地与质心匹配方向一致。 基于轮廓匹配的轮廓拼接方法的基本思想是对预先给定的两条对应轮廓线， 查找其中一条轮廓线上点与另一条轮廓线上点的对应关系。目前，弹性匹配【3 9 】 是解决形变匹配的有效方法之一。b u n - 4 0 】在弹性匹配算法中使用了动态协作模型 模拟弹性模型实现非刚体的匹配。为克服弹性匹配方法存在的计算复杂和内部制 约力不强的缺点，文献【4 l 】提出了一种基于线性弹性模型的形变轮廓匹配方法。 当相邻层的轮廓线具有几何相似性时，苏安等提出一种基于相邻层轮廓线几 何形状匹配的三维重建算法【4 2 】。虽然该算法对一些过渡性很好的轮廓线能取得 较好的重建效果，但是对突变性很大的轮廓线，该算法并不适用。李小勇等【4 3 】 采用模拟退火遗传算法实现表面拼接，提高了传统的全局法轮廓线拼接算法的效 率。 3 、轮廓分支问题 轮廓分支问题产生于一个物体在相邻断层上的轮廓个数不相等的情况。基于 轮廓线拼接的表面建模算法中，分支问题是一个关键性问题。因为仅仅通过分支 的局部信息来确定轮廓线对应关系，往往得不到很好的结果，所以需要通过全局 的拓扑和几何结构来确定对应关系。目前方法主要有两类：( 1 ) 分解或组合轮廓 线的方法；( 2 ) 相邻层间插入中间层轮廓线或插入中轴线的方法。 ( 1 ) 分解或组合轮廓线的方法 这类方法在分解或连接轮廓线的位置选择上非常重要。何小海1 4 4 j n 用数学 形态学中的膨胀算法分解单支轮廓，x u m e i h e 4 5 l 提出了一种根据轮廓凸包周长和 9 轮廓中心位置分解单支轮廓的方法，黄永丽1 4 6 】采用按照周长比率解决分支问题， 李小勇等【4 7 】将d e l a u n a y 三角剖分应用到分支问题上，他们提出的这些方法对于 解决独立分支有很好的效果。另外，还有一些学者【4 8 。5 0 l 也采用此类方法将一条轮 廓线分解为两条轮廓线来解决分支问题。 ( 2 ) 在相邻层间插入中间层轮廓线或插入中轴线的方法 c h r i s t i a n s e n 和s e d e r b e r g t 3 7 j 最早提出构建过渡轮廓来解决一对二分支问题。 他们通过构建过渡轮廓线，在两个分支轮廓线的最小距离点之间添加一个内桥， 然后将分支后的两个封闭区域通过该点合二为一，这样就把问题转化为一对一的 单轮廓线的连接。这类方法一般计算量大。m e y e r s 等【5 1 1 将分支轮廓投影到基础 轮廓上，将其作为基础轮廓线的孔来处理，计算带孔轮廓的中心轴线，并用其来 构造过渡轮廓，这种方法构造的轮廓形状与基础轮廓形状相似。j j e o n g ，k 1 d m 5 2 】 通过使用距离映射插入中间轮廓线来解决分支问题。j o a q u i n t 5 3 】将两层的轮廓线 映射到同一断层平面上，利用提取骨架的方法生成中间层。 另外，b a r e q u e t l 5 4 】提出了一种以动态规划为基础的最优三角剖分策略的方 法。该算法通过其他途径来解决分支问题，避开了传统的分支处理方法。 总之，由于约束性的缺乏，基于轮廓线拼接的建模方法具有很大的随意性。 特别是在轮廓线形态复杂，轮廓线位置错位严重，方向和形状差异较大时，该方 法重建的结果不理想。虽然目前有大量的研究工作【5 5 5 6 1 ，但仍然不能从根本上完 全解决。 2 2 基于体素级的建模方法 2 2 i 体素模型定义 体素的定义分为两种5 7 1 ：一种类似于二维图像中的像素定义，将体素定义 为体数据中的一个采样点；另一种则以相邻的8 个采样点组成为一个体素。本文 采用后一种定义方式。 对某一个区域内的三维空间进行采样，若采样间距为缸，知，z ，且采 样点在x ，y ，z 三个方向上是分布均匀的，那么可以用三维数字矩阵甜( f ，k ) 来 表示体数据【5 7 1 。一个体素由8 个相邻的采样点所定义的立方体区域。8 个采样点 称为体素的顶点。它们的坐标分别为( f ，k ) ，( f + l ，歹，七) ，( f ，j f + 1 ，k ) ， ( f + l ，一，+ 1 ，后) ，( f ，k + 1 ) ，( f + l ，_ ，k + 1 ) ， ( f ，+ 1 ，k + 1 ) ，+ 1 ，+ 1 ，k + 1 ) 。 1 0 a z lp v o ( f ，j + l ，七) ( f ，七) 图2 - 3 体素模型 圪( f + l ，- ，七) 设体素内的任意一待求值点p 6 = ( x ，y ，z ) ，p ，( i = 0 , 1 ，l ，5 ) 为与风点为同 一个平面上的点，它们关系如图2 - 3 所示。仇的值采用该体素的8 个顶点进行三 线性插值来估计。首先将仇物理坐标转化为图像坐标( f 6 ，五，吃) ，其中i 6 = 叫缸， = y a y ，z 6 = z 止。然后根据公式( 2 1 ) 进行计算 u ( p 6 ) = k ( p 4 ) ( f + l i 6 ) + u ( p 5 ) ( 屯一f ) 】 又因为 u ( p 。) = k ( p 。) ( j f + 1 一兀) + 甜( p ，) ( 五一) 】 “( 岛) = l ( p 。) ( 歹+ 1 一五) + “( p ：) ( 丘一) 】 材( p 。) = “( f ( 九) ，_ ( 刀) ，七) ( 七+ l 一心) + 甜( f ( 行) ，( 刀) ，后+ 1 ) ( k 6 一七) 其中 ，、f i 疗= o ，l ； “功2 “1 刀：2 ，3 ； ，、f 歹 刀= o ，3 ； ，( 力_ ) 2t j + 1 刀：l ，2 ； 将式( 2 2 ) 、( 2 3 ) 、( 2 - 4 ) 代入式( 2 1 ) 整理可得 公式( 2 1 ) 公式( 2 2 ) 公式( 2 3 ) 0 = 0 , 1 ，2 ，3 ) 公式( 2 4 ) u ( x ，y ，z ) = a o + 口l x + a 2 y + a 3 z + a 4 x y + a 5 x g + a 6 y z + a 7 x y z 公式( 2 - 5 ) 其中a i ( 扛o ，1 ，l ，7 ) 为常数，它们由体素的8 个顶点值唯一确定。 2 2 2 等值面定义 等值面是三维空间中具有相同值的点的集合，采用公式( 2 6 ) 来表示 ( x ，j ，z ) lu ( x ，y ，z ) = c ) ，c 为常数 公式( 2 6 ) 若当前体素的8 个顶点值均小于或大于常数f 时，那么等值面不经过该体素。 要计算边界体素与等值面的交线， 体素中任意一点值的计算公式( 2 5 ) ， 可设体素中等值面的方程为z = g o ，根据 得到假设的表面方程为 c = ( a o + a 3 z o ) + ( 口1 + 口5 z o ) x + ( a 2 + 口6 z o ) y + ( a 4 + 口7 z o ) x y 公式( 2 7 ) 除体数据的边界处外，两个共面体素之间的交线是它们的公共面与等值面的交 线，因此不存在两体素之间交线不吻合的情况。 2 2 3 等值面构造 等值面的构造是实现基于面绘制方法的表面建模的关键步骤，等值面构造方 法是否合理，直接影响着表面的生成效果。等值面构造方法主要有三种：( 1 ) 立 方体法【1 6 】；( 2 ) 剖分立方体法【1 7 1 ；( 3 ) 移动立方体法【1 蚋。 l o r e n s o n 【1 8 1 等在1 9