基于粒子群算法的三维扫描点云数据在机配准*

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

(大连理工大学 机械工程学院 现代制造研究所，辽宁 大连 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