基于遺傳算法的三維模型匹配方法

葉建華， 高誠輝， 江吉彬

(1. 福州大學(xué)機(jī)械工程及自動化學(xué)院，福建 福州 350108；2. 福建工程學(xué)院機(jī)械與汽車工程學(xué)院，福建 福州 350108)

基于遺傳算法的三維模型匹配方法

葉建華1,2， 高誠輝1， 江吉彬2

(1. 福州大學(xué)機(jī)械工程及自動化學(xué)院，福建 福州 350108；2. 福建工程學(xué)院機(jī)械與汽車工程學(xué)院，福建 福州 350108)

逆向測量模型與正向設(shè)計(jì)模型的自動匹配是三維檢測的關(guān)鍵技術(shù)之一。通過空間六自由度的旋轉(zhuǎn)與平移變換調(diào)整模型方位，基于K-D樹和拓?fù)湫畔@取三維模型與不同方位平面的相交輪廓。利用二維相交輪廓的差異度作為兩模型間的匹配判據(jù)，避免海量數(shù)據(jù)點(diǎn)與復(fù)雜曲面間的直接匹配計(jì)算。采用遺傳算法進(jìn)行兩模型最佳匹配方位的求解，以空間六自由度為個體的染色體，通過群體的多點(diǎn)搜索，歷經(jīng)選擇、交叉、變異操作，得到全局最佳匹配方位。通過實(shí)例驗(yàn)證了方法的有效性。

模型匹配；三維模型；遺傳算法；歸一化

隨著自由曲面在汽車、船舶、航空、航天和模具等領(lǐng)域的廣泛應(yīng)用，對其制造精度的檢測也變得越發(fā)重要。由于傳統(tǒng)的自由曲面檢測方法需要有足夠的測量空間、確定的測量基準(zhǔn)和專用的模板檢具，難以實(shí)現(xiàn)高精、高效測量。而隨著三維數(shù)字化掃描精度、測量效率的不斷提高，三維檢測技術(shù)得到快速發(fā)展與應(yīng)用。三維檢測技術(shù)采用三維數(shù)字化掃描設(shè)備獲取零部件的三維網(wǎng)格測量模型，并與正向設(shè)計(jì)的數(shù)字化模型進(jìn)行匹配，進(jìn)而通過誤差分析評估制造精度。其中三維網(wǎng)格測量模型與正向設(shè)計(jì)CAD模型的匹配是三維檢測技術(shù)的關(guān)鍵。

模型匹配的目的在于建立一致的誤差分析基準(zhǔn)。由于從三維數(shù)字化掃描設(shè)備所獲得海量點(diǎn)云數(shù)據(jù)構(gòu)成的三角網(wǎng)格數(shù)據(jù)模型與正向設(shè)計(jì)的三維CAD模型之間的坐標(biāo)系統(tǒng)沒有任何關(guān)聯(lián)，因此，在分析之前需要匹配兩模型的方位，實(shí)現(xiàn)測量坐標(biāo)系與設(shè)計(jì)坐標(biāo)系的統(tǒng)一。目前，基于形狀的自適應(yīng)匹配方法[1]是模型匹配的研究重點(diǎn)，諸多學(xué)者開展了相關(guān)研究。常用的主元分析法(principal component analysis，PCA)[2]通過主軸進(jìn)行匹配，提供了每根主軸的方向，但當(dāng)模型采樣不一致時，會導(dǎo)致主軸的不確定，主要作為初匹配方法。傳統(tǒng)的迭代近鄰點(diǎn)算法(iterative closest point，ICP)[3]是基于優(yōu)化理論對海量數(shù)據(jù)點(diǎn)進(jìn)行近鄰匹配調(diào)整，是一種精確匹配方法，但該方法易受初始點(diǎn)云位置的影響，不能保證收斂。Claudet[4]提出的基于點(diǎn)云與 NURBS曲面的匹配方法、Pottmann和Leopoldseder[5]提出的基于點(diǎn)云速度場的配準(zhǔn)方法是直接基于三維信息進(jìn)行匹配，處理的數(shù)據(jù)量大，算法的收斂性及效率不易保證。由于二維圖形圖像處理技術(shù)的研究已較成熟，且算法簡單，出現(xiàn)了基于視覺圖像相似性實(shí)現(xiàn)標(biāo)準(zhǔn)化坐標(biāo)系的方法[6]，通過模型的自動旋轉(zhuǎn)和多視點(diǎn)圖像的比較，將坐標(biāo)系逐漸標(biāo)準(zhǔn)化，該方法是一種窮舉搜索法。遺傳算法(genetic algorithm, GA)是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的全局搜索算法，它采用群體的方式進(jìn)行多點(diǎn)搜索，經(jīng)交叉操作實(shí)現(xiàn)個體的遺傳進(jìn)化逐步產(chǎn)生最優(yōu)個體，并利用變異操作避免陷入局部極值。鑒于上述算法的不足，結(jié)合二維圖形算法的高效性和遺傳算法的魯棒性，本文提出通過三維模型不同方位的二維輪廓圖進(jìn)行匹配度評測，并采用遺傳算法進(jìn)行兩數(shù)據(jù)模型最佳匹配方位的全局搜索，從而實(shí)現(xiàn)匹配算法的效率與魯棒性。

1 匹配模型建立

模型匹配就是在三維空間中求解兩模型的最佳一致姿勢方位。設(shè)測量獲得的三角網(wǎng)格模型為調(diào)整模型 A，正向設(shè)計(jì)的數(shù)字化模型為參考模型S，則模型匹配過程就是在參考模型S固定不動的情況下，通過旋轉(zhuǎn)、平移操作將原本處在任意位置、姿態(tài)的調(diào)整模型A調(diào)整到與參考模型S相一致的位置。也就是要使以下目標(biāo)函數(shù)最?。?/p>

其中ia為模型A的頂點(diǎn)；si為ai到參考模型S的最近點(diǎn)；R為調(diào)整姿態(tài)的旋轉(zhuǎn)變換矩陣：

α、β、γ為模型A分別繞Z、Y、X軸旋轉(zhuǎn)角度；T為調(diào)整位置的平移變換矩陣：

l、m、n為模型A沿X、Y、Z三個坐標(biāo)方向的平移量。

可知，兩模型的匹配，就是要找到一組α、β、γ、l、m、n值，使得ε最小。

2 匹配度評測方法

ε值的計(jì)算過程也就是兩模型方位匹配度的評測過程。正向設(shè)計(jì)模型是包含自由曲面的復(fù)雜CAD模型，逆向測量模型是包含海量數(shù)據(jù)點(diǎn)的三角網(wǎng)格模型，若直接基于三維數(shù)據(jù)模型進(jìn)行匹配度評測值ε的計(jì)算，則計(jì)算方法復(fù)雜、效率低下。為了簡化ε值的計(jì)算復(fù)雜度、提高算法效率，本文把三維模型的匹配度ε評測，轉(zhuǎn)化成二維相交輪廓圖的相似度D的評測。算法的基本思路為：把正向的CAD模型S進(jìn)行離散化得到三角網(wǎng)格數(shù)據(jù)模型S′，然后用不同方位的平面與三角網(wǎng)格數(shù)據(jù)模型 A、S′進(jìn)行求交，得到相交的二維輪廓圖，接著基于這些二維輪廓圖定義定量的度量標(biāo)準(zhǔn)和匹配度評測方法。

2.1 三維CAD模型網(wǎng)格化

為了不同方位的平面與三角網(wǎng)格數(shù)據(jù)模型A、正向的CAD模型S的求交方法的統(tǒng)一，需要將正向設(shè)計(jì)的三維CAD模型S離散，并轉(zhuǎn)化成三角網(wǎng)格模型S′。三維CAD模型是由NURBS曲面包裹而成，模型的網(wǎng)格化也就是對多張NURBS曲面的離散和離散點(diǎn)的三角化剖分。

NURBS曲面的參數(shù)化表達(dá)式[7]為：

式中， Qij( i =0,1,… ,n; j =0,1,… ,m)為網(wǎng)格控制頂點(diǎn)， Wij( i =0,1,… ,n; j =0,1,… ,m)為網(wǎng)絡(luò)控制點(diǎn)的權(quán)值， Ni,k(u)為NURBS曲面u參數(shù)方向的B樣條基函數(shù)，Nj,l(v)為NURBS曲面v參數(shù)方向的B樣條基函數(shù)，k、l為B樣條基函數(shù)的階次。

由式(2)可知，對NURBS曲面的三角網(wǎng)格化可以轉(zhuǎn)化為：先在參數(shù)域上對 u∈ [0,1]，v ∈ [0,1]的二維平面進(jìn)行離散并網(wǎng)格化，然后從參數(shù)域映射回歐式空間實(shí)現(xiàn)NURBS曲面的網(wǎng)格化。在參數(shù)域上進(jìn)行離散時，為了實(shí)現(xiàn)三角面片的粒度與掃描獲得的一致，確定u、v方向的平均初始離散步長 Δu 、Δv為：

式中，Area為 NURBS曲面控制多邊形網(wǎng)格的面積，a rea _ trii( i = 0,1,… ,N)為三角網(wǎng)格模型A中三角面片的面積。在離散過程中通過曲率半徑值調(diào)整離散步長 Δu、 Δv：若 Δu＞ K ρu,Δu= K ρu；若Δv＞ K ρv,Δv= K ρv；ρu和 ρv分別為上一離散點(diǎn)沿u、v方向的曲率半徑，K為比例系數(shù)。對離散獲得的采樣點(diǎn)，根據(jù)鄰接關(guān)系進(jìn)行三角化剖分，從而得到參數(shù)域上的網(wǎng)格剖分結(jié)果。然后通過式(2)映射回歐式空間得到每張 NURBS曲面的網(wǎng)格模型子集。對網(wǎng)格模型子集進(jìn)行拼接即可得到三角網(wǎng)格化模型S′。

2.2 截交平面

由于用同一組包含不同方位的平面去截取不同位置、姿勢的三維模型所得的相交輪廓會有差異，因此，提出利用相交輪廓的差異度來度量兩模型的匹配度。采用參考模型坐標(biāo)系統(tǒng)的三個正交面和模型包圍盒縮小 1/3得到正六面體的表面延伸面作為獲取三維模型輪廓圖的切割平面，所得到的相交輪廓能同時反映模型的總體特征和局部細(xì)節(jié)特征。其中參考模型坐標(biāo)系統(tǒng)的原點(diǎn)設(shè)置在模型包圍盒的中心。在最佳一致位置的求解過程，模型 A的位置與姿勢需要不斷地調(diào)整。由于模型 A包含的數(shù)據(jù)量大，相應(yīng)的調(diào)整過程計(jì)算量也大，而平面的方位調(diào)整卻很簡單，因此本文采用切割平面的逆向變換來實(shí)現(xiàn)求解過程模型 A的不變換。即把由α、β、γ、l、m、n確定的調(diào)整模型A相對原點(diǎn)的旋轉(zhuǎn)、平移變換A· R· T轉(zhuǎn)化成由-α 、-β、-γ、-l、-m、-n值確定的上述9個切割平面的逆變換Planes· T ′·R ′，即調(diào)整模型A的切割平面為： Plani′ = Planei· T ′·R ′,(i =1,… ,9)。

2.3 三維網(wǎng)格模型與平面求交

二維輪廓圖是通過三角網(wǎng)格模型S′、A與二維平面求交獲得的。三角網(wǎng)格模型S′作為參考模型只需在初始時與上述 9個平面進(jìn)行求交計(jì)算，而調(diào)整模型A在匹配過程中需要與不同方位的9個切割平面進(jìn)行頻繁地求交計(jì)算，求交算法效率直接決定著整個匹配方法的效率。為了保證效率，本文提出采用 K-D樹檢索每個相交輪廓的第一條邊，進(jìn)而利用拓?fù)潢P(guān)系搜索出其余相交邊的方法。以調(diào)整模型A與切割平面 Plani′為例進(jìn)行求交算法的說明：

(1) 建立調(diào)整模型 A的 K-D樹。樹節(jié)點(diǎn)為 q的K-D樹具有時間復(fù)雜度為O( log2q)[8]的搜索速度。K-D樹的每個節(jié)點(diǎn)在三維空間上表現(xiàn)為空間六面體，包含著屬于這一節(jié)點(diǎn)的三角面片序列，同層節(jié)點(diǎn)通過平面識別器進(jìn)行分割，并記錄著指向下一層的左子樹指針和右子樹指針。根據(jù)調(diào)整模型 A所包含的三角面片規(guī)模確定最大層數(shù)和每個六面體節(jié)點(diǎn)中包含的三角面片個數(shù)。K-D樹的根節(jié)點(diǎn)就是包含網(wǎng)格模型 A的所有三角面片的包圍盒，樹的建構(gòu)過程為：判別三角面片是在識別器平面哪一側(cè)，根據(jù)判別結(jié)果歸類到左、右子樹三角面片序列中，如果三角面片與識別器平面相交則同時記錄到左、右子樹三角面片序列中；逐層遞歸分解，從而建構(gòu)起一顆完整的K-D樹。

(2) 利用K-D樹檢索每個輪廓的第一條邊。逐層判斷切割平面 Plani′與節(jié)點(diǎn)平面識別器的關(guān)系，如果不相交則判斷在哪一側(cè)；如果相交則求出交線，后續(xù)則用交線分割后的半平面去與平面識別器做判斷；通過逐層判斷獲得切割平面 Plani′跨過的空間六面體所對應(yīng)的葉節(jié)點(diǎn)。從葉節(jié)點(diǎn)中得到這一節(jié)點(diǎn)所包含的三角面片序列，并與切割平面Plani′求交，從而獲得與 Plani′相交的第一條邊。往往調(diào)整模型 A與切割平面 Plani′存在多個相交環(huán)，求得相交環(huán)后，還要重復(fù)去判斷是否存在未求交過的三角形與切割平面 Plani′存在相交，從而獲得下一個環(huán)的第一條邊。

(3) 建立網(wǎng)格的拓?fù)湫畔ⅰＭ負(fù)湫畔⒁簿褪峭負(fù)湓氐念愋?、個數(shù)以及相互之間關(guān)系的表達(dá)。通過拓?fù)湫畔⒖梢钥焖俚孬@得與拓?fù)湓叵噜彽膸缀卧亍Ｔ诰W(wǎng)格模型的拓?fù)湫畔⒅薪?gòu)以下拓?fù)潢P(guān)系：頂點(diǎn)相關(guān)的一階領(lǐng)域邊；邊所包含的兩頂點(diǎn)；邊所對應(yīng)的左、右三角面片；三角面片所包含的頂點(diǎn)與邊。

(4) 利用拓?fù)湫畔⑺阉鞒銎溆嘞嘟贿?。以第一條邊為搜索起點(diǎn)，利用拓?fù)潢P(guān)系獲得邊所對應(yīng)的三角面片，進(jìn)而獲得三角面片所對應(yīng)的其他邊和頂點(diǎn)，并與切割平面iPlan′求交獲得下一相交邊；如果交點(diǎn)落在頂點(diǎn)上，則通過頂點(diǎn)獲得其一階領(lǐng)域邊與切割平面iPlan′求交獲得下一相交邊。不斷重復(fù)上述過程，直到又找到搜索起點(diǎn)邊或向兩個方向都找到邊界邊為止。求出與切割平面iPlan′相交的所有交點(diǎn)ikCa，即可得到一個完整的相交截面輪廓iCa。為了下個環(huán)第一條邊的計(jì)算效率，求過交的邊和所在的三角面片做已計(jì)算標(biāo)記。

(5) 重復(fù)步驟(2)和(4)求出所有相交輪廓。

2.4 一致性判據(jù)

兩模型位置與姿勢的匹配程度通過截面輪廓圖的相似度進(jìn)行定量分析，而截面輪廓圖相似度的評測一般由距離、邊長、面積、角度等來度量。為了兼顧效率和魯棒性，本文在截面輪廓點(diǎn)Huasdorff距離[9]的基礎(chǔ)上，加入邊長差來度量兩個模型間的相似度：

其中， Csij、 Caik為參考模型S′、調(diào)整模型A與第i個截交面的交點(diǎn)， Csi、 Cai為參考模型S′、調(diào)整模型A與第i個切割面的相交多邊形輪廓；DH為兩個截交面輪廓點(diǎn)集中任意兩點(diǎn) Huasdorff距離的度量； LC為兩個截面輪廓 Csi、 Cai的邊長差的度量。R、T的變換變量值由α、β、γ、l、m、n確定。對 Caik和 Cai進(jìn)行坐標(biāo)變換的目的是把調(diào)整模型A與第i個切割面的截交點(diǎn)和截交輪廓變換到統(tǒng)一的坐標(biāo)系統(tǒng)下進(jìn)行相似度計(jì)算。

3 基于遺傳算法的匹配

遺傳算法[10]具有很強(qiáng)的魯棒性，將其應(yīng)用到兩模型匹配上的基本流程為：對α、β、γ、l、m、n六個參量進(jìn)行編碼，進(jìn)而產(chǎn)生初始群體；把兩個模型間的相似度值D作為個體適應(yīng)度的判斷依據(jù)，歷經(jīng)選擇算子、交叉算子、變異算子的遺傳操作實(shí)現(xiàn)群體的進(jìn)化，從而實(shí)現(xiàn)兩模型的最優(yōu)匹配。

3.1 編碼

六個調(diào)整參量中，旋轉(zhuǎn)調(diào)整量α、β、γ的最大取值區(qū)間為[- π,π]，平移調(diào)整量l、m、n的取值由兩匹配模型的最小包圍盒大小決定。六個參量α、β、γ、l、m、n在取值范圍內(nèi)任意值的組合為一個體。調(diào)整量的具體取值因模型而異，取值區(qū)間越小越容易收斂?；谡{(diào)整參量的取值特點(diǎn)，采用歸一化的浮點(diǎn)數(shù)編碼方法進(jìn)行編碼，并隨機(jī)產(chǎn)生M個初始個體。設(shè)某一個體的六個調(diào)整參量值為x1, x2,x3, x4,x5,x6，則個體的表現(xiàn)型描述為：X =[x1, x2,x3, x4,x5,x6]；對應(yīng)的基因型為：T =[t1, t2, t3, t4, t5, t6]，其中bi、 ai是 xi的上下限。

3.2 適應(yīng)度函數(shù)

兩模型匹配的目的在于目標(biāo)函數(shù)值D最小，且D值恒為正，因此目標(biāo)函數(shù) D( X)可以直接對應(yīng)到搜索空間作為適應(yīng)度函數(shù)： E( T ) = D( X)。而為了維護(hù)早期群體的多樣性和避免早熟以及后期階段個體間的無序競爭，對適應(yīng)度尺度進(jìn)行變換：E ′= exp(- δ E)，其中δ為尺度系數(shù)。

3.3 遺傳算子設(shè)計(jì)

(1) 選擇算子：根據(jù)群體中的個體適應(yīng)度進(jìn)行優(yōu)勝劣汰。采用無回放式余數(shù)隨機(jī)選擇的方法[11]選擇遺傳到下一代的個體，以保證適應(yīng)度值較大的一些個體能得到繁殖。首先，根據(jù)個體的適應(yīng)度值占群體總適應(yīng)度值的比例，計(jì)算該個體在下一代群體中的生存期望數(shù)目 ENi：

然后，用 ENi的整數(shù)部分確定該個體遺傳到下一代的數(shù)目，從而確定出個個體遺傳到下一代。剩余的個個體通過新的適應(yīng)度值按選中概率與新適應(yīng)度值的大小成正比的方法通過賭盤進(jìn)行隨機(jī)確定。

(2) 交叉算子：是GA產(chǎn)生新個體的主要方法，對遺傳下來的個體以隨機(jī)的方式兩兩組成交叉組，通過線性組合的方式進(jìn)行交叉操作。設(shè)第g代的兩個隨機(jī)配對的個體則交叉操作后產(chǎn)生的新個體為：

其中σ為[0,1]上產(chǎn)生的隨機(jī)數(shù)。產(chǎn)生的新個體要進(jìn)行有效性判斷，避免越界。交叉概率太大容易引起搜索過程的隨機(jī)化，太小則容易引起早熟，本文取 Pc= 0.86。

(3) 變異算子：是產(chǎn)生新個體能力的輔助方法，目的在于改善局部搜索能力和避免早熟。采用均勻變異方法增加群體的多樣性，依次指定個體染色體中的基因作為變異點(diǎn)，以變異概率 Pm確定該點(diǎn)是否進(jìn)行基因變異，對要變異的基因進(jìn)行隨機(jī)變異。設(shè)個體 Tc在 tk處變異，隨機(jī)變異的新基因值 tk′ = τ，τ為[0,1]上的隨機(jī)數(shù)。取變異概率Pm= 0.068。

4 應(yīng)用實(shí)例

利用Visual C++語言，在OpenGL技術(shù)的支持下開發(fā)了原型系統(tǒng)，驗(yàn)證了本文方法的可行性。圖1是渦輪葉片的匹配實(shí)例。圖1(a)為正向設(shè)計(jì)軟件 Pro/ENGINEER creo 2.0建立的渦輪葉片三維CAD模型；圖1(b)為離散化后的三角網(wǎng)格模型；圖1(c)為離散化后的三角網(wǎng)格模型與9個切割面的相交輪廓圖；圖1(d)是從三維數(shù)字化掃描設(shè)備所獲得的三角網(wǎng)格數(shù)據(jù)模型，包含198 436個三角形面片；圖1(e)是目標(biāo)函數(shù)的平均值和最小值經(jīng)過120代進(jìn)化的變化曲線，從圖可看出GA的收斂趨勢；圖1(f)是匹配的結(jié)果；圖1(g)是兩模型的匹配偏差云圖。根據(jù)匹配結(jié)果可知本文算法能進(jìn)行有效的匹配。

圖1 渦輪葉片的匹配實(shí)例

圖2是凸輪的匹配實(shí)例。圖2(a)為正向設(shè)計(jì)軟件SolidWorks 2013建立的凸輪三維CAD模型；圖 2(b)是從三維數(shù)字化掃描設(shè)備所獲得的三角網(wǎng)格數(shù)據(jù)模型，包含104 783個三角形面片；圖2(c)是采用本文算法經(jīng)過GA 120代進(jìn)化后的兩模型匹配偏差分析圖；圖 2(d)是在 Geomagic Studio2012中采用最佳擬合方式進(jìn)行匹配后的誤差分析圖，可知兩個模型有明顯的錯位?？芍疚乃惴ǖ钠ヅ渚哂休^好的魯棒性。

圖2 凸輪的匹配實(shí)例

5 結(jié) 論

本文構(gòu)建了三維模型六個自由度匹配調(diào)整的數(shù)學(xué)模型。采用二維輪廓圖間的Huasdorff距離與邊長差的加權(quán)和作為模型匹配程度的判據(jù)，把實(shí)測數(shù)據(jù)的三角網(wǎng)格模型與三維CAD模型的匹配，轉(zhuǎn)換成二維輪廓圖形匹配度的度量，避免了海量數(shù)據(jù)點(diǎn)與復(fù)雜曲面的直接計(jì)算。在三維CAD模型三角化離散的基礎(chǔ)上，基于K-D樹和拓?fù)潢P(guān)系求三維模型與平面的交截輪廓圖，避免了三維CAD模型與平面的直接求交，并有效提高了算法效率。以二維輪廓圖間的差異最小為目標(biāo)，用GA搜索兩模型最佳匹配時的位置、姿勢六參量，通過實(shí)例驗(yàn)證了該算法具有良好的魯棒性和匹配精度。

[1]高 藝, 王 斌, 胡楷模, 等. 基于典型面匹配的機(jī)械零件檢索方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報, 2011, 23(4)： 640-648.

[2]唐 勇, 沈 哲, 呂夢雅, 等. 改進(jìn)的三維模型檢索PCA預(yù)處理算法[J]. 系統(tǒng)仿真學(xué)報, 2008, 20(11)：2832-2835.

[3]Besl P J, Mckay N D. A method for registration of 3-D shapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828), 1992, 14(2)： 239-255.

[4]Claudet A A. Analysis of three dimensional measurement data and CAD models [C]//PHD Dissertation of Georgia Institute of Technology, 2001： 45-56.

[5]Pottmann H, Leopoldseder S. A concept for parametric surface fitting which avoids the parameterization problem [J]. Computer Aided Geometric Design (S0167-8396), 2003, 20： 343-362.

[6]Tangelder J W H, Veltkamp R C. A survey of content based 3D shape retrieval methods [J]. Multimedia Tools and Applications, 2008, 39(3)： 441-471.

[7]施法中. 計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條[M].北京： 高等教育出版社, 2001： 435-440.

[8]陳志楊, 葉建華, 沈 瑛, 等. 交疊網(wǎng)格的檢測與合并[J]. 中國機(jī)械工程, 2008, 19(17)： 2064-2068.

[9]徐士彪, 車武軍, 張曉鵬. 基于形狀特征的三維模型檢索技術(shù)綜述[J]. 中國體視學(xué)與圖像分析, 2010, 15(4)：439-450.

[10]董加強(qiáng). 基于遺傳算法的航天測控網(wǎng)資源分配模型與仿真[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(7)： 2074-2077.

[11]楊 平, 鄭金華. 遺傳選擇算子的比較與研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2007, 43(15)： 59-62.

A 3D Models Matching Algorithm Based on Genetic Algorithm

Ye Jianhua1,2, Gao Chenghui1, Jiang Jibin2
(1. School of Mechanical Engineering and Automation, Fuzhou University, Fuzhou Fujian 350108, China; 2. School of Mechanical & Automotive Engineering, Fujian University of Technology, Fuzhou Fujian 350108, China)

Marching mesh model which get by measurement sensor to CAD model is one of key technology in geometrical parameter measurement. It is necessary to research the consistent match orientation and position for two models. In this paper, a 3D models matching algorithm was proposed based on genetic algorithm. The translation and rotation operations in three dimensional spaces to adjust the position and orientation are used, and 2D outline features was used to match the two models. Genetic algorithm is applied to searching the consistent match orientation and position for two models. The prototype system was developed and the results were reported. Based on practice, this method is robust and efficient.

model matching; 3D models; genetic algorithms; unitary coordinate

TP 391

A

2095-302X(2015)01-0022-06

2014-04-17；定稿日期：2014-08-05

國家自然科學(xué)基金資助項(xiàng)目(51305079)；福建省自然科學(xué)基金資助項(xiàng)目(2013J01168)；福建省教育廳A類科技資助項(xiàng)目(JA13216)；福建省省屬高?？蒲匈Y助項(xiàng)目(JK2012031)

葉建華(1980-)，男，福建寧德人，講師，在讀博士。主要研究方向?yàn)橹圃爝^程自動化及信息化。E-mail：yeuser@fjut.edu.cn

高誠輝(1953-)，男，福建福清人，教授，博士生導(dǎo)師。主要研究方向?yàn)槟Σ翆W(xué)、表面工程、數(shù)字化設(shè)計(jì)。E-mail：gch@fzu.edu.cn