（应用数学专业论文）nurbs曲线曲面的小波分解与重构.pdf

哈尔滨理工人学理学硕士学位论文 n u r b s 曲线曲面的小波分解与重构 摘要 n u r b s 曲线曲面造型技术和小波方法都是上世纪八十年代发展起来的 新兴技术，小波方法具有很多其他方法无法比拟的优点，将小波方法应用于 n u r b s 曲线曲面的造型，在曲线曲面造型领域是一种新的突破，并且得到 相当不错的效果，因此对基于小波的曲线曲面的造型技术的研究尤为重要。 本文主要研究均匀b 样条曲线与曲面小波分解与重构的算法，准均匀 b 样条曲线曲面的小波分解与重构快速算法，以及n u r b s 曲线小波分解与 重构的新算法。具体包含以下内容： 对准均匀b 样条曲线小波分解算法进行研究，给出准均匀b 样条曲线 及曲面小波分析思想，并尝试将准均匀b 样条曲线小波分解与重构的算法 延拓到b 样条曲面上来，对该算法进行补充研究。 在准均匀b 样条曲线曲面小波分解与重构的基础上对均匀b 样条曲线 曲面小波分解与重构进行研究，实际上均匀b 样条曲线曲面小波分解和重 构与准均匀b 样条曲线曲面小波分解和重构的区别就在于均匀b 样条曲线 曲面在经过小波分解以后所得到的小波在定义域边界与内部可以采用统一的 表达式。在进行小波重构时仅需作乘法运算。 给出n u b s 曲线曲面多分辨造型技术，并对已有研究成果作进一步研 究和改进。 提出了半j 下交b 样条小波分解和重构的新算法。同时给出了处理非均 匀有理b 样条曲线的整数阶与非整数阶分辨率的小波分解和重构算法，并 实现了任意非均匀有理b 样条曲线的多分辨率表示，对于任意非均匀有理b 样条即n u r b s 曲线，无论它有多少个控制点，均可以对它进行半证交分解 和重构，而不受控制点数必须等于2 + 3 的限制。从这个意义上讲，该方法实 现了连续分辨率水平的非均匀b 样条曲线造型，并且对非均匀有理b 样条 即n u r b s 曲线进行精确的分解和重构。 关键词准均匀b 样条；均匀b 样条；n u r b s 曲线曲面；小波分解与重 构 哈尔滨理下大学理学硕十学位论文 w a v l e t a n a l y s i sa n d r e c o n s t r u c t i o no fn u r b s c u r v e sa n ds u r t a c e s j 1 一f 、 一 a b s t r a c t t h em o d e l i n gt e c h n o l o g yo fn o n - u n i f o r mr a t i o n a lb s p l i n e ( n u r b s ) c u r v e s a n ds u r f a c e sa n dt h ew a v e l e tt e c h n o l o g ya r en e wt e c h n o l o g i e sd e v e l o p e di nt h e l9 8 0 s t h ew a v e l e tm e t h o dh a sm a n ya d v a n t a g e sw h i c ht h eo t h e rm e t h o d sc a n n o tb ec o m p a r e dw i t h u s i n gw a v e l e tm e t h o dt om o d e lb s p l i n ec u r v e sa n d s u r f a c e s ，w eh a v eg o tm a n yg o o dr e s u l t s s ot h er e s e a r c ho fm o d e l i n gt e c h n o l o g y o fc u r v e sa n ds u r f a c e sb a s e do nw a v e l e tm e t h o di sv e r yi m p o r t a n t t h ed is s e r t a t i o nr e s e a r c h e sm a i n l yt h ea l g o r i t h m so fw a v e l e td e c o m p o s i t i o n a n dr e c o n s t r u c t i o no fp r e - u n i f o r ma n du n i f o r mb s p l i n ec u r v e sa n ds u r f a c e sa n d n e wa l g o r i t h mo fd e c o m p o s i t i o na n dr e c o n s t r u c t i o no fn u r b sc u r v e s t h e c o n t e n ti sa sf o l l o w s ： t h ea l g o r i t h mo fw a v e l e td e c o m p o s i t i o na n dr e c o n s t r u c t i o no fp r e - u n if o r m b s p l i n ec u r v e sa n ds u r f a c e si ss t u d i e d t h ei d e ao fw a v e l e ta n a l y s i so fp r e u n i f o r mb - s p l i n ec u r v e sa n ds u r f a c e si sg i v e n ，a n dt h ea l g o r i t h mo fw a v e l e t c o m p o s i t i o na n dr e c o n s t r u c t i o no fp r e - u n i f o r mb - - s p l i n ec u r v e sa n ds u r f a c e si s t r i e dt oe x t e n dt ob s p l i n ec u r v e sa n ds u r f a c e s t h ec o m p l e m e n t a r yr e s e a r c hi s m a d eo nt h i sa l g o r i t h m b a s e do nt h e a l g o r i t h mo fw a v e l e tc o m p o s i t i o n a n dr e c o n s t r u c t i o nr e u n i f o r mb s p l i n ec u r v e sa n ds u r f a c e s ，r e s e a r c ho nt h ea l g o r i t h mo fw a v e l e t d e c o m p o s i t i o na n dr e c o n s t r u c t i o no fu n i f o r mb - s p l i n ei sm a d e a c t u a l l y ，t h e d i f f e r e n c eb e t w e e nt h ew a v e l e ta n a l y s i sa n dr e c o n s t r u c t i o no fu n i f o r mb s p l i n e a n dr e u n i f o r n l b - s p l i n e c u r v e sa n ds u r f a c e si st h a tt h ew a v e l e ta f t e r d e c o m p o s i t i o no ft h eu n i f o r mb s p l i n ec u r v e sa n ds u r f a c e sc a nb ee x p r e s s e d c o n s i s t e n t l yi nt h ed o m a i na n do nt h eb o u n d a r y t h em o d e l i n gt e c h n o l o g yo ft h em u l t i - r e s o l u t i o ne d i t i n go fn u b sc u r v e s a n ds u r f a c e si sg i v e na n dt h ee x i s t i n gr e s u l t sa r er e s e a r c h e df u r t h e ra n di m p r o v e d 一i l 哈尔滨理t 大学理学硕一f j 学位论文 暑皇暑詈詈詈毫皇量詈皇詈詈詈皇葛量暑詈鲁兽詈詈穹皇皇= 暑亭墨詈暑詈皇皇暑毫阜葛暑鲁= = = = = 墨i m 詈詈詈詈詈詈墨篁詈皇詈皇鲁寡暑詈= 暑鼍詈暑= 鼍詈暑皇毫詈鼍 t h en e wa l g o r i t h mo fw a v e l e tc o m p o s i t i o na n dr e c o n s t r u c t i o no fs e m i - o r t h o g o n a lb - s p l i n ei sr e s e a r c h e d a tt h es a m et i m e ，t h ea l g o r i t h mo fw a v e l e t c o m p o s i t i o na n dr e c o n s t r u c t i o no fn u r b sc u r v e sw i t hi n t e g r a lo r d e ra n dn o n - i n t e g r a lo r d e rr e s o l u t i o n si so b t a i n e d a n dt h ew a v e l e tc o m p o s i t i o no fa r b i t r a r y o r d e rn u r b sc u r v e si sr e a l i z e d f o ran u r b sc u r v e ，s e m i o r t h o g o n a l d e c o m p o s i t i o na n dr e c o n s t r u c t i o nc a nb ed o n ew h e t h e r t h e r ea r eh o wm a n y c o n t r o lp o i n t sw i t h o u tt h el i m i t so ft h ea m o u n to fc o n t r o lp o i n t s i nt h i ss e n s e ， t h ea l g o r i t h mr e a l i z e dt h em o d e l i n go fc u r v e so fc o n t i n u o u sr e s o l u t i o na n dt h e a c c u r a t ec o m p o s i t i o na n dr e c o n s t r u c t i o ni sm a d ef o rn u r b sc u w c s i nt h i ss e n s e ，t h ea l g o r i t h mr e a l i z e dt h em o d e l i n go fc u w c so fc o n t i n u o u s r e s o l u t i o na n dt h ew a v e l e tc o m p o s i t i o na n dr e c o n s t r u c t i o no fn u r b sa c c u r a t e l y w i t h o u tt h el i m i t so ft h en u m b e ro fc o n t r o lp o i n t s k e y w o r d sp r e - u n i f o r mb s p l i n e ，u n i f o r mb s p l i n ec u r v e s ，n o n u n i f o r mr a t i o n a l b s p l i n ec u r v e sa n ds u r f a c e s ，w a v e l e tc o m p o s i t i o na n dr e c o n s t r u c t i o n i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文n u r b s 曲线曲面小波分解 与重构，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已 发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文 中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：i 岛曰易农 日期： 彬7 年4 月吕日 哈尔滨理工大学硕士学位论文使用授权书 ( ( n u r b s 曲线曲面小波分解与重构系本人在哈尔滨理工大学攻读硕士 学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工 大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔 滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交 论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用 影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密d 。 ( 请在以上相应方框内打4 ) 作者签名：i 岛喀灰 日期：矽移年历月名同 导师签名：叁垧娟每日期：卵年垆月矿日 哈尔滨理f t 人学理学硕，i j 学位论文 1 1 研究目的及意义 第1 章绪论 计算机辅助几何设计( 英文缩写是c a g d ) 是一门迅速发展的新兴学科，它的 出现和发展既是现代工业发展的要求，又对现代工业的发展起到了巨大的作 用。它使几何学从传统时代进入数字化定义的信息时代，使其焕发出勃勃生 机。c a g d 的核心问题就是解决工业产品几何形状的数学描述。而要解决此问 题，就必须要以描述参数曲线曲面为基础，即寻找描述曲线曲面的最优方法。 自二十世纪八十年代中期以后，国际上就看准了这个领域内最有发展前景的非 均匀有理b 样条( n o n - u n i f o r mr a t i o n a lb s p l i n e ，简称n u r b s ) 方法。国际标准 化组织( i n t e r n a t i o n a ls t a n d a r d i z a t i o no r g a n i z a t i o n ，简称i s o ) 于1 9 9 1 年正式颁布了 关于工业产品几何定义的s t e p ( s t a n d a r df o rt h ee x c h a n g eo f p r o d u c tm o d e ld a t a ， 产品模型数据交换标准) 作为国际标准，把n u r b s 方法作为定义产品形状的唯一 数学方法。在对该方法的研究不断深入的同时，越来越多的商用c a d c a m 系 统，如国际上著名的c a t i au g i ip r o e n g i n e e ri - d e a ss o l i d w o r k ss o l i d e d g e c i m a t r o nm d t 等三维c a d c a m 软件及内核a c i s 与p a r a s o l i d ，都先后开发、 扩充了n u r b s 功能，国内也先后推出了分别以a c i s 与p a r a s o l i d 内核的广州红地 公司的金银花、北航一海尔公司的c a x a 三维电子图板与制造工程师等三维 c a d 软件，迅速将科研成果转化为生产力。国际上对n u r b s 有突出贡献的皮格 尔( p i e 9 1 ) 与蒂勒( t i l l e r ) 在所合著t h en u r b sb o o k - - 书序言中指出，n u r b s 起 着类似于科技英语和商贸英语角色的作用。当今，还可以看到n u r b s 应用于可 视艺术如电影、动画、娱乐、艺术、雕塑中的物体造型，在虚拟现实应用中制 作场景等。可以预见，n u r b s 将会在越来越广阔的范围内获得应用。 小波分析是二十世纪八十年代后期形成的一个新兴的数学分支。它是在傅 里叶分析的基础上发展起来的，是一种局部化时频分析，它用时域和频域的联 合表示信号的特征，作为时一频分析方法，小波分析比傅罩叶分析有许多本质上 的进步。它能够从信号中提取许多有用的信息，是各种信号处理方法的统一框 架，它的快速算法为分析和解决实际问题带来了极大的方便【1 1 ，特别是在 n u r b s 曲线曲面造型当中的应用。通常，小波分析研究在直线域r 上的函数的 多分辨率表示。但在几何造型中，人们感兴趣的是定义在闭区问上的曲线。 哈尔滨理t 大学理学顽f - e 8 位论文 f i n k e l s t e i n 和s a l e s i n 研究了闭区间上多分辨分析的一般理论，并应用这一理论 构造了闭区间 0 ，1 上的b 样条小波，将小波技术推广应用到曲线曲面。通常， 我们借助修改控制顶点来编辑其所定义的n u r b s 曲线，方法简单直观。但是， 当曲线的控制顶点很多时，若仅要求修改曲线的轮廓走向而希望保留曲线的局 部细节不变，就必须修改大量的控制顶点；反之，若仅要求修改局部细节而希 望保留曲线的大致轮廓走向，又不得不增加许多控制顶点以达到修改细节的目 的。在这种情况下，仅靠n u r b s 曲线的局部性，都会给修改工作带来不便。因 此，为了能在不同分辨率下对曲线曲面进行编辑，就需要一种更为灵活的表示 方式。表示方法有如下优点： 1 逼近曲线能够保留原来曲线的总体形态； 2 逼近曲线能够由较少的控制顶点表示，因而可用于曲线的数据压缩； 3 小波分解将曲线分解为低分辨部分( 低频成分) 和细节部分( 高频部分) 。 逼近曲线是由原曲线去掉高频成分得到的，看起来比原曲线更顺眼。分解次数 越多，得到的逼近曲线越光滑； 4 允许用两种不同的编辑方式在不同的分辨率下编辑曲线：在保持细节特 征不变的情况下改变曲线的整体形状；在保持整体形状不变的情况下改变曲线 的细节特征。因此，增加了调节曲线形状的自由度； 5 可由半日到精地对曲线进行分级传输和显示。 小波方法具有很多其他方法无法比拟的优点，将小波方法应用于n u r b s 曲 线曲面的编辑，势必得到事半功倍的效果，因此小波方法对基于曲线曲面的造 型研究尤为重要。 1 2 国内外研究现状分析 n u r b s 曲线曲面以及小波技术都是上世纪八十年代发展起来的新兴学科。 最初，并没有任何学者将小波技术应用到曲线曲面造型技术领域。 1 9 9 4 年，f i n k e l s t e i n 和s a l e s i n 将小波技术应用到曲线曲面造型领域【2 】，开辟 了曲线曲面多分辨造型的新时代。他们以b 样条小波为基础，研究了准均匀b 样 条曲线的多分辨率表示及在多分辨编辑中的应用。同年，q u a k 和w e y r i e h 做了准 均匀b 样条曲线的多分辨率的进一步研究【3 1 ，在f i n k e l s t e i n 和s a l e s i n 的理论的基础 上，对算法做了进一步的完善。随着小波技术被应用到曲线曲面造型领域，国 内外有一大批学者致力于基于小波的曲线曲面造型技术的研究与应用。 19 9 5 至j j19 9 6 年间，s t o l l n i t zej ，g o r t l e rsj 和e c km 等将此技术应用于图像 哈尔滨理下大学理学硕 j 学位论文 处理【4 1 _ 【7 1 。同时，s t o l l n i t z 等将此技术应用于曲线曲面的光顺，并达到了良好的 效果，小波分析技术在曲线曲面造型领域的应用有了进一步发展【8 l 。 1 9 9 7 年，k a z i n n i k 和e l b e r 应用小波技术将非均匀b 样条曲线进行了半j 下交 分解和重构，开辟了小波分解在曲线曲面造型上的新时代【9 l 。同年，l o u s b e r y 多 分辨分析和小波技术推广到任意拓扑形状的曲线造型，拓广了小波技术的应用 范围f 1 0 ) 1 9 9 8 年，s h i g e o 和y o s h i h i s a 在连续分辨率水平上对曲线曲面进行了小波分 解与重构【1 1 1 。同年，孙延奎等给出了任意b 样条曲面的多分辨表示及光顺。 1 9 9 9 年，孙延奎、朱心雄开辟了曲线分层表示新方法，从几何方面论述了 小波在曲线曲面造型上的应用 1 2 - 1 4 1 。1 9 9 9 年至u 2 0 0 1 年，以孙延奎，朱心雄为代表 的许多学者曾先后以准均匀三次b 样条曲线的为例给出了准均匀b 样条曲线的小 波分解与重构的算法1 1 s - 2 2 1 ，并推广到曲面的小波分解与重构，给出了严格的数学 描述，引入了准均匀双三次b 样条曲面多分辨表示的概念。同时，赵罡、穆国旺 等给出了均匀b 样条曲线曲面的小波分解与重构算法f 2 3 】，均匀b 样条曲线曲面的 小波分解与准均匀b 样条曲面多分辨表示的不同之处在于均匀b 样条曲线曲面在 经过小波分解以后所得到的小波在定义域边界与内部可以采用统一的表达式， 在进行小波重构时仅需作乘法运算，计算速度大为提高，在交互设计中有重要 意义。孙延奎在其2 0 0 0 年出版的自由型曲线曲面造型技术一书中将均匀与 准均匀b 样条小波分解与重构技术做了详细地总结。 随后的几年罩，刘建、右江等研究了任意n u b s 曲线多分辨造型技术f 2 4 】，提 出了半正交b 样条小波分解和重构的新算法，同时给出了非均匀b 样条曲线的非 整数阶分辨率的小波分解和重构算法，并实现了任意非均匀b 样条曲线的多分辨 率表示，对于任意非均匀b 样条曲线或者n u b s 曲线无论它有多少控制顶点，均 可以对它进行半正交分解与重构，而不受控制顶点数必须等于固定数的限制， 从这个意义上说，该方法不仅可以实现连续分辨率水平的非均匀b 样条曲线造 型，还可以对非均匀b 样条和n u b s 曲线进行精确的分解和重构，这对于b 样条 曲线曲面的多分辨率造型与显示具有重大应用价值。 2 0 0 2 年至1 1 2 0 0 3 年问，b 样条曲线的多分辨编辑开始被广泛应用于c a d 中【2 5 1 。 同时，n a r a y a n a s w a m i 也阐述了此技术在c a d 中的举足轻重的地位【2 6 1 ，从此这项 理论有了质的飞跃。此时，l o u s b e r y 又将小波技术推广到任意拓扑形状的曲面造 型中【2 7 1 ，从此，曲线曲面的小波分解这项技术不但在原有应用领域有了更广阔 的发展，而且在更多的全新领域得到应用。 2 0 0 6 年，石岩、彭国华等采取变步长选取待插值点的方法对曲面进行光顺 哈尔滨理工人学理学硕1 ：学位论文 处理【2 引，避免选用坏点，达到良好的效果。 2 0 0 7 年，李奇敏等非均匀b 样条的小波分解方法应用于曲面的光j l l 页f 2 9 1 ，提高 了光顺的效果。同年，黄洪琼、汤天浩的基于样条小波变换局部的医学图像 边缘提取得到了两院院士的关注【3 0 】。自此，样条小波比应用于医学图像领 域，样条小波的路将越走越宽。 最近几年间，曲线曲面小波分析技术的应用范围越来越广，也取得了丰硕成 果【3 1 3 6 1 。 1 3 课题来源 本课题属于应用基础理论研究范畴，来源于国家自然科学基金项目 1 0 5 7 1 0 3 7 。 1 4 本文主要研究内容 总结前人所做的工作，我们看到，对各类样条曲线曲面小波分解与重构的 算法的研究已经得出丰硕的成果，但是这些方法仍然存在一些局限性和亟待解 决的问题，对这些问题，本文都将一一给出了解决方法。 在对均匀b 样条曲线曲面进行小波分解与重构过程中，算法的实质是将 ip 7i q 7j 转化为一个带状矩阵，进而直接求解方程组求出c 产1 ，d j 。此方法对 l j 于方阵i 尸7i q 7i 中零元素比较多的情况下快速有效，但是以带状矩阵为系数矩阵 l i j 的方程组求解过程仍然需要应用列主消元法进行解的计算，计算量并不小。在 这个过程当中，很多算法语言的数学专业性很强，也不利于工程技术人员的理 解和进一步研究。 根据矩阵l l q 7l 为可逆方阵，可采用矩阵消元的方法，将矩阵 lj b j = i 尸oi q 7l c i ( 方程组的增广矩阵) 转化为行简化矩阵( 即每一行的非零首元都 l i i j 等于1 ，而且非零首元所在的列，除非零首元本身外其余元全为零的阶梯形矩 阵) ，直接就可以求解方程组，简单有效，更方便了工程技术人员的理解和进一 步研究。 f i n k e l s t e i n 和s a l e s i n 研究了闭区问上多分辨分析的一般理论，并且应用这 理论，构造研究了基于小波技术的b 样条曲线的多分辨表示及其在曲线多分 辨编辑中的应用，用小波基代替b 样条基，实现了在不同分辨水平下对曲线进 哈尔滨理- 下人学理学硕i ：学位论文 行编辑，构造了非均匀b 样条空间的正交分解，实现了非均匀b 样条曲线曲面的 分解和重构，但是他们的算法需要进行大量的内积运算，需要的内存空间也非常 大，因此该方法具有一定的局限性而半正交b 样条小波分析方法最大的优点就 是计算简单，所需要的内存相对较小，但是缺点也是很明显的，这种方法将处 理的曲线( 或曲面) 局限在了控制点数为2 + 3 的准均匀b 样条曲线( 或曲面) 上。 鉴于这种情况，孙延奎和朱心雄等在非均匀b 样条曲线上进行离散化采样，根据 曲线的型值点反算出2 + 3 个控制顶点，再利用准均匀b 样条曲线逼近非均匀b 样条曲线，从而把问题转换为准均匀b 样条曲线的多分辨表示，但是这样做却 引入了额外的误差。 鉴于此，本文将对前人的算法进行改进，使算法不但解决了上述诸多问 题，还将大大节省计算和存储时间。 另外，根据n u r b s 曲线的小波分解方法，加入一次比较算法，灵活运用 曲线的升降阶算法【3 7 3 引，本文还将提出了任意n u r b s 曲线的分解和重构新算 法。 最后，对各类样条曲线曲面作了总结，并提出有待解决的相关问题，对日 后的工作进行了展望。 1 5 本章小结 本章阐述了本文的研究的目的和意义，对准均匀b 样条曲线曲面及均匀b 样条曲线曲面，n u r b s 曲线曲面的小波分解与重构等的国内外研究现状进行了 详细地分析，提出亟待解决的问题以及解决问题的初步方案。介绍了本课题的 来源。另外，本章还简要阐述了本文即将研究的几个算法以及即将得到的比较 满意的效果。 哈尔滨理t 大学理学硕。f ：学位论文 第2 章基础知识 2 1b 样条曲线曲面的基本理论 2 1 1b 样条与b 样条曲线的基本概念 为 我们采用一套特殊的基函数即b 样条基函数。于是，b 样条曲线方程可写 p ( “) - - z 4 m 。( “) ，毒0 ( 2 一1 ) 其中，d = o ，1 ，z ) 为控制顶点，又称德布尔点。m 。 ) ( f = o ，l ，n ) 称为k 次 规范b 样条基函数，其中每一个称为规范b 样条，简称b 样条。它是由一个称 为节点矢量的非递减的参数u 的序列u ：u 。u “+ 。所决定的k 次分段多项 式，也即是尼次多项式样条，被称为基本样条，简称b 样条。 另外，b 样条还有很多其他的等价定义。在理论上较多地采用截尾幂函数的差 商定义。例如德布尔考克斯递推公式 啪，_ 嚣i + l m t ( “) = 生m 卜。( “) + 丝吐m + l , k - i ) ( 2 2 ) “j + 孟一u iu i + 七+ l u i + l 规定旦：o o m 。( “) 的双下标中第一个下标f 表示序号，第二个下标庀表示次数。该递推 公式表明，欲确定第i 个后次b 样条批。( 甜) ，需要用到u i ，l 一，u i m 。共七+ 2 个 节点。称区间 “，u i m ，】为m ，。( “) 的支撑区间。m 。( “) 的第一下标等于其支撑区间 左端节点的下标，即表示该b 样条在参数u 轴上的位置。 哈尔滨理t 大学理学硕 ：学位论文 2 1 2b 样条曲线的类型划分 这里只研究位置连续的b 样条曲线。b 样条曲线按节点矢量中节点的分布 情况的不同，可分为如下的4 种类型： 均匀b 样条曲线( u n i f o r mb s p l i n ec u r v e s ) 节点矢量中节点为沿参数轴均匀 或等距分布，所有节点区问长度a ；= u 川一u i = 常数 0 ( 扛o ，l ，1 + k ) 。这样的 节点矢量定义了均匀b 样条基。 。 准均匀b 样条曲线( q u a s i u n i f o r mb s p l i n ec u r v e ) 其节点矢量中两端节点具 有重复度后+ l ，即u o = u l = = u ku 川= u 砒= = u 枞+ l 所有内节点均匀分布， 具有重复度1 。定义域u u k ，甜川】内节点区间长度a ；= 常数 00 = 矗，k + l ，珂) 与均匀b 样条曲线定义域内节点分布相同，差别仅在于两端节点。这样的节点 矢量定义了准均匀b 样条基。 分段贝齐尔曲线( p i e c e w i s eb e z i e rc u r v e ) 其节点矢量中两端节点重复度为 k + l ，所有内节点重复度为k 。选用该类型有一个限制条件，控制顶点数减一 必须等于次数的f 整数倍，即，形= 正整数。这样的节点矢量定义了分段伯恩斯 坦基。 一般非均匀b 样条曲线( g e n e r a ln o n u n i f o r n lb s p l i n ec u r v e ) 在这种类型罩， 任意分布的节点矢量u = ，“i ，一，u 枞+ 。】，只要在数学上成立( 其中节点序列非递 减，两端节点重复度k + 1 ，内节点重复度k ) 都可选取。这样的节点矢量定义 了一般非均匀b 样条基。可见，前三种类型都可以作为特殊被包含在这种类型 里。对于开曲线，通常为使它具有同次贝齐尔曲线的端点几何性质，两端节点 取成重复度k + 1 。 均匀、准均匀和非均匀三种类型早就存在，s t e p 标准支持把分段贝齐尔曲 线作为一种特殊类型【3 9 j 。 给定( 掰+ 1 ) 研+ 1 ) 个控制顶点呸= 0 ，1 ，m ；j = 0 ，1 ，n ) 的阵列，构成一 张控制网格。又分别给定参数甜，的次数k ，和两个节点矢量 u = 【，u 。卅，】与v = ，m ，屹+ 川】。就定义一张kx 1 次张量积b 样条曲 面。其方程为p ( u ，力= z ，m ，以) m ，( v ) ，“m + l ，m y + l i = 0j = 0 其中，b 样条基m ，( “) ( i = 0 ，1 ，m ) 与，( 1 ，) ( j = o ，l ，z ) 分别由节点矢量 德布尔一考克斯递推公式决定。 b 样条曲线的局部性质可以推广到曲面。 哈尔滨理i t 人学理学硕f j 学位论文 2 2 小波分析与重构的基本理论 一般地，对于r ( r ) 的子空间矿_ ，且y ，关于标准内积构成的内积空间。并 满足以下嵌套关系：矿oc 矿1c cv j - rc ，对于v j 1 ，设缈，。为矿_ 在矿， 中的正交补。即矿，= v j - 10 w j 。将y 7 的一组基排成行向量形式，记为， 则有，1 为y ，- 1 一组基的行向量形式，将矽j 叫中的一组基排成行向量形式，记 为甲7 一，则存在矩阵p 7 ，q 7 使7 = 7 p 7 ， 甲7 = 7 q 7 或者 ( 1 ) j - 1 p = 吖尸i q ( 2 - 3 ) 称川为尺度函数，甲川为小波函数。关系式( 2 3 ) 为他们之间的二尺度关系。 令y j ( t ) 为一b 样条曲线，c 7 为某采样点离散信号，c 7 可看作y j ( ) 的控制 顶点的标值。则必有y j ( f ) = 7 c 7 ，令 俐= 蚶1 则 吡锄p 蚓等l 仁4 ， 则 c ，= h 叫i f 州c , - i ， 令c ，d ，。1 为c 7 的低分辨部分和细节部分则 c j 一= a j c j d j = b j c j 即 c j - ii d 川 = c o i b 根据( 2 4 ) 式有c 。= p j c 7 。1 + q 7 d 7 一， 彳7 ，b 7 称为分解矩阵，q 7 称为重构矩阵。 因此，y j - j ( f ) = 巾一c 川为y 7 ( f ) 的低分辨曲线或逼近曲线。 y 7 ( f ) 的细节曲线。 低分辨部分 y j - | ( f ) = y j - 2 ( f ) + j 罗j - 2 ( f ) y j - 2 ( f ) = y j - 3 ( f ) + 广( f ) y 2 ( f ) = 7 ( f ) + 1 ( f ) ( 2 - 5 ) 7 1 ( f ) = 甲一d 一1 为 哈尔滨理下大学理学硕f ：学位论文 厂1 ( f ) = y o ( f ) + p o ( f ) 即y s ( t ) = y o ( ，) + 矿( f ) + + y - i ( f ) ，7 0 ( f ) ，厂7 - 1 ( f ) 为厂( t ) 的多分辨逼 近表示，此过程为b 样条曲线小波分解过程。反之，为b 样条曲线的小波重 构。实际上，上述曲线的小波分解过程是将曲线转化为控制顶点序列c 7 的小波 分解。以准均匀三次b 样条曲线为例，下图直观表示了b 样条曲线的多分辨分 解：y 2 ( f ) 是由七个控制顶点定义的准均匀三次b 样条曲线，经过一次小波分解 获得低分辨曲线y 1 ( f ) 和细节曲线1 ( f ) 。低分辨曲线7 1 ( f ) 经过一次小波分解获得 低分辨曲线厂o ( f ) 和细节曲线p o ( f ) 。 - - 广 y 0e ) i l l - 一 p 1 茹) - 一 弋 少g ) 矿g ) 图2 - 1b 样条曲线得多分辨分解图 f i g 2 - 1m u l t i - r e s o l u t i o nd e c o m p o s i t i o no fb s p l i n e 图中各曲线特征如下： 1 原曲线2 ( f ) 7 个控制顶点瑶，k 2 ，瑶：节点矢量 = ( o ，0 ，0 ，0 ，1 4 , 2 4 , 3 4 ，l ，1 ，l ，1 ) ； _ 哈尔滨理t 大学理学硕i j 学位论文 2 逼近函数y 1 ( f ) 5 个控制顶点v o ，k ，日；节点矢量 u = ( o ，0 ，0 ，0 ，1 2 ，1 ，1 ，1 ，1 ) ； 3 逼近函数7 ”【n 4 个控制顶点v o o ，k o ，曙，曙；节点矢量 u o = ( o ，0 ，0 ，0 ，1 ，1 ，1 ，1 ) ； 4 细节曲线( f ) 2 个顶点磁，科： 5 细节曲线o ( f ) 1 个顶点碟 2 3 本章小结 本章介绍了b 样条与b 样条曲线曲面的基本概念和基本理论，详细阐述了 小波分析基本理论以及b 样条曲线曲面小波分解与重构的基本理论和分析过 程。以准均匀三次b 样条曲线为例，通过画图，直观的表示出曲线经过小波分 解以后各阶逼近曲线的局部特性以及整体形态。控制顶点的特征以及内节电的 分解规律。 哈尔滨理t 大学理学硕 j 学位论文 第3 章准均匀b 样条曲线曲面的小波分解与重构 准均匀b 样条曲线小波分解与重构的算法可以拓广到张量积b 样条曲面， 而曲面小波分解与重构的算法是曲面多分辨造型的关键。本章在介绍准均匀b 样条曲线小波分解快速算法的基础上，建立张量积b 样条曲面多分辨率表示的 概念，并用数学形式严格描述曲面小波分解与重构的快速算法。该算法具有线性 计算复杂度，是研究曲面多分辨编辑、光顺与显示的基础。 3 1 准均匀b 样条曲线的小波分析基础 对任一非负整数， 设尉门，科力，磁+ ：是由节点矢量 q = ( o ，0 ，0 ，0 ，”，l 一，l ，1 ，l ，1 ) 定义2 ，+ 3 个准均匀三次b 样条，v 7 是 由它们的所有线性组合构成的线性空间。y 7 关于标准内积构成的内积空间并满 足如下嵌套关系： v ocv 1c cv sc 对l ，设形7 一为矿7 一在y 7 中的正交补空间，若记 呜= ( 磷力，科 ，嘭+ ：) 甲川= ( 喇严n ，喇产n ，咄2 ：) 其中，磁力，研力，w 2 j 锄为v ，的尺度函数，w o u - i ) , 啄产n ，形：( ，- 一1 ：为w 产1 的2 产1 个 三次b 样条小波，则尺度函数和小波函数之间的二尺度关系为 川l 甲川】= - ， el g ，式中：e 和g 分别为( 2 7 + 3 ) ( 2 川+ 3 ) 和( 2 + 3 ) 2 川 阶带状矩阵。 对任一非负整数，设r j ( t ) = ( ( f ) ，y ( f ) ，z j ( f ) ) 是由2 7 + 3 个控制顶点 曙d ，巧u ，唆：定义的准均匀三次b 样条曲线，节点矢量为 哈尔滨理t 大学理学硕，l j 学位论文 = ( 0 ，o ，o ，o ，乃，l 一l 1 ，i ，1 ) 其中，x j ( t ) ，y ，( f ) ，z j ( f ) v ，o f 1 。记q = ( 曙力，k d ，唆2 ) 7 ，则 乃( f ) = ，q 一 令 吲= 式中：4 是( 2 川+ 3 ) ( 2 。3 ) 阶矩阵，哆是( 2 川+ 3 ) ( 2 4 3 ) 阶矩阵，引和 弓i g 都是分块矩阵， el q 一表示矩阵 ei g 的逆矩阵。 则 q t = 4 q ( 3 - 1 ) 哆一。2 哆q ( 3 - 2 ) 分别为q 的低分辨率部分和细节部分，并且 q = e q t + g q 一- ( 3 - 3 ) 式( 3 - 3 ) 表明，矩阵e 和g 的作用从低分辨率部分q 一，和细节部分q 一。重构 q 。因而称为重构矩阵。相应地，a ，和哆称为分解矩阵。称乃一。( f ) = 一q 一，为 乃( f ) 的低分辩率曲线或逼近曲线。称岛一。= 甲川q 一为乃( f ) 的细节曲线。可以证 明，乃( f ) 可由乃一。( f ) 和岛一( f ) 的过程称为曲线的小波分解。反之，由乃一。( f ) 和 风恢复7 ) 的过程称为曲线的小波重构。曲线的小波分解过程可以递归地应 用于低分辨部分厂h ( 味由此可得到曲线l ( t ) 的多分辨率逼近表示 ( f ) ，y h o ) 。 3 2 准均匀b 样条曲线小波分解与重构的快速算法 现将c ，c h 和d n 分别看成具有2 7 + 3 ，2 ，一+ 3 和2 _ 1 的采样点的离散信 号，则下述结论成立： 7 ) 分解为低分辩曲线，- j ( f ) 和细节曲线h ( f ) 并可由其重构，与信号c ，分 解成低分辩率部分c ，和细节部分d h 并可由其重构，两者的本质是相同的。 由于信号c ，表示形式简单，通常用它的小波分解与重构研究曲线的小波分 解与重构，即信号c ，分解成低分辩部分c h 和细节部分d h 等价于将曲线y ，( f ) 哈尔滨理工人学理学硕： ：学位论文 分解成低分辨部分，_ i c ，- l 和细节部分甲，- l d ，i 。反之，从信号c ，的低分辩部分 q 一和细节部分q 一。重构e ，等价于从曲线乃( f ) 的低分辩部分一q 一。和细节部 分、壬，一i d ，一i 重构7 f ( f ) = m ，c 7 。 由带状矩阵e 和q ，重构c ，具有线性复杂度0 ( 2 7 + 3 ) 。因而是快速算法。但 一般地，由于4 和毋是稠密矩阵，由q 计算q 一。和q 一。的乘法运算的复杂度是 二次的。针对这个问题研究了不计算4 和哆而直接从q ，弓和g 入手求出q 一。 和d j 一。的快速算法，现介绍如下： 设q ，弓和，同上，则q 的低分辨率部 q i = ( 瑶川，v i ( - i ) c - , 喀芒：) r 细节部分 d h = ( o ( o j - i ) 科产n ，叫恐) 7 可以通过如下线性方程组求出： 厂。 弓圳等| - q l 一一1j 算法说明与分析： 由于系数矩阵l 弓l gl 是可逆的，故求得的q 一。和q 一。是唯一的。孩算法达 到了不计算分解矩阵a 和乃而实现小波分解的目的。求解方程组的基本思想 是，适当地交换带状矩阵e 与g 各列，将系数矩阵iei gi 转化成一个带状矩 阵，然后快速求解所得到的线性程组。例如令 m ，= 0 o 】，p j 1 ，g o 】，弓 2 】，q j b ，弓 3 】，9 【2 一1 】，尸 2 p 1