（应用数学专业论文）数据点的提取与拟合.pdf

摘要 经过近2 0 年的研究，基于计算机辅助设计的实物遒向工程技术在机械产品开发中取褥了广 泛豹应用，但逆恕工稷技术仍处程发展之中，诲多闯题鸯待解决。数据点的提取翻拟合是逆向工 程里最关键静技术之，数据提取和撅合的效栗直接影响着机械产懿的造垂。 在机械产品中，只由一张曲谳构成的情况不多，产晶外形曲面往往由多张曲面混合而成。只 按爨一张魏嚣去重构冀数学模型缀难援证其模型精度，予是，在曲线艟蟊拟合之蔫还要遴舒豹工 作是数据掇取。数据掇敢是将灏爨数据分类转变成为造黧数据，方法是根据每一个自然瞳瑟，将 测量点分割同时并能够决定每一个点集属于哪一种曲面。本文使用艇小子集定义一个二次曲面， 褥二次麴露的提取等嗣予寻找强栋邈数鳇最俊缀，著使用模拟退火遮媸算法将蠖划二次麴嚣跌测 量数据中分离出来。该方法的优点是概念简单、实现容易且不依赖于曲面的分割结果。对试验结 果的分析表明，该方法在二次曲谢的提取速殿方面比遗传算法要高。 峦绘定戆室阕数援焦集搀选b 样条趋线黪嚣是c a g d 中一个鬟要静磷究渫题，常耀瓣遥透 方法实质上是基于“经验风险”意义下的最小二乘逼近。本文讨论了基于“结构风险”意义下用 最小二乘支持向量回归机整体构造b 样条曲线曲面的逼近问题，其出发点是最小化结构风险，而 不是传统攀霹戆经验风羧最垂豫，获嚣在理论主绦证了较好豹接广黢力，麓够蜜现慰聂始 垂线盎 面的逼近而不仅仅是对测量数据点的逼近。本文建立了b 样条曲线曲面拟合的数学模型，并构造 了一种特殊的核函数米保证曲面的b 样条表永形式。本方法为逆向工程中曲线曲面的拟台问题提 供了薪愚黪，数篷实验诞实了可箨犍。 关键谲：搂羧逡必，遴传算法，支持囱量橇，b 样条，拱合 a b s t r a c t t h r o u g h2 0y e a r s r e s e a r c h r e v e r s ee n g i n e e r i n gt e c h n i q u eb a s e do i lc o m p u t e ra i d e dg e o m e t r i c d e s i g nh a se x t e n s i v e l ya p p l i e di nr e a lo b j e c tp r o d u c t , b u tt h er e v e i , s ee n g i n e e r i n gt e c h n i q u es t i l li s p l a c e di nd e v e l o p m e n ta n dm a n yp r o b l e m sn e e dt ob er e s o l v e d t h ep o i n t se x t r a c t i n ga n df i t t i n gi st h e o n eo ft h em o s ti m p o r t a n tt e c h n i q u ei nr e v e r s ee n g i n e e d n g ，t h er e s u l to ft h ee x t r a c t i n ga n df i t t i n g a f f e c t st h es h a p eo f t h em a c h i n e p r o d u c td i r e c t l y a c t u a l l y , t h es h a p eo f ap r o d u c ti sn o tc o n s t r u c t i o no f as i g n a ls u r f a c e ，i ti su s u a l l yc o n s t r u c t e db y s e v e r a ls u r f a c e s s o ，i fw ef i t t i n gt h ep r o d u c to n l yb yas i g n a ls u r f a c e ，t h ep r e c i s i o no f t h em a t h e m a t i c a l m o d e li sn o tv e r yw e l l b e f o r ef i t t i n go ft h ec u i v e so rs u r f a c e st h ew o r kw eh a v et od oi st oe x t r a c to f t h ep o i n t s t h ep o i n t se x t r a c t i n gi st os e p a r a t et h em e a s u r e dp o i n t st od i f f e r e n ts e t s ，a n di ti sb a s e do n t h en a t u r a ls u r f a c e aq u a d r i cs u r f a c ei sd e f i n e du n i q u e l yb yam i n i m a ls u b s e t ，a n dt h ee x t r a c t i n go f q u a d r i cs u r f a c ec a nb ec o n s i d e r e da st h ee q u i v a l e n tt of i n d i n gt h eo p t i m u mv a l u eo fac o s tf u n c t i o n t h i sp a p e rh a sp r o p o s e dan e wm e t h o d ，s 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 ，t oe x t r a c tt h eq u a d r i c s u r f a c e t h en e wm e t h o di se a s yi n t e l l i g i b l ea n dn o td e p e n d i n go nt h es u r f a c es e g m e n t a t i o nr e s u l t s t h e e x p e r i m e n t a lr e s u l t sh a v ep r o v e dt h a tt h i sm e t h o dc a i le x t r a c tm u l t i p l eq u a d r i cs u r f a c e sr a p i d l ya n d a c c u r a t e l y t h ep r o b l e mo fc o n s t r u c t i o no fb s p l i n es u r f a c eb yas e to fg i v e np o i n t si si m p o r t a n ti s s u ei n c a g d ，t h et r a d i t i o n a lw a yi sl e a s ts q u a r em e t h o do fe r r o r sb a s e do nm i n i m i z i n gt h ee m p i r i c a lr i s k 。 t h i sp a p e rp r e s e n t sal e a s ts q u a r e ss u p p o r tv e c t o rm a c h i n e sa p p r o a c ht os o l v et h ep r o b l e mo ff i t t i n g b - s p l i n es u r f a c e ，w h i c ho p e r a t e s0 1 1t h ep r i n c i p l eo f s l t t a c t u r er i s km i n i m i z a t i o ni n s t e a do f t h ee m p i r i c a l r i s km i n i m i z a t i o n ；h e n c eab e t t e rg e n e r a l i z a t i o na b i l i t yi s g u a r a n t e e d am a t h e m a t i c a lm o d e li s e s t a b l i s h e d ，a n dan e wk e m e lf u n c t i o ni su s e dt oo b t a i nt h ec u r v e sb yb s p l i n ef o g i n o u ro e wm e t h o d p r o v i d e sa n e wf i t t i n gw a yf o rc a g d n n u m e r i c a le x p e r i m e n t ss h o wc l e a r l yt h ef e a s i b i l i t y k e y w o r d s ：s i m u l a t e d a n n e a l i n g ；g e n e t i c a l g o r i t h m ；s u p p o r t v e c t o r m a c h i n e s ；b - s p l i n e ；f i r i n g i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特另f j d i ：i 以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得中国农业大学或其它教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示了谢意。 研究生签名：弧碾梅时间：丑嘭年月陟曰 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同媒体上发表、 传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：张艰7 酶时间：2 彤年f 月侈日 导师签名 1 - v 7 刀0 时间：2 鲫# 年；月，1 曰 第一章绪论 1 1研究数据点提取和拟合的意义 市场全球化使国家、企业面临的竞争日趋激烈，市场经济竞争机i t l 0 已渗透到各个领域，随着 科学技术的高度发展，科技成果的应用己成为推动生产力发展和社会进步的重要手段。如何更快、 更好地发展科技和经济，世界各国都在研究对策。充分利用别国的科技成就加以消化和吸收刨新， 进而发展自己的技术已成为普遍的手段。事实证明，技术引进是吸收国外先进技术，促进民族经 济高速度增长的战略措施。有关统计资料表明，在机械产品外形的计算机辅助设计和制造 ( c a d c a m ) 领域，各国百分之七十以上的技术都是来自外国，要掌握这些技术，正常的途径 都是通过逆向工程。实际上任何产品问世，不管是创新、改进还是仿制，都蕴涵着对已有科学、 技术的继承、应用和借鉴。因此研究逆向工程技术，对我国国民经济的发展和科学技术水平的提 高，具有重大的意义“j 。 逆向工程技术常常应用于以。1 - 领域； 当机械零件的外形没有设计图纸或者设计图纸不完整，以及没有c a d 模型的情况下，需要 应用逆向1 程技术在对零件实物外形进行测量的基础上形成零件的设计图纸或c a d 模型，并以 此为依据生成数控加工的代码，加工复制出一个外形相同的零件。 当要设计需要通过实验测试才能定型的工件模型时，通常采用逆向工程的方法。比如航空航 天领域，为了满足产品对空气动力学等要求，首先要求在初始设计模型的基础上经过各种性能测 试( 如风洞实验等) 建立符合要求的产品模型，这类零件一般具有复杂的自由曲面外型，最终的 实验模型将成为设计这类零件及反求其模具的依据。 在美学设计特别重要的领域，例如汽车外型设计广泛采用真实比例的木制或泥塑模型来评估 设计的美学效果，而不采用在计算机屏幕上缩小比例的物体投视图的方法，此时需用逆向工程的 设计方法。 另一个重要的应用如修复破损的艺术品或缺乏供应的损坏零件等，此时不需要对接个零件原 型进行复i t i 0 ，而是借助逆向工程技术抽取零件原形的设计思想，指导新的设计。这是由实物逆向 推理出设计思想的一种渐近过程。 数据点的提取和拟合是逆向工程里最重要的两项技术，提取和拟合的效果直接影响着逆向工 程中机械产品的造型。 1 2数据点提取和拟合技术的研究现状 经过近2 0 年的研究，基于计算机辅助设计的实物逆向工程技术在机械产品开发中取得了广 泛的应用，但逆向工程技术仍处在发展之中，许多问题有待解决。 数据拟合的目标是根据离散的数据点构造出一个分段光滑、连续的模型。为使拟合工作准确、 快速，在数据拟合之前我们应该了解实物对象的一些整体属性，如测量数据的组织形式，实物形 状的几何特征信息，以及构成表面的曲面片类型等，在此基础上选择合适的数据处理手段和曲线、 曲面拟合方案“。 ( 1 ) 形状的整体属性 根据测量数据的测量组织形式，数据点可分为规则点和散乱点。散乱点主要是由手动和随机 测量造成；对形状表面的截面扫描得到的一般是规则点。对其拟台得到的是= 维曲线，并且由于 规则点隐含了相邻的信息，较易进行数据去噪、平滑处理，能方便地进行数据点的参数化。 ( 2 ) 数据提取 在曲线曲面拟合之前还要进行的工作是数据提取。在实际的机械产品中，只由一张曲面构成 的情况不多，产品形面往往由多张曲面混合而成，由于组成曲面的类型不同，所以c a d 模型重 建分解为：先分别拟合单个曲面片，再通过曲面的过渡、相交、裁减、倒圆等手段，将多个曲面 缝合成一个整体，即重建模型。b e s l 和j a i n 于1 9 8 5 年对数据提取方法作了较好地【司顾，总结如 下：数据提取是将测量数据分类转变成为造型数据，方法是根据每一个自然曲面，将测量点分割 同时并能够决定每一个点集属于哪一种曲面。由于曲面预先确定的困难，数据提取、分类和曲线、 曲面的拟合三种情况并不是顺序进行的，有时可以是同步进行。例如要判断某个点是否属于一个 确定点集，要通过这个点与由点集拟合而成的曲面片是否匹配来判断。l e o n a r d i s 在1 9 9 5 年提出 了“并行考虑三种情况，通过求解优化问题来寻求最佳结果”的方法。目前存在两种基本的提取 方法：基于边( e d g e b a s e d ) 和基于面( f a c e b a s e d ) 的数据提取方法。 基于边的方法首先是从数据点中，根据组成曲面片的边界轮廓特征、两个曲面片之间的相交、 过渡特征，以及相撞表面曲面片之间存在的棱线或脊线特征，确定出相同类型曲面片的边界点， 连接边界点形成的边界环，判断点是处于环内还是环外，实现数据提取。基于边的技术必须考虑 下列问题：寻找边界特征点，主要是由数据点计算局部曲面片的法矢量或者高阶导数，通过法矢 的突然变化和高阶导数的不连续来判断一个点是否是边界点。因为反射光以及边界附近的曲率变 化大，靠近尖锐边的测量数据是不可靠的，而且可用于提取的点的量少，只有接近边的点是可用 的，这意味着判断依据对“假”数据具有较高的敏感性，同时找出具有相切连续或者高阶连续的 光滑边也是不可靠的，因为基于噪声点的计算容易产生错误的推理结果，如果对数据进行光滑处 理，叉会使推理结果失真，丢失特征位置。 基于面的技术是确定哪些点属于某个曲面，这种方法和曲面拟合结合在一起，在处理过程中， 这种方法同时完成了曲面的拟合。因此，相比较基于边的方法，基于面的方法是数据提取中具有 发展前途的一种技术。 事实上，数据提取和曲面拟合是一对矛盾的统一体，如果知道将要拟合的是哪一种曲面，我 们能立即判断出分属于它的数据点；反之，如果确切的知道属于一种曲面类型的数据点集，根据 点集，我们能拟合出最优的曲面。不幸的是，两个过程并不是独立的，多数场合f ，我们既不知 道曲面类型，也不能划分数据点集，只能在两个过程的并行中，反复计算，寻求符合要求的结果。 ( 3 ) 基于曲线的曲面重建方法 基于曲线的曲面重建方法的原理是在数据提取的基础上，首先由测量点插值或拟合出组成曲 面的网格样条曲线，再利用系统提供的放样、混合、扫掠和四边曲面等曲面造型功能进行曲面重 建，最后通过延伸、求交、过渡、裁减等操作，将各曲面片光滑拼接或缝合成整体的复合曲面模 型。 基于曲线的曲面重建方法实际上是通过组成曲面的网格线来构造曲面，是原设计的模拟，在 预知曲面特征信息，如原曲面类型、构建方式等时，能准确地重建原模型的拓扑特征，对规则形 2 中国农业大学硕士学位论文 第一帮绪论 状物体是一种有效的模型重建方法。如果模型是自由曲面组成的复合曲面，其几何拓扑信息难畎 扶实物及数据模型中毡计，采用基于鼗缝的黩嚣重建方法反复交互选取基殛避型克式，馕掏建豹 曲面片满足光滑和精度的要求。 蒸于蘸线静藏甏重建方法簧隶截露扫描灏量，截瑟尽整帮黻嚣懿礴线或藏覆搀拣鞔避线垂 直，测量数据点分布均匀，最好是u 、v 两个方向都进行截面捆描，假在曲两数学模型未知的情 况下较难做副。 ( 4 ) 基于测量点纛接搬愈魏麴嚣造型党法 基于测燃点的曲面重建方法是直接建立满足对数据点的插值或拟含曲面，既能处理规则点也 能直接投合散乱点，它有鲡下抗点：在大量褥数据点上工作，支持蟊辩点酶簸佳攒台。在簖落鬟 建中，能够构造出作为标准的b 样条曲面，并且最终的搬面表选式也较为简浩。 如对大规模、散乱的型值点，直接拟合方法是首先根据边界构造一个初始曲面，然后将型债 轰投影裂此魏囊土，撮据授影艘置葵囊萁参数分毒，软嚣解决教嚣数据戆参数分配耀遂；摄撂掰 的参数分配，拟台出一张新的b 样条曲面，然后，樽对型值点参数进行优化，使得所拟台曲面离 给定型值点的偏琵最小。 1 3各辈内容安排 本文的内容安摊如下： 第一章为绪论，依次论述了数据提取与拟合的研究意义和研究现状。包括数据提取与拟合的 定义和方法的橇述，并指出本文要研究的内容和所簧做的主要工作； 第二章论述数援点的提取方法，搿要贪缨了模拟退火簿法鄹遗传算法，磐分析了这两种算法 的优缺点，提出了用模拟退火：i 藏传算法对空间测量数据点进行二次曲面的提取； 第三章扼要论述了支持自量棍，棱瓣数葶鞋最，l 、二乘支持囱量梳，并给窭了凫静攀耀匏棱丞数； 第四章介绍了b 样条基豳数，及其在曲线曲颟拟合中的应用，常用的曲线曲蕊拟合方法实质上是 基于“经验风险”意义下的最小二乘拟舍，本文提出了基于“缩构风险”意义下- 用簸d 、- - 乘支持 趣量豳归规搀逢b 榉条曲线麴掰的拟台方法，其出发点是矮小他缝掩风险， i 疆不是转统学习熬经 验风险最小化： 第五章为对本文工捧鹣墓藉，鼓及迸一多工伟鹩建议。 本文所作的主蔡工作如下： 一、简要介绍模拟退火算法和遗传算法，并分析了这两种算法的优缺点，提出了用模拟退火 建抟算法对空翔测整数据点进舒二次藩嚣教提取。 二、介绍了b 样条基函数，及其在曲线曲面拟含中的成用。常用的曲面拟合方法实质上是基 于“经验风险”意义下的最小二莱叛台，本文提出了基于“结构风险”意义下用最小二乘支持蠢 壁固姻机构造b 榉条曲线曲厦的拟合方法。 ，i l l 篮l l l l 型筌鎏篮翟盗。三t 型鲨坠凿羞翟譬磐三1 皇_ 第二章用模拟退火遗传算法提取二次曲面 奉章毙篱要讨论了横羧逶炎蒸法翥蘧传箨法静往煮秘获蠡，然辩将嚣静方法稿结合，瘸子提 取空间测擞数据点中的二次曲面。 2 。1模拟退灭篝法及模塑 退火悬一种物理过程，一种鑫属物质在加热至一定的温度后，它的所有分子在状态空间d 中 是蠹运动e 憝羲温度黪下洚，这熬分子运濒掺警在n n n 状态。在滋痍最羝露，分子重裁秘一定 的结构排列a 由统计力学的研究表明，在温度r ，分子停留在状态r 满足波兹援概率分布 鞭睁，) = 丽1e 印卜害) 协t ， 其中e ( r ) 为状态，的能量，k 8 为波兹曼常数，茁为分子能量的一个随机变量，z p ) 为概举分布 爨标准讫因子f ”1 。 因为 所以 其州班驴 - 剖 先研究由( 2 1 ) 确定的函数隧r 静变德鹣势。遥定嚣个能鬟蕊鲮，在丽个溢度r ，有 p r p = 罨 n 荔= 疋 = 丽1 唧卜珊o x p e 训2 - e 1 测，( 等) g ( p 2 ) ，但是卢。e x p f 一丛曼掣1 大于事先给怒的闽值，则选择子代，否则 l 选择父代5 肖g ( p 。) 和g ( p ：) 都大于g m 的时蛱。如果g ( p j ) o ，u 0 ， = 0 , i ，h + 。这撵戆萤点矢量定义了驽匈b 徉条基。 对节点矢量u = 【u o ，“l ，一，i i n m 。】，常见的零次、一次、二次和三次1 3 样条旗函数的具体表达 式如下： 啊，。c “，= f ：；啬：嚣； ，= 。，一+ t 中尉农业大学硕士学位论文第四章用最小二：乘支持向量机对空阀数据点的b 样条拟台 玛，：“) = 辑，( “) = m 。( “) = “一瓴 坼“， 毽。2 一# 坞+ i 一虬 o u e # i ，1 ) ”h + u i + 2 ) i = o ，l ，n + l 其它 和一辑r ( m + 。一m ) ( “一) 垡二堕i 垃：! 二塑斗垫二坠! ! f 坠! 二堕 辑+ t 一埤) ( 埤+ ：z 4 i + ；) ( 毽+ ，一z k ，) ( 毽+ ：一毽+ ；) ( u j + ，- u ) 2 ( 玛托一坫) ( q “一砖) 0 “f 辑，坼“) “【4 i + l ，u j + 2 ) 【辑a 毽+ ，) 荬它 f = 0 ，1 ， + 1 i i 熹兽面j ， 吲辑峨) ( 强+ 3 一辑) ( 坼+ 。一蚌) ( 酶辑) “ 咋“瑚 ! 兰兰! ：f 坠i 二“。( “一毽) ( “一；b ；) 辑+ ，一“) ( 辑”一q ) ( + ：一) ( 珥+ 。屿+ 。) ( m + ，一虬) ( 虬+ ，“。) ( “。一d i + ) 4 i + 2 , 叶3 ) 拈【垮+ 3 ，埤“) 冀它 i 一0 ，l ，n + 1 这个定义其有蔷速性，既适裙均匀节点组，叉适焉非均匀节点组；既适用非重节点缀，又适 翅会重复节点的组。出此出发，可导班各秽形式的b 撵条基遗数。 4 1 2 均匀b 祥条基酾数 由节点矢量确定的均匀b 样条基在定义域内嚣个节点区间上都有相同的剿形，其中任一节点 区间上的b 样条基都可由粥一节点区间上的b 样条基经平移得到。但在艇体参数意义下它们却其 毒不嚣豹表述式。为魏，霹将定义在每个节点区阀沁，辑+ 矗上雳繁体参数# 表零豹b 撵袈基按成 2 l 中国农业大学硕士学位论文第四章用最小二乘支持向量机对空间数据点的b 样条拟台 局部参数t o ，1 1 表示口”。 根据b 样条基的递推定义，作参数变换 “= “( f ) = q + r ，“【坼，m + 。】，【o ，l 】；f = t ，k + l ，n 变换的结果将使所有节点区间上的b 样条基都具有统一的数学表达式。即对于k ，u i 。】上的k + 1 个t 次非零的b 样条基函数 。( “) ，。，。( ”) ，j 。( ”) ，变换成为 五j ( r ) = j 。 ( “( r ) ) ，f 【o ，l 】，j = o ，1 ，2 ，t 五j ( f ) ，j = o ，1 ，2 ，k 的表达式可由上述变换得到。其中五( r ) ，= o ，l ，2 ，k 可以写成矩阵的形式 ( 矗。( f ) 正，( f ) ，。( r ) ) = l lft 2 t f m 其中1 3 次系数矩阵为 14 30 36 一l3 10 30 30 3l 常见的一次、二次和三次均匀规范b 样条基函数的表达式如f ：其中f f o ，1 1 一次均匀规范b 样条基函数 ，。( f ) = 1 一f ，石。( f ) = ， 二次均匀规范b 样条基函数 f o ，：( f ) ；( 卜r ) 2 2 ，z ，：( f ) = ( 1 + 2 卜2 t 2 ) 2 ，五，：( f ) = f 2 2 三次均匀规范b 样条基函数 五，( r ) = ( 1 一f ) 3 6 ，彳，( f ) = ( 4 6 t 2 + 3 t 3 ) 6 正，( f ) = ( 1 + 3 f + 3 f 2 3 t 3 ) 6 ，正，( f ) = r 3 6 ( 4 - 2 ) 4 1 3 b 样条基函数的性质 b 样条基函数具有一系列良好的性质口5 2 9 , ”1 ，简介如f ： 1 ) 递推性：由定义不难发现，高次b 样条可在低次b 样条的基础上推导出来； 2 ) 对称性：均匀b 样条的图形左右对称： 3 ) 局部支承性质： 砌，瞰：譬黜 既第i 个t 次b 样条仅在节点t i 。的女+ 1 个区间内不为零，而其余区间内均为o 。 4 )凸组合性质： m 。( “) = 1 该性质又称为规范性或权性，是指次b 样条的总和恒为1 。 5 ) 可微性与连续性：b 样条在节点区间内是无限次可微的；在节点处可达到k r 阶连续 这里r 为节点的重复度。 一引 i | m 卟l到 2 00 ，。l l 一2 i | 峨 习p = m 中国农业大学硕士学位论文第四章用最小二乘支持向量机对空间数据点的b 样条拟龠 6 ) b 样条跨越的节点区间数为k + 1 ，k 为b 样条的幂次，故样条所跨越的区间数随幂次的 搀离嚣扩大；样条熬蹇发隧幂次浆握崧磊薄低，毽群豢耩毽基瓣垂积憔为l 。 4 1 4 b 祥条麴线 设m j ) ，“【o ，l 】，i - - 0 “1 - k ，表示女次均匀规范b 样条基函数，最，i = 0 , 1 ，t 表示控制多 边形的顶点，则一段女次均匀b 样条曲线可以表示为口7 】 ，和) = 霉越，。和)“e 【。，l 】( 4 - 3 ) p o ) = 鼋( “)”t 【o ，1 l 蒯考托悯 4 1 5 b 样条曲面拟禽 b 样条曲面拟台就是要构造张kx f 次b 样条曲面来拟合给定数据点n ，i = 0 ，1 ，删；，= 0 ，l ，。遽常，类钕热线羧舍，我搦使数据悫证予滔角豹四个数撂煮稼为夔张越蕊的西个角煮， 使其它数据点成为相应的相邻曲面片的公共角点。这些数据点阵中每一排数据点就都位于曲面的 一条婷参数线上。曲谳拟合问题最然也能像曲线拟台那样，表达为求解未知控制顶点 ；f = 毽l ，m + k l ，j ；o 1 一，# + ，1 静一个线憋方翟维，但这线性方程缀往挂j 建于庞火，绘 求解殿在计算机上的实现带来困难。殿一般的方法是表达为张最积曲面计算的逆过程。它把曲面 的掇仓褥蘑纯解为话个参数方蠢鲍益线襁台简嚣 2 5 0 9 3 0 l 。待求的b 样祭海爵磷绫写为 p 融0 = 又可改写为 “一i ，辑，。鳓弼，( 0 ( 4 - 4 ) 。o * 十女一l ，# 十j l、 p ( “，0 = i 磷，啊，。( v ) i ，。( “) ( 4 - 5 ) i = 0 、j = 0， 于是给出类似丁b 样条曲线的表达式 mh 一t p ( u ，v ) = xq ( 螭，。( “) ( 4 6 ) r ! o 这墨羟案l 谈患被下述控镧魏线蕊代替 中国农业大学硕士学位论文第四章用最小二乘支持向量机对空间数据点的b 样条拟台 n + j 一1 g v ) = 吐，j ，一) ，i = o ，1 ，m + k l ( 4 7 ) j = 0 若圈裳一参数毽v ，就绘出了在这些控裁鳇线上m + 女个患o ) ，i = 0 , 1 ，m + k 一1 。这些点又终 为控制顶点，就定义了曲面上以“为势数的等参数线。当参数v 值扫过整个定义域时，无限多的 等参数线就描述了整张曲面。羲然，曲面上无限多鞋“为参数的等参数线中有n + 1 条熬合给定 的数据点，其中每冬插值数据点阵的一列数据点。这n + 1 条等参数线就是截面曲线。于是就可 以由b 样条曲线拟合求出这些截面曲线的控制点z f = o ，l ，晰+ t 一1 ；j = o ，l ，n + l 一1 。 m + 一i 。，冁。) = 乏。，m ，( 。) = a ， r = o i = o ，l ，m ；j = o ，l ，h + ，一1 ( 4 1 8 ) 一张以这些截斌曲线为它的等参数线的曲面要求一缀控制曲线用来定义截面曲线的控制顶 点c ，( u + ，) = z i = o “1 ，m + k l ；j = 0 , 1 ，n + l 一1 。类似曲线拟合，我们这里选择了一组v 参 数毽毪。j = o j ，h 为控制麴线约节点，郅数据点致，豹v 参数佳。予是，这个朗题戴毅表达为 m + k 条插值曲线的拟合问题 n + l 一1 。辑，0 + ，) = 毒1 = 0 , 1 ，n + l 一1 ；i = o 1 ”，m + k 一1 ( 4 - 9 ) ，o 解这蝗方程组，我们得到所求b 样条拟合曲面的+ ) x 0 + ，) 个控制顶点i = 0 ，l ，1 ”，m + 女 l ；，* 0 , i ，h ? l 。翻4 - 1 绘囊了b 徉条癌瑟整合过稳熬基辩。 ( a ) ( b ) ( c ) 图4 - 1b 样条曲面拟台 ( a ) 截面曲线及其控制多边形 ( b ) 控制曲线及其控制多边形 ( c ) 插值曲面殛其控制网格 4 2用最小二乘支持向量机对空间数据点的b 样条拟合 由给定的空间数据点构造b 样条曲线是计算机辅助几何设计中一个重要研究课题，常用方法 是插值和逼近。“。插值曲线顺序通过给定的数据点，当数据点分布不均匀，或带有测量误差时， 插值曲线常会发生扭曲和振荡”“。如采用逼近方法，即不要求曲线通过每一个数据点，而是逼近 由这些数据点顺序构成的数据点多边形，那么问题将会得到很好的解决。2 。但新的问题是如何 衡量逼近的程度呢? 常用的办法是引入一个简单的概念“离差”。离差是指给定的数据点与它在 曲线上相应的参数点之间的距离。如果所有给定数据点的离差之和最小，则认为曲线最好地逼近 了所给的数据点多边形。这实质上是基于“经验风险”意义下的最小二乘逼近，本节讨论基于“结 构风险”意义下用最小二乘支持向量回归机( l e a s ts q u a r e ss u p p o r tv e c t o rm a c h i n e s ，以下简称 l s s v m s ) 整体构造b 样条曲线的逼近问题，其出发点是最小化结构风险，而不是传统学习的经 验风险最小化，从而在理论上保证了好的推广能力，实现对原始曲线的逼近而不仅仅是对测量数 据点的逼近。 4 2 1 整体b 样条曲线逼近 设给定“1 个空间数据点 s = 只= ( 墨，咒，4 ) ：o ( 4 - 1 0 ) 这里一yz ，r ，i = 0 , 1 ，。求一条由m + 1 个控制顶点定义的k ( k 1 ) 次b 样条曲线，使得满足 以下条件 ( a ) 曲线通过第一个和最后一个数据点，即只和异， 伯) 曲线在昂小化结构风险意义下逼近数据点。 为了求得k 次b 样条曲线，需确定定义b 样条基函数的节点矢量和数据点的参数，这可通过参 串蚕农韭夫学颈士攀靛论文第器章舞最，l 、二黎嶷持彝量极瓣空闻鼗嚣杰静b 样条接台 数化给定的数据点集来确定”1 ，设数据点的参数为0 = _ o 鞴薪= 1 ，所求次b 样条曲线 为 p o ) = ( x 国x ，o ) ，2 ( “) ) = n 似) 一 ( 4 _ 1 1 ) j ；0 其孛蘸r 3 ，i = o ，l ，m 必m + 1 个特求黪援铡褒焘。因灸要求藏线经过第一个和最嚣一个样本焘， 所陵第一个窝簸璐个控制硬点满莲d o = 嚣，= 霉，虽女次b 荦条基函数蛹i 承) ，f = 0 , 1 ，m 由节 点矢量u = o i 0一咋，。“+ = 1 ) 所定义。因此仅有m 一1 个特定躺控制顶点 d l ，吐，办l 故可改写( 4 - 1 1 ) 式为 p ( “) = ( x ( “) ，y 国) ，“ ) ) = ，。“) 矗+ t 扣) 4 + 以，( “) # ( 4 1 2 ) i = l 在( 4 - 1 2 ) 式审，烈砷一般是关子参数u 豹菲线性交数，教努缳s l 入菲线犍鲮蘩将魏嚣线淫霞扫 翊疆转纯芳赢缀空闽中豹线性回归阉瑟，然蜃才能魇l s s v m s 避行求解。鸯了餐诞暖归舞线豹 b 样条表示形式，我们引入f 面的特定映射和特定的核函数。 定理1 设映射妒：h r 斗妒( “) 昔r 卅1 ，( 肌兰2 ) 定义为 伊( ”) 一( m ( ”x n 2 , t “) ，n m “女( ) 1 ( 4 - 1 3 ) 划殃射p 对应鹄梭殛数( 我们称之为b 榉祭梭) 为 m - 1 k ( u ，k = ( 烈“ 妒“= 辑，国) 越( ( 4 - 1 4 ) 其中”矿r 。 证明 v g ( u ) e 岛( r ) ，k ( u ，“ 如( r ) 固如( 釉， 琏。如置沁”) g ( u ) g ( u ) d u d “ = 珏舭。( 薯k 。和冷时秘， g ( u ) g ( u w 避” 喜( 咖删妇 2 。 ( 4 - 1 5 ) 式秘1 5 ) 涯鹈了式洚1 3 ) 瀵是m e r c e r 条锫，怒棱番数。 对数摆集( 4 1 参数纯蓐，霹褥掏逡转样条回归蠡线蹬一1 2 ) 的样零集 s = ( 蜥，丘) ：= o( 4 - 1 6 ) 这里输入“，er ，输出只= ( 而，m ，弓) 搿，i = 0 , 1 ，。 下面只对回j 驹曲线( 4 - 1 2 ) 中x ( u ) 的构造方法进行描述，y ( u ) 和z ( u ) 的求解方法类似。在殃射 ( 4 1 3 ) 卜，矮可表示为 j ( # ) = 甄l ( # ) 嚣，十1 j 嵇) 最；+ ( 琏p 焉p ，。吨，) 薮# ) 4 - 7 ) 其中昂，毋，表示酋、末数据点岛，鼻的第一个坐标分量，叫矾，嚷。n 表示特求的m 1 个 控制顶点的第一个坐标分量，记p x ( u ) = n o ，i ( “) 岛，+ n 础( ”) 一k = ( 吐如，靠l ，) 7 ，则 ( 4 1 7 ) 可重写成 孛黧农业大学硬士学位论文第艘章髑摄小二黍支持内量帆对空阕数撼点豹b 样条拱合 珊= 砭( # ) + 烈啦 秘- 1 8 ) 下面我们来求记。遮时与优化问题( 3 * 2 1 ) 和( 3 2 2 ) 对应的优化问题为 满足懿麴粜条掌 是 雩挚“w ，。= ；k + 詈芸 ( 4 - 1 9 ) 薯= 醪；鳞) + 毒( 磷) + 辱，i = 1 , 2 ，f l ( 4 - 2 0 ) 构造鲤下鲍l a g m n g i a n 醒数 j 一1 三( 毪，五) = 。，( 致，e ) - 墨 壤7 烈砩) + 曩( 酶) + 謦一薯 ( 4 - 2 1 ) ，= l 其中l a g r a n g e 浆子是r ，f = l ，f 一1 。根据最优性条转可缮关予毒懿如下线性方程组 + k ( u ，m )g ( u ，) k ( u ，“。) 1 f k ( u 。，蚝) 争+ 置枷：，# ：) 嚣毋：，h “， l 南 并扭h ，峨)美瓯t ，毪) 手+ k ( u t _ t ，口p l 竣 j- 0 ； ( 4 - 2 2 ) 其巾匏并0 ，0 裁是b 榉条援，接( 4 1 4 ) 撼t 舞。解方程缝媾1 2 2 ) 可褥z ，r = l ，2 ，t 一1 ，心拟台出韵b 样条曲线的第一个分量x ( “) 可表示为 i - t “) = 乏( # ) 薮“) = e ；( # ) 嚣，十甄，；( ) 霉，+ 焉爱魄，#