基于粒子群算法的三維掃描點云數據在機配準*

王永青，冀志超，侯 博，趙 亮

(大連理工大學 機械工程學院 現代制造研究所，遼寧 大連 116024)

基于粒子群算法的三維掃描點云數據在機配準*

王永青，冀志超，侯 博，趙 亮

(大連理工大學 機械工程學院 現代制造研究所，遼寧 大連 116024)

針對配準過程中經典ICP算法存在的對初始位置要求高、效率低、不易收斂、與加工環節分離等問題，文章提出一種對于掃描點云數據的基于粒子群優化算法的改進ICP配準算法，并嵌入測量-加工一體化設備內，實現配準過程的在機操作。針對使用回轉截面線法掃描得到的掃描點云數據，采用弦高差法進行數據的去噪和精簡處理，使用改進后的粒子群優化算法進行預配準，再利用基于K-Dtree數據結構加速的ICP算法進行精配準。結果表明：該方法降低了ICP算法配準時對于初始位置的高要求，配準后葉片加工部位偏差處于±0.5mm范圍以內。通過基于數控機床和數控系統的實驗平臺的在機實驗，驗證了所提出的在機配準方法，能夠滿足工件下一步加工需要。

粒子群算法；在機配準；點云數據；回轉截面線法

0 引言

為了提高工件加工精度及加工效率，測量-加工一體化設備已得到越來越廣泛的關注。在測量-加工一體化設備的工作過程中，測量環節影響著后續加工環節的結果。激光掃描工件表面實際形貌的點云數據與原始設計模型數據進行配準及比對，進而獲得下一步加工余量等加工信息。近年來，國內外眾多學者已經提出了很多配準方法：朱延娟等[1]使用點云數據的曲率和法矢等特征進行粗配準，但算法復雜速度較慢；Besl等[2]提出了經典的ICP算法來進行配準。它具有較好的配準精度，但它對兩組點云間的初始位置要求較高，如果初始位置相差太大，則ICP算法有可能不收斂。Masuda等人[3]提出了一種使用最小中值平方法取代最小平方法的改進ICP算法；Y.Chen[4]提出了使用切平面來逼近點云的方法對ICP算法進行改進，但配準需要較好的初值。

常見的初始配準方法有：中心重合法[5]，即簡單的把兩組點云的重心重合，這種方法只能縮小平移錯位而無法縮小旋轉錯位；標記點法[6-7]，即在測量時認為的貼上一些特征點，通過不同視角下的對應標記點進行定位，這種方法依賴于測量儀器及人工操作；提取特征法[8]，即通過提取測量點云上的平面特征或輪廓線特征來進行定位，但要求測量點云具有比較明顯的易提取特征。

本文針對使用回轉截面線法測量得到的一系列掃描點云數據，對目前點云配準算法進行了研究和分析，并基于數控機床和數控系統的實驗平臺進行了在機實驗驗證。

1 基于粒子群優化算法的改進ICP算法

本文的方法是將兩組點云數據間最小歐氏距離代數和作為對粒子群優化算法的優化函數進行改進，并引入全局最優值停滯步長因子來增強粒子搜索能力，避免局部收斂，針對三維散亂點云數據進行全局搜索。然后得到兩組點云數據間一個較好的相對位置作為下一步精配準的初值，并使用K-Dtree數據結構搜索最近點來對精配準過程進行加速，最終得到滿足精度要求的配準結果。

1.1 粒子群優化算法原理

粒子群算法(PSO算法)[9-10]是一種基于群體智能方法的演化計算優化技術。它具有獨特的搜索機理，優良的收斂性能，算法簡單易于計算機實現，在工程優化領域得到了廣泛應用。粒子群算法最主要的用途是來求解全局最優解。每個粒子更新的自身速度V及位置X的數學描述如下：

vi(t+1)=vi+c1·r1(t)·(pbest-xi(t))+c2·r2(t)·(gbest-xi(y))

xi(t+1)=xi(t)+vi(t+1)

(1)

其中,c1與c2為非負的學習因子；r1(t)與r2(t)為介于0～1間的隨機數；pbest是第i個粒子搜索到的個體最好位置；gbest是所有粒子目前為止搜索到的全局最好位置。通過不斷迭代更新粒子群中各粒子位置，即可找到全局最優解。

1.2 點云配準目標函數的建立

對激光掃描得到的掃描點集Dp={pi∈R3，i=1，2，……，m}。與待配準模型點云點集Dq={qj∈R3，j=1，2，……，n}之間建立起粒子群優化的優化函數Ft：

Ft=min∑m,ni=1,j=1‖qj-(Rpi+T)‖

(2)

其中,R和T是兩組掃描點云數據間的旋轉量和平移量。其中R=Rx、Ry、Rz，分別為繞x軸，y軸和z軸的旋轉角度；T=Tx、Ty、Tz，分別為沿x軸，y軸和z軸的平移距離。

1.3 基于粒子群算法的改進ICP算法

經典粒子群算法雖然收斂速度快，但容易忽略對未來有貢獻潛力的粒子，導致群體中粒子多樣性迅速降低，因此，粒子群算法的搜索容易停滯在一個最先搜索到的局部最優值導致搜索范圍減小，搜索速度變慢，產生過早收斂的現象。

為此，在全局粒子群算法的基礎上，引入如下改進策略：

(1)引入一個慣性權重方案[11-12]，在粒子群中引入一個慣性權重因子ω(t)。慣性權重因子ω(t)能夠控制當前粒子的飛行速度，對粒子下一步飛行速度的飛行方向進行影響。當ω(t)值比較大時，粒子群算法的全局搜索能力較強，能夠控制當前粒子往更遠更新的空間飛行搜索；當ω(t)值比較小時，粒子群算法的局部搜索能力較強，能夠得到更精確的最優值。

(2)引入全局最優值停滯步數NGbest用來判斷當前全局最優值Gbest是否陷入局部最優值當中。當全局最優值Gbest在一段時期閾值內一直沒有出現更優值來代替它，即NGbest大于一定閾值，則判斷粒子群搜索可能陷入一個局部極值范圍內。此時調用慣性權重因子ω(t)對當前粒子速度進行影響：

vi(t+1)=ω(t)·vi+c1·r1(t)·(pbest-xi(t))+
c2·r2(t)·(gbest-xi(y))

(3)

通過改變ω(t)增強當前粒子的全局搜索能力，不斷搜索新的搜索空間，找到潛在的更優值，使整個粒子群逃離處當前局部極值。

(3)當迭代次數達到最大迭代次數或適應度函數小于最小誤差，即達到迭代終止條件，此時終止迭代，輸出迭代優化結果。

(4)將粒子群算法優化結果作為ICP精配準算法的優良初值，結合適用于空間最近鄰域搜索的k-dtree數據結構，即可得到滿足要求的旋轉矩陣R和平移矩陣T。

綜上，整個算法流程如圖1所示。

圖1 配準算法流程圖

2 在機實驗及配準

2.1 實驗材料

實驗材料為船用螺旋槳葉片的廓型，如圖2所示。其槳葉表面形狀為三維螺旋自由曲面，各處薄厚不均，因此數控加工困難，多使用手工鏟磨方式加工，加工質量難以保證。

圖2 實驗葉片

2.2 實驗裝置

實驗裝置為五軸聯動測量加工一體化龍門磨床，如圖3所示。X軸行程2000mm，Z軸行程1200mm，X/Z軸定位精度0.02mm，重復定位精度0.012mm。配備西門子840D-SL數控系統為控制核心，其主要配置為：系統主控模塊NCU572.5，驅動單元Simodrive611D；人機交互操作單元為PCU50.3-P，操作面板OP012，機床控制面板MCP483C；可編程邏輯控制單元為SimaticS7-300(CPU317-2DP)；數控系統二次開發軟件包為840DHMIProgramming-Package。

2.3 測量裝置

數據采集裝置為激光位移傳感器，型號為OptoNCDT1300-50，如圖4所示。測量范圍為45mm～ 95mm，絕對誤差≤±0.2%，靜態分辨率為10μm，測量頻率為500Hz。

圖3 實驗機床

圖4 掃描裝置

2.4 在機數據測量及精簡方法

圖5 回轉截面線法原理

實驗使用回轉截面線法對螺旋槳葉片表面形貌進行數據采集。該方法具有連續、快速提取曲面測點坐標的特點。待測曲面被一組稱作數字化曲面的回轉曲面分割，分割所得截交曲線成為數字化曲線。在測量過程中，激光位于傳感器入射光與反射光組成的平面上并與龍門機床Y軸垂直，入射光方向與Z軸平行，激光位移傳感器沿Z軸做一維仿形退讓動作，龍門機床C軸θ坐標系做進給運動，采用θ坐標與Z坐標聯動方式，使激光位移傳感器沿數字化曲線對曲面進行測量。基于回轉截面的坐標提取原理如圖5所示。激光位移傳感器的測量運動被約束在不同半徑的回轉曲面{Πj}內。

圖6 在機數據精簡原理

在機精簡方法如下：

首先，測量系統按照等時采樣記錄第一個采樣點Pi作為初始記錄點；然后，在每個采樣周期里，測量系統不斷計算當前采樣點Pi+n和上一個記錄點Pi的連線到兩點間實際曲線軌跡的最大弦高hmax。弦高hmax可以通過下式計算得出：

h(i+m)=|A(x(i+m)-xi)-B(y(i+m)-yi)|/A2+B2

(4)

圖7 葉片測量過程

其中，A=yi+n-yi，B=xi+n-xi，(xi，yi)、(xi+m，yi+m)、(xi+n，yi+n)分別是點Pi、Pi+m、Pi+n的坐標值。然后對所有計算求得的弦高h(i+1)，h(i+2)，……，h(i+m)，……，h(i+n-1)進行比較，求得最大弦高hmax并將其與預設逼近精度ε進行比較。如果hmax<ε，則與hmax相對應的采樣點不會被記錄。令i+1→i按下一個采樣點計算求解與之對應的hmax，直至hmax>ε，則將Pi-1點記錄，并作為下一個周期求解最大弦高hmax的參考記錄點。循環上述過程，直至整個測量過程結束，從而實現掃描點數據的精簡處理。

2.5 在機配準

本實驗采用MicrosoftVisualC++6.0與VisualBasic混編方法實現本文提出的粒子群改進ICP算法，完成算法的人機交互界面可視化設計，并將程序嵌入到測量-加工一體化龍門磨床數控系統Sinumerik840D標準HMI中，實現了在機測量-在機精簡-在機配準-在機加工的一系列連續在機過程。并對如表1所示回轉截面線法掃描點云數據進行了在機配準實驗。

表1 掃描數據

3 在機實驗結果及分析

二次開發后的數控系統開機運行后，顯示如圖8所示在機配準模塊界面。圖9a顯示了使用等弦高差法精簡點云數據的結果；圖9b顯示讀入模型點云數據；圖9c顯示使用基于粒子群算法的改進ICP算法配準后的結果。

圖8 在機配準界面

(a) 精簡點云數據

(b) 讀入模型點云

(c) 配準結果圖9 點云數據

通過顯示配準偏差可以看出，在螺旋槳葉片的主要加工部位配準后的偏差大約在±0.5mm以內，說明配準效果比較好，對于直徑約三米的大型螺旋槳，配準誤差能夠接受且數據可以用于下一步磨拋加工余量的計算。等弦高差法對于人為引入的測量誤差產生的噪點也具有很好的精簡去噪效果，保證了測量數據的準確性；螺旋槳葉片型面是典型的自由曲面，表面不具有易于提取的幾何特征，此配準方法對于自由曲面具有很好的適用性。

圖10 配準偏差

4 結論

(1)針對測量加工一體化設備測量環節中點云數據配準問題，本文提出了一種基于粒子群優化的改進ICP算法。

(2)該改進的ICP算法可以有效地提高ICP算法

初始位置精度，提高了配準效率。

(3)針對基于回轉截面法掃描點云數據進行弦高差法精簡處理，并在實際在機試驗中驗證了本文方法的可行性與有效性，結果可以滿足工件下一步加工需求，實現了在機測量-在機配準-在機加工一體化。

[1] 朱延娟, 周來水, 張麗艷. 散亂點云數據配準算法[J]. 計算機輔助設計與圖形學學報, 2006, 18(4):475-481.

[2]PJBesl,NDMckay.Methodforregistrationof3-Dshapes[C]//Robotics-DLtentative.InternationalSocietyforOpticsandPhotonics, 1992: 586-606.

[3]TMasuda，NYokoya.Arobustmethodforregistrationandsegmentationofmultiplerangeimages[J].ComputerVisionandImageUnderstanding, 1995, 61(3): 295-307.

[4]YChen,GMedioni.Objectmodellingbyregistrationofmultiplerangeimages[J].Imageandvisioncomputing, 1992,10(3): 145-155.

[5]XZhang,JXi,JYan.Researchondigitalmeasurementtechnologybasedonpointclouddataofcomplexsurfaces[J].COMPUTERINTEGRATEDMANUFACTURINGSYSTEMS-BEIJING, 2005, 11(5): 727.

[6] 羅先波，鐘約先，李仁舉. 三維掃描系統中的數據配準技術[J]. 清華大學學報: 自然科學版, 2004, 44(8):1104-1106.

[7] 吳敏，周來水，王占東,等. 測量點云數據的多視拼合技術研究[J]. 南京航空航天大學學報, 2003, 35(5):552-557.

[8] 何文峰，查紅彬. 基于平面特征的深度圖像配準[A]. 中國人工智能進展.上卷[C]. 北京:北京郵電大學出版社, 2003:643-648.

[9]JKennedy.RParticleswarmoptimization[M].Encyclopediaofmachinelearning.US:Springer,2011.

[10] 黃太安, 生佳根, 徐紅洋, 等. 一種改進的簡化粒子群算法[J]. 計算機仿真, 2013, 30(2): 327-330.

[11]REberhart,YShi.Particleswarmoptimization:developments,applicationsandresources[C]//evolutionarycomputation, 2001.Proceedingsofthe2001Congresson,IEEE, 2001, 1: 81-86.

[12] 孫湘, 周大為, 張希望. 慣性權重粒子群算法模型收斂性分析及參數選擇[J]. 計算機工程與設計, 2010,31(18):4068-4071.

(編輯 李秀敏)

On-Machine 3-D Scanned Point Registration Based on Improved Particle Swarm Optimization

WANGYong-qing，JIZhi-chao，HOUBo，ZHAOLiang

(ModernManufacturingInstitute，SchoolofMechanicalEngineering，DalianUniversityofTechnology，DalianLiaoning116024，China)

Duetothehighdemandforinitialposition,lowefficiency,difficultconvergenceandthedisengagementofprocessingproblemsinICPinregistration,animprovedICPregistrationmethodbasedonimprovedparticleswarmoptimizationisproposedtorealizetheon-machineregistration.Fortherotary-section-line-basedsampledpointdata,firstlytheequalchordheighterroralgorithmisusedtoreducedata,thentheimprovedSPOisusedtofinishtheroughregistrationandusingtheresultstofinishtheK-D-tree-basedICPregistration.Theon-machineexperimentresultsshowsthattheerrorofregistrationcanbecontrolledbetween0.5mmandtheresultsofregistrationcanbefulfillthedemandofnextprocessing.

particleswarmoptimization；on-machineregistration；pointcloud；rotarysectionline

1001-2265(2016)12-0023-04DOI:10.13462/j.cnki.mmtamt.2016.12.007

2016-02-22；

2016-03-24

國家973計劃課題(2014CB046604)

王永青(1969—)，男，內蒙古赤峰人，大連理工大學教授，博士，研究方向為復雜曲面數字化加工技術與裝備，(E-mail)yqwang@dlut.edu.cn。

TH16；TG

A