基于正則漸進迭代逼近的自適應B樣條曲線擬合

劉明增，郭慶杰，王思奇

?

基于正則漸進迭代逼近的自適應B樣條曲線擬合

劉明增，郭慶杰，王思奇

(大連理工大學盤錦校區基礎教學部，遼寧 盤錦 124221)

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

B樣條曲線擬合；正則漸進迭代逼近；自適應加細；曲率估計

給定數據點的B樣條曲線擬合在計算機圖形學、CAD/CAM和計算機視覺等許多領域是經常遇到的一個問題[1-4]。標準的B樣條曲線擬合通常要進行數據點的參數化，然后建立以B樣條曲線控制頂點為未知量的一個優化問題，繼而轉化為求解相應的線性方程組[1,4]。

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

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

1 基于正則漸進迭代的自適應擬合算法

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

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

1.1 數據點的參數化

1.2 主導點的初始選取及節點向量的配置

圖1 人臉輪廓數據的B樣條曲線擬合示例

1.3 主導點及節點向量的更新

于是，更新后主導點集形成的內部節點向 量為

從式(4)易知，只需對式(2)中的節點向量進行部分更新即可。

1.4 正則漸進迭代逼近曲線的生成

記相應基函數的配置矩陣為

則第+1次迭代曲線為

整理式(8)可得

根據式(11)可得

1.5 算法流程

本文算法流程如下：

（4）德城區建成區的擴展主要受人口、經濟、交通和政策4個因素綜合影響．其中，政策因素成為主導城市發展的最重要驅動力．

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

步驟4.2.選取加細區S,e和新的主導點new=new。

步驟4.4.如果滿足指定擬合誤差結束循環。

2 數值算例

表1 數據點集統計信息

圖2 A1數據的曲線擬合結果

表2 圖2最大誤差信息

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

圖3 A1人臉輪廓數據的擬合效率分析

圖4 A2音符數據RPIA擬合曲線及擬合效率分析

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

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

表4 圖6最大誤差信息

3 結束語

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

[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] 藺宏偉. 幾何迭代法及其應用綜述[J]. 計算機輔助設計與圖形學學報, 2015, 27(4): 582-589.

[6] 齊東旭, 田自賢, 張玉心, 等. 曲線擬合的數值磨光方法[J]. 數學學報, 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曲線曲面擬合數據點的迭代算法[J]. 數學研究及應用, 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

國家自然科學基金項目(11601064)；中央高?；究蒲袠I務專項資金項目(DUT14RC(3)024，DUT16RC(4)67，DUT17LK09)

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