用四點插值細分曲線擬合離散點列

邱 慧,李亞娟,鄧重陽

(杭州電子科技大學,浙江 杭州 310018)

0 引 言

數據擬合廣泛地應用于計算機輔助幾何設計、計算機圖形學[1]、逆向工程[2]等領域。B樣條曲線以其分段光滑、幾何不變性和局部支撐性等[3]優點成為了數據擬合的首選方法[4]。利用B樣條曲線進行數據擬合時,通常需要先確定節點向量和參數,然后求解控制頂點。在節點向量和參數確定之后,控制頂點的計算即求解一個線性方程組[5]。而一般情況下,由于數據點的數量較多,所以經常需要采用迭代法計算該線性方程組。Lin等[6]提出了基于漸進迭代逼近(progressive and iterative approximation, PIA)的B樣條曲線插值算法。2005年,趙宇等[7]對用于數據插值的PIA算法進行擴展,使該算法適用于數據逼近問題。而Deng等[8]進一步提出基于最小二乘法的漸進迭代逼近(progressive and iterative approximation for least squares, LSPIA)算法。該算法通過調整控制點的數目和節點向量構造一系列逼近數據點列的三次均勻B樣條曲線。對于大規模的數據點集,在擬合過程中,也能夠合理地控制擬合曲線的形狀,具有保形的效果。近40年來,細分逐漸走入了計算機輔助幾何設計、計算機圖形學的研究領域。以其固有的特性,也被應用到曲線重建中[9]。細分法最早由Rham[10]提出,該方法幾何直觀,操作簡單,修正方便,層次清晰,并且生成的曲線光滑性較好[11]。之后,Dyn等[12]提出的四點插值細分法是第一個單參數的插值型細分曲線造型法,且其極限曲線C1連續。本文利用Deng等[13]提出的四點插值細分法的極限曲線上的點的計算公式,結合離散點的參數化及最小二乘法(LSM)求解擬合曲線的初始控制點,并根據初始控制點確定逼近離散數據點列的四點插值細分曲線。與三次均勻B樣條曲線的擬合算法相比,該算法在一定的擬合誤差下,所需的初始控制點數目較少。在實際應用中,該算法只需少量的初始控制點即可確定離散數據點列的擬合曲線,具有數據簡化的作用。而運用于多分辨率分析時,可以利用細分法的特性,控制初始控制點的細分次數,得到任意個數點列構成的擬合曲線。

1 四點插值細分法的極限曲線上的點的計算公式

四點插值細分法是細分法中的一個經典方法,根據其細分規則遞歸地定義極限曲線。

(1)

圖1 以初始控制點細分多次形成的四點插值細分極限曲線

四點插值細分法雖然是單參數的插值型細分法,但由于細分規則的非參數化表達,這使其在應用中受到了很多限制。所以在應用中,通過借助四點插值細分法的極限曲線上的點的計算公式,由參數值直接確定每一個離散點對應在極限曲線上的確切位置。同時,這也有利于之后將本文算法推廣到曲面的工作。

(2)

同理,極限曲線上的任一極限點都可由初始控制點表示其在極限曲線上的精確位置。

2 基于四點插值細分法多項式表示曲線擬合算法

相比于參數形式和隱函數形式表示的曲線造型方法,細分法具有參數法的許多優點[14]。而四點插值細分法不僅細分規則及表示相對較簡單,而且具有多項式重構性,應用于擬合離散數據點列,將比參數法具有更強的適應性。

本節將詳細介紹基于四點插值細分法多項式表示的曲線擬合算法,并給出其實現步驟。

2.1 算法描述

2.1.1 一般參數化確定系數點列

(3)

[Pk+1]=Ak[Pk]

(4)

[Pk]=A[P0]

(5)

(6)

2.1.2 分組參數化確定系數矩陣

對每一個t′i,i=1,…,n+1,可由

(7)

(8)

(9)

相比于公式,公式的計算方法簡單方便,且可達到算法的要求。

本文算法步驟如下:

3 實例與分析

本節通過三個具體實例,展示了四點插值細分曲線擬合算法的擬合效果。并將其擬合效果與三次均勻B樣條曲線的擬合效果,分別就給定擬合誤差下的控制頂點數目和給定控制頂點數目下的擬合誤差進行對比。實驗數據說明該算法在實際應用中能夠對數據點列進行有效擬合。

本節利用LSPIA算法構造三次均勻B樣條曲線。另外,選用距離平方和的均值作為擬合誤差,其計算公式為:

(10)

以下三個實例中,離散數據點列都提取于一些封閉圖像模型的邊框輪廓,具有隨機性和代表性。圖2～圖4中,圖(a)及圖(c)內的圓點表示細分的初始控制點,圖(b)中的圓點表示細分一次后所產生的新點及老點,圖5～圖7中的圓點均表示細分的初始控制點。

圖2～圖4分別為由70、40、40個初始控制點細分多次形成的四點插值細分曲線擬合離散數據點列。其中,(d)圖的擬合曲線是以LSPIA算法構造的一系列三次均勻B樣條曲線。初始控制點與對應例子個數相同,并且在前后兩次迭代的擬合誤差相差10-7時算法停止迭代。

圖2 例1:四點插值細分曲線與三次均勻B樣條曲線擬合1161個離散數據點列所形成的近似曲線

圖3 例2:四點插值細分曲線與三次均勻B樣條曲線擬合501個離散數據點列所形成的近似曲線

圖4 例3:四點插值細分曲線與三次均勻B樣條曲線擬合577個離散數據點列所形成的近似曲線

上述實例在控制點個數相同下,不同算法的擬合誤差對比如表1所示。由表可知,利用四點插值細分法擬合離散點列,其擬合誤差相比之下更小。其中EB-spline表示由LSPIA算法構造的一系列三次均勻B樣條曲線的擬合誤差,E4-point表示由本文算法構造的四點插值細分曲線的擬合誤差。

表1 控制點個數相同時,不同算法的擬合誤差

而由表2可知在給定的擬合誤差下,本文算法利用的初始控制點數目較少,其中PB-spline表示由LSPIA算法構造的一系列三次均勻B樣條曲線的初始控制點個數,P4-point表示由本文算法構造的四點插值細分曲線的初始控制點個數。

表2 擬合誤差相同時,不同算法的初始控制點個數

圖5～圖7為對應實例依次新增10個初始控制頂點時,曲線擬合離散數據點列的情況。

圖5 例1 不同初始控制點的四點插值細分曲線擬合離散數據點列所形成的近似曲線

圖6 例2:不同初始控制點的四點插值細分曲線擬合離散數據點列所形成的近似曲線

圖7 例3:不同初始控制點的四點插值細分曲線擬合離散數據點列所形成的近似曲線

初始控制點依次遞增10個,三個實例對應的曲線擬合誤差如表3所示,其中N0表示每個實例首次擬合的初始控制點個數,即在實例1中,N0=70,而在實例2、3中,N0=40,在此基礎上,每次擬合的初始控制點依次遞增10個,但對應的擬合誤差都逐漸減少。

表3 依次遞增10個初始控制點時,不同實例的擬合誤差

當處理數據點集時,該算法可以充分利用細分法的特性,以少量的初始控制點得到數據點列中任意多個有效的近似數據點,進行數據分析。例如上文的第1個例子,算法將70個初始控制點細分1次、2次,直至多次,分別得到140個數據點、280個數據點、擬合所有離散數據點列的曲線。這樣可以在不同的研究目的下,選擇不同個數的數據集,減少研究的工作量,提高工作效率。另外,在存儲數據點列時,只需存儲少量的初始控制點,即可得到與原數據點列誤差較小的近似數據點列,節約數據點列的存儲空間。

4 結束語

本文提出一種用四點插值細分曲線擬合離散點列的算法。該算法適用于擬合散亂數據點集,與三次均勻B樣條曲線的擬合算法相比,在一定的擬合誤差下,可以有效減少擬合曲線的初始控制點的個數。在實際應用中,利用該算法可以有效地對曲線模型的數據點列進行簡化,提高工作效率。另外,該算法運用于多分辨率分析時,可以得到由任意個數點構成的擬合曲線。下一步將該算法推廣到曲面的情況。