（应用数学专业论文）基于遗传算法的b样条曲线曲面重建.pdf

祸建师范大学学位论文使用授权声叨 福建师范大学学位论文使用授权声明 呈交的论文( 论文题目：基王塑馒篡洼的趋绫曲面重建) 是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果。本人了解福建师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交的学位论文并允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容；学校可以采用影印、缩印或其他复制手段保存 论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名盏p 粗指导教师签名名江 签名日期圣翌垒垒鱼盛鱼璺 祸建师范大学硕：e 学位论文 摘要 逆向工程技术是随计算机技术的发展和成熟及测量数据技术的进步而迅速发展 起来的一门新兴学科与技术，指从实体重建出它外形的c a d 模型，以便进一步利用 先进技术对其进行处理。曲线曲面重建是逆向工程的重要研究内容，在航空汽车制 造业、医学成像、地形地貌描述等领域应用广泛。文本研究了b 样条闭曲线重建和 层次b 样条曲面重建，主要成果概括如下： 一、分析和指出在曲线拟合过程中传统方法容易造成数据冗余，而使用基本遗传算 法虽然可以同时优化节点值与参数值，减少数据冗余，但是控制顶点个数需要 事先人为确定。针对这些不足，本文提出了一种基于m c s s a y 遗传算法的自适 应b 样条闭曲线拟合方法：在进化计算过程中，通过种群中每个染色体的基 因和基因个数的不断变化，自适应地调整参数序列、节点向量和控制顶点个数， 从而获得b 样条闭曲线在误差范围内逼近有序数据点序列。该方法只要输入b 样条闭曲线的阶数和有序数据点就可以得到一条满足预期的形状的b 样条闭 曲线。它有较强的自适应能力，可用于智能曲线拟合系统开发。一些实验结果 表明该方法是有效的。 二、回顾已有层次b 样条曲面拟合方法采用全局细化方法和均匀加倍细化规则等 缺点。本文提出了一种局部自适应细化层次b 样条曲面逼近三角网格的方法。 首先用遗传算法对边界进行同步拟合，接着用最小二乘拟合方法得到插值边界 曲线的b 样条曲面，然后利用遗传算法在误差超限的区域上由粗糙到精细地局 部自适应优化曲面，同时保持不同层次b 样条曲面的c 2 连续。这样一层在另 一层之上进行局部细化拟合直到满足给定的误差。最后获得的层次b 样条曲 面满足给定误差下逼近三角网格。该方法可减少控制网格规模，最后获得的层 次结构的b 样条曲面可以用于网络分层传输与渐渐显示。 关键词：最小二乘拟合：b 样条闭曲线；层次b 样条曲面；遗传算法 福建师范火学郑峰松硕士学位论文 a b s t r a c t r e v e r s ee n g i n e e r i n gi san e ws u b j e c ta n dt e c h n o l o g yc o m i n g u pw i t ht h e d e v e l o p m e n to fc o m p u t e rs c i e n c ea n dd a t ad i g i t i z a t i o n w i t h r e v e r s ee n g i n e e r i n g t e c h n o l o g y , c a dg e o m e t r i c a lm o d e l sa l er e c o n s t r u c t e df r o me x i s t e n to b j e c t s ，w h i c hc a n b ep r o c e s s e db ya d v a n c e dt e c h n o l o g y c u r v ea n ds u r f a c er e c o n s t r u c t i o nw h i c hi sa n i m p o r t a n tp a r ti nr e v e r s ee n g i n e e r i n gi sw i d e l yu s e di nv a r i o u sf i e l d ss u c ha sa v i a t i o na n d a u t o m o b i l em a n u f a c t u r i n gi n d u s t r y , m e d i c a li m a g i n g ，d e s c r i p t i o nt o p o g r a p h ya n ds oo n t h i st h e s i sm a i n l ys t u d i e st h er e c o n s t r u c t i o no fb s p l i n ec l o e s e dc u r v e sa n dh i e r a r c h i c a l bs p l i n es u r f a c e si nr e v e r s ee n g i n e e r i n g t h em a i nc o n t r i b u t i o n sa r es u m m a r i z e da s f o l l o w s ： 1 b a s e do nt h ea n a l y s i st ot h ec o n v e n t i o n a la p p r o a c h e sf o rb s p l i n ec u r v ef i t t i n g , i ti s p o i n t e do u tt h a tt h e s ea p p r o a c h e sa r ee a s yt or e s u l ti nd a t ar e d u n d a n c y i nc u r v ef i t t i n g b a s e do ns i m p l eg e n e t i ca l g o r i t h m ，t h o u g hn o d ev a l u e sa n dp a r a m e t e rv a l u e sc a nb e o p t i m i z e da tt h es a m et i m e ，t h en u m b e ro fc o n t r o lp o i n t so fb - s p l i n ec u r v es h o u l db e s p e c i f i e di na d v a n c e i no r d e rt oo v e r c o m et h e s ed e f i c i e n c i e s ，an e wa p p r o a c ho fb - s p l i n e c l o s e dc u r v ef i t t i n gt oas e to fo r d e r e dp o i n t si sp r e s e n t e db a s e do nm c s s a yg e n e t i c a l g o r i t h m i nt h ep r o c e s s o fe v o l u t i o n a r yc o m p u t a t i o n ，ab - s p l i n ec l o s e dc u r v e a p p r o x i m a t et o as e to fo r d e r e dp o i n t sw i t h i nag i v e ne r r o ri so b t a i n e db ya d a p t i v e l y a d j u s t i n gp a r a m e t e r ss e q u e n c e ，n o d ev e c t o ra n dt h en u m b e ro fc o n t r o lp o i n t s a n dt h e s e a d j u s t m e n t sa r ec a u s e db yc o n s t a n t l yc h a n g i n gg e n e sa n dg e n en u m b e ro fc h r o m o s o m ei n t h ep o p u l a t i o n w i t ht h i sa p p r o a c h ，ab - s p l i n ec l o s e dc u r v es a t i s f y i n gt h ed e s i r e ds h a p e f i d e l i t yc a nb cg e n e r a t e da sl o n ga sas e to fo r d e r e dp o i n t sa n dt h eo r d e ro fb s p l i n e c l o s e dc u r v ea r ei n p u t e d t h i sa p p r o a c hh a ss t r o n ga d a p t i v ec a p a c i t ya n dp a nb ea p p l i e d i n ai n t e l l i g e n tc u r v em o d e l i n gs y s t e m s o m ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t ei t s e f f e c t i v e n e s s 2 s o m ec o n v e n t i o n a la p p r o a c h e sf o rh i e r a r c h i c a lb s p l i n es u r f a c ef i t t i n ga r cr e v i e w e d ， a n ds o m es h o r t c o m i n g sd u ct oo v e r a l lr e f i n i n gm e t h o da n dr e f i n e du n i f o r mr u l e sa r e a n a l y z e d i n t h i sp a p e r al o c a la d a p t i v er e f i n e m e n ta p p r o a c hf o rt r i a n g u l a rm e s h n 福建师范大学硕士学位论文 a p p r o x i m a t i o nw i t hh i e r a r c h i c a lb - s p l i n es u r f a c ei sp r o p o s e d f i r s t l y , t h eb o u n d a r yo f t r i a n g u l a rm e s hi sf i t t e ds y n c h r o n o u s l yb yg e n e t i ca l g o r i t h m s e c o n d l y ，t h ef i r s tl e v e l b s p l i n es u r f a c ei n t e r p o l a t i n gb o u n d a r yo l iv ei so b t a i n e db yl e a s ts q u a r ef i t t i n gm e t h o d t h i r d l y , i nt h er e g i o ne x c e e d i n gag i v e ne r r o r , g e n e t i ca l g o r i t h mi su s e dt oo p t i m i z et h e s u r f a c ea d a p t i v e l yw h i l et h eb s p l i n es u r f a c e sa td i f f e r e n tl e v e l sk e e pc 2c o n t i n u i t y o n e l e v e la b o v ea n o t h e rl e v e l ，t h el o c a lr e f i n e m e n tf i t t i n gi sc a r d e do u tu n t i lm e e t i n gag i v e n e l t o r a tl a s t ，t h eh i e r a r c h i c a lb - s p l i n es u r f a c ef i t t i n gt h et r i a n g u l a rm e s hw i t h i na g i v e n e r r o ri sc o n s t r u c t e d w i t ht h i sa p p r o a c hal e s ss i z eo ft h ec o n t r o lg r i dc a nb eo b t a i n e d t h eb - s p l i n es u r f a c e sg e n e r a t e db yt h ea p p r o a c hc a l lb eu s e df o rm u l t i 1 e v e ln e t w o r k t r a n s m i s s i o na n d p r o g r e s s i v es h o w k e y w o r d s ：l e a s ts q u a r ef i t t i n g ；b s p l i n ec l o s e dc u r v e ；h i e r a r c h i c a lb - s p l i n es u r f a c e ； g e n e t i ca l g o r i t h m i i i 福建师范大学郑峰松硕士学位论文 中文文摘 计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，简称c a g d ) 是随现代 工业发展而兴起的一门边缘学科，主要研究在计算机图像系统的环境中曲线曲面的 表示和逼近，为计算机辅助设计与制造( c a d c a m ) 中几何造型提供了核心理论和方 法。b 样条是c a g d 的一个主要研究对象，具有局部控制的能力，在不改变多项式次 数下增加控制顶点等优点，广泛用于计算机辅助交互设计，是许多c a d 系统中形状 描述的基本工具。本文研究了逆向工程中b 样条曲线曲面重建问题。曲线曲面重建 逆向工程的重要研究内容之一，广泛地应用于航空汽车制造业、人体器官造型、玩 具业、影视广告设计、服装设计、地形地貌描述等领域。全文共分四章： 第一章首先概述c a d 中逆向工程技术，然后对c a g d 中曲线曲面重建的研 究意义和研究现状进行总结和分析，并讨论其优缺点。最后简要 介绍了遗传算法。 第二章将m e s s a y 遗传算法与最d , - 乘理论相结合，给出一种控制顶点个 数自适应调整的b 样条闭曲线拟合方法。一条b 样条曲线的形状 是由它的节点向量和控制节点确定的。用b 样条曲线拟合有序数 据点序列的一个关键问题是选择好的节点向量和参数化，而在b 样条曲线最小二乘拟合问题的模型中，关于节点向量和参数向量 都是非线性的，所以在传统的方法中一般预先按某种规则确定节 点向量和参数向量以得到一个关于控制顶点的线性系统，解得控 制顶点，接着评价拟合误差。在误差超限的位置，通过插入新节 点来减少拟合误差，然后这样不断迭代计算直到误差满足为止。 这样容易造成数据冗余，因为有可能通过调整节点的位置就可以 改善逼近效果。利用m e s s a y 遗传算法对有序数据点序列的参数值 和b 样条闭曲线节点向量中的自由节点进行实数编码做为一个染 色体( 个体) ，来释放节点向量和参数向量的自由度。通过剪切 和拼接算子使得染色体的长度发生变化。而在每个染色体中含参 数值信息的基因的个数是不变，所以含有节点信息的基因的个数 发生变化，即节点的个数发生变化，由于在k 次b 样条曲线中， i v 福建师范大学硕士学位论文 控制顶点个数= 节点个数一k - 1 ，从而控制顶点的个数也发生变化， 进而可以对控制点个数自适应调整。本章采用最小二乘拟合误差 与近似弧长误差之和的倒数来评价种群中个体的适应度，然后通 过轮盘赌选择算子、剪切拼接算子、均匀变异算子运算驱动整个 种群进入下一代种群，这样重复进行直到满足终止条件为止。本 章基于m e s s a y 遗传算法的b 样条闭曲线最d - - 乘拟合方法在优 化参数向量与节点向量的同时，自适应调整控制顶点个数。通过 多个的实例验证了该方法的正确性，并与基于基本遗传算法的拟 合方法进行了比较。本章拟合方法适用于智能曲线拟合系统的开 发。 第三章在c a d 中，从点云中重建出被测物体表面的三角网格模型后，更 重要的是如何将三角网格模型转换为用b 样条表示的曲面。本章 将遗传算法与层次b 样条相结合，给出一种局部自适应细化层次b 样条曲面拟合方法。共分下面5 个步骤执行： ( 1 ) 边界拟合：首先将边界三角网格点参数化到单位正方形边界 上，然后利用基本遗传算法与最小二乘方法对同方向的边界进 行同步拟合，获得两条插值于角点的b 样条曲线。同理可以得 到另一个方向的两条插值于角点的b 样条曲线，从而得到四条 插值于四个角点的b 样条边界曲面。 ( 2 ) 基面拟合：利用f l o a t e r 方法进行内部三角网格点参数化，为 了减少计算量，通过均匀采样选取原始数据点的一部分做为第 一层曲面拟合的对象。然后以( 1 ) 步求得两个方向b 样条曲 线的节点向量做为b 样条曲面的节点向量以及b 样条曲线的 控制点做为边界约束，利用最d - - 乘方法反求出第一层b 样 条曲面的其他控制点，最后得到第1 层b 样条曲面( 基面) ， 初始化k = l 。 ( 3 ) 误差搜索：搜索误差超限的小节点区域，然后用最小包围盒包 围这些小节点区域来确定第k 层b 曲面拟合误差超限的区域。 为了保持上下层b 样条曲面的c 2 连续性，把最小包围盒向四 个方向扩张一个节点区间，然后把这个扩展区域作为第k + l v 福建师范大学郑峰松硕士学位论文 层b 样条曲面拟合的节点区间。 ( 4 ) 局部细化拟合：对参数值落在误差超限的扩展区域的数据点进 行非均匀采样。利用遗传算法对插入的节点进行编码，使得两 个方向的新插入的节点的个数之和固定，而每个方向的新插入 的节点的位置和个数可以自适应调整。同时当误差超限的小节 点区域个数小于最小包围盒内的小节点区域总个数的三分之 一时，采用新规则保留上一层的一些控制顶点不变，然后对非 均匀采样点进行约束最小二乘拟合，形成第k + l 层b 样条曲面。 ( 5 ) k = k + l ，然后执行第( 3 ) 一( 5 ) 步骤，直到满足误差为止。最后获 得的层次b 样条曲面表示成基面b 样条曲面加上它上面每一层 的局部b 样条曲面的控制网格偏移量表示的b 样条曲面。 第四章结束语总结全文的主要创新点和进一步研究的方向 v i 第1 章绪论 第一章绪论 本章首先简要介绍c a d c a m 中的逆向工程技术、然后综述c a g d 中的自由曲线曲 面重建技术，最后简要介绍遗传算法。 1 1c a d 中逆向工程技术简介 市场全球化使国家、企业面临的竞争日趋激烈，市场设计的要求发生了根本的 变化，多品种、小批量替代了少品种、大批量的传统生产模式，能否快速地生产出 合乎市场要求的产品就成为企业成败的关键，在许多情况下，只有产品模型和实物 模型，而没有产品的定义和图纸。传统的复制方法是用立体雕刻机或液压三次元靠 模铣床制作山一比一成等比例的模贝，秤进行量产。这利- 方法屈称类比式( a n a l o g t y p e ) 复制，无法建立工件尺寸图档，也无法实现外形的优化和创新。每一种方案 都制作实物样品，要付出大量的劳动，还存在着精度低、设计周期长及成本费用高 等问题。 为了适应先进制造技术的发展，需要将这些样件和实物转化为c a d 模型，以便 进一步利用a 址) a c e q 蝴以及c i m s 等先进技术对其进行处理。尽管已经出现了 许多成功的三维c a d 软件，但运用这些软件建立一个复杂的几何模型，尤其是利用 n u r b s 曲面模型进行曲面造型时，设计师常常需要调整成千上万个控制顶点，生成 满足要求的曲面模型二_ i 二a ，s l b t p 困难。基于计算机技术，自动实现样件和实物到c a d 模型 的转化，减轻设计师的负担，这就应用到了逆向工程( r e v e r s ee n g i n e e r i n g ) 。 2 0 世纪8 0 年代初由美国3 m 公司、日本名古屋工业研究所以及美国u v p 公司 正式提出了逆向工程的概念【1 1 。逆向工程的一般体系结构如图1 1 所示，它由离散 数据获取技术、数据预处理与三维重建以及规模化生产三部分组成。逆向工程技术， 从一个实体模型出发，利用数据采集设备( 如图1 2 ，从不同视点测量被测物体 表面，获得实物表面的一系列深度图像数据，经过数据预处理后，如进行低通滤波 消除测量误差，然后进行数据配准，将局部坐标系中的每一幅图像数据通过平移和 旋转配准到一个全局坐标系中。最后利用三维几何建模方法重构实物的c a d 模型， 福建师范大学郑峰松硕士学位论文 并最终生成i g e s 或s t l 数据，据此就能进行快速成型或c n c 数控加工。i g e s 数 据可传给一般的c a d 系统( 如：u g 、p r o e 等) ，进行进一步修改和再设计。另 外，也可传给一些c a m 系统( 如：u g 、m a s t e r c a m 、s m a r t - c a m 等) ，做刀 具路径设定，产生数控代码，由c n c 机床将实体加工出来。s t l 数据经曲面断层处 理后，直接由激光快速成型方式将实体制作出来。 图1 1 逆向工程体系结构图 第1 章绪论 图l 一2 ( a ) 数抛采集改备的分类：( b ) c y b e r w a r e 公司制造的激光扫描仪： ( c ) 接触式探头：( d ) 有计算机控制的坐标测缱机【2 i 随着计算机技术和测量技术的进步，逆向工程技术在许多工业领域中有着 广泛的应用。例如在仿型设计中，需要克隆某个产品，然而通常却没有该产品 的原始设计草案或文档，又如在零件的改良设计中，需要从现存的产品出发， 构造出它的几何模型，从而可以利用现有的c a d 系统进行进一步的分析与优 化，开发出新产品，此外在汽车飞机制造业、玩具业、游戏业、艺术业、医学 工程及产品造型设计等领域也得到广泛应用1 3 】o 1 2 曲线重建技术 曲线重建指从已知的采样点集拟合出一条或多条曲线，反映出该点集的形状和 走向。它在逆向工程、计算机视觉等方面都有广泛的应用。曲线拟合面临两个关键 问题。一个问题是拟合曲线的表示形式，虽然在c a g d 中自由曲线有许多不同的数学 模型，但人们通常采用具有良好分析和计算性质的多项式参数曲线，如b 样条曲线： 另一个问题是拟合误差的定义，用几何距离定义误差是最优的，但难以解析表示， 所以通常采用近似几何距离或代数距离来定义拟合误差。同时对参数曲线模型还有 一个重要问题是参数化问题。参数化方法可分为两种：一种是固定参数化方法，简 单但自适应程度不高，不能对所有的情况都获得较好的参数化；另外一种是动态参 数化，在拟合过程中通过算法调整优化参数值，这种方法自适应程度高，但计算耗 赞大。下面根据已知采样点集合的性质对有序离敞点集的曲线拟合和无序离散点集 的曲线拟合进行概述。 福建师范大学郑峰松硕士学位论文 1 2 1 有序点集曲线拟合 基于有序点集的曲线拟合，最早可以追溯到曲线的最小二乘拟合。然而在逆向 工程中，对有序点进行曲线拟合，要求得到的重建曲线能够反映出原始点集的形状 与特征。许多的研究者针对有序数据点的保形曲线拟合做出了许多有益的研究。 1 9 7 5 年，齐东旭等【4 l 提出了样条拟合的盈亏修正思想。2 0 0 3 年，蔺宏伟【5 】基于盈 亏修正的思想，提出迭代非均匀b s p l i n e e 曲线曲面的算法，其方法优点是无需求解 方程组得到拟合( 插值) 给定点集的曲线曲面。2 0 0 2 年，b o r g e s 6 】基于整体最小二乘 方法，用b 样条曲线和贝齐尔曲线拟合有序数据点集。2 0 0 5 年，周明华等f 7 】对利用遗 传算法同时对参数向量和节点向量进行实数编码，使得b 样条拟合误差在最小二乘意 义下最优。并与g a u s s n e w t o n 迭代法、p i e g l 算法对比，具有较好的鲁棒性( 拟合曲 线与初始值无关) 、较高的精度及控制顶点少等优点。2 0 0 6 年，穆国旺等1 8 】研究了在 给定误差要求下，用最少控制顶点的b 样条曲线拟合测量数据点问题，将节点向量中 的内部节点映射成一个二进制串，并称这个二进制串为染色体，利用遗传算法优化 节点向量。这种方法在一定程度上对节点个数进行自适应选择。但是这种方法无法 克服对节点离散化产生的误差和不能处理重节点情况。肖少拥等人【9 】提出了一种基 于正交神经网络的曲线重建方法，得到的重建曲线在样本点和非样本点处均具有很 高的逼近精度。2 0 0 6 年，h y u n g j u np a r k 1 0 】提出了- - ) t 基于采用支配点进行曲线自适 应细化的b 样条曲线拟合方法，该方法获得的拟合曲线在相同控制顶点个数下偏差比 传统的方法小。 1 2 2 无序点集曲线拟合 由于数据采样方式的不同，有时候得到的采样数据点集没有一定的组织形式， 而是一组无序的离散数据点云，而且由于采样密度足够稠密，无需找到一条曲线通 过所彳的采样点，只需要根据该，气集的分斫i 拟合出一条反映出原始数据点云的形状 与走向的曲线作为其重建曲线。关于无序离散点的曲线重建，近年来逐渐受到人们 的重视。 1 9 9 5 年，f a n g 等人【1 1 】给出了一种基于弹力模型的无序点曲线重建算法，通过模 拟曲线的受力情况，构造一组能量函数，将曲线重建问题转化问题关于能量函数的 极值问题，用有限元方法进行优化求解。 u n 等人【1 2 l 用区间b 样条曲线逼近带状点云，然后抽取中心曲线作为重建曲线。 第1 章绪论 成嫒嫒等人【l 别提出了一种基于自适应遗传算法的无序点云的曲线重构算法。该 算法先把点云分布空间网格化，然后在每个网格中用自适应遗传算法搜索出最能代 表该网格中点集的特征点，然后利用改进的自适应的s i g ( s p h e r e - o f - i n f l u e n c e g r a p h ) 图来对每个特征点进行进一步调整，以便能使得到待重建曲线的型值点，最 后利用测地距离函数来确定型值点的拓扑结构，并利用b 样条函数来重建曲线。 李云夕等人【1 4 】提出了一种基于有向距离场的隐式b 样条曲线重建方法。相对于 显示b 样条曲线重建，隐式b 样条曲线重建无需参数化、容易判断点是否在隐式曲线 上和加入其他形状约束等优点，但是不能和普遍采用参数表示的商用c a d 系统兼容、 不符合工业产品数据交换的s t e p 标准、绘制复杂等缺点。 1 3 曲面重建技术 随着激光测距扫描仪、计算机辅助断层扫描等三维数字扫描设备的快速发展， 使得获取物体表面的点集采样模型变得日趋简单、便宜与准确。从这些表示某一几 何形状的采样点集，重建出其内蕴表示的目标曲面，使得这些点集离该目标曲面在 某种度量意义下偏差最小，这个过程称为曲面重建。曲面重建被广泛应用于计算机 辅助几何设计、计算机图形学、医学图像处理、计算机视觉等众多领域。曲面重建 算法很多，下文仅从四边域曲面重建、三边域曲面重建、细分曲面重建和层次模型 曲面重建四个方面进行概述。 1 3 1 四边域曲面重建 以b 样条曲面和n u r b s 等为代表的基于四边域曲面的几何重构方法是曲面重 建中常用的方法。其中b 样条是n u r b s 的一个子集，因此n u r b s 比b 样条灵活性 亚大，其具有在形状定义方面的强大功能和在设计方面的巨大潜在灵活性。n u r b s 理论基础与目前大多数c a d c a 卜1 系统相同，容易直接融入现有的c a d c a m 系统中。 但它也有其自身的缺点，比如，比一般的曲面定义方法更费存储空间和处理时间， 权因子如果选择不当会造成形状畸变等，因此在曲面重建中b 样条的使用更为普遍。 在c a d 中，从点云中重建出被测物体表面的三角网格模型后，更重要的是如何 将三角网格模型转换为用b 样条表示的曲面。为了用b 样条曲面拟合一张有四条边 福建师范大学郑峰松硕士学位论文 界的三角网格模型，首先需要将这张三角网格曲面参数化到单位正方形的参数域中。 很多学者对三角网格的参数化进行研究。1 9 9 5 年，e c k f l 5 l 将三角网格中的每条边看 作一个弹簧，先将三角网格的边界映射到预先定义好的多边形上，然后通过最小化 三角网格的弹性势能来参数化内部三角网格点。1 9 9 7 年，f l o a t e r l l 6 】首先将一个开的 三角网格的边界点根据弦长比例映射到一个平面凸多边形上，将三角网格的每个一 个内点表示成它的邻接点的凸组合，得到一个线性方程组，然后解这个线性方程组 得到所有内点的参数值。这种方法保证参数化的结果为一一映射，对于不同网格曲 面的参数化变形情况比较稳定，但由于采用固定边界参数化，适合于参数具有规则 边界形状的三角网格。2 0 0 3 年，f l o a t e r 【r 7 】研究了通过计算定义于三角网格上的调和 场来得到三角网格的参数化，给出了一种中值坐标方法，在一类凸线性组合映射中， 寻找一个逼近调和映射的映射，但是这种近似调和场并不收敛于真正的调和场。同 年，蔺宏伟【5 】提出了一种新颖的三角网格参数化方法基于温度场的三角网格参 数化技术，通过解一个三维调和方程，得到定义于三角网格曲面上的稳定温度场， 从而将这个三角网格曲面参数化到单位正方形的参数域中。 另外，为了直接拟合点云，许多学者还研究了对点云的参数化。在拟合中广泛 应用的参数化方法是由m a 和k r u t h 提出的基于投影的方法，即对于一个给定的点 云，首先确定一张初始基曲面，然后将点云中的点投影到这张基曲面上，把投影点 在初始基曲面上的参数值作为点云中相应点的初始参数值。然后，按照次初始参数 值拟合点云，得到一张新的基曲面，再重新投影得到新的参数值，重复这个过程， 直到满足一定的精度为止。这个方法简单易行，在某些情况下很有效，但是也存在 着严重的局限性。第一，初始基曲面的选取比较困难，会影响参数化结果；第二， 点云中两个不同的点有可能投影到基曲面上同一个点，使得两个不同的数据对应于 同一个参数值；第三，这个迭代过程的收敛性得不到保证【5 】。2 0 0 4 年，孙玉文等【1 8 j 提出利用蒙皮技术构造基面，然后采用数据点在基面投影参数化方法：( 1 ) 将基面 划分成等参数线网格，得到每个网格点的坐标值和对应的参数值；( 2 ) 对给定的某 一个数据点，找到距离其最近的网格点，并以该节点的参数值作为这个数据点的迭 代初始值；( 3 ) 利用牛顿迭代法，从这个初始值出发，计算到这个数据点距离最小 的基面上投影点，该投影点的参数值，做为这个数据点的参数化结果。最后采用加 权最小二乘算法，实现b 样条曲面的迭代拟合。这种方法一定程度上克服m a 和k r u t h 的方法缺陷，但是参数线网格的分辨率是人为确定，有一定的局限性。 第1 章绪论 此外，朱东波等人i ”】应用h a r d y s 双二次局部插值得到的网格化数据点取代点 云作为最d 、- - - - 乘b 样条曲面拟合的数据点。这样处理避免了直接对点云进行拟合， 显著减少了拟合数据量。s e o k 等【2 0 】研究了用n u r b s 曲面去拟合旋转曲面。第一步， 将原来的点云数据转化到正交坐标系统中：第二步，用b 样条曲面去拟合转化后的数 据；第三步，用b 样条f ( u ，v ) 转化后的数据：第三步，构造一个n u r b s 基球面b ( u ，v ) 与f ( u ，v ) 进行符号乘积操作，将f ( u ，v ) 转化为n u r b s 曲面。这种方法优点是它提供一 种自然的参数化方法，能从表示旋转曲面的点云数据中精确还原出n u r b s 曲面和简 单点关系分类。施云惠等人【2 1 】在再生核空间w 上构造一种新型的神经网络及相应的 学习算n e w t o n - - b p 交替算法，进而给出神经网络的自由曲面重构算法。与传统方法 相比，神经网络方法具有很强的灵活性。但是容易陷入局部极小的致命缺点，收敛 速度慢的缺点。 1 3 2 三边域曲面重建 三角曲面拟合目1 j i f 主要有三边b e z i e r 曲面法。由邱泽阳等人i 冽提出在三角形网 格的基础上用三角曲面片( 三角b 6 z i e r 曲面片) 对原始曲面进行稃逼近此算法对平 缓变化的曲面，逼进效果极佳但是在曲面的尖锐变化部分，逼进效果则不理想。 林芳等人团l 针对尖锐变化的曲面，提出了一种基于三角b z i e r 曲面的曲面重构方 法先将数据点进行分组，使每个分片曲面相对平缓对于包含有特殊点如“尖点 、 “拐点”( 曲面凹凸发生改变的点) ，可选定这些点为边界角点，并相邻两片共用此 边界角点，使选择的角点近可能的为正三角形。该方法使生成的曲面具有较好的光 顺性。三角形域曲面由于构造灵活、边界适应性好的特点，一直是研究者关注的焦 点。它的优点有概念简单、数据压缩量大并在自适应曲面逼近的过程中不需要对整 个曲面进行重构，而只改变有关区域，所以速度快。缺点在于所构造的曲面模型不 符合产品描述标准，与现有的c a d c a m 软件系统接口很难。并且这种方法生成的三 角网格数目一般都很庞大，需要用专门的算法对网格进行简化处理，所以该类方法 在国内、外的有关反求工程的c a d c a m 软件中都较少采用。 福建师范大学郑峰松硕士学位论文 1 3 3 细分曲面重建 虽然n u r b s 以被作为工业产品数据交换的s t e p 标准，是描述工业几何形状的唯一 数学方法，但是单一的n u r b s 曲面不能表达任意拓扑结构的曲面，其拓扑局限性使得 在逆向重建复杂自由曲面的过程中面临很大的难关。采用先分片再拟合的方法虽然 可以构造出自由曲面，但很难达到理想的效果，曲面在接缝处保持光滑即使近似的 光滑也很困难，并且剪裁要花费大量的时间和资源；基于三角域的b 6 z i e r 曲面重建 声称比四边域曲面具有更宽松的拓扑要求和更好的边界适应性，但它仍然不具有任 意拓扑性。与n u r b s 一样，作为一种参数曲面，它在剪裁、拼接的时候同样很困难， 接缝处的过渡区域也很难实现平滑。细分曲面可以轻易解决以上困难。细分曲面是 通过用低分辨率的控制网格和定义在控制网格上的细分规则来表示光滑曲面的。细 分曲面由控制网格开始，因此具有多边形建模技术的任意拓扑性：在极限时，控制 网格收敛于一张光滑曲面且一般自动满足切平面连续，因此又具有连续曲面的性质： 与n u r b s 相似，细分曲面的每个顶点只是有限相邻点的线性组合，故还具有局部控制 性。李登耐2 4 】提出一种用于构造给定三维模型的拟合l o o p 细分曲面的迭代优化算法， 使得拟合曲面与原始模型之间的逼近误差最小。算法中的逼近误差定义为原始模型 各面元到拟合曲面最小距离的积分。与l o o p 细分小波分解算法的比较表明，该算法 以适度的运行时间代价得到了更优的结果。此外，该算法还可以加以推广，作为一 类从输入模型生成其近似表示的优化算法的基础。细分曲面与传统的连续造型曲面 相比，大有后来居上之势，但是它是一种网格细分为特征的离散造型曲面，不属于 工业产品数据交换的标准，主要用于特征动画和雕塑曲面的设计。 1 3 4 层次模型曲面重建 用张量积b 样条曲面拟合具有丰富细节的复杂几何模型，传统上利用插入节点 进行局部修改。但是对张量积b 样条曲面，节点插入不是局部的过程。插入一个节 点向量，相应的要加入一整行和一整列的控制顶点往往造成冗余，从而导致处理的 数据量大大增加，降低了效率。为了解决这个问题国内外学者利用多分辨率技术在 不用细节层次上去数据进行处理。1 9 9 5 年，f o r s e y 和b a r t e l s 2 5 】提出了用一种层次b 第1 章绪论 样条的方法来进行曲面拟合和曲面编辑，这种方法能提供很好的连续性，并且具有 修改方便的优点。该算法使用了一个层次次结构的控制点网格，一步一步地从一个 较粗糙的网格到一个较精细的网格来提高逼近的精度，但是它的应用仅限于规则网 格。1 9 9 7 年，s e u n g y o n gl e e 等人1 2 6 】从图像变形技术出发，提出了散乱数据的多层 次b 样条插值方法。该方法对给定的一组散乱数据，通过求解一个不定方程的伪逆 矩阵来求解一组控制点，再通过最小二乘法来最终得到控制网格该算法实现起来 非常简单、但它的这些优点部分来自于它处理的点集的规模小，由于不加选择的细 化，处理时间上远远不能满足需要。1 9 9 9 年张伟强和唐泽圣 2 7 1 在s e u n g y o n gl e e 等 人的多层次b 样条插值算法以及f o r s e y 等人的层次b 样条曲面拟合算法的基础上， 用一种自适的算法自动对某些需要细化的区域进行细化，这样大大减少计算量，提 高计算效率。m a r t i nb e r t r a m 2 8 1 利用基于四叉树聚类的方法划分数据点集，在该层的 每个聚类用双线性或双二次贝齐尔张量曲面进行拟合，通过节点去除构成该层次一 个的b 样条曲面。然后通过该b 样条曲面计算每个聚类内的点拟合最大误差，如果 某个聚类拟合大于给定的误差，则对该聚类进行一次划分，进入下一层次剩余误差 进行拟合。这样不断进行下去，直到某一层的每个聚类的最大误差满足给定的误差 为止。2 0 0 6 年，童伟华等人【2 9 j 研究了用层次隐式张量积b 样条曲面对无结构散乱点 数据进行曲面重建，该方法相对显式张量b 样条曲面重建，其优点是无需要对散乱 点集参数化，缺点是不能进行后继的交互修改。 1 4 遗传算法简介i 粥3 l 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局 优化概率搜索算法。它最早山英国密切安大学的h o l l a n d 教授提出，起源于6 0 年代 对自然和人工自适应系统的研究。遗传算法有效性的理论依据为模式定理和积木块 假设。模式定理保证了较优的模式的样本里指数级增长，从而满足了寻找最优解的 必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗 传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式在 遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，。最终生成 全局最优解。近十年来，遗传算法得到迅速发展。目前，遗传算法在计算机辅助设 计、数据分析、动态处理、建模与模拟、机器人学、图像处理、函数优化、组合优 福建师范大学郑峰松硕士学位论文 化、自动控制、遗传编程、数据挖掘、信息战等领域都得到应用，成为求解全局优 化问题的有力工具之一。 1 4 1 遗传算法的发展 2 0 世纪6 0 年代，j o h nh o l l a n d 教授和他的数位博士受其生物模拟技术的启发， 认识到自然遗传可以转化人工遗传算法。1 9 6 2 年j o h nh o l l a n d 提出了利用种群体、 适应值、选择、变异、交叉等基本概念。1 9 6 7 年，h o l l a n d 的学生j d b a g e l y 在其 博士论文中首次提出了“遗传算法 的一词，他发展了复制、交叉、变异、显性、 到位等遗传算子，在个体编码上使用了双倍体的编码方法。h o l l a n d 教授用遗传算法 的思恕对自然和人工白适应系统进行了研究，提出了遗传算法的基本定理模式 定理，并于1 9 7 5 年出版了第一本系统论述遗传算法和人工自适应系统的专著 a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) 。同年，d ej o n g 基于遗传算法的思想 在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上， 1 9 8 9 年，g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架。1 9 9 1 年，d a v i s 介 绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1 9 9 2 年，k o z a 将遗 传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程( g e n e t i c p r o g r a m m i n g ，简称g p ) 的概念。在控制系统的离线设计方面，c u s i n 等人证明了使 用遗传算法在太空应用中导出优异的控制器结构比使用传统方法所用的时间更少。 遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起 国内外学者的高度重视。 1 4 2 基本遗传算法概要 基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计 了许多不同的编码方法来表示可行解，开发出了许多种不同的遗传算子来模仿不同 环境下的生物遗传特性。这样，有不同的编码方法和不同的遗传算子就构成各种不 同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中 选择、交叉、变异机制的模拟，来完成对问题最优解的自适应搜索过程。基于这些 共同的特点，g o l d b e r g 总结出了一种统一的最基本的遗传算法基本遗传算法 第1 章绪论 ( s i m p l eg e n e t i c a l g o r i t h m s ，简称s g a ) ，是其他一些遗传算法的雏形和基础。