基于速率變化的最優(yōu)參數(shù)化

陳 軍， 周 聯(lián)

(1.寧波工程學(xué)院理學(xué)院, 浙江 寧波 315211；2.上海海事大學(xué)文理學(xué)院, 上海 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)

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

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

1 最優(yōu)參數(shù)化

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

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

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

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

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

2 問題的描述

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

01N-1N P(t)經(jīng)過如式(3)的分段線性變換t(u)后，下述定積分達(dá)到最?。?/p>

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

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

這里，

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

上述N-1個(gè)方程雖然不是線性方程，但是經(jīng)過計(jì)算，Δui可以由Δu0簡單表達(dá)：

4 數(shù)值實(shí)例

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

圖1 曲線1及其重新參數(shù)化后的曲線速率

圖2 曲線2及其重新參數(shù)化后的曲線速率

圖3 曲線3及其重新參數(shù)化后的曲線速率

表1 節(jié)點(diǎn)數(shù)增加時(shí)速率變化量IN(N=3,5,7)的變化趨勢

5 結(jié) 論

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

[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]郭鳳華, 楊興強(qiáng).C-Bézier曲線的一種重新參數(shù)化新方法[J].工程圖學(xué)學(xué)報(bào), 2006, 27(2): 108-111.

[6]郭鳳華.參數(shù)曲線的最優(yōu)參數(shù)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2007, 19(4): 464-467.

[7]陳 軍, 王國瑾.2 次有理Bézier曲線的最優(yōu)參數(shù)化[J].計(jì)算機(jī)研究與發(fā)展, 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]黃偉賢, 王國瑾.一次復(fù)有理Bézier曲線的最優(yōu)參數(shù)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2010, 22(11):1972-1977.

[10]厲玉蓉, 胡芳剛.平面二次代數(shù)曲線的最優(yōu)參數(shù)化[J].圖學(xué)學(xué)報(bào), 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.