刘晓艳,邓重阳

(杭州电子科技大学理学院，浙江 杭州 310018)

摘要：提出了非均匀三次B样条曲线插值的GS-PIA算法。该算法与解线性方程组的高斯-赛德尔迭代法有同样的优点，即把已经更新的点参与到迭代过程来优化迭代过程；同时也具有渐进迭代逼近方法的优点，即有明确的几何意义，并能得到一系列逐次逼近插值点的非均匀三次B样条曲线。

关键词：非均匀三次B样条；迭代算法；渐进逼近

DOI: 10.13954/j.cnki.hdu.2015.02.019

非均匀三次B样条曲线插值的GS-PIA算法

刘晓艳,邓重阳

(杭州电子科技大学理学院，浙江 杭州 310018)

摘要：提出了非均匀三次B样条曲线插值的GS-PIA算法。该算法与解线性方程组的高斯-赛德尔迭代法有同样的优点，即把已经更新的点参与到迭代过程来优化迭代过程；同时也具有渐进迭代逼近方法的优点，即有明确的几何意义，并能得到一系列逐次逼近插值点的非均匀三次B样条曲线。

关键词：非均匀三次B样条；迭代算法；渐进逼近

DOI:10.13954/j.cnki.hdu.2015.02.019

收稿日期：2014-06-16

基金项目：国家自然科学基金资助项目(61003194,61370166)

通信作者：

作者简介：刘晓艳(1989-)，女，河南泌阳人，在读研究生，计算机图形学.邓重阳副教授，E-mail: dcy@hdu.edu.cn.

中图分类号：O242

文献标识码：A

文章编号：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引言

数据拟合是求解现实世界中科学与工程问题的基本工具之一。渐进迭代逼近(Progressive Iteration Approximation，PIA)是一种将数据点拟合成为曲线或曲面的技术。文献[1]在研究样条拟合问题时，就基于盈亏修正思想提出了均匀三次B样条曲线的几何迭代算法。文献[2]在一次学术交流讨论会中也阐述了这一思想。文献[3]证明了对于非均匀三次B样条曲线和曲面同样具有PIA性质。文献[4]将PIA推广到了拥有归一化全正基函数的混合曲线、曲面中。文献[5]证明了有理B样条曲线曲面同样具有这个PIA性质。文献[6]比较了不同种类基函数的选取对于收敛速度的影响，并且证明了B样条基函数不仅具有保形和PIA性质，而且具有最快的收敛速度。文献[7]设计了一种PIA方法，本质上来说就是均匀周期三次B样条的PIA方法。文献[8]设计了一种带权值的PIA来加快拟合的收敛速度。文献[9]发现了PIA的局部性质，即渐进迭代逼近可以为每一个数据点分别设定拟合精度。文献[10]通过变换矩阵，提出了一种可以统一传统PIA方法、带权值的PIA方法和局部PIA方法的扩展方法。最近，文献[11]进一步提出了LSPIA，即基于PIA的B样条曲线曲面最小二乘拟合方法。

在考察PIA方法与解线性方程组的经典迭代法之间的联系时本文笔者发现，如果每次迭代时把已经更新的点参与到迭代过程中去，高斯-赛德尔(Gauss-Seidel，GS)迭代法也可以看作是一种PIA方法，本文称之为GS-PIA方法。数值算例表明，非均匀三次B样条曲线插值的GS-PIA方法是收敛的，而且比以前PIA方法的存储量更少，收敛速度也更快。

1GS-PIA算法

1.1　PIA算法的导出

文献[3]中给出了非均匀三次B样条曲线曲面的渐进迭代逼近算法，并证明了这种算法的收敛性。其中非均匀B样条曲线的渐进迭代逼近算法的具体流程如下。

1.2　GS迭代法

设有线性方程组Ax=b，即：

(1)

1.3　GS-PIA算法的导出

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

(2)

第j个控制点的第k+1次调整量为：

(3)

得到k+1次迭代需要的第j个控制点：

(4)

那么，第k+1次迭代后的一条非均匀三次B样条曲线为：

(5)

文献[3]提出的PIA算法如下：

(6)

通过比较式(5)和式(6)可知，本文提出的GS-PIA算法的迭代格式中，k层少了一项，因此GS-PIA算法存储量更少。

2数值实例

图1　采用GS-PIA算法插值三叶玫瑰线上的采样点

表1　两种PIA算法插值三叶玫瑰线上的采样点的误差

3结束语

本文提出了用于非均匀三次B样条曲线插值的GS-PIA算法，数值算例表明，GS-PIA算法是收敛的，且收敛速度较快，优于原来的PIA算法。同时该算法存储更少。但是算法的收敛性如何证明，以及对于更高次的非均匀B样条曲线插值，类似的GS-PIA算法是否收敛，收敛速度如何都是值得继续探讨的问题。

参考文献

[1]齐东旭，田自贤，张玉心，等.曲线拟合的数值磨光方法[J].数学学报，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