基于特征性质的三次B样条拟合算法

基于特征性质的三次B样条拟合算法

姓名：陈露申请学位级别：硕士专业：计算数学指导教师：罗钟铉

20090623

大连理工大学硕士学位论文摘要应用测量得到的数据来重构曲线曲面模型，是逆向工程的核心工作。将测量数据进行重构，可以消除测量带来的误差，使模型具有更好的性质。通常，处理曲面上大量数据点的方法是先进行曲线拟合，再进行曲面重构。因此，本文将重点讨论曲线拟合的问题，并在此基础上，给出相应的曲面重构方法。通过对传统方法的考察，我们采用三次Ｂ样条进行模型拟合，考虑从几何特征点出发，通过特征点确定节点分布及其参数，在反求控制点的过程里，我们选用稳定性更好，适应性及可控性更强的能量最小化方法，得到拟合曲线的控制点，进而得到初始拟合曲线，最后，以满足误差精度为前提，不断的添加或删除控制点使样条曲线的组合段数尽量的少，以符合实际加工的要求。通过与最小二乘ＤＰ法以及等距包络法的比较，本文方法在保证精度的前提下具有较少的分段数，在控制点数固定的前提下拟合误差较小。在曲线拟合算法的基础上，本文以同样的思想，提出基于截面特征的曲面重构方法。将数据点集切片获取截面曲线，并基于曲线的几何特征，建立截面曲线特征点对应模型，以曲线特征匹配准则优化对应，逐步建立截面曲线的对应关系并映射为参数对应，进而可以采用成熟的算法进行曲面重构。关键词：三次Ｂ样条；拟合；重构；特征点；相容基于特征性质的三次Ｂ样条拟合算法ＣｕｂｉｃＢ—ｓｐｌｉｎｅＦｉｔｔｉｎｇＭｅｔｈｏｄＢａｓｅｄｏｎＤｏｍｉｎａｎｔＩｎｆｏｒｍａｔｉｏｎＡｂｓｔｒａｃｔＲｅｃｏｎｓｔｒｕｃｔｉｏｎｏｆｃｕｒｖｅｓａｎｄｓｕｒｆａｃｅｓｗｉｔｈｍｅａｓｕｒｅｄｄａｔａｉｓｔｈｅＣＯｎｗｏｒｋｏｆｒｅｖｅｒｓｅｅｎｇｉｎｅｅｒｉｎｇ．１１１ｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎｕｓｉｎｇｍｅａｓｕｒｅｄｄａｔａｗｉｌｌｍａｋｅｔｈｅｍｏｄｅｌｉｎｇｂｅＲｅｒ．Ｕｓｕａｌｌｙ，ｔｈｅｃｕｒｖｅｆｉｒｉｎｇｉｓｔｈｅｆｉｒｓｔｓｔｅｐａｎｄｔｈｅｎｃｌｌＹｖｅｓｕｒｆａｃｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｃａｌｌｂｅｏｂｔａｉｎｅｄ．ｎｅｐｏ缺０ｆａｔｈｉｓｐａｐｅｒｉｓｆｉｔｔｉｎｇａｎｄｓｕｒｆａｃｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎ．ｕｓｅＢｙｒｅｓｅａｒｃｈｉｎｇｔｈｅｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄｓ，ｗｅＣｕｂｉｃＢ—ｓｐｌｉｎｅｔｏｆｉｔｓｅｔｏｆｏｒｄｅｒｅｄｄａｔａ．ｎｅｋｎｏｔｐｌａｃｅｍｅｎｔｉｓｄｅｔｅｒｍｉｎｅｄｂｙａｖｅｒａｇｉｎｇｔｈｅｐａｒａｍｅｔｅｒｖａｌｕｅｓｏｆｔｈｅｄｏｍｉｎａｎｔｐｏｉｎｔｓ，ａｌｌｃｕｒｖｅｗｈｉｃｈｐｌａｙｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｐｒｏｄｕｃｉｎｇｂｅＲｅｒｃｕｒｖｅａｐｐｒｏｘｉｍａｔｉｏｎ．乃岔ｒｅｓｕｌｔｉｎｇｅｒｒｏｒ－ｂｏｕｎｄｅｄｗｉｔｈｆｅｗｅｒｃｏｎｔｒｏｌｐｏｉｎｔｓｂａｓｅｄｏｎｅｎｅｒｇｙｍｉｎｉｍｉｚａｔｉｏｎ．Ｉｎｓｕｒｆａｃｅｉｓｃｏｎｓｔｒｕｃｔｉｏｎ，ｏｎｅＭｇｏｆｉｔｈｒｎｂａｓｅｄｏｎｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｉｓａｌｓｏｃｏｎｓｉｄｅｒｅｄ，ｗｈｉｃｈｃｏｎｓｔｉｔｕｔｅｓｔｈｅｍａｐｐｉｎｇｏｆｃｈａｒａｃｔｅｒｉｓｔｉｃｓａｎｄｔｒａｎｓｆｅｒｉｔｔｏｔｈｅｍａｐｐｉｎｇｏｆｐａｒａｍｅｔｅｒ．ＢｙｕｓｉｎｇＯｕｒｍｅｔｈｏｄ。ｗｅｃａｌｌｇｅｎｅｒａｔｅａＢ．ｓｐｌｉｎｅｓｅｔａｌｓｏｃｕｒｖｅｏｒｓｕｒｆａｃｅｗｉｔｈｌｅｓｓｄｅｖｉａｔｉｏｎａｎｄｔｈｅｏｕｒｄｏｍｉｎａｎｔａｐｐｒｏａｃｈｉｎｆｏｒｍａｔｉｏｎｏｆｔｈｅｄａｔａｕｓｅｆｕｌｎｅｓｓａｎｄｑｕａｌｉｔｙ．ａｐｐｅａｒｓ．ＳｏｍｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅＫｅｙＷｏｒｄｓ：ＣｕｂｉｃＢ－ｓｐｌｉｎｅ；Ｆｉｔｔｉｎｇ；Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ；Ｄｏｍｉｎａｎｔｐｏｉｎｔｓ；Ｃｏｍｐａｔｉｂｉｌｉｔｙ—ＩＩ—大连理工大学学位论文独创性声明作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：茎童堑三至！些墅翌三垄垦登笙丝坌茎ｉ圣日期：—２竺乙年—互月二竺日作者签名：］堑篮大连理工大学硕士学位论文大连理工大学学位论文版权使用授权书本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或扫描等复制手段保存和汇编本学位论文。学位论文题目：作者签名：导师签名：日期：竺互年—Ｌ月生日日期：．翌￡年—Ｌ月三Ｌ日大连理工大学硕士学位论文１绪论本章阐述本文所涉及的理论及研究背景，综述与之相关的研究成果，简要介绍本文的意义、方法、结论以及主要的结构安排。１．１逆向工程随着计算机技术的发展，ＣＡＤ技术已经成为产品设计人员进行研究开发的重要工具，其中的三维造型技术已经被制造业广泛应用于产品以及模具设计、方案审评、自动化加工制造及管理维护等各个方面。在实际开发制造过程中，设计人员接收的技术资料可能是各种数据类型的二维或三维模型，但很多时候，却是从上游厂家得到产品的实物模型。设计人员需要通过一定的途径，将这些实物信息转化为数字化信息，这就应用到了逆向工程技术。逆向工程（ｒｅｖｅｒｓｅｅｎｇｉｎｅｅｒｉｎｇ），也称反向工程、反求工程，是在没有产品原始图样、文档或者ＣＡＤ模型数据的情况下，通过对已有实物的工程分析和测量，得到重新制造产品所需的几何模型、物理和材料特性数据，从而复制出已有产品的过程ｎ３。一般来讲，逆向工程技术包括形状反求、工艺反求和材料反求等几个方面，在工业领域的实际应用中，主要包括以下几个内容：（１）新零件的设计，主要应用于产品的改形或仿形设计；（２）已有零件的复制，再现原产品的设计意图；（３）损坏或磨损零件的还原；（４）数字化模型的检测，例如检验产品的变形分析、焊接质量等。逆向工程的实施步骤如图１．１所示：图１．１逆向工程的具体步骤Ｆ噜１．ＩＭａｉｎｓｔｅｐｓｏｆｒｅｖｅｒｓｅｅｎｇｉｎｅｅｒｉｎｇ可以看出，逆向工程技术的整个操作过程，可以一’手为如下几个部分：基于特征性质的三次Ｂ样条拟合算法（１）物件数据化：目前常见的采集三坐标的数字化技术有三种Ｈ１，分别是：①接触式测量法，包括手动方法、三坐标测量机中的触摸式测量方法、超声波法等。②非接触式测量方法，如光栅投影法、激光扫描测量法中的激光三角形法等。③逐层扫描测量方法，如工业ＥＴ（ＩｎｄｕｓｔｒｉａｌＣｕｔｔｉｎｇＣｏｍｐｕｔｅｄＴｏｍｏｇｒａｐｈｙ）、层去图像法（Ｌａｙｅｒ—ＬａｙｅｒＩｍａｇｅ）法等。（２）对数据进行处理，从采集的数据中分析物件的几何特征：依据数据的属性，进行分割、再采用几何特征和识别方法来分析物件的设计和加工特征。（３）物件的三维模型重建：针对不同的数据信息，利用不同的方法或软件，得出实物的三维模型，并对模型进行校验和修正。不难看出，应用测量得到的数据来重构曲线曲面模型，是逆向工程的几个核心工作之一，将测量数据进行重构，可以消除测量带来的误差，使所构建模型与实物具有更好的拟合度。通常，处理曲面上大量数据点的方法是先进行曲线拟合，再在此基础上进行曲面重构。因此，本文将先讨论曲线拟合的问题，在此基础上，进一步给出相应的曲面重构方法。１．２研究背景及现状１．２．１研究背景作为我们研究工作的主要内容，曲线曲面重构，是逆向工程中的一个核心步骤，也是学者们所研究的重要问题。近年来，随着计算机辅助几何设计和图形学的发展以及计算机技术的广泛应用，以曲线、曲面重构为代表的逆向工程技术，无论在理论还是应用上都取得了巨大的成功，其应用范围几乎涉及了自然科学和工程技术的一切领域¨３，包括汽车、飞机、轮船外形设计与制造等工业领域，化学分子模型构造领域，基于地震勘探数据或测井数据的地质勘探领域，以及需要大量数据计算和对计算结果进行分析的气象领域，需要实现形体的网格划分及结果数据显示、优化的有限元分析，以及根据测量数据建立人体骨骼和器官的计算机模型的医学和定制生产领域，地形地貌描述、军事作战模拟、动画制作和多媒体技术等领域哺３。在数学科学的背景下，该问题可以描述为：对未知或已知的曲线或曲面，通过采样得到一组采样数据点，从这组数据点出发，构造出相应的曲线或曲面，使得得到的曲线或曲面尽可能的逼近原始曲线或曲面，即误差尽可能的小。大连理工大学硕士学位论文１．２．２现有的曲线拟合方法由已知的采样点集拟合出一条或多条曲线，反映出该点集的形状和走向，即曲线拟合问题。曲线拟合问题在逆向工程和计算机视觉中有着广泛的应用。传统的曲线曲面重构方法，是按照点一线一面的重建顺序来获待重建图形的ｎ幻。根据已知采样点集的性质可以将曲线拟合的方法分为有序离散点集的曲线拟合和无序散乱点集的曲线拟合：（１）有序离散点集的曲线拟合是指给出依次采样于某条曲线上的一系列采样点，如何构造出一条曲线依次通过或近似通过这些采样点，作为原曲线的逼近，要求得到的拟合曲线能够反映出原始点集的形状和特征。基于加工效率的考虑，总是要求在给定的误差精度下所得到的拟合曲线具有比较少的组合段数，即比较少的控制点数，而最少能用多少控制点构造一条样条曲线才能满足误差要求，是目前学者们所关注的问题。实际上，通过解一个非线性的优化问题，可以得到较少的控制点数目，但并不能确保是最小值ｎ３，并且算法的运行时间长，效率低，不宜应用在工程中。从目前的研究情况看，针对有序数据点，常见的方法可分为两种：①由一个小数目的控制点数出发获得初始拟合曲线，通过检查拟合曲线对数据点的偏差来增加控制点数目，经过数次迭代得到指定误差精度内的拟合曲线：如１９９９年，Ｓａｕｘ和Ｄａｎｉｅｌｕ引，２００５年Ｌｉ呦１等提出的方法，都是按照此步骤进行的；②由一个大数目的控制点数出发得到初始曲线，根据误差要求，通过迭代删除相应的控制点实现逼近：如１９８７年Ｌｙｃｈｅ和Ｍ矽ｒｋｅｎ㈨，１９９５年Ｅｃｋ和Ｈａｄｅｎｆｅｌｄ滔１所提出的方法。上世纪八十年代，Ｆｒｉｔｓｃｈ和Ｃｌａｒｓｏｎ，Ｂｕｔｌａｎｄ等人讨论了如何用分段三次益线进行插值曲线拟合ｎ５’１叼，更一般的，Ｐａｓｓｏｗ和Ｒｏｕｌｉｅｒ讨论了如何用多项式样条函数进行有序点曲线拟合的问题ｎ刀。２０００年，Ｉｍｖｅｒｙ在瞻妇论文中给出了一种用三次光滑厶样条多尺度的保形拟合数据点的方法，也有其他研究者讨论了用圆弧样条、双圆弧样条或其他参数样条进行有序点曲线拟合的问题‰铆。若考虑数据点集的几何信息，１９７３年Ｄｏｕｇｌａｓ和Ｐｅｕｃｋｅｒ提出距离约束法，即经典ＤＰ方法阳３；２００３年Ｍａｒｊｉ和Ｓｉｙ提出一种新的特征点检测法汹３；２００４年Ｐａｒｋ提出等距包络法ｎ们。这类方法的拟合效果较好，在实际应用中较受欢迎。（２）无序散乱点的曲线拟合，由于数据采样方式的不同，得到的数据点集没有一定的组织形式，而且由于采样密度不足够稠密，无法也无需找到一条曲线通过所有的采样点，只需根据该点集的分布拟合出一条反映出原始数据点集形状与走向的曲线作为其拟合曲线。解决此类问题的经典方法有：１９９８年，Ｌｅｖｉｎ提出了一种移动最小二乘法（Ｍｏｖｉｎｇｌｅａｓｔ—ｓｑｕａｒｅｓ）进行曲线拟合的方法‰３；２０００年，Ｌｅｅ推广了该方法伫钉，对基于特征性质的三次Ｂ样条拟合算法原始点集进行两次局部最小二乘回归，调整数据点位置，细化点云，得出拟合曲线。另外，还有模型拟合法、骨架法、离散法等。由于本文重点研究有序数据点集的拟合问题，故对于无序离散点集不做过多介绍。通过对传统方法的考察，结合实际加工中的要求，我们要求曲线拟合不仅具有较好的保形性，还要具有组合段数少，加工步长自适应选取等特点，综合考虑以上几点，现有的研究成果仍不够成熟，算法仍需完善。因此，在上述实际问题背景下的有序点集的曲线拟合问题仍然是目前学者们较关心的热点问题。１．２．３现有的曲面重构方法曲面重构是逆向工程中最重要的一个步骤，即构造出物体的几何模型，主要有以Ｂ样条或ＮＵＲＢＳ曲面为基础的曲面构造方案以及以三角Ｂｅｚｉｅｒ曲面为基础的曲面构造方案。本文重点讨论前者。我们可以把用于重构曲面的数据点云分为以下几类，对于不同的数据点，有不同的睦面重构方法：（１）阵列数据，即数据具有行×列的特点。对于此类数据点，人们通常采用张量积的方法把数据点重构问题转化为曲线重构问题。ＢＳａｒｋａｒ和Ｃ卅Ｍｅｎｑ测运用图像处理的原理，获取曲面的特征线，然后根据这些曲线将曲面划分为不同的块，每块用Ｂ样条曲面拟合，最终将所有块拼接成一个整体；ＴａｍａｓＶａｒａｄｙ渤３等提出一种四叉树方法，首先构造一张整体的曲面，若不能满足要求，则将其一分为四，再对每一小块进行相同处理，直至所有小块满足要求为止。（２）按光刀扫描组织的数据，数据点基本上位于同一等截面线上，可认为是部分散乱数据。对于这一类数据点，通常先对数据点进行截面曲线的拟合，然后采用蒙皮法构成重构曲面；（３）完全散乱的、无组织的数据点云。对于此类数据点，若运用Ｂ样条或ＮＵＲＢＳ曲面进行拟合，首先要解决的是单一矩形域内散乱数据点的曲面拟合问题。在众多研究中，ＷｅｉｙｉｎＭａ和Ｊ．Ｐ．Ｋｒｕｔｈｍｌ的工作比较具有代表性，首先根据边界构造出初始曲面，然后将数据点投影到该初始曲面上，接着根据投影位置算出其参数分布（从而解决散乱数据的参数分配问题），根据这一参数分配拟合出一张新的Ｂ样条或ＮＵＲＢＳ曲面后，再通过对数据点参数的优化，使拟合曲面离给定的数据点误差最小。然而，在以Ｂ样条蓝面为基础的曲面构造中，曲线网格的建立、分块等很难自动完成，需要较强的交互参与；曲面构造的精度较难控制，在所介绍的算法中，往往是若不能满足要求，则必须从头开始计算，导致运行效率较低。大连理工大学硕士学位论文１．３本文主要工作针对上述曲线曲面重构问题，通过对传统方法的考察，我们发现，如果能很好的把握数据点所表达出来的几何特征，就能很好的把握拟合曲线。因此，我们考虑从几何特征点（尖点、拐点、曲率最大点等）出发，给出一个简单有效的曲线曲面重构算法。（１）在曲线拟合方面，我们采用三次Ｂ样条进行，通过特征点的选择，确定节点分布及其参数，在反求控制点的过程里，我们选用稳定性更好更容易控制的能量最小化方法，得到拟合曲线的控制点进而得到初始拟合曲线，最后以满足误差精度为前提不断的添加或删除控制点使样条曲线的组合段数尽量的少。通过与最ｔＪ、＿－乘ＤＰ法以及等距包络法的比较，本文方法在保证精度的前提下具有较少的分段数，在控制点数固定的前提下拟合误差较小。（２）在曲面拟合的问题上，以曲线拟合算法为基础，本文以同样的思想，提出基于截面特征的曲面重构方法。将数据点集切片获取截面曲线，并基于曲线的几何特征，建立截面曲线特征点对应模型，以曲线特征匹配准则优化对应，逐步建立截面曲线的对应关系并映射为参数对应，进而可以采用成熟的算法进行曲面重构。１．４本文结构安排本文后续章节安排如下：第２章：介绍Ｂ样条曲线曲面重构的相关基础知识。第３章：研究逆向工程中的曲线拟合问题。通过对传统算法的介绍和研究，提出基于特征点选择和能量最小化方法的曲线拟合算法，给出算法的基本思想、详细内容以及相关的数值试验结果。第４章：在第３章的基础上，研究逆向工程中的曲面重构问题。提出基于截面曲线特征的曲面重构算法，给出算法的基本思想以及详细内容。最后：对全文进行总结，并对今后研究的方向和重点进行分析展望。大连理工大学硕士学位论文２基础知识这一部分，我们对曲线曲面重构问题中，所涉及到的相关概念和内容进行介绍。２．１数据的插值、逼近与拟合插值与拟合都是函数逼近或数值逼近中的重要组成部分。（１）插值插值是函数逼近的重要方法之一，利用它可以通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值，即在离散数据的基础上，补插连续函数，使得这条连续曲线通过全部给定的离散数据点。早在６世纪，中国的刘焯己将等距二次插值用于天文计算。１７世纪之后，Ｉ．牛顿，Ｊ．一Ｌ．拉格朗日分别讨论了等距和非等距的一般插值公式。在近代，插值法仍然是数据处理和编制函数表的常用工具，又是数值积分、数值微分、非线性方程求根和微分方程数值解法的重要基础，许多求解计算公式都是以插值为基础导出的。插值问题可以描述为：已知区间［ａ，ｂ】上的实值函数ｆ（ｘ）在区间上忍＋１个互不相同的点Ｘｏ，而，…矗处的值是ｆ（Ｘｏ），厂（而），…，厂（毛），要求估算出厂（功在［口，ｂ］中某一点的函数值。其做法是：在事先选定的一个由简单函数构成的有刀＋１Ｉｆ－参数Ｃｏ，ｃ１，…巳的函数类Ｏ（Ｃｏ，ｃｌｏ厶）中，求出满足条件ｐ（五）＝ｆ（ｘｉ）（净０，１，…，ｎ）的函数ｐ（ｘ），并以ｐ（·）作为厂（·）的估值。此处厂（功称为被插值函数，Ｘｏ，五，…吒称为插值结点，Ｏ（Ｃｏ，ｑ，…巳）称为插值函数类，上面的等式称为插值条件，Ｏ（ｃｏ，Ｇ，…Ｇ）中满足上式的函数称为插值函数，上述的求解问题，即为插值问题。插值的方法有很多，最常见的是多项式插值，包括Ｌａｇｒａｎｇｅ插值多项式和Ｎｅｗｔｏｎ插值多项式等；除此之外，还有Ｈｅｒｍｉｔｅ插值、分段插值、样条插值和三角函数插值等。（２）逼近当数据点太多时，构造插值函数使其通过所有的数据点会相当困难，有时即使能构造出来这样的函数，也会由于函数次数太高或形式复杂而使整个算法的效率降低；在实际应用中，更会遇到找不到解析函数表达式的情况，客观的说，由于数据点过多，测量误差对数据的影响也加大，此时，我们也没有必要寻找一个插值函数精确的通过所有的数据点。因此，我们往往选择一个次数较低的函数，在某种意义上最佳逼近这些数据点。而逼近的问题本质上就是函数的近似表示问题，即在选定的一类函数中寻找某个函数ｐ（ｘ），使它是己知函数ｆ（ｘ）在一定意义下的近似表示，并求出用ｐ（ｘ）近似表示ｆ（ｘ）基于特征性质的三次Ｂ样条拟合算法而产生的误差，这就是函数逼近问题。其中，用来逼近已知函数厂（ｘ）的函数类可以有不同的选择，即使函数类选定了，在该类函数中用作ｆ（ｘ）的近似表示的函数ｐ（ｘ）的确定方式仍然是各式各样的，ｐ（ｘ）对ｆ（ｘ）的近似程度，即误差，也可以有各种不同的含义。所以函数逼近问题的提法具有多样的形式，其内容十分丰富。（３）拟合工业上的拟合，并不是通常数学意义上严格定义的插值和逼近的总称，而是指在曲线曲面的设计过程中，用插值或逼近的方法，得到曲线或曲面达到某种设计要求，诸如在允许范围内贴近原始数据点或控制点即可。通常，我们并不知道所获得的数据点是遵循哪一类函数形式的，只要找到一种形式的函数，使之在某种意义下，与数据点所表达的信息尽可能相符即可。由于实验误差的存在，我们所选择的函数也未必是最合适的，拟合出来的函数一般也难以通过所有的已知数据点，但是只要与原始数据点尽可能的近，从而近似的表示出函数关系，即是合格的拟合曲线。２．２曲线曲面的基本理论嘲在计算几何中，熟知的曲线曲面的表示方法有两种，即参数表示与代数表示。其中参数曲线曲面由于其构造简单、计算容易等特点而流行于世并成为几何设计的主要方法之一。相比于参数曲线曲面，代数曲线曲面同样具有自身的优势，并且成为当今研究的热点问题之一。下面我们就两种定义方法进行介绍。２．２．１曲线曲面的参数表示１曲线的参数表示空间中的一条曲线可以表示为参数ｆ的向量函数ｐ（ｔ）＝（ｘ（ｆ），ｙ（ｆ），ｚ（，）），ｒ∈［口，ｂ］。曲线的这种表达方式称为曲线的参数表示，【ａ，ｂ］称为参数域。给定了一个具体的曲线方程，称之为给定了一个曲线的参数化。显然，同一条曲线的参数化可能是不同的。如果ｐ（ｔｏ）＝（圣（％），夕（％），ｅ（ｔｏ））≠０，称曲线ｐ（ｔ）在ｔ＝％是正则的，点Ｐ（ｔｏ）称为曲线的正则点。由上式，点ｐ（ｔｏ）为正则点的充要条件是文（ｆｏ），夕（ｒｏ），三（岛）不同时为零。若曲线ｐ（ｆ）的所有点都是正则点，就称曲线ｐ（ｆ）为正则曲线。非正则的点称为曲线的奇点。值得注意的是，同一条曲线上的一个点，在某些参数化下为正则点，但是在另外的参数化下可能不是正则点。大连理工大学硕士学位论文如果曲线ｐ（ｔ）的所有分量函数ｘ（ｒ），ｙ（ｆ），ｚ（ｔ）的ｋ阶导数存在且连续，并且曲线ｐ（ｔ）为正则曲线，则称曲线属于Ｃ‘类的。２曲面的参数表示用双变量“，ｖ的向量函数ｐ（ｕ，ｖ）＝（ｘ（ｕ，１，），ｙ（ｕ，１，），ｚ（ｕ，ｖ））所描述的曲面，称为曲面的参数表示。参数Ｕ，ｖ通常的变化区间为ｚｎ，平面上的一个矩形区域“∈‰，Ｕ：】，１，∈【ｖｌ，ｖ２】。给定了曲面的参数方程就给定了曲面的一个参数化，也决定了参数域‰，屹］＠［Ｍ，吃】上的点与曲面上的点的对应关系。显然，曲面的参数化也是不唯一的。如果固定一个参数，例如．矿－－－％，那么ｐ（ｕ，Ｖｏ）为单参数甜的向量函数，它表示曲面上的一条曲线，称为等参线或“曲线。３参数化方法及优势对于拟合曲线或曲面，数据点Ｐｏ，ｐｌ，．一，Ｐ。与其参数域内的节点之间有一种对应关系。对于一组数据点，确定一种参数分割，就称对这组数据点进行参数化。对于一组数据点ｐ。，ｐｌ，．一，Ｐ。参数化的常见方法有以下几种：（１）均匀参数化：使每个节点区间长度△，＝０，－ｔ，＝正常数（ｆ－０，１，…，ｍ－１），节点在参数轴上呈等距分布，０。＝‘＋正常数。（２）累加弦长参数化：ｆ岛＝¨．Ｉｔ＝０ｌ＋Ｉ锄一１ｌ，ｆ＝ｌ，２，…，聊其中，衄＝陬。一只为向前差分矢量，即弦边矢量。这种参数法能如实反映出数据点按弦长分布的情况，能够克服数据点按弦长分布不均匀的情况下采用均匀参数化所出现的问题。（３）向心参数化：』岛２ｏ忙ｔ１ｏ＋Ｉ蛔一。ｆ１，２’ｉ－－－１，，－－－，？Ｙ／由于累加弦长法没有考虑相邻弦边的折拐情况，而向心参数化假设在一段曲线弧上的向心力与曲线切矢从该弧段始端至末端的转角成正比，加上一些简化假设，得到向心参数化法。此法尤其适用于非均匀数据点分布。参数化方法还有很多种，这里我们不一一列举。与非参数曲线曲面相比，参数表示方法有其自身的优点，主要有：一９一基于特征性质的三次Ｂ样条拟合算法（１）易于作图，只需对不同的参数值求其坐标即可；（２）易于规定曲线曲面的范围；（３）易于表达空间曲线；（４）易于推广到高维情形，只需增加分量即可；（５）易于进行仿射变换与投影变换：（６）易于计算，例如利于计算曲线曲面上的点的切向量、曲率等；（７）易于进行曲线曲面的分段描述。２．２．２曲线曲面的代数表示１显式表示曲线曲面的显式代数表示实质上就是多项式曲线曲面。在直角坐标系下，显式表示的代数曲线曲面分别为：Ｙ＝ｆ（ｘ），ｚ＝ｇ（ｘ，Ｙ），其中，ｆ（ｘ）和ｇ（ｘ，Ｙ）是多项式。显式代数曲线曲面表达式非常简单，但是由于他们均为单值函数，因此不能表示复杂的图形。如圆、球等就不能用显式代数的形式表示。显式代数曲线曲面还可以看作一类特殊的参数曲线曲面。２隐式表示在直角坐标系下，隐式代数曲线曲面就是多项式的零点集，即：ｆ（ｘ，Ｙ）＝０，ｇ（ｘ，Ｙ，ｚ）＝０，其中ｆ（ｘ，Ｙ）和ｇ（ｘ，Ｙ，ｚ）是多项式。显然，显式代数曲线曲面是隐式表示的特殊形式。隐式表达式能描述复杂的图形，如圆、球、封闭的曲线曲面、自交的曲线曲面等。在曲线曲面重构中，隐式比显式应用更为广泛。参数蓝线曲面是一定可以隐式化的，但是隐式代数曲线曲面并不一定都可以进行参数化。因此隐式表示比参数表示更为一般，可以描述更为灵活的几何形状。３隐式表示的优势相比于其他表示方法，曲线曲面的隐式表示具有其自身的优点，主要罗列如下：（１）易于计算点与曲线曲面间的关系，例如直接将点带入表达式就可以确定其是否在曲线上；（２）具有几何运算（求和、求差、求交、偏移）的封闭性；（３）能表达复杂的曲线曲面；（４）具有更多的自由度，能提供更多的形状控制手段；大连理工大学硕士学位论文（５）曲线曲面拟合不需要对数据点进行参数化。当然，隐式表示也有其自身的缺点，例如：多分支性、空间曲线不易表示、不易计算等等。２．３Ｂ样条相关知识Ｂ样条基及性质２．３．１Ｂ样条有不同的定义方式，在应用上较简便的Ｂ样条定义是由如下递推公式给出的：给定参数ｆ轴的一个剖分丁：｛‘）：二（‘≤‘小ｉ＝０，±ｌ，…）。用下列的递推方式所确定的函数Ⅳ，，ｐＯ）称为相应于剖分２’的ｐ次，即ｐ＋ｌ阶Ｂ样条基函数：Ｍ，。ｐ）＝１，ｔ∈［ｔｊ’。１）＿，，‘力２ｉ了芎Ｍ川‘Ｄ＋ｉ胪，一ｉ％，川‘吐ｐ＞１＿，，（力２ｉｔ了－ｔ＃Ｍ川（Ｄ＋ｉｔｊ胪＋ｐ，＋一１－ｉｔ％，川（ｆ），ｐ≥１规定一０：Ｏ０上式称为ｄｅＢｏｏｒ－Ｃｏｘ公式，丁称为节点序列或节点向量，ｆ．称为节点。若钿＜‘＝ｆＩ＋１＝…＝０Ｈ＜０，，则称‘，０】，．一，‘＋ｆ－１为丁的，重节点。注意到：（１）当Ｐ＞０时，Ⅳ细（ｆ）由两个ｐ－１次Ｂ样条基通过线性函数组合得到；（２）为计算Ｂ样条基，需要给定节点向量丁和系数Ｐ；（３）Ⅳ油（ｆ）定义在整个实轴上但一般只用到它在其支集上的性质；未必都不相同，所以其长度可以是零。以下列出Ｂ样条基函数的若干重要性质，它们在刻画Ｂ样条曲线曲面的几何特征时很有用。性质１（４）半开区间Ｉｔ，，ｆ，＋，）称为第ｆ节点支撑。因为节点局部支集性每个Ｂ样条基函数只在局部的区间上非零，在实轴其余部分为零，即：Ⅳｆ。，（ｆ）＝０，ｆ仨睛，“胪。）。因此，区间酶，０川）称为Ｍ．，（ｒ）的支集。性质２非负性Ⅳ加（ｆ）≥０，对一切，，Ｐ和ｆ成立。性质３单位分解性∑Ｍ，ｐ（ｆ）＝１，ｊｍｏｆ∈［■，，ｏ，）。以后我们可以看到，正是由于Ｂ样条基函数的良好性质，突破了多项式函数的限制，使样条函数具有了局部可调的性质和简化计算的优点。基于特征性质的三次Ｂ样条拟合算法２．３．２Ｂ样条曲线有刀＋１个空间向量ｂ／（，＝ｏ，．．．，川．虬，，（ｆ）是定义在节点向量Ｔ＝｛岛，‘，．．．ｏｐ－Ｉｏ，＞上的ｐ一１次Ｂ样条基函数，则称ｃｐ）＝∑Ｍ，，◇）ｂ，，（ｏ。≤ｒ≤ｏ。）为相应于节点向量丁的ＪＩＯｐ－１次非均匀的Ｂ样条函数，称ｂｊＵ＝Ｏ，．．．，刀）为控制顶点。因为Ｂ样条基函数的性质，使得Ｂ样条曲线形式具有如下性质：（１）局部性由于Ｂ样条的局部性，ｐ－１次Ｂ样条曲线上参数为ｔ∈Ｉｔ，，０。］的一点Ｃ（ｆ）至多与ｐ个控制顶点有关，与其他控制顶点无关；移动该曲线的第ｆ个控制顶点ｂ．至多影响定义在区间阮，０。】上的那部分区间的形状，对曲线的其余部分不发生影响。（２）连续性Ｃｑ）在ｒ重节点处的连续阶不低于ｐ一１－ｒ，曲线Ｃ（ｆ）的连续阶不低于夕一卜，幺，其中ｋ表示位于区间（ｒ舻。，ｏ，）内的节点的最大重数。（３）凸包性Ｃ０）在区间Ｉｔ，，０，】上的部分位于ｐ个点ｂｉ＿ｍｌ，＇－＇，ｂ，的凸包内，整个曲线则位于各凸包的并集之内。（４）分段参数多项式ｃ（ｔ）在每一区间阮，‘＋，】上都是次数不高于ｐ一１的参数ｒ的多项式。（５）几何不变性Ｂ样条曲线的形状和位置与坐标系的选择无关。（６）仿射不变性对任一仿射变换彳，有彳［ｃ（ｆ）】＿∑Ａ［ｂ，】Ｍ。ｐ（ｆ），ｆ∈［ｏ，，ｏ，），即在仿射变换下，ｃ（ｆ），１０的表达式具有形式不变性。（７）直线保持性和造型灵活性当控制多边形退化为一条直线时，曲线也退化为直线，并且造型灵活，易于控制。大连理工大学硕士学位论文２．３．３Ｂ样条曲面这里，我们着重介绍张量积型的Ｂ样条曲面。给定（珑＋ｐ）×（以＋ｇ）个空间向量ｂｆ。ｆ（ｉ＂－－－ｐ，一ｐ＋１，…，ｍ一１；／＝－ｑ，－ｑ＋１，…刀一１），Ｍ。，＠）和Ｍ灯（１，）分别为定义在节点向量ｕ－－｛Ｕ＿ｐ，虬川，…，“衙＋ｐ）和矿＝｛ｖ－ｇ，ｖ－ｐｌ，…，ｋｇ｝上的一元Ｐ次和口次Ｂ样条基函数，则与其相应的张量积曲面：ｍ－Ｉｎ－１Ｃ（ｕ，１，）＝∑∑Ｍ．户（“）％（１，）ｂｕ，沁ｖ）∈‰‰】×［ｖ０以】ｉ＝－ｐＪ＝ｔ—ｑ称为一个ｐｘｑ次Ｂ样条曲面。ｂ，，称为控制顶点，依次用直线段连接同行同列相邻两个控制点所得的折线网格称为控制网格。张量积型的Ｂ样条曲面与Ｂ样条曲线具有相似的性质：局部性、连续性、凸包性、几何不变性和仿射不变性等等，这些性质与Ｂ样条越线类似，使得Ｂ样条曲面同样具有很广泛的应用范围和很高的实际应用价值，这里不再重述。大连理工大学硕士学位论文３基于特征点的曲线拟合通过对传统方法的研究，我们发现，如果能很好的把握数据点集所表达出来的几何信息，就能很好的把握拟合曲线。所以，我们考虑从几何特征点出发，通过特征点确定节点分布及其参数，在反求控制点的过程里，我们选用稳定性更好，可控性更强的能量最小化方法，得到拟合曲线的控制点，进而得到初始拟合曲线，最后，以满足误差精度为前提，不断的添加或删除控制点使样条曲线的组合段数尽量的少。通过与最小二乘ＤＰ法以及等距包络法的比较，本文方法在保证精度的前提下具有较少的分段数，在控制点数固定的前提下拟合误差较小。３．１问题描述给定一组数据点ｐ，（江Ｏ，．．．，历）及容许误差ｓ，找到一条Ｐ阶（ｐ－１次）Ｂ样条曲线．ｋＣ（ｔ）２艺Ｍ。，（ｆ）ｂ／，（０１≤ｆ≤０１），ｊ＝Ｏ使得：勰ｌｌｃ（ｔ）一Ｐｊｌ｜＜占，其中ｂ／（，＝ｏ，…，，ｚ）是控制点，ⅣＪ，，（ｆ）是定义在节点向量Ｔ＝｛ｔｏ，ｔ１，．．．ｏ旷，，ｏｐ）上的ｐ阶Ｂ样条基，‘是ｐ，的参数值，要求Ｃ（ｆ）的控制点尽量少。３．２传统算法３．２．１运用最／ｊ、＿－乘的ＤＰ算法该方法由Ｄｏｕｇｌａｓ和Ｐｅｕｃｋｅｒ等提出隋１，是从图像处理中借鉴而来的，该方法从曲线的整体出发，是一种全局的曲线拟合方法，算法通过多次递归的方法来选择关键点，进而较好的把握数据点集的信息，其基本思想如下：（１）设给定点序ＹＵｐ∥＝０，．．．，ｍ），连接首末点ＰｏＰ。，计算其余各点ｐ，到连线ｐｏＰｍ的代数距离，选取其中距离最大的点Ｐ，。若ｄ（ｐ，）≤占，则删除ｐ。Ｐ。内全部内点，否则保留Ｐ，并将点列分为ｐ。Ｐ，和ｐ，Ｐ册段，重复上述步骤；如图３．１；（２）设ｄｓＵ＝Ｏ，．．．，力）是由第一步得到的特征点，令初始控制点数为刀＋１，若样条曲线的次数为Ｐ一１，则样条结点个数为咒＋ｐ＋ｌ，运用最小二乘法反求其控制顶点得到初始曲线，通过判断误差要求添加或删除控制点以达到控制点尽量少的目的。基于特征性质的三次Ｂ样条拟合算法该算法思想简单，易于理解，并且当数据点数目较少，容许误差较小时，运算速度很快，拟合效果很好，但是容易忽略一些局部极小值点使得所得曲线出现扭曲现象，在误差精度较高时，分段太多导致运算效率降低；误差要求较低时。图３．１Ｆｉｇ．３．１ＤＰ法的关键点检测ｋｅｙｐｏｉｎｔｓｉｎＤＰｍｅｔｈｏｄＳｅｌｅｃｔｔｈｅ３．２．２等距包络法该方法又称ＯｆｆｓｅｔＥｎｖｅｌｏｐｅ法，是由Ｐａｒｋ于２００４年提出的ｎ引，该方法以等距包络关键点检测法为主要部分，具有较强的自适应性，具体分为两步：（１）对给定的点序列ｐ∥＝Ｏ，．．．，ｍ），连接首末点ＰｏＰ。，以容许误差占为宽度分别做连线ｐ。Ｐ。的上下等距线ｐｏ．ｐ。．和ｐ。．Ｐ，．，其中Ｐｏ．与ｐｏ．是ｐ。的上下等距点，Ｐ。．与Ｐ朋．是Ｐ。的上下等距点，分别以ＰｏＰ。．，ｐ。．ｐ瘸．为直径，以ｐ。，Ｐ。为圆心作半圆，称ｐ。．Ｐ，．、Ｐｏ＇Ｐｏ．、；。．ｐ：、Ｐｏ＂ｐ研．为ｐ。Ｐ，的等距包络，如图３．２所示。若ｐ。Ｐ。内所有点ｐ∥＝０９ｏ．·９ｍ）到该等距包络的距离都满足：ｄ（ｐ，）≤８，则保留Ｐ。，Ｐ。点，删除其余所有点，否则添加新的分段点：Ｐ々＝［（ｐ。＋ｐ。）／２］（［．】表示向左取整），将点列分成两段。重复上述步骤；（２）定义弦长上界△唧为：（１／４）△嘴＋（３／４）△一，其中△哪，厶嘣分别为每一分段直线长度的平均值和最大值，比较每一分段直线长度Ｉｐ，Ｐ州Ｉ与△聊的值，若小于△唧，则添加新的分段点：Ｐ。＝［（ｐ。＋ｐ研）／２］，重复上述步骤直到所有的分段直线长度小于△叨。第二部分类似于ＤＰ算法，但要求添加的控制点满足相应的曲率及弦长信息。这个问题对于最小二乘ＤＰ方法的不足，仍然不能完全解决，扭曲现象还是会出现。大连理工大学硕士学位论文图３．２线段的等距包络示意图Ｆｉｇ．３．２ＯｆｆｓｅｔＥｎｖｅｌｏｐｅｏｆｌｉｎｅｓｅｇｍｅｎｔ３．３本文算法通过研究上述传统方法所出现的问题，本文提出基于特征点的三次Ｂ样条曲线拟合方法，通过能量最小化方法（ｅｎｅｒｇｙｍｉｎｉｍｉｚａｔｉｏｎ）反求控制点，并得到拟合曲线。首先，考虑到实际数据采样及加工特点，约定：曲线的首末控制点即为给定点列的首尾点；若点列含有微小噪声，则指采样工具及人为原因造成的可估计误差范围的扰动。在以上假设的基础上，本文算法（简称为ＥＭ算法）可以分为以下步骤：表３．１蹦算法步骤Ｔａｂ．３．１ＡｌｇｏｒｉｔｈｍｏｆＥＭＭｅｔｈｏｄＳｔｅｐｌ运用累加弦长参数化法，计算所有数据点ｐ，（ｉ＝Ｏ，．．．，ｍ）的参数值ｔ；Ｓｔｅｐ２利用曲率信息寻找根节点，指定控制点数为根节点数；构造样条结点；用能量最小建立拟合方程得到初始曲线；计算数据点与初始曲线上对应点之间的偏差，即：Ｓｔｅｐ３ｄｉｓｔ（Ｃ，Ｐ，）＝０ｉ—ＰＩｆ｜：ｄｉｓｔ（Ｃ，Ｐ，）≤ｓ，则算法结束；Ｓｔｅｐ４找出使得ｄｉｓｔ（Ｃ，Ｐ，）＞占的数据点，并依据曲率和弦长信息，在该数据点所在的范围内选取新的特征点；Ｓｔｅｐ５构造新样条结点及新控制顶点，得到新的Ｂ样条曲线；返回Ｓｔｅｐ３。可以看出，与传统方法的实现步骤比较，ＥＭ方法在参数化方面没有做更多的工作，本文直接采用常用的累加弦长参数化法，我们采取对特征点的参数进行平均的方法，继基于特征性质的三次Ｂ样条拟合算法而使得本算法具有局部调整性，即。卜，＝害ｊ。芝２ｔ，ｕ），（ｆ＝ｌ，．．．，甩一Ｐ＋１），其中ｉ是ｐ，的参数值，厂Ｕ）是一个简单函数，将特征点ｄ，的角标转化为其在数据点集中的角标。本文的核心工作主要集中在：初始特征点的选择、新特征点的添加以及能量最小化方法。下面我们逐项进行介绍。３．３．１特征点的选择本算法是基于自适应细分的算法，可以做到在较平坦的区域选择出的特征点较少，在复杂区域选择出的特征点较多，其主要步骤如下：表３．２特征点的选择步骤Ｔａｂ．３．２ＳｅｌｅｃｔｉｏｎｏｆｄｏｍｉｎａｎｔｐｏｉｎｔｓＳｔｅｐ１定义％为当前特征点下标的最大值，令‰＝一１，指定曲线拟合所要求的特征点数目聆；Ｓｔｅｐ２Ｓｔｅｐ３从点集中选出根节点，依据其有效性递减排列并存储至ＳＥＥＤ：判断：若ＳＥＥＤ非空且％＜，２：从ＳＥＥＤ队列中提出第一个点，作为新的特征点，％卜咒。＋１；若ＳＥＥＤ非空且ｎｄ≥以：跳至Ｓｔｅｐ５；否则跳至ＳｔｅｐＳｔｅｐ４４；判断：若％＜ｎ：按以下步骤选择新特征点ｄ，寻找两点ｄｌ＝Ｐ，和ｄ川＝Ｐ。０ｅ—ｓｆ＞１），使得由这两点定义的区域具有最大偏差；从此区域内，选择点Ｐｗ０＜ｗ＜ｅ）为新的特征点，嘞卜％＋１；否则跳至ＳｔｅｐＳｔｅｐ５５；输出：特征点ｄ，（．，＝Ｏ，．．．，咒）；１根节点的选择在给定的数据点集中，有很多种特殊的点能很好的表达数据的几何信息，我们选取这样的点为根节点。通常，这些点包括：局部曲率最大点（ＬＭＣ）、尖点、拐点、端点等。在这些点中，选择哪些为特征点，是由他们的定义方式和鲁棒性来决定的，在绝大多数情况下，这些特殊的点是由曲率信息所定义的，但是当给定的数据点是含噪点时，精确的估计曲率信息就比较困难了，因此对于上述特殊点的确定也造成了影响。但是相大连理工大学硕士学位论文对于其他点来说，ＬＭＣ点的确定相对容易，而且鲁棒性好，对噪声的容错性也较好，因此，在我们的算法中，我们考虑两种点为根节点：两个端点和ＬＭＣ点。对于给定的数据点，我们可以得出每一点的曲率磅，如果而＞ｋ。并且墨＞ｋｔ＋，，该点就可以判定为ＬＭＣ点。这些点，也就是在曲率信息坐标图里，曲率曲线的局部极大值点。在找到所有的ＬＭＣ点之后，考虑到噪声的影响，要对ＬＭＣ点进行筛选。我们给定曲率界‰＝‰／４，其中‰为所有给定数据点的离散曲率的平均值。在所有的ＬＭＣ点中，去除那些曲率小于ｋ的点，剩余的ＬＭＣ点以及两个端点即可选为根节点。在根节点中，端点是最典型的点，其余的ＬＭＣ点，曲率越大越典型，因此，根节点按照：端点、ＬＭＣ点曲率由大到小的顺序进行排列。２新特征点的选择注意在选择特征点的步骤中，可能会遇到根节点数目小于我们必需的特征点数目的情况，因此需要添加新的特征点，即从根节点之外的点中选择新的特征点。首先，由已有的特征点，我们可以通过拟合得到一条曲线Ｃ（ｔ），并通过这条曲线，更新离散点的曲率信息。选择新的特征点，即对现有的曲线段进行细分，我们定义Ｓ。。是由特征点ｄ，＝Ｐ。和ｄ『＋１＝ｐ。所确定的曲线段，从所有这些曲线段中选出包含至少三个点的那些，即要求ｅ—ｓＩ＞１。对于选出的这些曲线段所包含的点，找出与现有曲线ｃ（ｒ）偏差最大的点Ｐ。，这里的偏差即０ｃ（‘）一ｐ，０。于是，我们就选定点Ｐｃ所在的曲线段进行细分，即在其中选择新的特征点。现在考虑如何在这个曲线段Ｓ础上选取新的特征点Ｐ，。最直观的方法有两种：一是选择Ｓ。。上所有数据点的中位数点，即位于中间位置的点；二是直接选择Ｐ。点作为细分点。这两种直观的方法非常简单易行但是效果却不甚理想。前者可能会得到较多数目的特征点，后者直接受ｐ，点的影响，曲线的光滑性不能得到保障，而ｐ，点又是受到误差干扰的，所以上述两种方法都不能很好的表述数据点的信息。为了更合理的选择新特征点Ｐ。，我们考虑使用数据点的几何信息。已知Ｓ“是包含数据点Ｐ。（Ｊｉ｝＝ｓ，．．．，口）的曲线段，定义ｓ邓上的形状指标九．。是描述曲线段复杂程度的量，具体表达形式为：Ｆ，五，＝，．二奠互＋（１一，．）二业一Ｋ咖厶．册基于特征性质的三次Ｂ样条拟合算法其中，ｏ≤，．≤１’Ｋｓ，。表示曲线段ｓ邓的全曲率，可由墨，。＝∑：０屯ｌ＋Ｉｋ，１）ｏ“ｔ－ｔｒ）／２进行估计，蚝。ｍ是给定数据点的全曲率的逼近，厶，。表示曲线段Ｓ掣的弦长，可由Ｌ即＝∑：№卅－ｐｆ｜Ｉ进行估计，厶棚表示给定数据点的弦长的逼近。不难看出，以．。是评价曲线段复杂程度的量，当权，．＝Ｏ时就相当于弦长均匀分布，当权，．＝１时就相当于全曲率均匀分布。在实际应用中，很难自动的选取权重ｒ的值，但是根据经验，当数据点受噪声影响越大时，权重，．就应该越小。在后面的实验中，我们选取，．＝Ｏ．８。应用上述定义的形状指标，在曲线段Ｓ；卫上选取点Ｐ。，使得由此点分开的曲线段Ｓｓ，ｗ和Ｓ哗的形状指标是最相似的，也就是说，在ｓ即上，选取使得Ｉ以，，一九，一最小的点Ｐ。作为新的特征点。３．３．２能量最小化方法对于Ｂ样条曲线的拟合问题，即给定一组具有微小噪声的数据点列ｐ。（汪０，．．．，册）及容许误差占，找到一条ｐ阶（ｐ一１次）Ｂ样条曲线ｃ（ｒ）＝∑Ｍ，ｐ（ｆ）ｂ／，（０。≤ｆ童ｏ，），其中ｊ＝Ｏｂ』Ｕ＝ｏ，．．．，刀）是控制点，Ｕ，ｐ（ｆ）是定义在节点向量Ｔ＝｛ｔｏ，＾，．．．ｏ广。，ｏ户）上的ｐ阶Ｂ样条基。使得：勰ｌｌｃ（ｔ）一Ｐｒ６＜占，‘是ｐ，的参数值。当给定了数据点Ｐ，的参数值ｔ，、Ｂ样条函数的阶数ｐ以及节点向量Ｔ时，每一个数据点ｐ，都应落在曲线ｃ（ｆ）＝∑Ｍ，ｐｏ）ｂ，，（ｏ。＜－－ｔ＜ｔｒ一，）上，即满足下列线性方程：ｐ，＝ｃ（ｔ，）＝羔ｂ／－。ｐ（；『）（ｆ＝０，．．．，ｍ）ｊｊ＝ＯⅣｏ．，（ｆｏ）…Ｍ，户（ｆｏ）；’．ｉⅣｏ．ｐＯｍ）…Ｍ。ｐ（ｆ册）刚：卜＝Ｐ７’Ｐ其中Ａ是一个（ｍ＋１）×仰＋１）的数量矩阵，Ｘ是存储曲线控制点的解向量，Ｐ是存储输入点的向量。当我们要拟合的曲线没有其他约束（诸如切线或导数信息等）时，曲线Ｃ（ｆ）的控制点向量Ｘ可以通过最小二乘方法得到，即最小化下述最小平方误差Ｅ７（Ｘ）：ｍｉｎｅ７（ｘ）＝矧ｐｆ－ｃ（训２＝（Ａｘ—Ｐ）ｒ（ＡＸ—Ｐ）≥ＡｒＡＸ＝Ａ大连理工大学硕士学位论文其中Ａ７’Ａ是一个对称带状矩阵，带宽为（２ｐ一１）。对于上述的最小化问题，为了使其具有唯一解，数据点ｐ，的个数ｍ＋ｌ应该不小于控制点的数目ｎ＋ｌ而使得ＡｒＡ是非奇异的。然而，当数据点的个数大于但十分接近于控制点的数目时，上述最小化问题系统变得十分不稳定，拟合曲线容易出现大的波动。而在实际应用中，数据点以及控制点的数目是会经常变化的，在这种情况下，最小二乘方法就不太合适了。在这里，我们考虑使用能量最小化方法，即在考虑曲线拟合误差的同时，充分考虑到曲线能量泛函在最小化问题里的客观影响，采用曲线拟合误差与曲线能量泛函相结合的方式来求控制点。我们将最小化问题中的二次泛函Ｅ脚（Ｘ）表达成曲线能量泛函与最小平方误差Ｅ７（Ｘ）的和的形式：Ｅ触（ｘ）＝ｊ（口胁）１１２＋水（哪）ｄｒ＋ｙ副ｐｆ＿ｃ‘ｉ）１１２＝Ｘｒ（口工黼ｒｄｔ＋∥』黼ｒ防）ｘ＋厂（Ａｘ—Ｐ），（叙一Ｐ）＝Ｘ７（ａＫｌ＋∥Ｋ２）Ｘ＋ｙ（ＡＸ—Ｐ）７（Ａｘ—Ｐ）＝Ｘ１ＫＸ＋７（ＡＸ—Ｐ）１（ＡＸ—Ｐ）其中，非负系数口，∥，ｙ分别叫做伸缩系数、弯曲系数和拟合系数。Ｎ（ｋ）表示Ｂ样条基函数的七阶导Ｎ似’＝［圮譬（ｆ）…圮：◇）］。·Ｋ称为曲线ｃｏ）的劲度矩阵，由伸缩形式和弯曲形式的加权和表示，即Ｋ＝口Ｋｌ＋ＺＫ：＝口』瀚ｒ防＋∥互黼丁ｄｔ，Ｋ是＠＋１）×ｏ＋１）的带状矩阵，带宽为２ｐ一１。这样，蓝线ｃ（ｔ）的控制点向量Ｘ可以由最小化二次泛函Ｅｈ（Ｘ）来得到：ｍｉｎＥ７＋。（Ｘ）＝Ｘ７’ＫＸ＋ｒ（ＡＸ－Ｐ）ｒ（ＡＸ－ｒ）ｊＯＫ＋ｙＡｒＡ）Ｘ＝ｙＡｒＰ≥Ｘ＝ｙ（Ｋ＋ｙＡｒＡ）－１ＡｒＰ这里的Ｋ＋ｙＡ７’Ａ仍然是一个具有２口一１带宽的对称矩阵，并且是正定非奇异的。这样，解ｘ就是唯一的了。在解这个方程的时候，Ｃｈｏｌｅｓｋｙ分解法是十分有效的，我们直接使用。对于上述的系数口，∥，７，在实际应用中，我们可以通过改变这些系数，来实现曲线的变形，达到我们所希望的效果。而在后面，我们将选取Ｏｆ＝１．０，∥＝０．２，ｙ＝１０６进行试验ｎ们。基于特征性质的三次Ｂ样条拟合算法３．４实验算例及分析为验证本文算法的效果，针对相同的数据点信息，分别使用最小二乘的ＤＰ算法、等距包络法及本文的ＥＭ法进行拟合实验，实验都是应用Ｍａｔｌａｂ７．７在个人ＰＣ机上进行，配置为：ＣＰＵ—Ｉｎｔｅｌ（Ｒ）Ｃｏｒｅ（ＴＭ）２；内存＿２Ｇ。例１：对５１个取自：Ｙ＝ｓｉｎ（ｘ），ｘ∈卜万，ｙ／＂］的离散点，分别使用最ｄｘ－－乘ＤＰ算法、等距包络法和本文的ＥＭ方法进行拟合。在我们的实验中，根据正弦曲线的对称性，选取曲率最大点、中心零点及两个端点为特征点，一共得Ｎ９个特征点，得到的拟合曲线如图３．３所示。此拟合曲线与原曲线的误差为１．１０３×１０ｑ，效果已经很好。接下来，我们在控制点数目不超过９个的前提下使用经典方法进行试验，并考察误差，与ＥＭ方法比较。得到结果：。。’”””‘；。原曲线ｓｉｎ（ｘ）７：。７‘‘…７敲自ｓｉｎｔｘ）Ｆ３ｓ１个数据点拟合由线图３．３正弦曲线，在其上取５１个数据点，本文算法拟合的曲线及误差Ｆｉｇ．３．３Ｓｉｎｕｓｏｉｄ。５１ｄａｔａｐｏｉｎｔｓｓｅｌｅⅡｚｔｅｄｆｒｏｍｔｈｉｓｃｕｒｖｅＦｉｔｔｉｎｇｃｕｒｖｅｏｆＥＭｍｅｔｈｏｄ大连理工大学硕士学位论文包络拟合曲线图３．４最ｌＪ、－－乘ＤＰ算法拟合的曲线及误差；等距包络法拟合的曲线及误差Ｆｉｇ．３．４Ｆｉｔｔｉｎｇｃｕｒｖｅａｎｄ锄ｆｏｆＤＰｍｅｔｈｏｄ，ｆｉｔｔｉｎｇｃｕｒｖｅａｎｄｅｒｒｏｒｏｆＯｆｆｓｅｔｅｎｖｅｌｏｐｍｅｔｈｏｄ由结果看出，在同样数目的控制点的要求下，本文算法得到的曲线与原数据点列的误差最小。基于特征性质的三次Ｂ样条拟合算法例２：对３１个取自：ｙ：ｏ．５×√ｉ而，ｘｅ［－１，２】的离散点，分别使用最小二乘ＤＰ算法、等距包络法和本文的ＥＭ方法进行拟合。在实验中，我们选取曲率最大点及两个端点为特征点，得到的拟合曲线如图３．５Ｎ示，共得到控制点数８个。此拟合曲线与原曲线的误差为７．４０８×１０。５ｏ，～：…一。～ｙ一“？：…。｝“取自厦曲线上的３１个数据点．．·‘｛’’’７’＋＋；。·．．拟台曲线／／。ｊ“、、、＼，、％÷、图３．５抛物线，在其上取３１个数据点，本文算法拟合的曲线及误差Ｆｉｇ．３．５Ｐａｒａｂｏｌａ，３１ｄａｔａｐｏｉｎｔｓｓｅｌｅｃｔｅｄｆｒｏｍｔｈｉｓＣＨＩＶｅＦｉｔｔｉｎｇｃｕｒｖｅｏｆＥＭｍｅｔｈｏｄ大连理工大学硕士学位论文例３：由于等距包络法的处理对象为平面曲线，因此对于空间的情形，只对本文方法和ＤＰ方法进行比较。对下述螺旋线进行试验：ｘ＝ｅ－ｏＪ’ｃｏｓ（ｔ），ｙ＝ｅ－０ｍｓｉｎ（ｔ），ｚ＝ｔ，ｒ＝［０，６ｚｒ］。在空间曲线的实验中，我们给定实验误差，在此基础上比较各个方法的控制点数目：比较来看，本文由于需要计算曲率等一些几何信息，因此在算法的运行时间上没有优势，但是在控制点的数目以及误差效果方面，本文ＥＭ方法的效果是较好的。实验结果如下图所示：ｏｆ｜…■ｌ‘”？牡｝ｊ一’‘…？々１｛。峭·一７：＿＿’：。原曲线～＋１。……ｗ？带取自原曲线的９１个数据点■１１，Ｄ。０—Ｉ－１ｊ二１０一百，０拟台曲线越合曲线１｝１：国Ｄ．一ｉ曩，－１ｊ■；０√“、！；。’。二一：ｔ…－１０。｛：ｊ二。一¨“。一一ｉ一，；图３．５螺旋曲线；在其上取９１个数据点；本文ＥＭ方法及最小二乘ＤＰ方法拟合效果及误差Ｆｉｇ．３．５Ｈｅｌｉｘ，９１ｄａｔａｐｏｉｎｔｓｓｅｌｅｃｔｅｄ，ｆｉｔｔｉｎｇｅｆｆｅｃｔａｎｄｅｒｒｏｒｏｆＥＭｍｅｔｈｏｄａｎｄＤＰｍｅｔｈｏｄ基于特征性质的三次Ｂ样条拟合算法例４：对空间曲线进行试验：ｚ＝ｔ２ｘＣＸ）ＳｔＸｅ～，ｙ＝ｒ２ｘｓｉｎｔｘｅ～，ｚ＝０．０１ｘｔ２，ｔ∈［０，２ｘ］。我们给定误差占＝０．０１比较来看，本文由于需要通过逼近计算获得曲率等一些几何信息，因此在算法的误差上没有太多优势，但是在控制点的数目以方面，本文ＥＭ方法的效果是较好的。实验结果如下图所示：。。１”“：’：“？”７１一：９’¨’……？？’：ｊ獗硅茸＿线取自厦曲线的４１个数据意Ｄ．珥０．３ｎ２Ｏ．１０１；０１５－０．５Ｅ删馥合曲线ＤＰ拟合曲线１２．４０３ａ２０ｊ１０１１图３．６Ｆｉｇ．３．６曲线；在其上取４１个数据点；本文ＥＭ方法及最小二乘ＤＰ方法拟合效果及误差ＣＵＩ＇ＶＣ，４１ｄａｔａｐｏｉｎｔｓｓｅｌｅｃｔｅｄ，ｆｉｔｔｉｎｇｅｆｆｅｃｔａｎｄｅｒｒｏｒｏｆＥＭｍｅｔｈｏｄａｎｄＤＰｍｅｔｈｏｄ一２６—大连理工大学硕士学位论文４基于截面特征的曲面重构曲面重构是逆向工程中的关键环节，也一直是工程领域的研究热点。在多年的研究和实践中，重构的目的已不仅仅是在满足精度与光滑性要求下对测量数据的简单逼近，更重要的是获取产品的设计意图，得到物件的原始设计参数。因此重建曲面模型必须反映出原始物理物件所蕴含的特征信息。４．１问题描述及相关研究与曲线拟合问题类似，曲面的重构问题就是针对一组给定的数据点，找到一个曲面，使之与原数据点的偏差尽可能的小，继而可以近似的重构出该数据点集所在的曲面。对于上述实际问题和要求，近年来很多学者做出了大量的研究。Ｌｉｎ等人口孔首先提出了将测量数据按行进行Ｂ样条曲线拟合，然后用蒙皮生成曲面的方法，Ｐｉｅｇｌ等人∞１和Ｐａｒｋ等人ｎ妇分别以不同的方法实现了截面曲线的逼近蒙皮算法。本章中，我们在第３章曲线拟合算法的基础上，将数据点集切片以获取截面曲线，提出基于截面特征的曲面重构算法。鉴于我们从线到面的实施步骤，实际上曲面重构的问题，就转化为如何由一族曲线构造出一个曲面的重构问题ｂ１。为了方便问题的描述，我们简称直线、圆弧和样条等设计的基本元素为曲线元。一条截面蓝线可以分层次的描述为｛ｃ，，｝ｉ＝ｏ，ｌ；歹＝ｏ，ｌ＇…，臻＞，其中ｆ为层次，ｏ为特征点层，这里，特征点的概念与第３章中曲线拟合的特征点概念一致，１为特征曲线元层，刀．为第ｆ层所包含的特征的数目。因此，曲面重构问题就可以描述为：给定一族截面曲线｛ｃ，ｋｊ，七＝ｏ，…，ｍ｝，构造曲面ｓ（“，ｖ），使得ｍａｘ（Ｓ（ｕｋ，ｖ）一ｃ：ｆ（１，））≤ｓ，其中，Ｆ为给定的曲面重构误差。４。２特征相容在进行益面重构时，一个最重要的问题，就是解决曲线的相容问题。所谓曲线相容，通俗的说，就是对于一族曲线，要求它们都是有理或无理形式的，它们必须有相同的阶数，必须定义在相同的节点向量上，只有这样的曲线族，我们才可以通过曲线放样或曲面蒙皮的方法，获得重构曲面。在基于截面特征相容的曲面重构中，每一段曲线元都可视为截面曲线间建立特征对应关系的可能特征，而曲线元之间的对应关系又建立在特征点之间的对应关系上，因此，我们需要建立判断特征点之间是否匹配的准则。我们用Ｌ（％，）和乃（％。）表示截面曲线Ａ、Ｂ在特征点％』＋１和反州处的单位切矢。考虑到属于同一个实物模型的相邻截面曲基于特征性质的三次Ｂ样条拟合算法线之间具有几何形状上的相似性，因此，对应的特征点处其切矢方向应基本一致，内积（乃（约＋，），乃（唯＋，）＞＞ｏ，故我们有结论ｎ∞：如果两截面曲线彳、Ｂ在某特征点处的切矢内积（乃（扎Ｍ），ＴＢ（ｖ。＋。））＝ｌ，则称两特征点完全匹配。图４．１Ｆ逗。４．１曲线特征点切矢方向匹配ＭａｔｃｈｄｉｒｅｃｔｉｏｎｓｏｆｔａｎｇｅｎｔｆｉｅｌｄｓｏｆｔｗｏＣＵｌＷｅＳ而截面曲线的特征相容，一般需要经过特征点搜索、初始特征对应以及优化特征对应三个过程来建立曲线元之间的对应关系。４．２．１特征点搜索在曲面重构中，我们所指的特征点包括：尖点、拐点、曲率最大值点以及端点。这些特殊数据点的意义如下图所示：蒜童１）尖点２）拐点３）由事最大点图４．２截面曲线特征点Ｆｉｇ４．２Ｃｏｎｎｅｃｔｉｎｇｐｏｉｎｔｓｏｆｓｅｃｔｉｏｎａｌｃｕｒｖｅ对于上述特征点的搜索，除了可以参考本文第３章，依据曲率信息进行搜索外，还有一些比较成熟的方法，比如曲线的单凸性判断准则，黄金分割优化算法等等，本文不再详述。大连理工大学硕士学位论文４．２．２初始特征对应设ｃ：．『，ｏ≤ｆ≤朋和ｃ；√，ｏ≤／≤刀分别为两条相邻截面曲线ｃ１（甜）和ｃｚ（ｖ）的特征点列，Ｆ（ｏ≤ｆ≤ｍ）和Ｔ；（ｏ≤／≤刀）为截面曲线在特征点处的对应切矢。我们已经知道，如果两截面曲线么、Ｂ在某特征点处的切矢内积为１，即（耳，＠），砭，ｐ））＝１，则两个特征点完全匹配。所以，若使两截面曲线特征点之间达到最佳匹配，需满足ｍ－１ｍ－－｜１呀善（Ｔ１，引，ｍ－Ｉｍ－－ｉＩ、ｓ．ｔ．ｊ（Ｏ）＝ｏ，ｊ（ｍ一１）＝ｒｌ一１，／（ｆ）≤／（ｆ＋１）Ｊ即：唧善（１一（Ｆ，蚴），｝ｓ，．／（ｏ）＝ｏ，ｊ（ｍ一１）＝刀一１，ｊ（ｉ）≤＿，Ｏ＋１）Ｊ式中，（ｆ）表示两截面曲线特征点间的映射关系，这样就可以把截面曲线的特征点匹配问题转化为求解上式的离散最优化问题，我们采用动态规划法求解，其原理是：在求解问题的过程中，通过处理位于当前位置和所达目标之间的中间点来找到整个过程的解ｎ射。我们将所有可能的＠，）对应关系作为矩阵的元素建立，ｚｘ聊矩阵Ｍ，其中Ｍ（ｉ，，）＝ｌ一（Ｚ１，乎），我们不妨称Ｍ（ｆ，Ｊ）为（ｆ，Ｊ）建立对应关系时所付出的代价，显然，Ｍ（ｉ，歹）为零时，两特征点符合匹配条件。设允，（ｆ，Ｊ『）表示对应特征点ｃ：，，与ｃｉ．，之间，所有已经建立的最优对应决策的代价。当ｉ＝ｊ＝－Ｉ时允，（ｆ，，）＝０，而由初始条件可知，从江。到／＝０的对应关系，是计算所有厶（ｆ，／）的起点。我们可以得到下列式子成立口１：．怎，（ｆ，ｊ『）＝ｍｉｎ（ｆ嘲，（ｆ一１，Ｊ一１），。厂弼，（ｆ一１，／），。厂雠，（ｆ，Ｊ—１））＋Ｍ（ｉ，ｊｆ）容易看出，允，（ｆ，，）小于１时，匹配都是可以作为初始特征对应的。根据上式，利用回溯的思想，我们即可以建立截面曲线之间特征点及曲线元的初始对应关系。表４．１给出了一个简单的ｌ＇ｒｌ＝嚣＝４的例子，左侧表为特征点两两对应计算所得的初始４×４阶Ｍ矩阵，右侧表为基于Ｍ矩阵所建立的对应代价矩阵，其中黑体阴影数字的路径为最优决策过程。观察右侧表中的矩阵可以发现，最优路径的建立是从矩阵的左顶部向下、向右或向右下移动的过程。基于特征性质的三次Ｂ样条拟合算法表４．１特征点对应矩阵系数表Ｔａｂ４．１Ｃｏｒｒｅｓｐｏｎｄｉｎｇｃｏｓｔｂｅｔｗｅｅｎｆｅａｔｕｒｅｐｏｉｎｔｓ２３ｔ２３图４．３特征点初始对应关系Ｆｉｇ．４．３Ｉｎｉｔｉａｌｃｏｒｒｅｓｐｏｎｄｉｎｇｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｓｅｃｔｉｏｎｃｕｒｖｅｓ这样，就可以建立起了特征点的初始对应。４．２．３优化特征对应使用动态规划法，难以避免的就是特征点一对多映射的出现，如图４．４所示：Ｂ２ＢＡｏＡ３图４．４曲线映射点的一对多情形Ｆｉｇ．４．４Ｏｎｅｔｏｔｗｏｃａｓｅｉｎｐｏｉｎｔｓｍａｔｃｈｉｎｇ４鸣，局垦为两段Ｂ样条曲线，则由４．２．２节中的算法可知，４点同时对应马，岛两个特征点，这种现象的出现，是因为在某些截面曲线中，有的曲线元不足以和其他曲大连理工大学硕士学位论文线元之间建立“平等”的对应关系，也就是说，鼠点此时已经退化为曲线元内部的一个点，不能作为曲线元的分界点。为了解决此种情况，我们只需将“一对多＂拆分为“一对一＂，并逐个进行比对即可，本文不做详述。４．３曲面重构对于给定的一组截面曲线Ｃ。（甜），ｋ＝０，１，２，．．．，聊，基于特征相容算法进行曲面重建，算法步骤描述如下：．表４．２基于特征相容算法步骤Ｔａｂ．４．２ＡｌｇｏｒｉｔｈｍｏｆｃｏｍｐａｔｉｂｉｌｉｔｙＭｅｔｈｏｄＳ１；ｅｐ１Ｓｔｅｐ２依据曲率信息搜索特征点；曲线特征相容处理：１）在Ｃ。（甜）和Ｃ，＠）两条截面曲线之间建立特征对应关系，并根据对应情况删除内部特征点，调整曲线元；２）对调整后的Ｃ，（“）和Ｃ州＠）（ｆ＝ｌ，２，．．．，ｍ－１）进行处理，建立对应关系，如果此时Ｃ，（“）有内部特征点，则同时删除已与该内部特征点建立对应关系的其他特征点，并调整Ｃ，（”），，＝０，．．．，ｉ－１。３）按照截面曲线的顺序，依次执行２）操作，协调所有建立所有截面曲线之间的特征对应关系，并将曲线元的对应关系表达为（肌＋１）×＠＋１）次矩阵Ｃ＝（ＣｆＪ，），ｆ＝０，…，，打，Ｊ＝０，…，刀。Ｓｔｅｐ３对应曲线元特征的节点相容。鉴于插值方法进行节点相容存在的种种闯题，本文使用参考文献［６］中的逼近方法对矩阵Ｃ中的列向量，即对应曲线元进行节点相容。分别在曲线元上以弦高误差和弧长为控制手段采样，并基于相同的节点矢量序列逼近重构曲线元。Ｓｔｅｐ４重新拼合曲线元为一条完整的３次Ｂ样条曲线。以原截面曲线元之间的连续线为约束，拼合曲线元，使重建曲线保持原曲线元之间的连续性约束。经过上述操作，截面曲线之间已经具有相同次数和节点矢量，可直接生成３×３次Ｂ样条蒙皮曲面。Ｓｔｅｐ５大连理工大学硕士学位论文结论在曲线拟合方面，本文通过数据点自身的几何特征检测特征点，应用能量最小化方法反求控制点并进行曲线拟合，本方法自适应性强，稳定性好，受误差要求及数据密度的影响较低，可通过改变不同的参数来调整图形形状并具有局部优化性。在曲面重构方面，基于截面特征相容的方法能准确的表达曲面的几何特征，算法简单易懂，容易实现，运行效率和稳定性也有所提高。事实上，虽然本文算法有一定的优越性，但是仍然需要进一步的改善，以下是作者的一些构想：（１）在曲线拟合中，特征点的选取是通过曲率信息得到的，由于噪声影响，曲率信息难以准确表达，可以考虑将曲率信息以及其他信息如弦长信息等共同考虑进特征点的选取过程中，使得算法对噪声的敏感度降低，更好的表达出曲线的实际信息。（２）在曲面重构中，初始特征点对应的过程，是一个递推的过程，因此，当添加新的数据点时，若某特征点发生变化，其后的所有对应都将受其影响，降低算法效率，因此，可以考虑局部或分段递推的方式，使算法具有局部性，便于实际应用。大连理工大学硕士学位论文参考文献［１３许鹤峰、闰光荣．数字化模具制造技术［Ｍ］．北京：化学工业出版社２００１．［２］王仁宏，李崇君，朱春钢．计算几何教程［Ｍ］．北京：科学出版社２００７．［３］柯映林，王青．基于截面特征相容的曲面约束重构．浙江大学学报（工学版）２００６，１０：１７１５－１７１９．［４］夏静、罗钟铉．列表曲线的三次Ｂ样条自适应逼近算法．大连理工大学研究生院网络学刊［２００８］．［５］戴仕全、罗钟铉．自适应三次样条插值逼近算法．大连理工大学研究生院网络学刊［２００８］．［６］林子植．基于局部一整体的曲线曲面重建［Ｄ］．福建：福建师范大学，２００８．［７］ＳａｒｋａｒＢ，ＭｅｎｑＣＨ．Ｐａｒａｍｅｔｅｒｍｅａｓｕｒｅｍｅｎｔｏｐｔｉｍｉｚａｔｉｏｎｉｎａｐｐｒｏｘｉｍａｔｉｎｇｃｕｒｖｅｓａｎｄｓｕｒｆａｃｅｓｔｏｄａｔａ．ＣｏｍｐｕｔｅｒＡｉｄｅｄＧｅｏｍｅｔｒｉｃＤｅｓｉｇｎ，１９９１，８：２６７—２９０．ｆｏｒｔｈｅｒｅｄｕｃｔｉｏｎｏｆｔｈｅｎｕｍｂｅｒｏｆｐｏｉｎｔｓｒｅｑｕｉｒｅｄ［８］Ｄ．Ｄｏｕｇｌａｓ，Ｔ．Ｐｅｕｃｋｅｒ．Ａｌｇｏｒｉｔｈｍｓｆｏｒｒｅｐｒｅｓｅｎｔ１１２－１２２．ａｄｉｇｉｔｉｚｅｄｌｉｎｅｏｒｉｔｓｃａｒｉｃａｔｕｒｅ．ＣａｎａｄｉａｎＣａｒｔｏｇｒａｐｈｅｒ，１９７３，１０（２）：［９３ＨｙｕｎｇｊｕｎＰａｒｋ，Ｊｏｏ－ＨａｅｎｇｒｅｆｉｎｅｍｅｎｔｕｓｉｎｇｄｏｍｉｎａｎｔＬｅｅ．Ｂ－ｓｐｌｉｎｅｃｕｒｖｅｆｉｔｔｉｎｇｂａｓｅｄｏｎａｄａｐｔｉｖｅｃｕｒｖｅｐｏｉｎｔ．Ｃｏｍｐｕｔｅｒ－ＡｉｄｅｄＤｅｓｉｇｎ，２００７，３９：４３９—４５１．［１０］ＨｙｕｎｇｊｕｎＰａｒｋ．Ａｎｅｒｒｏｒ－ｂｏｕｎｄｅｄａｐｐｒｏｘｉｍａｔｅｍｅｔｈｏｄｆｏｒｒｅｐｒｅｓｅｎｔｉｎｇｐｌａｎａｒｃｕｒｖｅｓｉｎＢ—ｓｐｌｉｎｅｓ．ＣｏｍｐｕｔｅｒＡｉｄｅｄＧｅｏｍｅｔｒｉｃＤｅｓｉｇｎ，２００４，２１：４７９—４９７．ｆｏｒａｐｐｒｏｘｉｍａｔｅＮＵＲＢＳｃｕｒｖｅ［１１３Ｈ．Ｐａｒｋ，Ｋ．Ｋｉｍ，ＳＣ．Ｌｅｅ．Ａｍｅｔｈｏｄｏｎｃｏｍｐａｔｉｂｉｌｉｔｙｂａｓｅｄｍｕｌｔｉｐｌｅｃｕｒｖｅｒｅｆｉｔｔｉｎｇ．Ｃｏｍｐｕｔｅｒ－ＡｉｄｅｄＤｅｓｉｇｎ，２０００．３２：２３７—２５２．［１２］ＳｈｍｕｅｌＣ，ＧｅｒｓｈｏｎＥ，ＲｅｕｖｅｎＢＹ．ＭａｔｃｈｉｎｇｏｆｆｒｅｅｆｏｒｍＣｕｒｖｅｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ－ＡｉｄｅｄＤｅｓｉｇｎ．１９９７，２９（５）：３６９—３７８．［１３］ＭｉｃｈａｌｅｗｉｃｚＺ，ＤａｖｉｄＳｐｉｎｇｅｒ－Ｖｅｒｌａｇ，２０００．ＢＦ．Ｈｏｗｔｏｓｏｌｖｅｉｔ：ｍｏｄｅｒｎｈｅｕｒｉｓｔｉｃｓ［Ｍ］．Ｂｅｒｌｉｎ：［１４］Ｎ．Ｓ．ＳａｐｉｄｉｓａｎｄＰ．Ｊ．Ｂｅｓｌ，Ｄｉｒｅｃｔｒａｎｇｅｃｏｎｓｔｒｕｃｔｉｏｎｏｆｐｏｌｙｎｏｍｉａｌｏｎｓｕｒｆａｃｅｓｆｒｏｍｄｅｎｓｅｉｍａｇｅｓｔｈｒｏｕｇｈｒｅｇｉｏｎｇｒｏｗｉｎｇ，ＡＣＭＴｒａｎｓａｃｔｉｏｎｓＧｒａｐｈｉｃｓ，１９９５，１４（２）：１７１—２００．［１５３Ｆ．Ｎ．ＦｒｉｔｓｃｈａｎｄＪ．Ｂｕｔｌａｎｄ，Ａｍｅｔｈｏｄｆｏｒｃｏｎｓｔｒｕｃｔｉｎｇｌｏｃａｌｍｏｎｏｔｏｎｅｐｉｅｃｅｗｉｓｅｃｕｂｉｃｉｎｔｅｒｐｏｌａｔｅｓ．ＳＩＡＭＪｏｕｒｎａｌｏｆＳｃｉｅｎｔｉｆｉｃａｎｄＳｔａｔｉｓｔｉｃａｌＣｏｍｐｕｔｉｎｇ，１９８４，５：３０３－３０４．［１６３Ｆ．Ｎ．ＦｒｉｔｓｃｈａｎｄＲ．Ｅ．Ｃａｒｌｓｏｎ，Ｍｏｎｏｔｏｎｅｐｉｅｃｅｗｉｓｅｃｕｂｉｃｉｎｔｅｒｐｏｌａｔｉｏｎ，ＳＩＡＭＪｏｕｒｎａｌｏｆＮｕｍｅｒｉｃａｌＡｎａｌｙｓｉｓ，１９８０，１７：２３８—２４６．ｃｏｎｖｅｘ［１７３Ｅ．ＰａｓｓｏｗｏｆａｎｄＪ．Ａ．Ｒｏｕｌｉｅｒ．ＭｏｎｏｔｏｎｅａｎｄＡｎａｌｙｓｉｓ，１９８７：９０４—９０９．ｓｐｌｉｎｅｉｎｔｅｒｐｏｌａｔｉｏｎ，ＳＩＡＭＪｏｕｒｎａｌＮｕｍｅｒｉｃａｌ一３５—基于特征性质的三次Ｂ样条拟合算法［１８］Ｘ．ＹａｎｇａｎｄＧ．Ｗａｎｇ，ＰｌａｎａｒｐｏｉｎｔＤｅｓｉｇｎ，２００１，３３：３５—４３．ｓｅｔｆａｉｒａｎｄｆｉｔｔｉｎｇｂｙａｒｃｓｐｌｉｎｅｓ，Ｃｏｍｐｕｔｅｒ－Ａｉｄｅｄ［１９］ＳａｕｘＥ，ＤａｎｉｅｌＭ．ＤａｔａｒｅｄｕｃｔｉｏｎｏｆｐｏｌｙｇｏｎａｌＣｕｌｗｅｓｕｓｉｎｇＢ－ｓｐｌｉｎｅｓ．ＣｏｍｐｕｔｅｒＡｉｄｅｄＤｅｓｉｇｎ．１９９９，３１（８）：５０７—５１５．［２０３ＬｉＷ，ＸｕＳ，ＺｈａｏＧ，ｅｔａ１．ＡｄａｐｔｉｖｅｋｎｏｔｐｌａｃｅｍｅｎｔｉｎＢ－ｓｐｌｉｎｅｃｕｒｖｅａｐｐｒｏｘｉｍａｔｉｏｎ．ＣｏｍｐｕｔｅｒＡｉｄｅｄＤｅｓｉｇｎ．２００５，３７（８）：７９１—７９７．［２１３Ｊ．Ｅ．Ｌａｖｅｒｙ，Ｓｈａｐｅ－ｐｒｅｓｅｒｖｉｎｇ，ｍｕｌｔｉｓｃａｌｅｆｉｔｔｉｎｇｓｍｏｏｔｈｉｎｇｏｆｕｎｉｖａｒｉａｔｅｄａｔａｂｙｃｕｂｉｃＬ１ｓｐｌｉｎｅｓ，ＣｏｍｐｕｔｅｒＡｉｄｅｄＧｅｏｍｅｔｒｉｃＤｅｓｉｇｎ，２０００，１７：７１５—７２７．ｐｏｉｎｔｓｅｔｆａｉｒａｎｄｆｉｔｔｉｎｇｂｙ［２２］Ｘ．ＹａｎｇａｎｄＧ．Ｗａｎｇ．ＰｌａｎａｒＤｅｓｉｇｎ，２００１，３３：３５—４３．ａｒＣｓｐｌｉｎｅｓ，ＣｏｍｐｕｔｅｒＡｉｄｅｄ［２３］Ｍ．Ｋｏｒｓｔｅｒｓ，Ｃｕｒｖａｔｕｒｅ—ｄｅｐｅｎｄｅｎｔＡｉｄｅｄｐａｒａｍｅｔｅｒｉｚａｔｉｏｎｏｆｃｕｒｖｅｓａｎｄｓｕｒｆａｃｅｓ．ＣｏｍｐｕｔｅｒＤｅｓｉｇｎ１９９１，２３（８）：５６９—５７８．Ｋ．Ｋｎｏｔｒｅｍｏｖａｌｆｏｒｐａｒａｍｅｔｒｉｃ［２４３ＬｙｃｈｅＴ，Ｍ矽ｒｋｅｎＢ—ｓｐｌｉｎｅｃｕｒｖｅｓａｎｄｓｕｒｆａｃｅｓ．ＣｏｍｐｕｔｅｒＡｉｄｅｄＧｅｏｅｔｒｉｃＤｅｓｉｇｎ．１９８７，４（３）：２１７—３０．［２５］ＥｃｋＭ。ＨａｄｅｎｆｅｌｄＪ．ＫｎｏｔｒｅｍｏｖａｌｆｏｒＢ—ｓｐｌｉｎｅｃｕｒｖｅｓ．ＣｏｍｐｕｔｅｒＡｉｄｅｄＧｅｏｍｅｔｒｉｃＤｅｓｉｇｎ．１９９５．１２：２５９—２８２．［２６３Ｄ．Ｌｅｖｉｎ，Ｍｅｓｈ—ｉｎｄｅｐｅｎｄｅｎｔＭａｔｈ．ｓｕｒｆａｃｅｉｎｔｅｒｐｏｌａｔｉｏｎ，ＴｏａｐｐｅａｒｉｎＡｄｖａｎｃｅｓｉｎＣｏｍｐ．［２７３Ｉ．Ｋ．Ｌｅｅ，Ｃｕｒｖｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎｆｒｏｍｕｎｏｒｇａｎｉｚｅｄｐｏｉｎｔｓ，ＣｏｍｐｕｔｅｒＡｉｄｅｄＧｅｏｍｅｔｒｉｃＤｅｓｉｇｎ，２０００，１７：１６１—１７７．［２８］ＭａｒｊｉＭ，ＳｉｙｏｆｄｉｇｉｔａｌＰ．Ａｎｅｗａｌｇｏｒｉｔｈｍｆｏｒｄｏｍｉｎａｎｔｐｏｉｎｔｄｅｔｅｃｔｉｏｎａｎｄｐｏｌｙｇｏｎｉｚａｔｉｏｎｃｕｒｖｅｓ．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ．２００３，３６：２２３９—２２５１．ｏｐｔｉｍｉｚａｔｉｏｎｉｎａｐｐｒｏｘｉｍａｔｉｎｇｃｕｒｖｅｓａｎｄｓｕｒｆａｃｅｓ［２９］ＳａｒｋａｒＢ，ＭｅｎｑＣ．Ｈ．ＰａｒａｍｅｔｅｒｔｏＭｅａｓｕｒｅｍｅｎｔｄａｔａ．ＣｏｍｐｕｔｅｒＴａｍａｓ．ＲｅｖｅｒｓｅＧｒａｐｈｉｃｓ．１９８６．２０：１７９—１８８．ｍｏｄｅｌｓａｎｄｉｎｔｒｏｄｕｃｔｉｏｎ．ＣＡＧＤ．［３０］Ｖａｒａｄｙｅｎｇｉｎｅｅｒｉｎｇｏｆｇｅｏｍｅｔｒｉｃ１９９７，２９（４）：２５５—２６８．［３１３ＭａＷ，ＫｒｕｔｈＪ．ＰａｒａｍｅｔｅｒｉｚａｔｉｏｎｃｕｒｖｅｓｏｆｒａｎｄｏｍｌｙｍｅａｓｕｒｅｄｐｏｉｎｔｓｆｏｒｌｅａｓｔｓｑｕａｒｅｓｆｉｔｔｉｎｇｏｆＢ—ｓｐｌｉｎｅａｎｄｓｕｒｆａｃｅｓ．ＣＡＤ．１９９５．２７：６６３—６７５．ｓｕｒｆａｃｅ—ｌｏｆｔｉｎｇａｐｐｒｏａｃｈｆｏｒｓｍｏｏｔｈ—ｓｕｒｆａｃｅ［３２３ＬＩＮＣＹ。ＬＩＵＣＳ，ＬＡＩＪＹ．Ａｒｅｃｏｎｓｔｒｕｃｔｉｏｎｆｒｏｍ３ＤｍｅａｓｕｒｅｍｅｎｔｄａｔａＥＪ］．ＣｏｍｐｕｔｅｒｓｉｎＩｎｄｕｓｔｒｙ，１９９７，３４（１）：７３－８５．［３３３ＰＩＥＧＬＬ，ＴＩＬＬＥＲ１８（４）：２７３—２８３．ｗ．Ｓｕｒｆａｃｅｓｓｋｉｎｎｉｎｇｒｅｖｉｓｉｔｅｄ［Ｊ］．ＴｈｅＶｉｓｕａｌＣｏｍｐｕｔｅｒ，２００２，一３６—大连理工大学硕士学位论文攻读硕士学位期间发表学术论文情况陈露．基于特征性质的三次Ｂ样条拟合算法（本硕士论文第三、四章），大连理工大学网络学刊２００９年基于特征性质的三次Ｂ样条拟合算法致谢在论文完成之际，我要特别感谢我的导师罗钟铉教授，两年来，罗老师无论在学习还是生活中都给予了我极大的支持和帮助，罗老师渊博的专业知识、深厚的学术素养、严谨的治学态度、精益求精的工作作风、诲人不倦的高尚师德对我影响深远，也是我永远学习的榜样，并将积极影响我今后的学习和工作，使我终身受益，正是他的督促指导和不倦教诲，才有了这篇论文的顺利完成。感谢张洁琳老师、孟兆良老师以及所有的师兄弟姐妹在讨论班上对我的帮助和指导，也感谢大家在学习和生活中对我的关心和帮助，大家互相学习，共同进步的良好氛围，令人难忘。感谢我的爸爸妈妈，谢谢你们对我的无私奉献和关心培养，养育之恩，无以回报。感谢所有关心、支持、帮助过我的良师益友。最后，向在百忙中抽出时间对本文进行评审并提出宝贵意见的各位专家以及出席硕士论文答辩会的各位老师，表示衷心的谢意。基于特征性质的三次B样条拟合算法

作者：

学位授予单位：

陈露

大连理工大学

1.学位论文 郑尚文 逆向工程中曲线和曲面重构的研究 2004

逆向工程中基于点云的三维模型重建，在许多应用中具有重要意义.然而测量系统和三维CAD系统之间无法直接结合，因为测量得到的数据是海量散乱点，三维CAD无法对之进行高效处理.这成为逆向工程的一个瓶颈.该论文研究设计一个Test3D软件，其设计思想是：第一步作为三维扫描仪器和三维CAD软件的接口模块，搭起二者之间的桥梁，然后在此基础上研究直接由点云做面的处理方法，目的是通过对点云处理后能直接输出可供CAM软件使用的曲面模型.该论文的第一章阐述了逆向工程技术的应用背景、组成和原理.论述了在产品开发中应用逆向工程技术的各关键环节（即对象数字化、对象模型重构和对象加工）的原理和方法，并说明了该论文要重点研究的内容.第二章研究了如何自动由点云寻找特征点云带.该章在不附加物体表面上任何几何信息的条件下，通过寻找邻近点计算曲率，并通过曲率大小自动搜索物体表面特征区域.第三章对由离散点构建曲线进行了研究.在第二章得到特征点云带的基础之上，该章进而得到点云的特征点，并根据这些特征点生成自由曲线，这些自由曲线插值于特征点.第四章探讨了由海量散乱点重构曲面的技术.该章提出了一种新的曲面重构的方法，该方法兼备Bezier法和B样条法的优点，而且使用该方法得到的曲面是C<'2>连续的.第五章对全文进行了总结.

2.期刊论文 李俚.廖小平.耿葵花.苏文桂.周志华.王烈 电话话筒盖曲面重构设计的方法研究 -现代制造工程2004(5)

介绍基于NURBS曲面造型的电话话筒盖面反求设计方法.通过分析电话话筒盖面形状特征,提出采用等间距扫描采样方法进行数据采集,并将曲面简化成截面曲线模型,进行特征线NURBS曲线拟合,为NURBS曲面造型提供了合理化数据.

3.学位论文 李中海 反求工程中拟合曲面连续性的研究 2005

本文主要应用反求工程原理,达到了以下预定目标:对曲面重构进行分析以及理论算法研究,通过分析、比较和研究得出最优的数学模型和实际操作的理论基础.分析比较反求工程中自由曲线拟合以及自由曲面重构的方法,最后选出最佳的拟合方法和光顺处理使其满足本文所要求的光顺度和精度.对通过三坐标测量机所测量的自由曲面的实物样件的大量的、散乱的数据\"点云\"利用Surfacer软件进行预处理.利用Surfacer软件对点云进行曲线拟合以及曲面重构拟合,通过对拟合曲线和自由曲面的误差分析以及连续性的分析,使构造的自由曲面光顺度和精度均满足要求,从而实现理论与实际的相结合.利用UGNX软件进行实体生成,经过数控加工编程和刀具文件的后处理最终形成可以加工的实体模型.

4.学位论文 张军 基于钩锁类零件的逆向工程实用技术研究 2005

目前，激烈的市场竞争使产品更新换代频繁，要求企业做出快速反应。工业产品中自由曲线曲面设计由于三视图表达不清而难以进行CAD建模。利用逆向工程技术，可以有效缩短产品开发时间，提高市场竞争力，解决CAD建模中的难题。本文在全面分析国内外逆向工程领域研究现状的基础上，以钩锁铁蜡模样件作为应用对象，对复杂曲面产品的逆向设计进行了深入研究。研究工作主要包括以下内容：

1.样件的数字化复杂曲面产品的样件数字化方法不仅影响产品的开发速度，而且间接决定了曲面重构的速度和质量。论文运用一级模糊综合评判方法研究了复杂曲面产品的数字化策略，并以钩锁铁蜡模为例，讨论了基于CMM的数据采集关键技术及采集数据的具体流程；

2.点云数据的预处理针对散乱点云数据的特点，详细阐述了基于形状特征匹配的点云对齐方法。研究了散乱数据的误差修正和数据优化途径，对多种噪声点滤除方法和数据精简方式进行了对比分析，以找出满足应用需求的数据规范方法。并根据曲面重构的需要研究了点云特征的提取方法和曲面分块原则；

3.曲面重构论文首先从工程应用的角度分析了NURBS曲线、曲面造型方法中各种参数对曲线、曲面重构质量的影响。在此基础上，本文提出采用网格法进行三维散乱点曲面重构。对散乱点曲面拟合分为两种基本类型：由点直接生成面以及由点—线—面的方式生成面，并对各类型曲面拟合的特点及适用场合进行了归纳总结。对曲面拼接，发现实现光顺拼接的关键因素是曲面边界的选择及曲面变化趋势，并依此提出了一种新的曲面拼接方法。对工程中的三边域曲面及Y型曲面等特殊形状的曲面重构给出了解决方案，对蒙皮法中出现的曲面畸变现象进行了具体分析，并通过边界规范化、数据延拓以及曲面裁剪等方法使曲面畸变得到控制。

4.精度评价分析逆向模型的误差源、各种误差产生的原因及对逆向模型的影响；提出评价逆向模型精度的指标；简要分析了误差控制策略。 最后，本文将所述逆向设计实用技术应用于钩锁铁样件的模型重构，取得工程应用的较好效果。

5.学位论文 蔡炜斌 逆向工程中基于轮廓数据的曲面重构 2001

逆向工程是一项正在迅速发展的技术,而复杂贡面的CAD模型重建是反求工程的研究重点之一.该文总结了作者在基于截面轮廓数据的曲面重构方面所做的工作.该文描述了一种使用三角片模型对截面轮廓数据进行曲面得构的具体方法,并将模型以STL和一种紧凑的自定义文件格式输出.该文还详细分析了使用基于截面曲线的方法对截面轮廓数据进行B样条曲面重构的算法.该算法首先使用最小二乘法进行曲线拟合,在拟合过程中对多个轮廓在统一节点矢量情况下,运用二分法进行最小控制点数目的寻找得到一系列轮廓曲线,然后对这一系列曲线进行蒙皮操作生成B样条曲面.为了验证B样条曲面重构算法的正确性,该文还提出了相应的对重构模型进行误差检测的算法.

6.期刊论文 王传涛.杨建玺.张洛平.苏春堂.WANG Chuan-Tao.YANG Jian-Xi.ZHANG Luo-Ping.SU Chun-Tang 逆向工程中NURBS曲面重构技术 -河南科技大学学报（自然科学版）2009,30(2)

针对激光扫描系统采集的机械零件点云数据的特点,在原始点云数据预处理上,采用删除非曲面上的点云数据、拼接、排序和点云数据切片等方法,对数据进行平滑和分块,利用非均匀B样条法对切片点云数据进行光滑和数据插补,给出了NURBS曲面的重构方法,重构过程简单、适用,该方法是一种有效实用的方法.

7.学位论文 邵云 基于通用软件的人体模型构建方法探讨 2009

本文主要探讨了用通用软件构造人体模型的方法。根据建模方式以及功能上的差异，对各个软件在人体曲面重构过程中的应用进行了合理安排。从人体本身的几何特征、人体与服装关系、建模方式等角度考虑特征点的分布。根据特征点的分布，将人体划分区域，计算各区域内横截面个数。用各软件支持的画线方法进行曲线拟合实验，通过拟合误差比较，筛选出拟合状况相对好的曲线。通过实验比较u loft与uv loft的不同。设置不同的横截面层数，根据视觉效果、xov得出的拟合误差数据，分析曲面拟合质量以及不同层数对曲面质量的影响。
　　

试验结果表明当横截面上点的个数为60个，按照角度均匀排列时，3ds Max的点曲线拟合状态最好。由于uv loft的纵截面曲线要求与横截面曲线上的点建立对应关系，采用u loft作为构造人体模型的具体方式。通过对点曲线构造的曲面拟合误差分析，发现横截面上设置60点，横截面个数为60、70、80时，曲面拟合质量都很好，并且完成了缩减文件大小的目标。从简化操作、缩减数据角度考虑，使用60层重构人体模型是优化选择。

8.学位论文 吴新声 逆向工程在工业产品设计中的应用 2005

曲面重构是逆向工程研究的重要内容之一，本文从散乱数据曲面重构的实际需要出发，对散乱数据的测量、数据处理、曲面重构等技术进行了研究，进一步丰富和完善了逆向工程的有关内容。论文的主要研究内容和成果如下：

1)研究了基于点云数据的光滑截面线生成算法，给出了光滑实体截面线的生成方法。

2)研究了基于点云数据的复杂特征截面线生成技术。用曲率法提取轮廓特征点，以特征点为分界点，将截面数据点分为若干个数据单元，然后对各数据单元进行线型判断，最后用基于约束的平面轮廓线一次整体拟合。

3)通过对洗衣机波轮的反求，着重分析和介绍了以光学测量技术为主的数据采集原理及与其它测量方式的对比；通过对洗衣机波轮的测量、数据处

理和建模，在实践中打通了从ATOS到Imageware以及后续CAD通用软件(UG)的一条技术路线，在UG软件平台中实现了三维重构，并进行了精度分析与数控模拟加工，取得了较满意的结果。

9.期刊论文 黄健求.钟守炎.HUANG Jian-Qiu.ZHONG Shou-Yan 逆向工程中B样条拟合曲线与曲面的算法与实现 -机电产品开发与创新2006,19(4)

利用产品原形的三维测量数据,通过逆向工程设计新产品、改进或生产旧产品的过程中,曲线拟合及曲面重构是关键.采用B样条曲线拟合及B样条曲面重构,曲线更改灵活,曲面连接光滑,在逆向工程中具有广泛的实用性.

10.学位论文 彭琨 有序点曲线重构的研究和应用 2005

逆向工程技术是随着计算机技术的发展和成熟以及数据测量技术的进步而迅速发展起来的一门新兴学科与技术。它的出现，改变了原来CAD系统中从图纸到实物的设计模式，为产品的迅速开发以及快速原型化设计提供了一条新的途径。曲线和曲面的重建是逆向工程中的重要问题，特别是按照计算机图形学中点线面的发展规律，曲线重构更是其中很重要的一步，它为后面的曲面重构奠定了研究基础。重构问题是指由已知的采样数据点构造出物体的几何模型。这是对物体进行分析，计算和绘制的根据，也是研究曲线和曲面性质的重要途径。

本文首先介绍了计算机辅助设计与制造技术的发展历史，从而引出该领域的一个新的研究热点——逆向工程的概念和逆向工程中的曲线重构问题以及一些已有的解决方法。

第二章开始介绍对有关有曲线拟合的重要的定义和目前常用的方法的思想。对于曲线拟合最早可以追溯到曲线的二乘拟合。曲线的最终实现方式由早期的多项式曲线发展到参数曲线进而发展到现在的一个新热点——细分曲线。就参数曲线而言，数据点的参数化是一个重要步骤。目前常见的参数化方法有均匀参数化，累加弦长参数化，向心参数化等。对于细分曲线，现在也提出了很多常用的概念和方法。

第三章针对参数曲线的常见参数化方法提出了一个改进算法。目前的参数化方法大多不具有仿射不变的特性，即在进行某个或一系列仿射变换后为了正确反映曲线的形变而不得不重新参数化，从而效率较低。新的方法改进并证明了Nielson仿射不变基函数，后将其应用在参数化过程中，取得了良好的效果。但是该方法的数学定义无法处理已知数据点在一条直线上的情况。

第四章针对第三章的遗留问题提出新的解决方法——细分曲线。这种曲线重构方法本身不是参数曲线重构，因而不用先做参数化，而是直接根据已知数据点的位置关系插入新的定点，逐层细化后连成一条曲线。这种方法思路简单，本身不受任何仿射变换影响。与目前常见的细分方法不同的是，本文提出的方法采用半静态回插思想。更为有意义的是回插时根据上层数据点的位置特征和相对偏移回插，从而尽可能的对曲线保形。同时半静态的思路还使这种方法可被用于计算机设计中。

最后文章分析了曲线重构问题的困难所在，分析了文中介绍的方法的优点和缺点。文中提出的新方法都还停留在曲线问题的研究上，将来还可以将它们应用于曲面重构的研究领域中。

本文链接：http://d.g.wanfangdata.com.cn/Thesis_Y1481540.aspx

授权使用：大连大学图书馆(dldx)，授权号：369810d5-66da-43fb-99ea-9e9a00c099fd

下载时间：2011年3月2日