Grouped progressive iterative approximation method of data fitting

Guo Zheng; Li Zhang; Shijie Zhang; Zhuangping Du; Yi Liu; Jieqing Tan

doi:10.11834/jig.170559

Computer Graphics | Views : 0 下载量: 83 CSCD: 0

PDF
Export
Share
Collection
Album

Grouped progressive iterative approximation method of data fitting
Vol. 23, Issue 7, Pages: 1081-1090(2018)
Received：03 November 2017，

Revised：2018-1-28，

Published：16 July 2018
DOI： 10.11834/jig.170559
稿件说明：

移动端阅览

DOI：

Guo Zheng, Li Zhang, Shijie Zhang, Zhuangping Du, Yi Liu, Jieqing Tan. Grouped progressive iterative approximation method of data fitting[J]. Journal of Image and Graphics, 2018, 23(7): 1081-1090. DOI： 10.11834/jig.170559.

摘要

目的

在计算机辅助设计领域里，曲线或曲面的渐进迭代逼近（PIA）性质在插值与拟合问题中有着广泛的应用。如果直接使用PIA方法对所有的数据点集进行拟合，那么在拟合大规模数据点时就缺少一定的灵活性。为了进一步提高渐进迭代逼近方法在拟合大规模点集时的灵活性，提出基于分组的渐进迭代逼近方法。

方法

首先对待拟合点集进行分组；其次对分组后的点集采用PIA方法或是基于最小二乘的渐进迭代逼近方法（LSPIA）来得到一组插值或拟合精度不断改善的曲线/曲面；最后运用曲线/曲面拼接算法保证曲线/曲面的连续性，得到1条/张插值或拟合于给定点集的曲线/曲面。

结果

给定相同的数据点集，分别采用分组PIA方法，PIA方法和LSPIA方法进行拟合。分组PIA方法与PIA方法相比误差减少的倍数与组数相当；分组PIA方法与LSPIA方法相比误差减少一半。

结论

本文将分组思想引入渐进迭代逼近方法之中，提出了基于分组的渐进迭代逼近方法。该分组算法适用于拟合大规模数据点集，在拟合过程中，可以提高渐进迭代逼近方法在拟合大规模点集时的灵活性；经过理论推导证明了曲线/曲面的迭代效率有所提高，且与PIA方法相比误差有较大的改善。

Abstract

Objective

The progressive iterative approximation (PIA) method has a wide range of applications for solving interpolation and fitting problems in computer-aided design. The PIA format presents an intuitive way of data fitting by adjusting the control points iteratively. This method format generates a sequence of curves/surfaces with fine precision. According to the PIA property

the limit of the curve/surface sequence interpolates the initial data points if the blending basis is normalized and totally positive and its corresponding collocation matrix is nonsingular. To increase the flexibility of the PIA method in the large-scale fitting of data points

a new PIA method

which is based on grouping

is proposed in this work.

Method

First

the initial data points to be fitted are divided into several groups. Second

by applying the PIA or LSPIA method on these grouped data points separately

we can obtain a sequence of curves/surfaces with the PIA property for each group of data. Then

by adjusting the control points on the boundary according to the continuity conditions

a blending algorithm is implemented on these separate curves/surfaces. Thus

we finally acquire one whole curve/surface piece and ensure its continuity. Moreover

by grouping the data points

we can reduce the computation and improve the iteration efficiency.

Result

We use the PIA

LSPIA

and proposed methods on a single data set to fit data points. The grouped PIA method is convergent because we use the PIA or LSPIA method to fit each group of data points. Compared with the fitting error of the PIA method

that of the grouped PIA method decreases according to the number of groups we divide. That is

the more groups we divide

the more the fitting error is reduced. Compared with the fitting error of the LSPIA method

that of the grouped PIA method is lower by approximately one half.

Conclusion

This study mainly aims to combine the grouping idea with the PIA method and proposes a grouped PIA method of fitting the data set. This method not only brings enhanced flexibility to the large-scale fitting of data points but also delivers a higher convergence rate and fewer errors than the PIA and LSPIA methods do. Numerous numerical examples are presented to show the effectiveness of this technique.

关键词

Keywords

references

Qi D X, Tian Z X, Zhang Y X, et al. The method of numeric polish in curve fitting[J]. Acta Mathematica Sinica, 1975, 18(3):173-184.

齐东旭, 田自贤, 张玉心, 等.曲线拟合的数值磨光方法[J].数学学报, 1975, 18(3):173-184.

de Boor C. How does agee's smoothing method work?[R]. Washington, DC: Army Research Office, 1979: 299-302. https://www.researchgate.net/publication/266720210_How_does_Agees_smoothing_method_work .

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.[DOI:10.1360/02yf0529]

Lin H W, Bao H J, Wang G J. Totally positive bases and progressive iteration approximation[J]. Computers&Mathematics with Applications, 2005, 50(3-4):575-586.[DOI:10.1016/j.camwa.2005.01.023]

Chen J, Wang G J, Jin C J. Two kinds of generalized progressive iterative approximations[J]. Acta Automatica Sinica, 2012, 38(1):135-139.

陈杰, 王国瑾, 金聪健.两类推广的渐近迭代逼近[J].自动化学报, 2012, 38(1):135-139. [DOI:10.3724/SP.J.1004.2012.00135]

Zhang L, Li Y Y, Yang Y, et al. Generalized progressive iterative approximation for Said-Ball bases on triangular domains[J]. Journal of Image and Graphics, 2014, 19(2):275-282.

张莉, 李园园, 杨燕, 等.三角域上Said-Ball基的推广渐近迭代逼近[J].中国图象图形学报, 2014, 19(2):275-282. [DOI:10.11834/jig.20140213]

Delgado J, Peña J M. Progressive iterative approximation and bases with the fastest convergence rates[J]. Computer Aided Geometric Design, 2007, 24(1):10-18.[DOI:10.1016/j.cagd.2006.10.001]

Lu L Z. Weighted progressive iteration approximation and convergence analysis[J]. Computer Aided Geometric Design, 2010, 27(2):129-137.[DOI:10.1016/j.cagd.2009.11.001]

Liu X Y, Deng C Y. Jacobi-PIA algorithm for non-uniform cubic B-spline curve interpolation[J]. Journal of Computer-Aided Design&Computer Graphics, 2015, 27(3):485-491.

刘晓艳, 邓重阳.非均匀三次B样条曲线插值的Jacobi-PIA算法[J].计算机辅助设计与图形学学报, 2015, 27(3):485-491.

Lin H W. Local progressive-iterative approximation format for blending curves and patches[J]. Computer Aided Geometric Design, 2010, 27(4):322-339.[DOI:10.1016/j.cagd.2010.01.003]

Lin H W, Zhang Z Y. An extended iterative format for the progressive-iteration approximation[J]. Computers&Graphics, 2011, 35(5):967-975.[DOI:10.1016/j.cag.2011.07.003]

Deng C Y, Lin H Y. Progressive and iterative approximation for least squares B-spline curve and surface fitting[J]. Computer-Aided Design, 2014, 47:32-44.[DOI:10.1016/j.cad.2013.08.012]

Zhang L, Ge X Y, Tan J Q. Least square geometric iterative fitting method for generalized B-spline curves with two different kinds of weights[J]. The Visual Computer, 2016, 32(9):1109-1120.[DOI:10.1007/s00371-015-1170-3]

Zhang L, Tan J Q, Ge X Y, et al. Generalized B-splines' geometric iterative fitting method with mutually different weights[J]. Journal of Computational and Applied Mathematics, 2018, 329:331-343.[DOI:10.1016/j.cam.2017.05.034]

Lin H W. Survey on geometric iterative methods with applications[J]. Journal of Computer-Aided Design&Computer Graphics, 2015, 27(4):582-589.

蔺宏伟.几何迭代法及其应用综述[J].计算机辅助设计与图形学学报, 2015, 27(4):582-589.

Che X J, Liang X Z. G 1 continuity conditions of b-spline surfaces[J]. Northeastern Mathematical Journal, 2002, 18(4):343-352.

Gao Z H. The smooth connection algorithm between b-spline patches[D]. Changchun: Jilin University, 2004. http://cdmd.cnki.com.cn/Article/CDMD-10183-2004099735.htm .

高占恒. B样条曲面间的光滑拼接算法[D]. 长春: 吉林大学, 2004.