• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2013-07-11 09:36:20秦新強王偉偉
    計算機工程與應用 2013年5期
    關鍵詞:控制頂點圖形學降階

    秦新強,王偉偉,胡 鋼

    西安理工大學 理學院,西安 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

    猜你喜歡
    控制頂點圖形學降階
    帶互異權值的B樣條曲線的最小二乘漸進迭代逼近
    單邊Lipschitz離散非線性系統(tǒng)的降階觀測器設計
    突出實踐需求的GIS專業(yè)《計算機圖形學》課程優(yōu)化改革
    有理二次Bézier形式共軛雙曲線段的幾何計算
    圖學學報(2015年2期)2015-12-02 10:43:40
    降階原理在光伏NPC型逆變微網(wǎng)中的應用研究
    電源技術(2015年11期)2015-08-22 08:50:58
    基于Krylov子空間法的柔性航天器降階研究
    基于CFD降階模型的陣風減緩主動控制研究
    航空學報(2015年4期)2015-05-07 06:43:34
    面向控制頂點優(yōu)化的自由曲線交互擬合技術
    曲率對車身A級曲面控制頂點排列的影響*
    汽車技術(2013年9期)2013-04-17 06:37:42
    第7屆國際圖象圖形學學術會議
    九寨沟县| 锦屏县| 称多县| 澜沧| 荃湾区| 东宁县| 图们市| 芜湖市| 津市市| 滨海县| 达尔| 尉犁县| 鲜城| 湾仔区| 五原县| 平舆县| 卢氏县| 广水市| 乳源| 萨迦县| 新津县| 吴川市| 紫金县| 平和县| 准格尔旗| 千阳县| 屏东市| 昌宁县| 含山县| 涞水县| 布拖县| 平阴县| 江城| 淮南市| 兰溪市| 宝鸡市| 景东| 辛集市| 巴东县| 古浪县| 黑龙江省|