劉明增，郭慶杰，王思奇

?

基于正則漸進(jìn)迭代逼近的自適應(yīng)B樣條曲線擬合

劉明增，郭慶杰，王思奇

(大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部，遼寧 盤錦 124221)

基于漸進(jìn)迭代逼近(PIA)的數(shù)據(jù)擬合方法以其簡(jiǎn)單和靈活的特性獲得了廣泛的關(guān)注。為了獲得高保真度的擬合曲線，提出了一種基于主導(dǎo)點(diǎn)選取和正則漸進(jìn)迭代逼近(RPIA)的自適應(yīng)B樣條曲線擬合算法。首先根據(jù)數(shù)據(jù)點(diǎn)的曲率估計(jì)選取初始主導(dǎo)點(diǎn)并生成初始PIA曲線。然后，借助于擬合誤差和數(shù)據(jù)點(diǎn)集的曲率分布選取加細(xì)的主導(dǎo)點(diǎn)及實(shí)現(xiàn)PIA曲線的更新。得益于基于曲率分布的主導(dǎo)點(diǎn)選取，使得擬合曲線在復(fù)雜區(qū)域分布較多的控制頂點(diǎn)，而在平坦區(qū)域則較少。通過正則參數(shù)的引入構(gòu)造了一種RPIA格式，提升了漸進(jìn)迭代控制的靈活性。最后，數(shù)值算例表明相比于傳統(tǒng)最小二乘曲線擬合該算法在使用較少數(shù)量的控制頂點(diǎn)時(shí)可實(shí)現(xiàn)較高的擬合精度。

B樣條曲線擬合；正則漸進(jìn)迭代逼近；自適應(yīng)加細(xì)；曲率估計(jì)

給定數(shù)據(jù)點(diǎn)的B樣條曲線擬合在計(jì)算機(jī)圖形學(xué)、CAD/CAM和計(jì)算機(jī)視覺等許多領(lǐng)域是經(jīng)常遇到的一個(gè)問題[1-4]。標(biāo)準(zhǔn)的B樣條曲線擬合通常要進(jìn)行數(shù)據(jù)點(diǎn)的參數(shù)化，然后建立以B樣條曲線控制頂點(diǎn)為未知量的一個(gè)優(yōu)化問題，繼而轉(zhuǎn)化為求解相應(yīng)的線性方程組[1,4]。

最近，一種不需要求解線性方程組且具有明顯幾何意義的漸進(jìn)迭代逼近(progressive iterative approximation，PIA)方法獲得了大量的關(guān)注[5]。其主要利用混合基函數(shù)的PIA性質(zhì)：構(gòu)造一條初始擬合曲線，通過逐次迭代調(diào)整其控制頂點(diǎn)使得該擬合曲線插值或逼近給定的數(shù)據(jù)點(diǎn)集。齊東旭等[6]提出了均勻3次B樣條具有上述的PIA性質(zhì)。LIN等[7-8]進(jìn)一步推廣上述結(jié)果到非均勻3次B樣條曲線，并首次提出了英文術(shù)語progressive iterative approximation。文獻(xiàn)[9]指出有理非均勻B樣條(non-uniform rational B-Splines，NURBS)曲線曲面也具有上述的PIA性質(zhì)。此外，LIN和ZHANG[10]提出一種用于擬合大規(guī)模數(shù)據(jù)點(diǎn)的EPIA(extended PIA)算法，該算法允許控制頂點(diǎn)數(shù)目少于數(shù)據(jù)點(diǎn)數(shù)。LIN[11]提出一種在每次迭代中可部分調(diào)整控制頂點(diǎn)的局部PIA算法。文獻(xiàn)[12-13]通過在迭代步中引入權(quán)重因子進(jìn)而提升了PIA算法的效率。針對(duì)在PIA方法中每次迭代中數(shù)據(jù)點(diǎn)的參數(shù)值固定不變問題，MAEKAWA等[14]提出將數(shù)據(jù)點(diǎn)的參數(shù)值更新為每次迭代曲線上最近點(diǎn)的參數(shù)值并稱之為幾何插值法。近來，DENG和LIN[15]提出一種新的PIA算法，該算法的極限曲線或曲面等價(jià)于給定數(shù)據(jù)點(diǎn)的最小二乘擬合結(jié)果。

得益于B樣條曲線的局部支集性質(zhì)，可認(rèn)為每個(gè)控制頂點(diǎn)都支配著待表示物體的部分幾何信息。顯然，事先無法知道需要多少控制頂點(diǎn)在滿足指定精度的前提下來表達(dá)物體。在本文中，將考慮如何在保持?jǐn)M合精度的前提下，減少B樣條曲線的控制頂點(diǎn)數(shù)目以期減少冗余控制頂點(diǎn)的信息。YANG等[2]基于SDM(squared distance minimization)優(yōu)化提出了一種自動(dòng)調(diào)整控制定點(diǎn)數(shù)據(jù)的算法，但該算法對(duì)初始B樣條曲線過于敏感。在擬合問題中，一些點(diǎn)會(huì)對(duì)擬合曲線的精度產(chǎn)生決定性的影響?；谶@種觀察，PARK[4]提出了一種基于主導(dǎo)點(diǎn)(dominant point)選取的自適應(yīng)B樣條曲線擬合算法，但在該算法每次迭代中需要求解一個(gè)線性方程組，且隨著迭代的進(jìn)行方程組的規(guī)模也逐步增長。文獻(xiàn)[16]提出一種約束曲線在曲面上的基于主導(dǎo)點(diǎn)選取的自適應(yīng)保形曲線擬合算法。本文擬基于數(shù)據(jù)點(diǎn)的幾何信息(如曲率)獲取初始曲線的控制頂點(diǎn)。而后，采用漸進(jìn)迭代近似實(shí)現(xiàn)數(shù)據(jù)點(diǎn)集的擬合，繼而避免了求解線性方程組。鑒于此，提出一種基于正則漸進(jìn)迭代逼近(regularized progressive iterative approximation, RPIA)的自適應(yīng)B樣條曲線擬合算法，該算法采用基于主導(dǎo)點(diǎn)選取的曲線加細(xì)技術(shù)來保證擬合曲線的精度。

1 基于正則漸進(jìn)迭代的自適應(yīng)擬合算法

PIA方法是一種具有明顯幾何意義的幾何迭代方法，通過迭代調(diào)整曲線的控制頂點(diǎn)得到最后擬合給定點(diǎn)集的逼近曲線[7-13,15]。盡管PIA方法的初始控制頂點(diǎn)可以任意指定，合理選取初始曲線的控制頂點(diǎn)對(duì)極限曲線的生成質(zhì)量有極其重要的影響[15]。

綜上，為避免求解線性方程組，本文采用PIA方法擬合給定的數(shù)據(jù)點(diǎn)集。同時(shí)，考慮結(jié)合數(shù)據(jù)點(diǎn)集曲率信息來進(jìn)行初始控制頂點(diǎn)的選取，且在迭代格式中引入一個(gè)正則自由度來增加PIA的靈活性。本文算法流程概括如下：首先通過估計(jì)數(shù)據(jù)點(diǎn)的曲率信息獲取初始的主導(dǎo)點(diǎn)集，繼而生成首次RPIA曲線；然后，結(jié)合迭代曲線的擬合誤差和數(shù)據(jù)點(diǎn)曲率信息增選相應(yīng)的主導(dǎo)點(diǎn)；最后，更新RPIA曲線直到滿足指定的擬合精度。本文算法由4部分組成：數(shù)據(jù)點(diǎn)的參數(shù)化、主導(dǎo)點(diǎn)的初始選取和更新、節(jié)點(diǎn)向量的配置及更新和RPIA曲線的生成。圖1展示了人臉輪廓數(shù)據(jù)的自適應(yīng)B樣條擬合示例。

1.1 數(shù)據(jù)點(diǎn)的參數(shù)化

1.2 主導(dǎo)點(diǎn)的初始選取及節(jié)點(diǎn)向量的配置

圖1 人臉輪廓數(shù)據(jù)的B樣條曲線擬合示例

1.3 主導(dǎo)點(diǎn)及節(jié)點(diǎn)向量的更新

于是，更新后主導(dǎo)點(diǎn)集形成的內(nèi)部節(jié)點(diǎn)向 量為

從式(4)易知，只需對(duì)式(2)中的節(jié)點(diǎn)向量進(jìn)行部分更新即可。

1.4 正則漸進(jìn)迭代逼近曲線的生成

記相應(yīng)基函數(shù)的配置矩陣為

則第+1次迭代曲線為

整理式(8)可得

根據(jù)式(11)可得

1.5 算法流程

本文算法流程如下：

（4）德城區(qū)建成區(qū)的擴(kuò)展主要受人口、經(jīng)濟(jì)、交通和政策4個(gè)因素綜合影響．其中，政策因素成為主導(dǎo)城市發(fā)展的最重要驅(qū)動(dòng)力．

步驟4.1. RPIA擬合曲線c()。

步驟4.2.選取加細(xì)區(qū)S,e和新的主導(dǎo)點(diǎn)new=new。

步驟4.4.如果滿足指定擬合誤差結(jié)束循環(huán)。

2 數(shù)值算例

表1 數(shù)據(jù)點(diǎn)集統(tǒng)計(jì)信息

圖2 A1數(shù)據(jù)的曲線擬合結(jié)果

表2 圖2最大誤差信息

圖3對(duì)比分析了A1人臉輪廓數(shù)據(jù)在本文RPIA方法、LS-Fitting算法和P-fitting算法的擬合效率信息。由圖3(a)可知，在指定相同的擬合誤差標(biāo)準(zhǔn)時(shí)，RPIA方法需要較少的控制頂點(diǎn)數(shù)目，即一定程度上是減少了冗余控制頂點(diǎn)信息。由圖3(b)可知，在控制頂點(diǎn)數(shù)目相同時(shí)，RPIA擬合可以達(dá)到較小的擬合誤差。

圖3 A1人臉輪廓數(shù)據(jù)的擬合效率分析

圖4 A2音符數(shù)據(jù)RPIA擬合曲線及擬合效率分析

圖6為帶噪聲平面曲線擬合結(jié)果(A4數(shù)據(jù)集)和3D空間曲線(A5數(shù)據(jù)集)擬合結(jié)果。表4列出了圖5中數(shù)據(jù)點(diǎn)集的誤差信息。

表3 不同控制頂點(diǎn)數(shù)目(21,31,41,51,61,71)時(shí)的最大誤差

表4 圖6最大誤差信息

3 結(jié)束語

本文提出了一種基于RPIA的曲線擬合方法，結(jié)合主導(dǎo)點(diǎn)的選取實(shí)現(xiàn)了擬合的自適應(yīng)。通過數(shù)值算例驗(yàn)證可知，與傳統(tǒng)的最小二乘擬合方法相比，在指定擬合誤差時(shí)，本文方法只需較少的控制頂點(diǎn)，而在指定相同控制頂點(diǎn)數(shù)目時(shí)，具有更小擬合誤差。由于PIA格式的引入避免了傳統(tǒng)擬合方法中求解線性方程組的問題，提高了求解效率。但本文中也有一些不足之處，本文算法中涉及到B樣條曲線的節(jié)點(diǎn)刪除操作，會(huì)導(dǎo)致刪除后B樣條曲線的誤差增大，繼而增大迭代步數(shù)。

[1] PIEGL L, TILLER W. The NURBS book [M]. 2th ed. New York: Springer, 1997: 410-419.

[2] YANG H P, WANG W P, SUN J G. Control point adjustment for B-spline approximation [J]. Comuter-Aided Design, 2004, 36(7): 639-652.

[3] WANG W P, POTTMANN H, LIU Y. Fitting B-spline curves to point clouds by curvature-based squared distance minimization [J]. ACM Transactions Graphics, 2006, 25(2): 214-238.

[4] PARK H. An error-bound approximation method for representing planar curves in B-splines [J]. Computer-Aided Design, 2004, 21(5): 479-497.

[5] 藺宏偉. 幾何迭代法及其應(yīng)用綜述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015, 27(4): 582-589.

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

[7] 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 F, 2004, 47(3): 315-331.

[8] LIN H W, BAO H J, WANG G J. Totally positive bases and progressive iteration [J]. Computers and Mathematics with Applications, 2005, 50(3/4): 575-586.

[9] 史利民, 王仁宏. NURBS曲線曲面擬合數(shù)據(jù)點(diǎn)的迭代算法[J]. 數(shù)學(xué)研究及應(yīng)用, 2016, 26(4): 735-743.

[10] LIN H W, ZHANG Z Y. An extended iterative format for the progressive-iterative approximation [J]. Computer & Graphics, 2011, 35(5): 967-975.

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

[12] LU L Z. Weighted progressive iteration approximation and convergence analysis [J]. Computer Aided Geometric Design, 2010, 27(2): 129-137.

[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]. Visual Computer, 2016, 32(9): 1109-1120.

[14] MAEKAWA T, MATSUMOTO Y, NAMIJI K. Interpolation by geometric algorithm [J]. Computer-Aided Design, 2007, 39(4): 313-323.

[15] 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: 32-44.

[16] HU P, LIU M Z, LI B J, et al. Adaptive shape-preserving curve fitting on surfaces [J]. Journal of Information & Computational Science, 2012, 9(1): 15-23.

[17] PARK H, LEE J. B-spline curve fitting based on adaptive curve refinement using dominant points [J]. Computer-Aided Design, 2007, 39(6): 439-451.

Adaptive B-spline Curve Fitting Based on Regularized Progressive Iterative Approximation

LIU Mingzeng, GUO Qingjie, WANG Siqi

(School of Mathematics and Physics Science, Dalian University of Technology, Panjin Liaoning 124221, China)

The use of progressive iterative approximation (PIA) to fit data points has received a deal of attention benefitting from its simplicity and flexibility.To obtain a fitting curve satisfying the shape high fidelity, we present an adaptive B-spline curve fitting algorithm based on regularized progressive iterative approximation (RPIA) and the selection of dominant points. Firstly, the initial dominant points are selected from the given points in terms of curvature estimates and an initial progressive iterative approximation curve is constructed. Then the fitting curve based on RPIA is updated by means of the fitting error and the selection of refinement dominant points according to the curvature distribution of given points. The fitting curve possesses fewer control points at flat regions but more at complex regions. By the use of a regular parameter, progressive iterative approximation is generalized and the flexibility of PIA is promoted. Finally, numerical examples are provided to demonstrate that compared with the conventional least square approaches the proposed method can achieve a higher fitting precision with far fewer control points.

B-spline curve fitting; regularized progressive iterative approximation; adaptive refinement; curvature estimation

TP 391

10.11996/JG.j.2095-302X.2018020287

A

2095-302X(2018)02-0287-08

2017-07-13；

2017-08-28

國家自然科學(xué)基金項(xiàng)目(11601064)；中央高?；究蒲袠I(yè)務(wù)專項(xiàng)資金項(xiàng)目(DUT14RC(3)024，DUT16RC(4)67，DUT17LK09)

劉明增(1984–)，男，河南淮陽人，講師，博士。主要研究方向?yàn)橛?jì)算幾何、計(jì)算機(jī)圖形學(xué)。E-mail：mzliu@dlut.edu.cn