基于速率變化的最優參數化

陳 軍， 周 聯

(1.寧波工程學院理學院, 浙江 寧波 315211；2.上海海事大學文理學院, 上海 201306)

Chen Jun1, Zhou Lian2

(1.Faculty of Science, Ningbo University of Technology, Ningbo Zhejiang 315211, China;2.Liberal Arts & Sciences College, Shanghai Maritime University, Shanghai 201306, China)

參數曲線在CAD/CAM的各項應用中，往往需要取其參數為弧長參數。這是由于弧長參數能夠使得在參數域內均勻分布的點對應曲線上均勻分布的點，即參數的速率保持勻速不變。這種直觀的幾何意義和良好的幾何性質，使其在模具加工的實時插補算法、曲線求交以及幾何外形分析等研究中占有重要的地位。

但是，文獻[1]指出除了直線以外，多項式/有理形式的參數曲線其參數不可能為弧長參數。為此，文獻[2]利用M?bius變換，通過對曲線速率和單位速率之間的L2范數進行最小化操作，得到了Bézier曲線的“最優參數化”。 這種方法不僅有嚴謹的數學理論支持，而且能夠事先直接提供用于優化的顯式表達式而無需實時計算，可以較好地應用于實際。在此基礎上，一系列改進和推廣最優參數化的工作不斷出現：文獻[3]極大地簡化了最優參數化的中間步驟，得到了與文獻[2]相同的結果；文獻[4]在進行M?bius變換前事先對參數域進行分段，取得良好的效果；文獻[5]給出了一種不同于M?bius變換的的分式變化，使得計算過程更簡單；文獻[6]利用遺傳算法，使參數速率偏離單位速率的最大值達到最小；文獻[7-8]利用積分公式得到了用于最優參數化有理二次Bézier曲線的精確解析解；文獻[9]分別從代數和幾何兩個角度得到了一次復有理Bézier曲線的最優參數化；文獻[10]則把最優參數化從參數曲線推廣到了平面二次曲線。

1 最優參數化

設P(t)(t∈[0,1])是一條n階Bézier曲線，對其參數t進行M?bius變換：

能使P(tα(u))的表達式為一條有理Bézier曲線，其控制頂點與P(t)相同，而權因子為顯然，M?bius變換并不改變曲線P(t)的外形，僅僅改變其參數分布而已。

文獻[2]利用定積分：來衡量當前參數與弧長參數的差距，J越小則表示其越接近于弧長參數。那么，最優參數化即為尋找一個α∈(0,1)，使得達到最小。

與以往的研究不同，本文用下述定積分：來取代式(1)。對比式(1)與式(2)：式(1)描述的是曲線的速率大小，而式(2)描述的是曲線速率變化率的大小，因此將式(2)中的定積分I稱為速率變化量。當曲線取弧長參數時，其參數速率為恒值，此時速率變化量I能夠取到最小值I=0。因此，速率變化量I也能夠合理地衡量當前參數的優劣：I越小，則參數速率越接近于均勻速率。

為此，需要尋找一個變換，使得變換后的曲線表達式其速率變化量I達到最小。但是，如果仍沿用M?bius變換，速率變化量I的計算將十分復雜。受文獻[4]的啟發，對參數域進行分段，用分段線性變換來代替M?bius變換，從而把分段節點作為自由度，使得經過分段線性變換后的曲線表達式其速率變化量I達到最小。此時，與以往的最優參數化不同，新生成的曲線表達式不再是有理Bézier曲線，而是一系列多項式Bézier曲線。

2 問題的描述

那么，基于速率變化量I的最優參數化問題為：給定一條n階Bézier曲線P(t)以及一組滿足0=t0＜t1＜…＜tN-1＜tN=1的點列，求滿足0=u＜u＜…＜u＜u=1的點列，使得

01N-1N P(t)經過如式(3)的分段線性變換t(u)后，下述定積分達到最小：

根據式(3)～(4)，可得：

那么，對式(5)作進一步化簡，有：

這里，

若要使得I取到最小，需要滿足：

上述N-1個方程雖然不是線性方程，但是經過計算，Δui可以由Δu0簡單表達：

4 數值實例

圖1～3對3條曲線進行了基于速率變化的最優參數化。為方便起見，其用于分段的節點取均勻節點圖中還給出了由文獻[2]得到的參數速率。通過觀察可得，兩者在不同的區域其速率各有優劣，但本文的方法使得曲線較少出現部分區域速率過大的情況。表1給出了在節點數N取不同的值時，相應的速率變化量IN的值。我們發現，文獻[2]的最優參數化在本文的標準下并不總能改善曲線的速率。顯然，隨著節點數N的增大，用于最優參數化的自由度將增加，相應的速率變化量IN的值將減小。根據經驗，一般取N=7即可得到滿意的效果。需要注意的是，雖然在最優參數化后，曲線的速率不連續，但是曲線本身形狀并不發生改變。

圖1 曲線1及其重新參數化后的曲線速率

圖2 曲線2及其重新參數化后的曲線速率

圖3 曲線3及其重新參數化后的曲線速率

表1 節點數增加時速率變化量IN(N=3,5,7)的變化趨勢

5 結 論

本文用分段線性變換代替M?bius變換，把分段節點作為自由度，對曲線進行最優參數化。同時，對參數優劣的衡量標準進行了改進，使最優參數化后的曲線速率其變化率達到最小。特別地，本文采用的分段線性變換使得最優參數化后的曲線仍為Bézier曲線，這有助于對于曲線的進一步分析。最后給出的數值實例驗證了算法的有效性。近年來，陸續有一些研究成果把最優參數化從曲線拓展到曲面上[11-13]，取得了良好的效果。如何把本文的衡量標準相應地推廣到Bézier曲面上，將是我們進一步研究的內容。

[1]Farouki R T, Sakkalis T.Real rational curves are not‘unit speed’ [J].Computer Aided Geometric Design,1991, 8(2): 151-157.

[2]Farouki R T.Optimal parameterizations [J].Computer Aided Geometric Design, 1997, 14(2): 153-168.

[3]Jüttler B.A vegetarian approach to optimal parameterizations [J].Computer Aided Geometric Design, 1997, 14(9): 887-890.

[4]Costantini P, Farouki R T, Manni C, Sestini, A.Computation of optimal composite re-parameterizations [J].Computer Aided Geometric Design, 2001, 18(9): 875-897.

[5]郭鳳華, 楊興強.C-Bézier曲線的一種重新參數化新方法[J].工程圖學學報, 2006, 27(2): 108-111.

[6]郭鳳華.參數曲線的最優參數化[J].計算機輔助設計與圖形學學報, 2007, 19(4): 464-467.

[7]陳 軍, 王國瑾.2 次有理Bézier曲線的最優參數化[J].計算機研究與發展, 2008, 45(9): 1601-1604.

[8]Cattiaux-Huillard I, Albrecht G, Hernández-Mederos V.Optimal parameterization of rational quadratic curves [J].Computer Aided Geometric Design, 2009,26(7): 725-732.

[9]黃偉賢, 王國瑾.一次復有理Bézier曲線的最優參數化[J].計算機輔助設計與圖形學學報, 2010, 22(11):1972-1977.

[10]厲玉蓉, 胡芳剛.平面二次代數曲線的最優參數化[J].圖學學報, 2012, 33(2): 49-52.

[11]Yang Yijun, Yong Junhai, Zhang Hui, Paul J C, Sun Jiaguang.Optimal parameterizations of Bézier surfaces [C]//Bebis G, et al.ISCV 2006, LNCS 4291.Berlin Heidelberg: Springer-Verlag, 2006: 672-681.

[12]Li Yufei, Wang Wenping, Tu Changhe.Optimal sampling of parametric surfaces [J].Computer-Aided Design & Applications, 2012, 9(1): 55-60.

[13]Yang Yijun, Zeng Wei, Yang Chenglei, Deng Bailin,Meng Xiangxu.Sitharama Iyengarc.An algorithm to improve parameterizations of rational Bézier surfaces using rational bilinear reparameterization [J].Computer-Aided Design, 2013, 45(3): 628-638.