基于自由曲面的点云配准算法

卢章平，郑 航，沙春发，李明珠

(江苏大学机械工程学院，江苏镇江 212013)

在现阶段的工业制造领域，某些自由曲面零件(如钛合金蒙皮)工艺要求其处于非约束状态，不能安放零件固定装置，这样导致模型压制后曲面的位置和姿态会存在变动而无法完成后续打孔、切割等工序的精确定位.按照传统的“靠模+专用夹具”工装进行定位，制造成本高，柔性差.为解决这一问题，文中提出一种基于自由曲面的点云配准方法，对2组点云模型进行配准来实现曲面零件的精确寻位，使工艺过程无需使用专用工装定位.实现工件精确寻位的关键在于能否实现点云数据之间的准确匹配.

所谓点云配准，就是将2组或者2组以上具有重复区域的点云数据，根据数据隐含的源误差，计算点云之间的平移错位和旋转错位，从而转换到统一坐标系下的数学计算过程［1］.点云配准通常分为初始配准和精确配准2个步骤.初始配准是为了缩小2组点云之间错位，提供给后续精确配准良好的初始值以提高精确配准的效率和趋向，精确配准是为使2组点云之间的配准误差达到最小［2］.

当前，自动配准技术在工程中的使用较为广泛，支撑该技术的算法大致可分为以下2类:基于特征的配准算法和迭代配准算法.Meng Yu等［3］提出了基于法向的采样球匹配算法，王欣等［4］则以点云边界特征点作为联系特征进行初始配准.迭代配准算法中，最具代表性的算法是P.J.Besl等［5］于1992年提出的迭代最近点(iterative closest point，ICP)算法.由于ICP算法对点云数据的初始位置和包含关系要求较高，所以在精确配准之前，需要先通过初始配准得到一个大体对齐的配准模型.传统的配准方法在配准精度或时间复杂度等方面有待进一步提高，且往往忽略了噪声点的影响，导致算法鲁棒性不高.

为了提高点云配准的精度，加快配准效率，文中拟设计一种用于点云数据配准的分阶段配准算法，为精确寻位提供理论支撑.

1 点云初始配准

1.1 基于共面4点集的RANSAC算法

RANSAC(random sample consensus)即随机采样一致性算法，其基本思想如下:起初利用尽可能小的一部分采样数据作为内点，估计出模型参数，然后在采样集中选择符合模型参数的数据点来尽量扩大初始采样集，并通过不断重复的迭代，产生最大一致性数据集［6］.

同时，根据视觉几何原理，共面4点的长度和交点分得对应线段间的比例具有欧式特征不变性.图1为共面4点集.

图1 共面4点集

如图1所示，数据集P中4点{a，b，c，d}与点集Q中的共面4点{a'，b'，c'，d'}组成共面4点集，且公式

中2条线段的长度及比例r1，r2在刚体变换下都是欧式不变量.因此，通过共面4点集提取的4对匹配点对可以作为RANSAC算法的初始样本.

1.2 初始配准算法步骤

根据前面的分析，下面详细说明基于共面4点集的RANSAC算法步骤:

1)在目标点集P中，随机选取同一平面上不共线的4 个点{a，b，c，d}，其中应满足0 ＜ri＜1(i=1，2)，若不符合条件则重新选取4点;

2)在参考点集Q中，寻找对应的4点集{a'，b'，c'，d'}.根据欧式不变性可以得出在点集Q中点间距离为d1或d2的任意2点对都是可能的对应点，分别存放在集合S和集合T中;

3)对于集合S中的所有点对，根据比例r1计算出每一线段的2个交点 e1，e2，其中 e1=a'+r1×(b'-a')，e2=b'+r1(a'-b').同样，根据比例r2计算出集合T中每一线段的2个交点e3，e4，其中e3=d'+r2(c'-d')，e4=c'+r2(d'-c').因为比例r1，r2不会随着点云的坐标变换而改变，所以，如果集合S和集合T中某2条线段根据比例计算出的交点满足eS≈eT，则可以确定这2条线段的4个端点就是对应的 4 点集{a'，b'，c'，d'}，如图2 所示;

图2 相同交点确定对应4点集

4)利用得到的共面4点集作为内点，进行2组点云的欧式变换矩阵Hc的估计;

5)计算在变换矩阵Hc和误差阈值ε下，目标点云P和参考点云Q之间的一致程度，如果满足误差的对应点对总数大于一个阈值，则输出变换矩阵，相反如果在误差阈值ε下，匹配点对数目小于给定的阈值，则返回步骤1)继续迭代;

6)迭代K次，即经过K次随机取样，选择2个点集对应一致程度最大的变换矩阵H.

2 点云精确配准

经过初始配准后，虽然在很大程度上缩小了参考点云和目标点云的旋转和平移错位，但是其精度仍很难满足要求，所以在初始配准后，又加入了精确配准的操作，使得点云之间的配准误差达到最小.精确配准一般采用迭代的方法，相对靠近的点云位置也为ICP配准创造了有利的初始条件.

2.1 ICP算法概述

1)设定阈值τ＞0，作为迭代终止的条件;

2)对于目标点集P中的每个数据点pi，从参考点集Q中搜索相应的最近点p'i;

4)将刚体变换矩阵Hk作用于目标点集P，得到更新的目标点集P'k+1=Rkpi+Tk;

2.2 精确配准算法的关键步骤

虽然ICP算法在精确配准领域取得了很好的应用，但其仍然存在一定的问题和局限性，例如配准可能收敛于局部最小、时间复杂度高、无法排除错误匹配点对等［7-8］.故文中使用精确配准的关键步骤如下:

1)源数据集的重采样.算法的精度取决于匹配点对的准确性，而不在于待匹配点数目的多少，因此可以从目标点云中采样部分的点作为待匹配点.对源数据集进行降采样后，能够使数据量大为减少，不仅减少了后续的计算时间，而且初步去除一些外点的影响，增强了点集的可靠性.所以，文中选择随机采样这一简单快速的降采样方法，对目标点云进行随机均匀采样，而在整个参考点云中寻找匹配点，则不会改变匹配点对的对应关系，改变的只是匹配点对的数量.如此，就合理减少了源点集数据量，有效减少迭代计算时间.

2)匹配点对的确立.对于重采样之后的每个采样点，都需要在参考点云中找到其对应点进行匹配.利用最近点匹配法对往往无法准确得到对应点，因此，在配准之前，有必要按照一定的策略确定匹配点对.文中使用双法向投影匹配策略:对于重采样后点云P上的一点pi，使其沿着该点法矢量方向在另一个数据集拟合曲面上进行投影，若投影交点恰好为点云Q上的数据点qi，再确定qi沿着其法矢量在点云P上的投影点m，假如‖pi-m‖≤t，则获得一组初始配准点对(pi，qi);若pi的投影点m不是点云Q上的数据点，则在阈值t范围内寻找最近点，同样再将该最近点法向投射到点云P上，在满足‖p2-m'‖≤t的条件下，也可获得初始匹配点对(p2，q2).利用相同的方法则可以找出所有匹配点对，如图3所示.

图3 匹配点对的确立

3)不可靠点对的剔除.采用上述方法确立的匹配点集不可避免地存在不可靠点对，在算法迭代初期尤为明显.为了消除不可靠点对对于配准结果的影响，必须尽量剔除错误的匹配点对.文中提出利用约束点对以及匹配点的曲率特征来剔除不可靠点对，在选择匹配点对时附加以下约束条件:根据匹配点对间距离的分布，每次迭代均剔除与距离均值相差较大的点对;匹配点对应具有相似的曲率值.匹配点对的距离依据刚体运动一致性原理，反映的是曲面上点和点之间的约束关系;曲率特征约束依据曲面上点的几何特征不变性原理，反映的是单个点本身的约束.通过结合这2类约束，能有效去除不可靠点对，消除其对匹配结果的不利影响.

精确配准流程如图4所示.

图4 改进ICP算法流程图

3 仿真实例与应用效果

仿真采用2组简单的CAD曲面轮廓点云，试验平台在Intel Pentium Dual CPU，2 GB内存的计算机上使用Matlab实现.试验结果如图5-7所示.

图5展示了2组自由曲面在初始配准阶段寻找到的共面4点集，通过该对应关系计算出刚性矩阵完成初始配准，得到的结果如图6所示.

图5 共面4点集

图6 初始配准效果

从图6可见，文中初始配准算法的效果良好，大部分数据点已接近配准范围，但是仍然需要通过二次配准进一步提高匹配的精确度.

精确配准阶段以初配结果作为新的初始位置，目标点云经过重采样后的所有点在参考点云中寻找匹配点，最终精确配准的效果如图7所示，可见基本上能达到较为满意的配准精度.

图7 精确配准效果

另外，文中采用以下几种算法或算法的组合进行点云配准并比较配准的效果:传统的基于特征的初始配准算法［9］、文中初配准算法、文中初配准算法+ICP算法、文中初配准算法+改进ICP算法.表1和表2列出了2组点云模型使用以上算法或算法组合进行配准的运行时间和配准误差.

表1 第1组曲面点云数据配准比较

表2 第2组曲面点云数据配准比较

分析表1-2中数据可知，基于特征的初配算法虽然在精度上与本文算法相差不大，但是其要计算每个点的曲率等信息，故导致时间复杂度过高，同时，基于曲率等几何特征的匹配对曲面类型有一定要求，若曲面较为平坦，曲率变化不明显的情况下，该方法可能失效.此外，文献［10］指出，基于RANSAC框架的配准算法对噪声的鲁棒性较高，即使在较多无关点的干扰下配准精确也可以得到保证，这是传统算法所不具备的.在初配准基础上，改进的ICP算法通过减少点数据量以及对匹配点对的引导，配准的速度和精度也都明显优于原始算法，配准效果更佳.

4 结论

1)相对于传统ICP算法，文中提出的基于自由曲面的点云配准算法减少了配准时间，提高了配准精度.

2)在进行精确配准之前加入初始配准能够避免算法陷入局部极值，可获得更小的误差并且加快收敛速度.

3)文中算法虽然在仿真实例中有良好效果，但是仍需要通过不同类型的曲面来比较结果，以便为工件后续加工提供可靠的位姿参照，这也是以后的研究重点之一.

References)

［1］施贵刚，程效军，官云兰，等.地面三维激光扫描点云配准的最佳距离［J］.江苏大学学报:自然科学版，2009，30(2):197-200，208.

Shi Guigang，Cheng Xiaojun，Guan Yunlan，et al.Best distance of terrestrial 3D laser scanning point cloud registration［J］.Journal of Jiangsu University:Natural Science Edition，2009，30(2):197-200，208.(in Chinese)

［2］杨现辉，王惠南.ICP算法在3D点云配准中的应用研究［J］.计算机仿真，2010，27(8):235-238.

Yang Xianhui，Wang Huinan.Application research of ICP algorithm in 3D point cloud alignment［J］.Computer Simulation，2010，27(8):235-238.(in Chinese)

［3］Meng Yu，Zhang Hui.Registration of point clouds using sample-sphere and adaptive distance restriction［J］.The Visual Computer，2011，27(6/7/8):543-553.

［4］王 欣，张明明，于 晓，等.应用改进迭代最近点方法的点云数据配准［J］.光学精密工程，2012，20(9):2068-2077.

Wang Xin，Zhang Mingming，Yu Xiao，et al.Point cloud registration based on improved iterative closest point method［J］.Optics and Precision Engineering，2012，20(9):2068-2077.(in Chinese)

［5］Besl P J，McKay N D.A method for registration of 3-D shapes［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14(2):239-256.

［6］钱鹏鹏，郑德华.一种新的扫描点云自动配准方法［J］.水利与建筑工程学报，2013，11(3):162-164.

Qian Pengpeng，Zheng Dehua.A new automatic registration method of scanning point cloud［J］.Journal of Water Resources and Architectural Engineering，2013，11(3):162-164.(in Chinese)

［7］Senin N，Colosimo B M，Pacella M.Point set augmentation through fitting for enhanced ICP registration of point clouds in multisensor coordinate metrology［J］.Robotics and Computer-Integrated Manufacturing，2013，29(1):39-52.

［8］周春艳，李 勇，邹峥嵘.三维点云ICP算法改进研究［J］.计算机技术与发展，2011，21(8):75-77.

Zhou Chunyan，Li Yong，Zou Zhengrong.Three-dimensional cloud ICP algorithm improvement［J］.Computer Technology and Development，2011，21(8):75-77.(in Chinese)

［9］Ko K H，Maekawa T，Patrikalakis N M.An algorithm for optimal free-form object matching［J］.Computer-Aided Design，2003，35(10):913-923.

［10］Papazov C，Burschka D.An efficient RANSAC for 3D object recognition in noisy and occluded scenes［C］∥Proceedings of the10th Asian Conference on Computer Vision Computer Vision.Heidelberg:Springer Verlag，2011:135-148.