（计算机应用技术专业论文）混合有理插值方法及其在图形图像中的应用.pdf

台肥工业大学博士学位论文 摘要 从给定的离散点的值去构造一个连续定义的函数，使得它与被逼近的函数在给定点 的值完全一致，这样的问题称为插值问题。在信息的存储、处理、分析、传输日益数字 化的今天，插值问题无处不在。多项式插值是整个数值逼近的基础，由于结构简单、便 于计算和应用，它被广泛应用于方程求根、函数逼近、数值微分、数值积分、积分和微 分方程数值解等。但是，高次多项式插值的龙格现象表明多项式插值的不灵活性限制了 它的应用。有理插值适合于逼近有极点的函数，且收敛速度比多项式插值快，但是有理 插值( 如t h i e l e 型连分式插值) 涉及存在性问题和不可达点问题。鉴于这些原因，本文开 展了混合有理插值等方面的研究。本文的主要工作可归纳如下： 在n e w t o n t h i e l e 插值系数算法的基础上，本文进一步给出了求值算法，所得到的 求值算法便于使用并具有继承性。给出的数值例子表明了算法的有效性。 为了解决传统的t h i e l e 型连分式插值中遇到的逆差商不存在或不可达点的问题，研 究了修正的t h i e l e 型连分式插值。首先，本文给出了计算简便的不可达点判定方法，进 一步给出了修正t h i e l e 型连分式插值。 通过引入对称混合差商，得到了新的二元混合有理插值的有效计算方法；给出了误差 估计；进一步研究了其极限形式，得到了函数的混合展开式。 将插值点集划分为一些子集( 块) ，在每个子集( 块) 上选择插值然后用类似于n e w t o n 插值、l a g r a n g e 插值或t h i e l e 型连分式插值的格式进行装配得到了各种新的一元或二 元块混合有理插值格式。给出了块混合有理插值的算法和相应的误差估计。这些混合有 理插值格式包含传统的n e w t o n 插值、l a g r a n g e 插值或t h i e l e 型连分式插值作为特例。 通过数值例子说明了新方法的有效性。 本文将传统的l a g r a n g e 插值方法和p a d e 逼近相结合，构造了一种新的混合有理插 值。对于每个插值节点处给定的形式幂级数，先在每个插值节点处求得其p a d e 逼近，然 后用l a g r a n g e 插值基函数对它们进行加权组合，从而得到种新的混合有理插值一一广 义l a g r a n g e 混合有理插值。 新的混合有理插值方法通过选择每个插值节点处的p a d e 逼 近，可以获得不同的混合有理插值，且包含传统的l a g r a n g e 插值作为特例。为了得到更 精确的插值，进一步研究了基于p a d e 型逼近和基于扰动p a d e 逼近的混合有理插值。给 出的数值例子表明了新方法的有效性。 本文将文献 7 9 中的三次多结点样条插值方法用于图像插值，研究了三次多结点样条 插值公式的逼近精度，给出了相应的边界条件，分析了作为插值核函数的三次多结点样 条的频域特性。与三次卷积插值的比较表明，上述方法可获得更高质量的插值图像。通 过引入更多的自由结点，本文构造了具有和三次卷积核函数相同的支撑和逼近阶、更高 的正则性的新的三次多结点样条插值核函数，分析了插值的逼近阶并给出了相应的边界 合肥工业大学博士学位论文 条件，得到了新的图像插值公式；为处理边缘失真，以上述公式为基础，进一步构造了 自适应的图像插值公式。在保证图像插值算法的效率的前提下，所得到的插值图像具有 更好的质量。 最后，本文将上述新的三次多结点样条应用于外形设计，构造了一种新的有理三次多 结点样条插值蓝线与曲面，并讨论了此类曲线与曲面的性质。 本文的创新点包括： 1 将插值点集划分为些子集( 块) 。在每个子集( 块) 上选择插值，然后用类 似于n e w t o n 插值、l a g r a n g e 插值或t h i e l e 型连分式插值的格式进行装配， 得到了各种新的一元或二元块混合有理插值格式，给出了相应的算法和相应 的误差估计。 2 本文将传统的l a g r a n g e 插值方法和p a d e 逼近相结合，构造了一种新的混合 有理插值。对于每个插值节点处给定的形式幂级数，先在每个插值节点处求 得其p a d e 逼近，然后用l a g r a n g e 插值基函数对它们进行加权组合，从而得 到了一种新的混合有理插值一广义l a g r a n g e 混合有理插值。为了得到更精确 的插值，进一步研究了基于p a d e 型逼近和基于扰动p a d e 逼近的混合有理插 值。 3 通过引入更多的自由结点，本文构造了新的三次多结点样条插值核函数，分 析了其逼近阶并给出了相应的边界条件，进而得到了新的图像插值公式：为 处理边缘失真，进一步构造了自适应的图像插值公式。最后，本文将上述新 的三次多结点样条应用于外形设计，构造了一种新的有理三次多结点样条插 值曲线与曲面，并讨论了此类曲线与曲面的性质。 关键词： 混合有理插值，递推算法，块混合有理插值，p a d e 逼近，三次多结点样条。 合肥工业大学博士学位论文 a b s t r a c t t h ep r o b l e mo fc o n s t r u c t i n gac o n t i n u o u s l yd e f i n e df u n c t i o nf r o mg i v e nd i s c r e t ed a t a i su n a v o i d a b l ew h e n e v e ro n ew i s h e st om a n i p u l a t et h ed a t ai naw a yt h a tr e q u i r e s i n f o r m a t i o nn o ti n c l u d e de x p l i c i t l yi nt h ed a t a i nt h i sa g eo fe v e r - i n c r e a s i n g d i g i t i z a t i o n i nt h es t o r a g e ，p r o c e s s i n g ，a n a l y s i s ，a n dc o m m u n i c a t i o no fi n f o r m a t i o n ，i ti sn o td i f f i c u l tt o f i n de x a m p l e so fa p p l i c a t i o n sw h e r et h i sp r o b l e mo c c u r s t h er e l a t i v e l ye a s i e s ta n di nm a n y a p p l i c a t i o n so f t e nm o s td e s i r e da p p r o a c ht os o l v et h ep r o b l e mi si n t e r p o l a t i o n w h e r ea 1 1 a p p r o x i m a t i n gf i m c t i o ni sc o n s t r u c t e di ns u c haw a y a st oa g r e ep e r f e c t l yw i t ht h eu s u a l l y r r l k n o w no r i g i n a lf u n c t i o na tt h eg i v e nm e a s u r e m e n tp o i n t s p o l y n o m i a li n t e r p o l a n t sa r e u s e da st h eb a s i cm e a n so f a p p r o x i m a t i o ni nn e a r l ya l la r e a so f n u m e r i c a la n a l y s i s t h e ya r e u s e di nt h es o l u t i o no fe q u a t i o n sa n di nt h ea p p r o x i m a t i o no ff u n c t i o n s ，o fi n t e g r a l sa n d d e r i v a t i v e s ，o fs o l u t i o n so fi n t e g r a la n dd i f f e r e n t i a le q u a t i o n s ，e t c p o l y n o m i a li n t e r p o l a n t s o w et h i sp o p u l a r i t yt ot h e i rs i m p l es t r u c t u r e ，w h i c hm a k e si te a s yt oc o n s t r u c te f f e c t i v e a p p r o x i m a t i o n sa n dt h e nm a k eu s eo ft h e m e x a m p l e so fm e r o m o r p h i cf i m c t i o n sf o rw h i c h t h ep o l y n o m i a li n t e r p o l a n td o e sn o tc o n v e r g eu n i f o r m l yw e r eg i v e nb ym 6 r a ya n dl a t e r r u n g e - - e s p e c i a l l yt h el a t t e rh a sb e c o m ew e l lk n o w na n dc a nb ef o u n di nm o s tm o d e m b o o k so nt h et o p i c t h e s ef m d i n g sr e v e a l e dt h e “i n f l e x i b i l i t y o fa l g e b r a i cp o l y n o m i a l sa n d t h e i rl i m i t e da p p l i c a b i l i t yt oi n t e r p o l a t i o n o nt h eo t h e rh a n d ，am o s tp o w e r f u li n t e r p o l a t i o n i st h eo n eu s i n gr a t i o n a lf u n c t i o n s t h em a i na d v a n t a g eo fr a t i o n a lf u n c t i o n so v e r p o l y n o m i a l si st h e i ra b i l i t yt om o d e lf i m c t i o n s 、 r i mn o n l i n e a rc h a r a c t e r s ( s u c ha sp o l e so r o t h e r s i n g u l a r i t y ) ，t h e i r f a s t c o n v e r g e n c em a k e s o n ea c h i e v ef l a i l a c c u r a c y f o r a p p r o x i m a t i o n t h e r ei s a i li n s t a b l ep r o b l e mo fc o m p u t a t i o nf o r t h i e l e - t y p ec o n t i n u e d f r a c t i o n si n t e r p o l a n t s ，w h i c hm e a n st h e r ea r ei n v e r s ed i f f e r e n c e sb e i n gi n f i n i t eo rt h e r ea r e s o m eu n a t t a i n a b l ep o i n t s f o rt h e s er e a s o n s ，t h i sd i s s e r t a t i o nf o c u s e so nt h es t u d yo fv a r i o u sb l e n d i n gr a t i o n a l i n t e r p o l a t i o n n l em a i nc o n t r i b u t i o n sf i r ea sf o l l o w s ： f i r s to fa 1 1 as u c c e s s i v ea l g o r i t h mf o rn e w t o n t h i e l e sr a t i o n a li n t e r p o l a t i o no v e r r e c t a n g u l a rg r i d si sp r e s e n t e d t l ep r o p o s e ds u c c e s s i v ei n t e r p o l a t i o na l g o r i t h mc a nc a r r y o nt h ee x i s t i n gi n t e r m e d i a t ec o m p u t a t i o n si fn e w p o i n t sa r ea d d e dt ot h eg r i d n u m e r i c a l e x a m p l e sa r eg i v e nt os h o wt h ee f f e c t i v e n e s so f o u rr e e u r s i v ea l g o r i t h m s s e c o n d l y , t od e a l 、v i lt h ep r o b l e mo fi n s t a b i l i t 3 , o fc o m p u t a t i o nf o rt h i e l e - t y p e c o n t i n u e df r a c t i o n si n t e r p o l a n t s ，w h i c hm e a n st h e r ea r ei n v e r s ed i f f e r e n c e sb e i n gi n f i l l i t eo r t h e r ea r es o m eu n a t t a i n a b l ep o i n t sw h e nw ec o m p u t et h er a t i o n a li n t e r p o l a n t sb a s e do n t h i e l e sc o n t i n u e df r a c t i o n s m o d i f i e dt h i e l e t y p eb l e n d i n gc o n t i n u e df r a c t i o ni n t e r p o l a t i o n v i an e w t o n 。si n t e r p o l a t i n gp o l y n o m i a li sp r e s e n t e d m o d i f i e dn e w t o n t l l i e l e 。sr a t i o n a l i n t e r p o l a t i o ni sd i s c u s s e d t h ep r o p o s e dm o d i f i e dm e t h o df o ri n t e r p o l a t i o nu s i n gr a t i o n a l f u n c t i o n sc a nb ev a l i da l lt h es a l d _ ei fs o m ei n v e r s ed i f f e r e n c e sd o n te x i s to rs o m e u n a t t a i n a b l ep o i n t so c c u r ；n u m e r i c a le x a m p l e sa r eg i v e nt os h o wt h ee f f e c t i v e n e s so fo u r a l g o r i t h m s 合肥工业大学博士学位论文 t h i r d l y , i nt h i sd i s s e r t a t i o n ，w ee x t e n dt h ep o i n tb a s e di n t e r p o l a t i o nt ot h eb l o c k b a s e d i n t e r p o l a t i o n i n s p k e db yt h ei d e ao ft h em o d e r na r c h i t e c t u r a ld e s i g n ，w ef i r s td i v i d et h e o r i g i n a ls e to fs u p p o r tp o i n t si n t os o m es u b s e t s ( b l o c k s ) ，t h e nc o n s t r u c te a c hb l o c kb yu s i n g w h a t e v e ri n t e r p o l a t i o nm e a n s 1 i n e a ro rr a f t o n a la n df i n a l l ya s s e m b l et h e s eb l o c k sb y n e w t o n sm e t h o d ，l a g r a n g e sm e t h o d ，o rt h i e l e sm e t h o dt os h a p et h ew h o l ei n t e r p o l a t i o n s c h e m e t h ea l g o r i t h m sf o rt h e s ei n t e r p o l a n t sa r ep r e s e n t e da n dt h ee r r o re s t i m a t i o n sa r e g i v e n o u rm e t h o do f f e r sm a n yf l e x i b l ei n t e r p o l a t i o ns c h e m e sf o rc h o i c e sw h i c hi n c l u d e t h ec l a s s i c a ln e w t o n 。s p o l y n o m i a li n t e r p o l a t i o n o r t l i e l e t y p e c o n t i n u e df r a c t i o n i n t e r p o l a t i o na s i t ss p e c i a lc a s e e a c hb i v a r i a t ea n a l o g yi sa l s od i s c u s s e da n dn u m e r i c a l e x a m p l e sa r eg i v e nt os h o wt h ee f f e c t i v e n e s so f o u rm e t h o d f o u r t h l y , i nt h i sd i s s e r t a t i o n ，w ea d o p tt h ei d e ao ft h el a g r a n g e si n t e r p o l a t i o nt o c o n s t r u c tak i n do fb l e n d i n gr a t i o n a li n t e r p o l a n t sv i ap a d ea p p r o x i m a t i o n f o rag i v e n f o r m a lp o w e rs e r i e sa te v e r yi n t e r p o l a t i o nn o d e ，w eb u i l dap a d ea p p r o x i m a n ta n dt h e n b l e n dt h e mb ym e a n so ft h el a g r a n g ei n t e r p o l a t i n gb a s i sf u n c t i o n st of o r man e w b l e n d i n g r a t i o n a li n t e r p o l a t i o n g e n e r a l i z e dl a g r a n g eb l e n d i n gr a t i o n a l i n t e r p o l a t i o n t h e r ea r e m a n yc h o i c e st om a k et od e t e r m i n et h ei n i t i a lp a d ea p p r o x i m a n ta te v e r yi n t e r p o l a t i o nn o d e ， o n rm e t h o do f f e r sm a n yf l e x i b l ei n t e r p o l a t i o ns c h e m e sf o rc h o i c e sw h i c hi n c l u d et h e c l a s s i c a ll a g r a n g e sp o l y n o m i a li n t e r p o l a t i o na si t ss p e c i a lc a s e p a r e - t y p ea p p r o x i m a t i o n b a s e db l e n d i n gr a t i o n a li n t e r p o l a t i o na n dp e r t u r b e dp a d 6a p p r o x i m a t i o nb a s e db l e n d i n g r a t i o n a li n t e r p o l a t i o na r ea l s os t u d i e df o ra c c u r a t ei n t e r p o l a t i o n n u m e r i c a le x a m p l e sa r e g i v e nt os h o wt h ee f f e c t i v e n e s so f o u rm e t h o d f i f t h l y , i n o r d e rt oo b t a i na n i n t e r p o l a t e di m a g ew i t h as u p e r i o r q u a l i t y , t h i s d i s s e r t a t i o np r e s e n t sa ne f f i c i e n ti m a g ei n t e r p o l a t i o nt e c h n i q u eu s i n gm a n y - k n o ts p l i n e b a s i sf u n c t i o nw i t hc o m p a c ts u p p o r t ( s e e 【7 9 ) t h eo n e d i m e n s i o n a lm a n y k n o ts p l i n e s i n t e r p o l a t i o na l g o r i t h mi se x t e n d e dt ot h ec a s ei no ft w od i m e n s i o n s ，w h i c hi sa p p l i e dt o i m a g ep r o c e s s i n g t h e nt h ea c c u r a c yo fa p p r o x i m a t i o n ，r e g u l a r i t yo fm a n y - k n o ts p l i n e s i n t e r p o l a t i o nm e t h o da n df r e q u e n c yp r o p e r t yo f t h ei n t e r p o l a t i o nk e r n e la r ew o r k e do u tf o r c o m p a r i s o n i tc a nb es h o w nt h a tt h ea p p r o a c hi ss u p e r i o rt oo t h e rm e t h o d s s u c ha sc u b i c c o n v o l u t i o n t h ee x p e r i m e n tr e s u l t sa r ep r e s e n t e dt os h o wt h a tt h ea l g o r i t h mp r o d u c e sa r e c o n s t r u c t e di m a g ew i t has u p e r i o rq u a l i t y m o r e o v e 5t h i sd i s s e r t a t i o np r e s e n t san e wc 2 c u b i cm a n y 。k n o ts p l i n ei n t e r p o l a t i o nk e r n e lf u n c t i o nw i t hc o m p a c ts u p p o r t ( 一2 ，2 ) t h e i n t e r p o l a t i o nf o r m u l ai sc o n s t r u c t e dv i ad e g r e e so f 盘e e d o mf r o mi n s e r t i n gk n o t s t h e a p p r o x i m a t i o no r d e ro ft h ei n t e r p o l a t i o nw i t ht h ea p p r o p r i a t eb o u n d a r yc o n d i t i o n sa n d c o n s t r a i n t si sa n a l y z e d t h eo n e d i m e n s i o n a lm a n y - k n o t s p l i n e si n t e r p o l a t i o na l g o r i t h mi s e x t e n d e dt ot h a to f t w od i m e n s i o n s ，w h i c hi sa l s oa p p l i e dt oi m a g e p r o c e s s i n g a na d a p t i v e i n t e r p o l a t i o nm e t h o di sp r e s e n t e db a s e do na p p l y i n ga ni n v e r s eg r a d i e n tt ot h ea b o v e i n t e r p o l a t i o nf o r m u l a t h ee x p e r i m e n tr e s u l t sa r ep r e s e n t e dt os h o wt h a t 血ea d a p t i v e i n t e r p o l a t i o na l g o r i t h mp r o d u c e sar e c o n s t r u c t e di m a g ew i t has u p e r i o rq u a l i t yi nt e r m so f e r r o ra n dp s n r f i n a l l y , i n t e r a c t i v ec a g ds y s t e m sp r o d u c ef a s t e ra n dm o r ea c c u r a t ec u r v ea n ds u r f a c e a n a l y s i sa n dd e s i g nb ym e a n so fg e o m e t r i co ra l g e b r a i ci n t e r p o l a t i o na l g o r i t h m s i nt h i s 合肥工业大学博士学位论文 d i s s e r t a t i o n ，an e wk i n do fr a t i o n a li n t e r p o l a t i o nc u r v e sa n ds u r f a c e sa r ep r e s e n t e db a s e do n t h ea b o v en e wc 2c u b i cm a n y - k n o ts p l i n eb a s i sf u n c t i o n t h ep r o p e r t i e so ft h ec u b i c r a t i o n a lm a n y ，k n o ts p l i n ei n t e r p o l a t i o nc u r v e sa n ds u r f a c e sa r ed i s c u s s e d w h a tf o l l o w sa r et h em a i nr e s u l t sa c h i e y e di nt h i sd i s s e r t a t i o n 1 i n s p i r e db yt h ei d e ao ft h em o d e ma r c h i t e c t u r a ld e s i g n , w ef i r s td i v i d et h eo r i g i n a ls e t o fs u p p o r tp o i n t si n t os o m es u b s e t s ( b l o c k s ) ，t h e nc o n s t r u c te a c hb l o c kb yu s i n g w h a t e v e ri n t e r p o l a t i o nm e a n s ，l i n e a ro rr a t i o n a la n df i n a l l ya s s e m b l et h e s eb l o c k sb y n e w t o n sm e t h o d 。l a g r a n g e sm e t h o d 。o rt 1 1 i e l e sm e t h o dt os h a p et h ew h o l e i n t e r p o l a t i o ns c h e m e t h ea l g o r i t h m sf o rt h e s ei n t e r p o l a n t sa r ep r e s e n t e da n d t h ee r r o r e s t i m a t i o n sa r eg i v e i l 2 w ea d c 。p tt h ei d e ao ft h el a g r a n g e si n t e r p o l a t i o nt oc o n s t r u c tak i n do fb l e n d i n g r a t i o n a li n t e r p o l a n t sv i ap a d ea p p r o x i m a t i o n f o rag i v e nf o r m a lp o w e rs e r i e sa te v e r y i n t e r p o l a t i o nn o d e w eb u i l dap a d ea p p r o x i m a n ta n dt h e nb l e n d 也e mb ym e a n so f t h e l a g r a n g ei n t e r p o l a t i n g b a s i sf u n c t i o n st of o r man e wb l e n d i n gr a t i o n a l i n t e r p o l a t i o n 一g e n e r a l i z e dl a g r a n g eb l e n d i n gr a t i o n a li n t e r p o l a t i o n t h e r ea r em a n y c h o i c e st om a k et od e t e r m i n et h ei n i t i a lp a d ea p p r o x i m a n ta te v e r yi n t e r p o l a t i o nn o d e ， o u rm e t h o do f f e r sm a n yf l e x i b l ei n t e r p o l a t i o ns c h e m e sf o rc h o i c e sw h i c hi n c l u d et h e c l a s s i c a l l a g r a n g e sp o l y n o m i a li n t e r p o l a t i o n a s i t s s p e c i a l c a s e p a d e - t y p e a p p r o x i m a t i o nb a s e db l e n d i n gr a t i o n a li n t e r p o l a t i o na n dp e r t u r b e dp a d 6a p p r o x i m a t i o n b a s e db l e n d i n gr a t i o n a li n t e r p o l a t i o na r ea l s os t u d i e df o ra c c u r a t ei n t e r p o l a t i o n 3 w ep r e s e n tan e wc 2c u b i cm a n y - k n o ts p l i n ei n t e r p o l a t i o nk e r n e l f u n c t i o nw i t h c o m p a c ts u p p o r t 【_ 2 ，2 ) t h ei n t e r p o l a t i o nf o r m u l ai sc o n s t r u c t e dv i ad e g r e e so f f r e e d o mf r o mi n s e r t i n gk n o t s t h ea p p r o x i m a t i o no r d e ro ft h ei n t e r p o l a t i o nw i t ht h e a p p r o p r i a t eb o u n d a r yc o n d i t i o n sa n dc o n s t r a i n t si sa n a l y z e d t h eo n e d i m e n s i o n a l m a n y - k n o ts p l i n e si n t e r p o l a t i o na l g o r i t h mi se x t e n d e dt ot 1 1 a to ft w od i m e n s i o n s w h i c h i sa p p l i e dt oi m a g ep r o c e s s i n g a na d a p t i v ei n t e r p o l a t i o nm e t h o di sp r e s e n t e db a s e do n a p p l y i n ga ni n v e r s eg r a d i e n tt ot h ea b o v ei n t e r p o l a t i o nf o r m u l a m o r e o v e r , an e wk i n d o fr a t i o n a l i n t e r p o l a t i o nc u r v e sa n ds u r f a c e s a r ep r e s e n t e db a s e do nt h ec u b i c m a n y - k n o ts p l i n ef u n c t i o n t h ep r o p e r t i e so ft h ec u b i cr a t i o n a lm a n y - k n o ts p l i n e i n t e r p o l a t i o nc 1 n v e sa n ds u r f a c e sa r ed i s c u s s e d k e y w o r d s ：b l e n d i n gr a t i o n a li n t e r p o l a t i o n ，r e c u r s i v ea l g o r i t h m ，b l o c kb a s e db l e n d i n g r a t i o n a li n t e r p o l a t i o n ，p a d ea p p r o x i m a t i o n ，c u b i cm a n y - k n o t s p l i n e s 台肥工业大学博士学位论文 插图清单 图6 2 原曲线和插值曲线比较 图6 3 原曲线与插值曲线比较 图6 4 原曲线与插值曲线比较 图7 2 1 插值函数的空域曲线和幅频特性曲线图 图7 2 2 不同插值方法的结果图像 图7 3 3 不同插值方法的误差图像 图8 2 三次多结点样条函数的图形 ，7 8 ，8 0 。8 1 。8 6 ，8 7 9 3 9 6 台肥工业大学博士学位论文 表格清单 表2 5 1 表2 5 2 表3 2 3 一 表3 3 3 表4 2 2 1 表4 2 2 2 表4 2 2 3 表4 2 2 4 表4 2 2 5 表5 2 4 表5 2 5 表5 3 5 表5 4 5 表5 5 4 表6 2 插值误差比较 表7 2 2 插值结果图像的峰值信噪比的比较 表7 3 3 与其它插值算法p s n r 比较 表8 2 两种插