潘偉杰，冀?？?/p>

（1.廣東工業(yè)大學計算機學院，廣州 510006; 2.廣船國際股份有限公司，廣州 510382）

船體外板旋轉(zhuǎn)匹配成形檢測算法研究與實現(xiàn)

潘偉杰1，冀?？?

（1.廣東工業(yè)大學計算機學院，廣州 510006; 2.廣船國際股份有限公司，廣州 510382）

在船舶生產(chǎn)過程中，部分船體外板的加工無法通過輥壓一次性加工成形，而需要附加額外的工人勞動使外板繼續(xù)形變直至檢測合格。當前工人所做的檢測工作主要利用活洛卡板與樣箱等工具進行檢測，該檢測方法效率較低。文章利用計算機模擬現(xiàn)實中工人的檢測方法，結(jié)合遺傳算法優(yōu)化實現(xiàn)檢測所得的現(xiàn)實加工板曲面與目標成形曲面旋轉(zhuǎn)匹配，并得到成形程度評估。

外板檢測；旋轉(zhuǎn)匹配；遺傳算法

0 引言

在船舶生產(chǎn)過程中，部分復雜船體外板的加工無法通過輥壓一次加工成形，而需要附加額外的工人勞動進行火工彎板使外板繼續(xù)形變直至檢測符合規(guī)格要求。當前復雜船體外板檢測主要利用三角樣板以及樣箱等檢測工具實現(xiàn)檢測。樣箱是一種木制的箱形架子，其中一面依照船體設(shè)計的曲面加工，能夠體現(xiàn)所加工船體外板的外形特性。檢測時樣箱將被放置于外板上，與外板上的相關(guān)標記對齊，如圖1所示。當樣箱與外板之間接觸間隙小于檢測章程規(guī)定時，則認為外板加工完成，否則表明外板的外形與船體設(shè)計不一致，未達到加工要求。該檢測方法延用至今，已靈活有效地用于檢測外板是否成形，但是手工的檢測方式主觀因素影響比較大，難以提高效率。因此數(shù)字化模擬這一檢測技術(shù)對所加工的外板進行檢測具有重要意義。

文獻[1]的工作與本文接近，但是文獻[1]中同樣以肋骨線檢測為主[1]，以弦線距作為成形程度評價指標，而本文著重模擬上述的檢測工具實現(xiàn)整體曲面的匹配，以曲面的重合程度進行成形程度評價。其中關(guān)鍵在于如何使檢測面適當?shù)嘏c外板表面重合比較，因此通過曲面匹配實現(xiàn)成形檢測。

圖1 外板成形檢測工具

目前已有大量關(guān)于曲面匹配的研究，文獻[2]回顧與總結(jié)了多種主要的曲面匹配算法的特點。ICP算法[3]是其中一種通用的精匹配算法，該算法迭代地減小最近點對之間的距離獲得精解。原始的ICP算法存在著收斂性和魯棒性的問題，文獻[4]使用一種魯棒性更強評判函數(shù)改進ICP算法[4]，文獻[5]進一步使用最小截平方和（Least Trimmed Squares，LTS）改進ICP算法的魯棒性，并且結(jié)合遺傳算法預匹配，實現(xiàn)任意朝向的曲面匹配[5]。

基于遺傳算法的曲面匹配是另一個主要的研究方向。文獻[6]中較早地把遺傳算法應(yīng)用到曲面匹配上[6]，文中利用遺傳算法直接計算曲面的匹配部分。隨后的文獻[7]提出了一種動態(tài)遺傳算法[7]，對曲面匹配對齊動作的6個參數(shù)進行編碼，搜尋最優(yōu)染色體。文獻[8]所用的方法與之相似[8]，而文獻[5]則利用類似的方法達到快速預匹配的效果。

本文解決的匹配問題有別于以上的曲面匹配。以上曲面匹配算法著重實現(xiàn)兩個形狀相似度十分高，接近完全相同的曲面的匹配。部分匹配算法如文獻[4]和[9]解決曲面與多個視圖的曲面匹配[4,9]，其中曲面之間可能僅僅存在部分重疊的部位，但是曲面可重疊部分形狀相似度仍然是十分高的。在本文中曲面匹配將用于外板成形檢測，因此外板表面與檢測面形狀不一定相同。另一方面，一般曲面匹配算法目標實現(xiàn)最大似然匹配，如文獻[10]中要求呈現(xiàn)一個大“斑漬”的曲面[10]，在本文的成形匹配中這可能會造成匹配錯誤，且成形檢測要求間隙平衡。此外，由于本文采用虛擬樣箱等檢測工具的檢測技術(shù)，這過程可比擬作模具與工件的比較，兩者不能相互刺穿，因此曲面匹配過程中還需要添加曲面碰撞測試。鑒于此本文選擇使用一種旋轉(zhuǎn)匹配的算法，以數(shù)值計算的方法搜尋一個合適的匹配位置。樸素的搜尋方法效率較低，故進一步引入遺傳算法提高搜尋效率。

本文利用掃描儀對整個鋼板進行掃描，得到鋼板的立體點云。在點云的基礎(chǔ)上擬合成鋼板檢測曲面，同時將外板表面與檢測面做旋轉(zhuǎn)匹配，在遺傳算法的優(yōu)化下，搜尋一個合適的匹配位置。最后計算曲面之間的差異，得出外板成形程度的結(jié)果。

1 外板成形檢測

1.1 曲面預處理

當今先進的船舶設(shè)計已能夠借助計算機輔助設(shè)計（CAD）進行立體三維空間的設(shè)計，待加工的船體外板的三維立體數(shù)據(jù)在此過程中產(chǎn)生。該船體外板設(shè)計亦是水火彎板加工的目標成形狀態(tài)，稱之為目標板。水火彎板對外板加工直至外板的形狀符合目標板的形狀則可結(jié)束，因此目標板用于檢測當前加工板的成形程度。

當前實際外板所加工的程度需要通過一種或多種檢測技術(shù)實現(xiàn)檢測與數(shù)據(jù)采集，然后在計算機中重構(gòu)出外板的三維形狀。這類檢測技術(shù)包括3D激光掃描、機器視覺識別，以及點抽樣檢測等。檢測所得到的現(xiàn)實加工板數(shù)據(jù)將用于重構(gòu)外板的三維模型，與目標板進行比較，計算出外板成形程度。檢測得到的現(xiàn)實外板的三維模型稱為檢測板。

目標板曲面容易從設(shè)計室給出的三維立體數(shù)據(jù)中提取得到，可還原形成一個無厚度的，作為檢測標準的曲面。曲面基本由網(wǎng)格拓撲組成，每一片網(wǎng)格形成一個Bezier子曲面。為體現(xiàn)模擬樣箱檢測，目標板以樣箱的形式展現(xiàn)，如圖2所示。

掃描檢測實際加工板以后首先得到的是外板的立體點云，檢測板曲面可根據(jù)這些立體點云數(shù)據(jù)擬合得到。為了與目標板曲面保持相同的拓撲結(jié)構(gòu)，檢測板曲面擬合過程中，將對目標曲面進行曲面展開，展開到檢測板立體點云上，重新擬合得出與目

標曲面具有相同拓撲結(jié)構(gòu)的檢測曲面，如圖3所示。所得的檢測曲面上的網(wǎng)格頂點與目標板曲面上的網(wǎng)格頂點仍能一一對應(yīng)。

圖2 樣箱形式的目標板曲面

圖3 網(wǎng)格形形式的檢測板擬合曲面

1.2 旋轉(zhuǎn)匹配

在計算外船加工成形程度之前，需要先將檢測板曲面與目標板曲面進行匹配，使兩板曲面經(jīng)過空間立體變換后處于一個適合做差異比較相對姿態(tài)上。結(jié)合外板檢測的實際需要，使用旋轉(zhuǎn)匹配的方法，計算出兩板匹配旋轉(zhuǎn)角度的數(shù)值解。

由于兩板曲面建立的時候所參照的坐標系不相同，所以初始時兩板曲面相對偏離較遠，相對空間位置也可能變得凌亂，可以先把兩曲面通過空間變換轉(zhuǎn)移到統(tǒng)一的位置上，然后兩曲面都基本放平。這主要取兩板曲面上對應(yīng)的三個角點進行控制，其中兩個角點相連形成向量，起點移至與坐標原點重合，方向旋轉(zhuǎn)至與x軸同向。再做一步空間變換，使曲面的三個角點所形成的平面的法向量平行于z軸。經(jīng)過這一步處理以后兩板曲面基本對齊，可用于進行匹配，如圖4所示。

圖4 兩板曲面基本對齊

經(jīng)過空間變換后對齊到一起的兩外板曲面需要做進一步的匹配，從而確定適合于比較兩曲面差異情況的匹配位置，計算出外板加工成形程度。如上文所述，這里主要使用一種旋轉(zhuǎn)匹配的方法，使目標板曲面繞曲面的一個中心頂點旋轉(zhuǎn)，一邊旋轉(zhuǎn)一邊測試目標板曲面是否與檢測板匹配，最終找出達到最佳匹配的旋轉(zhuǎn)角度的數(shù)值解。

目標板曲面具有相應(yīng)的空間網(wǎng)格拓撲結(jié)構(gòu)，取其中網(wǎng)格中心的頂點作為旋轉(zhuǎn)中心，對目標板曲面進行旋轉(zhuǎn)，如圖5所示。檢測板曲面上同樣取網(wǎng)格的中心作為曲面的中心點，讓兩板中心保持在XOY投影意義下對齊，其中產(chǎn)生平移Td。目標板曲面從x和y兩個旋轉(zhuǎn)分量進行旋轉(zhuǎn)，分別對應(yīng)兩個旋轉(zhuǎn)矩陣Rx與Ry。

圖5 按x與y旋轉(zhuǎn)分量對目標板曲面進行旋轉(zhuǎn)

為了達到模擬檢測的目的，目標板曲面將被用作檢測曲面的卡板和箱具，在目標板曲面與檢測板

曲面匹配的過程中，兩板曲面之間需要進行碰撞檢測。目標板曲面經(jīng)過空間變換旋轉(zhuǎn)后，沿z軸方向垂直抬升，使保證目標板曲面與檢測板曲面不發(fā)生碰撞。然后測試目標板上每個頂點到檢測板曲面的高度差，計算其中最小的高度差，使目標板曲面按最小高度差下沉回去，與檢測板曲面不發(fā)生碰撞，此間所發(fā)生的空間變換為Td。

至此完成一次匹配測試，合并起來的空間變換矩陣為：

其中，T是使目標板曲面旋轉(zhuǎn)中心平移至坐標原點以實現(xiàn)繞旋轉(zhuǎn)中心旋轉(zhuǎn)的平移矩陣。

外板曲面匹配的目標是使曲面上四個角點的最大差距Δmax最小，使兩個曲面盡可能重合貼近；且四個角點差距的方差Var最小，使未成形的外板曲面的差距均勻分布。

1.3 成形程度計算

外板曲面成功匹配以后，需要通過計算曲面間的差異程度計算外板的加工成形程度。計算成形程度時，計算完成匹配以后的兩個曲面上對應(yīng)網(wǎng)格頂點之間的空間距離，同時設(shè)定一個閥值 ε，最終以空間距離小于閥值ε的頂點數(shù)占總頂點數(shù)中的比例作為外板加工成形程度百分比。

2 遺傳算法

2.1 基本遺傳算法

對于上文所述建立在現(xiàn)實情形下的船體外板檢測技術(shù)，使船體外板檢測尋優(yōu)空間降低至二維的查尋空間，但是在大密度的搜索空間中進行全空間的搜索，匹配檢測效率仍然不高，因此適宜使用遺傳算法進行優(yōu)化。遺傳算法是一種仿照自然選擇和基因遺傳學原理的優(yōu)化算法，適合處理近似于本文所處理的非線性問題，獲得全局最優(yōu)解。

2.2 編碼與譯碼

基于本文所使用的外板檢測技術(shù)，目標板曲面繞以旋轉(zhuǎn)中心旋轉(zhuǎn)分別存在x和y的旋轉(zhuǎn)分量，x旋轉(zhuǎn)分量的旋轉(zhuǎn)角度ax在Ax[-α,α]內(nèi)，設(shè)置旋轉(zhuǎn)測試步長sx，共取個測試角；相應(yīng)的y旋轉(zhuǎn)分量旋轉(zhuǎn)角度ay在Ay[-β,β]內(nèi)，設(shè)置旋轉(zhuǎn)測試步長sy，共取個測試角，在這樣的旋轉(zhuǎn)匹配測試下，遺傳算法對應(yīng)的解空間為：

在這個解空間內(nèi)進行搜索，共有nx·ny個匹配測試點。

遺傳算法對解空間基因編碼時，采用均勻二進制編碼，首先需要對解空間中的每個解進行編號。解空間的解將根據(jù)Ax與Ay做笛卡爾積運算中各解的產(chǎn)生順序編號，更具體地，編號先按y旋轉(zhuǎn)分量從小到大排序，同時在y旋轉(zhuǎn)分量相同的情況下，按x旋轉(zhuǎn)分量從小到大地排序，可對其編號順序列出一個矩陣，并按矩陣行優(yōu)先順序進行編號。

為了使二進制編碼覆蓋所有的測試點，需要令編碼長度L滿足2L-1＜ nx·ny≤ 2L。進一步地，測試點的數(shù)量nx·ny不總是2的次冪，因此二進制編碼需要平均分配到每個測試點上。對于一個編號為No的解，可進行如下二進制編碼：

一個區(qū)間內(nèi)的編碼同分配至一個測試點。

2.3 適應(yīng)度度量

為模仿生物進化中適應(yīng)能力強的個體容易存活下來繁衍出更多后代的特點，曲面匹配遺傳算法同樣引入適應(yīng)度度量，區(qū)分遺傳群體中個體的好壞。對于每個個體的適應(yīng)度度量，根據(jù)每個個體（旋轉(zhuǎn)測試角度）按曲面匹配檢測目標的排序先后進行度量。如上文所述，曲面匹配目標有兩個，分別包括使曲面四個對應(yīng)角點最大差距最小，使曲面四個對應(yīng)角點差距方差最小。根據(jù)曲面四個對應(yīng)角點最大差距排序，每個個體得到相應(yīng)的排序結(jié)果odrΔ；同理，根據(jù)曲面四個對應(yīng)角點差距的方差排序，每個個體得到相應(yīng)的排序結(jié)果odrvar。最終每個個體按照

max(odrΔ, odrvar)排序，排序結(jié)果靠前的個體適應(yīng)能力較強。

2.4 選擇算子

適應(yīng)于遺傳個體適應(yīng)度的排序度量方式，曲面旋轉(zhuǎn)匹配遺傳算法將使用排序型的選擇算子。在種群X={X1, …, XN}中每個個體Xi, i=1, … , N將按照適應(yīng)度從小到大排序，根據(jù)排序結(jié)果，線性地對每個個體設(shè)置一個選擇概率。相關(guān)選擇概率分布為：

2.5 交叉算子

請注意，這里的旋轉(zhuǎn)匹配遺傳算法是針對繞兩個旋轉(zhuǎn)分量進行解空間尋優(yōu)的，是二維的，因此本遺傳匹配算法將使用兩點交叉雜交。通過對遺傳算法編碼方式的分析可知，遺傳算法中的個體的編碼方式基本是按一個二維矩陣的填充順序編排的，以一個4位的編碼為例，見表1。

表1 遺傳算法編碼方式舉例

從表1中可發(fā)現(xiàn)，以編碼中間位置劃分，編碼分為高位部分與低位部分，其中高位部分將控制個體跨行的選擇變化，在旋轉(zhuǎn)匹配上將產(chǎn)生y旋轉(zhuǎn)分量的變化；而低位部分將控制個體跨列的選擇變化，對應(yīng)于旋轉(zhuǎn)匹配的x旋轉(zhuǎn)分量的變化。因此基因交叉變異設(shè)置兩個交叉點較為適宜，使交叉點分別分布于高位部分與低位部分。

交叉位置具有相等的選擇概率pc，但是額外規(guī)定編碼中間位置為界，高位部分和低位部分都需要各選擇一個交叉位置，且編碼基因?qū)⒎謴母呶徊糠纸徊嫖恢玫骄幋a中間位置，以及從低位部分交叉位置到編碼未位兩段進行交叉變換。

2.6 變異算子

基因遺傳存在著一定概率pm發(fā)生突變，本遺傳算法中每個基因位具有相同的概率發(fā)生突變。

2.7 結(jié)束條件

在群體繁衍過程中，如果適應(yīng)度最高的個體重復若干代都相同，那么結(jié)束遺傳繁衍，取收斂所得的適應(yīng)度最高的個體作為曲面匹配的結(jié)果。同時，如果遺傳超過一定代數(shù)以后，遺傳繁衍同樣結(jié)束，取歷代最優(yōu)的個體作為曲面匹配的結(jié)果。

3 實驗計算

一般大型船板的寬度約為3 m，長度達10 m。本文實驗所使用的外板寬度約為1 m，長度約為3 m。相關(guān)的實驗參數(shù)在表2中列出。

表2 實驗參數(shù)

為使外板曲面匹配檢測足夠精確，實驗中各旋轉(zhuǎn)分量所設(shè)置的測試步長為sx=sy=0.01°，在此測試步長下，若長度為3 m的外板繞其中一端進行旋轉(zhuǎn)一個旋轉(zhuǎn)測度步長，另一端在旋轉(zhuǎn)后僅僅發(fā)生約為1 mm的位移。

經(jīng)過16代的繁衍以后，種群個體基本收斂于同一個體，編碼為01111010101010000000。

對編碼譯碼可知對應(yīng)的x旋轉(zhuǎn)分量為1.06°，以及y旋轉(zhuǎn)分量為-0.21°。

若設(shè)置成形程度閥值ε=0.01，使用遺傳算法得到的曲面匹配結(jié)果以后所計算得出的外板成形程度為33.33%，如圖6所示。

對比于在整個解空間中進行樸素的搜索，可得到全局最優(yōu)曲面匹配，其中對應(yīng)的 x旋轉(zhuǎn)分量為1.04°，以及y旋轉(zhuǎn)分量為-0.22°。同樣在ε=0.01的成形程度閥值下，全局最優(yōu)曲面匹配所計算得出的外板成形程度為35.71%，如圖7所示。

對比兩種外板曲面匹配與外板的成形程度結(jié)果可知，遺傳算法所得的結(jié)果與全局結(jié)果相近，但是使用遺傳算法僅進行了16代的繁衍約800次的匹配

測試，而全局搜索需要進行1 002 001次的匹配測試，因此本文中對船體外板檢測所引入的旋轉(zhuǎn)匹配遺傳算法有效改進船體外板檢測的效率。

圖6 使用遺傳算法所得的曲面匹配結(jié)果

圖7 全局搜索所得的曲面匹配結(jié)果

4 結(jié)論

針對船體外板檢測，引入旋轉(zhuǎn)匹配遺傳算法，有效改進了船體外板檢測的效率。但是從實驗結(jié)果可以看出，遺傳繁衍存在著收斂過快的問題，該算法仍需進一步改進。

[1]趙凱.船體外板加工成形自動檢測模型研究[D].武漢理工大學, 2008.

[2]Joaquim Salvi, Carles Matabosch, David Fofi, Josep Forest.A Review of Recent Range Image Registration Methods with Accuracy Evaluation[J].Image and Vision Computing, 2007, 25(5): 578-596.

[3]P.Besl and N.McKay.A method for registration of 3-D shapes[C]// IEEE Trans.on Pattern Analysis and Machine Intelligence, 1992.

[4]L.Silva.O.Bellon, K.Boyer.Enhanced Robust Genetic Algorithms for Multiview Range Image Registration[C]// Fourth International Conference on 3-D Digital Imaging and Modeling, 2003.

[5]Evgeny Lomonosov, Dmitry Chetverikov, Anikó Ekárt, Pre-registration of Arbitrarily Oriented 3D Surfaces Using a Genetic Algorithm[J].Pattern Recognition Letters -Special Issue: Evolutionary Computer Vision and Image Understanding, 2006, 27(11):1201-1208.

[6]K.Brunnstr¨om, A.Stoddart.Genetic Algorithms for Free-form Surface Matching[C]// Proc.International Conference on Pattern Recognition, Vol.4, IEEE Comp.Soc., 1996.

[7]C.Chow, H.Tsui, T.Lee.Surface Registration Using a Dynamic Genetic Algorithm[J].Pattern Recogn, 2004, 37(1):105-117.

[8]呂朝輝, 張兆揚, 安平.一種基于遺傳算法的立體匹配方法[J].計算機工程, 2003, 29(20): 24-30.

[9]D.Chung, Y.D.S.Lee.Registration of Multiple Range Views Using the Reverse Calibration Technique[J].Pattern Recognition, 1998, 31 (4): 457-464.

[10]G.Dalley, P.Flynn.Range image registration: A software platform and empirical evaluation[C]// In Proc.of the 3th Int.Conf.on 3-D Digital Imaging and Modeling, 2001.

Research and Compliment of Hull Plate Forming By Rotate Registration Algorithm

Pan Wei-jie1, Ji Hai-jun2

(1.School of Computers, Guangdong University of Technology, Guangzhou 510006, China; 2.Guangzhou Shipyard International Company, Guangzhou 510382, China)

In the process of shipbuilding, a part of hull plate is in complex shape and is unable to take shape by stamping at the first time.Additional work is employed in continuing forming the plate until specification is contented.Workers perform inspection with tools such as profile gauge, shape box and so on.The inspecting method is of low efficiency.The paper proposes an inspect method by simulating manual inspection in practice, performing rotate registration between the real scanned surface and the target forming surface, combining with genetic algorithm optimization.The forming valuation is gained.Key words: hull plate inspection; rotate registration; genetic algorithm

U662

A

10.14141/j.31-1981.2016.06.002

潘偉杰（1991—），男，碩士研究生，研究方向：物聯(lián)網(wǎng)與信息物理融合。