陳岳坪，靳龍，李書(shū)平，宋世柳，陳藝

(1.廣西科技大學(xué)廣西汽車(chē)零部件與整車(chē)技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西柳州 545006；2.柳州市產(chǎn)品質(zhì)量監(jiān)督檢驗(yàn)所，廣西柳州 545001)

近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)自由曲面匹配的算法做了大量的研究工作［1-4］。曲面匹配主要應(yīng)用在兩個(gè)方面:(1)根據(jù)三坐標(biāo)測(cè)量機(jī)的檢測(cè)結(jié)果，對(duì)加工曲面進(jìn)行加工精度的評(píng)價(jià)［5］，由于這個(gè)過(guò)程中存在測(cè)量基準(zhǔn)與設(shè)計(jì)基準(zhǔn)不統(tǒng)一的問(wèn)題，需要進(jìn)行曲面匹配，以消除自由曲面測(cè)量中的定位誤差;(2)在數(shù)控機(jī)床上進(jìn)行自由曲面類工件的自動(dòng)定位時(shí)［6-7］，也存在測(cè)量基準(zhǔn)與加工基準(zhǔn)不統(tǒng)一的問(wèn)題，需要根據(jù)曲面匹配的結(jié)果，修正數(shù)控加工程序以進(jìn)行正確的加工。目前，迭代最近點(diǎn)算法 (Iterative Closest Point，ICP)在曲面匹配中得到了廣泛使用。但是ICP算法常常收斂于局部最優(yōu)點(diǎn)，若迭代初始點(diǎn)選擇不好，將難以求出全局最優(yōu)解。針對(duì)此問(wèn)題，文獻(xiàn) ［8］采用遺傳算法求出初始值，但遺傳算法存在著早熟收斂、后期收斂速度慢等問(wèn)題。文獻(xiàn)［5］采用基于測(cè)量數(shù)據(jù)的重心和近似法矢來(lái)確定初始點(diǎn)，但根據(jù)測(cè)量數(shù)據(jù)求曲面的重心，這種方法受到測(cè)點(diǎn)分布情況的影響，若測(cè)點(diǎn)分布不均勻，將難于確定曲面的重心。另外，在采用數(shù)學(xué)優(yōu)化算法求解坐標(biāo)變換矩陣中的過(guò)程中，由于平移參數(shù)和旋轉(zhuǎn)參數(shù)的量綱不一致、數(shù)量級(jí)差別較大，影響最終匹配精度。

針對(duì)以上存在的問(wèn)題，文中采用兩步法進(jìn)行曲面匹配，即采用粗匹配和精匹配兩個(gè)步驟來(lái)進(jìn)行逐步求精。粗匹配過(guò)程中引入微分進(jìn)化法求取迭代計(jì)算的初始點(diǎn)，即全局最優(yōu)解的近似值;精匹配是根據(jù)最小二乘原理和最小條件原則，分別采用單純形法和坐標(biāo)輪換法循環(huán)求解精確的最優(yōu)值，在這個(gè)過(guò)程中，對(duì)設(shè)計(jì)變量進(jìn)行尺度變換，以解決平移參數(shù)和旋轉(zhuǎn)參數(shù)存在量綱不一致、數(shù)量級(jí)差別較大的問(wèn)題。采用這些方法，取得了較好的效果，實(shí)現(xiàn)了自由曲面的高精度匹配。

1 問(wèn)題描述

解決曲面匹配問(wèn)題的關(guān)鍵是:建立測(cè)量數(shù)據(jù)與理論曲面之間的聯(lián)系，尋找測(cè)量坐標(biāo)系和設(shè)計(jì)坐標(biāo)系之間的坐標(biāo)變換矩陣，使實(shí)測(cè)曲面和理論曲面達(dá)到最大限度的重合。曲面匹配只是對(duì)測(cè)量曲面的旋轉(zhuǎn)和平移，而不會(huì)改變曲面的形狀，匹配的結(jié)果是使得理論曲面與測(cè)量曲面間的誤差最小。一般的做法是根據(jù)最小二乘準(zhǔn)則，構(gòu)造目標(biāo)函數(shù)。

假設(shè)被測(cè)曲面上面存在著M個(gè)測(cè)量點(diǎn)(，，)，(i=1，…，M)，將這M個(gè)理論點(diǎn)進(jìn)行坐標(biāo)平移和旋轉(zhuǎn)變換，得出一組新的測(cè)量點(diǎn)值Pi(xi，yi，zi)(i=1，…，M):

其中:

式中:x0、y0、z0、α、β、γ分別為沿x軸、y軸、z軸的平移量和旋轉(zhuǎn)量。

根據(jù)最小二乘原理，構(gòu)造優(yōu)化問(wèn)題的目標(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)系與測(cè)量坐標(biāo)系之間的旋轉(zhuǎn)平移關(guān)系時(shí)，M個(gè)新測(cè)量點(diǎn)剛好落在理論曲面上。但由于上述目標(biāo)函數(shù)是一個(gè)高度非線性函數(shù)，可以采用數(shù)值迭代的方法進(jìn)行求解。

2 基于微分進(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)題，使用簡(jiǎn)便，在收斂速度和穩(wěn)定性方面都超過(guò)了其他幾種知名的隨機(jī)算法。1996年的首屆IEEE進(jìn)化算法大賽，在所有參賽算法中，DE被證明為最快的進(jìn)化算法，隨后該算法在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用［10］。但是，將該算法應(yīng)用到曲面匹配中來(lái)，尚未見(jiàn)諸文獻(xiàn)報(bào)導(dǎo)。

一般的優(yōu)化方法，隨初始條件不同其優(yōu)化結(jié)果將會(huì)收斂于不同的極值點(diǎn)。測(cè)量數(shù)據(jù)的粗匹配旨在為后續(xù)迭代匹配算法向全局最優(yōu)收斂提供一個(gè)良好的初始變換。DE與迭代匹配算法相比，它無(wú)需給定初始變換估計(jì)，它是在一組隨機(jī)初始條件下開(kāi)始進(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é)果，但是每次總能得到問(wèn)題的一個(gè)全局近似解?？梢酝ㄟ^(guò)適當(dāng)增加種群規(guī)模和進(jìn)化代數(shù)，獲得更高質(zhì)量的解。

3 綜合最小二乘原理和最小條件原則的曲面精匹配

3.1 曲面的高精度匹配

若只采用最小二乘準(zhǔn)則，即令被測(cè)曲面的所有點(diǎn)到設(shè)計(jì)曲面的距離平方和作為目標(biāo)函數(shù) (使其最小)，來(lái)調(diào)整被測(cè)曲面的位置和姿態(tài)，精度不能達(dá)到很高。若單獨(dú)采用最小條件原則［11］，即計(jì)算每個(gè)實(shí)測(cè)數(shù)據(jù)點(diǎn)到設(shè)計(jì)曲面的距離，取其中的最大值作為目標(biāo)函數(shù) (通過(guò)調(diào)整被測(cè)曲面的位置和姿態(tài)使目標(biāo)函數(shù)最小)，精度較高。文中將這兩種方法綜合起來(lái)，能解決搜索方向單一的問(wèn)題，進(jìn)一步提高匹配的精度，實(shí)現(xiàn)自由曲面的高精度匹配。

文中采用單純形法來(lái)求解最小二乘問(wèn)題。單純形法的基本思想是:根據(jù)問(wèn)題的維數(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)成新的單純形。隨著這種取代過(guò)程的不斷進(jìn)行，新的單純形將向著極小點(diǎn)收縮。這樣經(jīng)過(guò)若干次迭代，即可得到滿足收斂準(zhǔn)則的近似解。在用單純形法解決文中所述問(wèn)題時(shí)，由于初始參數(shù)值離最優(yōu)值已經(jīng)非常近，所以可以很容易獲得最優(yōu)值。

文中采用坐標(biāo)輪換法來(lái)求解最小條件問(wèn)題。坐標(biāo)輪換法是一種最老的多維搜索轉(zhuǎn)一維搜索的算法。它的迭代過(guò)程是沿不同的坐標(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 高精度曲面匹配流程圖

3.2 數(shù)學(xué)模型的尺度變換

在優(yōu)化設(shè)計(jì)中，若目標(biāo)函數(shù)嚴(yán)重非線性，致使函數(shù)性態(tài)惡化。此時(shí)無(wú)論采用哪種優(yōu)化方法，其計(jì)算效率都不會(huì)太高，而且計(jì)算很不穩(wěn)定［12］。若能對(duì)數(shù)學(xué)模型作尺度變換，則可大大地改善其性態(tài)，加速優(yōu)化計(jì)算的進(jìn)程。數(shù)學(xué)模型的尺度變換就是指通過(guò)放大或縮小各個(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è)為長(zhǎng)度單位，3個(gè)為角度單位 (rad)，即平移位移和旋轉(zhuǎn)角度的量綱并不相同。作者通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，若對(duì)這個(gè)問(wèn)題不加以處理，將嚴(yán)重影響優(yōu)化計(jì)算的精度，因此在確定位移和角度的搜索步長(zhǎng)時(shí)應(yīng)分別加以考慮。

通常對(duì)設(shè)計(jì)變量作尺度變換，采取量綱一化和規(guī)格化的辦法，經(jīng)過(guò)變換后，全部設(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ì)更順利。

4 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證上述匹配算法的有效性，構(gòu)造了一張控制點(diǎn)為4×4的雙三次B樣條曲面作為理論曲面，其模型如圖2所示，該B樣條曲面的16個(gè)控制點(diǎn)分別為:

圖2 雙三次B樣條曲面

在該曲面上取400個(gè)點(diǎn)進(jìn)行測(cè)試，將這些數(shù)據(jù)作為原始數(shù)據(jù)，用理論方法對(duì)這些數(shù)據(jù)點(diǎn)進(jìn)行平移和旋轉(zhuǎn)。為了模擬實(shí)際測(cè)量數(shù)據(jù)，對(duì)每一個(gè)測(cè)量點(diǎn)疊加上隨機(jī)誤差，該隨機(jī)誤差用正態(tài)分布N(0，0.005)生成，如圖3所示。進(jìn)行平移和旋轉(zhuǎn)，并疊加上隨機(jī)誤差重新得到的數(shù)據(jù)作為曲面匹配過(guò)程的虛擬測(cè)量數(shù)據(jù)。

圖3 疊加上的隨機(jī)誤差

采用文中所介紹的算法，以Visual C++6.0為開(kāi)發(fā)工具，編寫(xiě)了曲面匹配的計(jì)算機(jī)程序，計(jì)算出了測(cè)量坐標(biāo)系和理論坐標(biāo)系之間的關(guān)系，以及平移、旋轉(zhuǎn)后曲面的偏差。運(yùn)用粗匹配和精匹配計(jì)算出來(lái)的理論坐標(biāo)系與測(cè)量坐標(biāo)系的關(guān)系如表1所示;精匹配后曲面的部分?jǐn)?shù)據(jù)如表2所示。從表1中可以看出:精匹配后虛擬測(cè)量數(shù)據(jù)到模型曲面的平均距離誤差為0.009 979，最大距離誤差為0.012 875，這些誤差都很小;同時(shí)由于隨機(jī)誤差和計(jì)算誤差的存在，匹配誤差很難達(dá)到零。從表2中可以看出:精匹配后虛擬測(cè)量點(diǎn)數(shù)據(jù)與理論點(diǎn)數(shù)據(jù)十分接近。因此，應(yīng)用文中算法，得到了虛擬測(cè)量點(diǎn)與理論曲面之間的精確匹配結(jié)果，實(shí)際效果如圖4所示。以上的實(shí)驗(yàn)結(jié)果表明，所采用的算法是準(zhǔn)確的、可靠的，可以方便地應(yīng)用于自由曲面的高精度匹配。

表1 測(cè)量坐標(biāo)系與理論坐標(biāo)系的關(guān)系

表2 虛擬測(cè)量點(diǎn)與理論點(diǎn)的坐標(biāo)比較

圖4 實(shí)例曲面匹配效果圖

5 結(jié)論

(1)將微分進(jìn)化法 (DE)引入到曲面匹配求解過(guò)程，求出變換矩陣的初始點(diǎn)，解決了ICP算法容易收斂在局部最優(yōu)點(diǎn)的問(wè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í)差別較大的問(wèn)題，改善了數(shù)學(xué)模型的性態(tài)。

(4)文中所采用的幾種優(yōu)化算法，如微分進(jìn)化法、單純形法和坐標(biāo)輪換法，均有成熟的計(jì)算機(jī)程序，將其優(yōu)化組合，就可以直接使用以實(shí)現(xiàn)曲面匹配的優(yōu)化計(jì)算，方便了程序的設(shè)計(jì)開(kāi)發(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］徐毅，李澤湘.自由曲面的匹配檢測(cè)新方法［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ù)雜曲面加工檢測(cè)中的精確定位方法［J］.機(jī)械工程學(xué)報(bào)，2007，43(6):175-179.

［8］劉純國(guó)，劉暢，安百玲.基于遺傳算法的三維曲面配準(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áng)明盛，羅長(zhǎng)童.最優(yōu)化原理、方法及求解軟件［M］.北京:科學(xué)出版社，2006:140-145.

［11］于源，盧軍，王小椿.自由曲面測(cè)量中曲面匹配的建模及算法分析［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.