王 慧，鄧重陽，李亞娟

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

0 引 言

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

1 曲線擬合算法

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

(1)

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

(2)

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

P(0)=AP0

(3)

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

(4)

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

(3)更新控制頂點。

(5)

其矩陣形式為：

P(1)=AP1

(6)

(7)

(8)

(9)

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

(10)

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

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

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

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

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

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

2 實例分析

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

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

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

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

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

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

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

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

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

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

圖4 運用雙層LSPIA擬合例2—例9的擬合結果

3 結束語

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