秦新強(qiáng)，王偉偉，胡 鋼

西安理工大學(xué) 理學(xué)院，西安 710054

基于遺傳算法的C-Bézier曲線(xiàn)降階

秦新強(qiáng)，王偉偉，胡 鋼

西安理工大學(xué) 理學(xué)院，西安 710054

Bézier曲線(xiàn)曲面是幾何造型中最常用的曲線(xiàn)曲面之一。由于不同的CAD和CAM系統(tǒng)中多項(xiàng)式最高階數(shù)的限制范圍和要求是不同的，一方面為實(shí)現(xiàn)不同階數(shù)的曲線(xiàn)曲面的數(shù)據(jù)轉(zhuǎn)換、傳遞以及系統(tǒng)中數(shù)據(jù)存儲(chǔ)量的壓縮，另一方面為了提高計(jì)算效率和穩(wěn)定性，需要對(duì)曲線(xiàn)曲面進(jìn)行降階處理。曲線(xiàn)曲面降階的主要方法有兩類(lèi)：一類(lèi)是基于控制頂點(diǎn)的幾何方法。文獻(xiàn)[1]利用升階的逆過(guò)程來(lái)求降階曲線(xiàn)的控制頂點(diǎn)；文獻(xiàn)[2-4]利用擾動(dòng)控制頂點(diǎn)和約束優(yōu)化法來(lái)實(shí)現(xiàn)Bézier曲線(xiàn)曲面降階；文獻(xiàn)[5-6]利用Bézier曲線(xiàn)本身的幾何性質(zhì)并結(jié)合廣義逆矩陣、最佳一致逼近和最小二乘理論來(lái)實(shí)現(xiàn)降階逼近。另一類(lèi)方法是基于基轉(zhuǎn)換的代數(shù)方法。文獻(xiàn)[7-8]利用Chebyshev多項(xiàng)式理論實(shí)現(xiàn)Bézier曲線(xiàn)的降階；文獻(xiàn)[9]利用約束Legendre多項(xiàng)式來(lái)進(jìn)行降階逼近；文獻(xiàn)[10]提出了一種基于受限Jacobi多項(xiàng)式的Bézier曲線(xiàn)降階算法。

C-Bézier曲線(xiàn)的應(yīng)用非常廣泛，在描述曲線(xiàn)曲面方面有重要的作用且有形狀參數(shù)供設(shè)計(jì)人員選擇。目前針對(duì)C-Bezier曲線(xiàn)，學(xué)者們已經(jīng)研究了它的形狀修改[11]、光順[12]以及拼接[13]等問(wèn)題，而C-Bezier曲線(xiàn)的降階問(wèn)題卻少有涉及。文獻(xiàn)[14]給出了基于L2范數(shù)C-Bézier曲線(xiàn)的最小平方逼近方法，同時(shí)考慮了C0和C1約束條件下的最小平方降階逼近此。方法計(jì)算較繁瑣，且涉及多項(xiàng)式方程求解問(wèn)題，精度較低。為此，本文針對(duì)C-Bézier曲線(xiàn)的近似降階問(wèn)題，基于遺傳算法的理論，提出了該曲線(xiàn)的一種近似降階算法。

1 C-Bézier曲線(xiàn)的定義

定義1 n次C-Bézier基函數(shù){u0，n(t)，u1，n(t)，…，un，n(t)}定義如下[15]：

定義2由控制多邊形{p0，p1，…，pn}確定的n次C-Bézier曲線(xiàn)為：

式中，{u0，n(t)，u1，n(t)，…，un，n(t)}為定義在空間Γn=span{1，t，…，tn-2，sint，cost}上C-Bézier基函數(shù)，α∈[0，π]為全局形狀參數(shù)。

2 基于遺傳算法的C-Bézier曲線(xiàn)降階

2.1 降階問(wèn)題的提出

滿(mǎn)足條件：

上述問(wèn)題可以轉(zhuǎn)化為如下的帶約束優(yōu)化問(wèn)題[16]：

2.2 C-Bézier曲線(xiàn)降階的基本思想

2.2.1 編碼的表示和種群的初始化

遺傳算法的一個(gè)重要步驟是對(duì)所求的問(wèn)題變量實(shí)現(xiàn)編碼，主要有二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼和浮點(diǎn)數(shù)編碼。本文采用實(shí)數(shù)編碼，因?yàn)閷?duì)于大部分實(shí)數(shù)值優(yōu)化問(wèn)題采用實(shí)數(shù)編碼比采用二進(jìn)制編碼時(shí)算法的平均效率要高。遺傳算法在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合就構(gòu)成了不同的點(diǎn)。解空間中的解數(shù)據(jù)，作為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱(chēng)為編碼。實(shí)數(shù)編碼是將個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)實(shí)數(shù)（或浮點(diǎn)數(shù)）來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其變量的個(gè)數(shù)。

本文群體是由降階后C-Bézier曲線(xiàn)控制頂點(diǎn)的可行解組成。初始化種群首先要產(chǎn)生一個(gè)隨機(jī)數(shù)αi∈[0，1]，i= 0，1，…，n-1，然后利用下式求得區(qū)間[pmin，pmax]上的控制頂點(diǎn)：

2.2.2 適應(yīng)值函數(shù)的選取

群體的每個(gè)個(gè)體都有一個(gè)適應(yīng)值，個(gè)體的性質(zhì)越優(yōu)，適應(yīng)值越大，其繁殖下一代的可能性也就越大。為了滿(mǎn)足C-Bézier曲線(xiàn)x(t)的逼近條件，所以選適應(yīng)值函數(shù)為：

式中d(xj，xj)為Euclidean距離，α為全局形狀參數(shù)，xj，(j=0，1，…，s)為降階前后C-Bézier曲線(xiàn)上的點(diǎn)。

2.2.3 選擇

選擇的目的是把優(yōu)良的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代，使得最優(yōu)個(gè)體具有較高的復(fù)制數(shù)目。常用的方法有輪盤(pán)賭選擇、隨機(jī)競(jìng)爭(zhēng)、最佳保留、無(wú)回放隨機(jī)選擇等。為了能保留搜索過(guò)程中的最優(yōu)解，本文采用常用的轉(zhuǎn)盤(pán)方法（roulette wheel selection）來(lái)進(jìn)行選擇。

2.2.4 雜交

式中，βi，γi∈[0，1]的隨機(jī)數(shù)。

2.2.5 變異

交叉只能對(duì)現(xiàn)有的基因進(jìn)行排列組合，不能產(chǎn)生新的基因。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。變異算子是對(duì)群體中染色體的某些基因值作變動(dòng)。變異可使搜索跳出局部最優(yōu)，是避免算法早熟的重要算子。這里采用一般的隨機(jī)點(diǎn)對(duì)應(yīng)法，即從[pmin，pmax]中選擇一點(diǎn)，替換子解向量中對(duì)應(yīng)位置的點(diǎn)。

2.2.6 收斂條件

遺傳算法有兩種終止條件：一種是確定遺傳的代數(shù)，它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，即已經(jīng)處理完所有代群體;另一種是當(dāng)在最后的一代與前一代相比沒(méi)有任何的改進(jìn)時(shí)，運(yùn)算中止，這也表明遺傳算法不再向好的方向優(yōu)化，即已達(dá)到需要的誤差范圍。

2.2.7 控制參數(shù)的設(shè)定

在遺傳法中，群體的大小、遺傳運(yùn)算的終止進(jìn)化代數(shù)、交叉概率及變異概率四個(gè)控制參數(shù)需要預(yù)先給定。通過(guò)大量實(shí)驗(yàn)驗(yàn)證，本文采用的參數(shù)值為：80～120，180～250，0.5～0.9，0.02～0.15。

2.3 C-Bézier曲線(xiàn)降階的步驟

步驟1輸入降階前的C-Bézier曲線(xiàn)的次數(shù)及C-Bézier曲線(xiàn)的控制頂點(diǎn)序列{P0，P1，…，Pn}。

步驟2繪制降階前的C-Bézier曲線(xiàn)及其控制多邊形。

步驟3初始化種群（大小為100）、控制參數(shù)（迭代次數(shù)200、交叉概率0.7、變異概率0.05）及誤差（誤差限數(shù)量級(jí)=取控制頂點(diǎn)的數(shù)據(jù)數(shù)量級(jí)/100）。

步驟4產(chǎn)生初始種群。

步驟5根據(jù)公式（6）計(jì)算群體的每個(gè)個(gè)體的適應(yīng)值。

步驟6判斷迭代次數(shù)是否小于群體代數(shù)200或每個(gè)個(gè)體的適應(yīng)值是否大于給定誤差，是，執(zhí)行步驟7；否，執(zhí)行步驟8。

步驟7進(jìn)行選擇雜交產(chǎn)生新的子代，轉(zhuǎn)到步驟6，計(jì)算該個(gè)體的適應(yīng)值，并進(jìn)入下一代的遺傳操作。

步驟8繪出降階后的C-Bézier曲線(xiàn)的控制多邊形及C-Bézier曲線(xiàn)。

2.4 實(shí)例分析

為了驗(yàn)證本文算法的可行性和有效性，進(jìn)行大量的數(shù)值研究，以下為應(yīng)用本算法的數(shù)值實(shí)例。這里參數(shù)α=2。為了估計(jì)曲線(xiàn)降階的誤差，本文采用式（4）、（5）的誤差公式來(lái)判斷降階后曲線(xiàn)與待降階曲線(xiàn)的x(t)之間的誤差大小，其計(jì)算公式為：

2.4.1 端點(diǎn)G0連續(xù)下C-Bézier曲線(xiàn)降階

圖1（a）給定一條三次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，0），（150，75），（250，80），（350，0）}；圖1（b）給定一條三次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（－20，0），（5，25），（25，20），（50，0）}。

圖2（a）給定一條四次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，0），（150，40），（250，60），（300，0），（350，0）}；圖2（b）給定一條四次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，20），（150，40），（250，30），（300，10），（350，20）}。

2.4.2 無(wú)約束條件下C-Bézier曲線(xiàn)降階

圖3（a）給定一條三次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，0），（150，75），（250，80），（350，0）}；圖3（b）給定一條三次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，0），（100，95），（150，80），（200，0）}。圖4（a）給定一條四次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，0），（150，40），（250，60），（300，40），（350，0）}；圖4（b）給定一條四次的C-Bézier曲線(xiàn)，其控制頂點(diǎn)為{（50，20），（150，40），（250，30），（300，10），（350，20）}。

圖1 端點(diǎn)G0連續(xù)下三階降為二階的效果

圖2 端點(diǎn)G0連續(xù)下四階降為三階

圖3 無(wú)約束條件下三階降為二階

圖4 無(wú)約束條件下四階降為三階

表1給出了在端點(diǎn)G0連續(xù)條件下圖1、圖2中實(shí)例的降階誤差；表2給出了無(wú)約束條件下圖3、圖4中實(shí)例的降階誤差。從表1、2中可以看出，本文方法對(duì)于C-Bézier曲線(xiàn)降階的近似降階都可獲得比較小的降階誤差。這與降階效果圖的主觀評(píng)價(jià)相一致，表明本文方法對(duì)于C-Bézier曲線(xiàn)降階的近似降階是相當(dāng)有效的。

表1 圖1和2中實(shí)例的降階誤差

表2 圖3和4中實(shí)例的降階誤差

2.4.3 s取值的討論

針對(duì)公式（7）中s該如何取值，本節(jié)作了如下的分析。利用圖4（b）中的數(shù)據(jù)，當(dāng)s分別取不同的值時(shí)，得到了誤差ε與s的關(guān)系圖，具體如圖5所示。從圖中可以看出，隨著s的增大ε不斷減??；而當(dāng)s增大到一定程度之后，誤差ε將不再隨s值的變化而顯著變化。此外，還做了大量的不同的數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果均表明s的值達(dá)到40～60之間時(shí)，ε不再隨s的變化而顯著變化。又因?yàn)閟取值越大，會(huì)使得計(jì)算效率降低，所以綜合考慮效率和誤差兩個(gè)方面的因素，在本文中取s=40。

圖5 ε-s的關(guān)系示意圖

2.4.4 與文獻(xiàn)[14]做對(duì)比

為了進(jìn)一步驗(yàn)證本文方法對(duì)C-Bézier曲線(xiàn)的降階效果，用本文方法對(duì)文獻(xiàn)[14]中例4給定的五次C-Bézier曲線(xiàn)進(jìn)行降階，降階后曲線(xiàn)的控制頂點(diǎn)為{（0.093 2，－0.000 6），（－3.327 3，0.004 0），（－0.006 9，0.246 0），（3.335 8，0.004 1），（－0.094 8，－0.000 8）}，降階誤差ε=0.013 3，明顯優(yōu)于文獻(xiàn)[14]方法得到的降階誤差0.069 9。本文方法的運(yùn)行時(shí)間取決人為給定的遺傳的終止進(jìn)化代數(shù)（一般取100代），而文獻(xiàn)[14]方法只進(jìn)行一次方程組的求解，所以本文方法耗時(shí)相對(duì)較長(zhǎng)。圖6給出了兩種降階方法的對(duì)比效果，根據(jù)整條曲線(xiàn)降階效果的主觀評(píng)價(jià)和誤差比較可知，本文方法對(duì)C-Bézier曲線(xiàn)的近似降級(jí)取得效果更為理想。

圖6 本文方法和文獻(xiàn)[14]方法的降階對(duì)比

3 結(jié)束語(yǔ)

本文利用C-Bézier曲線(xiàn)的幾何性質(zhì)，并結(jié)合遺傳算法討論C-Bézier曲線(xiàn)的降階問(wèn)題，實(shí)例充分體現(xiàn)遺傳算法在降階過(guò)程中全局優(yōu)化的特性，使得降階曲線(xiàn)能很好地逼近原曲線(xiàn)。所提方法不僅可以獲得較好的降階效果，而且還給出了具體的降階誤差。實(shí)驗(yàn)結(jié)果表明本文方法在曲線(xiàn)設(shè)計(jì)中的有效性。

[1]任水利，張凱院，葉正麟.Bézier曲線(xiàn)降階的矩陣方法[J].工程數(shù)學(xué)學(xué)報(bào)，2007，24（6）：1007-1014.

[2]Delgado J，PenaJM.Progressiveiterativeapproximation and baseswith thefastestconvergence rates[J].Computer Aided Geometric Design，2007，24（1）：10-18.

[3]Lu L Z，Wang G Z.Optimal multi-degree reduction of Bézier curves with G2-continuity[J].ComputerAided Geometric Design，2006，23（9）：673-683.

[4]陸利正，胡倩倩，汪國(guó)昭.Bézier曲線(xiàn)降階的迭代算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21（12）：1689-1693.

[5]Young J A，Byung G L，Yunbeom P.Constrained polynomial degree reduction in the L2-norm equals best weighted Euclidean approximation of Bézier coefficients[J].Computer Aided Geometric Design，2004，21（2）：181-191.

[6]Cai H J，Wang G J.Constrained approximation of rational Béziercurvesbased on a matrix expression ofitsend points continuity condition[J].Computer-Aided Design，2010，42（6）：495-504.

[7]Lu L Z，Wang G Z.Application of Chebyshev II-Bernstein basis transformations to degree reduction of Bézier curves[J]. Journal of Computational and Applied Mathematics，2008，221（1）：52-65.

[8]Rababah A，Lee B G，Yoo J.A simple matrix form for degree reduction of Bézier curves using Chebyshev-Bernstein basis transformations[J].Applied Mathematics and Computation，2006，181（1）：310-318.

[9]梁秀霞，張彩明，徐琳，等.L∞范數(shù)下使用基本曲線(xiàn)和修正曲線(xiàn)的帶約束B(niǎo)ézier曲線(xiàn)降階[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（3）：401-405.

[10]徐少平，白似雪，熊宇虹，等.在端點(diǎn)處保持非對(duì)稱(chēng)階參數(shù)連續(xù)性的Bézier曲線(xiàn)降階[J].工程圖學(xué)學(xué)報(bào)，2008（5）：91-97.

[11]樊建華，張紀(jì)文，鄔義杰.C-Bezier曲線(xiàn)的形狀修改[J].軟件學(xué)報(bào)，2002，13（11）：2194-2199.

[12]楊雅迪，秦新強(qiáng)，胡鋼，等.C-Bezier曲線(xiàn)的光順逼近算法[J].計(jì)算機(jī)應(yīng)用，2008，28（12）：3132-3134.

[13]樊建華，鄔義杰，林興.C-Bézier曲線(xiàn)分割算法及G1拼接條件[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2002，14（5）：421-424.

[14]王文濤.C-Bézier曲線(xiàn)降階逼近[J].浙江大學(xué)學(xué)報(bào)，2009，36 （4）：396-400.

[15]Chen Q Y，Wang G Z.A class of Bézier-like curves[J]. Computer Aided Geometric Design，2003，20（1）：29-39.

[16]秦開(kāi)懷，吳邊，關(guān)右江，等.三維單純性劃分的遺傳算法[J].中國(guó)科學(xué)：E輯，1997，27（1）：67-73.

[17]徐宗本，高勇.遺傳算法過(guò)早收斂的特征分析及其預(yù)防[J].中國(guó)科學(xué)：E輯，1996，26（4）：364-375.

QIN Xinqiang,WANG Weiwei,HU Gang

School of Science,Xi'an University of Technology,Xi'an 710054,China

Aimingat C-Bézier curve of approximate degree reduction problem,a method for constructing an approximative C-Bézier curve of degree n to a C-Bézier curve of degree n+1 by genetic algorithm is provided.By means of optimization methods,degree reduction of C-Bézier curves is transformed to an optimization problem,by selecting the fitness function,using a simple loop reproduction,copy process,crossover process,mutation process,selection process obtaining the optimal value of the optimization problem to achieve C-Bézier curve endpoints in the endpoint G0unconstrained and constrained approximate reduction.The experimental results illustrate that the proposed method not only has a good merging effect,but also is easy to implement,has high precision and is simple for error estimation.

C-Bézier curve;genetic algorithm;degree reduction;least squares approximation;constraints

針對(duì)C-Bézier曲線(xiàn)的近似降階問(wèn)題，基于遺傳算法，給出了一種用n次C-Bézier曲線(xiàn)最小平方逼近n+1次C-Bézier曲線(xiàn)的方法。該方法從最優(yōu)化思想出發(fā)，把C-Bézier曲線(xiàn)的降階問(wèn)題轉(zhuǎn)化為求解函數(shù)的優(yōu)化問(wèn)題，通過(guò)選擇適應(yīng)值函數(shù)，利用簡(jiǎn)單的循環(huán)執(zhí)行復(fù)制、交叉、變異、選擇求出該優(yōu)化問(wèn)題的最優(yōu)值，從而實(shí)現(xiàn)了C-Bézier曲線(xiàn)在端點(diǎn)無(wú)約束和端點(diǎn)G0約束條件下的近似降階逼近。實(shí)例結(jié)果表明，所提方法不僅可以獲得較好的降階效果，而且易于實(shí)現(xiàn)、精度高、誤差計(jì)算簡(jiǎn)單，可以廣泛地應(yīng)用于計(jì)算機(jī)輔助設(shè)計(jì)中對(duì)曲線(xiàn)的近似降階。

C-Bézier曲線(xiàn)；遺傳算法；降階；最小平方逼近；約束條件

A

TP391

10.3778/j.issn.1002-8331.1107-0346

QIN Xinqiang,WANG Weiwei,HU Gang.Degree reduction of C-Bézier curve based on genetic algorithm.Computer Engineering and Applications,2013,49（5）：174-178.

國(guó)家自然科學(xué)基金（No.10926152）；陜西省自然科學(xué)基金（No.2011JM1006）；陜西省教育廳自然科學(xué)研究項(xiàng)目（No.11JK1052）。

秦新強(qiáng)（1962—），男，博士，教授，主要從事計(jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)、微分方程數(shù)值解的研究；王偉偉（1986—），男，碩士，主要從事計(jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)的研究；胡鋼（1979—），男，講師，研究方向：計(jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)。E-mail：xqqin@xaut.edu.cn

2011-07-18

2011-11-03

1002-8331（2013）05-0174-05

CNKI出版日期：2011-11-14 http://www.cnki.net/kcms/detail/11.2127.TP.20111114.0948.051.html