第34卷第5期2019年10月遥感信息Remote Sensing InformationVol.34,No.5Oct.,2019结合尺度不变特征的Super4PCS点云配准方法鲁铁定3,袁志聪i,郑坤i(1.东华理工大学，南昌330013；2,流域生态与地理环境监测国家测绘地理信息局重点实验室，南昌330013)摘要：点云配准是三维模型重建中的关键步骤。
针对传统初配准方法效率低等问题，提出一种结合点云特征的超四点快速鲁棒匹配算法(super four point fast robust matching algorithm,Super4PCS)。
首先对点云数据进行尺度不变特征提取，凸显点云的局部特征；然后把提取的特征点作为Super4PCS算法的初始值，以便实现源点云与目标点云的初配准；最后在初配准的基础上利用最近点迭代(ICP)算法进行精确配准。
通过斯坦福兔子点云及实测点云数据对比分析，表明该算法具有更好的配准性能。
关键词：点云配准；尺度不变特征；特征点；超四点快速鲁棒匹配算法；ICP算法doi：10.3969/j.issn.1000-3177.2019.05.005中图分类号:P232文献标志码：A文章编号：1000-3177(2019)165-0015-06Super4PCS Point Cloud Registration Algorithm CombiningScale Invariant FeaturesLU Tieding1'2,YUAN Zhicong1,ZHENG Kun1(1.East China University of Science and Technology,Nanchang330013t China;2.Key Laboratory Watershed Ecology and Geographical Environment Monitoring,National Administration of Surveying^Mapping and Geoinformation,Nanchang3300131China}Abstract:Point cloud registration is the key step in3D model reconstruction.In view of the low efficiency of the traditional initial registration methods,a super four point fast robust matching algorithm(Super4PCS)is proposed,which combines the feature of point cloud.Firstly,scale-invariant feature extraction is performed,to highlight the local features of the point cloud. Then,the extracted feature points are used as the initial values of the Super4PCS algorithm so as to realize initial registration between the source and the target point cloud・Finally,the closest point iteration(ICP)algorithm is used for accurate registration on the basis of the initial registration.By comparing and analyzing Stanford rabbit point cloud and measured point cloud data,the results show that the proposed algorithm has better registration performance.Key words:point cloud registration；scale invariant feature；feature point；Super4PCS；ICP algorithm0引言随着三维激光扫描技术的快速发展，三维重建技术的应用越来越广泛。
点云配准是三维模型重建中的关键环节，点云配准按配准步骤可分为初配准和精配准初配准能够很大程度上减小两点云的旋转和平移错位,为精配准提供一个好的初始位置，提高配准精度和效率。
常用的初配准□切方法有主成分分析法、标签法、中心重合法、4PCS算法3等。
精配准是在初配准的基础上对点云进行精确配准，使两点云尽可能地重合，即两点云的距离之和最小。
应用最广的精配准方法是由Besl和Mkcya提出的最近点迭代金门(ICP)算法。
近年来，Nicolas Mellado等田切提出的Super收稿日期:2018-04-28修订日期：2019-07-17基金项目：国家自然科学基金(41464001);国家重点研发计划(2016YFB0501405);国家重点研发计划(2016YFB0502601-04);江西省自然科学基金(2017BAB203032)。
作者简介:鲁铁定(1974—),男，教授，主要研究方向为测绘数据处理。
E-mail:tdlu@遥感信息2019年5期4PCS 算法逐渐得到人们的关注。
相对于4PCS 算法,Super 4PCS 算法利用智能索引极大地提高了点 云初配准的速率M ,同时Super 4PCS 也存在一些 不足，当点云本身具有堆成性时容易出现错误匹配等。
Rongchun Zhang 等口幻结合 Super 4PCS 算法 与旋转影像完成点云配准，利用旋转影像对Super4PCS 算法进行了优化。
针对Super 4PCS 算法的不足,本文通过结合3D-SiFT^切算法与super 4PCS 算法进行点云配准，利用3DSIFT 算法提取特征点，将整片点云缩至特征点 集，缩短点对提取时间，同时提高点对提取的准确率，最后设计了实验，比分析了相关算法的配准性能。
1 Super 4PCS 算法原理1.1 4PCS 算法原理4PCS 算法亦称为四点鲁棒快速匹配算法，是一种全局快速匹配算法,其原理为：假设点云P , Q分别为源点云和目标点云，4PCS 算法以共面不共 线的四点作为配准点基，首先在点云P 中选取4个 共面不共线的点作为点基(点基称作C),如图1(a)所示，在P 中选取的4点必须是P , Q 重叠区域的点,然后在Q 中利用点对间的距离与仿射不变性质寻找所有近似全等的点基集合= {D 1(D 2,6,…,D"}。
由于目标点云中有很多点对并不符合要求，如图1(b)所示，gig ：属于错误匹配点对，gig ； 与之间的角度不符合要求，利用C 与进行刚体运动估计,得到二者的刚体变换T,•，即对P 进行T ；变换后，T.(P)与Q 之间欧式距离平方和最小。
4PCS 算法具有较好的配准精度，但是其时间复杂度达到了二次，效率不高。
图1点云与目标点云点基1.2 Super 4PCS 算法配准原理在Super 4PCS ［8］算法中，利用球体提取点对，大 大提高了点对提取的效率。
在点云Q 中，以g,(i = l,2,…”)，为球心，半径为厂做球面，图2(a)为二维表达形式，在Q 中可做”个球面,形成球面集合，给定一误差限e ,落在区间Er-e,r+e ］上的点都符合要 求，如图2(a)中蓝色点所示。
将点云Q 进行不断剖分,以阵列存储落在区间Er-e,r + e ］上的点(图2(b)),图中蓝色点为提取的点对，黑色点为不符合要求的点，点对提取之后，利用仿射不变性质在Q 中提取与pipipspt 对应的Qi qiqsqt ，令P1P2为,PzPi 为r 2，记Q 中对应九的点对集合为Si ，对应r 2集合的点对为S2 ,对S1S2中任意点对，计算并存储对应的方向向量。
利用仿射不变性质都能求得一 交点e (图2(c)),根据方向向量以及角度0，给定区间Lr-e,r + e ］，即可在Q 中获得唯一的四点，如图2(d)所示。
2 改进Super 4PCS 算法原理2.1 3D-SIFT 算法原理尺度不变特征转换特征提取算法(sale ivariantfature tansform , SIFT)最先应用在图像处理中。
3D-SIFT 算法是由二维的SIFT ［15］算法转换而来的，利用点云的曲率值代替二维图像的强度值，建立 体素的尺度空间来提取特征点.3D-SIFT 算法的主要原理如下：①建立点云的尺度空间。
在三维点云空间中，通过体素栅格的方式建立点云体素金字塔，给定体 素栅格的大小，求得体素所包含点云的重心，以其重心近似代替该体素内所包含的点云，可用公式表 达为：式中：为第i 个体素栅格点云数据的重 心坐标；Pk 为第i 个体素栅格中第人个点的三维坐标；"为第i 个体素栅格中点的数量；组成的集合为原点云在尺度下。
下的采样点云。
(a)点基集合提取(b)二维剖分单元图2 Super 4PCS 算法点基提取引用格式:鲁铁定,袁志聪，郑坤.结合尺度不变特征的Super4PCS点云配准方法口］.遥感信息,2019,34(5)=15-20②建立点云高斯差分尺度空间。
在步骤①中构建了点云的体素金字塔，设金字塔共有m组，每组有S层，则第s层的尺度为：6=<Jo2s(2)式中：6为点云的初始尺度；6为点云金字塔第$层的尺度。
计算每个高斯空间尺度下采样点的高斯过滤响应值F,以及采样点相邻尺度的高斯差分值DOG。
对采样点及距离3。
邻域范围内的点进行曲率值高斯加权，高斯过滤响应值F和DOG高斯差分值的计算公式可表示为：k・仙F=f---------- (3)i=lw；=(4)dog=F-F P (5)式中：p为采样点第i个近邻点的曲率；w;的表达式如式(4)所示，d为采样点到邻域点的距离；<7为当前尺度空间的大小;式(5)中F pre为上一尺度的高斯过滤响应值。
③检测DOG尺度空间极值点。
若某点的DOG 值相比其邻域范围内的点的DOG值为极值，以及相邻上下2个尺度邻域范围内的DOG相比仍为极值,确保其在点云空间与尺度空间均为极值点，则记该点为特征点。
2.2结合SIFT特征点的Super4PCS算法Super4PCS算法具有很快的配准速度,但当点云具有对称性时(见算例2),Super4PCS算法点对识别易出错，针对以上问题,提出了一种结合点云SIFT 特征的Super4PCS算法，其主要步骤可描述为：①源点云与目标点云的SIFT特征提取，利用3D-SIFT算法能直接对点云进行特征点提取，将点云缩至特征点集,保留点云的主要成分，降低点云噪声对配准结果的影响，更加凸显点云的局部特征。