一種基于切向估計的低誤差B樣條插值方法

胡家豪,陳小雕

(杭州電子科技大學計算機學院,浙江 杭州 310018)

0 引 言

曲線插值問題是計算機輔助幾何設計和計算機圖形學中的基本問題之一。大多數方法先計算樣條曲線對應的節點,然后再求解對應的控制點信息。均勻節點法是一種簡單的選擇,其中節點等距分布。當連續數據點之間的距離變化很大時,統一參數化方法通常會導致結果不理想。弦長法[1-3]中使用的累積弦長是累積弧長的合理近似值。向心法[4]和Foley法[5]是弦長法的兩種變體,更多的相關討論可參見參考文獻[6]。文獻[7]利用能量優化方法來確定節點,Park討論了閉合B樣條曲線的節點選擇[8]。文獻[9]在節點向量與參數化相一致的情況下通過指定曲線段相對于所在弦的高度來確定節點值,能獲得令人滿意的結果,但相對高度的獲取在工程上并不容易。文獻[10]以插值點的切向作為約束,利用二次B樣條曲線本身的幾何性質進行參數化,使曲線在每個插值點上都滿足指定的切向,可以直觀地控制插值曲線的形狀以達到預期效果。文獻[11]指出,在插值誤差方面,上述三種弦長類型方法都沒有比其他方法具有明顯優勢。與通過求解全局方程獲得二次精度的方法[12]不同,Zhang等人[12]還提出了一種局部計算方法,可以二次多項式形式再現參數曲線,并且具有二次精度。文獻[13]通過優化曲線的彎曲和拉伸能量來確定曲線的自由度,使曲線的變化盡可能小來獲得更好的曲線形狀。文獻[14]通過最小化三次多項式曲線的三次系數來確定自由度,并采用三次多項式曲線對四個相鄰點進行插值。本文使用局部插值二次曲線估計二次B樣條的節點,從而得到最終的二次B樣條插值曲線。理論上,一旦從二次曲線中采樣得到插值點,得到的插值曲線可以完全重構出原始的二次曲線,即本文方法也具有二次精度。數值算例表明,新方法可以獲得比現有方法更小的插值誤差。

1 一種基于切向估計的低誤差B樣條插值方法

1.1 插值4個平面點的二次Bézier曲線

(1)

式中,A=(x1y3-y1x3)(x1y3-x2y3-y1x3+y2x3),B=(x1y3-y1x3)(y1x2-x1y2),C=(x1y2-y1x2)(x1y2-y2x3-y1x2+x2y3),那么剩下的ta、ai和bi可以表示為

(2)

式中,i=0,1,2,3和j=0,1,2,“×”表示兩個平面向量之間的叉積。

1.2 插值三個平面點和一個切向的二次Bézier曲線

P0=q0,P2=q2,P1=(α0s0,α0t0)

1.3 估計閉曲線情形下插值點的切向

(3)

(4)

認知靈活性指順應改變的情境而轉換到另一種思維或行為，以符合新情境的需要的能力反映思維和行為的適應能力。Ajilore等[24]研究發現，雙相障礙Ⅰ型穩定期患者(n=22)認知靈活性與健康對照人群(n=20)比較差異無統計學意義。劉傳朋[25]研究顯示青少年雙相抑郁患者無論是在急性期還是緩解期均存在認知靈活性等方面的缺陷。

α=1-tb,1β=tb,2-ta,2

(5)

α=tb,3-ta,3β=ta,4。

(6)

圖1 切向估計的示例

1.4 估計開曲線情形下插值點的切向

兩個切向量Tn-2和Tn-1可以用相同的方式估計。

1.5 構造二次B樣條插值曲線

1.6 時間復雜度討論

第一,給定n個插值點處的切向估計可以在線性時間內完成。首先,求解一條二次Bézier插值曲線的過程與輸入的插值點數n無關,可在常數時間內完成。然后,計算一條Bézier曲線在一點處的切向,也可以在常數時間內完成。從而,在某插值點處的切向估計可以在常數時間0(1)內完成。因此,所有插值點的切向估計可在0(n)時間內完成。

第二,得到插值點處的切向后,利用unclamping技術[15]來轉換為對應的B樣條形式的過程可在線性時間內完成。對于二次B樣條的unclamping,每增加一個點,對應的轉換過程可在常數時間內完成[15]。因此,采用增量式的方式,一個點一個點地增加,完成所有插值點的轉換過程,可以在0(n)時間內完成。

綜上兩點所述,求解插值二次B樣條的整個過程可以在線性時間內完成。

2 實例分析

為了評估算法性能,使用參考文獻[13]中的兩個測試實例,并與文獻[1-3]、文獻[4]、文獻[5]、文獻[13]中的方法進行比較。

其中n=10,20,…,100。令Gn(t)為對應于n的二次B樣條曲線。最大絕對誤差表示給定曲線F(ξ)和插值曲線Gn(t)之間的單邊Hausdorff距離,定義為

圖2 橢圓和30個插值點

表1列出了不同方法的最大誤差。表1中,對于n=10的情況,最好的結果3.6e-3來自向心法[4]。對于n=40的情況,最好的結果2.0e-5來自張的方法[13],與新方法2.1e-5的結果非常接近。新方法在其他情況下最大誤差最小,明顯優于其它方法。

表1 例1中,不同算法的最大絕對誤差比較

例2如圖3所示的8次Bézier曲線,其控制點為{(0,0),(19,24),(39,43),(58,37),(78,0),(98,50),(141,81),(164,64),(188,0)}。為了防止在端點q1和qn附近出現較大的誤差,還給出了q1和qn處的切向。在前面的五種方法中,在兩個端點處引入的方向切線約束會導致產生三次樣條。在這種情況下,新方法中得到的曲線仍然是二次B樣條曲線。插值誤差如表2所示,當n=20時,新方法的結果為4.5e-3,與張方法[13]的最佳結果4.3e-3非常接近,也遠優于三種弦長類型方法[1-3]。對于n≠20的情況,新方法的最大誤差始終優于其他五種方法?？梢灶A期,一旦在新方法中使用三次B樣條代替二次B樣條,相應的插值誤差可以得到進一步改善。

圖3 8次Bézier曲線和30個插值點

表2 例2中,不同算法的最大絕對誤差的比較

圖4 誤差曲線

3 結束語

本文提出一種基于切向估計的二次B樣條插值方法,具有二次精度和較小的逼近誤差。未來的研究工作,仍然有較大的改進空間。比如,使用三次或更高次數的B樣條曲線作為插值曲線,如何進一步優化節點的選擇,仍需要進一步研究。相關的思路,如何推廣到B樣條曲面插值問題中,也將是未來考慮的研究工作之一。