基于遺傳算法的C-Bézier曲線降階

秦新強，王偉偉，胡 鋼

西安理工大學 理學院，西安 710054

基于遺傳算法的C-Bézier曲線降階

秦新強，王偉偉，胡 鋼

西安理工大學 理學院，西安 710054

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

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

1 C-Bézier曲線的定義

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

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

式中，{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曲線降階

2.1 降階問題的提出

滿足條件：

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

2.2 C-Bézier曲線降階的基本思想

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

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

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

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

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

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

2.2.3 選擇

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

2.2.4 雜交

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

2.2.5 變異

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

2.2.6 收斂條件

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

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

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

2.3 C-Bézier曲線降階的步驟

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

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

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

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

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

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

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

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

2.4 實例分析

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

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

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

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

2.4.2 無約束條件下C-Bézier曲線降階

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

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

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

圖3 無約束條件下三階降為二階

圖4 無約束條件下四階降為三階

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

表1 圖1和2中實例的降階誤差

表2 圖3和4中實例的降階誤差

2.4.3 s取值的討論

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

圖5 ε-s的關系示意圖

2.4.4 與文獻[14]做對比

為了進一步驗證本文方法對C-Bézier曲線的降階效果，用本文方法對文獻[14]中例4給定的五次C-Bézier曲線進行降階，降階后曲線的控制頂點為{（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)于文獻[14]方法得到的降階誤差0.069 9。本文方法的運行時間取決人為給定的遺傳的終止進化代數(shù)（一般取100代），而文獻[14]方法只進行一次方程組的求解，所以本文方法耗時相對較長。圖6給出了兩種降階方法的對比效果，根據(jù)整條曲線降階效果的主觀評價和誤差比較可知，本文方法對C-Bézier曲線的近似降級取得效果更為理想。

圖6 本文方法和文獻[14]方法的降階對比

3 結束語

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

[1]任水利，張凱院，葉正麟.Bézier曲線降階的矩陣方法[J].工程數(shù)學學報，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]陸利正，胡倩倩，汪國昭.Bézier曲線降階的迭代算法[J].計算機輔助設計與圖形學學報，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ù)下使用基本曲線和修正曲線的帶約束Bézier曲線降階[J].計算機輔助設計與圖形學學報，2006，18（3）：401-405.

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

[11]樊建華，張紀文，鄔義杰.C-Bezier曲線的形狀修改[J].軟件學報，2002，13（11）：2194-2199.

[12]楊雅迪，秦新強，胡鋼，等.C-Bezier曲線的光順逼近算法[J].計算機應用，2008，28（12）：3132-3134.

[13]樊建華，鄔義杰，林興.C-Bézier曲線分割算法及G1拼接條件[J].計算機輔助設計與圖形學報，2002，14（5）：421-424.

[14]王文濤.C-Bézier曲線降階逼近[J].浙江大學學報，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]秦開懷，吳邊，關右江，等.三維單純性劃分的遺傳算法[J].中國科學：E輯，1997，27（1）：67-73.

[17]徐宗本，高勇.遺傳算法過早收斂的特征分析及其預防[J].中國科學：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

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

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

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.

國家自然科學基金（No.10926152）；陜西省自然科學基金（No.2011JM1006）；陜西省教育廳自然科學研究項目（No.11JK1052）。

秦新強（1962—），男，博士，教授，主要從事計算機輔助幾何設計與圖形學、微分方程數(shù)值解的研究；王偉偉（1986—），男，碩士，主要從事計算機輔助幾何設計與圖形學的研究；胡鋼（1979—），男，講師，研究方向：計算機輔助幾何設計與圖形學。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