发布时间: 2018-07-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.170559 2018 | Volume 23 | Number 7 计算机图形学

1. 合肥工业大学数学学院, 合肥 230009;
2. 合肥工业大学计算机与信息学院, 合肥 230009
 收稿日期: 2017-11-03; 修回日期: 2018-01-28 基金项目: 国家自然科学基金项目（61472466，61100126）；国家大学生创新计划基金项目（201610359061） 第一作者简介: 郑国, 1995年生, 男, 合肥工业大学数学学院本科生, 研究方向为计算机辅助几何设计。E-mail:2402444249@qq.com;张世杰, 男, 合肥工业大学数学学院本科生, 主要研究方向为计算机辅助几何设计。E-mail:1144279616@qq.com;杜壮平, 女, 合肥工业大学数学学院讲师, 研究方向为计算数学。E-mail:njbdzp0824@qq.com;刘逸, 男, 合肥工业大学计算机与信息学院本科生, 研究方向为计算机辅助几何设计。E-mail:237249938@qq.com;檀结庆, 男, 合肥工业大学数学学院教授, 研究方向为数值逼近、计算机辅助几何设计。E-mail:jieqingtan@hfut.edu.cn. 中图法分类号: TP391.41 文献标识码: A 文章编号: 1006-8961(2018)07-1081-10

# 关键词

Grouped progressive iterative approximation method of data fitting
Zheng Guo1, Zhang Li1, Zhang Shijie1, Du Zhuangping1, Liu Yi2, Tan Jieqing1,2
1. School of Mathematics, Hefei University of Technology, Hefei 230009, China;
2. School of Computer and Information, Hefei University of Technology, Hefei 230009, China
Supported by: National Natural Science Foundation of China (61472466, 61100126)

# 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.

# Key words

geometric iterative methods; grouped progressive iteration; blending algorithm; G2 continuity; iteration efficiency

# 1 预备知识

 $\mathit{\boldsymbol{M}}\left[ \begin{array}{l} {{\bar B}_0} \cdots {{\bar B}_n}\\ {t_0}\;\; \cdots \;\;{t_m} \end{array} \right] = \left[ \begin{array}{l} {{\bar B}_0}\left( {{t_0}} \right)\;\;\;{{\bar B}_1}\left( {{t_0}} \right)\;\;\; \cdots \;\;\;{{\bar B}_n}\left( {{t_0}} \right)\\ {{\bar B}_0}\left( {{t_1}} \right)\;\;\;{{\bar B}_1}\left( {{t_1}} \right)\;\;\;\; \cdots \;\;\;{{\bar B}_n}\left( {{t_1}} \right)\\ \;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \;\;\;\;\\ {{\bar B}_0}\left( {{t_m}} \right)\;\;\;{{\bar B}_1}\left( {{t_m}} \right)\;\;\; \cdots \;\;\;{{\bar B}_n}\left( {{t_m}} \right) \end{array} \right]$

# 2.1.2 基于曲线的PIA方法

$(B_{0}(t), B_{1}(t), …, B_{n}(t))$是一组标准全正基, 不妨记分组后的一组有序数据点集为$\{\mathit{\boldsymbol{P}}_{i}\}^{n_{1}}_{i=0}$, 以该点集作为初始的控制顶点, 得到初始曲线${\mathit{\boldsymbol{C}}^0}\left(t \right) = \sum\limits_{i = 0}^{{n_1}} {\mathit{\boldsymbol{P}}_i^0{\mathit{\boldsymbol{B}}_i}\left(t \right)}$, 其中, $\mathit{\boldsymbol{P}}^{0}_{i}=\mathit{\boldsymbol{P}}_{i}$, $i=0, 1, …, n_{1}$, 然后, 对每个控制顶点计算调整向量${\mathit \Delta} ^{0}_{i}=\mathit{\boldsymbol{P}}_{i}-\mathit{\boldsymbol{C}}^{0}(t_{i})$, 并且令$\mathit{\boldsymbol{P}}^{1}_{i}=\mathit{\boldsymbol{P}}_{i}+{\mathit \Delta} ^{0}_{i}$, $i=0, 1, …, n_{1}$, 可以得到$\mathit{\boldsymbol{C}}^{1}(t)=\sum\limits_{i = 0}^{{n_1}} \mathit{\boldsymbol{P}}^{1}_{i}B_{i}(t)$。重复这一过程, 可以得到不断靠近给定点集的曲线序列$\{\mathit{\boldsymbol{C}}^{k}(t)\}$, 且$\{\mathit{\boldsymbol{C}}^{k}(t)\}$的极限曲线会插值于给定的有序点集。

# 2.2.3 曲面的连续性

 ${T_2} = \frac{{{m^2}{n^2} + 4m{n^2} + 4{n^2}}}{2}$

# 2.4 算法流程

1) 用$count$保存组数, 初始值设为1。

2) 判断数据点的个数是否满足实际需要, 若满足则跳到步骤5), 否则进行下一步。

3) 对数据点进行分组, $count$++。

4) 分别判断每一组的数据点个数是否满足实际需要, 若满足则进行下一步, 否则返回步骤3)。

5) 采用PIA方法或是基于最小二乘法的渐进迭代逼近方法。

6) 判断组数$count>1$是否成立, 若成立则进行下一步, 否则跳到步骤8)。

7) 对分组之后得到的曲线/曲面, 采用曲线/曲面拼接算法。

8) 得到插值或拟合给定点集的曲线/曲面。

# 3 数值实例

 $e\left( k \right) = \mathop {\max }\limits_{\begin{array}{*{20}{c}} {i = 0,1, \cdots ,m}\\ {j = 0,1, \cdots ,n} \end{array}} {\kern 1pt} \left\| {P_{i,j}^0 - P_{i,j}^k} \right\|$ (7)

Table 1 The comparison of errors between LSPIA method and our method

 LSPIA方法 分组LSPIA方法 $E_{0}$ $4.818~8$ $3.627~3$ $E_{1}$ $6.495~5×10^{-1}$ $1.964~4×10^{-1}$ $E_5$ $1.854~3×10^{-1}$ $2.228~9×10^{-2}$ $E_∞$ $2.427~0×10^{-2}$ $1.375~0×10^{-2}$

$k$为迭代次数。

Table 2 The comparison of errors of different kinds of grouped PIA methods

 PIA方法 二分法 三分法 二次二分法 六分法 四次二分法 $E_0$ $6.865~6×10^{-1}$ $4.138~9×10^{-1}$ $1.100~7×10^{-1}$ $1.841~6×10^{-1}$ $1.350~0×10^{-1}$ $1.245~7×10^{-1}$ $E_1$ $3.348~7×10^{-1}$ $1.430~1×10^{-1}$ $7.552~4×10^{-2}$ $7.423~3×10^{-2}$ $5.899~1×10^{-2}$ $3.084~9×10^{-2}$ $E_5$ $8.294~6×10^{-2}$ $3.206~1×10^{-2}$ $2.314~2×10^{-2}$ $2.752~8×10^{-2}$ $1.648~8×10^{-2}$ $2.288~6×10^{-3}$ $E_{10}$ $4.093~7×10^{-2}$ $1.762~8×10^{-2}$ $8.785~0×10^{-3}$ $7.513~2×10^{-3}$ $4.708~4×10^{-3}$ $8.090~9×10^{-4}$

Table 3 The comparison of errors of different kinds of grouped PIA methods

 PIA方法 二分法 三分法 二次二分法 六分法 四次二分法 $E_0$ $3.852~9$ $2.596~3$ $1.204~8$ $2.199~9$ $1.241~6$ $1.570~2$ $E_1$ $2.383~9$ $1.343~6$ $7.178~9×10^{-1}$ $6.290~8×10^{-1}$ $3.454~9×10^{-1}$ $5.493~1×10^{-1}$ $E_5$ $8.612~8×10^{-1}$ $4.292~2×10^{-1}$ $2.255~7×10^{-1}$ $2.415~7×10^{-1}$ $7.899~6×10^{-2}$ $1.185~4×10^{-1}$ $E_{10}$ $5.479~5×10^{-1}$ $2.632~7×10^{-1}$ $1.223~8×10^{-1}$ $1.287~9×10^{-1}$ $4.122~4×10^{-2}$ $3.769~2×10^{-2}$

# 参考文献

• [1] 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. ]
• [2] 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
• [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. [DOI:10.1360/02yf0529]
• [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-4): 575–586. [DOI:10.1016/j.camwa.2005.01.023]
• [5] 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]
• [6] 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]
• [7] 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]
• [8] 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]
• [9] 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. ]
• [10] 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]
• [11] 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]
• [12] 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]
• [13] 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]
• [14] 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]
• [15] 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. ]
• [16] Che X J, Liang X Z. G1 continuity conditions of b-spline surfaces[J]. Northeastern Mathematical Journal, 2002, 18(4): 343–352.
• [17] Gao Z H. The smooth connection algorithm between b-spline patches[D]. Changchun: Jilin University, 2004. [高占恒. B样条曲面间的光滑拼接算法[D]. 长春: 吉林大学, 2004.] http://cdmd.cnki.com.cn/Article/CDMD-10183-2004099735.htm