基于粒子群算法的點云特征拼合方法*

束 怡，翟歡樂

（江蘇航空職業技術學院工程學院，江蘇鎮江 212000）

0 引言

在逆向工程中，數據采集和處理是實現三維模型重建的第一步工作，數據采集也稱零件的數字化，是通過特定的掃描設備和掃描方法獲取零件表面離散點的幾何坐標數據，這些幾何坐標數據稱為點云，在此基礎上進行復雜曲面的建模、評價、改進和制造，點云數據處理的好壞程度直接影響整個逆向設計過程的精度[1]。點云數據常用采集方法有CMM 坐標測量、激光掃描等，受測量技術、周圍環境、物體幾何形狀、定位以及夾具等因素的影響，通常需要對物體進行多方位測量，然后將不同方位下測的點云拼合成一個表達完整實物的點云，最后通過模型重建方法生成零件的三維模型[2]，然而這些方法獲取的測量物體表面數據點信息有限，需要進行多次測量。點云的拼合過程就是根據點云間的共有特征信息，設定評判準則，求解坐標系變換的旋轉矩陣和平移矩陣，以將所有點云拼合在同一坐標系下[3]。

點云拼合主要分為兩種方式，一種是基于點云的直接拼合，如最常見的ICP 算法[4]，該算法是將目標點云P與源點云Q 進行比較，匹配得到最接近的點云對，再進行相關運算得到誤差函數，并計算出使得誤差函數最小的參數旋轉矩陣R和平移向量t。在此基礎上，再對目標點云P 進行旋轉和平移變換，得到新的對應點集P′，隨后不斷重復該過程直到目標收斂條件達成。除了應用最廣泛的ICP 算法，還有Horn[5]提出的四元數法，劉宇[6]提出的基于法矢的點云拼合方法，孫世為[7]提出的基于曲率RGB 的多視點云拼合方法等；另一種是基于參考點的間接拼合，孫殿柱[8]、程俊延[9]等通過在零件上粘附一些固定球或者標簽，完成點云的拼合。

基于點云的直接拼合，優點是拼合精度高，缺點是計算難度大、成功率低；基于參考點的間接拼合，優點是拼合簡單、成功率高，缺點是新增物在一定程度上覆蓋了原有零件的部分表面，為后期逆向設計增加了難度[10]。鑒于此，本文基于零件原有的平面、直線或點特征來研究點云的拼合方法，并引入粒子群算法來提高拼合效率。

1 數據測量與處理

1.1 點云及幾何特征的測量

零件表面測量可分為接觸式測量與非接觸式測量兩種方式，接觸式測量主要用不同類型的機械探頭接觸需要測量的物體表面，通過機械臂上的傳感器得到相對坐標位置，最終得到測量零件的特征信息；非接觸式測量則是使用類似光學、聲學等領域的原理知識，再將得到的物理模擬量轉化為測量零件的表面信息[11]。關節臂測量機集兩種測量方式于一身，每次的測量數據可同時包含特征數據及點云數據，根據特征信息完成坐標系變換，即完成了點云數據的拼合。

測量時，會有環境、零件形狀、零件放置方式等因素影響測量結果，因此在測量之前，要做好規劃工作，以起到降低誤差的作用，一是判斷零件表面的顏色是否會產生鏡面反射，再確定掃描次數及放置方式，遵循全面性及穩定性原則，將復雜面朝向容易掃描的方向；二是確定要測量的特征，確保所選的特征比較精確、距離相對較遠且能夠使點云拼合方式唯一[12]。零件放置方式的規劃與特征的選擇相互影響，要綜合考慮，權衡取舍。

1.2 數據處理

通過關節臂測量機測量的平面特征可用4 個點來表達，直線特征可用2個點來表達。以2次掃描測得的數據進行分析，可分別寫成數據集合A={MAI,XAJ,DAK,YAM}，B={MBI,XBJ,DBK,YBN}，其中MAI、MBI均代表I個特征平面組成的集合，分別用4I×3矩陣表示；XAJ、XBJ均代表J個特征直線組成的集合，分別用2J×3 矩陣表示；DAK、DBK均代表K個特征點組成的集合，分別用K×3 矩陣表示；YAM代表M個點組成的點云集合，用M×3矩陣表示；集合YBN代表N個點組成的點云集合，用N×3矩陣表示。

數據集合A中的MAI、XAJ和數據集合B中MBI、XBJ無法直接通過坐標變換建立重合關系，需要變換表達方式，用方向向量和點坐標來表示[13]。其中，方向向量根據特征點的相對位置確定唯一性，點坐標通過特征點在平面或直線上到投影獲得。因此，集合A和B可采用新的表達方式：A={UA,WA,YAm}，B={UB,WB,YBn} 。其中，UA和UB表示方向矩陣；WA和WB表示坐標矩陣。因UB和WB的表達方式分別與UA和WA類似，只給出UA和WA的表達式：

2 拼合算法

2.1 點云拼合的約束特征分析

點云的拼合需要將零件的幾何特征進行對齊才能實現，首先需要確保約束特征達到拼合條件，使得用于拼合的幾何特征是表達三維空間的唯一方式。零件特征可簡化為平面、直線和點，即用這3種特征建立一個唯一的坐標系[14]。

由于特征沒有方向的特性，難以用來直接表達坐標軸，因此可以通過5個元素（原點、x軸、x軸正方向、y軸、y軸正方向）來定義坐標軸，x軸和y軸只是通過同一個原點，沒有方向，滿足這5個元素的特征集則被認為是唯一的定義三維空間[15]。平面、直線和點可以組成多種特征集，如點集、直線集、平面集、平面-直線-點集等。通過分析知，點云的約束特征是否能拼合的判斷方法是這些約束特征是否可以定義唯一的坐標系來表達三維空間，點云約束特征的數量與特征集拼合的可能性成正比。

2.2 計算思路

點云拼合的效果與拼合的適應度函數有關，當適應度函數達到最小值時，點云拼合效果最佳。拼合的適應度函數包含平面、直線與點拼合適應度3 種，平面和直線因為具有無限延伸、沒有邊界的特點，不能采用距離的方式定義其拼合適應度，而點拼合適應度則可以[16]。因此，針對特征拼合效果的評價有3 種方法，一是參數法，即評價平面方程參數、直線方程參數及點坐標參數的數值偏差，這種評價方式屬于直接評價，參數偏差大小與點云的拼合效果成反比；二是距離法，即在一個包含所有點云數據的長方體空間內評價平面、直線及點的最大距離偏差，這種評價方法屬于間接評價，計算相較第一種更復雜，但精度更高；三是組合法，即參數法與距離法的組合使用，結合了兩種評價方式的優勢。

2.3 計算步驟

粒子群算法是一種智能算法，通過群體中每個粒子位置和速度的不斷更新進行迭代計算，來完成對問題尋優[17-18]。粒子群算法與遺傳算法類似，但在解決一些典型函數優化問題時，優化結果會比遺傳算法更佳[19-20]，可以簡化問題解的編碼與適應性函數的選擇等步驟，簡單易實現，且需要調整的參數較少，同時具有收斂速度快的優點，具備良好的應用前景。

粒子群算法計算步驟[21]如下。

（1）將旋轉矩陣R與平移矩陣T組合作為粒子的位置參數，設置粒子群規模，并初始化粒子的位置和速度。

旋轉矩陣R表示為：

平移矩陣T表示為：

（2）計算適應度函數f，并與定義的收斂值ζ進行比較。

（3）更新粒子的位置和速度并再次計算，直至f≤ζ為止。

（4）將旋轉矩陣R與平移矩陣T用于點云YAM的坐標變換，最終實現與點云YBN的拼合。

2.4 參數法適應度函數

確定粒子群算法的變量為旋轉矩陣R和平移矩陣T，根據特征參數的對應關系建立參數法適應度函數。

適應度函數為：

式中：fU為方向矩陣UA經旋轉矩陣變換后與UB的誤差；fW為坐標矩陣WA經坐標變換后與WB的誤差；a為引入的平衡系數，用于平衡方向矩陣和坐標矩陣在元素數值大小方面的差距。

fU和fW的表達式為：

2.5 距離法適應度函數

確定一個長方體區域?，使得點云YBN和經過坐標變換的點云YAM均包含在內：

計算集合B中的某一平面與?的邊線相交得到的交點，再計算幾個交點到經過坐標變換后的集合A中對應平面的垂直距離，取最大值，即表示兩平面在長方體區域?內的最遠距離偏差。用Γ表示?的邊線集，針對集合A和B的i平面計算拼合偏差值fMi：

用Ψ表示?的邊界平面集，針對集合A和B的j直線計算拼合偏差值fXj：

針對集合A和B的k點計算拼合偏差值fDk：

由此得到距離法適應度函數f：

3 實例分析

本文以發動機右半軸支架為例進行分析，兩次測量得到的點云和特征數據如圖1 所示。安裝面、安裝軸與定位孔是這個零件比較重要的特征，因此可以選取一個平面、一條直線、一個特征點來代表這個發動機右半軸支架點云拼合的約束特征。其中，平面表示安裝面，直線表示安裝軸，點表示支架上其中的一個定位孔。

圖1 測量數據

（1）設定適應度允許值為0.1，分別采用參數法與距離法進行計算及收斂性比較，結果如表1 所示。由表可知，參數法的收斂性很好，5 次計算均能夠在10 s 內完成收斂；距離法的收斂效果很差，5 次計算僅有1 次完成收斂。

表1 參數法與距離法收斂性比較

（2）設定適應度允許值為0.01，分別采用參數法與組合法進行計算，其中組合法是進行兩次粒子群計算，第1次采用參數法，第2次采用距離法，第1次的計算結果作為第2次計算的初始值。

比較參數法與組合法的收斂性結果如表2 所示。由表可知，兩種方法的收斂速度相當，組合法的平均收斂速度略低。

表2 參數法與組合法收斂性比較

比較參數法與組合法的拼合精度，選擇拼合后點云的部分截線進行分析，參數法得到的拼合點云存在錯縫，組合法得到的拼合點云重合度較好，如圖2所示。

圖2 拼合精度比較

采用組合法得到拼合點云如圖3 所示，可很好地用于后期的三維模型重建工序。

圖3 組合法拼合的點云

4 結束語

本文基于粒子群算法，采用幾種方法對點云特征進行拼合，結果表明：（1）參數法計算速度快，收斂性好，但整體精度不高；（2）距離法收斂性差，一旦收斂則具有較好的拼合精度；（3）組合法同時具備了參數法與距離法的優點，具有計算速度快，收斂性好，拼合精度高的特點。

本文以發動機右半軸支架為例進行點云拼合方法的研究，最終摸索出了基于零件原有平面、直線或點特征的一種點云拼合方法，通過粒子群算法進行參數法及距離法數學模型的計算，減輕復雜問題的計算負擔；與原拼合方法相比，本文探索的拼合方法拼合速度更快、拼合精度更高，能夠很好地用于點云數據處理，為后期三維模型重建打下堅實的基礎。