楊 波，楊子宜

(中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，武漢430074)

注冊技術(shù)是數(shù)字檢測領(lǐng)域的關(guān)鍵技術(shù)，目前被廣泛應(yīng)用于無損檢測、逆向工程、計算機(jī)視覺、文物保護(hù)等領(lǐng)域.模型注冊用于實(shí)現(xiàn)組件測試、模型評估、誤差分析和數(shù)據(jù)擬合的前提.馬艷新等人[1]提出了一種三維注冊和全局定位的旋轉(zhuǎn)估計算法，該算法將兩個點(diǎn)云中的所有有效點(diǎn)投影到各個平面，根據(jù)投影產(chǎn)生的方向角來估計旋轉(zhuǎn)角度，能夠降低大規(guī)模點(diǎn)云注冊的復(fù)雜性，但局限于空間結(jié)構(gòu)化的點(diǎn)云.李千山等人[2]使用多個高斯分布來模擬不確定性表面，通過高斯混合模型(GMM)來表示表面用于點(diǎn)云注冊，但當(dāng)點(diǎn)云數(shù)量較多時生成GMM模型耗時且復(fù)雜度高.Arun和Blostein等人[3]提出一種基于SVD的R3矩陣分解方法，實(shí)現(xiàn)兩個三維點(diǎn)集的最小二乘擬合，擬合結(jié)果較好，但是計算較為復(fù)雜.Gagnon和Greenspan等人[4]提出一種借助計算機(jī)輔助的半自動配準(zhǔn)技術(shù)，該方法使用計算機(jī)和人工結(jié)合的方法能夠?qū)崿F(xiàn)對點(diǎn)云的精確配準(zhǔn)，但不能實(shí)現(xiàn)自動注冊.Besl和McKay[5]提出了迭代最近點(diǎn)算法ICP，該算法被廣泛應(yīng)用于匹配算法中，ICP的核心技術(shù)是搜索兩個注冊點(diǎn)集合之間的對應(yīng)關(guān)系來計算轉(zhuǎn)換矩陣，但算法需要很好的初始值才能確保收斂，否則可能不會收斂.平雪良等人[6]運(yùn)用遺傳算法實(shí)現(xiàn)了點(diǎn)云的配準(zhǔn)，對CAD模型的三角面片化，在目標(biāo)函數(shù)的建立過程中，通過使用參考球法對測量點(diǎn)建立參考球，以點(diǎn)云各點(diǎn)為球心，不斷地擴(kuò)大球體的半徑直到球體與模型接觸，同時判斷模型頂點(diǎn)是否落入球體內(nèi)或表面，計算得到球心與模型對應(yīng)的最近點(diǎn)，并確定對應(yīng)兩點(diǎn)間的距離，以此距離作為目標(biāo)函數(shù)值來使用遺傳算法進(jìn)行迭代求得滿意解.參考球的建立減少了點(diǎn)云與CAD模型距離計算的時間，提高了算法運(yùn)行效率，但該算法在配準(zhǔn)時間上仍然有很大的開銷.

本文提出基于遺傳算法的點(diǎn)云配準(zhǔn)技術(shù)，通過使用空間矩陣對三維點(diǎn)云坐標(biāo)進(jìn)行旋轉(zhuǎn)變換來進(jìn)行點(diǎn)云與模型的匹配，同時通過建立KD樹[7]對三維空間中的CAD模型進(jìn)行劃分，進(jìn)行近鄰搜索，減少了測量點(diǎn)云與CAD模型的距離計算時間，提高了配準(zhǔn)效率，實(shí)現(xiàn)了點(diǎn)云與CAD模型的自動注冊.

1 基于遺傳算法的配準(zhǔn)

遺傳算法(GA)[8]模擬自然界優(yōu)勝劣汰的過程，通過選擇、交叉、變異等操作使得問題的解在競爭過程中得以進(jìn)化從而求得滿意解.本文采用遺傳算法實(shí)現(xiàn)測量點(diǎn)云與CAD模型的配準(zhǔn)，就遺傳算法的編碼方案、初始種群、適應(yīng)度函數(shù)、遺傳操作算子、控制參數(shù)、評價準(zhǔn)則的確定進(jìn)行討論.

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

適應(yīng)度函數(shù)用于檢測個體的優(yōu)劣性，通過計算每一代個體的適應(yīng)值對具有滿意解的個體進(jìn)行選擇.

本文對CAD模型各個頂點(diǎn)使用KD樹進(jìn)行劃分.KD樹是一種分割K維空間的數(shù)據(jù)結(jié)構(gòu)，KD樹使用二分劃分的思想，將數(shù)據(jù)進(jìn)行逐層空間上的劃分，大大地提高了查詢的速度.使用KD樹對三維空間的數(shù)據(jù)點(diǎn)進(jìn)行劃分，利用該數(shù)據(jù)結(jié)構(gòu)的特性，將數(shù)據(jù)劃分后進(jìn)行近鄰搜索，降低點(diǎn)云注冊的配準(zhǔn)時間.

數(shù)據(jù)點(diǎn)劃分后利用K近鄰搜索確定點(diǎn)云中每個點(diǎn)到CAD模型頂點(diǎn)最近的點(diǎn)，計算得到點(diǎn)云中點(diǎn)與模型距離最近點(diǎn)的距離d，將最近距離之和的倒數(shù)S作為適應(yīng)度函數(shù)，即S=1/∑di，其中i=1,2,3,…，N，N為點(diǎn)云數(shù)目.

為使測量點(diǎn)云與CAD模型進(jìn)行準(zhǔn)確匹配，使用遺傳算法得到種群中每一代具有滿意解的個體，即旋轉(zhuǎn)矩陣R和平移矩陣T.將選擇的個體加入下一代種群中，最終目標(biāo)是使適應(yīng)度函數(shù)具有最大值，值越大則表明測量點(diǎn)到CAD模型對應(yīng)點(diǎn)距離越小，匹配越精確.測量點(diǎn)Qi,最近匹配點(diǎn)Ci,則兩者間距離為:

di=‖Qi-Ci‖2,i=1,2,3,…，N.

(1)

1.2 染色體編碼及初始種群

GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，串結(jié)構(gòu)則構(gòu)成了染色體個體.本文在配準(zhǔn)過程中始終保持測量點(diǎn)和CAD模型中心對齊，根據(jù)中心點(diǎn)坐標(biāo)來確定兩點(diǎn)平移矩陣T’，如下所示：

當(dāng)G為測量點(diǎn)Qi的中心時，

G=(∑Qi(x)/N,∑Qi(y)/N,∑Qi(z)/N).

(2)

當(dāng)C為CAD模型中頂點(diǎn)集Vi的中心時，

G=(∑Vi(x)/N,∑Vi(y)/N,∑Vi(z)/N).

(3)

配準(zhǔn)平移矩陣為:

(4)

在進(jìn)行中心對齊后，令α、β、γ分別表示為繞X、Y、Z軸旋轉(zhuǎn)的角度，旋轉(zhuǎn)角度的取值范圍為0～360度之間，則旋轉(zhuǎn)角度{α,β,γ}構(gòu)造為遺傳算法的搜索空間.

{α,β,γ}作為3個基因組構(gòu)成一條染色體，每個基因組隨機(jī)由三個角度組成xi=[xi1,xi2,xi3]i=1,2,3...n,n為初始種群的規(guī)模，本文中n為50，每個基因組被編碼為具有相同長度的二進(jìn)制數(shù).

1.3 選擇操作

選擇是用來確定重組或交叉的個體，以及被選個體將產(chǎn)生多少個子代個體.選擇方法有很多，本文采用一種類似于博彩游戲的輪盤賭選擇方法進(jìn)行選擇操作.對種群中的每個個體計算其適應(yīng)度，個體適應(yīng)度按照比例轉(zhuǎn)換為選中概率.每次旋轉(zhuǎn)產(chǎn)生一個隨機(jī)數(shù)，按照累積概率選擇相應(yīng)的個體，具體過程如下.

(1)計算每個染色體的累積概率:

Ki=sum(S(xi)/n),i=1,2,3,…，n.

(5)

(2)產(chǎn)生[0,Ki]之間的隨機(jī)數(shù)r.

(3)判斷r處于扇區(qū)的哪個區(qū)域，該區(qū)域?qū)?yīng)的染色體被選擇.

(4)重復(fù)(2)、(3)直到選擇出需要的m個染色體為止.

1.4 交叉操作

采用單點(diǎn)交叉進(jìn)行染色體組合產(chǎn)生新的子個體，挑選經(jīng)過選擇操作后種群中的兩個父個體作為交叉對象，兩個父個體xi,xj經(jīng)過染色體交換重組后產(chǎn)生兩個子個體xi’,xj’.本文中交叉概率為0.87.在[1,L-1]之間產(chǎn)生一個交叉位置,其中L為染色體長度.根據(jù)產(chǎn)生的交叉位置來將父個體的染色體進(jìn)行拆分，然后將拆分后的染色體重組成相同長度的染色體，所得染色體與父染色體不同即為子染色體.交叉過程如圖1所示.

圖1 交叉過程Fig.1 The process of crossover

1.5 變異操作

為避免過早收斂，擴(kuò)大搜索范圍，通過變異操作，在進(jìn)化過程中產(chǎn)生具有新遺傳基因的個體.本文對染色體采用的是二進(jìn)制編碼，以一定的變異概率(本文為0.08),在[1,L]范圍內(nèi)隨機(jī)產(chǎn)生一個變異位，其中L為染色體長度.由于二進(jìn)制只有0和1兩種值，產(chǎn)生變異位后，如果變異位為0則將其值變?yōu)?，若為1則變?yōu)?，實(shí)現(xiàn)基因碼的翻轉(zhuǎn).父個體xi進(jìn)行基因碼翻轉(zhuǎn)后變異產(chǎn)生子個體xi’.變異過程如圖2所示.

圖2 變異過程Fig.2 The process of mutation

1.6 遺傳算法評價準(zhǔn)則

準(zhǔn)則1:預(yù)先設(shè)定種群適應(yīng)度閾值，在種群進(jìn)化的每一代中，選取種群中個體的最大適應(yīng)度，如果最大適應(yīng)度超過預(yù)先設(shè)定的值，則種群停止迭代進(jìn)化.

準(zhǔn)則2:預(yù)先設(shè)定種群適應(yīng)度閾值，種群不斷地迭代進(jìn)化，并且計算得到每一代種群中個體的平均適應(yīng)度，種群中個體的平均適應(yīng)度如果超過預(yù)先設(shè)定的值，則停止迭代進(jìn)化.

準(zhǔn)則3:預(yù)先設(shè)定種群進(jìn)化代數(shù)，如果種群進(jìn)化代數(shù)超過預(yù)先設(shè)定的值，則停止迭代進(jìn)化.

GA在進(jìn)化的每一代中，根據(jù)適應(yīng)度函數(shù)計算得到種群個體的適應(yīng)度值，適應(yīng)度決定種群的進(jìn)化方向，選擇將適應(yīng)度值作為評價準(zhǔn)則，隨著種群的不斷進(jìn)化，種群適應(yīng)度會得到收斂，可以得到問題的全局最優(yōu)解，如果以進(jìn)化代數(shù)作為評價準(zhǔn)則，則在種群達(dá)

到指定進(jìn)化代數(shù)后，算法可能會過早收斂，無法得到全局最優(yōu)解.

為了使配準(zhǔn)結(jié)果達(dá)到一定的精度，以種群最大適應(yīng)度作為評價準(zhǔn)則，即適應(yīng)度在達(dá)到預(yù)先設(shè)定的值之后停止迭代進(jìn)化.

2 實(shí)驗(yàn)研究

本文使用的模型數(shù)據(jù)為將CAD模型文件轉(zhuǎn)換為stl格式文件的數(shù)據(jù)，stl文件包含了點(diǎn)集的坐標(biāo)以及法矢量數(shù)據(jù).用于配準(zhǔn)的點(diǎn)云數(shù)據(jù)為根據(jù)CAD模型掃描生成的點(diǎn)云數(shù)據(jù).CAD模型三角面片化后的數(shù)據(jù)如圖3所示.

a) CAD模型原始圖 b) CAD模型三角面片化后圖3 CAD模型面片化示意圖Fig.3 Illustration of CAD model’s triangular facets

為驗(yàn)證算法的可行性和有效性，采用四個不同的模型及軟件模擬掃描得到的點(diǎn)云測量數(shù)據(jù)來進(jìn)行試驗(yàn).在Windows 8操作系統(tǒng)(CPU主頻2.5GHZ,內(nèi)存8GB),采用Matlab R2016a實(shí)現(xiàn)本文的算法.

對4個頂點(diǎn)數(shù)、面數(shù)不同的模型進(jìn)行了實(shí)驗(yàn)，如圖4、5、6、7所示.配準(zhǔn)后，點(diǎn)云均勻地覆蓋在模型表面.模型復(fù)雜程度增加，也能達(dá)到理想的配準(zhǔn)效果.表1顯示了各個模型的配準(zhǔn)時間及配準(zhǔn)的均方誤差.

a) 茶壺模型與測量點(diǎn)配準(zhǔn)前 b) 茶壺模型與測量點(diǎn)配準(zhǔn)后圖4 茶壺模型的點(diǎn)云配準(zhǔn)Fig.4 Point cloud registration of the teapot model

a) 小刀模型與測量點(diǎn)配準(zhǔn)前 b) 小刀模型與測量點(diǎn)配準(zhǔn)后圖5 小刀模型的點(diǎn)云配準(zhǔn)Fig.5 Point cloud registration of the knife model

a) 閥門模型與測量點(diǎn)配準(zhǔn)前 b) 閥門模型與測量點(diǎn)配準(zhǔn)后圖6 閥門模型的點(diǎn)云配準(zhǔn)Fig.6 Point cloud registration of the valve model

a)渦輪葉片模型與測量點(diǎn)配準(zhǔn)前 b) 渦輪葉片模型與測量點(diǎn)配準(zhǔn)后圖7 渦輪葉片模型的點(diǎn)云配準(zhǔn)Fig.7 Point cloud registration of the turbine blade model

模型頂點(diǎn)數(shù)面數(shù)點(diǎn)云數(shù)配準(zhǔn)時間/s均方誤差/mm茶壺307210245308.80.98小刀47161572848181.35閥門1810260343013522.40渦輪葉片1038034601730371.92渦輪葉片[6]10380346017306602.50

由表1中可得，本文與文獻(xiàn)[6]進(jìn)行點(diǎn)云與渦輪葉片模型配準(zhǔn)比較，文獻(xiàn)[6]雖然使用參考球法減少了點(diǎn)云配準(zhǔn)時間，但該方法需要進(jìn)行多次迭代來判斷模型上的點(diǎn)和面是否處于半徑不斷擴(kuò)大的參考球中，計算量較大，在時間上需要很大開銷.本文中通過使用提出的算法對不同規(guī)模的點(diǎn)云進(jìn)行配準(zhǔn)實(shí)驗(yàn)，在配準(zhǔn)時間上得到了進(jìn)一步減少.由表1分析可知，本文提出的算法可以得到較為滿意的配準(zhǔn)效果.且與文獻(xiàn)[6]的實(shí)數(shù)編碼相比，本文采用的是二進(jìn)制染色體編碼，其優(yōu)點(diǎn)在于編碼解碼操作簡單，交叉、變異等遺傳操作便于實(shí)現(xiàn)，而且二進(jìn)制編碼搜索能力比實(shí)數(shù)編碼強(qiáng)，隨著種群大小的增大，這種差別也越來越明顯.

3 結(jié)語

本文針對3D模型與點(diǎn)云進(jìn)行配準(zhǔn)的問題，提出了一種用遺傳算法進(jìn)行解決的方法，該方法利用了遺傳算法具有進(jìn)行全局搜索的特點(diǎn)，同時通過為模型構(gòu)建KD樹的方法來進(jìn)行K近鄰搜索，提高KNN搜索的效率，以減小計算距離的次數(shù)，使得配準(zhǔn)結(jié)果具有較高的精度，配準(zhǔn)時間也有所減少.本文對不同復(fù)雜性的3D模型進(jìn)行配準(zhǔn)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文提出的算法可以實(shí)現(xiàn)點(diǎn)云與模型的注冊效果，且隨著測量點(diǎn)數(shù)量和模型復(fù)雜性的增加，配準(zhǔn)時間在一個理想范圍內(nèi)，達(dá)到了快速配準(zhǔn)的效果，配準(zhǔn)誤差也處于一個較小范圍.

參 考 文 獻(xiàn)

[1] Ma Y X, Guo Y L, Lei Y J, et al. Efficient Rotation Estimation for 3D Registration and Global Localization in Structured Point Clouds[J]. Image and Vision Computing, 2017, 67(5): 52-56.

[2] Li Q S, Xiong Y, et al. A GMM Based Uncertainty Model for Point Clouds Registration[J]. Robotics and Autonomous Systems, 2016, 91(31): 349-362.

[3] Arun K S, Huang T S. Least-Squares Fitting of Two 3-D Point Sets[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(5):698-700.

[4] Gannon E, Rivest J F. A Computer-assisted Range Image Registration System for Nuclear Waste Cleanup[J]. IEEE Instrumentation and Measurement Technology Conference, 1999, 48(3): 758-762.

[5] Besl P J, Neil D, McKay. Method for Registration of 3-D Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intellinegce, 1992, 14(2): 239-256.

[6] 平雪良, 耿 魯, 華 婷，等. 遺傳算法在點(diǎn)云配準(zhǔn)技術(shù)中的應(yīng)用[J]. 機(jī)械科學(xué)與技術(shù), 2010, 29(6): 809-812.

[7] Kjer H. Evaluation of Surface Registration Algorithms for PET Motion Correction[D]. Denmark: Technical University of Denmark, 2010.

[8] 黃席樾, 張著洪, 何傳江,等. 現(xiàn)代智能算法理論及應(yīng)用[M]. 北京:科學(xué)出版社, 2005.