（计算数学专业论文）细分网络下的散乱数据样条插值及其应用.pdf

中山大学博士学位论文 摘要 散乱数据指的是在二维或者三维空间里，无规则的、随机分布的数据。散乱 数据拟合是指用一个光滑的曲面来逼近或通过这一系列无规则的抽样数据点。 散乱数据的可视化就是对散乱数据进行插值或拟合，形成曲线或陆面并用图形 或图像表示出来。 在过去的4 0 多年中，尽管人们提出了各式各样用来解决散乱数据拟合的方 法，但是其研究成果离实用还有一段距离。特别是大规模散乱数据的拟合问题， 在连续性、计算量、实现方法等必不可少的方面，还没有一个算法能够达到实 用。 本论文从散乱数据的自然样条插值方面入手，讨论了基于细分网格点上的有 极值性质的散乱数据的二元自然样条插值函数的局部基，并讨论了细分网格点 散乱数据二元多项式插值自然样条函数的一些主要性质；研究基于加密节点散 乱数据的一元多项式样条插值及其二步算法，推广n z - 元情形，得到一种细分 网格点散乱数据二元多项式的样条插值的加密二步算法；形成一套曲面造型中 基于细分网格二元样条的快速计算方法，并应用到人脸造型上。 整篇文章按如下方式组织。 第一章介绍了散乱数据曲面拟合的历史发展、基本理论和基本概念。着重介 绍了目前主流的用于散乱数据拟合的各种方法，并比较其优缺点。 第二章讨论了基于加密节点散乱数据的一元多项式自然样条插值，即是考虑 在给定一批节点进行了一次样条插值之后，发现在某两节点间需要加插另一批 节点进行细微刻划的问题，并且给出在一元条件下的二步算法。( 本章主要结果 发表于中山大学学报自然科学版) 第三章讨论了基于细分网格点上的散乱数据的二元自然样条插值函数的局 部基，它具有很好的紧支撑性。在图象处理，计算几何等问题中都可以找到应 用。矩形网格的张澄积b 样条插值是它的特殊情形，插值样条基函数是不同类 + ， 型的张量积b 样条，计算简单。( 本章主要结果发表于计算数学毗及( c h i n e s e 中山大学博士学位论文 j o u r n a lo fn u m e r i c a lm a t h e m a t i c sa n dh p p l i c a t i o n ) 第四章讨论了细分网格点散乱数据的二元多项式自然插值样条函数的一些 重要的性质，并且还给出了一个加密二步算法。利用此算法可以大大简化计算 复杂度，很适于解决大规模数值计算问题。本章还给出用m a t l a b6 0 开发出的 对应软件包，可以很方便的实现算例的求解和作图。( 本章主要结果发表于 j o u r n a lo fc o m p u t a t i o n a la n da p p l i e dm a t h e m a t i c s ) 第五章讨论了细分网格样条技术在人脸造型中的应用。我们从研究多元散乱 点样条插值函数开始，已有一套对细分网格的二元样条快速计算的方法，把这 种方法应用到人脸造型上，具体实现起来并不困难。这里主要给出其具体实现 的过程及结果。( 本章主要结果发表于系统仿真学报) 关键词：散乱数据、样条插值、加密网格、局部基、二步法 i i 中山大学博士学位论文 s p l i n ei n t e r p o l a t i o n a n di t sa p p l i c a i t o nf o r s c a t t e r e dd a t ao v e rr e f i n e dg r i dp o i n t s m a j o r ：c o m p u t a t i o n a l m a t h e m a t i c s n a m e ：l i ub i n s u p e r v i s o r ：p r o f g u a n l u t a i a b s t r a c t s c a t t e r e dd a t am e a n st h ei n e r r a t i ca n dr a n d o md i s t r i b u t i n gd a t ai n2 do r3 d s p a c e s c a t t e r e d d a t a r e p r e s e n t a t i o n i n c l u d e ss c a t t e r e dd a t a a p p r o x i m a t i o n a n d s c a t t e r e dd a t ai n t e r p o l a t i o n t h er e l e v a n tc u r v e sa n ds u r f a c e sc a nb ed r a w nt o r e p r e s e n tt h es c a t t e rd a t ab ya p p r o x i m a t i o n o ri n t e r p o l a t i o nm e t h o d s o ，t h i si sc a l l e d s c a t t e r e dd a t av i s u a l i z a t i o n i nt h ep a s t4 0y e a r s ，s om a n ym e t h o d sw e l ep r e s e n t e dt os o l v et h ev a r i o u s p r o b l e m so fs c a t t e r e dd a t ar e p r e s e n t a t i o n ，b u tc o n s i d e r i n gt h ec o n t i n u i t y , o p e r a t i o n p r i c ea n do t h e ri n d i s p e n s a b l ec r i t e r i o n ，n o n eo ft h em e t h o d sc a nb ew e l l u s e di n p r a c t i c e ，e s p e c i a l l y f o rl a r g es c a l es c a t t e r e dd a t ar e p r e s e n t a t i o n i nt h i sd i s s e r t a t i o n ，f o ri n t e r p o l a t i n gp r o b l e m s ，an e w l o c a l l ys u p p o r t e d b a s i sf o r t h eb i v a r i a t ep o l y n o m i a ln a t u r a ls p l i n es p a c et or e f i n e dg r i dp o i n t si sc o n s t r u c t e d s o m e p r o p e r t i e so f t h i sb a s i sa r ea l s od i s c u s s e d a nr e f i n e dt w o s t e p sa l g o r i t h mc a n b ec a r r i e do u tn o to n l yb ys o l v i n gs o m el i n e a ra l g e b r a i cs y s t e m sw i t hd i a g o n a ls t y l e c o e f f i c i e n tm a t r i x e s ，b u ta l s of o rt h el a r g es c a l en u m e r i c a la p p l i c a t i o n s i nt h ee n d ，a t w o s t e p sa l g o r i t h m i su s e dt oh u m a nf a c ec o n s t r u c t i o n t h eo r g a n i z a t i o no f t h ed i s s e r t a t i o ni sa sf o l l o w s i nc h a p t e r1 ，t h eh i s t o r i c a ld e v e l o p m e n t ，b a s i c ，g n c e p t sa n dt h e o r i e so f s c a t t e r e d d a t a r e p r e s e n t a t i o n a r ei n t r o d u c e d t h em a i nm e t h o d sf o rs c a t t e r e dd a t a j 中山大学博士学位论文 r e p r e s e n t a t i o na n dt h ec o m p a r i s o n s a r ea l s od i s c u s s e d i nc h a p t e r 2 ，b a s e d0 n t h et h e o r yo f b - s p l i n ei n t e r p o l a t i o no v e rr e f i n e dk n o t s ，t h e p r o b l e m o nh o wt ou s et h er e s u l to f b s p l i n ei n t e r p o l a t i o nt om o d i f yt h ec u r v ew i l lb e d i s c u s s e d a t w o - s t e p sa l g o r i t h m i sp r e s e n t e da tt h ee n do f t h ec h a p t e r i nc h a p t e r3 t h em e t h o df b rc o n s t r u c t i n gt h en e wl o c a l l ys u p p o r t e df u n c t i o n sa s b a s i so ft h es p l i n es p a c ea n ds o m ep r o p e r t i e so f t h eb a s i sa r eg i v e nt ot h es c a t t e r e d d a t ao v e rr e f i n e dg i r dp o i n t s t h e i ra p p l i c a t i o n sc a nb ef o u n de a s i l yi nt h ef i e l d so f i m a g ep r o c e s s i n g a n d c o m p u t i n gg e o m e t r y i nc h a p t e r4 ，s o m ei m p o r t a n tp r o p e r t i e so f t h e s en e w l o c a l l ys u p p o r t e db a s i sf o r t h eb i v a r i a t ep o l y n o m i a ln a t u r a ls p l i n es p a c eo v e r r e f i n e dg i r dp o i n t sa r ed i s c u s s e d a r e f i n e dt w o - s t e p sa l g o r i t h mi s p r e s e n t e d ，w h i c h i ss u i t a b l ef o rt h e l a r g e s c a l e n u m e r i c a la p p l i c a t i o n s ac o m p u t i n gt o o l k i ti sd e v e l o p e di nm a t l a b6 0t oc a l c u l a t e t h ef u n c t i o n sa n dd r a wt h ef i g u r e s i n c h a p t e r5 ，as p l i n em e t h o do v e rr e f i n e d 画dp o i n t s f o rf a c em o u l d i n gi s p r e s e n t e d b e c a u s eo f t h el o c a ls u p p o r to f b - s p l i n e ，t h er e f i n e d 鲥ds p l i n em e t h o d i s s i m p l ea n de a s y t ob ec a r r i e do u ti nc o m p u t e r k e y w o r d s ：s c a t t e r e dd a t a ，s p l i n e i n t e r p o l a t i o n ，r e f i n e d g r i dp o i n t ，l o c a lb a s i s ， t w o s t e p sa l g o r i t h m 中山大学博士学位论文 1 1 引言 第一章散乱数据的曲面拟合 散乱数据 1 2 指的是在二维或者三维空间里，无规则的、随机分布的数据。 散乱数据拟合 3 是指用一个光滑的曲面来逼近或通过这一系列无规则的抽样 数据点。散乱数据的可视化就是对散乱数据进行插值或拟合，形成曲线或曲面 并用图形或图像表示出来。 散乱数据来源主要有三个 4 ：( 1 ) 物理量的测量值；( 2 ) 实验结果；( 3 ) 计 算结果。它们出现于各种科学和工程应用中，如地质学，大气学，海洋学，测 绘学和采矿业中常会收集到一些物理量的非均匀测量结果：化学物理学和工 程当中的散乱分布的实验数据；用有限元法解偏微分方程时其输出中的非均匀 分布的计算结果；散乱数据插值还在计算机图形学和计算机视觉中有着各种各 样的应用。大量的文献提供了各式各样的方法，许多都受到光滑性，时间复杂 性和所接受的数据分布样式的限制 4 大规模散乱数据则是指这一系列抽样数据点的个数比较多，一般在1 0 0 0 0 个 以上。这个问题的研究具有很重要的实际意义：在很多领域如石油勘探和地震 检测等活动中，人们需要在很多不规则的位置上对某些数据进行抽样。随着测 量仪器和测量方法的不断进步，这些点的规模也越来越大。抽样以后，人们需 要对这些数据进行分析，需要知道在任意位置点的数据值，而不是仅仅在那些 抽样位置的数据值。在这种情况下，就需要对所得到的抽样数据进行拟合。 在这些领域中，需要用散乱数据插值决定任意位霞的值，而不只是在可得数 据点处。于是涌现了许多多维散乱数据可视化的方法，如在医学成像中，散乱 数据插值是从一系列人体器官的c t 或m r i 图像重建闭合曲面的必经的一步；在地 质学中，演化的插值方法推进了从等高线图重建地表外貌：计算机视觉利用散 乱数据插值从基于特征的立体图像或运动图像得到的稀疏的测量结果重建曲 面；在图像变型( i m a g em o r p h i n g ) 中，散乱数据插值用来自一对图像上对应的 特征点组产生光滑的映射；同样的过程用于遥感应用中。以达到图像的配准 二三二 些查兰竖主兰堡堡奎 ( i m a g er e g i s t r a t i o n ) 。 由于散乱数据曲面拟合问题具有如此广泛的实际应用背景，所以成为近年来 逼近理论中的活跃领域。近年，在动态图像散乱数据曲面拟合方面的研究：微 分方程方法( 特别是水平集方法) 、统计方法在散乱数据曲面拟合方面的研究， 有不少工作。但由于本论文主要关心与数值逼近有关的散乱数据曲面拟合，所 以对其他方面的工作暂时不做综述。 1 2 散乱数据拟合问题的提法 数据拟合问题通常分为插值问题和光顺逼近问题。插值问题的解要求严格经 过型值点，光顺逼近问题的解虽不要求严格经过型值点，但它要求在某种约束 条件下( 比如最小二乘意义下) 达到一种整体逼近效果。 对于插值问题的一般提法为： 1 求定义于区域d 上的某种函数空间h 中的函数，使，( e ) = z ，i i 。 其中，是一个指标集，p 是d 中的某些点，z 是给定的( 实) 数值。 最t j 、- - 乘光顺逼近问题的一般提法为： 1 求定义于区域d 上的某种函数空间h 中的函数，使 善f ( ，( b ) 一f ) 2 r a i n 。a , ( g ( p , ) 一z ) 2 其中0 ，i i 。 当变量个数n 2 时，上述问题分别称为多元插值问题和多元最小二乘光顺 遁近问题。当数据带有噪声时，光顺逼近比插值逼近更为合理，数据点分布不 规则的情形称为散乱数据拟合问题。n = 2 时的情形就是散乱数据的曲面拟合。 它也是多元问题的基础。 1 3 散乱数据拟合方法分类 在过去的4 0 多年中，人们提印了各式各样的方法，尽管这个领域异常活跃过， 应用领域众多它仍然是一个较难且计算费用大( c o m p u t a t i o n a l l ye x p e n s i v e ) 中山大学博士学位论文 的问题。特别是大规模散乱数据的拟台问题，其研究成果离实用还有一段距离。 在连续性、计算量、实现方法等必不可少的方面还没有一个算法能够达到实 用。 常见的散乱数据拟合方法有：基于二步法( t w o s t a g em e t h o d s ) 、s h e p a r d 的方法、径向基函数法( r a d i a lb a s i sf u n c t i o n s ) 、薄板样条法( t h i np l a t e s p l i n e s ) 、箱样条法( b o xs p l i n e s ) 、有限元与顶点样条方法( f i n i t ee l e m e n t m e t h o d ) 、多项式自然样条法、光滑余因子与b 网方法以及近年来有很大影响的 层次b 一样条( h i e r a r c m c a lb - s p l i n e ) 、多层次b - 样条( m u l t i l e v e l h i e r a r c h i c a lb - s p l i n e ) 方法、三角剖分方法和细分算法等等。其中有关于这 方面的一些好的综述可以参见：r 4 5 儿6 7 。 1 3 1 二步法 早期关于散乱数据曲面拟合的结果主要停留在格子点插值问题，主要方式是 张量积插值，或者利用希尔伯特空间构造再生核的办法，s c h u m a k e r 系统的总结 了1 9 7 6 年前这方面的研究情况，他的二步法是解决这类问题的有效方法 8 。其 重要思想是把散乱数据拟合问题分成两步：第一步利用散乱数据点构造函数g ， 由函数g 得到格子点数据；第二步是针对上述格子点数据采用已有的格子点数据 的处理方法。 按照这两步具体实现的方法类型不同，可以分为( 1 ) 插值一插值型：( 2 ) 光顺逼近一插值型；( 3 ) 光顺逼近一光顺逼近型。但由于实际问题的背景和计 算上的考虑，( 3 ) 经常为( z ) 所取代。关于( 1 ) 型拟合法，有a k i m a k o l l i n g a n dw h i t t e n ，s p a t h 的工作，关于( 2 ) 型拟合有h e s s i n g 等人的工作。 1 9 9 1 年，ll s e h u m a k e r 和c t r a s s 提出了一种定义在球型光滑曲面s 上的函 数拟合方法 9 】，运用张量积多项式样条和周期三角样条，通过把曲面映射到矩 形域上构造了逼近曲面。给出了最小二乘法全局逼近和拟内插局部逼近算法， 构造了一种二步法。 f 第一步：用局部逼近方法构造拟内插所需的值。 第二步：用上述值去求拟内插系数。 二! = ! 坐查兰堕主兰垒丝苎 韩国强在1 9 9 3 年提出了一种计算稳定的二步拟合法，并且给出t - - 步拟合法 的误差估计。该方法可以避免薄板样条法和径向函数法当插值点较多时计算上 出现的病态，并可以减少存储与计算量。 1 9 9 7 年，l uh a n 和s c h u m a k e r 构造了具单调性散乱数据拟合的二步法。 1 0 其主要思想是：第一步：由具单调性的散乱数据构造具单调性格子点数据： 第二步：用c 1 分片三次样条函数构造单调性拟合曲面。 1 3 2 基于s h e p a r d 方法 有关散乱数据拟合的较早的一个算法是s h e p a r d 于1 9 6 8 年的方法 1 1 ，它 是一个与距离成反比的加权方法。这个方法首先由一些大气学者和地质学者提 出，其基本思想是将插值函数定义为”个数据点函数值的加权平均。s h e p a r d 方 法可应用于任意分布的空间数据点，它定义了一个对数据进行反距离加权平均 的插值函数，插值函数可显式写出。 令p 为平面上某一度量，通常取为距离度量，对定点( z ，y ) 令 = p ( 0 ，y ) ，“，y i ) x i = l ，2 ，n ) ，假定p 为一个正实数，对散乱数据点 ( ，m ，z ) ，i = 1 ，2 ，n ，则拟合曲面z = f ( x ，y ) 表示成下列插值公式： z = f ( x ，y ) = 这是一个关于( 玉，* ) ，i = 1 ，2 ，n 的全局插值公式，当( j ，y ) 是非插值点时 ，( x ，_ ) ，) 取所有函数值z 的权平均；权因子吉与( z ，y ) 有关，( 1 1 ) 式称为s h e p a r d 公式。 但是它定义的插值函数只能c 。连续并且还不能保证抽样点周围局部区域的 正确形状。所以用该方法得到的s h e p a r d 曲面代数精度低，在插值点附近会形 中山太学博士学位论文 成平台形状，没有良好的极值性质，而且改变一个数据还会影响整个曲面。因 此，f r a n k e 和n i e l s o n 在1 9 8 0 年引入了修正的二次s h e p a r d 方法解决上述缺 点并产生连续的插值1 2 。r f a r w i g 在1 9 8 6 年给出了s h e p a r d 方法的全局误差 估计并证明s h e p a r d 方法收敛性并给出最优逼近阶的条件 1 3 。 尽管s h e p a r d 方法有上述缺点，但s h e p a r d 方法可以处理观测数据的数目很 大，尽管模型粗糙，但是对于那些有峰值的曲面，却有良好的逼近效果。在实 际应用中，s h e p a r d 插值模型( 简称s p 模型) 是一种直观的、可操作的相似预 测法，已在降雨预测中得到成功应用 1 4 。 1 3 3 径向基函数法 1 9 8 7 年1 9 9 1 年，p o v e l l 与j a c k s o n ，r i p p a 等总结出径向基函数方法( r a d i a l b a s i sf u n c t i o n s ，用一系列径向基函数r ( ，) 插值，记= x 一f 曲面为 i1 口i r ( i ) ，常用r ( r ) 有( c 2 + r 2 ) j ，( c 2 + ，2 ) 一，l o g ( c 2 + r 2 ) 等。前两者由于最早 i = 1 由h a r d y 在t 9 7 1 年引入，又称为h a t d y e - 次径向基函数( m u l t i q u a d r a ti c s ) i5 。 一般来说，我们经常用下列形式的定义。 给定数据点( ，z ) ，t e 彤，掣，i = l ，2 ，n ，所谓径向基函数法是指：求 形如 s ( f ) = 窆q 种一f f d + 靠( f ) 的函数使得 s ( t 7 ) = z ，i = 1 ，2 ，并且a 。q ( t ) = o ，v q ( t ) 己 t = l 其中g 是定义在r + 上的元函数，g ( r 2 ) 又称为径向函数，m 是一正整数。 它定义插值函数为径向对称基函数的线性组合，每个基函数的中心落在某一 个数据点上，基函数的系数由解线性方程组决定。系数矩阵总是满的，常是病 态矩阵，需要前处理。一般选用g a u s s i a n ，m u l t i q u a d r a t i t s j 5 j 和s h i f r e d 中山大学博士学位论文 l o g 4 5 作为基函数。这里面，h a r d y 提出的多重二次函数法，也称为m q 方法 ( m u l t i q u a d r a t i c s ) 1 5 3 是其中最成功，易应用的方法，简单直观。他考虑了 平面上的插值问题： 求f 满足 f ( x ，力= a , b t ( x , y ) i = l 使得 a , b , ( x j ， ) = 乃，j = l ，2 ，n i = 1 i t 坤b j ( x ，力= ( + 炉) i t 嘭是第个插值点， ) 到力的距离， 为一 参数。 n e l s o n 在1 9 9 3 年的一篇文章 1 6 里面讲述了上述各类插值的比较。 r u p r e c h t 和m u l l e r 在1 9 9 5 年 1 7 对使用径向基函数在图像变形( i m a g e w a r p i n g ) 中的应用作了一个综述。d d y n 等人利用m i e c h e l l i 的思想，构造了 多元散乱数据的径向函数和插值法 1 8 1 9 。 1 3 4 薄板样条 在插值于散乱数据的函数中，使曲率的积分在整个定义域上最小，就导出了 薄板样条( t h i np l a t es d l i n e ) 。 1 9 7 6 年，j d u c h o n 最早建立了薄板样条理论 2 0 。这是一元样条到多元样条 的真正非张量积形式的推广。由于有较好的视觉效果且对海量数据非常稳定。 该方法有着广泛的应用。尽管，它通常被看作变分问题的解，d u c h o n 指出它可 由径向基函数推导出 2 0 。 d u c h o n 考虑的模型是 m ) = 谣等等= m i n u m ，2 刚甜 定理1 设r = ) 兰是掣中一有限子集，其零插值在只( f ) ( m 1 次多元多项式 集和) 合集上只有恒零鳃。则有唯一形如 盯( f ) = 乏：五局。( f t ) + p ( f ) ，p ( f ) 只( f ) 中山大学博士学位论文 的函数，使 五) = o v q e p ( 0 ，- i 且在，集合上取指定值a ( t 。) = z ，i = l ，2 , - - - , n ，从而，对所有在r 集合上取指定 值的函数而言，该口使j ( 盯) = r a i n ，其中 k = 2 弄竺耋i ：笔墨薯篓筹 我们从这里定理可以得到c r ( t ) 的求解算法，如果取”= 2 , t = ( j ，力，则成为平 面上最优插值问题。 a b r a n d t ，w l b r i g g s 和d t e r z o p o u l o s 等人通过使用多栅松弛 ( m u l t i g r i dr e l a x a t i o n ) 技巧来加速薄板样条的数值解 2 1 2 2 2 3 ；同样r s z e l i s k i ，s j g o r t l e r 和m f c o h e n 等人则使用有层次的基函数或小波也可 用来加速类似于共轭梯度下降法的迭代法的收敛 2 4 2 5 。此外，1 9 9 4 年， p o w e l l 2 6 考虑t z 维薄板样条插值问题，对于平方可积函数f ( x ，) ，) ，在任何 平面上非单个直线子集的有界集合d 上，证明了其薄板样条插值序列在d 上一 致收敛于厂。 此外，薄板样条也被用于在图像的变形( w a r p i n ga n dm o r p h i n g ) 中生成光 滑形变函数( s m o o t hw a r pf u n c t i o n ) 2 7 。然而，薄板样条不是多项式样条， 没有多项式样条的良好性质，所以在大型网格上求解插值函数其计算量依旧是 巨大的。 1 3 5 箱样条 一 1 9 8 3 # ：- c d e b o o r 辛f l rd e v o r e 引进了箱样条( b o xs p l i n e ) 推广了一元b 样 条的结果 2 8 2 9 ，可以处理某些非格子点插值问题，但是插值点分布仍要有 一定规律。由于发现对于平面散乱数据进行不同剖分，产生的样条函数空间维 墓会出现不一样的情况。更令人们想到要提出一个一般的方法来解决散乱数据 多元样条插值问题是很困难的。 二里二 生坐查兰苎主兰垡丝奎 根据 3 0 ，命 为一个“方向集”而有 以= p ，r ) c z 、 o ) s p a n x = ( 以) = r 再考虑仿射方体 刚= 如 = 倭：一扫专1 汕- ，0 由于( 以) = r 5 ，【以】的s 维体积是正的，这个体积表示为阳【k 】。 如果必要，重排 z 1 ，z “) ，使” x 1 ，一 o 我们有具有方向集以的箱样条m ( i 以) 的下述定义。 置 ，c x l x l ，- 一，z 5 ，= f j ；i i ；j i ：了 之后，对于m = s + 1 ，n ，递推定义 l m ( * i x ，矿) = 丘m o 一断”，x ”1 砷 并且置m ( | 以) = m ( | z 1 ，z “) 。 定理2 命以c z 5 、 o 而( 以) = r 5 ，那么箱样条肼( - i 置) 具有下述性质 ( i ) s u p p m ( i 以) = 【置】 ( i i ) m ( 刮置) o 对【以】的内点x 成立 眠= 隆儿j ：一知圭护士扣忙( 1 0 【卢i j 其中 c ) 表示 i _ ) _ 关于 l 一，n 的一个补集。那么，m ( i 以) 限制于反。补集 x 科如 中山大学博士学位论文 一9 一 的每一个分量是总次数h s 的一个多项式。其中皿称为箱样条m ( i 以) 的网。 2 0 0 0 年，袁晓君，李华 3 1 在他们的一篇文章中将单变量b o x 样条扩展到双 变量b o x 样条，并给出b o x 样条在图像处理中极为有用的几条性质。然后，提出 了一个使用一类双变量b o x 样条来计算滤波器库的方法，他们这样得到的滤波器 库在四频带分析综合框架中具有完全重构的性质，可用来十分有效地分解合成 图像。 2 0 0 1 年，袁晓君，李华 3 2 在 3 1 的基础上，针对图像处理中的图象重构问 题，结合多频带o f t 滤波器库和双变量b o x 样条，给出了形成完全重构模型的 条件并且构造了一个完全重构模型。并通过实验证明，该模型能满足完全重构 条件并可有效分解合成图像。 1 9 9 6 年，赵红星分别研究了b o x 样条曲面的控制点与b o x 样条曲面的正性之间 的关系 3 3 以及b o x 样条级数的控制点与b o x 样条级数单调性之间的关系 3 4 ， 给出它们的必要条件和充分条件，并由此得到b o x 样条曲面以及三方向和四方 向b o x 样条级数在任意方向上的单调性条件，推广了w d a h m e n 和c a m i c c h e l i 的 相应结果。 1 9 9 9 年，赵红星引入单向凸的概念，给出了箱样条曲面单向凸的必要条件和 充分条件 3 5 。2 0 0 1 年，赵红星 3 6 利用箱样条的性质，导出t - - - 元三方向和四 方向箱样条曲面在任意方向上的单调条件以及凸性的h e s s i a n 矩阵判别条件 推广了w d d h m e n 和c a m i c c h e l l i 的相应结果。 1 3 6 有限元与顶点样条 1 3 6 1 有限元法 1 9 7 7 年，c l a w s o n 把有限元法( f i n it ee l e m e n tm e t h o d ) 引入到散乱数据 点的曲面拟合领域 2 1 。该方法的主要思想是在给出具有双白变量的散乱数据 点u ( ，m ) 及其函数墨= 厂( ，片) ，i = 1 ，2 ，n 以后，首先求出二维平面上散乱点 的v 凸包，并对其进行三角剖分，形成条列的三角形。，五女，f f 。然后构 中山大学博士学位论文 造一系列的面片，使其插值于所有n 点的函数值弓。其中l a w s o n 2 1 在1 9 7 7 年 提出了几个准则以避免狭长三角形，再在每个三角形内构造满足插值和一定光 滑性条件的曲面。后来，由f a r i n 3 7 3 8 儿3 9 等人对这种方法进行了改进 除此之外，大多数c 。的方法使用c l o u g h t o c h e r 插值法 1 2 3 9 4 0 ， h e r r o n 插值法 4 1 和n i e l s o n 的最小模网络法( n 法。m i n i m u mn o r m n e t w o r k ) 4 2 4 3 1 4 4 。但是所有这类的方法，受限于数据的分布，狭长三角 形有时是不可避免的。 1 9 7 9 年，s e g a l m a n 4 5 等人将有限元拟合方法用于实验数据的处理。通过一 个选定的光顺参数控制光顺程度，进行光力学的变形分析。这种方法所需的输 入数据点比较少，数据点可以任意形式分布，并可用于处理不规则曲线边界的 问题。2 0 0 3 年，蔡中义，李明哲 4 6 基于这一恿想，提出了一种基于不规则分 布的数据点重建三维曲面的光顺一有限元方法。该方法根据数据光顺与最佳逼近 相结合的概念建立目标泛函，采用有限元法求解，并通过n e w t o n r a p h s o n 方法计 算l a g r a n g e 乘子。采用八节点等参元及n e w t o n r a p h s o n 方法对目标泛函极小 化，从而得到重构的曲面。由于结合了光顺技术，这种方法对原始数据的噪声 误差具有明显的抑制效果，与有限元拟合方法相比，所需的输入数据点少，重 构的曲面逼近精度高、光顺性好。另外，该方法对数据点分布形式没有任何特 殊要求，对均匀及散乱分布数据点的曲面重建问题同样适用。由于该方法采用了 八节点等参数单元对数据点所分布的区域形状没有任何限制，可用于任意不规 则边界的曲面重建问题。而且从数值实验结果表明，该方法简单，便于应用。 8 0 年代，n i e l s o n 4 2 儿4 3 4 4 给出了基于网格模极小的c 1 类散乱数据插 值的构造方法，随后。p o t t m a n n 4 7 4 8 3 在1 9 9 1 年将此方法作了进一步推广，得 到了c 2 类插值的构造方法。 1 9 9 5 年，a n d r e a sk o l b 和h a n s p e t e rs e i d e l 4 9 在他们二人的基础上，提 出了一种在删n 阏上的双变量散乱数据插值方法，这个方法也具有c 2 连续的性 质。2 0 0 1 年，王炅，王瑞芳，韩国强，林鹉等人给出t n i e l s o n 提出您一类基 于网格模极小的多元散乱数据插值的误差估计 5 0 。 中山大学博士学位论文 1 9 7 9 年，f o l e y 在他的博士论文中推广了布尔和插值，提出一种和插值， 有迭代格式方便计算。h w j l e e ，m p a s k o t a 和k l t e o 等人 5 1 在1 9 9 7 年利 用f o l e y 和n i e l s o n 的相关结果 5 2 5 3 ，构造散乱数据的双三次样条插值，提 出了一种新的用于解决混沌系统中的目标问题( t a r g e t i n gp r o b l e m ) 的基于混 合策略的全局局部最优反馈控制方法，它把状态矢量空间分割成目标区域空间 以及它的互补空问两部分。这个方法即使在大规模扰动情况下也具有非常强的 鲁棒性，并且不依赖于初始条件。因此，即使初始条件发生了改变，也不需要 进行第二次计算。 1 3 6 2 顶点样条 我们考虑一个重要的问题。对于预先给定的光滑性c ，五，和给定的网 剖分，决定在网上具有最低次数的c 7 中所有局部支撑的分片多项式函数， 这些函数的支撑包包含至多一个内部网点。这些函数称为顶点样条。其二元情 形是崔锦泰与来明骏 5 4 ，更广泛的情形是崔锦泰与来明骏 5 5 首先引入的。 在崔锦泰与来明骏 5 5 中，证明了假定d 2 r + 1 ，顶点样条存在。由于高 次多项式因各种原因常常是不合乎需要的，如果有大的局部维数和形状控制困 难，我们对于一个给定的，尽可能的减少d 。完成这个任务的一个途径是精化网 剖分。在有限元方法中。得到的元素称为一个微元。如果精化是以一个对称的 方法进行而且不增加维数。这就导致了广义顶点样条的概念。因此，一个广义 顶点样条的支撑同k 顶点样条的支撑是同样的，唯一不同的只是在支撑中的每个 胞腔( 即单纯形或平行多面体) 以一个对称的方法精化，使次数d 减少，但是仍 然满足光滑性条件c ，而使超光滑性条件c 矿”o 去掉了。 在崔锦泰与何天晓 5 6 3 中，参照p o w e l l ，s a b i n 5 7 3 和h e i n d l 5 8 的结果， 构造了一个任意( 正规) 三角剖分上的二元c 二次广义顶点样条，并研究了它 们的性质。 当一组局部的基底能促成计算方案正规方程求导以及某些结果的证明等等 时，顶点样条和广义顶点样条在逼近与插值的各种问题中是有用的。除对于 中山大学博士学位论文 h e r m i t e 插值的平凡应用外，它还应用于拟插值公式的构造，对连续和离散数据 的最小二乘逼近，保形逼近，计算机辅助几何设计以及梯度场的再构造等等。 1 3 7 层次b 一样条 1 9 8 8 年，f o r s e y 和b a r t e l s 首先提出了层次b 一样条( h i e r a r c h i c a l b - s p l i n e ) 的方法 5 9 来解决编辑全局( o v e r a l l ) 且维持细节的问题。最初需 要用户设计( 引入) 到一个显式的层次结构与模型中，接着在1 9 9 1 年，他们讨 论了递归的插值于一组网格化的数据点( 6 r i d d e dd a t a ) 从而自动生成一张有 层次结构的曲面以达到逼近的目的。整个过程是一个从粗到精 ( c o a r s e t o f i n e ) 的逼近，先做一个大致的逼近，再反复修正逼近( r e f i n i n g ) 误差大的区域，这样一步一步地从一个较粗糙的网格到一个较精细的网格来提 高逼近的精度直至整张曲面控制在允许的误差范围之内。这种方法能提供很好 的连续性，并且具有修改方便的优点 5 9 6 0 。目前f o r s e y 的h s p li n e 还只 能处理网格点数据插值( 数据点可映射到二维网格上) ，且数据结构复杂，所以 它的应用仅限于规则网格。 d a v i df o r s e y 是第一位使用b 一样条加细( r e f i n e m e n t ) 公式构造曲面的多 尺度表示的。几年以后这个思想被用来构造使用三次端点插值b 一样条基函数的 小波的多尺度曲面表示。( 参见 6 1 的6 1 节) 。9 0 年后，相继有许多人做了类 似的研究，其出发点近似，但是方法，名字有所差异。其中包括有g u n t h e r g r e i n e r 和k a ih o r m a n n ( 1 9 9 7 ) 6 2 ，s l e e 等的m u l t i l e v e lb - s p l i n e ( 1 9 9 7 ) 6 5 ，以上都是张量积的b 一样条，扩展到三角片上的有a d r e g e r 等人的多分 辨三角形b _ 样条曲面( m u l t i r e s o l u t i o nt r i a n g u l a rb - s p l i n es u r f a c e s ) ( 1 9 9 7 ) 6 3 6 4 。随后每个方面又有其各自的进展 有层次结构的曲面( h i e r a r c h i c a ls u r f a c e ) 是一种特殊的曲面表示法， 混合了粘贴曲面( p a s t e ds u r f a c e ) 和细分曲面( s u b d i v i s i o ns u r f a c e ) 的 一些因素。样条曲面是重要的一类细分曲面，这类细分曲面的极限可用显式的 函数表示。在曲面的局部应用细分规则，引入更高的细节( h i g h e rd e t a i l ) 散 布于相对低的细节( l o wd e t a i l ) 之内，并将高细节的部分通过曲面粘贴( s u r f a c e 中山大学博士学位论文 p a s t i n g ) 的过程，作为偏移( o f f s e t ) 引入进来，这就是有层次结构的曲面， 如果用的是b 一样条则是层次b 一样条曲面( h i e r a r c h i c a lb - s p l