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

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

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

1.引言

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

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

2.問題描述

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

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

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

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

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

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

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

3.算法描述

3.1 編碼方法

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

3.2 初始群體的生成

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

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

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

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

其中， Pi和是降階前后曲線上的點。

3.4 遺傳算子

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

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

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

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

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

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

圖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、進化代數(shù)T等。太大的交叉概率可能是搜索走向隨機化，太小則進化速度變慢；變異概率適當(dāng)增大可維持群體的多樣性，搜索過程可跳出局部，收斂到全局最優(yōu)。本文在分別在以下參數(shù)范圍做了大量實驗：150-200，200-250，0.4-0.99，0.0001-0.1。

3.6 實現(xiàn)步驟

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

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

Step3.繪制降階前的控制頂點和曲線。

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

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

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

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

Step 8.進行選擇雜交產(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ù)值實驗

例1：降兩階，給定五個控制點：

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

例2：降兩階，給定六個控制點：

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

例3：降三階，給定八個控制點：

{10,80}，{25,40}，{35,45}，{45,65}，{55,100}，{70,115}，{90,100}，{105,50}所確定的七次Bézier曲線，降三階，得到五個控制點為：{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ì)，實現(xiàn)了Bézier曲線保端點的多次降階，實驗表明，降階效果好，直觀性強。

[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.