基于多結(jié)點(diǎn)樣條磨光函數(shù)的幾何迭代法

霍彥妏，蔡占川

?

基于多結(jié)點(diǎn)樣條磨光函數(shù)的幾何迭代法

霍彥妏，蔡占川

(澳門科技大學(xué)資訊科技學(xué)院，澳門 999078)

幾何迭代法在計(jì)算機(jī)輔助幾何設(shè)計(jì)(CAGD)中有廣泛地應(yīng)用，為了提高傳統(tǒng)的B-樣條曲線插值在幾何迭代中的收斂速度和迭代精度，提出了基于多結(jié)點(diǎn)樣條磨光函數(shù)的幾何迭代法，引入多結(jié)點(diǎn)樣條磨光函數(shù)，在曲線擬合時(shí)把多結(jié)點(diǎn)樣條磨光方法和幾何迭代方法結(jié)合，經(jīng)過磨光和迭代，在L-BFGS迭代算法的最優(yōu)解下構(gòu)造具有高逼近性的曲線擬合方法。實(shí)驗(yàn)結(jié)果表明，在相同精度下，該方法不僅減少了迭代次數(shù)，且提高了迭代速度，可以用于飛機(jī)、汽車等外形設(shè)計(jì)上，亦可用于文物、房屋等外形重構(gòu)和重建，以及衛(wèi)星圖形圖像的處理中。

幾何迭代法；多結(jié)點(diǎn)樣條磨光；L-BFGS算法；B-樣條

1 研究背景

幾何迭代法[1-2](geometric iteration method，GIM)，早期被稱為漸進(jìn)迭代逼近(progressive- iterative approximation，PIA)，其是迭代逼近算法在幾何設(shè)計(jì)中的應(yīng)用。該方法是將原始的離散數(shù)據(jù)點(diǎn)集用迭代的方法調(diào)整控制點(diǎn)，形成逐漸逼近控制點(diǎn)的新樣條函數(shù)，最終形成一條光滑且具有更高逼近性的曲線或曲面的一種圖形數(shù)據(jù)擬合方法[3]。

幾何迭代法在計(jì)算機(jī)輔助幾何設(shè)計(jì)(computer- aided geometric design，CAGD)中，解決的主要問題是工業(yè)產(chǎn)品幾何形狀的數(shù)字描述，例如汽車車輪、渦輪發(fā)動(dòng)機(jī)、飛機(jī)外形的設(shè)計(jì)。CAGD技術(shù)起源于航空工業(yè)，由于飛機(jī)外形流線型的特殊結(jié)構(gòu)是由多個(gè)自由的曲線及曲面組成的，所以CAGD技術(shù)的研究與曲線、曲面的發(fā)展息息相關(guān)。

1975年，齊東旭等[4]提出均勻三次B-樣條的盈虧修正曲線擬合數(shù)值磨光方法，之后又在文獻(xiàn)[5-6]中提出多結(jié)點(diǎn)樣條的磨光方法，即用高階的多結(jié)點(diǎn)樣條磨光來達(dá)到更高的逼近效果，使“盈虧修正”方法得到更好地拓展和延伸。DE BOOR[7]于1979年也研究盈虧修正并且證明了該方法的收斂速度。2004年，LIN等[8]在非均勻三次B-樣條的研究上證明了其同樣具有盈虧修正的性質(zhì)，隨后在2006年提出了漸進(jìn)迭代逼近(progressive iterative approximation，PIA)[9-13]的概念，并證明了幾何迭代的性質(zhì)同樣適用于歸一化的全正基混合曲線和曲面中。

2007年DELGADO和PE?A[14]對(duì)比了在迭代過程中當(dāng)取不同基函數(shù)的樣條函數(shù)時(shí)，各自的收斂速度不同，且證明了B-樣條的基函數(shù)迭代具有最高的收斂速度。同年，MAEKAWA等[15]用相鄰數(shù)據(jù)點(diǎn)的參數(shù)值代替原始點(diǎn)的參數(shù)值并提出了幾何插值(geometric interpolation，GI[16])的概念。熟知，由于PIA和GI[17]方法的相似性，在CAGD研究領(lǐng)域，被統(tǒng)稱為幾何迭代法。

為了提高函數(shù)的迭代精度以及收斂性，本文提出基于多結(jié)點(diǎn)樣條磨光函數(shù)方法的幾何迭代法，采用L-BFGS算法求型值點(diǎn)和調(diào)整后控制點(diǎn)之間距離的最小值即最優(yōu)解，選取最恰當(dāng)?shù)狞c(diǎn)，以得到更加光滑且更加逼近型值點(diǎn)的幾何圖形。實(shí)驗(yàn)結(jié)果表明，該方法在相同的精度下，比通用的三次B-樣條曲線插值迭代次數(shù)減少，且收斂速度成倍加快，不僅有效地保證了幾何外形的精確性，還保持了其光滑的特性。

2 相關(guān)工作(GIM基本思想)

按此規(guī)律，生成的樣條曲線的表達(dá)式如下：經(jīng)過+1次迭代后，向量的差值為

圖1 迭代示意圖

3 多結(jié)點(diǎn)樣條磨光函數(shù)

自由曲線或曲面的數(shù)據(jù)擬合是幾何圖形設(shè)計(jì)中不可或缺的部分。為了提高三次B-樣條曲線或曲面的收斂性以及精確性，本文探討多結(jié)點(diǎn)樣條磨光方法并研究其迭代的幾何意義。

當(dāng)前，在CAD/CAM系統(tǒng)中，B-樣條曲線曲面已經(jīng)發(fā)展為被廣泛使用、很成熟的一類樣條方法。在齊東旭等[4]提出均勻的三次B-樣條曲線擬合數(shù)值磨光方法；之后，為了推廣B-樣條函數(shù)，在保證樣條曲線的精確性和光滑性同時(shí)兼顧的情況下，又引入級(jí)磨光算子，推出了“多結(jié)點(diǎn)” B-樣條函數(shù)的磨光法[5-6]。事實(shí)上，B-樣條函數(shù)是將次數(shù)為0的磨光算子在寬度=1的情況下，不斷地磨光計(jì)算得出的函數(shù)[5]。

在研究曲線或曲面的擬合逼近問題時(shí)，齊東旭[18]研究了單位算子，并推出含有微分算子的樣條函數(shù)磨光公式，使微分算子的逼近運(yùn)算精度更高[19]。文獻(xiàn)[20]研究了層次多結(jié)點(diǎn)樣條算法曲線曲面的擬合和應(yīng)用。

多結(jié)點(diǎn)樣條磨光函數(shù)的定義為

圖2 邊界延拓示意圖

樣條函數(shù)的次數(shù)可以有0次，1次，2次， 3次······，由次數(shù)分別為0，1，2，3的表達(dá)式形成的基函數(shù)的圖像，如圖3所示。

多結(jié)點(diǎn)樣條磨光法的優(yōu)點(diǎn)：

(1) 一般性。該磨光方法只儲(chǔ)存型值點(diǎn)，即不論幾何圖形是貓、狗亦或是松鼠這類型值點(diǎn)個(gè)數(shù)不同的幾何圖形，但其應(yīng)用曲線的表達(dá)式都是統(tǒng)一的，在處理結(jié)果的誤差上相比常用到的最小二乘法更小。

(2) 整體性。不論型值點(diǎn)如何增加，迭代的次數(shù)如何改變，幾何圖形的形狀均能保持和基本初始的數(shù)據(jù)形狀一致。

(3) 局部性。改變個(gè)別的數(shù)據(jù)點(diǎn)后，只會(huì)隨之影響這些點(diǎn)對(duì)應(yīng)的個(gè)別部分，而整體的幾何圖形形狀不會(huì)改變。

圖3 K=0,1,2,3時(shí)多結(jié)點(diǎn)樣條基函數(shù)圖像

4 基于多結(jié)點(diǎn)樣條磨光函數(shù)的幾何迭代法

熟知，牛頓法在進(jìn)行Hessian的逆運(yùn)算時(shí)，不僅費(fèi)時(shí)而且占用大量?jī)?nèi)存空間，給計(jì)算帶來很大的不便。相比牛頓法，BFGS算法由于Hessian的正定性即參數(shù)化的數(shù)據(jù)點(diǎn)唯一有且只對(duì)應(yīng)一個(gè)數(shù)據(jù)點(diǎn)，并不需要求解Hessian，也就不需要占用很大的內(nèi)存空間來存儲(chǔ)每次生成的矩陣結(jié)果，既節(jié)省存儲(chǔ)空間又提高了運(yùn)行速度。而L-BFGS算法更是被稱為“節(jié)省內(nèi)存的BFGS算法”。

1989年LIU和NOCEDAL[21]提出了L-BFGS (Limited-memory BFGS)算法，該算法常應(yīng)用于規(guī)模較大的數(shù)據(jù)處理的數(shù)值計(jì)算中。

其中，

上式是=3的情況，由于實(shí)驗(yàn)研究的是三次多結(jié)點(diǎn)樣條磨光的基函數(shù)，所以其他3種情況的表達(dá)式不做說明。

在使用均勻三次B-樣條函數(shù)進(jìn)行數(shù)據(jù)擬合時(shí)，需求解一組線性方程的根來確定該幾何形狀控制頂點(diǎn)的位置。反向求解方式為確定樣條函數(shù)的系數(shù)帶來了很大的不便，既增大運(yùn)算量，又延長(zhǎng)了運(yùn)算時(shí)間。本文采用多結(jié)點(diǎn)樣條磨光方法來克服B-樣條函數(shù)的不足。由圖4可知，使用三次多結(jié)點(diǎn)樣條磨光函數(shù)和三次B-樣條函數(shù)做對(duì)比，多結(jié)點(diǎn)樣條磨光函數(shù)的逼近效果要好于B-樣條函數(shù)，提高了幾何輪廓的精確性，而且更加逼近原始型值點(diǎn)。

圖4 多結(jié)點(diǎn)樣條磨光函數(shù)與B-樣條對(duì)比

基于多結(jié)點(diǎn)樣條磨光函數(shù)幾何迭代方法算法如下：

輸出：找到最小化函數(shù)值對(duì)應(yīng)的坐標(biāo)、步長(zhǎng)、梯度、精度。

步驟1. 初始化階段，選擇起始結(jié)點(diǎn)，原始型值點(diǎn)參數(shù)化。

步驟2. 形成初始磨光樣條函數(shù)曲線。

步驟3. 迭代次數(shù)=1；

步驟3.1. 閾值判定；

步驟3.2. 迭代正向或逆向求解。

步驟4. 閾值判定；

步驟4.1.若符合條件，畫出曲線；

步驟4.2. 若不符合，=+1，循環(huán)步驟3，4。

本文算法流程圖如圖5所示。

5 實(shí) 驗(yàn)

本文的實(shí)驗(yàn)操作是基于16 G內(nèi)存，i7-6700 CPUintel (R)處理器，在MATLAB編譯器上完成本文的實(shí)驗(yàn)內(nèi)容。

圖5 本文實(shí)現(xiàn)過程流程圖

5.1 實(shí)驗(yàn)結(jié)果

研究幾何迭代法離不開研究擬合曲線迭代的速度和精度，即算法收斂性。文獻(xiàn)[28]中在三次B-樣條函數(shù)的基礎(chǔ)上對(duì)各種幾何圖形做出了相應(yīng)的迭代擬合。圖6~20是本文算法與文獻(xiàn)[28]的實(shí)驗(yàn)結(jié)果的對(duì)比圖。當(dāng)原始型值點(diǎn)個(gè)數(shù)不同且接近100個(gè)數(shù)據(jù)點(diǎn)時(shí)，最大的迭代次數(shù)在5次以內(nèi)就可以達(dá)到所需的精度值。為了驗(yàn)證本文算法的收斂性，通過以下5種實(shí)例來驗(yàn)證算法的迭代效果以及精度分別與迭代次數(shù)和時(shí)間的關(guān)系。

在精度與迭代次數(shù)和時(shí)間的對(duì)比關(guān)系圖中，顯示相同的精度設(shè)置下的對(duì)比結(jié)果，藍(lán)色線條為三次B-樣條函數(shù)方法實(shí)現(xiàn)的迭代結(jié)果，紅色線條為多結(jié)點(diǎn)樣條磨光函數(shù)方法實(shí)現(xiàn)的迭代實(shí)驗(yàn)結(jié)果。由圖6~20可知，在相同精度下，多結(jié)點(diǎn)樣條磨光函數(shù)方法可比三次B-樣條用更少的迭代次數(shù)和運(yùn)行時(shí)間更加迅速地達(dá)到閾值條件。

5.2 實(shí)驗(yàn)分析

由表1和圖21不同幾何圖形的精度對(duì)比以及表2的5種迭代詳細(xì)情況對(duì)比可知，5種不同的幾何圖形用本文的算法迭代后在5次之內(nèi)均可達(dá)到閾值迭代精度。

圖6 牛迭代實(shí)驗(yàn)結(jié)果

圖7 牛誤差與迭代次數(shù)關(guān)系

圖8 牛誤差與時(shí)間關(guān)系

圖9 松鼠迭代實(shí)驗(yàn)結(jié)果

圖10 松鼠誤差與迭代次數(shù)關(guān)系

圖11 松鼠誤差與時(shí)間關(guān)系

圖12 大象迭代實(shí)驗(yàn)結(jié)果

圖13 象誤差與迭代次數(shù)關(guān)系

圖14 象誤差與時(shí)間關(guān)系

圖15 米老鼠迭代實(shí)驗(yàn)結(jié)果

圖16 米老鼠誤差與迭代次數(shù)關(guān)系

圖17 米老鼠誤差與時(shí)間關(guān)系

圖18 螃蟹迭代實(shí)驗(yàn)結(jié)果

圖19 螃蟹誤差與迭代次數(shù)關(guān)系

圖20 螃蟹誤差與時(shí)間關(guān)系

表1 不同幾何圖形誤差對(duì)比

圖21 5種幾何圖像誤差對(duì)比

表2 采用多結(jié)點(diǎn)樣條磨光方法與三次B-樣條函數(shù)方法的幾何圖形迭代詳細(xì)情況對(duì)比

6 結(jié) 論

本文基于多結(jié)點(diǎn)樣條磨光函數(shù)，提出了相應(yīng)的優(yōu)化幾何迭代方法。在獲取幾何圖形的原始型值點(diǎn)后，利用多結(jié)點(diǎn)樣條磨光函數(shù)的高逼近性和局部性，采用L-BFGS算法尋找最佳迭代逼近數(shù)據(jù)點(diǎn)的位置，通過數(shù)次磨光和迭代產(chǎn)生數(shù)據(jù)的最優(yōu)解，在迭代達(dá)到指定精度值后，得到所需具有“較高精確性”的光滑曲線。實(shí)驗(yàn)結(jié)果表明，本文提出的磨光方法，比三次B-樣條函數(shù)曲線在幾何迭代的曲線擬合上逼近性更高，收斂性更快，在精度和速度上都有所提升。

今后，將繼續(xù)探討基于多結(jié)點(diǎn)樣條磨光函數(shù)的幾何迭代方法在三維的立體幾何圖形以及曲面中的應(yīng)用。

[1] OKANIWA S, NASRI A, LIN H, et al. Uniform B-spline curve interpolation with prescribed tangent and curvature vectors [J]. IEEE transactions on visualization and computer graphics, 2012, 18(9): 1474-1487.

[2] LIN H, MAEKAWA T, DENG C. Survey on geometric iterative methods and their applications [J]. Computer-Aided Design, 2018, 95: 40-51.

[3] LIN H, ZHANG Z. An efficient method for fitting large data sets using T-splines [J]. SIAM Journal on Scientific Computing, 2013, 35(6): A3052-A3068.

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

[5] 齊東旭, 梁振珊. 多結(jié)點(diǎn)樣條磨光(Ⅰ)[J]. 高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào), 1979, (2): 196-209.

[6] 齊東旭, 梁振珊. 多結(jié)點(diǎn)樣條磨光(Ⅱ)[J]. 高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào), 1981, (1): 68-81.

[7] DE BOOR C. How does Agee’s smoothing method work? [R]. Washington D C: Army Research Office 79-3, 1979: 299-302.

[8] 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.

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

[10] LIN H, WANG G, DONG C. 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.

[11] 鄧少輝, 汪國(guó)昭. 漸進(jìn)迭代逼近方法的數(shù)值分析[J]. 計(jì)算輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2012, 24(7): 879-884.

[12] LIU M, LI B, GUO Q, et al. Progressive iterative approximation for regularized least square bivariate B-spline surface fitting [J]. Journal of Computational and Applied Mathematics, 2018, 327: 175-187.

[13] 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.

[14] 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.

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

[16] LIN H. The convergence of the geometric interpolation algorithm [J]. Computer-Aided Design, 2010, 42(6): 505-508.

[17] XIONG Y, LI G, MAO A. Convergence analysis for B-spline geometric interpolation [J]. Computers & Graphics, 2012, 36(7): 884-891.

[18] 齊東旭. 關(guān)于計(jì)算機(jī)輔助幾何造型數(shù)學(xué)方法的若干注記[J]. 北方工業(yè)大學(xué)學(xué)報(bào), 1991, 3(1): 1-8.

[19] 李岳生, 齊東旭. 樣條函數(shù)方法[M]. 北京: 科學(xué)出版社, 1979: 148-176.

[20] CAI Z C, LAN T, ZHENG C. Hierarchical MK splines: Algorithm and applications to data fitting [J]. IEEE Transactions on Multimedia, 2017, 19(5): 921-934.

[21] LIU D C, NOCEDAL J. On the limited memory BFGS method for large scale optimization [J]. Mathematical Programming, 1989, 45(1): 503-528.

[22] QIN Z W. The relationships between CG, BFGS, and two limited-memory algorithms [J]. Furman University Electronic Journal of Undergraduate Mathematics, 2016, 12(1): 5-20.

[23] NASH S G, NOCEDAL J. A numerical study of the limited memory BFGS method and the truncated- newton method for large scale optimization [J]. SIAM Journal on Optimization, 1991, 1(3): 358-372.

[24] SHANNO D F. On the convergence of a new conjugate gradient algorithm [J]. SIAM Journal on Numerical Analysis, 1978, 15(6): 1247-1257.

[25] LIU Y, WANG W P, LéVY B, et al. On centroidal voronoi tessellation-energy smoothness and fast computation [J]. ACM Transactions on Graphics, 2009, 28(4): 1-17.

[26] WANG Y C, DONG L, XUE X, et al. On the design of constant modulus sequences with low correlation sidelobes levels [J]. IEEE Communications Letters, 2012, 16(4): 462-465.

[27] WANG Y C, WANG X, LIU H, et al. On the design of constant modulus probing signals for MIMO radar [J]. IEEE Transactions on Signal Processing, 2012, 60(8): 4432-4438.

[28] 劉超, 辛士慶, 舒振宇, 等. 幾何迭代法的加速[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2016, 28(11): 1838-1843.

Geometric Iteration Method Based on Many-Knot Spline Polishing Functions

HUO Yan-wen, CAI Zhan-chuan

(Faculty of Information Technology, Macau University of Science and Technology, Macau 999078, China)

Geometric iteration method has been widely used in computer aided geometric design (CAGD). In order to improve the convergence speed and iterative accuracy of the traditional B-spline curve interpolation in geometric iterations, this study proposes the geometric iteration method based on many-knot spline polishing functions, which introduces many-knot spline polishing functions, and combines many-knot spline polishing functions method and geometric iteration method in curve fitting. After polishing operator and iterating, the curve fitting method with high approximation under the optimal solution of L-BFGS iterative algorithm is constructed. Experimental results show that the proposed method not only reduces the times of iterations, but also improves the iterative speed under the same accuracy. The proposed geometric iteration method can be used in the shape design of airplanes, automobiles, etc. It can also be used to reconstruct and rebuild the shape of cultural relic houses and satellite image processing.

geometric iteration method; many-knot spline polishing functions; limited-memory BFGS algorithm; B-splines

TP 391

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

A

2095-302X(2019)01-0015-09

2018-07-02；

2018-07-21

國(guó)家基礎(chǔ)研究計(jì)劃“973”項(xiàng)目(2011CB302400)；澳門科技發(fā)展基金項(xiàng)目(048/2016/A2，0012/2018/A1，0069/2018/A2)；國(guó)家自然科學(xué)基金面上項(xiàng)目(61272364)；浙江大學(xué)CAD&CG國(guó)家重點(diǎn)實(shí)驗(yàn)室開放課題(A1910)；北京理工大學(xué)珠海學(xué)院科研發(fā)展基金項(xiàng)目(XK-2018-04)

霍彥妏(1992-)，女，山西太原人，碩士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)等。E-mail：huohyw@163.com

蔡占川(1973-)，男，河北館陶人，教授，博士，博士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)圖形圖像處理、數(shù)值分析。E-mail：zccai@must.edu.mo