葉建華， 高誠輝， 江吉彬

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

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

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

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

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

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

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

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

1 匹配模型建立

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

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

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

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

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

2 匹配度評測方法

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

2.1 三維CAD模型網格化

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

NURBS曲面的參數化表達式[7]為：

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

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

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

2.2 截交平面

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

2.3 三維網格模型與平面求交

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

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

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

(3) 建立網格的拓撲信息。拓撲信息也就是拓撲元素的類型、個數以及相互之間關系的表達。通過拓撲信息可以快速地獲得與拓撲元素相鄰的幾何元素。在網格模型的拓撲信息中建構以下拓撲關系：頂點相關的一階領域邊；邊所包含的兩頂點；邊所對應的左、右三角面片；三角面片所包含的頂點與邊。

(4) 利用拓撲信息搜索出其余相交邊。以第一條邊為搜索起點，利用拓撲關系獲得邊所對應的三角面片，進而獲得三角面片所對應的其他邊和頂點，并與切割平面iPlan′求交獲得下一相交邊；如果交點落在頂點上，則通過頂點獲得其一階領域邊與切割平面iPlan′求交獲得下一相交邊。不斷重復上述過程，直到又找到搜索起點邊或向兩個方向都找到邊界邊為止。求出與切割平面iPlan′相交的所有交點ikCa，即可得到一個完整的相交截面輪廓iCa。為了下個環(huán)第一條邊的計算效率，求過交的邊和所在的三角面片做已計算標記。

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

2.4 一致性判據

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

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

3 基于遺傳算法的匹配

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

3.1 編碼

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

3.2 適應度函數

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

3.3 遺傳算子設計

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

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

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

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

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

4 應用實例

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

圖1 渦輪葉片的匹配實例

圖2是凸輪的匹配實例。圖2(a)為正向設計軟件SolidWorks 2013建立的凸輪三維CAD模型；圖 2(b)是從三維數字化掃描設備所獲得的三角網格數據模型，包含104 783個三角形面片；圖2(c)是采用本文算法經過GA 120代進化后的兩模型匹配偏差分析圖；圖 2(d)是在 Geomagic Studio2012中采用最佳擬合方式進行匹配后的誤差分析圖，可知兩個模型有明顯的錯位。可知本文算法的匹配具有較好的魯棒性。

圖2 凸輪的匹配實例

5 結 論

本文構建了三維模型六個自由度匹配調整的數學模型。采用二維輪廓圖間的Huasdorff距離與邊長差的加權和作為模型匹配程度的判據，把實測數據的三角網格模型與三維CAD模型的匹配，轉換成二維輪廓圖形匹配度的度量，避免了海量數據點與復雜曲面的直接計算。在三維CAD模型三角化離散的基礎上，基于K-D樹和拓撲關系求三維模型與平面的交截輪廓圖，避免了三維CAD模型與平面的直接求交，并有效提高了算法效率。以二維輪廓圖間的差異最小為目標，用GA搜索兩模型最佳匹配時的位置、姿勢六參量，通過實例驗證了該算法具有良好的魯棒性和匹配精度。

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

[2]唐 勇, 沈 哲, 呂夢雅, 等. 改進的三維模型檢索PCA預處理算法[J]. 系統(tǒng)仿真學報, 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]施法中. 計算機輔助幾何設計與非均勻有理B樣條[M].北京： 高等教育出版社, 2001： 435-440.

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

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

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

[11]楊 平, 鄭金華. 遺傳選擇算子的比較與研究[J]. 計算機工程與應用, 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

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

葉建華(1980-)，男，福建寧德人，講師，在讀博士。主要研究方向為制造過程自動化及信息化。E-mail：yeuser@fjut.edu.cn

高誠輝(1953-)，男，福建福清人，教授，博士生導師。主要研究方向為摩擦學、表面工程、數字化設計。E-mail：gch@fzu.edu.cn