（计算机软件与理论专业论文）散乱点的曲线重构研究.pdf

山东大学硕士学位论文 散乱点的曲线重构研究 硕士研究生：伯彭波 指导教师：张彩明 摘要 逆向工程技术是随着计算机技术的发展和成熟以及数据测量技术的进步而 迅速发展起来的一门新兴学科与技术它的出现，改变了原来c a d 系统中从图纸 到实物的设计模式，为产品的迅速开发以及快速原型化设计提供了一条新的途径 曲线和曲面的重建是逆向工程中的重要问题该问题指由已知的采样数据点构造 出物体的几何模型这是对物体进行分析，计算和绘制的根据，也是研究曲线和曲 面性质的重要途径 本文首先介绍了逆向工程的概念和逆向工程中的曲线重构问题以及一些已 有的解决方法对于有序点的曲线拟合，数据点的参数化是一个重要步骤有序点 的曲线拟合方法最早可以追溯到曲线的二乘拟合无序散乱点的曲线重建是逆向 工程中的重要问题由于噪音的影响，采样数据点都偏离原曲线，形成一个一定宽 度的数据点云这时无法找到一条曲线通过所有的采样点，只能根据该点集中点 的分布拟合出一条反映原始数据点云的形状和走向的曲线作为重建曲线对于该 问题现在的工作有最小二乘拟合法，模型重建法，骨架法和离散方法四类 第二章分析了移动最小二乘法的表现对于较细的点云，移动最小二乘法重构 出的曲线能很好的逼近数据点但是移动最小二乘法存在两个问题：( 1 ) 对于不同 曲线段上的数据点相互影响的点集，移动最小二乘法会失败( 2 ) 对于宽度变化的 点集，需要自适应的确定点集的宽度，以避免数据点的相互影响采用欧几里德最 小生成树获取数据点的连接关系，避免了无关点的影响在多数情况下欧几旱德最 小生成树表现良好，但对于较坏的数据点，该方法也会失败本章还分析了概率论 中的相关度概念对计算点集宽度的效果 第三章提出一个基于平面带权图最短路算法的散乱点曲线重建方法，该算法 以每个点为中心构造一个正态分布的影响函数所有点的影响函数的叠加形成平 面区域的势函数散乱点的d e l a u n a y 三角化在删除长边后形成一个连通图对每 山东大学硕士学位论文 条边赋一个权值后，形成一个带权图使用最短路算法求出两端点问的最短路多 边形作为原曲线的逼近最后对逼近多边形进行优化和光顺，求出关键点以关键 点为控制点构造有理b 样条曲线，得到重构的曲线该方法把无序点的曲线重构 问题转化为有序点的曲线重构问题 最后文章分析了散乱点曲线重构问题的困难所在，分析了文中介绍的方法的 优点和缺点指出散乱点的曲线重构结果强烈依赖于给定数据点集的质量在逆 向工程中，数据点采样自一条实际的光滑曲线，采样密度能够保证，因此一般的方 法能够给出好的结果如果原曲线的形状复杂，一段固定次数的多项式曲线难以 很好的逼近原曲线最短路逼近算法为该问题的解决提供了一个新的思路最短 路逼近算法用最短路多边形作为原曲线的逼近，多边形顶点的权值较好的反映了 点集的分布采用有理b 样条曲线能够很好的反映复杂的曲线形状，重构出尖点 等形状特征 关键词：逆向工程，曲线曲面重构，散乱点，势函数 山东大学硕士学位论文 c u r v e r e c o n s t r u c t i o nf r o m u n o r g a n i z e d p o i n tc l o u d g r a d u a t es t u d e n t ：b op e n g b o d i r e c t o r ：p r o f z h a n gc a l m i n g 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 wt e c h n i q u ed e v e l o p i n gw i t ht h ed e v e l o p m e n to f c o m p u t e r s c i e n c ea n dt h ep r o g r e s so fd a t am e a s u r i n gt e c h n o l o g y i t sa p p e a r a n c eh a s i nf a c tc h a n g e dt h ed e s i g nm o d eo fp r o d u c i n gm a t e r i a lo b j e c t si nc a ds y s t e mf r o m d r a w i n g i td e s i g n sa n do f f e r san e ww a y f o rf a s tp r o d u c t i o na n dr a p i dp r o t o t y p i n g 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 na r et w oi m p o r t a n tp r o b l e m si nr e v e r s ee n g i n e e r i n g r e c o n s t r u c t i n gt h eg e o m e t r i c a lm o d e lo f t h eo b j e c tf r o mt h es a m p l ep o i n t sc a r r i e so d t h ef o u n d a t i o no fa n a l y z i n g ，c a l c u l a t i n ga n dd r a w i n go ft h eo b j e c t i ti sa l s oa n i m p o r t a n tw a y t os t u d yt h en a t u r eo fc u r v e sa n ds u r f a c e s t h i s p a p e r f i r s ti n t r o d u c e st h ei d e ao fr e v e r s e e n g i n e e r i n g a n dc u r v e r e c o n s t r u c t i o nf r o md a t ap o i n t s s o m ee x i s t i n gm e t h o d sa r ei n t r o d u c e d i nt h ea r e ao f f i t t i n gac u r v et oap o i n ts e ti no r d e r , t h ep a r a m e t e r i z a t i o ni s ak e ys t e p t h ef i t t i n g m e t h o dc a nt r a c eb a c kt ot h el e a s t s q u a r e sm e t h o d ，t h ep r o b l e mo fr e c o n s t r u c t i n g c u r v ef r o mu n o r g a n i z e dp o i n t si sm o r ec o m m o ni nr e v e r s ee n g i n e e r i n g b e c a u s eo f t h ei n f l u e n c eo fn o i s e ，t h ed a t ap o i n t sa r ed e p a r t e df r o mt h eo r i g i n a lc u r v e t h u sa r t u n o r g a n i z e dp o i n tc l o u di sf o r m e d s oi t i si m p o s s i b l et or e c o n s t r u c tac u r v ep a s s i n g a l lt h ep o i n t s w ec a no n l yc o n s t r u c tac u r v er e f l e c t i n gt h es h a p ea n dt h ep o s i t i o no f t h eo r i g i n a lc u r v ew h i c hf i t st ot h ep o i n ts e t t or e a c ht h i sg o a l ，t h e r ea r ef o u rm e t h o d s h a v i n gb e e ns t u d i e d ，w h i c ha r ef i t t i n gw i t hl e a s t - s q u a r e sm e t h o d ，m a t h e m a t i c a lm o d e l m e t h o d ，s k e l e t o nm e t h o da n dd i s p e r s i o nm e t h o d i nc h a p t e r2 ，t h em o v i n g l e a s t s q u a r e sm e t h o d i se x p l o r e d f o ras l i md a t ac l o u d ， t h em o v i n g l e a s t - s q u a r e sm e t h o dc a np r o d u c e ac u r v e f i t t i n gt h ed a t ac l o u dq u i t ew e l l ， b u tt h i sm e t h o dh a v et w od r a w b a c k s ：( 1 ) i ft h ed a t ap o i n t sc o m i n gf r o md i f f e r e n t 山东大学硕士学位论文 s e g m e n t so f ac u r v ea f f e c te a c ho t h e r , t h em o v i n gl e a s t - s q u a r e sm e t h o dw i l lf a i l ( 2 ) f o rad a t ac l o u dw i t hv a r y i n gw i d t h ，i ti si n a p o r t a n tt od e t e r m i n et h ew i d t ho f t h ed a t a c l o u da d a p t i v e l yi no r d e rt oa v o i dt h ea f f e c t i o no fi r r e s p e c t i v ed a t ap o i n t s t h e e u c l i d e a nm i n i m u ms p a n n i n gt r e ei su s e dt og e tt h ec o r r e l a t i o no ft h ed a t ap o i n t s ， t h u st oa v o i dt h ea f f e c t i o no fi r r e s p e c t i v ed a t ap o i n t s t h ee u c l i d e a nm i n i m u m s p a n n i n gt r e ew o r k sw e l li nm o s tc a s e s ，b u ti t a l s of a i l sw h e nt h ed a t ac l o u di st o o b a d t h ec o n c e p to fc o r r e l a t i o nd e v e l o p e di np r o b a b i l i t yt h e o r yi su s e dt od e t e r m i n e t h ew i d t ho ft h ed a t ap o i n t s ，a n di t sp e r f o r m a n c ei sp r e s e n t e d t nc h a p t e r3 ，an e wm e t h o dt or e c o n s t r u c tac u r v ef r o m p l a n a ru n o r g a n i z e dp o i n t s i sp r e s e n t e dw h i c hi sb a s e do i lt h ea l g o r i t h mo f f i n d i n gt h es h o r t e s tp a t hb e t w e e n t w o p o i n t si naw e i g h t e dg r a p h f i r s t l yt h em e t h o dr e g a r d se a c hp o i n ta st h ec e n t r ea n d c o n s t r u c ta ni n f l u e n c ef u n c t i o no f n o r m a ld i s t r i b u t i o n a f t e rs u p e r p o s i n gt h ei n f l u e n c e f u n c t i o n so fa l lp o i n t s ，ac o n t i n u o u sf u n c t i o ni nt h ep l a n ei sf o r m e d t h e nt h el o n g e d g e si nt h eg r a p ho fd e l a u n a yt r i a n g u l a t i o na r ed e l e t e da n dac o n n e c t i n gg r a p hi s p r o d u c e d aw e i g h t e dg r a p hi sp r o d u c e da f t e rg i v i n ge a c he d g ei nt h ec o n n e c t i n g g r a p hav a l u e t h es h o r t e s tp a t hb e t w e e nt h et w oe n dp o i n t so ft h eo r i g i n a lc u r v e p r o d u c e db y t h ed i j k s t r aa l g o r i t h mi su s e da st h eg o o d a p p r o x i m a t i o no f t h eo r i g i n a l c h i v e i nt h el a s t ，t h ep a t hp o l y g o ni sr e f i n e da n dt h ek e yp o i n t sa r ed e t e r m i n e d t a k i n gt h ek e yp o i n t sa sc o n t r o lp o i n t s ar a t i o n a lb - s p l i n ec u r v ei sp r o d u c e d ，t h e n e wm e t h o dc o n v e r t sap r o b l e mo fc u r v ef i t t i n gt o u n o r g a n i z e dp o i n t si n t oo n et o o r d e r e dp o i n t s i nt h el a s t t h e p a p e ra n a l y z e st h ed i f f i c u l t yi nr e c o n s t r u c t i n gac n r v ef o ra u n o r g a n i z e dp o i n ts e t ，a n dp o i n t so u tt h ea d v a n t a g e sa n ds h o r t a g e so fd i f f e r e n t m e t h o d s t h ep a p e rp o i n t so u tt h a tt h ep e r f o r m a n c e so fv a r i o u sm e t h o d sg r e a t l y d e p e n do nt h eq u a l i t yo f t h eg i v e np o i n ts e t i nr e v e r s ee n g i n e e r i n g ，d a t ap o i n t sa r e g o t t e nf r o maf a i rc n r v e ，a n dt h ep o i n t si sd e n s ee n o u g h t h u sm o s tm e t h o d sc a n p r o d u c eg o o dr e s u l t s w h e nt h eo r i g i n a lc u r v ei sn o tf a i ra n di t ss h a p ei sc o m p l e x ，o n e p o l y n o m i a lc u r v eo f f i x e do r d e rc a n n o ta p p r o x i m a t et h eo r i g i n a lc u r v ew e l le n o u g h t h es h o r t e s t p a t h 。a p p r o x i m a t i o nm e t h o da p p r o x i m a t e st h eo r i g i n a l c u r v eb yap a t h p o l y g o n ，a n dt h ew e i g h t so ft h ep o i n t si nt h ep o l y g o nr e f l e c tt h ep o i n t ss e tw e l l a 山东大学硕士学位论文 r a t i o n a lb s p l i n ec u r v ec a nr e f l e c tt h es h a p eo fac o m p l e xc u r v ea n dr e c o n s t r u c tt h e s h a p ec h a r a c t e r s k e y w o r d s ：r e v e r s e e n g i n e e r i n g ，c u r v e a n ds u r f a c e r e c o n s t r u c t i o n ， u n o r g a n i z e dp o i n t s ，i n f l u e n c ef u n c t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：丝塑坚日期：兰翌丝生堡 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：徨兰丝导师签名： 日期：塑! 生生企 砌 山东大学硕士学位论文 1 1 逆向工程介绍 第一章绪论 计算机辅助设计与制造技术( c a d c a m ) 发展迅速，自由曲面造型技术在现代 工业产品的设计和制造中应用越来越广泛在许多情况下，只有产品模型和实物 模型，没有产品的定义和图纸为了适应先进制造技术的发展，需要将这些样件 和实物转化为c a d 模型这种根掘实物模型和样件测量数据，建立数学模型，得 到其设计思想，从而进一步修改原有设计，然后将这些模型和表征用于产品分 析、制造和加工生产的过程就是逆向工程随着数控测量技术的发展，逆向工程 技术己被广泛应用于航空、航天、造船、汽车和模具等现代制造业的各个领域 逆向工程技术改变了原来c a d 系统中从图纸到实物的设计模式，为产品的 快速丌发以及快速原型化设计提供了一条新的途径传统的产品丌发流程是一 种预定的顺序模式，即从市场需求出发，抽象出产品的功能描述( 规格及预定指 标) ，然后进行概念设计，在此基础上进行总体设计和详细的零部件设计制定工 艺流程，设计工具央具，完成加工及装配，进行检验及性能测试这种开发模式的 前提是已经完成了产品的蓝图设计或c a d 模型然而在很多场合下，产品的初 始信息状态不是c a d 模型，而是各种形式的物理模型或实物样件，这就需要用 到逆向工程技术逆向工程从原始的物体实物出发，通过对它进行数据采集，曲 面重建，得到它的几何模型和设计思想逆向工程与快速成型制造技术( r p m ， r a p i dp r o t o t y p em a n u f a c t u r e ) 相结合，可快速实现复杂物体的三维拷贝，经 c a d 系统修改参数重新建模，可以实现零件的变异复原 逆向工程技术在许多工业领域中有着广泛的应用在仿型设计中，需要克隆 某个产品，然而通常却没有该产品的原始设计草案或文档在零件的修改与改良 设计中，需要从现存的产品出发，构造出它的几何模型，从而可以利用现有的 c a d 系统进行进一步的分析与优化，进而开发出新的产品在汽车工业等领域， 车体外壳的美学设计尤其重要设计师更喜欢在真实的雕刻或油泥模型上进行 设计因为实物模型比计算机二维屏幕更能真实的反映物体的形状，更有利于设 计师阐释他的设计思想在特制的服装、鞋帽等产品定制领域，由于每个人的面 山东大学硕士学位论文 部，身体结构不同，统一的尺码并不一定适合客户的要求，又由于批量小，可能就 只生产一件产品，传统的设计方法冗长费时，在经济上也不合适逆向工程的体 系结构如图1 1 所示，它由离散数据获取技术、数据预处理与三维重建以及快 速制造三部分组成 图1 1 逆向二l ：程体系结构图 1 1 1 表面数据获取技术 在逆向工程中，物体的表面数字化是关键的第一步，是逆向工程的基础只 有获取测量数据，才能进行误差分析和曲面比较，进一步进行曲面重建( c a d 建 模) 同时测量点的分布和数量也直接影响曲面重建方法的效率和重建曲面的品 质实物的三维离散采样速度及数据质量是影响逆向工程技术应用的重要因素 之一 现有的三维数据的获取方法基本上可分为两大类，即接触式与非接触式接 触式测量是指利用接触式测量仪器对实物外表面进行测量在接触式测量方法 山东大学硕士学位论文 中，机械坐标测量机( c 删) 是一种发展较为成熟测量设备，它是利用传感器实现 测量头在工件上移动，将复杂的三维曲面测量转化为二维测量，按曲面曲率的变 化不均匀地布点，从而记录下路径点的坐标值它具有噪声低，精度高( 可达 0 5 u r n ) ，重复性好等优点但测量速度慢、效率低，摩擦力和弹性变形的存在容易 引起模型变形产生测量误差，对软体对象难以做精密测量，需要对测头表面损伤 和测头半径进行补偿，而且对测头不能触及的微细表面无法测及，不易获得连续 的坐标点测量数据的特点是高精度低密度 非接触式测量法可分为光学法、工业c t 、超声波法和核磁共振( m r i ) 等随 着机器视觉技术和光电技术的发展，采用光电方法的非接触测量技术得到迅速 发展新的测量技术如激光技术、材料转移的光谱技术、三维全息照相显示技术 不断地涌现相应的测量方法有相位法，深度图象法，全息法，激光三角形法等 相位法测量基本原理是将周期性的光栅投影到被测曲面上受到被测曲面轮廓 高度的调制，光栅影线发生变形，解调变形光栅图象，建立变形光栅图象与被测 曲面轮廓高度的函数关系，求出被测曲面形状的三维信息 1 测量原理及光路结构简单相位值的解调有相移法和傅立叶分析法傅立叶 变换是数字图象处理中最基本和有效的频域分析方法，采用频谱分析手段解调 曲面三维信息，速度快，检测自动化程度高相位法测量的优点是速度快，测量范 围大，成本低：缺点是只能测量起伏不大的较平坦的曲面，曲面变化剧烈的地方， 会出现大的偏差，测量精度较低基于几何光学三角形原理的激光三角形法是目 前应用最广泛的非接触式测量方法三角测量的基本原理是由半导体激光器发 出的激光通过聚光透镜在被测曲面上结成光点并反射，光敏元件( 如p s d ) 接收 其散射光，根据其在p s i ) 上的位置，即可测出故测点的空间坐标 三维坐标测量机和激光快速扫描仪广泛应用于逆向工程中，但是它们有一 个相同的缺陷就是无法测定零件内部的轮廓尺寸，因此在快速原型技术中受到 很大的限制能实现物体的内轮廓线测量的典型方法有工业c t 和逐层切削照 相测量工业c t 成本较高，所获得的点以物体的横截面形式绘出，精度较低，但 它不损伤实物，是测量没有备件或复制品的复杂形状实物的唯一方法逐层切自0 照相测量是一种新兴的断层测量技术，它以极小的厚度逐层切削实物，并对每一 断面进行照相，获取截面图像数据其轮廓测量精度可达0 0 2 5 4 m m 是目前断 山东大学硕士学位论文 层测量精度最高的方法，而且成本较低，但它的突出缺点就是损坏了实物从发 展趋势看，工业c t 和逐层切削照相测量将占逆向工程测量方法主导地位，应用 范围也会更加广泛 1 1 2 数据处理与曲面重建 逆向工程中的另一个核心问题是采样数据点的曲面重建数据处理与曲面 重建过程包括点的精简与光顺处理、点的聚合、数据点的分块、曲线瞄面拟合 以及实体模型构造五大部分 图1 2 数据点的聚合 无论是通过三维坐标测量仪还是激光扫描仪，将物体数字化后得到的是一 大批的数据点云，不便于直接进行曲面拟合由于不可避免的测量误差，得到的 采样点集并非完全落在原物体上由于激光扫描设备的局限性，固定物体和设备 从一个方向进行采样无法获得物体的完整采样因此在扫描过程中，需要调整物 体的位置或者旋转激光头的角度，从多个方向对物体进行扫描，得到多张视图数 据，然后通过点的聚合，对它进行拼接，从而得到完整的采样数据点集如图1 2 所示由于获取数据的方式不同，得到的初始数据点集也不一样，所以需要对数 据点进行简化，聚合等预处理，以便于进行三维物体的曲面重建 山东大学硕士学位论文 工程实际中原型往往不是由一张简单曲面构成，而是出大量初等解析曲面 ( 如平面、圆柱面、n f i l n 、球面、圆环面等) 及部分自由曲面组成，故三维实体 重构的首要任务是将测量数据按实物原型的几何特征分割成不同的数据块，使 得位于同一数据块内的数据点可用一张特定的曲面来表示，然后针对不同数据 块采用不同的曲面建构方案( 如初等解析曲面、b - s p l n e 曲面、b e z i e r 曲面、 n u r b s 曲面等) 进行曲面重建，最后将这些曲面块拼接成实体这个过程包括点 集分割与曲面重建两部分 点集分割可以分为基于边的分割方法和基于面的分割方法前者主要是利 用点以及该点附近的点的信息，依赖该点处的局部法向，曲率以及高阶微分信息 来判断它是否位于两张不同曲面的边界上确定边界点后，利用种子扩充的方法 延伸得到整条边界，从而将数据点分割成若干不同的部分 2 3 后者正好相反 它将具有相同或者相似局部性质的点划分到同一个子集内，用一张曲面表示各 曲面的边界利用曲面相交得到 曲面重建是逆向工程中最重要的问题，也是当前逆向工程研究中的热 点1 9 9 2 年，h o p p e 首先提出了曲面重建问题 4 ，随后众多的研究者在此方面 做出了卓有成效的工作根据重建曲面和数据点云之间的关系可将曲面重建分 为插值法和逼近法两大类前者得到的重建曲面完全通过原始数据点后者用分 片线性曲面或其它形式的曲面来逼近原始数据点，使得到的重建曲面是原始点 集的一个逼近根据重建曲面表示形式的不同可以分为五类：参数曲面重建、隐 式曲面重建、变形曲面重建、细分曲面重建和分片线性曲面重建 逆向工程的最终目标是从原始物体出发，自动地构造出该物体几何模型与 设计思想，以便于运用现有的c a d 造型工具对其进行再设计，或者利于快速成 型机实现物体的快速仿制通过曲面重建方法得到的几何模型通常是用初等解 析曲面，自由曲面或网格曲面表示的，因而需要将这些几何模型转化为边界表示 模型等c a d 系统可以接受的表示形式t v a r a d y ，z h u 等人在此方面做出了有 益的研究 5 6 山东大学硕士学位论文 “。? l 二 誊缪罄 ：珏 ：o - | ， i ，。+ 一 一囊：，：! ? ( a ) 数据点和估计的法向( b ) 投影点和逼近曲线( c ) 重构的旋转体曲面 幽1 - 3空间旋转体的重构 逆向工程的研究和应用近年进展很大，也存在不少有待进一步研究的问题 数据获取技术，快速成型技术的发展已趋成熟，但通过测量数据建构实物数学模 型的技术相对滞后，从而严重影响着逆向工程的实用化程度因此逆向工程领域 今后的研究应侧重于包含复杂曲面的实体特征建模技术方面以下问题仍是逆 向工程中值得研究的方面：1 ) 多视、多基点、变分辨率测量数据的坐标归一化 及融合投术：2 ) 特征的智能识别及表示，特征几何区域的自动分离，求精，重构及 拼装：3 ) 有关模型精度与光顺性的优化问题：4 ) 模型的简化及多分辨率显示 1 2 曲线重建方法 逆向工程的核心问题是如何从采样点出发重建出曲线、曲面模型传统的曲 面重建方法，是按点一线一面的重建顺序来获得重建曲面 7 先由点定义出一 组特征线，然后由这些曲线构造曲面在旋转面，扫成面，螺旋面等特殊的曲面重 建中，需要先分别重建出他们的脊线与母线，然后得到整个曲面的几何表示模型 8 图1 3 显示了先重构轮廓线再由轮廓线重构旋转曲面的过程将旋转体旋 转3 6 0 度，表面的数据点投影到过中轴的平面上，从而得到平面散乱点在计算 机视觉中，通常要考察如何从图象或扫描获得的离散数据点重建几何模型，以利 ，一 一一 二芝e ? 一奄 山东大学硕士学位论文 于形状分析和识别由已知的采样点集拟合出发一条或多条曲线，反映出浚点集 的形状和走向，即曲线重建的问题曲线重建问题在逆向工程和计算机视觉中有 蔚广泛的应用根据已知采样点集的性质可以将曲线重建的方法分为有序离散 点集的曲线重建和无序散乱点集的曲线重建 1 1 3 有序离散点的曲线重建 有序离散点的曲线重建是指给出依次采样于某条己知曲线上的一系列采样 点，如何构造出一条曲线依次通过或近似通过这些采样点，作为原曲线的逼近 基于有序点的曲线拟合，最早可以追溯到曲线的二乘拟合在逆向工程中，对有 序点进行曲线拟合，要求得到的重建曲线能够反映出原始点集的形状与特征，于 是越来越多的研究者针对有序数据点的保形曲线拟合做出了许多有益的研 究1 9 8 1 年，m c a l l is t e r 给出了用二次样条曲线进行插值重建的算法 9 ，f r i t s c h 和c l a r s o n ，b u t l a n d 等人讨论了用如何分段三次曲线进行插值 曲线重建 1 0 1 1 ，更一般的，p a s s o w 和r o u l i e r 讨论了如何用多项式样条函 数进行有序点曲线重建的问题 1 2 随着有理曲线的进一步研究和对有理曲线 性质的掌握，如何运用有理曲线进行有序数据曲线重建也被越来越多的研究者 提出柬 1 3 1 4 1 5 随着多分辨率思想的提出，如何用多尺度样条拟合数据点 这一课题摆在众多研究者面前2 0 0 0 年l a v e r y 在 1 6 文中给出一种用三次光 滑l 1 样条多尺度地保形拟合数据点的新方法也有其它研究者讨论了用圆弧 样条、双圆弧样条或其它参数样条进行有序点曲线重建的问题 1 7 1 8 1 2 1 1 数据点的参数化 有序数据点逼近的重要一步是数据点的参数化设给定”+ 1 个数据点 p ，f = o ，1 ，行如果我们把给定的”+ 1 个数据点看作是某一参数曲线上的点 p ( ，) 那么刺只，i = o ，1 ，”插值，就是要求出参数曲线p ( f ) ，使得p ( t ) = 只要 唯一地决定一条插值于”+ 1 个点p ，i = 0 ，1 ，h 的参数插值曲线或逼近曲线必 须先给数据点只指定相应的参数值t ，使其形成一个严格递增的序列 q ，：，o ，l ，称为关于参数，的个分割( p a r t i t i o n ) 其中每个参数值称 山东大学硕士学位论文 为节点( k n o t ) 或断点( b r e a k p o i n t ) 对于插值曲线而言，它决定了位于曲线 上的这些数据点与其参数域f 【f 0 ，。】内的相应点之间的一种对应关系对一组 有序数据点决定一个参数分割称之为对这组数据点实行参数化 ( p a r a m e t r i z a t i o n ) 把插值曲线看作质点顺序通过的一些空间位置( 即数据 点) 的运动轨迹，参数f 看作时间，那么对数据点的参数化，就等于规定了质点依 次到达这些空间位置的时间它们是人为给定的同一组数据点，即使采用同样 的插值法，若数据点的参数化不同，将可能获得不同的插值曲线我们希望，对数 据点的参数化，应尽可能反映设计员想要用数据点构造的曲线的性质对数据点 实行参数化有如下方法： 1 2 1 1 1 均匀参数化法 使每个节点区间长度( 用向前差分表示) ，= t 。一= 正的常 数江0 ，l ， 一1 ，即节点在参数轴上呈等距分布，为处理方便起见，常取成整 数序列f 。= i ，i = 0 ，1 ，”这种参数化法仅适合于数据点多边形各边( 或称 弦) 接近相等的场合，否则，在多边形相邻段弦长相差悬殊的情况下，生成插值曲 线后弦长较长的那段曲线显得较扁平，弦长较短的那段曲线则膨得厉害，甚至出 现尖点或打圈自交的情况 出现上述问题，从物理上可解释如下：把参数r 看作时间，质点j p 随着时间 变化在空间扫出一条依次经过给定位置( 即数据点) 的曲线p ( t ) 采用均匀参数 化就意味着在任意两邻点间花费同样多的时间，而不管它们间的距离如何如果 汽车沿着这样一条插值曲线行驶时，数据点成了站点，当两邻站点间距离大时， 就必须高速i j 进如果接下来的两相邻站点间距离很小时，由于不能把速度突然 减下来，就会发生过冲问题 1 2 1 1 2 累积弦长参数化法 令 f o = 0 t ，= l 一，+ l 舭一。 ，f = 1 ，2 ，” 其中l 叱f 是向量他的长度，叱= b 卅一只即弦线矢量这种参数化法反 山东大学硕士学位论文 映了数掘点按弦长的分布情况，一直被认为是最佳参数化法它克服了数据点按 弦长分布不均匀情况下采用均匀参数化所出现的问题在较多情况下能获得较 满意的结果，即所得插值曲线具有较好的光顺性弦长参数化法生成的插值曲线 在某种程度上可看作粗略的弧长参数化，切矢模长较接近单位长，似可看作为较 好光顺性的解释应该指出，插值曲线的光顺性不仅与数据点的参数化有关，还 与所采用的插值法有关当数据点取得足够密，且当插值法具有收敛性质，即加 密数据点时插值曲线收敛到被插曲线的性质时，将生成近似弧长参数化的插值 曲线但在工程实践中，都不希望费这样的麻烦人们希望能用尽可能少但又足 以表示形状的数据点，方便地生成所要求的曲线 1 2 1 1 3 向心参数化法 令 t o = 0 卜o + i 纰一f 这是美国波音公司的李( l e e ，1 9 8 9 ) 提出的他从积累弦长参数化法并不总 能保证生成光顺的插值曲线出发，认为问题在于未考虑数据点相邻弦线的折拐 情况就像汽车在高速公路上行驶那样，司机驱车的安全性与舒适感取决于使向 心加速度在一定界限内平稳地变化由此他假设在一段曲线弧上的向心力( 因而 向心加速度) 与曲线切矢从该弧段始端至术端的转角成正比，加上其它一些简化 假设，导出如上的参数化法与积累弦长参数化法在计算上的差别，这里取成了 弦长平方根的积累，故又称为平方根法据他介绍，在他所作的所有非均匀分布 数据点的试验中，向心参数化法都给出比前述两种方法好得多的结果但正如李 指出，在向心参数化法的最后结果中实际并未反映出数据点相邻弦线的折拐情 况 1 2 1 _ 1 4 修整弦长参数化法 令 t o = o = 一，+ 鼻l 纰一 其中：1 + 三( ! 竺= ：l 堡= ! + ! 竺堡 、 2 、j 北一：扯一1f 啦一。够 9 山东大学硕士学位论文 只= m i n p r 一么只一，f 争 只，i = l 只户0 1 2 最小二乘逼近 最小二乘法是曲线拟合的重要方法，在第二章中也会用到因此这里介绍最 小二乘逼近的思想考虑如下的”次参数m ( 所) 多项式曲线 p ( ，) = q 妃( ，) 其中红( ，) ，i = 0 , 1 ，n 为 n 次多项式空间的一组 基，a ，= i 只乏 ，i = 0 , 1 ，r 为待定的系数矢量设给定的数据点为 只= 【hh = 。 ，k = 0 ，1 ，m ，于之相应的参数是t o ，如果当作捅值 问题处理，将有如下线性方程组 q 仍( ， ) = 只， k = o ，1 ，珊 写成矩阵形式o a = p 其中系数矩阵 m = 为沏+ 1 ) ( + 1 ) 阶矩阵 ( o o ( t o ) ( ) 妫( 0 ) 鳓( 纸( f 。) 吼( ) q ，o ( t 。) 妒l ( ，。) o o ( t 。) a =卜= p 0 b 这里矢量方程个数m + 1 超过了未知矢量个数珂+ 1 这样的方程组称为超定 的，或称为矛盾方程组在一般情况下，解是不存在的即一般地不存在严格依次 通过这些数据点的插值曲线j p ( ，) 这时，我们只能寻求在某种意义下最接近这些 数掘点的参数多项式曲线户( ，) 作为逼近曲线 1 山东大学硕士学位论文 度量逼近的程度最常用的一种方法是耿逼近曲线p ( ，) 上具有参数值“的 点p ( t + ) 与数据点斥i 剧的距离平方和 ，：芝i p ( “) 一只1 2 ：以+ ，+ 止 达到最小，称之为最小二乘逼近 ( l e a s t s q u a r e a p p r o x i m a t i o n ) ，j = ( 以，j 。，以) 称为目标函数其中 上= e e , e l ( 1 女) 一“ 2 j y = 只仍( f j ) 一y a 2 以= 兰乏竹( 气) 一缸】2 欲使j 为最小，就应使j x , j 。j ：都为最小为此必须使下列偏导数为零 把 写成矩阵形式 = o , 1 ，n 要生= 兰妒，( “) n 墨仍( “) 一k 钡女= 0j = 0 = 兰妒，( o ) 童i 仍( 屯) 一兰伊，( ) 坼 女= 0f = ok = 0 。 0 0 0 = = l i 弘一墙、盟谚弛一呼 山东大学硕士学位论文 g 啦q j x = 嘶) 吣卜吣) = 眈( f o ) i ；o j ( t i ) 纺( r 。) ( ) 仍( ，。) e o ( t 1 ) 仍( f 1 ) 蛾( ，o ) 妒 j ( t ，) 即 同理可得 妒o ( t o ) 仍( f o ) ( f o ) 中 l 儿 中r 中i 誓 l 啦 嘛们。) ，、 旧5 x ol 髅代j 1 l 忙oj 1 ( f 。) 蛾( f o ) f ( ) 仍( f 1 ) l e o ( t 。，) 仍( ! 。) ( ，) 觋( ，) 吼( f 1 ) = 中7 = 中7 = 7 仍心) 弼( ，) 吼( f o ) 纯( f ) 吼( f 。，) 吼( f 。，) ( 1 2 ) ( 1 3 ) 卦 方程组( l1 ) 一( 1 3 ) 存在唯一解， 考虑到实际所给数据点的重要性与可靠性有可能是各不相同的，为此，可对 一一 ，。l ) ) ) 帕? 吼 得起一在合 玎20 i 丝吗 以所 一一一h编毗地门川川ij =l m m m 0 p 0 吼纪 皂= 五；k 仍 一；k 一一五；一k m ； 互： 山东大学硕士学位论文 每个数据点引入相应的权( w e i g h t ，或称因子权) ，k = 0 , i ，朋，使得重要性 与可靠性高的数据点对形成p ( ，) 的影响大于是，目标函数相应地变成 d = 吼m 。) 一硝 有多种实用的求解法方程的方法，如正交化方法和改进的正交化方法等解 之，即可求出未知系数矢量矩阵a 于是，就定义了逼近曲线p ( t ) ，特殊地，如果 m = n ，逼近曲线就成为插值曲线 i i 4 无序散乱点的曲线重建 在逆向工程中，一个更常见的问题是无序散乱点