B樣條曲線的雙層最小二乘漸進(jìn)迭代逼近算法

王 慧，鄧重陽，李亞娟

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

數(shù)據(jù)擬合在計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)和計(jì)算機(jī)輔助制造中均有廣泛的應(yīng)用。在逆向工程領(lǐng)域里，一般是從實(shí)物中獲取數(shù)據(jù)點(diǎn)集，然后運(yùn)用幾何方法建立其數(shù)字模型[1]。由于這類數(shù)據(jù)點(diǎn)集的排列往往是不規(guī)律的，所以通常選取B樣條曲線來擬合這類數(shù)據(jù)點(diǎn)集。使用B樣條曲線擬合數(shù)據(jù)點(diǎn)時(shí)，需要通過求解線性方程組來反算控制頂點(diǎn)。齊東旭等[2]提出均勻3次B樣條曲線的盈虧修正算法，Boor[3]證明了算法的收斂性。Lin等[4]先證明了非均勻3次B樣條曲線也具有盈虧修正性質(zhì)，然后將盈虧修正性質(zhì)推廣到所有全正基混合曲線，并給出了漸進(jìn)迭代逼近的英文術(shù)語(Progressive Iterative Approximation，PIA)[5]。對于二維斷面數(shù)據(jù)的曲線重建問題，徐進(jìn)等[6]提出基于特征點(diǎn)自動識別的3次B樣條曲線逼近算法。Lu[7]和Deng等[8]通過調(diào)整向量加權(quán)的方式，提升了PIA的收斂速度。為了實(shí)現(xiàn)用少量控制頂點(diǎn)擬合數(shù)據(jù)點(diǎn)集，2011年Lin等[9]提出一種擴(kuò)展的漸進(jìn)迭代逼近法(Extended Progressive Iterative Approximation，EPIA)。Deng等[10]進(jìn)一步提出基于最小二乘漸進(jìn)迭代逼近(Least Squares Progressive Iterative Approximation，LSPIA)的B樣條曲線擬合方法，在迭代中計(jì)算調(diào)整向量并更新控制頂點(diǎn)的位置，從而產(chǎn)生一個(gè)曲線序列，其極限曲線序列收斂到關(guān)于數(shù)據(jù)點(diǎn)的最小二乘法所得的曲線。Lin等[11]論證了奇異迭代矩陣LSPIA算法的收斂性。常清俊等[12]提出了分塊高斯-塞德爾迭代的曲線曲面擬合方法，與高斯-塞德爾迭代法相比，提升了收斂速度，但這種方法未考慮數(shù)據(jù)點(diǎn)集中特征點(diǎn)的擬合情形。為了高效且精確地?cái)M合大型數(shù)據(jù)點(diǎn)集，本文提出一種基于雙層LSPIA算法的均勻3次B樣條曲線擬合方法，通過相鄰點(diǎn)之間擬合圓弧的方法確定特征點(diǎn)，將特征點(diǎn)作為插值點(diǎn)，其余的數(shù)據(jù)點(diǎn)作為待擬合點(diǎn)，經(jīng)過雙層LSPIA算法，快速生成逼近數(shù)據(jù)點(diǎn)集的均勻3次B樣條擬合曲線。

1 曲線擬合算法

1.1 基于LSPIA的均勻3次B樣條曲線擬合算法

(1)

基于LSPIA的均勻3次B樣條曲線擬合算法主要步驟如下[10]。

(2)

式中，u∈[t0,tm]，基函數(shù)對應(yīng)的配置矩陣為：

P(0)=AP0

(3)

(2)計(jì)算每一個(gè)控制頂點(diǎn)的調(diào)整向量。

(4)

式中，λ0為矩陣ATA的最大特征值，μ為常數(shù)。

(3)更新控制頂點(diǎn)。

(5)

其矩陣形式為：

P(1)=AP1

(6)

(7)

(8)

(9)

根據(jù)新的控制頂點(diǎn)生成第k+1次擬合曲線如下：

(10)

(5)重復(fù)執(zhí)行上述的迭代過程，即可產(chǎn)生一個(gè)曲線序列{P(k)(t),k=0,1,2,…}。文獻(xiàn)[5]證明了當(dāng)基函數(shù)為全正基函數(shù)時(shí)，產(chǎn)生的極限曲線序列收斂到關(guān)于數(shù)據(jù)點(diǎn)列的最小二乘擬合結(jié)果。

1.2 基于雙層LSPIA的均勻3次B樣條曲線擬合算法

為了更高效地?cái)M合大型數(shù)據(jù)點(diǎn)集，本文提出基于雙層LSPIA的均勻3次B樣條曲線擬合算法，算法主要步驟如下。

(1)采用相鄰點(diǎn)之間擬合圓弧的方法[6]，近似估算每個(gè)數(shù)據(jù)點(diǎn)對應(yīng)的離散曲率，將數(shù)據(jù)點(diǎn)列中的曲率極值點(diǎn)、曲率不連續(xù)點(diǎn)和曲率拐點(diǎn)作為插值點(diǎn)，同時(shí)基于隔點(diǎn)采樣法，選取除插值點(diǎn)外數(shù)據(jù)點(diǎn)列的部分?jǐn)?shù)據(jù)點(diǎn)作為擬合點(diǎn)，不妨設(shè)插值點(diǎn)誤差為ε1，擬合點(diǎn)誤差為ε2。

(4)依次執(zhí)行1.1節(jié)中的步驟2和步驟3，得到1次迭代后生成的擬合曲線。

雙層LSPIA算法與LSPIA算法相比，在第一層LSPIA算法迭代過程中，構(gòu)建擬合曲線所含方程的個(gè)數(shù)等于第一層選取的待擬合數(shù)據(jù)點(diǎn)的個(gè)數(shù)，其中基函數(shù)的配置矩陣A的維數(shù)比LSPIA算法對應(yīng)的配置矩陣A的維數(shù)降低一半左右，因此第一層LSPIA算法的迭代速度更快；雖然第二層LSPIA算法是針對所有數(shù)據(jù)點(diǎn)進(jìn)行迭代逼近，但由于均勻3次B樣條曲線的局部性質(zhì)，只要控制頂點(diǎn)位置不變，那么擬合曲線的形狀就不會發(fā)生改變，即在第二層LSPIA算法迭代過程中，只需迭代更新除第一層待擬合數(shù)據(jù)點(diǎn)外的其余數(shù)據(jù)點(diǎn)對應(yīng)的控制頂點(diǎn)的位置，減少了迭代次數(shù)，同時(shí)縮短了迭代時(shí)間。

2 實(shí)例分析

實(shí)驗(yàn)平臺的操作系統(tǒng)為Windows，測試工具為MATLAB 2017b。實(shí)驗(yàn)選取的10個(gè)測試數(shù)據(jù)集是通過提取一些模型的邊緣輪廓獲得的，對其進(jìn)行擬合，來驗(yàn)證本文算法的有效性。當(dāng)數(shù)據(jù)點(diǎn)和擬合曲線上對應(yīng)點(diǎn)之間的距離足夠小時(shí)，認(rèn)為擬合曲線插值了這一數(shù)據(jù)點(diǎn)，故將插值點(diǎn)的誤差精度和擬合點(diǎn)的誤差精度分別設(shè)為ε1=10-16和ε2=10-5，即在數(shù)值實(shí)驗(yàn)過程中，當(dāng)插值點(diǎn)和擬合點(diǎn)的誤差均小于對應(yīng)的誤差精度時(shí)，算法迭代停止。分別使用基于LSPIA的均勻3次B樣條曲線擬合算法和基于雙層LSPIA的均勻3次B樣條曲線擬合算法擬合這10組數(shù)據(jù)集，獲得關(guān)于數(shù)據(jù)點(diǎn)集的最小二乘擬合結(jié)果。

比較基于LSPIA和基于雙層LSPIA的B樣條曲線擬合算法的迭代時(shí)間與迭代次數(shù)，對比結(jié)果如表1所示。迭代時(shí)間取多次測試時(shí)間的平均值，選用平均誤差作為擬合誤差，表示如下：

表1 不同方法迭代時(shí)間和迭代次數(shù)比較

從表1可以看出，無論在迭代時(shí)間還是迭代次數(shù)上，雙層LSPIA算法都比LSPIA算法的擬合效率高，尤其對大量數(shù)據(jù)點(diǎn)進(jìn)行擬合時(shí)，雙層LSPIA算法的迭代時(shí)間比LSPIA算法快了約2 s。

圖1展示了在相同的誤差精度下，分別運(yùn)用LSPIA算法和雙層LSPIA算法擬合例1—例8所需的迭代次數(shù)。從圖1可以看出，對于數(shù)據(jù)點(diǎn)數(shù)較大且含有較多特征點(diǎn)的數(shù)據(jù)點(diǎn)集(如例1、例7、例8)，雙層LSPIA算法的迭代次數(shù)明顯少于LSPIA算法。

圖2給出了LSPIA算法和雙層LSPIA算法擬合例9中10 001個(gè)數(shù)據(jù)點(diǎn)集所需的迭代次數(shù)隨控制頂點(diǎn)數(shù)的變化關(guān)系。從圖2可以看出，在控制頂點(diǎn)相同的條件下，雙層LSPIA算法的迭代次數(shù)明顯少于LSPIA算法，且控制頂點(diǎn)個(gè)數(shù)為200～500時(shí)，兩種算法迭代次數(shù)的差距較大，展現(xiàn)出本文算法的高效性。綜上分析表明，擬合9個(gè)數(shù)值實(shí)例中，雙層LSPIA算法所需的迭代次數(shù)明顯少于LSPIA算法，擬合時(shí)間更短。

圖1 不同方法迭代次數(shù)比較

圖2 迭代次數(shù)隨控制頂點(diǎn)數(shù)的變化關(guān)系

圖4展示了采用雙層LSPIA算法擬合例2—例9的最終曲線擬合效果，其中實(shí)心點(diǎn)為數(shù)據(jù)點(diǎn)，實(shí)曲線是均勻3次B樣條曲線的最終擬合效果，矩形框、實(shí)線圓和虛線圓分別表示第一層迭代選取的曲率極值點(diǎn)、曲率拐點(diǎn)和曲率不連續(xù)點(diǎn)。

圖3 擬合2 561個(gè)數(shù)據(jù)點(diǎn)的均勻3次B樣條曲線

圖4 運(yùn)用雙層LSPIA擬合例2—例9的擬合結(jié)果

3 結(jié)束語

在LSPIA算法的基礎(chǔ)上，本文引入分層迭代的思想，將雙層LSPIA算法應(yīng)用于均勻3次B樣條曲線擬合中。與LSPIA算法相比，雙層LSPIA算法的迭代次數(shù)和迭代時(shí)間更少，擬合效率更高。后期將研究多層LSPIA的B樣條曲線曲面擬合方法，進(jìn)一步提高誤差精度和擬合效率。