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

2021-08-10 09:36:32鄧重陽李亞娟

杭州電子科技大學學報(自然科學版) 2021年4期

王慧，鄧重陽，李亞娟

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

0 引言

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

1 曲線擬合算法

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

(1)

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

(2)

式中，u∈[t0,tm]，基函數對應的配置矩陣為：

P(0)=AP0

(3)

(2)計算每一個控制頂點的調整向量。

(4)

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

(3)更新控制頂點。

(5)

其矩陣形式為：

P(1)=AP1

(6)

(7)

(8)

(9)

根據新的控制頂點生成第k+1次擬合曲線如下：

(10)

(5)重復執行上述的迭代過程，即可產生一個曲線序列{P(k)(t),k=0,1,2,…}。文獻[5]證明了當基函數為全正基函數時，產生的極限曲線序列收斂到關于數據點列的最小二乘擬合結果。

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

為了更高效地擬合大型數據點集，本文提出基于雙層LSPIA的均勻3次B樣條曲線擬合算法，算法主要步驟如下。

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

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

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

2 實例分析

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

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

表1 不同方法迭代時間和迭代次數比較

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

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

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