基于遺傳算法的二次曲面提取技術(shù)研究

王長(zhǎng)明， 聶建軍

(1．新鄉(xiāng)巴山航空材料有限公司 河南新鄉(xiāng)453001;2．中原工學(xué)院 機(jī)電學(xué)院 河南鄭州450001)

0 引言

據(jù)Mills統(tǒng)計(jì)，在傳統(tǒng)機(jī)械零件中，85%的機(jī)械零件都可用平面、圓錐面、球面和圓柱面描述，其中圓柱面出現(xiàn)的頻率就達(dá)到了73．5%［1］．由此看出，一般工業(yè)零件表面存在大量的平面和二次曲面．這些規(guī)則曲面可用少量幾何參數(shù)精確表示，容易實(shí)現(xiàn)參數(shù)化設(shè)計(jì)與修改．如果統(tǒng)一使用NURBS曲面或三角Bezier曲面構(gòu)造零件表面上的這些規(guī)則曲面，從精確建模的角度看，顯然不合理．由于沒(méi)有考慮到曲面的特殊性質(zhì)，導(dǎo)致可用少量參數(shù)就能精確表示的曲面不得不用很多數(shù)據(jù)才能表示出來(lái)，甚至不能反映原來(lái)產(chǎn)品的設(shè)計(jì)信息和設(shè)計(jì)者的設(shè)計(jì)意圖，而且純NURBS曲面或三角Bezier曲面模型不利于轉(zhuǎn)換到現(xiàn)有實(shí)體和特征造型系統(tǒng)中進(jìn)行再設(shè)計(jì)，進(jìn)而影響到產(chǎn)品的創(chuàng)新．因此，將零件中的規(guī)則曲面從測(cè)量數(shù)據(jù)中提取出來(lái)，并判斷曲面類型，計(jì)算其幾何參數(shù)，可以減少計(jì)算量，對(duì)提高重建模型的精度和速度具有十分重要的意義．

目前對(duì)二次曲面的提取，大多以三角化的測(cè)量數(shù)據(jù)為基礎(chǔ)，但是，對(duì)海量點(diǎn)云數(shù)據(jù)進(jìn)行三角化運(yùn)算不僅效率低下，而且提取精度往往難以滿足實(shí)際需要．本文針對(duì)離散點(diǎn)云數(shù)據(jù)直接進(jìn)行二次曲面提取，首先對(duì)單一類型的點(diǎn)云數(shù)據(jù)塊進(jìn)行曲面識(shí)別，然后針對(duì)不同類型的二次曲面，利用其幾何參數(shù)方程，實(shí)現(xiàn)基于實(shí)數(shù)編碼遺傳算法的二次曲面提?。?/p>

1 基于實(shí)數(shù)編碼遺傳算法的二次曲面提取

遺傳算法(genetic algorithm，GA)［2］是由美國(guó)Michigan大學(xué)的Holland教授首先提出的一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過(guò)程中適者生存規(guī)則與種群內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合的隨機(jī)化搜索算法．遺傳算法使用群體搜索技術(shù)，通過(guò)對(duì)當(dāng)前群體施加選擇、交叉、變異等一系列遺傳操作，從而產(chǎn)生出新一代的群體，并逐步使群體進(jìn)化到包含或接近最優(yōu)解的狀態(tài)．

遺傳算法大致包含7個(gè)基本步驟［3］:(1)對(duì)所求問(wèn)題確定編碼方案;(2)確定適應(yīng)度函數(shù);(3)初始化一個(gè)種群;(4)選擇策略的確定;(5)選取遺傳過(guò)程中合適的控制參數(shù);(6)對(duì)整個(gè)種群反復(fù)進(jìn)行選擇、交叉、變異等遺傳操作，使得整個(gè)種群不斷趨向于最優(yōu)值;(7)滿足終止規(guī)則時(shí)，結(jié)束第(6)步的遺傳操作．

空間離散點(diǎn)云提取二次曲面實(shí)際上是尋找這些離散點(diǎn)的最佳擬合二次曲面，屬優(yōu)化問(wèn)題，理論上可用遺傳算法求解．與傳統(tǒng)優(yōu)化方法相比，遺傳算法采用交叉、變異等操作產(chǎn)生新個(gè)體，擴(kuò)大了搜索范圍，使優(yōu)化結(jié)果為全局最優(yōu)解，而非局部最優(yōu)解．多數(shù)傳統(tǒng)優(yōu)化算法，當(dāng)目標(biāo)函數(shù)僅具有單極點(diǎn)時(shí)，通常表現(xiàn)出較高的效率，但當(dāng)目標(biāo)函數(shù)有多個(gè)極點(diǎn)時(shí)，往往會(huì)陷入局部最優(yōu)解，而不能得到真正的全局最優(yōu)解［4］．因此，本文提出采用遺傳算法實(shí)現(xiàn)基于離散點(diǎn)云的二次曲面提取技術(shù)．

1．1 確定編碼方案

遺傳算法首先對(duì)實(shí)際問(wèn)題的可行解進(jìn)行編碼，用字符串表達(dá)問(wèn)題的解．字符串相當(dāng)于遺傳學(xué)中的染色體，其中的每個(gè)字符相當(dāng)于一個(gè)基因．通常編碼有二進(jìn)制編碼和實(shí)數(shù)編碼兩種方案．

二進(jìn)制編碼、解碼操作簡(jiǎn)單易行，交叉、變異操作便于實(shí)現(xiàn)，但對(duì)于像二次曲面這樣的多參尋優(yōu)問(wèn)題，若采用二進(jìn)制編碼，將導(dǎo)致編碼過(guò)長(zhǎng)，搜索效率降低．而實(shí)數(shù)編碼具有搜索空間大、全局搜索能力強(qiáng)、搜索速度快等優(yōu)點(diǎn)，同時(shí)可避免數(shù)制的轉(zhuǎn)換，在數(shù)值優(yōu)化方面具有更高的精度和效率，適合多參尋優(yōu)問(wèn)題［4］．因此，本文采用實(shí)數(shù)編碼．

設(shè)變量x(j)為第j個(gè)優(yōu)化變量，［L(j)，R(j)］為x(j)的變化區(qū)間，利用線性變換

將初始變化區(qū)間為［L(j)，R(j)］的第j個(gè)優(yōu)化變量x(j)映射到［0，1］區(qū)間上的實(shí)數(shù)y(j)，y(j)為基因．實(shí)數(shù)編碼直接把每個(gè)變量作為基因處理，也是一種沒(méi)有編碼的編碼方式．經(jīng)過(guò)這種實(shí)數(shù)編碼，所有優(yōu)化變量的取值范圍都統(tǒng)一在［0，1］區(qū)間．

1．2 確定適應(yīng)度函數(shù)

f(xi，yi，zi)反映點(diǎn)(xi，yi，zi)到二次曲面的代數(shù)距離，理想情況下，代數(shù)距離應(yīng)該為0．因此，目標(biāo)函數(shù)可

1．3 選擇策略

為將已有群體變?yōu)橄乱淮后w，遺傳算法仿效進(jìn)化論中“自然選擇，適者生存”的原則，從當(dāng)前群體中選擇優(yōu)良個(gè)體進(jìn)行復(fù)制．選擇依據(jù)是適應(yīng)度的大小，適應(yīng)度大的個(gè)體接受復(fù)制，使之繁衍;適應(yīng)度小的個(gè)體予以刪除，使之死亡．常見(jiàn)的選擇策略有轉(zhuǎn)盤式選擇、規(guī)則化幾何分布選擇、錦標(biāo)賽選擇等，其中轉(zhuǎn)盤式選擇策略使用的最多［5］．

為方便計(jì)算機(jī)編程，對(duì)轉(zhuǎn)盤式選擇策略作部分改進(jìn)．首先按照適應(yīng)度值從大到小進(jìn)行排序，將序號(hào)在前的m個(gè)個(gè)體復(fù)制兩份，淘汰序號(hào)在后的m個(gè)個(gè)體，序號(hào)在中間的(N－2m)個(gè)個(gè)體復(fù)制一份．該做法能夠保證群體尺寸不變，且編程非常容易．

1．4 遺傳算法的實(shí)現(xiàn)

為加快向最優(yōu)解收斂的速度，提高算法的執(zhí)行效率，編程時(shí)對(duì)標(biāo)準(zhǔn)遺傳算法引入以下策略［6］:

1)迭代初期使用大的交叉概率pc，小的變異概率pm，隨后動(dòng)態(tài)減小pc，增大pm．

2)分階段判斷終止條件．對(duì)父代種群進(jìn)行交叉操作后，已初步實(shí)現(xiàn)父代解朝最優(yōu)方向的改進(jìn)．因此，交叉操作完成后，滿足終止條件的最優(yōu)解可能已存在，如再次進(jìn)行下一步變異操作，可能會(huì)暫時(shí)破壞最優(yōu)解，增加迭代次數(shù)，延長(zhǎng)搜索最優(yōu)解的時(shí)間．因此，在交叉操作完成后、變異操作執(zhí)行前增加一次終止條件的判斷，能夠一定程度上提高執(zhí)行效率．

3)變異操作時(shí)，總希望優(yōu)秀個(gè)體被選中的機(jī)會(huì)大，較差個(gè)體被選中的機(jī)會(huì)小．因此，可用交叉操作產(chǎn)生的種群中的優(yōu)秀個(gè)體替換最差個(gè)體，從而使參加變異的種群中優(yōu)秀個(gè)體數(shù)量增加，被選中的機(jī)會(huì)也增大，使搜索更快的朝著有利于最優(yōu)解的方向發(fā)展，該操作過(guò)程稱為擇優(yōu)操作．

2 應(yīng)用實(shí)例分析

本文采用大量模擬數(shù)據(jù)進(jìn)行驗(yàn)證．假設(shè)點(diǎn)云數(shù)據(jù)已完成前期分割，對(duì)指定的單一曲面采用遺傳算法進(jìn)行提取實(shí)驗(yàn)．

2．1 遺傳算法提取二次曲面

采用3組模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，用計(jì)算機(jī)生成常用二次曲面離散數(shù)據(jù)(精確到小數(shù)點(diǎn)后5位)作為一組，然后分別在生成數(shù)據(jù)的基礎(chǔ)上加入兩種不同程度的高斯噪聲(≤0．02和≤0．2)作為另外兩組，如圖1所示．

圖1 實(shí)驗(yàn)用點(diǎn)云數(shù)據(jù)Fig．1 Experimental data of point cloud

遺傳迭代時(shí)，取表面上100個(gè)數(shù)據(jù)點(diǎn)，遺傳控制參數(shù)設(shè)為:群體規(guī)模N為100，交叉概率pc初始值為0．85，變異概率pm初始值為0．12，算法終止條件為誤差平方和小于0．01或進(jìn)化代數(shù)大于10 000代．

2．2 遺傳算法提取二次曲面結(jié)果分析

遺傳算法提取結(jié)果分析如表1所示．在正常數(shù)據(jù)情況下，遺傳算法的迭代次數(shù)為362次，執(zhí)行時(shí)間為14．95 s，當(dāng)加入0．02噪聲時(shí)，遺傳算法的迭代次數(shù)為586次，執(zhí)行時(shí)間為18．14 s;當(dāng)加入0．2噪聲時(shí)，遺傳算法的迭代次數(shù)為726次，執(zhí)行時(shí)間為26．84 s．

表1 遺傳算法提取結(jié)果分析表Tab．1 Analysis table of extraction results using genetic algorithm

從表1可以看出，對(duì)正常數(shù)據(jù)或較少噪音的數(shù)據(jù)來(lái)講，遺傳算法計(jì)算精度非常高，隨著噪音數(shù)據(jù)的增多增大，遺傳算法仍具有很強(qiáng)的抗噪音能力，甚至在加入大量0．2噪音數(shù)據(jù)的情況下，依然能得到精度很高的提取結(jié)果，但效率稍低．

3 結(jié)論

本文詳細(xì)介紹了基于實(shí)數(shù)編碼遺傳算法的二次曲面提取技術(shù)，并通過(guò)實(shí)例，針對(duì)不同類型的二次曲面，驗(yàn)證了實(shí)數(shù)編碼遺傳算法提取二次曲面的有效性，分析了實(shí)數(shù)編碼遺傳算法在曲面提取中的優(yōu)缺點(diǎn)，對(duì)實(shí)際工程中應(yīng)用實(shí)數(shù)編碼遺傳算法提取二次曲面具有一定的指導(dǎo)意義．結(jié)果表明:對(duì)正常數(shù)據(jù)或較少噪音的數(shù)據(jù)來(lái)講，遺傳算法計(jì)算精度非常高，隨著噪音數(shù)據(jù)的增多增大，遺傳算法仍具有很強(qiáng)的抗噪音能力，甚至在加入大量0．2噪音數(shù)據(jù)的情況下，依然能得到精度很高的提取結(jié)果，但效率稍低．本文研究結(jié)果建立在點(diǎn)云數(shù)據(jù)已前期分割為單一二次曲面的假定基礎(chǔ)之上，對(duì)由多個(gè)二次曲面拼接而成的復(fù)雜曲面及二次曲面的判定方法有待進(jìn)一步研究．

［1］ Yang M，Lee E．Segmentation of measured point data using a parametric quatric surface approximation［J］．Computer Aided Design，1999，31:449 －457．

［2］ Pottmann H，Hofer M，Odehnal B，et al．Line geomettry for 3D shape understanding and reconstruction［C］//Proceedings of the 8th European Conference on Computer Vision．Prague，2004:297 －309．

［3］ Marshall D，Lukacs G，Martin R．Robust segmentation of primitives from range data in the presence of geometric degeneracy［J］．IEEE Transaction on Pattern Analysis and Machine Intelligence，2001，23(3):304－314．

［4］ Sablatning R，Kampel M．Model-based registration of front and backviews of rotationally symmetric objects［J］．Computer Vision and Image Understanding，2002，87(1/2/3):90 －103．

［5］ Pottmann H，Peternell M，Ravani B．An instruction to line geometry with applications［J］．Computer Aided Design，1999，31(1):3－16．

［6］ Benko P，Varady T．Best fit translational and rotational surfaces for reverse engineering shapes［C］//9th IMA Conference on the Mathematics of Surface．London，2000:70－81．