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

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

溫州醫學院生物信息工程學院 白寶剛

1.引言

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

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

2.問題描述

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

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

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

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

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

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

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

3.算法描述

3.1 編碼方法

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

3.2 初始群體的生成

產生隨機數αi∈[0,1],i=0,...,m,然后應用

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

3.3 適應值函數

適應值函數即個體評價函數，函數值越大表示適應能力越好，符合適者生存的生物進化規律，一般而言，適應值函數的設定需要從目標函數轉換得來，我們采用的是實數編碼，適應值函數?。?/p>

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

3.4 遺傳算子

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

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

經雜交產生兩個后代為：

則他們之間有如下關系：

其中α∈[0,1],為隨機數。

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

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

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

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

3.5 控制參數

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

3.6 實現步驟

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

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

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

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

Step5.產生初始群體。

Step6.計算群體的每個個體的適應值.

Step7.若迭代次數小于群體代數或每個個體的適應值大于給定誤差，轉Step8；否則，轉Step9。

Step 8.進行選擇雜交產生新的子代，返回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.數值實驗

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

{90,150}，{150,300}，{260,360}，{400,280}，{570,100}的四次Bézier曲線，降兩階得兩次Bézier曲線，產生三個控制點為：{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}，產生降階后的四次Bézier曲線，如圖3，誤差為：6.342841。

6.結論

基于遺傳算法，根據Bézier曲線的基本性質，實現了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.