非均勻三次B樣條曲線插值的GS-PIA算法

劉曉艷,鄧重陽(yáng)

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

摘要：提出了非均勻三次B樣條曲線插值的GS-PIA算法。該算法與解線性方程組的高斯-賽德?tīng)柕ㄓ型瑯拥膬?yōu)點(diǎn)，即把已經(jīng)更新的點(diǎn)參與到迭代過(guò)程來(lái)優(yōu)化迭代過(guò)程；同時(shí)也具有漸進(jìn)迭代逼近方法的優(yōu)點(diǎn)，即有明確的幾何意義，并能得到一系列逐次逼近插值點(diǎn)的非均勻三次B樣條曲線。

關(guān)鍵詞：非均勻三次B樣條；迭代算法；漸進(jìn)逼近

DOI: 10.13954/j.cnki.hdu.2015.02.019

非均勻三次B樣條曲線插值的GS-PIA算法

劉曉艷,鄧重陽(yáng)

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

摘要：提出了非均勻三次B樣條曲線插值的GS-PIA算法。該算法與解線性方程組的高斯-賽德?tīng)柕ㄓ型瑯拥膬?yōu)點(diǎn)，即把已經(jīng)更新的點(diǎn)參與到迭代過(guò)程來(lái)優(yōu)化迭代過(guò)程；同時(shí)也具有漸進(jìn)迭代逼近方法的優(yōu)點(diǎn)，即有明確的幾何意義，并能得到一系列逐次逼近插值點(diǎn)的非均勻三次B樣條曲線。

關(guān)鍵詞：非均勻三次B樣條；迭代算法；漸進(jìn)逼近

DOI:10.13954/j.cnki.hdu.2015.02.019

收稿日期：2014-06-16

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61003194,61370166)

通信作者：

作者簡(jiǎn)介：劉曉艷(1989-)，女，河南泌陽(yáng)人，在讀研究生，計(jì)算機(jī)圖形學(xué).鄧重陽(yáng)副教授，E-mail: dcy@hdu.edu.cn.

中圖分類號(hào)：O242

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2015)02-0079-04

Abstract:This paper presents a non-uniform cubic B-spline curve interpolation algorithm of GS-PIA. The algorithm and the Gauss-Seidel iterative method of solving linear equations have the same advantages， namely the points involved in the iterative process which has been updated to optimize the iterative process. At the same time， the algorithm also has the advantage of progressive iterative approximation method， namely， there is a clear geometric significance， and can make a series of non-uniform cubic B-spline curve approximation interpolation points．

0引言

數(shù)據(jù)擬合是求解現(xiàn)實(shí)世界中科學(xué)與工程問(wèn)題的基本工具之一。漸進(jìn)迭代逼近(Progressive Iteration Approximation，PIA)是一種將數(shù)據(jù)點(diǎn)擬合成為曲線或曲面的技術(shù)。文獻(xiàn)[1]在研究樣條擬合問(wèn)題時(shí)，就基于盈虧修正思想提出了均勻三次B樣條曲線的幾何迭代算法。文獻(xiàn)[2]在一次學(xué)術(shù)交流討論會(huì)中也闡述了這一思想。文獻(xiàn)[3]證明了對(duì)于非均勻三次B樣條曲線和曲面同樣具有PIA性質(zhì)。文獻(xiàn)[4]將PIA推廣到了擁有歸一化全正基函數(shù)的混合曲線、曲面中。文獻(xiàn)[5]證明了有理B樣條曲線曲面同樣具有這個(gè)PIA性質(zhì)。文獻(xiàn)[6]比較了不同種類基函數(shù)的選取對(duì)于收斂速度的影響，并且證明了B樣條基函數(shù)不僅具有保形和PIA性質(zhì)，而且具有最快的收斂速度。文獻(xiàn)[7]設(shè)計(jì)了一種PIA方法，本質(zhì)上來(lái)說(shuō)就是均勻周期三次B樣條的PIA方法。文獻(xiàn)[8]設(shè)計(jì)了一種帶權(quán)值的PIA來(lái)加快擬合的收斂速度。文獻(xiàn)[9]發(fā)現(xiàn)了PIA的局部性質(zhì)，即漸進(jìn)迭代逼近可以為每一個(gè)數(shù)據(jù)點(diǎn)分別設(shè)定擬合精度。文獻(xiàn)[10]通過(guò)變換矩陣，提出了一種可以統(tǒng)一傳統(tǒng)PIA方法、帶權(quán)值的PIA方法和局部PIA方法的擴(kuò)展方法。最近，文獻(xiàn)[11]進(jìn)一步提出了LSPIA，即基于PIA的B樣條曲線曲面最小二乘擬合方法。

在考察PIA方法與解線性方程組的經(jīng)典迭代法之間的聯(lián)系時(shí)本文筆者發(fā)現(xiàn)，如果每次迭代時(shí)把已經(jīng)更新的點(diǎn)參與到迭代過(guò)程中去，高斯-賽德?tīng)?Gauss-Seidel，GS)迭代法也可以看作是一種PIA方法，本文稱之為GS-PIA方法。數(shù)值算例表明，非均勻三次B樣條曲線插值的GS-PIA方法是收斂的，而且比以前PIA方法的存儲(chǔ)量更少，收斂速度也更快。

1GS-PIA算法

1.1　PIA算法的導(dǎo)出

文獻(xiàn)[3]中給出了非均勻三次B樣條曲線曲面的漸進(jìn)迭代逼近算法，并證明了這種算法的收斂性。其中非均勻B樣條曲線的漸進(jìn)迭代逼近算法的具體流程如下。

1.2　GS迭代法

設(shè)有線性方程組Ax=b，即：

(1)

1.3　GS-PIA算法的導(dǎo)出

仿照首次迭代知k次迭代后有：

(2)

第j個(gè)控制點(diǎn)的第k+1次調(diào)整量為：

(3)

得到k+1次迭代需要的第j個(gè)控制點(diǎn)：

(4)

那么，第k+1次迭代后的一條非均勻三次B樣條曲線為：

(5)

文獻(xiàn)[3]提出的PIA算法如下：

(6)

通過(guò)比較式(5)和式(6)可知，本文提出的GS-PIA算法的迭代格式中，k層少了一項(xiàng)，因此GS-PIA算法存儲(chǔ)量更少。

2數(shù)值實(shí)例

圖1　采用GS-PIA算法插值三葉玫瑰線上的采樣點(diǎn)

表1　兩種PIA算法插值三葉玫瑰線上的采樣點(diǎn)的誤差

3結(jié)束語(yǔ)

本文提出了用于非均勻三次B樣條曲線插值的GS-PIA算法，數(shù)值算例表明，GS-PIA算法是收斂的，且收斂速度較快，優(yōu)于原來(lái)的PIA算法。同時(shí)該算法存儲(chǔ)更少。但是算法的收斂性如何證明，以及對(duì)于更高次的非均勻B樣條曲線插值，類似的GS-PIA算法是否收斂，收斂速度如何都是值得繼續(xù)探討的問(wèn)題。

參考文獻(xiàn)

[1]齊東旭，田自賢，張玉心，等.曲線擬合的數(shù)值磨光方法[J].數(shù)學(xué)學(xué)報(bào)，1975，18(3):173-184．

[2]De Boor C. How does Agee’s smoothing method work[C]//Proceedings of the 1979 army numerical analysis and computers conference， ARO Report 1979:299-302.

[3]Lin H W， Wang G J， Dong C S. Constructing iterative non-uniform B-spline curve and surface to fit data points[J]. Science in China Series: Information Sciences，2004.47(3):315-331．

[4]Lin H W， Bao H J， Wang G J. Totally positive bases and progressive iteration approximation[J]. Computers & Mathematics with Applications，2005.50(3):575-586．

[5]Shi L， Wang R. An iterative algorithm of NURBS interpolation and approximation[J]. Journal of Mathematical Research and Exposition，2006，26(4):735-743．

[6]Delgado J， Pea J M. Progressive iterative approximation and bases with the fastest convergence rates[J]. Computer Aided Geometric Design，2007，24(1):10-18．

[7]Martin T， Cohen E， Kirby RM. Volumetric parameterization and trivariate B-spline fitting using harmonic function[J]. Computer Aided Geometric Design，2009，26(6):648-664．

[8]Lu L Z. Weighted progressive iteration approximation and convergence analysis[J]. Computer Aided Geometric Design，2010，27(2):129-137．

[9]Lin H W. Local progressive-iterative approximation format for blending curves and patches[J]. Computer Aided Geometric Design，2010，27(4):322-339．

[10]Deng S H， Guan S J， Wang G Z，et al. An Extension of a New Kind of Graphics Fitting Method[J]. Applied Mathematics & Information Sciences，2013，7(2):741-747．

[11]Deng C Y， Lin H W. Progressive and iterative approximation for least squares B-spline curve and surface fitting[J]. Computer-Aided Design，2014，47(1):32-44．

Non-uniform Cubic B-spline Curve Interpolation Algorithm of GS-PIA

Liu Xiaoyan， Deng Chongyang

(SchoolofScience，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Key words: non-uniform cubic B-spline curve; iterative algorithm; progressive approximation