基于遺傳算法的Bézier曲線降多階逼近

溫州大學(xué)物理與電子信息工程學(xué)院 于世亮

溫州醫(yī)學(xué)院生物信息工程學(xué)院 白寶剛

1.引言

參數(shù)曲線曲面在許多造型系統(tǒng)中都有重要的應(yīng)用，不同的造型系統(tǒng)中多項(xiàng)式基的次數(shù)是不同的，如果在系統(tǒng)間進(jìn)行數(shù)據(jù)傳遞[1]，就需要將參數(shù)曲線曲面的階數(shù)統(tǒng)一起來(lái)。由于高階曲線可以精確的表示低階曲線，一般來(lái)講，低階曲線卻不能精確表示高階曲線，近年來(lái)，參數(shù)曲線曲面的降階問題引起了國(guó)內(nèi)外許多學(xué)者的興趣。同時(shí)，降階曲線可以減少數(shù)據(jù)的存儲(chǔ)量，提高了造型系統(tǒng)的效率。此外，降階處理也應(yīng)用在曲線的光順處理過程中[2]。

Bézier曲線由于本身具有的良好的性質(zhì)，被廣泛應(yīng)用于計(jì)算機(jī)輔助設(shè)計(jì)和制造，國(guó)內(nèi)外許多學(xué)者研究了Bézier曲線的降階問題[3-6]。Hoschek[3]首先對(duì)原曲線進(jìn)行離散，然后利用原曲線的幾何信息，通過多段低階曲線來(lái)插值逼近原曲線；Worsey[4]，Lachance[5]及Eck[6]利用Chebyshev多項(xiàng)式理論，對(duì)降階進(jìn)行了研究；胡事民[7]提出了B網(wǎng)擾動(dòng)和約束優(yōu)化的方法等。這些方法只進(jìn)行了一次降階，如需多次降階，則要循環(huán)運(yùn)用算法，這樣一方面是計(jì)算繁瑣耗時(shí)大，另一方面是誤差有可能會(huì)很大。2002年陳國(guó)棟和王國(guó)瑾[8]給出了帶端點(diǎn)插值條件的Bézier曲線一次降多階逼近方法；鄭建民和汪國(guó)昭[9]著眼于幾何逼近技術(shù)，對(duì)原曲線控制頂點(diǎn)作最小擾動(dòng)來(lái)得到約束降多階曲線。這些研究或者計(jì)算繁瑣，或者沒有很好的誤差估計(jì)，逼近精度未必最佳，或者沒有降階后曲線的顯式表示。本文在上述研究的基礎(chǔ)上，應(yīng)用遺傳算法的性質(zhì)特點(diǎn)，與Bézier曲線降階相結(jié)合，運(yùn)用matlab工具箱實(shí)現(xiàn)了多次降階。

2.問題描述

所謂n次Bézier曲線Pn( t)降多階到m次，即尋找另一組控制頂點(diǎn)所確定的m次Bézier曲線,使得降階前后兩條曲線之間的距離函數(shù)：

達(dá)到最小。本文只討論n次Bézier曲線降階的非退化情形，上述問題可轉(zhuǎn)化為如下的帶端點(diǎn)約束的最優(yōu)化問題：

傳統(tǒng)的解決最優(yōu)化問題存在各種弊端，而遺傳算法（Genetic Algorithm，簡(jiǎn)稱GA）是以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過程中適者生存規(guī)則與群體內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合的高效全局尋優(yōu)搜索算法，與傳統(tǒng)的搜索方式相比較，具有如下優(yōu)點(diǎn)：

a.遺傳算法的操作對(duì)象是一組可行解，而非單個(gè)可行解；搜索軌道有多條，而非單條，因而具有良好的并行性。

b.遺傳算法只需要利用目標(biāo)的取值信息，而無(wú)需梯度等高價(jià)值信息，因而適用于任何大規(guī)模、高度非線性的不連續(xù)多峰函數(shù)的優(yōu)化以及無(wú)解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化，具有很強(qiáng)的通用性。

c.遺傳算法擇優(yōu)機(jī)制是一種軟選擇，加上其良好的并行性，使它具有良好的全局優(yōu)化和穩(wěn)健性。

d.遺傳算法操作的可行解是經(jīng)過編碼化的（通常采用二進(jìn)制編碼），目標(biāo)函數(shù)解釋為編碼化個(gè)體（可行解）的適應(yīng)值，因而具有良好的可操作性和簡(jiǎn)單性。

3.算法描述

3.1 編碼方法

我們采用實(shí)數(shù)編碼，直接使用問題變量進(jìn)行編碼，避免了二進(jìn)制編碼對(duì)解的精度限制，提高了遺傳算法的精度要求；無(wú)需編碼解碼，改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率。我們將每次產(chǎn)生的m個(gè)控制點(diǎn)組成解向量，成為一個(gè)個(gè)體。

3.2 初始群體的生成

產(chǎn)生隨機(jī)數(shù)αi∈[0,1],i=0,...,m,然后應(yīng)用

求出降階后的控制頂點(diǎn)，即一個(gè)個(gè)體，然后根據(jù)群體大小，得到初始群體。Pmin和Pmax為Bézier曲線左右降一階然后分別遞歸執(zhí)行n- m-1次所得到的控制點(diǎn)，為保證端點(diǎn)的插值性，令

3.3 適應(yīng)值函數(shù)

適應(yīng)值函數(shù)即個(gè)體評(píng)價(jià)函數(shù)，函數(shù)值越大表示適應(yīng)能力越好，符合適者生存的生物進(jìn)化規(guī)律，一般而言，適應(yīng)值函數(shù)的設(shè)定需要從目標(biāo)函數(shù)轉(zhuǎn)換得來(lái)，我們采用的是實(shí)數(shù)編碼，適應(yīng)值函數(shù)取：

其中， Pi和是降階前后曲線上的點(diǎn)。

3.4 遺傳算子

選擇：輪盤賭選擇由于使個(gè)體實(shí)際被選中的次數(shù)與它應(yīng)該被選中的期望值之間可能存在著一定的誤差，因此這種選擇方法的選擇誤差比較大，有時(shí)甚至連適應(yīng)度高的個(gè)體也選不上。我們采用隨機(jī)競(jìng)爭(zhēng)選擇方法，每次按輪盤賭選取一對(duì)個(gè)體，然后讓這兩個(gè)個(gè)體進(jìn)行競(jìng)爭(zhēng)，適應(yīng)度高的被選中，反復(fù)進(jìn)行，直到選滿。

交叉：群體中的個(gè)體采取隨機(jī)配對(duì)的策略，交叉操作是在這些配對(duì)個(gè)體組中兩個(gè)個(gè)體之間進(jìn)行，雙親的染色體以雜交的方式產(chǎn)生出子代染色體，從而使子代染色體繼承了雙親的遺傳特性，為了保證雜交產(chǎn)生的后代，其分量仍在[Pmin,Pmax]上，同時(shí)相應(yīng)于實(shí)數(shù)編碼，我們采用非均勻算數(shù)雜交，假設(shè)兩個(gè)父解向量為：

經(jīng)雜交產(chǎn)生兩個(gè)后代為：

則他們之間有如下關(guān)系：

其中α∈[0,1],為隨機(jī)數(shù)。

變異：變異運(yùn)算雖然只是產(chǎn)生新個(gè)體的輔助方法，但它也是必不可少的一個(gè)步驟，它決定了遺傳算法的局部搜索能力，此外，變異運(yùn)算維持了群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。采用均勻變異的方法，依次指定個(gè)體編碼串中的每一個(gè)基因座為變異點(diǎn)，對(duì)每一個(gè)變異點(diǎn)以設(shè)定的變異概率從對(duì)應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)來(lái)代替原有值。

圖1 四次Bézier曲線降到兩次Bézier曲線

圖2 五次Bézier曲線降到三次Bézier曲線

圖3 七次Bézier曲線降到四次Bézier曲線

3.5 控制參數(shù)

遺傳算法中，控制參數(shù)的選擇非常關(guān)鍵，參數(shù)包括群體的規(guī)模N、交叉概率cP、變異概率Pm、進(jìn)化代數(shù)T等。太大的交叉概率可能是搜索走向隨機(jī)化，太小則進(jìn)化速度變慢；變異概率適當(dāng)增大可維持群體的多樣性，搜索過程可跳出局部，收斂到全局最優(yōu)。本文在分別在以下參數(shù)范圍做了大量實(shí)驗(yàn)：150-200，200-250，0.4-0.99，0.0001-0.1。

3.6 實(shí)現(xiàn)步驟

Step1.輸入降階前的控制頂點(diǎn) Pi，i=0,1,···,n-1，輸入需要降階到的m值。

Step2.求左右降一階的控制點(diǎn)頂點(diǎn)并遞歸n-m-1次，求得最終的m對(duì)控制頂點(diǎn)。

Step3.繪制降階前的控制頂點(diǎn)和曲線。

Step4.初始化初始化群體代數(shù)和控制參數(shù)及誤差。

Step5.產(chǎn)生初始群體。

Step6.計(jì)算群體的每個(gè)個(gè)體的適應(yīng)值.

Step7.若迭代次數(shù)小于群體代數(shù)或每個(gè)個(gè)體的適應(yīng)值大于給定誤差，轉(zhuǎn)Step8；否則，轉(zhuǎn)Step9。

Step 8.進(jìn)行選擇雜交產(chǎn)生新的子代，返回Ste p 6。

Step 9.繪制降階后的Bézier曲線的控制多邊形及曲線。

4.誤差分析

n次Bézier曲線P( t)降n-m次得到m次Bézier曲線，將降階后的曲線升n-m-1次，得到n-1次Bézier曲線x( t)，與原曲線的誤差為：

5.數(shù)值實(shí)驗(yàn)

例1：降兩階，給定五個(gè)控制點(diǎn)：

{90,150}，{150,300}，{260,360}，{400,280}，{570,100}的四次Bézier曲線，降兩階得兩次Bézier曲線，產(chǎn)生三個(gè)控制點(diǎn)為：{90.0000,150.0000}，{229.8573,472.2235}，{570.0000,100.0000}，如圖1，其中虛線代表降階后的控制多邊形和曲線，實(shí)線代表降階前的控制多邊形和曲線（下同），誤差為：3.012745。

例2：降兩階，給定六個(gè)控制點(diǎn)：

{70,280}，{150,450}，{250,410}，{360,300}，{450,260}，{600,420}的五次Bézier曲線，降兩階后，得到由四個(gè)控制點(diǎn)：{70.0000,280.0000}，{203.7269,571.3842}，{396.4577,150.1183}，{600.0000,420.0000}控制的三次Bézier曲線，如圖2，降階前后曲線誤差為：5.198758。

例3：降三階，給定八個(gè)控制點(diǎn)：

{10,80}，{25,40}，{35,45}，{45,65}，{55,100}，{70,115}，{90,100}，{105,50}所確定的七次Bézier曲線，降三階，得到五個(gè)控制點(diǎn)為：{10.0000,80.0000}，{33.2864,9.7327}，{45.0332,90.4035}，{79.9754,141.6573}，{105.0000,50.0000}，產(chǎn)生降階后的四次Bézier曲線，如圖3，誤差為：6.342841。

6.結(jié)論

基于遺傳算法，根據(jù)Bézier曲線的基本性質(zhì)，實(shí)現(xiàn)了Bézier曲線保端點(diǎn)的多次降階，實(shí)驗(yàn)表明，降階效果好，直觀性強(qiáng)。

[1]DANNEBERG,L,NOWACKI,H.Approximate conversion of surface representations with polynomial bases[J].Computer-Aided Geometric Design,1985,2(2):123-132.

[2]FARIN,G.Degree reduction fairing of cubic B-Spline curves[J].In：Barnhill,R,E,ed.Geometry Processing for Desiging and Manufactur-ing.Philadelphia:SIAM,1992.87-99.

[3]HOSCHEK,J.Approximation of spline curves[J].Computer-Aided Geometric Design,1987,4(1):59-66.

[4]WATKINS,M,WORSEY,A.Degree reduction for Bézier curves[J].Computer-Aided Design,1988,20(7):398-405.

[5]LACHANCE,M A.Chebyshev economization for parametric surfaces[J].Computer-Aided Geometric Design,1988,5(3):195-208.

[6]ECK,M,A.Degree reduction of Bézier curves[J].Computer-Geometric Design,1993,10(4):237-257.

[7]HU SM,SUN JG,JIN TG,WANG GZ.Approximate degree reduction of Bézier curves[J].Tsinghua Science and Technology,1998,3(2):997-1000.

[8]GUO-DONG CHEN,GUO-JIN WANG.Optimal multi-degree reduction of Bézier curves with constrains of endpoints continuity[J].Computer Aided Geometric Design 19(2002):365-377.

[9]Zheng J M,Wang G-Z,Perturbing Bézier coefficients for best constrained degree reduction[J].Graphical Models,2003,65(6):351-368.