（计算机软件与理论专业论文）物体表面重建方法的研究与实现.pdf

摘要 三维物体表面重建是计算机视觉、模式识别和可视化技术等领域 的研究重点之一。重建物体的三维几何模型也是分析、仿真、决策的 前提。本文主要对断层图象上轮廓线的几何重建及其相关技术进行研 究，该问题可以分成四个子问题：轮廓线对应、廓线拼接、分支处理 和曲面拟合。 首先，为了有效的实现物体表面重建中的轮廓线拼接，本文提出 了基于模拟退火遗传算法实现廓线拼接。该算法以面积、边长和三角 形内角共同形成一个加权函数做为最优目标函数，通过在遗传算法中 融入退火处理操作，提高了种群的多样性，避免了遗传算法中存在 的早熟收敛问题，有效地增强了算法的全局寻优能力。因为交叉操作 在该算法中占用了大部分执行时间，故本文为提高交叉操作效率，提 出一种基于边的最小交叉多边形算法，实验表明该新交叉算法可以极 大的提高算法的交叉效率。算法中还针对问题的特点设计了有针对性 的数据结构，有效地提高了算法的性能。为了处理物体表面重建中的 各种不同情况，本文还实现了添加辅助线方法来实现更加灵活的轮廓 线拼接。 然后，为了处理物体表面重建中的分支情况，本文改进了一种分 支处理算法。该算法根据平面点集d e l a u n a y 三角剖分的特性，将 d e l a u n a y 三角剖分应用到分支问题上。将相邻层轮廓线投影到同一个 剖面上形成一个带约束边的平面点集，并将它们d e l a u n a y 三角化， 根据这些三角形组来生成新的轮廓线，使相邻层的轮廓线一一对应来 完成物体表面重建的分支处理。实验结果表明该算法实现的效果较符 合实际情况，能有效地处理各种不同情况。为能够灵活的处理各种分 支情况，本文还实现了手动分解轮廓线算法。 最后，介绍了三维空间模型的分类和应用以及可视化原理。论文 结合具体项目实现了本文中的算法，在实验和实践中都取得了较为满 意的效果。 关键词三维表面重建，模拟退火遗传算法，轮廓线拼接，分支处理， d e l a u n a y 三角剖分，三维模型 n a b s t r a c t 3 ds u r f a c er e c o n s t r u c t i o ni sa nl m p o r t a n tt o p i ci nt h ea r e a so f c o m p u t e rv i s i o n ，p a t t e r nr e c o g n i t i o na n d3 dd a t av i s u a l i z a t i o n t h e3 d m o d e lo fr e c o n s t r u c t i o ni sa l s ot h ep r e m i s eo fa n a l y s i s ，e m u l a t i o na n d d e c i s i o n m a k i n g t h ep a p e rf o c u s e so n3 ds u r f a c er e c o n s t r u c t i o nf r o m s l i c e i m a g e sd a t a ，t h ep r o b l e mc a nb eb r o k e ni n t of o u rs u b p r o b l e m s ：t h e c o r r e s p o n d e n c ep r o b l e m ，t h et i l i n gp r o b l e m ，t h eb r a n c h i n gp r o b l e m ，a n d t h es u r f a c e f i t t i n gp r o b l e m f i r s t l y , an e ws o l u t i o nt ot h ep r o b l e mo fc o n t o u rt i l i n gi sp r o p o s e di n t h i st h e s i s ，b a s e do ns i m u l a t e da n n e a l i n gg e n e t i ca l g o r i t h m ，w h i c h e f f e c t i v e l yi m p l e m e n t sc o n t o u rt i l i n gi n3 ds u r f a c er e c o n s t r u c t i o n t h i s a l g o r i t h mu s et h ew e i g h t e da v e r a g eo fi n t e r n a la n g l eo ft r i a n g l e s ，a r e aa n d p e r i m e t e ra si t so p t i m i z e do b j e c t i v ef u n c t i o n ，a n db ya d d i n gs i m u l a t e d a n n e a l i n gp r o c e s s t ot r a d i t i o n a lg e n e t i ca l g o r i t h m ，i ti m p r o v e st h e d i v e r s i t yo fp o p u l a t i o n ，a v o i d i n gt h ep r e m a t u r ec o n v e r g e n c ep r o b l e m e x i s t e di ng e n e t i ca l g o r i t h m s ，a n de f f e c t i v e l ye n h a n c i n gt h ea b i l i t yt o s e a r c h i n gf o rt h eg l o b a lo p t i m u m b e c a u s ec r o s so p e r a t i o nc o s t sm o s to f t h et i m ei nt h ea l g o r i t h m ，an e wa p p r o a c ho fi m p r o v i n gt h ee f f i c i e n c yo f t h ec r o s sf u n c t i o ni sd e s c r i b e d ，u s i n gan e wm i n i m u mc r o s s o v e rp o l y g o n a l g o r i t h mb a s e do ne d g e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e w c r o s sa l g o r i t h mr e m a r k a b l yi m p r o v e st h ee f f i c i e n c yo ft h ec r o s sf u n c t i o n s p e c i a ld a t as t r u c t u r e i s d e s i g n e d ，a c c o r d i n gt o t h ec h a r a c t e r i s t i co f c o n t o u r st i l i n gp r o b l e m ，t oi m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h m a n d a l s o ，t od e a lw i t hd i f f e r e n ts i t u a t i o no fc o n t o u rt i l i n g ，am e t h o do ft i l l i n g c o n t o u r st h r o u g ha d d i n ga c c e s s o r i a ll i n em a n u a l l yi si m p l e m e n t e d s e c o n d l y , t od e a lw i t ht h eb r a n c h i n gp r o b l e mi n 3 ds u r f a c e r e c o n s t r u c t i o n ，an e wm e t h o dt h a tc a ne f f e c t i v e l yh a n d l et h eb r a n c h i n g p r o b l e mi sp r o p o s e d t h ea l g o r i t h ma p p l i e sd e l a u n a yt r i a n g u l a t i o nt o b r a n c h i n gp r o b l e ma c c o r d i n gt ot h ec h a r a c t e r i s t i co ft h ed e l a u n a y t r i a n g u l a t i o no f c o n s t r a i n e de d g ep o i n ts e t si np l a n e t h i sm e t h o dp r o j e c t s t h en e i g h b o r i n gs e c t i o nc o n t o u r s o n t oas a m es e c t i o nw h i c hc r e a t e sa c o n s t r a i n e de d g ep o i n ts e t t h ec o n s t r a i n e de d g ep o i n ts e ti np l a n ei s d e l a u n a yt r i a n g u l a t e d ，t h e nn e wc o n t o u r sa r ec r e a t e da c c o r d i n gt ot h e t r i a n g u l a t i o n a n di t f o r m so n e t o o n er e l a t i o no ft h ec o n t o u r s t h e i i i e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ea l g o r i t h mp e r f o r m sw e l li np r a c t i c e ， a n dc a nd e a lw i t ho fd i f f e r e n ts i t u a t i o n se f f e c t i v e l y am e t h o di s d e s c r i b e d ，w h i c hc a nh a n d l ef l e x i b l yk i n d so fb r a n c h i n gp r o b l e mb y m a n u a l l yd e c o m p o s e c o n t o u r f i n a l l y , t h ec l a s s i f i c a t i o na n da p p l i c a t i o no ft h e3 dm o d e la n dt h e v i s u a l i z a t i o nt h e o r yi n s c i e n t i f i cc o m p u t i n ga r ei n t r o d u c e d t h e a l g o r i t h m s a r e i m p l e m e n t e di np r a c t i c a lp r o je c t ，a n d a t t a i nr a t h e r s a t i s f a c t o r yr e s u l ti ne x p e r i m e n ta n di np r a c t i c e k e yw o r d s3 d o b je c ts u r f a c er e c o n s t r u c t i o n ，s i m u l a t e da n n e a l i n g g a ，c o n t o u r st i l i n g ，b r a n c h i n gp r o b l e m ，d e l a u n a yt r i a n g u l a t i o n ， 3 d m o d e l i v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：幽日期：竺l 年二月生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：翌l 年三月! 日 第一章绪论 随着科技和计算机科学的发展，计算机技术已经深入的渗透到社会生活的各 个领域。近年来，计算机图形学取得了长足发展，在科技，教育、文化和娱乐等 领域有着越来越广泛的应用。同时，来自超级计算机、卫星、宇宙飞船、c t 扫 描仪、核磁共振仪以及地质勘探等待处理的数据种类越来越多，数据量越来越大。 如何采用各种手段和技术从各种各样的海量数据信息中提取其本质、结构和规 律，逐渐形成了近几年迅速发展的科学计算可视化、模式识别、计算机视觉等。 而科学计算可视化( 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 ) t l 】指运用计算机图形学和 图像处理技术，将科学计算过程中的计算结果数据转换为图形及图像在屏幕上显 示出来并进行交互处理的理论、方法和技术。它涉及到计算机图形学、图像处理、 计算机辅助设计、计算机视觉及人机交互技术等几个领域。 人们在利用计算机对客观事物进行分析和研究时，需要建立相应的模型来表 示实际的或抽象的现象或对象，这个过程称为建模。通过处理所获得的各种海量 数据，以图形或者图像的形式显示出来，这样就使得原本抽象的、难以理解的原 理和规律变得直观、形象生动和易于理解。因此，三维重建是科学计算可视化、 计算机视觉和模式识别等领域研究的重要内容。 一般计算机通过各种传感器等多种辅助设备来获取现实世界中物体的各种 信息，这个过程称为数据采样。三维重建的任务就是从获取的采样数据中恢复物 体的三维结构，即物体的原型。在医学和地学等领域1 2 , 3 1 ，用不同的方法来获各 种采样数据，尽管方法各有不同，但是都是试图从有限离散采样点中恢复完整连 续的物体模型。通过重建物体的三维模型，对它们进行定性或者定量的分析，为 我们分析和决策提供有力的帮助。 1 1 研究内容和研究意义 物体三维模型可以分为面元模型( f a c i a lm o d e l ) 和体元模型( v o l u m e t r i cm o d e l ) 两类，对应的三维重建可以分为表面重建方法和体素级重建方法两大类1 2 , 3 1 。本 文研究的物体表面重建算法首先由三维空间数据场构造出中间几何图元( 如曲 面、平面等) ，然后由传统的计算机图形学技术实现画面绘制。最常见的中间几 何图元就是平面片( 一般是三角形) ，从三维数据场抽取等值面( i s o s u r f a c e ) 就属于 这种情况。本文主要研究基于断层数据的连接轮廓线表面重建方法，该方法一般 包括轮廓对应、轮廓线拼接、分支处理等几个问题。 表面重建方法和体素级重建方法相l t , t 2 1 ，其优点是数据结构简单，数据存储 量小，对硬件要求不高，易于掌握，便于修改。而基于断层数据的连接轮廓线表 面重建方法在虚拟物体的三维重建中，可以把三维问题转化成二维问题，而且可 以有效的利用现有的图形硬件实现绘制功能，使图像生成及变换具有较快的速 度。 物体的面元模型( f a c i a lm o d e l ) 在医学，地学等领域有大量的应用。如在医学 中应用先进的可视化技术对c t 、核磁共振和超声波等图像进行处理、构造三维 实体模型以及对其进行剖切显示，有助于医生理解复杂的病人情况和进行辅助医 学诊断和治疗，为拟定最佳手术方案提供可靠的依据，以提高手术质量，减少医 疗事故。再如，在地学可视化中，输入的数据经常是一序列的二维等高线，由二 维等高线重构出具有光照效果的三维地形图像以对实际地形进行仿真，根据实际 的需要进行相应的操作模拟。利用地震学探测技术，从这些“声纳 信号断层重 构出三维物体模型。或者利机械钻孔获取地下矿床样本，从这些离散的钻孔数据 重构出三维物体模型。为地质专家进行地质状况和结构进行分析和研究提供帮 助。 1 2 三维物体表面重建的关键问题及研究现状 三维物体表面重建目前有几种较典型的方法，它们的各有优缺点，适应不同 的应用领域。如基于断层数据的连接轮廓线表面重建法 4 , 5 1 处理序y 0 酗j - 维轮廓 线数据，它是一种规则场数据，该方法适用于医学人体器官和地质体的表面建模， 而m c 方法【6 , 7 , 8 】从三维空间规则数据场中抽取等值面的标准方法，这种方法属于 曲面绘制方法，由于这一原理简单，速度较快，易于实现，目前已经得到了较为 广泛的应用。曲面拟合方法【9 】基于计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i c d e s i g n ，c a g d ) 和数字分析技术，用一组曲面片表示重建物体，它能较好的处理 散乱点的曲面重建，在c a d c a m 等领域有较为广泛的应用。 本文主要对基于断层数据的连接轮廓线表面重建方法进行研究和实现。由一 序n - 维轮廓线重建物体的三维表面形状是三维数据场可视化中一种主要的表 面绘制方法，可以把它看作是由一组离散采样数据点重建表面模型的问题【i o l ， 只是这些离散点有规律地分布在各条轮廓线上。下面简要介绍一下轮廓线重建表 面的相关技术及其研究发展现状。 在体视化中，将从一组平面轮廓重建三维表面的过程称之为基于断层轮廓线 重建物体表面( 或切片级重建) 。当原始图象的分辨率很低时，采用切片级重建方 法能够构造出比较光滑的物体表面。 基于断层数据的连接轮廓线表面重建是一个传统的物体表面重建算法，它的 输入是一组平行的平面，称为切片( 或剖面) ( s e c t i o n ) ，每个切片有一个或多个 轮廓线，故也称切片级重建。算法一般只在两层切片之间进行讨论。通过连接切 片上轮廓线的项点来构造分片的线性曲面，最常用的是三角片。两层切片连接好 以后就在切片间形成了一条三角带，所有的三角带组合起来就构成了一个拟合物 体表面的三角网格。它包括以下几个关键的子问题，它们是轮廓对应，轮廓线拼 接，分支处理。 整个表面重建过程分为两步：拓扑重建和几何表面重建。拓扑重建的目的是 对每一段层上的轮廓线进行分组，确定各轮廓的包含和对应连接关系，保证几何 表面重建的正确性。轮廓线表面重建中的四种基本连接方式所对应的四类基本实 体【1 1 1 ，它们是末端连接，单轮廓线的简单连接，不连通的分支连接和和 连通的分支连接四种情况。 轮廓对应、轮廓拼接和分叉问题更具体的原理和研究现状见论文第二章。这 三个问题都存在弱约束的特点，具有很大的随意性。其中，前者属于拓扑重建， 后两者属于几何表面重建。目前，大多数算法主要是解决不连通分支连接方式的 表面重建问题。 上面所讲述的表面重建方法可以称为连接轮廓线方法，但是其中大多数算法 只能解决三个基本问题中的一个或两个问题，而且多数算法只能解决一对多的轮 廓分支情况。 近年来，有学者提出了另一种轮廓线的表面重建方法1 1 2 1 ，将该问题转化为 体数据中等值面的构造问题，称之为隐函数曲面法。通过距离变换，将断层上的 轮廓线转化为三维规则体数据，然后采用等值面抽取的( m a r c h i n gc u b e sm c ) 算 法【6 7 ，引，重建出物体的表面。 此外，还有一些研究者将表面重建问题转化为数学问题来求解 1 3 , 1 4 】，以重建 表面上所有点的曲率之和最小为约束条件，把重建问题数学描述为偏微分方程的 形式，利用迭代方法计算出微分方程的数值解。最终也要转为体数据，然后在进 行表面显示。 综上所述，现有的表面重建算法各有各的优缺点： ( 1 ) 连接轮廓线方法：由于在轮廓拼接前需要对轮廓线进行多边形逼近，会 丢失轮廓线的细节信息，因此重建表面比较粗糙；对应和分支问题的处理比较量 费时间； ( 2 ) 基于体素的表面重建：这种方法构造出的等值面不能反映整个原始数据 场的全貌及细节，但对感兴趣的等值面可以产生清晰的图像，而且可以利用现有 的图形硬件实现绘制功能，速度较快。 ( 3 ) 隐函数曲面法等数学方法：能保留轮廓和表面的细节信息，避免了轮廓 对应和分叉问题的判断，总体的拓扑关系由局部的拓扑关系来保证，可以处理多 对多的分支问题。缺点是数据量较大。数学方法比较复杂，迭代方法比较费时， 因此不十分常用。 1 3 三维空间信息系统模型 人类现实生活的现实世界本来就是三维或者多维的，因此，我们所需要操纵 的空间数据必须是三维而不是二维的【”】。对于城市规划与管理、地下地质建模、 采矿与石油开发等应用领域，3 dg i s 的研究与应用需求十分强烈【1 5 1 ，3 dg i s 具 有非常重要的意义。3 dg i s 的根本目标是多维时空现象的三维表示。三维空间 数据模型是描述三维空间目标的基础，也是3 dg i s 和3 dg m s 的核心。 三维空间构模方法研究是目前3 dg i s 领域以及3 dg m s 领域研究的热点问 题。过去十来年中，国内外学者围绕三维地理空间构模、三维地质空间构模以及 三维地理空间与三维地质空间集成构模，研究提出了二十余种三维空间数据模 型。根据三维空间模型对地学空间目标的几何特征的描述是以表面描述方式还是 以空间剖分方式，可以分为面元模型( f a c i a lm o d e l ) 和体元模型( v o l u m e t r i cm o d e l ) 两类。基于这两类三维空间模型，形成了3 类三维空间构模方法，即单三维构 4 模( s i n g l e3 dm o d e l i n g ) 、混合三维构模( c o m p o u n d3 dm o d e l i n g ) 和集成三维构模 ( i n t e g r a l3 dm o d e l i n g ) 。 1 4 可视化技术概述和开发现状 科学计算可视化( 简称可视化) 【1 1 ，是计算机图形学的一个重要研究方向，是 图形科学的新领域。科学计算可视化的基本含义是运用计算机图形学或者一般图 形学的原理和方法，将科学与工程计算等产生的大规模数据转换为图形、图象， 以直观的形式表示出来。它涉及计算机图形学、图像处理、计算机视觉、计算机 辅助设计及图形用户界面等多个研究领域，已成为当前计算机图形学研究的重要 方向。近年来，随着计算机应用的普及和科学技术的迅速发展，来自超级计算机、 卫星遥感、c t 、天气预报以及地震勘测等领域的数据量越来越大，因此，科学 计算可视化技术已经成为科学研究中的必不可少的手段。它是科学工作者以及工 程技术人员洞察数据内含信息，确定内在关系与规律的有效方法，使科学家和工 程师以直观形象的方式揭示理解抽象科学数据中包含的客观规律，从而摆脱直接 面对大量无法理解的抽象数据的被动局面。 尽管可视化技术由产生到现在只有一十几年的时间，但软件工作者和工程技 术人员针对不同研究领域的不同用途开发出了许多可视化软件，解决了许多数据 场可视化的问题。可视化软件平台的研究沟通了可视化理论与应用，为科学计算 可视化的应用提供了有力的支持，国外在9 0 年代初己陆续推出了一些较为成功 的可视化软件系统，如a v s ，a p e ，e x p l o r e r , p v 二w a v e ，v o x e l v i e w , d a t av i s u a l i z e r 。 这些软件大多数为工作站版的，一般来说，系统价格比较昂贵。又如g e o c o m ， m i r e o m i n e ，e a r c hv i s i o n ，d 触队m i n e 等等地质矿山三维可视化软件。目前， 针对医学和地学领域的，国内己有很多科研单位开发了自己的体视化软件，我国 自主知识产权的针对地学领域的成熟商业软件还比较少，需要我们去做大量的工 作。 1 5 研究思路和关键问题 物体三维模型重建是可视化研究的一个重要课题，物体表面重建法是物体三 维模型的一种重要方法，本文研究的基于断层数据的连接轮廓线表面重建是一种 重要的物体表面重建方法，它与体素级重建相比具有数据结构简单，速度较快等 优点。基于断层数据的连接轮廓线表面重建方法需要解决轮廓线拼接问题，分 支问题，轮廓对应。本文根据项目和研究的需要，主要解决基于断层数据轮廓线 的物体表面重建中的拼接问题和分支问题。 轮廓线拼接问题【4 5 】就是解决相邻轮廓线之间的三角划分，其结果需要满足 不自交和没有空隙的条件。论文以边长、表面积和最大角的加权值来形成适应值 函数，论文采用模拟退火遗传算法来寻找最优适应值，来实现轮廓线的拼接。本 文采用的轮廓线拼接方法属于全局优化方法【4 5 】，全局优化方法能对轮廓线的整 体信息进行考虑，实现效果较为理想。因此本文在轮廓线拼接算法方面要做以下 二个方面的研究和实现： 1 、引入模拟退火遗传算法来实现轮廓线拼接； 2 、设计具有较好性能的变异、交叉算法和数据结构。 基于断层数据轮廓线的物体表面重建中分支处理【2 ，3 1 用来解决相邻层的轮廓 线条数不一样的情况，如何有效的处理相邻层的一对多，或者多对多情况。目前 国内外已经对这个问题也做了大量的研究，如采用分解或组合轮廓线的方法和在 相邻层间插入中间层轮廓线或插入中轴线。两种方法各有优缺点。本文拟对分解 或组合轮廓线的方法进行研究和实现。根据实践的需要和问题特点，需做以下两 个方面的研究和实现： l 、用人工辅助方法实现分支问题算法； 2 、利用d e l a u n a y 三角网来改进分解轮廓线法的分支问题算法。 根据“危机矿山三维信息评价系统 课题需要，在v c + + 和o p e n g l 开发环 境下，利用本文的算法实现物体表面重建的构模可视化系统。 1 6 论文的组织结构 本文共分为六章，分别为绪论、物体表面重建方法、基于模拟退火遗传算法 的轮廓线拼接、分解轮廓线分支处理改进算法、三维空间模型及项目实现。 第一章为绪论，主要概述了本文的研究内容和研究意义，介绍了物体表面重 建方法在国内外的研究现状和水平，并详细描述了研究思路和关键问题。 6 第二章主要详细地介绍了几类主要的物体表面重建方法包括基于断层数据 的连接轮廓线表面重建方法、体素级重建方法和其它曲面重建技术；并阐述了它 们的方法思路、优缺点和适用情况。 第三章介绍了优化算法的基本概念和特点，并详细的介绍了用模拟退火遗传 算法实现轮廓线拼接算法的各个步骤和关键数据结构，并给给出了算法的性能分 析及效果。本章中也给出了手工添加辅助线算法的实现并给出了效果图。 第四章主要详细地介绍了物体表面重建中的分支处理的基本原理和研究现 状。还介绍了d e l a u n a y 三角网( 具有整体最优性的t i n ) 的基本概念和特性； 给出了引入d e l a u n a y 三角网来改进分解轮廓线法实现分支处理算法，并给出了 详细的算法步骤、分析和效果。人工处理分支问题具有极大的灵活性，作为辅助 手段，本章介绍并实现了人工处理分支问题的原理和实现。 第五章先介绍了三维空间模型的基本概念和分类。本章对可视化原理也进行 了介绍。简要的介绍了危机矿山项目的相关情况，结合项目实践，介绍了基于剖 面的三维地质体建模步骤，并用本文算法实现了某矿体的三维空间模型，并给出 了效果图。 第六章也是全文的最后一章，对全文所开展的工作进行了总结，并指出了进 一步的研究工作。 7 第二章物体表面重建方法 目前，三维物体表面重建目前有几种较典型的方法，它们的各有优缺点，适 用于不同的应用领域。目前比较常用的有连接轮廓线重建物体表面法、移动立方 i s ( m a r c h i n gc u b e ) 法和曲面拟合法等【2 3 1 。本章将介绍它们的算法原理和研究现 状。 2 1 物体表面重建方法概述 基于三维数据建模就是根据离散数据来构建物体或对象的几何表达，是数据 场可视化的重要研究内容。数据建模的方法分为表面重建和体素重建两大类，其 中表面重建主要是按照给定闭值从三维体数据中抽取等值面，然后利用传统的表 面绘制方法绘制此等值面。表面重建方法主要有：连接轮廓线的表面重建、基于 体素的表面重建、几何变形法和造型法。本章将介绍这几种表面重建方法。 表面重建方法其主要优点是可以采用比较成熟的计算机图形学方法进行显 示( 如裁剪、隐藏面和浓淡计算等，而这些都可以通过o p e n g l 来实现) 。计算量 小，运行速度快，可以在目前使用的普通p c 机上面绘制，完全可以实现实时交 互显示。 2 2 连接轮廓线的表面重建方法 2 2 1 基本原理 由序列二维轮廓线数据连接轮廓来重建物体的三维表面形状是三维数据场 可视化中一种主要的表面绘制方法，可以把它看作是由一组离散采样数据点重建 表面模型的问题，只是这些离散点有规律地分布在各条轮廓线上。下面简要介绍 一下连接轮廓线重建表面的相关技术及其研究发展现状。 由连接轮廓线重建表面问题的数学表达为：已知n 层断层平面上的组闭 合曲线慨，k = 1 , 2 ，n ，其中b k = ! x ，y ) l s ( x ，y ) = z 。 ，重建表面s ( x ，y ) 。整个表面 重建过程分为两步：拓扑重建和几何表面重建。拓扑重建的目的是对每一段层上 8 的轮廓线进行分组，确定各轮廓的包含和对应连接关系，保证几何表面重建的正 确性。图2 1 给出了由轮廓线表面重建中的四种基本连接方式所对应的四类基本 实体【2 ，l l 】。 ( 1 ) 末端连接：在同断层上有一条轮廓线，而在另一断层上没有归类的轮 廓线； ( 2 ) 单轮廓线的简单连接：又称为圆柱体连接，在两个相邻断层上只有两个 简单的封闭曲线； ( 3 ) 不连通的分支连接：在一个断层上有两个或两个以上的独立不嵌套的轮 廓线，在另一断层上只有一条轮廓线； ( 4 ) 连通的分支连接：在一个断层上有两个分离的嵌套的轮廓线，另一断层 上只有一条轮廓线，第一个断层上的两个或两个以上的轮廓线又被分别归类到单 轮廓线的连接。 ( a ) 末端连接 ( a ) 单轮廓线的简单连接 ( c ) 不联通的分支连接 ( d ) 联通的分支连接 图2 - 1 四种基本的连接方式 基于断层数据的连接轮廓线表面重建法是一个传统的物体表面重建算法，它 的输入是一组平行的平面，称为切片( s e c t i o n ) ，每个切片有一个或多个轮廓线， 故也称切片级重建。算法一般只在两层切片之间进行讨论。通过连接切片上轮廓 线的顶点来构造分片的线性曲面，最常用的是三角片。两层切片连接好以后就在 切片间形成了一条三角带，所有的三角带组合起来就构成了一个拟合物体表面的 三角网格。它包括以下三个关键的子问题，它们是轮廓对应，轮廓线拼接，分支 9 处理。 表面重建必须解决三个基本问题：轮廓对应、轮廓拼接和分叉问题。这三个 问题都存在弱约束的特点，具有很大的随意性。其中，前者属于拓扑重建，后两 者属于几何表面重建。目前，大多数算法主要是解决不连通分支连接方式的表面 重建问题。 2 2 2 轮廓对应 确定相邻断层上的轮廓对应关系，它是在轮廓拓扑包含检测的基础上完成 的。由于约束不足，轮廓对应存在很大的任意性。当相邻断层上轮廓之间的错位 很大时，对应问题就变得愈发难以解决。 轮廓的包含关系就是确定哪些轮廓为孔轮廓，哪些轮廓为外表面轮廓。包含 关系判断方法可以采用传统图形学的方法，即逐一判断某一轮廓线的各边是否在 另一条轮廓包围区域内【1 6 , 1 7 】。 目前主要有两类轮廓对应方法：基于重叠的轮廓对应【i s , 1 9 和全局轮廓对应方 法1 2 0 1 。基于重叠的轮廓对应是一种局部判断准则，以相邻断层上轮廓线包围区 域的重叠大小为判断标准，确定轮廓的对应关系。如果断层距离过大，轮廓错位 比较严重，不能准确、可靠地确定轮廓对应关系，此时需要全局地考虑整个轮廓 组。全局轮廓对应方法以椭圆来近似代表轮廓，以广义柱体生长法来寻找轮廓间 的对应关系，含盖了物体的全局信息，能够比较准确的确定轮廓对应关系。最小 生成树方法【l8 】以外接椭圆来近似代表轮廓( 其中对凹轮廓采用多边形逼近) ，建立 对应于全部轮廓线的无向图，每个节点表示一条轮廓线，每条边表示两条轮廓有 对应关系，通过计算图中的最小生成树，来确定各轮廓对应关系。清华大学的徐 美和【2 ”定义了相邻断层上轮廓的尺寸和位置的关系的判定准则，并以该准则来 确定轮廓线的对应关系。 2 2 3 轮廓线拼接 假设两相邻平行平面上各有一轮廓线，上、下轮廓线的点列分别只，只，只一。 和q o ，g ，q 一将上述点列依次用直线段连接起来，得到两条轮廓线的多边形 近似表示，每一个直线段称为轮廓线段，连接上轮廓线上一点与下轮廓线上一点 的线段称为跨距。一条轮廓线段，以及将该线段两端点与相邻轮廓线上的一点相 1 0 连的两段跨距构成一个三角面片，称为基本三角面片。主要有两种轮廓拼接方法： 基于圆环图的轮廓拼接和基于轮廓匹配的轮廓拼接。 对于断层轮廓线是单一的凸轮廓线的重构，h f u c h s 4 1 对可接受表面的定义如 下： ( 1 ) 每一个轮廓线线段必须在而且只能在一个基本三角面片中出现。如果 上、下两条轮廓线各有m 、1 1 个轮廓线段，合理的三维表面模型将包含m + n 个基 本三角面片； ( 2 ) 如果一个跨距在某一基本三角面中为左跨距，则该跨距是而且仅是另一 个基本三角面片的右跨距； ( 3 ) 各面片之间不允许自交。其原理图如图2 2 所示。 一一 r1r 1r 一 一 u r1r 1r u u y l u 暑；5；弓车二；二；亭# n u n 1 1 1 2 - 2 表面重建原理图图2 3 表示轮廓线上点列链接关系的有向图g 、 设相邻两轮廓线上的逆时针点列分别为只，只，己一。及绕，q l ，q ，其中m 、n 分别表示轮廓线上采样点的个数。可以用一个m 列、n 行的有向图g 来表 示点列及其间的连接关系，如图2 3 所示。顶点y = 舐i f = o ，l ，m 一1 ，j = o ，l , - - , n - l ， 屹对应连线面，弧彳= ( ，圪淞= 七，且七= l + 1 或s = 七+ l 且f = ， ，这样( ，圪) 对 应于一个基本三角片。 实际上，g 是一个有向图，巧是第i 行第j 列的顶点，( ，巧w ) 是垂直弧， ( ，巧川) 是水平弧，任何基本三角面片的集合可以看作是g 的一个子图。如果s 是g 的子图，v 是g 中的顶点，定义： i n d e g r e e 。( 功是s 中进入哟弧数，o u t d e g r e e 。( 功是s 中离开啪弧数。这样，上 述的可接受表面可表述为： 1 ) 对于i ： i = 0 , 1 ，所一1 ，在f ，批1 之间存在一条垂直弧，对应于一轮廓线段币i 。 l l 对于j ： _ ，：0 ，l ，刀一1 ，在，p l 之间存在一条水平弧，对应于一轮廓线段瓦。 2 ) 对于g 中的一个顶点： 要么i n d e g r e e s ( 功= o u t d e g r e e s ( 伊0 或i n d e g r e e s ( v ) o _ r o u t d e g r e e s ( 功 o ，一个可 接受表面对应于上述的一个可接受子图。如图2 4 为一组可接受表面及其在有向 图中的路径示意图。 因而，进行三角面片连接也就是在有向图g 中寻找一条从( o ，0 ) 到( r n 1 ，刀1 ) 的 路径，可接受的表面组合总数等于由开始走到v m n 时可能存在的路径总数， 所以可接受表面的路径数为：彳【豫力】= 号兰n 群。在如此众多的可接受表面 i一! l 玎一l i ! 组合中，如何确定所需要的一种组合? 如果给每条弧赋以不同的权，则最佳的表 面逼近对应一条最优路径。 p0 4 j2 345 1 r 一 1r 1r r 1 r 1 r - - l 一 1r 图2 4 一组可接受表面的实例及其在有向图中的路径 如果每条弧度a 都赋以一个权重吃，一个可接受表面有m + n 条弧度，则当 盯= y 吃。为最优对应的是最佳表明逼近。 百。 最早开始研究轮廓拼接问题的是k e p p e l 2 2 1 ，他把轮廓拼接问题转化为圆环图 的搜索问题，对于圆环图中的每一条弧赋予一个权值，它是对弧所表示的三角片 的一种度量，图中一个坏上每条弧的权值之和为费用( c o s t ) 。搜索在该度量准则 下的费用最小或最大的环，就是在该度量准则下的最优解，对应的三角片组就用 来拼接轮廓。常用的准则有体积最大瞄】、表面积最小5 1 、跨度最小【2 3 1 或者使轮廓 1 2 o l 2 3 4 5 6 点匹配方向最大程度地与质心匹配方向一致【2 4 1 。浙江大学的陈凌钧【2 5 1 、金建荣口6 】 采用模拟退火算法和神经网络算法求解上述二种目标的最优解。但是，对于每个 准则总可以构造出反例，使得重建表面不是我们通常所期待的解，上面的这些目 标函数和优化方法都不能保证在所有情况下都能得到期望解。因此需要根据实际 需要进行必要的调整。 基于轮廓匹配的轮廓拼接方法是对给定的相邻断层上的两个对应的轮廓，对 于其中的一个轮廓上的每一个点，在另一个轮廓上相应地找到一点与其相匹配。 当两个相对应的轮廓在形状、位置和朝问上不同时，需要在匹配中考虑形体自身 的形变问题。目前解决形变匹配的有效方法之一是弹性匹配【2 6 1 ，文献【2 7 】克服了 弹性匹配方法存在的计算复杂或内部相互制约力不强的缺点，提出了一种基于线 性弹性模型的形变轮廓匹配方法。但是这些方法都有各自的局限性，模拟的弹性 模型没有充分发挥弹性模型固有的相互制约和协调作用，而真正的物理模型的求 解又十分复杂。 2 2 4 分支处理 当一个物体在一对相邻切片上的轮廓数目不相同时，就会产生分叉问题。这 时，一般不能通过分叉发生的局部信息确定轮廓对应关系，必须依赖于形体全局 的拓扑和几何结构。常用的分叉处理方法中有中间轮廓构造法和如图2 5 所示的 几种方法。 $ $ 圆圆 图2 - 5 分支的不同情况处理 这个问题的解决方法目前主要有两类：( 1 ) 采用分解或组合轮廓线的方法【2 9 】 【3 0 】，对于这类方法，其分解或连接轮廓线的位置选择非常重要。( 2 ) 在相邻层间 插入中间层轮廓线或插入中轴线1 3 l j 这类方法一般计算量大。 目前国内外学者提出了不同的方式解决这个问题，以满足实际应用的需要。 较典型的主要有，对于分支问题c h r i s t i a n s e n 等【3 0 1 通过构建过渡轮廓线来解决， 在两个分支轮廓线的最小距离点之间添加一个内桥，将分叉后的两个封闭区域通 过该点合二为一，把问题转化为一对一的单轮廓线的连接。c h a n d r a j i tl b a j a j 方 法 2 9 1 是将分支轮廓线的单一轮廓线分解，转换成一一对应问题。m e y e r s 等将 分支轮廓投影到基础轮廓上，将其作为基础轮廓线的孔来处理，计算带孔轮廓的 中心轴线，并用其来构造过渡轮廓，这种方法构造的轮廓形状与基础轮廓形状相 似。 e k o u l e t l 9 】认为相邻断层的两个轮廓的凸包具有很好的相似性，通过将多边形 按凸凹递归地分段，并在相邻层间构造过渡轮廓来处理连通分叉和多分叉的情 况，把单轮廓线与多轮廓线间的连接问题，转换为多个单轮廓线之间的连接问题。 何小海等【3 2 】提出基于数学形态方法的分叉曲面分解。 另外还有如何小海等 3 2 1 提出基于数学形态方法的分叉曲面分解和 b a r e q u e t 3 3 1 【3 4 1 等提出一个基于动态规划算法的最优化三角剖分策略等方法，就避 免了传统的分支处理策略，通过其它的途径来实现物体表面重建。 2 3 体素级重建方法 m c 算法是由w el o r e n s o n 和h e c l i n e 在1 9 8 7 年提出来的【6 。它是从 三维空间规则数据场中抽取等值面的标准方法【1 】。 这种方法属于曲面绘制方法，它构造出的可视化图形虽不能反映整个原始数 据场的全貌及细节，但是可以对感兴趣的等值面产生清晰的图形，而且可以利用 现有的图形硬件实现绘制功能。由于这一原理简单，速度较快，易于实现，目前 己经得到了较为广泛的应用【7 3 5 1 。这种方法要求x ，y ，z 三个方向的数据分辨 率相差不大，经过插值，轮廓线z 轴分辨率接近x ，y 轴的分辨率，m c 算法的 基本原理如下。 2 3 1m c 方法的基本原理 在m c 方法中，假定原始数据是离散的三维空间规则数据场。为了在这一数 1 4 据场中构造等值面，用户应先给出所求等值面的值，设为c o 。m c 方法首先找出 该等值面经过的体元的位置，求出该体元内的等值面并计算出相关参数，以便由 常用的图形软件包或图形硬件提供的面绘制功能绘制出等值面。