基于差分進化算法的B樣條曲線曲面擬合

何兵朋， 馮仁忠， 余勝蛟

(北京航空航天大學數學與系統科學學院，北京 100083)

基于差分進化算法的B樣條曲線曲面擬合

何兵朋， 馮仁忠， 余勝蛟

(北京航空航天大學數學與系統科學學院，北京 100083)

應用B樣條曲線曲面擬合內在形狀帶有間斷或者尖點的數據時，最小二乘法得到的擬合結果往往在間斷和尖點處誤差較大，原因在于最小二乘法將擬合函數B樣條的節點固定。本文在利用3次B樣條曲線和曲面擬合數據時，應用差分進化算法設計出一種能夠自適應地設置B樣條節點的方法，同時對節點的數量和位置進行優化，使得B樣條擬合曲線曲面在間斷和尖點處產生擬多重節點，實現高精度地擬合采樣于帶有間斷或尖點的曲線和曲面數據。

數據擬合；B樣條曲線曲面；最小二乘法；差分進化算法；自適應；擬多重節點

B樣條曲線曲面已被廣泛應用于數據擬合、幾何建模、CAD、醫學成像等領域[1-4]。當擬合數據的內在形狀較為復雜時，簡單的多項式難以精確地擬合，然而具有局部可調性質的B樣條是一種有效的擬合函數。節點的設置對B樣條曲線的形狀有重要的影響，不合理的節點矢量可能會產生不可接受的形狀[5-6]。所以，應用 B樣條進行數據擬合的關鍵在于尋找最優的節點矢量，包括節點的數量和位置。節點設為變量的B樣條擬合問題是一個多元和多極值的非線性最優化問題[7]，難以獲得其全局最優解且最小二乘法無法直接求解此類問題。鑒于此，許多傳統的方法[8-10]被提出來，這些方法可分為2類：節點插入和節點刪除，如Jupp[9]提出一種將節點進行對數轉化的方法；Lyche和M?rken[8]提出一種數據簡化算法實現節點刪除的方法。近年來，許多異于上述傳統方法的自適應設置節點的算法被提出[5-6, 11-13]，如Yoshimoto等[11]提出一種基于遺傳算法的自適應地優化節點數量和位置的方法，能夠較好地擬合帶有尖點和間斷的數據；Li等[5]提出一種基于數據點的光滑曲率和啟發式準則的非迭代算法，較好擬合稠密的和帶噪音的數據點；ülker和??ler[12]提出一種人工免疫系統方法以求解B樣條曲面擬合問題。然而，很多文獻只是將提出的方法用于B樣條曲線擬合，并沒有將其擴充到B樣條曲面擬合。

本文應用差分進化算法[14](differential evolution, DE)設計出一種新的求解B樣條擬合的方法，其能夠根據數據的變化情況自適應地設置節點，同時對節點的數量和位置進行優化，并且在間斷和尖點處產生擬多重節點。通過計算機程序計算浮點型節點產生真正的多重節點是幾乎不可能的，但是通過數值試驗發現，本文提出的方法能夠產生多個非常接近的節點，可稱之為擬多重節點。擬多重節點使得擬合曲線能較好地擬合急劇變化的數據，包括間斷和尖點。

從對比數值試驗的結果可發現，本文提出的方法的擬合效果比最小二乘法和遺傳算法都要好，能更精確地求解采樣于帶有間斷和尖點函數數據的B樣條曲線曲面擬合問題。

1　基于最小二乘法的B樣條擬合

以二維數據擬合為例，介紹B樣條擬合的最小二乘法。假設擬合數據為：

其中，f(x)為采樣函數(對于散亂數據，f(x)是未知的)，ε為噪音誤差，N為采樣數量。

設定義k次B樣條曲線的節點為ξi∈[a,b] (i=0,1,…,n+2 k +1)，n為內節點數。通常將端節點設為k+1重節點，即：

擬合函數記為：

其中，di(i=0,1,…,n+ k)為控制頂點，Ni,k( i=0,1,…,n+ k) 為k次B樣條基函數，其遞推公式為：

用R記以下殘差平方和：

2　基于差分進化算法的B樣條擬合

最小二乘法是在 B樣條的內節點數量和位置均固定的情況下求得最優擬合曲線或曲面，以致其對間斷和尖點的擬合效果較差。本文在最小二乘法的基礎上，應用差分進化算法設計出一種能夠根據擬合數據的變化情況自適應地設置 B樣條節點的方法，同時對節點數量和位置進行優化，從而更精確地擬合急劇變化的數據。

2.1B樣條擬合的差分進化算法實現

(1) 初始種群。在差分進化算法中將優化問題的一個可行解作為一個個體，在這里將B樣條擬合問題中的一組可行內節點(ni為ξi的長度)作為一個個體，由NP個個體組成一個種群，NP稱為種群規模。本文中初始種群個體長度均設為L=[λN]，N是被擬合數據點數量，λ稱為節點率，其取值隨具體實例的不同而改變。

本文在差分進化算法的變異和雜交操作的基礎上增加刪除和插入節點功能，來自適應地調整內節點的數量和位置。對第G代的第i(i=0,1,…,NP-1)個個體進行變異、雜交和選擇操作。

(2) 變異操作。變異操作分3步來完成。

步驟1. 隨機選取 3個互不相同且不同于ξi,G的個體,分別對進行如下操作：

如果rand()1＜dp(dp稱為刪除概率，rand()1為[0,1]之間的隨機數)，則隨機刪除ξj,G中的一個節點，得到一個新個體ξ′j,G；否則，按升序向ξj,G隨機插入一個(a,b)之間的節點，得到一個新個體。

步驟2. 取D=m in{nr1,nr 2,nr 3}，其中nr1,nr 2,nr 3分別為的長度。如果D=nr 1，則將中每nr2-D+1個元素相加后求其平均值按順序依次存入 ξr′2,G中，即：

同樣地，對ξr′3,G進行此操作。如果D=nr或D=nr3時，同樣依此方法處理。

其中，FG稱為變異系數，本文其值取為，Gm為最大迭代次數。

(3) 雜交操作。將ξi,G和Ui,G雜交得到試驗向量Vi, G：

(4) 選擇操作。本文使用統計學中貝葉斯信息準則 BIC[15](評價模型擬合效果的一種方法)作為適應度函數，在本文曲線擬合問題中，其表達式為：

其中，N為擬合數據點的數量，R為殘差平方和，2n+k+1為變量的數量。曲面擬合問題中，其表達式類似給定。BIC值的大小反映了擬合精度，其值越小，擬合精度越高。

選擇操作過程：首先對個體ξi,G通過第 1節中最小二乘法求得對應的B樣條最優控制頂點；然后利用式(2)求出相應的殘差平方和R，進而利用式(3)計算出與ξi,G對應的適應度函數值ξ_BIC。同時，采用同樣的方法計算出與Vi,G對應的適應度函數值V_BIC。最后，根據貪婪法則，選擇較優個體遺傳到下一代：

2.2數據擬合算法

結合上述差分進化算法的描述，給出以下數據擬合算法：

步驟2. 輸入差分進化算法參數，包括種群規模NP、節點率λ、節點刪除概率dp、最大迭代次數Gm；

步驟4. 對每一個個體應用最小二乘法求得與之對應的最小殘差平方和，進而計算出對應的適應度函數BIC值；

步驟5. 進行變異和雜交操作；

步驟6. 根據適應度函數值進行選擇，并更新種群；

步驟7. 判斷迭代終止條件G＞Gm。如果達到終止條件，則停止計算，輸出最優內節點組；否則，轉到步驟4。

3　數值試驗

利用第1～2節介紹的算法，對幾組采樣于帶有間斷、尖點以及間斷面的曲線和曲面數據進行擬合，將擬合結果與遺傳算法的結果及最小二乘法擬合結果進行比較。

3.1曲線擬合

例1. 擬合數據由以下函數生成：

該函數在x=0.4附近發生劇烈的變化，其形狀類似于一個臺階。相關參數設置：λ=0.025，dp=0.6。

圖1、2為每一代最優個體的適應度函數值以及內節點數量隨迭代次數的增加而變化的圖像，其中點劃線表示 30次試驗的平均適應度函數值隨迭代次數的增加的變化圖像，實線表示 30次試驗中最好的一次試驗的適應度函數值隨迭代次數的增加的變化圖像，點線表示內節點數隨迭代次數的增加的變化圖像。從圖1可看出，DE算法大概在25代收斂，且收斂結果穩定；內節點數很快由初始給定的5個減少為4個，并保持不變；DE算法收斂后適應度函數值為630，大約為遺傳算法同等條件下的收斂值1 200的一半。這反映了本文方法的擬合精度高于遺傳算法。

將最小二乘法擬合效果和本文提出的算法收斂時的擬合效果進行了對比，圖3為5個均勻分布內節點的B樣條的最小二乘法擬合效果圖，圖4為差分進化算法收斂后的擬合效果圖。通過兩圖對比可看出，在x=0.4附近，最小二乘法得到的3次B樣條擬合曲線出現較大的波動，擬合效果較差，而差分進化算法得到的3次B樣條擬合曲線在此處附近與采樣數據點相合較好，其擬合效果明顯優于最小二乘法。原因在于差分進化算法能對內節點的位置和數量進行優化，節點由初始均勻分布的5個，優化為匯集在x=0.4附近的4個，并在x=0.4處產生一個擬二重節點，提高了擬合精度。

圖1　DE算法適應度函數值以及節點數變化圖像

圖2　遺傳算法適應度函數值以及節點數變化圖像

圖3　最小二乘法擬合效果圖

圖4　DE算法擬合效果圖

例2. 擬合數據由以下函數生成：

該函數在x=5處不可導，有一個尖點。相關參數設置為：λ=0.05，dp=0.6。

由圖5可知，DE算法大概在75代收斂，收斂結果穩定；內節點數很快由初始給定的10個減少為7個，并保持不變；對比圖5和圖6，DE算法收斂后適應度函數值為640，大約為遺傳算法的計算結果1 200的一半。對比圖7、8易知，差分進化算法收斂后冗余的節點被刪除，并且在尖點處產生了一個擬三重節點；在尖點 x=5附近，最小二乘法得到的3次B樣條擬合曲線是光滑的，擬合效果較差，而差分進化算法對節點數量和位置進行優化后得到的擬合曲線幾乎與采樣點重合，擬合效果較好。

圖5　DE算法適應度函數值以及節點數變化圖像

圖6　遺傳算法適應度函數值以及節點數變化圖像

圖7　最小二乘法擬合效果圖

圖8　DE算法擬合效果圖

3.2曲面擬合

應用提出的方法對表1中2個帶有間斷或尖點的曲面進行擬合。曲面擬合數值試驗：均取32×32的網格進行無噪音數據采樣；均通過均勻節點加隨機擾動的方法生成初始種群；差分進化算法參數均設置為NP=50，Gm=2 000；終止條件均設為：平均平方誤差MSE＜10-5或者迭代次數 G＞Gm。MSE的定義為：

表1　測試函數

表2　曲面擬合數值試驗計算結果

由表2可知，與初始時節點數量相比，DE算法收斂后測試1節點的數量減少了，而測試2節點數量增加了，這說明本文提出的方法實現了節點自適應設置。

將差分進化算法收斂后的擬合效果與最小二乘法擬合效果進行對比。圖9為按照表2設置的初始均勻分布內節點的情況下最小二乘法擬合效果圖和差分進化算法收斂后的擬合效果圖。比較圖9(a)～(b)可知，最小二乘法得到的擬合曲面在間斷處是光滑的且有振蕩，擬合效果較差；而差分進化算法收斂后得到的3次B樣條擬合曲面幾乎能準確構造出采樣數據曲面。比較圖9(c)～(d)可知，最小二乘法擬合結果在圖形底部有較大的誤差，而差分進化算法收斂后擬合結果較好重構出被擬合函數的圖像。

圖9　曲面擬合數值試驗效果圖

4　結論與展望

本文利用差分進化算法設計了一種求解3次B樣條曲線曲面非線性擬合問題的方法，該方法能夠自適應地優化內節點的數量和位置，在間斷和尖點附近產生擬多重節點，實現了對帶有間斷和尖點的曲線曲面高精度擬合。通過數值試驗發現，迭代過程中誤差呈臺階式下降。此外，本文提出的方法對不同的實例需要通過試驗來確定節點刪除概率的大小。鑒于此，作者將進一步研究差分進化算法和本文提出的方法，加快算法收斂速度，實現參數對不同實例的自適應調整。

[1] Safari A, Lemu H G, Jafari S, et al. A comparative analysis of nature-inspired optimization approaches to 2D geometric modeling for turbomachinery applications [J]. Mathematical Problems in Engineering, 2013, (11): 1-15.

[2] 馮仁忠, 查理. 局部構造C2連續的三次B樣條插值曲線和雙三次插值曲面[J]. 工程圖學學報, 2005, 26(6): 110-117.

[3] Lee D, Pavlidis T. One-dimensional regularization with discontinuities [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1988, 10(6): 822-829.

[4] Zhao X Y, Zhang C M, Xu L, et al. IGA-based point cloud fitting using B-spline surfaces for reverse engineering [J]. Information Sciences, 2013, 245(10): 276-289.

[5] Li W S, Xu S H, Zhao G, et al. Adaptive knot placement in B-spline curve approximation [J]. Computer-Aided Design, 2005, 37(8): 791-797.

[6] Zhao X Y, Zhang C M, Yang B, et al. Adaptive knot placement using a GMM-based continuous optimization [J]. Computer-Aided Design, 2011, 43(6): 598-604.

[7] Dierckx P. Curve and surface fitting with splines [M]. Oxford: Oxford University Press, 1993: 58-61.

[8] Lyche T, M?rken K. A data-reduction strategy for splines with applications to the approximation of functions and data [J]. Ima Journal of Numerical Analysis, 1988, 8(2): 185-208.

[9] Jupp D L B. Approximation to data by splines with free knots [J]. SIAM Journal on Numerical Analysis, 1978, 15(2): 328-343.

[10] Piegl L, Tiller W. The NURBS book [M]. New York: Springer Press, 1997: 141-187.

[11] Yoshimoto F, Harada T, Yoshimoto Y. Data fitting with a spline using a real-coded genetic algorithm [J]. Computer-Aided Design, 2003, 35(8): 751-760.

[12] ülker E, ??ler V. An artificial immune system approach for B-spline surface approximation problem [C]//Lecture Notes in Computer Science. Berlin: Springer Press, 2007: 49-56.

[13] Garcia-Capulin C H, Cuevas F J, Trejo-Caballero G, et al. Hierarchical genetic algorithm for B-spline surface approximation of smooth explicit data [J]. Mathematical Problems in Engineering, 2014, 2014: 1-11.

[14] Storn R, Price K. Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous spaces [J]. Journal of Global Optimization, 1995, 23(4): 341-359.

[15] Schwarz G B. Estimating the dimensions of a model [J]. The Annals of Statistics, 1978, 6(2): 461-464.

B-Sp line Curve and Surface Fitting Using Differential Evolution A lgorithm

He Bingpeng,Feng Renzhong,Yu Shengjiao

(School of Mathematics and System Science, Beihang University, Beijing 100083, China)

To use B-spline curve and surface to fit data with an underlying function having discontinuous points and/or cusps, the fitting results obtained by least squares method are often bad in the vicinity of discontinuous points and cusps because of the fixed B-spline knots. In this paper, we propose a method for solving data fitting problem with cubic B-spline curve and surface by using differential evolution algorithm. Our method can set B-spline knots adaptively, so as to optim ize the number and location of knots simultaneously and produce quasi-multiple knot in the vicinity of discontinuous points and cusps. W ith this, we can fit data with an underlying function having discontinuous points and/or cusps with high precision.

data fitting; B-spline curve and surface; least squares method; differential evolution algorithm; adaptation; quasi-multiple knot

TP 391.7

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

A

2095-302X(2016)02-0178-06

2015-09-24；定稿日期：2015-10-01

國家自然科學基金項目(11271041)；民用飛機專項項目(M J-F-2012-04)

何兵朋(1993–)，男，湖北咸寧人，碩士研究生。主要研究方向為計算幾何。E-mail：hebinpeng429@126.com

馮仁忠(1967–)，男，江西都昌人，教授，博士。主要研究方向為數值逼近與計算幾何。E-mail：fengrz@buaa.edu.cn