Bezier曲線約束降多階的算法分析與比較(

1、Bézier曲線約束降多階的算法分析與比較收稿日期: 2006-*基金項目：國家自然科學(xué)基金項目(No. 60673031 , 60333010), 國家重點基礎(chǔ)研究發(fā)展規(guī)劃973項目(2004CB719400).作者簡介：王國瑾(1944-),男, 浙江紹興人, 教授, 主要從事計算機輔助幾何設(shè)計、計算機圖形學(xué)研究. E-mail: wanggj.王國瑾P 1,2P 喻春明1,2 (1浙江大學(xué)計算機圖像圖形研究所 2浙江大學(xué)CAD&CG國家重點實驗室 浙江 杭州 310027)摘 要： 為了產(chǎn)品外形數(shù)據(jù)的壓縮與傳遞得以順利進(jìn)行,急需開發(fā)參數(shù)曲線降階這一項關(guān)鍵技術(shù),特別是構(gòu)造

2、L2范數(shù)下Bézier曲線帶高階端點插值條件的降多階算法,并分析各類算法的每個優(yōu)缺點.這是當(dāng)前計算機輔助設(shè)計(CAD)領(lǐng)域的熱門課題之一.基于工程的應(yīng)用需要,對國際CAD期刊近年來發(fā)表的此課題中最有代表性的4種算法,從理論機理、誤差預(yù)測、表達(dá)形式、逼近精度、機時消耗這5個方面,作了系統(tǒng)的剖析與對比,并用大量實例對算法效果進(jìn)行比較,指明了各種算法的優(yōu)缺點,找到了一種最優(yōu)的算法,從而為外形設(shè)計及圖形顯示系統(tǒng)的研制提供了富有參考價值的意見.關(guān)鍵詞： 算法比較；Bézier曲線；降多階；端點約束；L2范數(shù)中圖法分類號： TP391 文獻(xiàn)標(biāo)識碼：AAnalyse and compar

3、ison for some algorithms of multi-degree reduction with constrained Bézier curvesWANG Guo-jin1,2, YU Chun-ming1,21(Computer Institute of Images and Graphics, Zhejiang University, Hangzhou 310027, China) 2(State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou 310027, China)Abstract:

4、In order to actualize the compression and communication of product model data successfully, it is urgently required to develop a key technique, the reduction of parameter curve, especially to construct an algorithm for multi-degree reduction of Bézier curves with constraints of endpoints contin

5、uity of high degree in L2-norm, and to analyze every strongpoint and shortcoming of all kinds of algorithms. This is one of the popular project in the field of Computer Aided Design (CAD) at present. Based on the request of application of engineering to practice, four typical algorithms, published i

6、n the international CAD journals these years, are roundly analyzed and compared according to their theoretical mechanism, error forecast, expression form, approximation accuracy and computing time. Also numerical tests are made to validate and compare the arithmetic effect by using many samples. The

7、n the merits and weaknesses of the above various methods are indicated, and an optimal algorithm is found. Thus the valuable suggestions to the development of shape design and graphics display systems are provided.Key words: Algorithm comparison; Bézier curve; multi-degree reduction; constraint

8、s of endpoints; L2-norm參數(shù)曲線的降階技術(shù),應(yīng)用于外形設(shè)計系統(tǒng)中對數(shù)據(jù)的壓縮、交換和傳遞1,2,是當(dāng)前計算機輔助設(shè)計領(lǐng)域的熱點課題之一.在眾多降階算法中,L2范數(shù)下Bézier曲線約束降多階的算法相當(dāng)?shù)湫投鴮嵱?,4,占有重要的一席之地,因而倍受人們關(guān)注.這一研究的進(jìn)程,大致上可按其技術(shù)指標(biāo)劃分為2002年前、后兩個階段.在2002年以前, 各種算法不能同時實現(xiàn)曲線端點高階插值與降多階；文獻(xiàn)5沖破了這種局限,使得兩者同時實現(xiàn),開啟了第2研究階段.值得注意的是：2002年以來,圍繞這一專題,國際上的專業(yè)或綜合期刊恰好每年都發(fā)表一篇代表性論文5-85方面作了系統(tǒng)的梳

9、理與比較,旨在揭示其原始思想,評介其長處短處,并用大量實例進(jìn)行驗證,希望為外形設(shè)計系統(tǒng)的降階運算提供富有參考價值的意見.為便于比較,本文把這4篇論文中有關(guān)算法與公式的形式在保持原意的前提之下作了較多改寫,并把各種幾何參數(shù)用統(tǒng)一的符號加以表達(dá)；4篇論文的算法分別簡記為算法15,算法26,算法37以及算法48.1 符號與定義定義1. 假設(shè), 是次Bernstein基, 若對次 Bézier曲線, , 存在次Bézier 曲線,使得兩者按某一范數(shù)意義的距離達(dá)到最小,且滿足則稱這種降階為在該范數(shù)意義下帶次端點插值條件的Bézier曲線降階. 定義2. 在L2范數(shù)意義下,曲

10、線相對于曲線的逼近誤差定義為定義3. 對一條已知的Bézier曲線,如果只有求出其相應(yīng)的降多階曲線以后,才能算出其逼近誤差,則稱該降階逼近不能進(jìn)行誤差預(yù)測,稱其誤差為事后誤差；否則,稱該降階逼近能進(jìn)行誤差預(yù)測,稱其誤差為先驗誤差.降階誤差預(yù)測對工程具有明顯價值. 若先驗誤差大于公差,可避免盲目降階,而是先對原曲線分割,再對子曲線求先驗誤差, 直到其小于公差,再施行降階.2 4種約束降多階算法的剖析2.1 算法1 5的分析 算法的新穎思想是把原曲線分解為3個獨立的部分,讓它們各司其職：其中第1和第3部分作為欲求降階曲線和式的首段與末段,次數(shù)均為次,因而將只需分別執(zhí)行保左右端點高階插值的

11、功能而不必考慮降階；中間部分的曲線在兩端點處分別有直到次的零導(dǎo)矢, 因而將只需執(zhí)行降多階逼近的功能而不必考慮保證端點約束.這樣就解決了以往降多階與端點高階插值不能兼顧的矛盾.本方法在降多階逼近中,應(yīng)用了Jacobi多項式的最佳最小平方逼近性質(zhì).先把曲線化為以為控制頂點的次Bézier曲線與的乘積,再把曲線化為,即以為控制頂點的次Jacobi曲線；應(yīng)用Jacobi多項式逼近理論,曲線的前項是對它的最佳最小平方逼近,所以這前項的倍是對曲線的最佳最小平方逼近. 剩下的問題只是將曲線的前項化回以為控制頂點的次Bézier曲線,并把曲線與的乘積化為降階曲線和式的中間段.最后綜合起來,

12、曲線就可同時實現(xiàn)端點次插值與降多階.該算法不能進(jìn)行誤差預(yù)測,事后誤差為從以上分析可看出, 該算法的優(yōu)點是分解原曲線為3個獨立的部分再應(yīng)用Jacobi多項式的逼近性質(zhì),首次解決了端點約束與降多階在實現(xiàn)過程中的矛盾；但也正因為分解所得的第1和第3部分是僅按端點約束條件決定的,被隔絕于逼近過程之外,沒有與第2部分一起作為一條完整的曲線去實行最小平方逼近,所以算法的最終逼近精度未必最佳；此外,雖然該算法的降階曲線并不以顯式表達(dá),但具有顯式表達(dá)的潛力；3年后,文獻(xiàn)9把它改進(jìn)為矩陣形式的顯式表達(dá).2.2 算法26的分析算法的基本思想是著眼于幾何逼近技術(shù), 對原曲線控制頂點作一個最小擾動來得到約束降多階曲線

13、.其理論創(chuàng)新在于作者證明的這樣一個結(jié)論：Bézier曲線在區(qū)間兩端點帶次插值條件的降多階最佳L2逼近問題,等價于按照加權(quán)的Euclidean范數(shù)去尋求其控制頂點的帶約束的最小擾動量.因此,該問題的目標(biāo)為用此待定最小擾動向量來表達(dá)的降階曲線,與原曲線的加權(quán)Euclidean距離為最小,亦即問題被歸結(jié)為求控制頂點的加權(quán)最小二乘擾動, 而條件是降階曲線升階以后其各個高次項系數(shù)為0.于是按Lagrange乘子法可求出最佳擾動量與降階曲線.時, 降階曲線控制頂點才具有顯式表示；而且這時沒有提供先驗誤差,僅求得其事后誤差函數(shù)為特別, 當(dāng)時, 此誤差函數(shù)可化簡, 從而這時有一個粗略的上界. 當(dāng)降階

14、次數(shù)大于1,即時,降階曲線的控制頂點不能用顯式表示,其擾動量須根據(jù)Lagrange乘子法, 從下列極小化問題 (為待定乘子)去求得：而則根據(jù)端點處次插值條件去求得, 且這時沒有提供先驗誤差與事后誤差.如果要得到顯式降階公式,只能逐次降階,那樣做顯然會影響逼近精度與上機時間.從以上分析可知, 該算法的優(yōu)點在于把幾何逼近與范數(shù)等價逼近相結(jié)合, 具有最佳逼近精度；略為不足之處是：除了逐次降階, 它沒有顯式表達(dá)式與誤差表達(dá)式,更沒有先驗誤差.2.3 算法37的分析算法的創(chuàng)新思想是利用兩個正交補空間的等價性,把范數(shù)意義下Bézier曲線的約束降多階問題,轉(zhuǎn)化為加權(quán)Euclidean范數(shù)意義下滿

15、足端點條件的最小二乘求解問題,最后的解借助廣義逆矩陣來表示.為了方便,下面以Bézier曲線的分量來進(jìn)行算法評述.把兩端點分別有直到次零導(dǎo)數(shù)的次多項式全體所張成的空間記為 可以證明,的子空間相對于內(nèi)積 的正交補空間等同于它相對于其Bézier縱標(biāo)之加權(quán) 的Euclidean內(nèi)積的正交補空間.利用此性質(zhì),可推得：對已給次Bernstein多項式,尋求次多項式的逼近問題無論相對于內(nèi)積, 還是相對于加權(quán)Euclidean內(nèi)積, 均有相同的極小解. 于是, 已知次Bernstein多項式的Bézier縱標(biāo) 去求約束降多階多項式的Bézier縱標(biāo)的問題, 就進(jìn)一步

16、轉(zhuǎn)化為在的條件下,按上加權(quán)Euclidean內(nèi)積的一個最小二乘求解問題, 把欲求的解分解為已知部分和未知部分,即有,則最后的解可借助于升階矩陣的廣義逆矩陣來表出.從以上分析可看出,該算法的優(yōu)點是利用范數(shù)意義的等價轉(zhuǎn)換,把約束降多階轉(zhuǎn)化為條件控制下的最小二乘問題.但它不能預(yù)測誤差,沒有給出事后誤差,也沒能證明具有最佳的逼近誤差.此外,其降階曲線并不以顯式表達(dá),只是對部分中間結(jié)果有顯式表達(dá).還須指出,文獻(xiàn)7給出的權(quán)是錯的.文獻(xiàn)10糾正了此錯誤, 把原表達(dá)式改正為：在本文第3節(jié)的實例中, 系采用糾正后的權(quán). 若用原文獻(xiàn)7的權(quán),則逼近誤差還將明顯增大.2.4 算法48的分析算法的基本思想是把原曲線與欲

17、求的降階曲線之差分解為關(guān)于權(quán)函數(shù)的次Jacobi多項式曲線與函數(shù)的乘積, 即 上式有一石四鳥之功效： 1. 它輕松地滿足了降階曲線的端點次插值；2. 它自然地誘導(dǎo)了降階逼近的先驗誤差： 再應(yīng)用Jacobi多項式在上關(guān)于權(quán)函數(shù)的正交性, 立即得到 3. 它確切地保證了降階逼近的最佳性質(zhì)：從(1)式兩端對多項式次數(shù)的比較可看出,常向量僅與已知曲線有關(guān), 而與降階曲線的選擇無關(guān). 因此, 最佳逼近必定能夠達(dá)到,其充要條件是為零； 4.它直接地實現(xiàn)了降階逼近曲線的顯式表達(dá)：利用曲線與曲線的次項系數(shù)對應(yīng)相等關(guān)系,即可求出于是由(2)可確定先驗誤差, 由(1)能得出,從而得到降階曲線的控制頂點這里是帶權(quán)J

18、acobi基向冪基的轉(zhuǎn)換矩陣,是Bernstein基與冪基的相互轉(zhuǎn)換矩陣8.從以上分析可看出,該算法的特點在于充分利用Jacobi多項式的正交性、冪基的線性無關(guān)性以及正交基與冪基的相互轉(zhuǎn)換性, 巧妙地導(dǎo)出了約束降多階的顯式表達(dá)式. 此公式非常簡單,只要用一個約束降多階變換的矩陣,去左乘原曲線的控制頂點所組成的列向量即可.尤其應(yīng)當(dāng)指出的是, 此矩陣可事先按各種參數(shù)算好, 象三角函數(shù)表那樣存儲于計算機內(nèi), 隨時準(zhǔn)備調(diào)用,這樣就大大節(jié)省了交互操作時間. 此外,該算法具有先驗誤差,逼近精度不可再改進(jìn),因而克服了以往的種種局限,具有相當(dāng)大的應(yīng)用價值.3 4種約束降多階算法的比較為了比較4種約束降多階算法

19、的逼近精度與計算速度, 我們進(jìn)行了全面的編程試驗, 用同一批曲線樣本、按同一類參數(shù)作了大量實際考核與效果對比, 并繪制了逼近曲線圖. 所有算法均采用Matlab7.0軟件,在奔騰微機上予以實現(xiàn). 表1是實驗曲線的3批已知數(shù)據(jù), 分別列出了已知曲線的次數(shù)及降階曲線的次數(shù), 左右端點約束的階數(shù)以及已知曲線的控制頂點的平面坐標(biāo).表1. 約束降多階試驗的已知曲線數(shù)據(jù)Table 1. Data of the known curve for the tests of constrained multi-degree reduction參數(shù)控制頂點坐標(biāo)控制頂點坐標(biāo)實例1139430, 0.7, 2, 3,

20、3.75, 4.5, 5, 6, 7, 6, 5, 4, 3, 40, -50, -11, -30, 12, 22, 27, 24, 0, -20, -70, -20 ,-10, 0實例254120, 0.2, 0.4, 0.6, 0.8, 10, 1, 4, 2, 5, 0實例396220, 4, 5.5, 7, 7, 8.5, 12.5, 14.5, 18.5, 18.5.0, 4, 3.4, 2.5, -4, 3, 4, 2, 3, 0圖1-3顯示的是對每批已知數(shù)據(jù)用4種不同的約束降多階算法進(jìn)行降階的結(jié)果曲線圖.其中已知曲線用細(xì)實線表示,算法1, 2, 3, 4所得降階曲線分別用五角星、

21、三角形、小圓與虛線表示.從圖中可以明顯看出,就降階逼近精度而言,算法4與算法2相同, 在這4種降階方法中為最高；算法3略為次之,而算法1則位于其后.表2顯示的是對每批已知數(shù)據(jù)用4種不同的約束降多階算法進(jìn)行降階的機時消耗值. 從表中可以明顯看出, 就機時消耗而言, 算法4在這4種降階方法中為最少, 算法2緊隨其后, 接下來為算法3, 而算法1則位于其后. 算法 4之所以計算快捷, 乃是因為它具有顯式表達(dá)公式, 而約束降多階變換的矩陣已事先按各種參數(shù)算好存儲于計算機內(nèi), 整個計算過程僅需執(zhí)行一個矩陣乘法而已.最后, 按照以上試驗結(jié)果及上節(jié)中的理論分析, 我們可以把這4種約束降多階算法的特性與功能統(tǒng)

22、一地列成表3加以比較.圖1. 實例1的計算結(jié)果Fig.1 The results of computing for Example 1圖2. 實例2的計算結(jié)果Fig.2 The results of computing for Example 2圖3. 實例3的計算結(jié)果Fig.3 The results of computing for Example 3表2. 約束降多階試驗的機時消耗對比(時間單位：秒)Table 2. Comparison between computing times for the tests of constrained multi-degree reduction

23、 s 算法1算法2算法3算法4實例10.25000.11000.15600.0470實例20.09400.04700.04700.0310實例30.20300.07800.09300.0160表3. 約束降多階算法的特性與功能比較Table 3. Comparison between characteristics and functions of the algorithms of constrained multi-degree reduction比較指標(biāo)顯式表達(dá)公式先驗/事后誤差公式逼近精度機時消耗算法1無無/有較低最多算法2無(降一次時有)無/無(降一次時有)最高較少算法3無(部分中間

24、結(jié)果有)無/無較高較多算法4有有/有最高最少所以我們能夠得出如下結(jié)論：這4種不同的約束降多階算法中,逼近效果最好的是算法4與算法2,計算時間最省的是算法4；惟一地既具有顯式降階曲線公式又具有先驗降階誤差公式的還是算法4.因此建議在幾何設(shè)計及圖形系統(tǒng)中,大力推廣與應(yīng)用算法4. 至于算法2和算法3在理論基礎(chǔ)上有類似與相通之處,它們都是受Lutterkort 等人4的工作啟發(fā)而做的研究,都把文獻(xiàn)4的降階理論成功地推廣到了曲線端點保高階插值的情況,因而大大拓廣了原技術(shù)的應(yīng)用范圍, 這是它們的獨到創(chuàng)新之處.而算法1則在首次同時實現(xiàn)曲線端點保高階插值與降多階方面功不可沒,其思想與技巧也是富有啟發(fā)性和值得借

25、鑒的.參考文獻(xiàn)(References)1 HU Shi-min, SUN Jia-guang, JIN Tong-guang, et al. Approximate degree reduction of Bézier curves J. Tsinghua Science and Technology, 1998, 3(2): 997-1000.2 胡事民. CAD系統(tǒng)數(shù)據(jù)通訊中若干問題的研究D. 杭州: 浙江大學(xué)博士學(xué)位論文, 1996年4月.HU Shi-min. Research on some problems in data communication for CAD sy

26、stems D. Hangzhou: PhD Dissertation in Zhejiang University, April 1996.3 ECK M. Least squares degree reduction J. Computer Aided Design, 1995, 27(11): 845-851.4 LUTTERKORT D, PETERS J, REIF U. Polynomial degree reduction in L2-norm equals best Euclidean approximation of Bézier coefficients J. Computer Aided Geometric Design, 1999, 16(7): 607-612. 5 CHEN G.uo-dong, WANG Guo-jin. Optimal multi-degree reduction of Bézier curves with constraints of endpoi