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

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

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

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

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

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

粒子群算法；在機配準；點云數(shù)據(jù)；回轉(zhuǎn)截面線法

0 引言

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

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

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

1 基于粒子群優(yōu)化算法的改進ICP算法

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

1.1 粒子群優(yōu)化算法原理

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

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間的隨機數(shù)；pbest是第i個粒子搜索到的個體最好位置；gbest是所有粒子目前為止搜索到的全局最好位置。通過不斷迭代更新粒子群中各粒子位置，即可找到全局最優(yōu)解。

1.2 點云配準目標函數(shù)的建立

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

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

(2)

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

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

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

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

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

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

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

(3)

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

(3)當?shù)螖?shù)達到最大迭代次數(shù)或適應(yīng)度函數(shù)小于最小誤差，即達到迭代終止條件，此時終止迭代，輸出迭代優(yōu)化結(jié)果。

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

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

圖1 配準算法流程圖

2 在機實驗及配準

2.1 實驗材料

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

圖2 實驗葉片

2.2 實驗裝置

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

2.3 測量裝置

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

圖3 實驗機床

圖4 掃描裝置

2.4 在機數(shù)據(jù)測量及精簡方法

圖5 回轉(zhuǎn)截面線法原理

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

圖6 在機數(shù)據(jù)精簡原理

在機精簡方法如下：

首先，測量系統(tǒng)按照等時采樣記錄第一個采樣點Pi作為初始記錄點；然后，在每個采樣周期里，測量系統(tǒng)不斷計算當前采樣點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并將其與預(yù)設(shè)逼近精度ε進行比較。如果hmax<ε，則與hmax相對應(yīng)的采樣點不會被記錄。令i+1→i按下一個采樣點計算求解與之對應(yīng)的hmax，直至hmax>ε，則將Pi-1點記錄，并作為下一個周期求解最大弦高hmax的參考記錄點。循環(huán)上述過程，直至整個測量過程結(jié)束，從而實現(xiàn)掃描點數(shù)據(jù)的精簡處理。

2.5 在機配準

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

表1 掃描數(shù)據(jù)

3 在機實驗結(jié)果及分析

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

圖8 在機配準界面

(a) 精簡點云數(shù)據(jù)

(b) 讀入模型點云

(c) 配準結(jié)果圖9 點云數(shù)據(jù)

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

圖10 配準偏差

4 結(jié)論

(1)針對測量加工一體化設(shè)備測量環(huán)節(jié)中點云數(shù)據(jù)配準問題，本文提出了一種基于粒子群優(yōu)化的改進ICP算法。

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

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

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

[1] 朱延娟, 周來水, 張麗艷. 散亂點云數(shù)據(jù)配準算法[J]. 計算機輔助設(shè)計與圖形學學報, 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] 羅先波，鐘約先，李仁舉. 三維掃描系統(tǒng)中的數(shù)據(jù)配準技術(shù)[J]. 清華大學學報: 自然科學版, 2004, 44(8):1104-1106.

[7] 吳敏，周來水，王占東,等. 測量點云數(shù)據(jù)的多視拼合技術(shù)研究[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] 孫湘, 周大為, 張希望. 慣性權(quán)重粒子群算法模型收斂性分析及參數(shù)選擇[J]. 計算機工程與設(shè)計, 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—)，男，內(nèi)蒙古赤峰人，大連理工大學教授，博士，研究方向為復(fù)雜曲面數(shù)字化加工技術(shù)與裝備，(E-mail)yqwang@dlut.edu.cn。

TH16；TG

A