陳岳坪,靳龍,李書平,宋世柳,陳藝
(1.廣西科技大學(xué)廣西汽車零部件與整車技術(shù)重點(diǎn)實(shí)驗(yàn)室,廣西柳州 545006;2.柳州市產(chǎn)品質(zhì)量監(jiān)督檢驗(yàn)所,廣西柳州 545001)
近年來,國內(nèi)外學(xué)者對(duì)自由曲面匹配的算法做了大量的研究工作[1-4]。曲面匹配主要應(yīng)用在兩個(gè)方面:(1)根據(jù)三坐標(biāo)測量機(jī)的檢測結(jié)果,對(duì)加工曲面進(jìn)行加工精度的評(píng)價(jià)[5],由于這個(gè)過程中存在測量基準(zhǔn)與設(shè)計(jì)基準(zhǔn)不統(tǒng)一的問題,需要進(jìn)行曲面匹配,以消除自由曲面測量中的定位誤差;(2)在數(shù)控機(jī)床上進(jìn)行自由曲面類工件的自動(dòng)定位時(shí)[6-7],也存在測量基準(zhǔn)與加工基準(zhǔn)不統(tǒng)一的問題,需要根據(jù)曲面匹配的結(jié)果,修正數(shù)控加工程序以進(jìn)行正確的加工。目前,迭代最近點(diǎn)算法 (Iterative Closest Point,ICP)在曲面匹配中得到了廣泛使用。但是ICP算法常常收斂于局部最優(yōu)點(diǎn),若迭代初始點(diǎn)選擇不好,將難以求出全局最優(yōu)解。針對(duì)此問題,文獻(xiàn) [8]采用遺傳算法求出初始值,但遺傳算法存在著早熟收斂、后期收斂速度慢等問題。文獻(xiàn)[5]采用基于測量數(shù)據(jù)的重心和近似法矢來確定初始點(diǎn),但根據(jù)測量數(shù)據(jù)求曲面的重心,這種方法受到測點(diǎn)分布情況的影響,若測點(diǎn)分布不均勻,將難于確定曲面的重心。另外,在采用數(shù)學(xué)優(yōu)化算法求解坐標(biāo)變換矩陣中的過程中,由于平移參數(shù)和旋轉(zhuǎn)參數(shù)的量綱不一致、數(shù)量級(jí)差別較大,影響最終匹配精度。
針對(duì)以上存在的問題,文中采用兩步法進(jìn)行曲面匹配,即采用粗匹配和精匹配兩個(gè)步驟來進(jìn)行逐步求精。粗匹配過程中引入微分進(jìn)化法求取迭代計(jì)算的初始點(diǎn),即全局最優(yōu)解的近似值;精匹配是根據(jù)最小二乘原理和最小條件原則,分別采用單純形法和坐標(biāo)輪換法循環(huán)求解精確的最優(yōu)值,在這個(gè)過程中,對(duì)設(shè)計(jì)變量進(jìn)行尺度變換,以解決平移參數(shù)和旋轉(zhuǎn)參數(shù)存在量綱不一致、數(shù)量級(jí)差別較大的問題。采用這些方法,取得了較好的效果,實(shí)現(xiàn)了自由曲面的高精度匹配。
解決曲面匹配問題的關(guān)鍵是:建立測量數(shù)據(jù)與理論曲面之間的聯(lián)系,尋找測量坐標(biāo)系和設(shè)計(jì)坐標(biāo)系之間的坐標(biāo)變換矩陣,使實(shí)測曲面和理論曲面達(dá)到最大限度的重合。曲面匹配只是對(duì)測量曲面的旋轉(zhuǎn)和平移,而不會(huì)改變曲面的形狀,匹配的結(jié)果是使得理論曲面與測量曲面間的誤差最小。一般的做法是根據(jù)最小二乘準(zhǔn)則,構(gòu)造目標(biāo)函數(shù)。
假設(shè)被測曲面上面存在著M個(gè)測量點(diǎn)(,,),(i=1,…,M),將這M個(gè)理論點(diǎn)進(jìn)行坐標(biāo)平移和旋轉(zhuǎn)變換,得出一組新的測量點(diǎn)值Pi(xi,yi,zi)(i=1,…,M):
其中:
式中:x0、y0、z0、α、β、γ分別為沿x軸、y軸、z軸的平移量和旋轉(zhuǎn)量。
根據(jù)最小二乘原理,構(gòu)造優(yōu)化問題的目標(biāo)函數(shù)如下:
其中:Qi(xi,yi,zi)表示理論數(shù)據(jù)點(diǎn)的坐標(biāo),定義為理論曲面上距離Pi最近的點(diǎn) (投影點(diǎn)),可以采用文獻(xiàn)[5]介紹的快速迭代法進(jìn)行求解,文中不贅述。
當(dāng)矩陣T= [x0,y0,z0,α,β,γ]中的6個(gè)參數(shù)恰好是理論坐標(biāo)系與測量坐標(biāo)系之間的旋轉(zhuǎn)平移關(guān)系時(shí),M個(gè)新測量點(diǎn)剛好落在理論曲面上。但由于上述目標(biāo)函數(shù)是一個(gè)高度非線性函數(shù),可以采用數(shù)值迭代的方法進(jìn)行求解。
當(dāng)采用數(shù)值迭代的方法如單純形法進(jìn)行求解時(shí),必須確定迭代的初始點(diǎn),即需要先進(jìn)行曲面的粗匹配。微分進(jìn)化法[9](Differential Evolution,DE)是一種實(shí)數(shù)編碼的基于種群進(jìn)化的全局優(yōu)化算法,尤其適合解決非線性不可微連續(xù)函數(shù)的全局最小化問題,使用簡便,在收斂速度和穩(wěn)定性方面都超過了其他幾種知名的隨機(jī)算法。1996年的首屆IEEE進(jìn)化算法大賽,在所有參賽算法中,DE被證明為最快的進(jìn)化算法,隨后該算法在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用[10]。但是,將該算法應(yīng)用到曲面匹配中來,尚未見諸文獻(xiàn)報(bào)導(dǎo)。
一般的優(yōu)化方法,隨初始條件不同其優(yōu)化結(jié)果將會(huì)收斂于不同的極值點(diǎn)。測量數(shù)據(jù)的粗匹配旨在為后續(xù)迭代匹配算法向全局最優(yōu)收斂提供一個(gè)良好的初始變換。DE與迭代匹配算法相比,它無需給定初始變換估計(jì),它是在一組隨機(jī)初始條件下開始進(jìn)化的算法,其方向收斂于全局最優(yōu)點(diǎn)。結(jié)果是總能找到全局最優(yōu)點(diǎn)或接近于全局最優(yōu)點(diǎn)的解。
DE基本算法的核心思想是[10]:對(duì)種群中的每個(gè)個(gè)體i,從當(dāng)前種群中隨機(jī)選擇3個(gè)點(diǎn),以其中一個(gè)點(diǎn)為基礎(chǔ),另兩個(gè)點(diǎn)為參照作一個(gè)擾動(dòng),所得點(diǎn)與個(gè)體i交叉后“自然選擇”,保留較優(yōu),從而實(shí)現(xiàn)種群進(jìn)化。
采用微分進(jìn)化算法求解變換矩陣6個(gè)參數(shù)的流程為:
(1)初始化。設(shè)種群規(guī)模為N(通常取5k~10k,個(gè)體數(shù)量較大時(shí)可取k,文中取k=6為變量個(gè)數(shù)),交叉概率Pc(通常取0.1),交叉因子F∈ (0,1)(通常取0.5);進(jìn)化代數(shù)t=0,自變量 (變換矩陣的6個(gè)參數(shù))的下界lb和上界ub,隨機(jī)生成初始種群X(0)={X1(0),X2(0),…,XN(0)},其中Xi(0)=[(0),…,(0)]為參數(shù)向量。
(2)個(gè)體評(píng)價(jià)。計(jì)算每個(gè)個(gè)體Xi(t)的目標(biāo)適應(yīng)度函數(shù)值f(Xi(t)),并記錄。
(3)繁殖。對(duì)于種群中的每個(gè)個(gè)體Xi(t),隨機(jī)生成3個(gè)互不相同的隨機(jī)整數(shù)r1,r2,r3∈ {1,2,…,N}和隨機(jī)整數(shù)jrand∈ {1,2,…,k},則有:
(4)選擇。
(5)終止檢驗(yàn)。如果Xi(t+1)滿足終止準(zhǔn)則,則輸出Xi(t+1)中具有最小目標(biāo)值的個(gè)體作為最優(yōu)解。否則轉(zhuǎn)步驟 (2)。
以式 (3)作為目標(biāo)函數(shù),采用上述微分進(jìn)化法進(jìn)行粗匹配后,得到了包含6個(gè)參數(shù)的接近全局最優(yōu)的初始矩陣T0,作為下一步進(jìn)行精匹配的初始點(diǎn),為進(jìn)一步精確計(jì)算矩陣的6個(gè)參數(shù)創(chuàng)造了良好的條件。由于微分進(jìn)化算法采用隨機(jī)的搜索機(jī)制,因此,不能期望下次運(yùn)行得到完全相同的結(jié)果,但是每次總能得到問題的一個(gè)全局近似解??梢酝ㄟ^適當(dāng)增加種群規(guī)模和進(jìn)化代數(shù),獲得更高質(zhì)量的解。
若只采用最小二乘準(zhǔn)則,即令被測曲面的所有點(diǎn)到設(shè)計(jì)曲面的距離平方和作為目標(biāo)函數(shù) (使其最小),來調(diào)整被測曲面的位置和姿態(tài),精度不能達(dá)到很高。若單獨(dú)采用最小條件原則[11],即計(jì)算每個(gè)實(shí)測數(shù)據(jù)點(diǎn)到設(shè)計(jì)曲面的距離,取其中的最大值作為目標(biāo)函數(shù) (通過調(diào)整被測曲面的位置和姿態(tài)使目標(biāo)函數(shù)最小),精度較高。文中將這兩種方法綜合起來,能解決搜索方向單一的問題,進(jìn)一步提高匹配的精度,實(shí)現(xiàn)自由曲面的高精度匹配。
文中采用單純形法來求解最小二乘問題。單純形法的基本思想是:根據(jù)問題的維數(shù)n,選取由n+1個(gè)頂點(diǎn)構(gòu)成的單純形,求出這些頂點(diǎn)處的目標(biāo)函數(shù)值并加以比較,確定它們當(dāng)中有最大值的點(diǎn)及函數(shù)值的下降方向,再設(shè)法找到一個(gè)新的比較好的點(diǎn)替換那個(gè)有最大值的點(diǎn),從而構(gòu)成新的單純形。隨著這種取代過程的不斷進(jìn)行,新的單純形將向著極小點(diǎn)收縮。這樣經(jīng)過若干次迭代,即可得到滿足收斂準(zhǔn)則的近似解。在用單純形法解決文中所述問題時(shí),由于初始參數(shù)值離最優(yōu)值已經(jīng)非常近,所以可以很容易獲得最優(yōu)值。
文中采用坐標(biāo)輪換法來求解最小條件問題。坐標(biāo)輪換法是一種最老的多維搜索轉(zhuǎn)一維搜索的算法。它的迭代過程是沿不同的坐標(biāo)方向輪流地進(jìn)行搜索。設(shè)初始點(diǎn)為X0,先只改變一個(gè)變量,保持其他變量為常數(shù),進(jìn)行一維尋優(yōu),得到第一個(gè)最優(yōu)點(diǎn)X1;在換一個(gè)變量,同樣進(jìn)行一維搜索,得到第二個(gè)最優(yōu)點(diǎn)X2。如此繼續(xù)下去,逐步逼近獲得最優(yōu)值。文中將單純形法和坐標(biāo)輪換法結(jié)合在一起,能擴(kuò)大搜索范圍,提高優(yōu)化計(jì)算的精度。
如圖1所示,自由曲面的高精度匹配的具體流程如下:
(1)在采用微分進(jìn)化法進(jìn)行粗匹配,得到初始點(diǎn)T0的基礎(chǔ)上,首先以最小二乘準(zhǔn)則進(jìn)行曲面匹配的精匹配,即以式 (3)為目標(biāo)函數(shù),以單純形法為優(yōu)化算法,求得變換矩陣T1。
(2)以上一步的結(jié)果T1為新的初始位置,再以最小條件原則為目標(biāo)函數(shù)進(jìn)行進(jìn)一步的匹配,即以式(6)為目標(biāo)函數(shù),以坐標(biāo)輪換法為優(yōu)化算法,進(jìn)行參數(shù)優(yōu)化,進(jìn)行第二次精匹配,求得變換矩陣T2。
(3)判斷迭代精度是否滿足要求,若不滿足,以變換矩陣T2為新的初始點(diǎn),轉(zhuǎn)步驟 (1)。
(4)停止計(jì)算。
圖1 高精度曲面匹配流程圖
在優(yōu)化設(shè)計(jì)中,若目標(biāo)函數(shù)嚴(yán)重非線性,致使函數(shù)性態(tài)惡化。此時(shí)無論采用哪種優(yōu)化方法,其計(jì)算效率都不會(huì)太高,而且計(jì)算很不穩(wěn)定[12]。若能對(duì)數(shù)學(xué)模型作尺度變換,則可大大地改善其性態(tài),加速優(yōu)化計(jì)算的進(jìn)程。數(shù)學(xué)模型的尺度變換就是指通過放大或縮小各個(gè)坐標(biāo)的比例尺,從而改善數(shù)學(xué)模型性態(tài)的一種技巧。實(shí)踐證明:設(shè)計(jì)變量的量綱一化、約束條件的規(guī)格化和改變目標(biāo)函數(shù)的性態(tài),對(duì)加快優(yōu)化設(shè)計(jì)的收斂速度、提高計(jì)算的穩(wěn)定性和數(shù)值變化的靈敏性都有一定的好處,并且認(rèn)為是工程優(yōu)化設(shè)計(jì)中使用統(tǒng)一程序的一種有效的措施。在優(yōu)化設(shè)計(jì)中,確定為設(shè)計(jì)變量的幾個(gè)參數(shù),會(huì)遇到不同的量綱、不同數(shù)量級(jí)的情況。例如,文中坐標(biāo)變換矩陣的6個(gè)參數(shù),其中3個(gè)為長度單位,3個(gè)為角度單位 (rad),即平移位移和旋轉(zhuǎn)角度的量綱并不相同。作者通過實(shí)驗(yàn)發(fā)現(xiàn),若對(duì)這個(gè)問題不加以處理,將嚴(yán)重影響優(yōu)化計(jì)算的精度,因此在確定位移和角度的搜索步長時(shí)應(yīng)分別加以考慮。
通常對(duì)設(shè)計(jì)變量作尺度變換,采取量綱一化和規(guī)格化的辦法,經(jīng)過變換后,全部設(shè)計(jì)變量量綱均為一,它們的數(shù)值范圍比較接近,數(shù)量級(jí)一致。設(shè)計(jì)變量的尺度變換公式如下:
式中:x'i為變換后的設(shè)計(jì)變量;
ci為尺度變換系數(shù);
xi為變換前的設(shè)計(jì)變量。
通常取變換系數(shù):
式中:為設(shè)計(jì)變量x在優(yōu)化設(shè)計(jì)時(shí)取的初始值。若初始點(diǎn)取在接近最優(yōu)點(diǎn)處,則經(jīng)尺度變換后的設(shè)計(jì)變量值均在1的附近變動(dòng)。文中,單純形法的初始點(diǎn),為采用微分進(jìn)化法或坐標(biāo)輪換法計(jì)算的優(yōu)化結(jié)果;而坐標(biāo)輪換法的初始點(diǎn),又是采用單純形法計(jì)算的優(yōu)化結(jié)果。采用這樣的處理后,各設(shè)計(jì)變量就會(huì)規(guī)格一致,它們?cè)趦?yōu)化設(shè)計(jì)程序中的地位就較均衡,因而計(jì)算就會(huì)更順利。
為了驗(yàn)證上述匹配算法的有效性,構(gòu)造了一張控制點(diǎn)為4×4的雙三次B樣條曲面作為理論曲面,其模型如圖2所示,該B樣條曲面的16個(gè)控制點(diǎn)分別為:
圖2 雙三次B樣條曲面
在該曲面上取400個(gè)點(diǎn)進(jìn)行測試,將這些數(shù)據(jù)作為原始數(shù)據(jù),用理論方法對(duì)這些數(shù)據(jù)點(diǎn)進(jìn)行平移和旋轉(zhuǎn)。為了模擬實(shí)際測量數(shù)據(jù),對(duì)每一個(gè)測量點(diǎn)疊加上隨機(jī)誤差,該隨機(jī)誤差用正態(tài)分布N(0,0.005)生成,如圖3所示。進(jìn)行平移和旋轉(zhuǎn),并疊加上隨機(jī)誤差重新得到的數(shù)據(jù)作為曲面匹配過程的虛擬測量數(shù)據(jù)。
圖3 疊加上的隨機(jī)誤差
采用文中所介紹的算法,以Visual C++6.0為開發(fā)工具,編寫了曲面匹配的計(jì)算機(jī)程序,計(jì)算出了測量坐標(biāo)系和理論坐標(biāo)系之間的關(guān)系,以及平移、旋轉(zhuǎn)后曲面的偏差。運(yùn)用粗匹配和精匹配計(jì)算出來的理論坐標(biāo)系與測量坐標(biāo)系的關(guān)系如表1所示;精匹配后曲面的部分?jǐn)?shù)據(jù)如表2所示。從表1中可以看出:精匹配后虛擬測量數(shù)據(jù)到模型曲面的平均距離誤差為0.009 979,最大距離誤差為0.012 875,這些誤差都很小;同時(shí)由于隨機(jī)誤差和計(jì)算誤差的存在,匹配誤差很難達(dá)到零。從表2中可以看出:精匹配后虛擬測量點(diǎn)數(shù)據(jù)與理論點(diǎn)數(shù)據(jù)十分接近。因此,應(yīng)用文中算法,得到了虛擬測量點(diǎn)與理論曲面之間的精確匹配結(jié)果,實(shí)際效果如圖4所示。以上的實(shí)驗(yàn)結(jié)果表明,所采用的算法是準(zhǔn)確的、可靠的,可以方便地應(yīng)用于自由曲面的高精度匹配。
表1 測量坐標(biāo)系與理論坐標(biāo)系的關(guān)系
表2 虛擬測量點(diǎn)與理論點(diǎn)的坐標(biāo)比較
圖4 實(shí)例曲面匹配效果圖
(1)將微分進(jìn)化法 (DE)引入到曲面匹配求解過程,求出變換矩陣的初始點(diǎn),解決了ICP算法容易收斂在局部最優(yōu)點(diǎn)的問題,并克服了遺傳算法收斂效率不高的缺陷。
(2)基于最小二乘準(zhǔn)則和最小條件原則,采用兩步法即分別采用單純形法和坐標(biāo)輪換法,綜合求解曲面匹配的變換矩陣,實(shí)現(xiàn)了自由曲面的高精度匹配。
(3)在優(yōu)化算法中,對(duì)變換矩陣的6個(gè)參數(shù),即3個(gè)平移參數(shù)和3個(gè)旋轉(zhuǎn)參數(shù)采用尺度變換的方法,解決了這些參數(shù)存在的量綱不一致、數(shù)量級(jí)差別較大的問題,改善了數(shù)學(xué)模型的性態(tài)。
(4)文中所采用的幾種優(yōu)化算法,如微分進(jìn)化法、單純形法和坐標(biāo)輪換法,均有成熟的計(jì)算機(jī)程序,將其優(yōu)化組合,就可以直接使用以實(shí)現(xiàn)曲面匹配的優(yōu)化計(jì)算,方便了程序的設(shè)計(jì)開發(fā)。
[1]ZITOVA Barbara,F(xiàn)LUSSER Jan.Image Registration Methods:A Survey[J].Image and Vision Computing,2003,21(11):977-1000.
[2]BESL Paul J,MCKAY Neil D.A Method for Registration of 3-D Shapes[J].IEEE Transactions on Parern Analysis and Machine Intelligence,1992,14(2):239-256.
[3]SHARP Gregory C,LEE Sang W,WEHE David K.ICP Registration Using Invariant Features[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(1):90-102.
[4]徐毅,李澤湘.自由曲面的匹配檢測新方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2010,42(1):106-108.
[5]杜建軍,高棟,孔令豹.光學(xué)自由曲面誤差評(píng)定中匹配方法的研究[J].光學(xué)精密工程,2006,14(1):133-138.
[6]LI Yadong,GU Peihua.Free-form Surface Inspection Techniques State of the Art Review[J].Computer-Aided Design,2004,36:1395-1417.
[7]徐金亭,孫玉文,劉偉軍.復(fù)雜曲面加工檢測中的精確定位方法[J].機(jī)械工程學(xué)報(bào),2007,43(6):175-179.
[8]劉純國,劉暢,安百玲.基于遺傳算法的三維曲面配準(zhǔn)[J].鍛壓裝備與制造技術(shù),2009,44(4):110-113.
[9]STORN R,PRICE K.Differential Evolution:A Simple and Efficient Heuristic for Global Optimization over Continuous Space[J].Journal of Global Optimization,1997,11(4):341-359.
[10]陽明盛,羅長童.最優(yōu)化原理、方法及求解軟件[M].北京:科學(xué)出版社,2006:140-145.
[11]于源,盧軍,王小椿.自由曲面測量中曲面匹配的建模及算法分析[J].機(jī)械科學(xué)與技術(shù),2001,20(3):467-471.
[12]雍龍泉.優(yōu)化設(shè)計(jì)數(shù)學(xué)模型的分析與評(píng)價(jià)[J].統(tǒng)計(jì)與決策,2008(22):149-151.