（计算数学专业论文）基于rbf的点云数据三维重建技术研究.pdf

论文题目： 专业： 硕士生： 指导教师： 基于i u 强的点云数据三维重建技术研究 计算数学 郭丽霞 康宝生教授 摘要 ( 签名) ( 签名) 随着三维数据采样技术和硬件设备的长足发展和计算机图形对于真实性、实 时性要求的日益增强，点云数据的曲面重建已经成为c a d 、c g 和c v 等领域的 研究热点之一作为点云数据插值的重要工具之一，r b f 隐式表示为曲面重建、 光顺、融合等许多问题提供了一个统一的框架但由于r b f 拟台的计算量大， 限制了重建速度和可处理的点云数据规模鉴于此，众多学者做了大量的工作本 文在总结径向基函数插值理论和对比已有重建算法的基础上，就点云数据的r b f 重建问题进行了研究，其主要工作如下： 1 总结了r b f 插值理论以及插值问题有解的充分条件和基于正则化理论的 既能精确插值点云数据又能逼近有噪点云数据的一个统一的砌强模型 2 提出基于八叉树空间递归分割的点云数据砌弹重建方法方法首先对数 据点云进行空间分割，建立相应的八叉树拓扑关系，然后在八叉树的每个叶结点， 构造插值或逼近属于该结点的数据点的m u h i o r d e r 径向基函数由于这时重建只 在八叉树的叶结点进行，降低了方程组系数矩阵的阶数，从而能够在合理的时间 内重建大规模的数据点集较之薄板基函数，m u l t i o r d c r 径向基的减函数性质改 善了系数矩阵状况进而加快了重建的速度；重建时间与约束点数几乎呈线性关 系，不会随约束点增加而激增；从重建结果看，霞建曲面既保持了局部细节又保 证了全局光滑；通过分析基函数中两个光滑因子万和r 与重建曲面光滑性的关系 表明，两参数的增加，增强了m u l t i _ o r d e r 径向基函数的灵活性 3 将智能算法与曲面重建理论结合，给出一种基于微种群遗传算法的r b f 神经网络曲面重建方法方法首先建立基于函数逼近理论的三层| j 馈r b f 神经 t 网络模型，并将表示曲面的映射关系存储于网络的联接权值中，然后用微种群遗 传算法完成神经网络的训练，确定权值向量，并将该网络模型应用于显式和隐式 曲面的重建g a u s s 基函数的f 定性保证重建问题解的存在性微种群遗传算法 通过“起动，再起动”过程，使网络既可避免早熟收敛，又有较快的收敛速度r b f 神经网络具有很强的容错性和泛函逼近能力数值实验表明，该模型适合于散乱 数据的光滑插值和缺陷表面的局部修复 关键词：隐式曲面，曲面重建，点云数据，r b f 多变量插值，m u l t i o r d e r 径向基 函数，八叉树递归分割，微种群遗传算法，g a u s s 基函数，r b f 神经网 络，等值面抽取 i i m a s t e rd e g r e ed i s s e r t a t i o n o np o i n t c l o u dd a t ar e c o n s t r u c t i o nu s i n gi 【b f g u ol i x i a ( d e p a r t m e n to f m a t h e m a t c s ，n o n h w e s tu n i v e r s n mx j a i l7 1 0 0 6 9 ) s u p e n r i s o r ： p r o f e s s o rk a n g b a o s h e n g a b s t r a c t a l o n gw i mm eg r e a tp r o g r e s si n3 dd a t am e a s l l r e m e n tt e c l l l l i q u ea i l dd e v i c ea n d i n c r e a s i n gr e q u i r e m e n to fr e a l i t y 、r c a l t i m e 血c o m p u t c rg r a p h i c s ，r e c o n s t m c t i o no f p o i n t c l o u dd a t ah a sb e c o m eo n e o f m em n d a m e n t a lp r o b l e m si nc a d ，c ga s 、w l la s cv a so n eo ft l l ei m p o r t a mp o i n t c l o u dd a t ai n t e r p o l a t i o nt 0 0 1 s ，t h ei m p l i c i t r e p r c s c n t a t i o no fo b j e c t ss h a p e sw i 血r b fo 腩r s 矗u n m e d 舳m e w o r kf o rs e v 啪1 p m b l e m ss u c ha ss u r f a c er e c o n s t r u c t i n g 、s m o o t h i n ga i l db l e n d i n g b e c a u s eo ft h e c o m p u t a t i o na 1 1 ds t o m g ec o h 巾l e x i t yo fr b ff i m n g ，t h es p e e do fr e c o n s t r u c t i o na t l d t h es c a l eo fp o i n t - c l o u dd a 诅a f er e s 订i c t e d o nt h eb a s eo f 伽ep r e d e c e s s o r s w o r k ，t l l s t h e s i s 芦e s e n t ss o m ee 伍c i e ma l g o r i 也m sf o rp o i m - c l o u dd a t ar e c o n s t m “o n t h e m a j o rw o r k si n v o l v e da r ea sf o l l o w s ： f i r s to fa l l ，i ts 啪m a r i z c st h e 血e o r yo fr b fi n t e r p o l a t i o na n dm es u m c i e n t c o n d i t i o no ft h es 0 1 v a b i l i t yo fi m e r p o l a t i o np r o b l e m b a s e do nr e g u l a r i z a t i o n t e c h n i q u e s ，au n m e dr b fa p p r o a c h ，也砒a l l o w st h es u r f a c et oe x a c t l yi n t e 印o l a t et h e d a t aa n da p p r 0 x i m a t e 也en o i s yd a t a ，i sp r e s e m e d t h ea p p f o a c hc r e a t e sas i n g l e i m p l i d tf u r 皿t i o nb ys 啪m i n gt o g e t h e rs e v e r a lw e i g h t e dr a d i a lb a s i sf m k t i o n s s e c o n d l kb a s e do no c t r e es p a c ep a n i t i o n ，af a s ts u r f h c er e c o n s t n l c t i o nm e t h o d f o rp o i m c l o u dda _ t a l l s i n gr b f i sp r o p o s e d np a r t i t i o i l st h ep o i n t - c l o u dd a t as p a c e m s t l ya 1 1 dc r e a t e so c t r e et o p o l o g i c 咖c t u r ea c c o r d i n g l h1 1 l e n ，a te a c hc e l lo ft h e o c t r e ep a r t i t i o n s ，am u l t i _ o r d e rr a d i a lb a s i g 如n c t i o nt h a ti n t e r p o l a t e so r 印p r o x i m a t e s t h ed a t ap o i n t sw h i c hb e l o n gt ot h ec u r r e n tc e l li sc r e a t e d d u et ot h ee a l e c t i v eo c t r e e a l g o r i m m ，t h es i z eo fr e s u l t i n gm a t r i xn e e d e dt ob ep m c e s s e de a c ht i m ei sr e d u c e d u i t h a tp e r m i t sr e c o n s t m c t i n go f1 a r g e - s c a l ed a t as e t si nar e a s o n a b l et i m e f u r t h e r m o r e ， t h em u l t i o r d e rb a s i s 向n c t i o nh a sg e v e r a la d v a n t a g e sc o m p a r e dw i t ht h et h i n p l a t e b a s i s c t i o n t h ec o n d i t i o no ft h es y s t e mm a t r i xf o n e d b yt h ed e c r e a s i n g m u l t i o r d e rb a s i sm n c t i o ni si m p r o v e d r 1 m n i n gt i m ei n c r e a s e sf a i r l yl i n e a d ya sm o r e c o n s t r a i m sa r e s p e c i f i e d t h er e c o n s 仃u c t e ds u r f a c ei sl o c a l l yd e t a i l e d ，y e tg l o b a l l y s m o o t h ，b e c a u s et h er b ft h a tw eu s ea c l l i e v em u l t i d l eo r d e r so fs m o o t h n e s s t h e r e l a t i o n s l l i pb e t w e e nt h es m o o t l l i l e s so fs u r f h c ea n dt h ev a l u e so fd a r a i r i e t e r s 占a i l dr i sa l s oa n a l y z e d a tt h el a s t ，b a s e d0 nm i c r o g e n e t i ca l g o r i t h r n 柚dr b fn e l l r a ln e t w o r k ，an o v e l a p p r o a c h f o r p o i m - c l o u d d a t ar e c o n s m l c t i o ni s p r e s e n t e d i t e s t a b l i s h e sa 也r e e 。l a y e r e dn e 啪1n e t w o r k t h ew e i g h t sb e t w e e nt h eo u t p u ta n dt h eh i d d e nl a y e r a r ed e t e m l i n e db y 仃a i n i n gn e t w o r ku s i n gm i c r o - g e n e t i ca l g o r i m m t h en e t w o r ki s d e s i g n e da n du s e dt or e c o n s t r u c te x p l i c i ta n di m p “c i ts u i f a c e s i nt h ec a s eo f m i c r o 。g e n c t i ca l g o r i t h mt h e “s t a r ta 1 1 dr e s t a n p r o c e d u r eh e l p si na v o i d i n gt h e p r e m a t u r ec o n v e 唱e n c ea t l da c c e l e r a t i n gm ec o n v e 唱e n c eo fn e t w o r k m o r e o v e r ，r b f n e l l r a ln e t w o r kh a sb e t t e r 曲i l i t yo ff a u n - t o l e r a n c ea n df h n c t i o n a l 印p r o x i m a t i o n t h e e x p e r i m e m a lr e s u l t ss h o wt h a tt l l er b fn e u r a ln e t w o r ki ss u i t a m ef o rs c a t t e r e dd a t a s m o o t l li n t e r p 0 1 a t i o na i l di se m c i e n ti nr 印枷n g i n - c o m p l e t em e s h e s k e y w o r d s ：h 1 1 p l i c “s u 曲c e ，s u r f a c er e c o n s t n l c t i o n ，p o i m c 1 0 u d ，r b fm u l t i v a r i a b l e i n t e r p o l 撕o n ，m u l t i o r d e rr 枷a lb a s i sf u n c t i o n ，o c t r e er e c u r s i v cp a n i t i o n ， m i c r 0 g e n e t i ca l g o r i t l l i i l ， g a u s s i a n ， r b fn e u r a l n e t w o r k i s o s l l r f a c e e x t r a c t m g 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西北大学。学校有权保留并向国家有关部门或机 构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存和汇编本学位论文。同时，本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 - 学位论文作者盘名：郭丽l 霞 指导教师签名：吒倦 拜，月多日 枷彳年，月多日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其 他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：南丽霞 m j 年f 月，日 第一章绪论 1 1 逆向工程和曲面重建技术 1 1 1 逆向工程 逆向工程( r c v e r s ee n g i n e e r i n g r e ) 又称反向工程或反求工程，是随计算机 技术的发展和成熟及数据测量技术的进步而迅速发展起来的一门新兴学科与技 术它是在无图纸或图纸不完整以及无c a d 模型的情况下，从现有产品模型或 实物模型，利用数字化及计算机辅助设计技术转化为工程设计模型或概念模型的 过程 在工程技术人员的一般概念中，传统的正向设计过程是一个从无到有的过 程如产品设计，设计人员首先在大脑中构思产品的外形、性能和大致的技术参 数等，然后通过绘制图纸建立三维数字化模型，最终将这个模型转入制造流程中， 完成其整个设计制造周期，而逆向工程可以认为是一个从有到无的过程简单地 说，逆向工程就是从已有的零件或已经存在的模型入手，首先通过测量扫描等先 进的数字化处理手段获得实物信息( 即用一个庞大的三维数据点云来表示整个零 件或实物模型) ，然后利用重建技术快速准确地建立数学模型，最后再在工程分 析基础上，数控加工出成品或者模具后制成成品的过程从这个意义上说，逆向 工程在工业设计中的应用已经很久了，早期的船舶工业中常用的船体放样设计就 是逆向工程的很好实例 随着计算机技术在各领域的广泛应用，特别是数字化测量技术的迅猛发展， 逆向工程技术越来越多地被应用到医疗成像数据的可视化、地质勘探数据处理、 虚拟现实、文化遗产保护等其它领域 因此，通过数字化测量设备( 如坐标测量机、激光测量设备等) 获取物体的 空间数据，利用曲面重构技术建立对象三维模型的逆向工程技术可以认为是将实 物模型转化为三维模型的相关数字化技术和几何建模技术的总称，它的实施过程 是多领域、多学科的协同过程逆向工程的体系结构主要由点云数据获取、数据 预处理、曲面重建以及快速制造等几部分组成，下面简要介绍其中的前三部分 1 1 2 点云数据获取 三维物体形状的数字化是计算机视觉、虚拟现实等领域的关键技术，而近年 来出现的许多大容量、高速度的计算机和各种先进的采样设备，为点云数据的采 集工作提供了必要的工具目前采用的主要测量设备有：三坐标测量仪、激光测 距扫描仪、光学照相测量仪、计算机x 线断层摄影术( c t ) 、核磁共振电子计 算机断层扫描术( m r i c t 或m r i ) 和逐层切削照相测量等三坐标测量仪、激 光测距扫描仪、光学照相测量仪主要用于对实物原型的外部形状的测量，而c t 、 m r i 和逐层切削照相测量则用于具有复杂型腔轮廓的实物的测量 由于测量设备的不同，这些空间上离散的点云数据集就可以分成两种形式： 散乱数据和结构数据散乱数据仅包含点在空间的位置信息，如地质勘探数据、 气象监测数据、测井数据等。结构数据除了含有点在空间的位置以外，还含有其 它附加信息，如由c t 、m r i 等采集的信息，数据点之间在重建时有邻接关系等 拓扑信息可以利用本文的方法主要针对散乱表面数据进行重建 1 1 3 点云数据处理 数据处理是逆向工程中的关键环节，它的结果将直接影响后期模型重建的速 度和质量数据处理过程常包含以下几个方面的工作u j ：数据预处理，如去 噪处理、多视合并等，增强数掘的合理性和完备性数据优化，压缩不必要 的数据点，减少后期的计算量数据分块处理，通过先进测量设备所获取的 点云数据量往往比较庞大，由于时间效率和存储空间的要求以及一些重建算法的 限制，对点云数据进行分割处理有时也是必要的数据光顺，通常采用局部 回弹法、圆率法、最小二乘法和能量法等来光顺 在用现有的测量设备生成数据时，难免会因为人为扰动或者扫描测量设备本 身的缺陷使之带有噪声，因此在对数据进行重建前有必要对其进行去噪处理去 噪的目标是在剔除噪声获取离散曲面更高阶光滑性的同时，尽量防止模型产生收 缩和过光顺目前，点云模型的去噪算法主要有三类：第一类，参数化三维数据， 并对参数进行均匀重采样，然后扩展图像处理中的滤波技术对数据去噪【2 ，但是 由于离散点参数化技术本身的难度，这类方法去噪效果并不理想另一类比较有 效的方法是基于概率统计和曲线曲面理论，对三维模型采样点进行离散几何分 析，直接在三维空间对点云数据进行估计去噪处理胡国飞1 3 j 提出的点云模型的 各向异性去噪算法就属于这一类，其基本思想是利用采样点的法向和曲率等内在 几何信息，根据g a u s s 核函数来各向异性地扩散噪声信号，达到快速去噪和光顺 点云模型的目的第三类则通过选取光滑曲面对离散点进行拟合重建达到去噪目 的，这类方法去噪效果在很大程度上取决于所采用的拟合曲面的形状欲获取光 滑盐面却比较费时，如c a r r 【4 j 的隐式光顺算法 当所获取的采样点数据量很大且采样密度很小时，需要适当缩减数据量例 如，螺旋c t 扫描的层间距很小，仅为l m m ，图像的分辨率也很高，通常为 5 1 2 x 5 1 2 ，而且原始数据的灰度等级为4 0 9 6 因此，一组5 1 2 5 1 2 1 0 0 的c t 扫描图像其数据量可达5 3 兆字节，很难被目前的中低档工作站和微型计算机所 接受这时就需要对数据加以精炼和选择，既要减少数据量，又要最大限度地减 少有用信息的丢失c a r r 【5 1 采用贪婪算法( g r e e d ya 1 9 0 r i t h m ) 精简点云数据，用 优化后较少的数据点集达到预定的拟合精度，同时还加速后续方程组求解，减少 嗌面重建的时间 面对庞大的数据量，对其进行分块或分层次处理，化繁为简，分而治之，同 样也是提高重建效率的一种行之有效的方法m i u r a l 6 j ，k o i e k i n e 【”，y u t a k a o h t a k e 【8 9 】，f r i s k e n 【1 0 等都采用八叉树分割技术对数据集进行分割，建立八叉树 数据结构，然后在每个叶结点进行r b f 拟合或p u 逼近f i o a t e r 和i s k e 【首先 通过d e l a 吼a y 三角剖分构造数据点集的一个嵌套序列，然后分层进行c s r b f s 插值；y 0 b t a k e 【l “”】提出了改进的用紧致支撑局部径向基函数插值和逼近3 d 点 云数据的分层次方法 1 1 4 曲面重建基本概念及相关技术 基于测量数据的曲面重建技术是逆向工程技术关注的主要对象，也是逆向工 程中最重要和最困难的问题之一其目的在于寻找某种数学描述形式，精确、简 洁地描述一个已存在的物理曲面的形状，并以此为依据对曲面本身进行分析、计 算、修改和绘制它有两方面的含义，首先已有的物理曲面是曲面重建的根据， 即是对从该曲面上采集的数据的重建；其次已有的曲面是衡量重建曲面质量好坏 的标准，要求建立的模型能忠实地恢复已有曲面的原状【1 4 1 曲面重建基本概念 描述物体表面形状的数学表达式称为物体的几何模型，也称为曲面的数学模 型曲面的数学模型非常重要，它是对物体进行分析、计算和绘制的根据，是研 究曲面性质的工具【川 曲面是具有某种性质的点的集合，从理论上讲，每张曲面都有它自己的数学 模型但是曲面的数学模型存在是一回事，人们对它的掌握又是另外一回事有 很多复杂的曲面，其模型并未为人们所掌握，例如人的头颅、雕塑、工艺品等的 外形和野外地形等等；也有很多复杂的曲面虽有数学模型，但是未掌握在需要者 手里，例如复杂叶片、机械零件和某些出土文物器皿的外表面等等为了利用计 算机对这类物体和其外表曲面进行分析处理，首要的任务就是为其建立数学模 型，即曲面重建过程 曲面重建的基本要求是准确易行准确即要求建立起来的模型比较准确的反 映原来曲面的形状，或者说较好地逼近原来的曲面易行即要求对所建立的数学 模型易于进行各种操作，或者说较方便地适用于计算机进行曲面的存储、分析、 计算和绘制等 2 曲面重建方法 对大量的测量数据点进行睦面重建是逆向工程的核心研究内容之一，由于它 在工业制造、医疗、地质及气象等应用领域的重大意义，引起了国内外众多学者 的广泛关注，提出了一系列曲面重建的算法，可按重建方式分为以下几种【l 刈： 曲面拟合：曲面拟合是基于参数曲面、隐式曲面或分片多项式近似数据 点的一类方法，它主要包括隐式拟合和显式拟合 隐式拟合( i m p l i c i tf i t t i n g ) ：通过定义函数( x ) ：m 3 _ + 婀，保证函数的零 值集逼近给定离散点集通过所选函数形式不同可将其分为参数拟合( p 猢e t r i c f i t t i n g ) 和隐函数拟合，前者用x ，弘z 坐标上的多面体为函数，生成如x = 一( “，v ) ， y = 正( ”，= = 正( ，v ) 形式的代数曲面，后者则选用势函数或场函数，如b l i n n l l “、 m u r a k i 【1 7 l 的g a u s s 密度函数、n i s h i m u r a 的分段二次多项式和w y v i l l 的六次多项 式等多种形式以及目前广泛使用的径向基函数表示【1 8 2 8 】等等下面分别介绍几 种在隐式拟合中常用的几种曲面形式 简单曲面p r a t t 【2 9 利用平方h a u s d o r f f 距离之和的最小化，直接用球、立 方体、圆柱等拟合数据点简单曲面的解析表达式十分简单，但难以重建复杂拓 扑的曲面形状 超二次曲面超二次曲面在二次曲面方程中引入额外参数，大大提高了 形状描述能力p e n t l 锄d 【3 0 】利用隐函数易于曲面求交计算的特性，用变形超二次 曲面，以模式变形描述整体形状，以盐面沿表面法矢的偏移表达局部细节这种 混合的隐函数参数曲面方法以单一的隐式方程同时描述曲面的局部和全局特 性，提供了一种描述物体形状的通用隐函数形式；z h o u 【3 l 】将超二次曲面的特征 指数由常数扩展到函数形式，可得光滑变形的非对称体 b 样条曲面( b s p l i n es u r f a c e )b 样条曲面是矩形域参数曲面的代表， b 样条具有表示和设计自由曲面曲线的强大功能，在重建曲面中被广泛使用多 年来，人们一直用多个b 样条曲面通过面片间的光滑连接实现重建，可惜算法 受数学复杂性限制多不实用b 样条有统一、通用、有效的标准算法，b 样条曲 面具有直观性、凸包性、局部性、连续性与光滑性好以及低次样条拟合稳定等优 点，但难以解决以下问题：不能精确表示二次曲面；难以用单一b 样条曲面重 建任意拓扑曲面；任意拓扑时，难以自动构造b 样条面片网和对面片上数据点 的参数化；难以同时满足相邻b 样条面片间的切面连续和保持面片网对数据点 的拟合 ( 曾n u r b s 曲面( n o n - u n i f o m lr a t i o n a lb s p l i n es l l r f a c e )n u r b s 曲面能 精确表示解析实体和自由曲面，比b 样条曲面灵活性更大，效率和简洁度高， 是s t e p 标准中描述产品几何形状的惟一方法但因引入了权因子，增加了算法 复杂性，仅能处理小规模的简单曲面 隐式拟合中，参数曲面具有计算曲线曲面的几何量简单、便于显示、控制方 便、易剖分和几何不变性等特点，但往往难以找到一个合适的参数形式来表示被 测曲面隐式曲面具有可自动融合成光滑曲面的重要特性，连续性和变形性好， 适合于描述具有光滑复杂外形的物体，然而，难以进行实时绘制、曲面编辑及尖 锐特征表达的不足又限制了它的使用参数曲面拟合和隐式曲面拟合相比，前者 的公式表达简洁，后者在拟合计算方面收敛更快，在曲面求交、变形方面更方便、 快捷和精确 显式拟合( e x p i i c i tf i t t i n g ) ：通过给定二维点集 置= ( ，h ) ：。及其对应标 量值 如，构造函数，( x ) ：巩2 _ 孵，使得，( 置) = ( 插值) 或者，( x ，) * ( 逼 近) 主要的方法有s h c p a r d 法，f r a i l k e 等的m q s ( m o d i f i e dq u a d r a t i cs h e p a r d ) 方法以及h a r d y 的m q ( m u l t i q u a d r i c ) 方法1 2 0 】等显式拟合多基于全局计算， 所得曲面整体形状美观可是，因需求解大规模线性方程组而限制了它所能处理 的数据集规模，通常一个点( x ，y ) 将对应多个z 值，导致其适用范围很狭窄 分片线性重建：分片线性重建是一类通过建立多面体化的表面，插值或 逼近给定点的方法，这类方法又可分为多边形方法和体方法 多边形方法( p o l y 罟o n a lm e t h o d ) ：基于雕塑或区域生长的方式建立多面体 模型，是一类局部重建方法基于雕塑的方法的基本原理是对数据点集作四面体 网格的d e l 姗a v 剖分，得到一包含所有数据点的凸包，然后以类似雕塑的方式， 通过层层剥离冗余四面体，保证在四面体网格拓扑关系不变的情况下，使物体表 面所有散乱数据可见，即所有点都在四面体表面或不存在可进一步删除的四面 体，此时四面体网格的边界三角网格就是数据点集的三角剖分网格基于区域生 长的方法是从一种子三角形开始，基于某种准则，不断选择新点并加入当前的区 域边界，生成新三角形，更新边界，直到遍历所有点将所得数据点的初始剖分 优化后，获取逼近被测面的d e l a u n a y 三角网格 基于雕塑的方法可从理论上保证重建曲面的质量，即所得曲面拓扑正确，且 随着采样密度的增大，重建曲面最终收敛于真实的被测曲面，还可克服人为划分 点云数据区域所带来的操作繁琐和低可靠性但是四面体剖分的计算量和内存占 用很大，处理具有上百万点的点云时易导致数值不稳定，采样数据存在噪声、采 样点分布较稀疏或具有尖锐特征时，易造成网格丢失而基于区域生长的方法能 处理大规模数据点集，可直接处理凸封闭曲面和开曲面情况然而，此类方法通 常需要人为对数据点集预先划分区域，不可靠，也降低了自动化程度 体方法( v o i u m e t r i cm e t h o d ) ：将三维区域分割成体素( 通常为三维盒状 体) ，每个体素包含8 个顶点，通过在这些顶点处计算场函数，可提取等值面作 为对原始曲面的近似h o p p e 【3 2 对每个数据点用其最邻近的个点通过最小二乘 法拟合一个逼近的切曲面，切平面的方向通过构造一个加权r i e m a n n 图并计算此 图的最小生成树来确定遍历此树，所有切平面的方向即可确定下来，用每个点 到切平面的距离来构造点到物体表面的( 有向) 距离场，该距离场零等值面即为 重建曲面h o p p e 方法重建的曲面为逼近曲面而不是插值曲面，本质上相当于对 数据进行了低通滤波而其寻找每个数据点的女个邻近点的方法对点的分布较为 敏感，如医学图像数据中，某个数据点的t 个邻近点可能均在同一个切片上，这 样将导致错误的切平面估计周儒荣【3 3 】将切平面中心直接取成数据点，改善了边 界质量，同时提出并解决了法向传播中可能出现的“孤岛”问题基于类似思想， c u r l e s s 和l e v o v 【3 4 j 将每幅图像扫描转换成一个加权有向距离场，从而合并多幅 图像并表示于一个规则三维网格中，该方法因在不同深度图像中使用标量场法， 可处理上百万的数据点，大大优于h o p p e 3 2 j 几万个点的处理量体方法是一种全 局重建方法，与多边形方法比较时间效率更高 分片线性重建方法表示简单、直观、适于快速计算和实时显示的需要，当前 许多c a d 造型系统和快速原型制造系统数据输入输出也逐步采用多边形表示模 式，已成为目前应用最广泛的方法之一然而，该类方法存在计算量大、对计算 机硬件设备要求高、所产生的拓扑结构未考虑被测体固有的曲面拓扑结构而可能 导致重建曲面与被测曲面拓扑不一致以及三角片本身不保证光滑连续性的缺陷 细分曲面( s u b d i v i s i o ns u r f a c e ) 重建：细分方法将光滑益面定义为连续细 化过程的极限，它通常没有显示表达式，仅提供算法描述过程，用以产生加密的 离散点阵来表达曲面的信息，统一了传统参数曲面与多边形两种实体表面的表示 方法因而细分曲面是一种极限曲面，对给定的初始网格，通过指定新顶点生成 规则和它们之间的连接关系获得更密的网格，重复该过程将控制网格逐渐磨光使 之最终收敛到一张光滑曲面随着ca _ 咖u 1 1 c l a r k 细分曲面的出现，基于不同细 分规则的细分曲面不断涌现，如l o o p 模式、b u t t e m y 模式、d o o s a b i n 模式 等h o p p e 州等在1 9 9 4 年提出通过反求控制顶点的方法，为需要重建的曲面建 立控制网格，然后运用一系列的细分算子，对控制网格进行细分，生成细分睦丽， 来逼近需要重构的曲面细分曲面可以通过在不规则拓扑结构处采用特殊的细分 规则而定义在任意拓扑网格上：而曲面的光顺性可以由细分模式的极限性质自动 保证，不存在拼接和裁剪问题，几乎可描述任意复杂的光滑曲面，其层次性和递 归性使之与多分辨分析紧密相连，保证了数值稳定性，常用于特征动画设计和复 杂雕塑曲面重建但由于细分曲面上的点并非显式给出，给曲面的几何设计等带 来一定困难 基于物理的重建：这类方法是基于构造的初始几何模型，通过引入物体 本身物理特征和所处外部环境因素的描述使模型变形并逼近散乱点这类模型又 分为离散模型和连续模型两大类 离散模型是从离散的局部入手，然后综合到整体，最典型的是粒子弹簧模型 ( m a s s s p m i gm o d e l ) ，它将变形物体简化成由弹簧连接的线弹性质点系统，利 用该系统的运动规律描述物体的弹性变形过程r u p r e c h t l 36 】等通过模拟曲面在一 定物理属性和外力综合作用下的变形，使之最终变形到被测曲面，可用于预知拓 扑条件下的任意三维表面的重建，但结果与模型初始位置有关t u r k p 基于粒子 互斥模型，将分布到模型表面的新顶点集相互连接和细化，建立曲面网格的多层 次表示，保证具有初始表面的几何和拓扑粒子弹簧模型简单易构造，计算速度 快，支持交互和实时重建，适合于并行计算不足之处是难以进行弹簧常数的选 值和网络拓扑的设计，易导致计算量激增和曲面失真 连续模型从遵循连续机制的等式而产生，有基于有限元( f i n i t ee l e m e n t m e 由o d ，f e m ) 和基于边界元( b o u n d a r ye l e m e n tm e t h o d ，b e m ) 的模型等 基于物理的方法是一种动态建模方法，它具有高度逼真的造型效果，尤其适 合于描述形状特别奇怪的物体或柔性变形体，在计算机视觉中应用较多但难以 找到合适的变形函数和物理模型实现曲面的精确重建，求解规模往往十分庞大， 导致求解速度慢 基于神经网络的重建：人工神经网络实质是一个多变量方程求解系 统网络神经元之间按某种规律连接，相互传递信息选择不同的网络模型，可 形成不同的重建方法，目前应用较为广泛的网络模型主要有：b p ( b a c k p r o p a g a t i o n ) 网纠3 9 “卅和径向基三层前馈网络【4 1 埘 pg u 【3 9 1 利用b p 算法，以已 实现的逼近曲面或非均匀b 样条面为样本，训练四层神经网络模型，将一组样 本的输入输出问题转化为非线性优化问题，用梯度搜索技术使网络实际输出与期 望输出的方差最小，最终得到逼近原始点集的n u r b s 曲面该方法所得模型逼 近精度较高，但对曲面曲率收敛性的稳定性差：由于b p 算法是一种非线性优化 方法，它不可避免的存在局部最优解的缺点，王铠等1 4 0 l 结合b p 网络和模拟退火 算法，用变步长梯度下降法修改权值，用模拟退火技术按概率随机接受一个不成 功的训练结果，使梯度下降中产生随机噪声扰动，提高网络训练速度，该方法兼 有快速梯度下降的优点和全局最优性，提高了鲁棒性和容错性，但不能从神经网 络的参数提取参数曲面的控制顶点，与通用的几何建模系统兼容性差熊邦书 4 “、 邓春梅等m 佣性能优于b p 网络的r b f 神经网络实现了对自由曲面的重建缪 报通等【4 3 j 用r b f 神经网络的对c a g d 中散乱数据插值和曲面上离散点集的光滑 插值问题进行求解而李道伦等( 4 4 把径向基神经网络与隐式曲面构造原理相结 合，提出了一种构造三维实体曲面的新方法新方法首先把实体盐面看成由三元 隐式函数所描述的封闭曲面，并以此隐式函数为基础构造一个三元显示函数，使 得隐式函数所描述的曲面为所构造的显式函数所描述的超曲面的零等值面然后 用径向基神经网络对三元显式函数进行逼近，最后从仿真超曲面中抽取出零等值 面 神经网络具有强大的泛函逼近能力，三层前向网络能以任意精度逼近任意连 续函数及其各阶导数，且具有较强的容错性和联想能力神经网络将表示曲面的 映射关系存储于网络的联接权值和阈值中，使得模型极适合于光滑曲面重建、重 建曲面的局部修改和缺陷表面的局部修复实际应用中，虽然有一些加速网络收 敛的训练算法，但由于网络收敛难度大，计算费用高，一般仅适用于单张简单曲 面，无法满足任意拓扑和任意复杂形状的曲面的重建 重建算法多种多样，本文则主要侧重于隐函数曲面重建方法和神经网络重建 方法的研究，第三、四章将分别给出详细介绍 1 2 隐函数曲面重建的发展现状 隐函数拟合方法是用一个函数零值集表示被测曲面的曲面方程的方法：若函 数，( x ) 隐式定义睦面m ，则满足，( x ) = o 的所有点x 都在曲面上，其中标量 函数厂：暇3 _ 孵本文中我们有如下约定： i x l ，( x ) = o ，x 孵3 ) 表示目标曲面 x i ，( x ) o ，x 暇3 ：表示曲面内部 l xj ，( x ) o ，j d = j ( s ) ，当p ( x i ，x 2 ) o ，( x ) o ，厂( x ) = o 的点的 函数值d 分别取为1 、o 、一1 在这里尚有一个未解决的问题：数据点x 处对应 法