有理Bézier曲線降階綜述

蔣 莉

（湖南農(nóng)業(yè)大學(xué) 理學(xué)院，湖南 長(zhǎng)沙 410128）

有理Bézier曲線降階綜述

蔣 莉

（湖南農(nóng)業(yè)大學(xué) 理學(xué)院，湖南 長(zhǎng)沙 410128）

有理Bézier曲線的降階是樣條曲線和曲面造型中的關(guān)鍵技術(shù)之一，為了實(shí)現(xiàn)不同CAD系統(tǒng)之間的數(shù)據(jù)交換，都要用到這一技術(shù)，因此它已經(jīng)成為該領(lǐng)域的熱點(diǎn)問(wèn)題.本文結(jié)合作者在該領(lǐng)域的研究成果，綜述了近年來(lái)國(guó)內(nèi)外專家學(xué)者關(guān)于有理Bezier曲線的降階逼近研究的方法、理論成果及實(shí)際應(yīng)用情況，對(duì)各種不同的方法進(jìn)行了分析比較.

有理Bézier曲線；NURBS曲線；齊次坐標(biāo)；權(quán)因子；降階逼近

1 引言

有理Bézier曲線的降階逼近問(wèn)題是指對(duì)于給定的一條n階的有理Bézier曲線，要求我們找到一條m(m＜n)階的有理Bézier曲線，使其與原曲線的逼近誤差達(dá)到最小.它經(jīng)常應(yīng)用于計(jì)算機(jī)輔助幾何設(shè)計(jì)的很多方面.比如數(shù)據(jù)交換，高次曲線曲面的降階處理，曲線曲面的光順性研究等.對(duì)于這個(gè)問(wèn)題，近年來(lái)許多學(xué)者都進(jìn)行了很多研究，提出了一些方法，產(chǎn)生了一些研究成果.覃廉和關(guān)履泰[2]提出了基于最優(yōu)化理論和方法的有理Bézier曲線降階方法，還將此方法用于NURBS樣條曲線曲面的降階，即將曲線曲面降多階問(wèn)題轉(zhuǎn)化為一個(gè)二次規(guī)劃問(wèn)題來(lái)求解.郭清偉，宋穎祥[3]提出了基于廣義逆矩陣的有理Bézier曲線一次降多階逼近的方法.成敏[4]在2003年提出了一種NURBS曲線降階逼近新算法，該方法利用了已有的NURBs曲線的顯式矩陣表示和具有最佳一致逼近性質(zhì)的chebyshev多項(xiàng)式.周聯(lián)提出了基于權(quán)因子優(yōu)化的有理Bézier曲線約束降多階，利用M?bius變換，即重新參數(shù)化的方法得到含參數(shù)的新的權(quán)因子.給出一個(gè)方差最小化的目標(biāo)函數(shù)，求解得到參數(shù)的值，從而給出了優(yōu)化的權(quán)因子.由于有理Bézier曲線降階不僅在曲線曲面造型而且在CAD/CAM系統(tǒng)中都有重要的應(yīng)用，本文總結(jié)了幾種經(jīng)典的有理Bézier曲線降階逼近方法，并分析了各種方法的優(yōu)缺點(diǎn).

2 幾種有理Bézier曲線的降階方法

我們首先描述有理Bézier曲線的降階逼近問(wèn)題.給定一條n次有理Bézier曲線：

所謂在L2范數(shù)下，曲線P(t)作n-m(n＞m)階降階逼近，指去尋找一組控制頂點(diǎn)q0,q1,…,qm及相應(yīng)的權(quán)因子γ0,γ1,…,γm，由其確定的m次有理Bézier曲線

滿足條件||P(t)-Q(t)||L2為最小值，

曲線P(t),Q(t)在齊次坐標(biāo)下的曲線分別是指

針對(duì)上述問(wèn)題已有如下求解方法.

2.1 將有理Bézier曲線降多階問(wèn)題轉(zhuǎn)化為二次規(guī)劃問(wèn)題的求解方法

為了解決有理Bézier曲線降階的非線性規(guī)劃問(wèn)題的遺傳算法[5]非常費(fèi)時(shí)的問(wèn)題，覃廉和關(guān)履泰將有理Bezier曲線曲面和NURBS曲線曲面放到齊次坐標(biāo)空間中來(lái)討論[2]，即考慮r次NURBS曲線

其中Nj,r(t)是B樣條基函數(shù).利用齊次坐標(biāo)系，先將f(t)表示成齊次坐標(biāo)形式然后用 k(k＜r)次 B 樣條曲線逼近它.利用齊次坐標(biāo)，作者將有理Bezier曲線曲面和NURBS曲線曲面的降階問(wèn)題轉(zhuǎn)化為如下二次規(guī)劃問(wèn)題：

2.2 基于廣義逆矩陣的有理Bézier曲線降多階逼近方法[3]

郭清偉，宋穎祥提出了基于廣義逆矩陣的有理Bézier曲線的降多階逼近方法[3]，該方法完全類似于基于廣義逆矩陣的多項(xiàng)式Bézier曲線的降階逼近的方法，利用了齊次坐標(biāo)表示，且分別考慮了不保端點(diǎn)插值和保端點(diǎn)高階插值條件兩種情形.假設(shè)有一條n次有理Bézier曲線P(t)（見（1））和一條m次有理Bézier曲線Q(t)（見（2）），且Q(t)是P(t)的降階逼近曲線.利用齊次坐標(biāo)作者首先把P(t)和Q(t)分別表示成齊次坐標(biāo)形式應(yīng)用多項(xiàng)式Bézier曲線的升階公式n-m次，即逐次將Sm(t)升高，每次升高1階，直到升高到n次，可得

其中S*是升階前的控制頂點(diǎn)，R*是升階后的控制頂點(diǎn)，An是n階升為n+1階的升階矩陣，其它Ai類似.將上式簡(jiǎn)記為：

其中 A=An-An-1…Am+1Am.由于此關(guān)系式中的 A(n+1)×(m+1)并非可逆矩陣，但是是一個(gè)列滿秩矩陣，故利用廣義逆矩陣來(lái)求解得：

上式是不保端點(diǎn)插值下的一次降n-m階后的有理m

考慮保端點(diǎn)高階插值的降階逼近時(shí)，即要求在首末端點(diǎn)處(r,s)(r+s+1＜m+n)階插值的一次降n-m(n-m≥2)階，實(shí)際上作者是在控制頂點(diǎn)處增加如下條件：

來(lái)求得，其中A1和A3分別是A的前面r+1列和后面s+1列，由此解得

分析和評(píng)價(jià)：優(yōu)點(diǎn)是利用升階的反過(guò)程，但因?yàn)槠渚仃嚥⒎欠疥?，沒有逆，故而利用廣義逆矩陣，原理比較清晰易懂.給出了顯示表達(dá)式.存在的問(wèn)題是采用的是齊次坐標(biāo)，即在齊次坐標(biāo)下利用升階的逆過(guò)程來(lái)求解得到降階曲線，但是在仿射坐標(biāo)系下有本質(zhì)上的不同，所得到的降階曲線完全不是嚴(yán)格意義上的升階的逆.因此也并沒有給出降階后誤差函數(shù)的界的估計(jì)，逼近的效果如何不明顯.

2.3 基于權(quán)因子優(yōu)化的有理Bézier曲線的約束降階

周聯(lián)首先利用齊次坐標(biāo)變換和蔡宏杰的結(jié)論[6]，得到保端點(diǎn)高階插值的降多階的頂點(diǎn)的顯式變換公式.

其中Q0,Q1,…,Qm和P0,P1,…,Pn分別是降階前后的控制頂點(diǎn)，變換矩陣M要經(jīng)過(guò)計(jì)算給出.顯然，他給出了一個(gè)顯式的變換公式.接著推導(dǎo)了一個(gè)誤差上界函數(shù)的公式：

周聯(lián)在文獻(xiàn)[7]中證明了，縮小原曲線權(quán)因子之間的比值可以減少降階誤差；而且，利用文獻(xiàn)[7]的一種重新參數(shù)化的技術(shù)，也就是利用M?bius參數(shù)變換只改變權(quán)因子但不改變控制頂點(diǎn)的性質(zhì)重新參數(shù)化原曲線，得到新的含參數(shù)χ的權(quán)因子；利用權(quán)因子方差最小化建立關(guān)于參數(shù)χ的一個(gè)目標(biāo)函數(shù)，它是一個(gè)二次函數(shù)，解此最優(yōu)化問(wèn)題求出這個(gè)合適的參數(shù)χ的值.從而實(shí)現(xiàn)了原曲線權(quán)因子之間的比值縮小的目的.又作者研究出在有些情況下，利用上述方法求出的結(jié)果中可能會(huì)出現(xiàn)負(fù)權(quán)因子，所以作者在此目標(biāo)函數(shù)上增加了一個(gè)不等式約束，以保證降階曲線的權(quán)因子為正.

分析和評(píng)價(jià)：該文章的優(yōu)點(diǎn)是首先利用了已有的一個(gè)Bézier曲線的顯式降階算法，該算法在兩端點(diǎn)處保任意階連續(xù)，利用的是齊次坐標(biāo)，原理比較清晰易懂.且給出了顯示表達(dá)式.然后證明了一個(gè)定理，即縮小最大和最小權(quán)因子間的比值就能減少誤差.利用此定理和M?bius變換，即重新參數(shù)化的方法得到含參數(shù)的新的權(quán)因子，這是因?yàn)镸?bius變換中有一個(gè)自由參數(shù)，就利用這個(gè)自由參數(shù)建立了一個(gè)目標(biāo)函數(shù)，使得方差最小化，從而優(yōu)化最大權(quán)因子和最小權(quán)因子之間的比值，得到最優(yōu)參數(shù)的值.文章還給出了降階誤差函數(shù)的上界的一個(gè)表達(dá)式，對(duì)誤差進(jìn)行了一定的分析和討論.但是并沒有討論其他參數(shù)化方法.

2.4 基于NURBS曲線顯式矩陣表示和Chebyshev逼近理論的NURBS曲線降階逼近[4]

在齊次坐標(biāo)空間中，成敏利用規(guī)范化參數(shù)變換將NURBS曲線在非空區(qū)間中的一段轉(zhuǎn)換成冪基形式[4].即考慮相應(yīng)于節(jié)點(diǎn)向量T的k階(k-1次)NURBS曲線：

先轉(zhuǎn)換成冪基形式

其中系數(shù)矩陣Ar,k,T的求解是NURBS曲線表示為冪基形式的一個(gè)關(guān)鍵問(wèn)題.利用廣義差商和Marsden恒等式可以求出系數(shù)矩陣的兩種顯示形式.其次，根據(jù)可退化即可降一階的充分必要條件這是一個(gè)線性方程組）求出rr-k+1，rr-k+2，…,rr的值.由此推出降階曲線的表達(dá)式為

又利用Chebyshev基與Bernsetin基的轉(zhuǎn)換公式推出Chebyshev多項(xiàng)式基Tn(x)=cos(narccosx)與冪基Mn=(1,u,…,un)的線性轉(zhuǎn)換矩陣：

從而將NURBS曲線轉(zhuǎn)化成Chebyshev多項(xiàng)式形式：

根據(jù)已知的Chebyshev多項(xiàng)式的最佳一致逼近性質(zhì)，得到k-1次曲線最佳一致逼近降階多項(xiàng)式，即如下k-2次曲線：

它的特點(diǎn)是系數(shù)完全相同，只是減少了一項(xiàng).

最后再利用前面的公式將它化回NURBS形式：

用這種方法一次降多階就相當(dāng)于逐次應(yīng)用降一階的方法來(lái)降階.算法給出了NURBS降階逼近曲線的顯式表達(dá)式，且不需要解方程組，每次降階都只需要減少一項(xiàng)就可以了.降多階時(shí)就重復(fù)其步驟，等價(jià)于取曲線在Chebyshev級(jí)數(shù)表示下的部分和，快速高效，方法獨(dú)特，計(jì)算方便，并且避免了累積誤差.類似地利用了它的近似最佳一致逼近性質(zhì)作者得到了低次的Chebyshev多項(xiàng)式.算法對(duì)單區(qū)間上的NURBS曲線段有較好的降階效果，然而對(duì)于整條曲線的降階，作者首先分段處理，然后再對(duì)不同段上相同位置的控制點(diǎn)和權(quán)因子進(jìn)行平均，從而得出整條曲線的近似最優(yōu)降階逼近曲線.顯然，該方法得到的曲線不一定是整條曲線的最優(yōu)降階逼近曲線.

2.5 其他有理Bézier曲線的降階方法

Sederberg和常庚哲在1993年給出了有理平面Bézier曲線的一種降階方法，利用的是最佳線性公因子，該方法是對(duì)沒有公因子的多項(xiàng)式組{x(t),y(t),w(t),a≤t≤b}進(jìn)行一個(gè)微小攝動(dòng){Xx(t),Xy(t),Xw(t)}，使得擾動(dòng)后的{x(t)+Xx(t),y(t)+Xy(t),w(t)+Xw(t)}具有有公因子t-T，將問(wèn)題轉(zhuǎn)化為多變量的管道問(wèn)題，然后結(jié)合Chebyshev多項(xiàng)式進(jìn)行求解，接著求出有理降階逼近曲線.但是此方法沒有實(shí)現(xiàn)在端點(diǎn)處插值.利用移位的Chebyshev多項(xiàng)式，陳發(fā)來(lái)進(jìn)行了保端點(diǎn)的攝動(dòng)，給出了保端點(diǎn)插值的有理曲線降階逼近方法.康寶生、石茂則把有理曲線的降階問(wèn)題轉(zhuǎn)化為求解最優(yōu)化問(wèn)題，結(jié)合仿生學(xué)和遺傳算法來(lái)實(shí)現(xiàn)保端點(diǎn)插值的多次降階.但是沒有顯式解，且計(jì)算繁瑣.

3 結(jié)論

鑒于它的實(shí)際應(yīng)用背景，有理平面Bézier曲線的降階問(wèn)題已經(jīng)成為了研究熱點(diǎn)，且已經(jīng)取得了一些研究成果.但這些方法各有弊端，有的可以得到好的降階效果，有的效果卻不明顯.本文小結(jié)了已有的國(guó)內(nèi)外幾乎所有的方法，為將方法推廣到B樣條曲面和NURBS曲線曲面降階提供了思路，其中的問(wèn)題也很多，如齊次坐標(biāo)下逼近誤差與非齊次誤差之間的關(guān)系研究成果還比較少，需要更進(jìn)一步地研究.

〔1〕張銳，張彩明.B樣條曲線曲面降階綜述[J].工程圖學(xué)學(xué)報(bào)，2009(2):1-8.

〔2〕覃廉，關(guān)履泰.有理曲線曲面的降階逼近[J].中國(guó)圖像圖形學(xué)報(bào)，2006，11(8):1062-1067.

〔3〕郭清偉，宋穎祥.基于廣義逆矩陣的有理Bézier曲線降多階逼近[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005，28(7):824-828.

〔4〕成敏.基于顯式矩陣表示和多項(xiàng)式逼近論的NURBS曲線降多階[J].中國(guó)科學(xué)（E 輯），2003，33(8):673-681.

〔5〕康寶生，石茂，張景嶠.有理 Bézier曲線的降階[J].軟件學(xué)報(bào)，2004，15(10):1522-1527.

〔6〕Cai hong-jie WANG-Guo-jin-(Institute-of-Computer-Images-and-Graphics，-State-Key-Laboratory-of-CAD-&-CG，-Zhejiang-University，-Hangzhou-310027，-China).Constrained multi-degree reduction of rational Bézier curves using reparameterization[J].Journal of Zhejiang University(Science A:An International Applied Physics&Engineering Journal)， 2007，8(10):1650-1656.

〔7〕周聯(lián).用重新參數(shù)化技術(shù)改進(jìn)有理參數(shù)曲線曲面的導(dǎo)矢界[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22(7):1104-1109.

O241.5；TP391

A

1673-260X（2017）12-0001-03

2017-09-22

本文系15年湖南省教育廳科學(xué)研究項(xiàng)目“項(xiàng)目名稱:有理Bézier曲線曲面的降階逼近算法及誤差分析”(項(xiàng)目編號(hào)：15C0656）