船體外板旋轉匹配成形檢測算法研究與實現

潘偉杰，冀海俊

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

船體外板旋轉匹配成形檢測算法研究與實現

潘偉杰1，冀海俊2

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

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

外板檢測；旋轉匹配；遺傳算法

0 引言

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

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

圖1 外板成形檢測工具

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

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

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

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

1 外板成形檢測

1.1 曲面預處理

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

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

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

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

標曲面具有相同拓撲結構的檢測曲面，如圖3所示。所得的檢測曲面上的網格頂點與目標板曲面上的網格頂點仍能一一對應。

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

圖3 網格形形式的檢測板擬合曲面

1.2 旋轉匹配

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

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

圖4 兩板曲面基本對齊

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

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

圖5 按x與y旋轉分量對目標板曲面進行旋轉

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

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

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

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

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

1.3 成形程度計算

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

2 遺傳算法

2.1 基本遺傳算法

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

2.2 編碼與譯碼

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

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

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

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

一個區間內的編碼同分配至一個測試點。

2.3 適應度度量

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

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

2.4 選擇算子

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

2.5 交叉算子

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

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

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

交叉位置具有相等的選擇概率pc，但是額外規定編碼中間位置為界，高位部分和低位部分都需要各選擇一個交叉位置，且編碼基因將分從高位部分交叉位置到編碼中間位置，以及從低位部分交叉位置到編碼未位兩段進行交叉變換。

2.6 變異算子

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

2.7 結束條件

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

3 實驗計算

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

表2 實驗參數

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

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

對編碼譯碼可知對應的x旋轉分量為1.06°，以及y旋轉分量為-0.21°。

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

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

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

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

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

圖7 全局搜索所得的曲面匹配結果

4 結論

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

[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—），男，碩士研究生，研究方向：物聯網與信息物理融合。