陳岳坪，靳龍，李書平，宋世柳，陳藝

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

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

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

1 問題描述

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

假設被測曲面上面存在著M個測量點(，，)，(i=1，…，M)，將這M個理論點進行坐標平移和旋轉變換，得出一組新的測量點值Pi(xi，yi，zi)(i=1，…，M):

其中:

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

根據(jù)最小二乘原理，構造優(yōu)化問題的目標函數(shù)如下:

其中:Qi(xi，yi，zi)表示理論數(shù)據(jù)點的坐標，定義為理論曲面上距離Pi最近的點 (投影點)，可以采用文獻［5］介紹的快速迭代法進行求解，文中不贅述。

當矩陣T= ［x0，y0，z0，α，β，γ］中的6個參數(shù)恰好是理論坐標系與測量坐標系之間的旋轉平移關系時，M個新測量點剛好落在理論曲面上。但由于上述目標函數(shù)是一個高度非線性函數(shù)，可以采用數(shù)值迭代的方法進行求解。

2 基于微分進化法的曲面粗匹配

當采用數(shù)值迭代的方法如單純形法進行求解時，必須確定迭代的初始點，即需要先進行曲面的粗匹配。微分進化法［9］(Differential Evolution，DE)是一種實數(shù)編碼的基于種群進化的全局優(yōu)化算法，尤其適合解決非線性不可微連續(xù)函數(shù)的全局最小化問題，使用簡便，在收斂速度和穩(wěn)定性方面都超過了其他幾種知名的隨機算法。1996年的首屆IEEE進化算法大賽，在所有參賽算法中，DE被證明為最快的進化算法，隨后該算法在各個領域得到了廣泛的應用［10］。但是，將該算法應用到曲面匹配中來，尚未見諸文獻報導。

一般的優(yōu)化方法，隨初始條件不同其優(yōu)化結果將會收斂于不同的極值點。測量數(shù)據(jù)的粗匹配旨在為后續(xù)迭代匹配算法向全局最優(yōu)收斂提供一個良好的初始變換。DE與迭代匹配算法相比，它無需給定初始變換估計，它是在一組隨機初始條件下開始進化的算法，其方向收斂于全局最優(yōu)點。結果是總能找到全局最優(yōu)點或接近于全局最優(yōu)點的解。

DE基本算法的核心思想是［10］:對種群中的每個個體i，從當前種群中隨機選擇3個點，以其中一個點為基礎，另兩個點為參照作一個擾動，所得點與個體i交叉后“自然選擇”，保留較優(yōu)，從而實現(xiàn)種群進化。

采用微分進化算法求解變換矩陣6個參數(shù)的流程為:

(1)初始化。設種群規(guī)模為N(通常取5k～10k，個體數(shù)量較大時可取k，文中取k=6為變量個數(shù))，交叉概率Pc(通常取0.1)，交叉因子F∈ (0，1)(通常取0.5);進化代數(shù)t=0，自變量 (變換矩陣的6個參數(shù))的下界lb和上界ub，隨機生成初始種群X(0)={X1(0)，X2(0)，…，XN(0)}，其中Xi(0)=［(0)，…，(0)］為參數(shù)向量。

(2)個體評價。計算每個個體Xi(t)的目標適應度函數(shù)值f(Xi(t))，并記錄。

(3)繁殖。對于種群中的每個個體Xi(t)，隨機生成3個互不相同的隨機整數(shù)r1，r2，r3∈ {1，2，…，N}和隨機整數(shù)jrand∈ {1，2，…，k}，則有:

(4)選擇。

(5)終止檢驗。如果Xi(t+1)滿足終止準則，則輸出Xi(t+1)中具有最小目標值的個體作為最優(yōu)解。否則轉步驟 (2)。

以式 (3)作為目標函數(shù)，采用上述微分進化法進行粗匹配后，得到了包含6個參數(shù)的接近全局最優(yōu)的初始矩陣T0，作為下一步進行精匹配的初始點，為進一步精確計算矩陣的6個參數(shù)創(chuàng)造了良好的條件。由于微分進化算法采用隨機的搜索機制，因此，不能期望下次運行得到完全相同的結果，但是每次總能得到問題的一個全局近似解?？梢酝ㄟ^適當增加種群規(guī)模和進化代數(shù)，獲得更高質量的解。

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

3.1 曲面的高精度匹配

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

文中采用單純形法來求解最小二乘問題。單純形法的基本思想是:根據(jù)問題的維數(shù)n，選取由n+1個頂點構成的單純形，求出這些頂點處的目標函數(shù)值并加以比較，確定它們當中有最大值的點及函數(shù)值的下降方向，再設法找到一個新的比較好的點替換那個有最大值的點，從而構成新的單純形。隨著這種取代過程的不斷進行，新的單純形將向著極小點收縮。這樣經(jīng)過若干次迭代，即可得到滿足收斂準則的近似解。在用單純形法解決文中所述問題時，由于初始參數(shù)值離最優(yōu)值已經(jīng)非常近，所以可以很容易獲得最優(yōu)值。

文中采用坐標輪換法來求解最小條件問題。坐標輪換法是一種最老的多維搜索轉一維搜索的算法。它的迭代過程是沿不同的坐標方向輪流地進行搜索。設初始點為X0，先只改變一個變量，保持其他變量為常數(shù)，進行一維尋優(yōu)，得到第一個最優(yōu)點X1;在換一個變量，同樣進行一維搜索，得到第二個最優(yōu)點X2。如此繼續(xù)下去，逐步逼近獲得最優(yōu)值。文中將單純形法和坐標輪換法結合在一起，能擴大搜索范圍，提高優(yōu)化計算的精度。

如圖1所示，自由曲面的高精度匹配的具體流程如下:

(1)在采用微分進化法進行粗匹配，得到初始點T0的基礎上，首先以最小二乘準則進行曲面匹配的精匹配，即以式 (3)為目標函數(shù)，以單純形法為優(yōu)化算法，求得變換矩陣T1。

(2)以上一步的結果T1為新的初始位置，再以最小條件原則為目標函數(shù)進行進一步的匹配，即以式(6)為目標函數(shù)，以坐標輪換法為優(yōu)化算法，進行參數(shù)優(yōu)化，進行第二次精匹配，求得變換矩陣T2。

(3)判斷迭代精度是否滿足要求，若不滿足，以變換矩陣T2為新的初始點，轉步驟 (1)。

(4)停止計算。

圖1 高精度曲面匹配流程圖

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

在優(yōu)化設計中，若目標函數(shù)嚴重非線性，致使函數(shù)性態(tài)惡化。此時無論采用哪種優(yōu)化方法，其計算效率都不會太高，而且計算很不穩(wěn)定［12］。若能對數(shù)學模型作尺度變換，則可大大地改善其性態(tài)，加速優(yōu)化計算的進程。數(shù)學模型的尺度變換就是指通過放大或縮小各個坐標的比例尺，從而改善數(shù)學模型性態(tài)的一種技巧。實踐證明:設計變量的量綱一化、約束條件的規(guī)格化和改變目標函數(shù)的性態(tài)，對加快優(yōu)化設計的收斂速度、提高計算的穩(wěn)定性和數(shù)值變化的靈敏性都有一定的好處，并且認為是工程優(yōu)化設計中使用統(tǒng)一程序的一種有效的措施。在優(yōu)化設計中，確定為設計變量的幾個參數(shù)，會遇到不同的量綱、不同數(shù)量級的情況。例如，文中坐標變換矩陣的6個參數(shù)，其中3個為長度單位，3個為角度單位 (rad)，即平移位移和旋轉角度的量綱并不相同。作者通過實驗發(fā)現(xiàn)，若對這個問題不加以處理，將嚴重影響優(yōu)化計算的精度，因此在確定位移和角度的搜索步長時應分別加以考慮。

通常對設計變量作尺度變換，采取量綱一化和規(guī)格化的辦法，經(jīng)過變換后，全部設計變量量綱均為一，它們的數(shù)值范圍比較接近，數(shù)量級一致。設計變量的尺度變換公式如下:

式中:x'i為變換后的設計變量;

ci為尺度變換系數(shù);

xi為變換前的設計變量。

通常取變換系數(shù):

式中:為設計變量x在優(yōu)化設計時取的初始值。若初始點取在接近最優(yōu)點處，則經(jīng)尺度變換后的設計變量值均在1的附近變動。文中，單純形法的初始點，為采用微分進化法或坐標輪換法計算的優(yōu)化結果;而坐標輪換法的初始點，又是采用單純形法計算的優(yōu)化結果。采用這樣的處理后，各設計變量就會規(guī)格一致，它們在優(yōu)化設計程序中的地位就較均衡，因而計算就會更順利。

4 實驗驗證

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

圖2 雙三次B樣條曲面

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

圖3 疊加上的隨機誤差

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

表1 測量坐標系與理論坐標系的關系

表2 虛擬測量點與理論點的坐標比較

圖4 實例曲面匹配效果圖

5 結論

(1)將微分進化法 (DE)引入到曲面匹配求解過程，求出變換矩陣的初始點，解決了ICP算法容易收斂在局部最優(yōu)點的問題，并克服了遺傳算法收斂效率不高的缺陷。

(2)基于最小二乘準則和最小條件原則，采用兩步法即分別采用單純形法和坐標輪換法，綜合求解曲面匹配的變換矩陣，實現(xiàn)了自由曲面的高精度匹配。

(3)在優(yōu)化算法中，對變換矩陣的6個參數(shù)，即3個平移參數(shù)和3個旋轉參數(shù)采用尺度變換的方法，解決了這些參數(shù)存在的量綱不一致、數(shù)量級差別較大的問題，改善了數(shù)學模型的性態(tài)。

(4)文中所采用的幾種優(yōu)化算法，如微分進化法、單純形法和坐標輪換法，均有成熟的計算機程序，將其優(yōu)化組合，就可以直接使用以實現(xiàn)曲面匹配的優(yōu)化計算，方便了程序的設計開發(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è)大學學報，2010，42(1):106-108.

［5］杜建軍，高棟，孔令豹.光學自由曲面誤差評定中匹配方法的研究［J］.光學精密工程，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］徐金亭，孫玉文，劉偉軍.復雜曲面加工檢測中的精確定位方法［J］.機械工程學報，2007，43(6):175-179.

［8］劉純國，劉暢，安百玲.基于遺傳算法的三維曲面配準［J］.鍛壓裝備與制造技術，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］.北京:科學出版社，2006:140-145.

［11］于源，盧軍，王小椿.自由曲面測量中曲面匹配的建模及算法分析［J］.機械科學與技術，2001，20(3):467-471.

［12］雍龍泉.優(yōu)化設計數(shù)學模型的分析與評價［J］.統(tǒng)計與決策，2008(22):149-151.