收稿日期:20180614;修回日期:20180802
作者简介:李强(1991),男,山西稷山人,硕士,主要研究方向为虚拟现实(hanwuxin@163.com);高保禄(1971),男,讲师,博士,主要研究方
向为智能信息处理;窦明亮(1992),男,硕士,主要研究方向为虚拟现实.
基于多重特征匹配的点云配准算法
李 强,高保禄,窦明亮
(太原理工大学 信息与计算机学院,太原 030024)
摘 要:针对最近点迭代(iterativeclosestpoint,ICP)算法搜索匹配点对规则单一、准确度低的问题,提出一种基
于多重特征匹配的点云配准算法。首先采用改进自适应八叉树算法分割点云,通过移动最小二乘法(movingleast
squares,MLS)对其叶节点进行局部拟合后,计算点的多重特征;然后提出了基于多重特征的点对相似度,选取满足
相似度约束的点对作为匹配点对,进而求取旋转矩阵和平移矩阵实现点云配准。实验表明,该算法能在保持点云
配准速度较高的基础上,有效提升配准的准确度,且准确度的提升幅度随着点集数量的增大呈升高趋势。
关键词:八叉树;移动最小二乘拟合;曲率;点云配准;四元数
中图分类号:TP3919 文献标志码:A 文章编号:10013695(2020)02060058805
doi:10.19734/j.issn.10013695.2018.06.0575
Pointcloudregistrationalgorithmbasedonmultiplefeaturematching
LiQiang,GaoBaolu,DouMingliang
(CollegeofInformation&Computer,TaiyuanUniversityofTechnology,Taiyuan030024,China)
Abstract:Tosolvetheproblemthat,ICPalgorithmhasasinglefeatureforsearchingandlowaccuracyforregistration,this
paperproposedapointcloudregistrationalgorithmbasedonmultiplefeaturematching.Itchosetheimprovedadaptiveoctree
algorithmtosegmentthepointcloud.Thenitcalculatedthemultiplefeaturesofthepointsafterthelocalfittingoftheleaf
nodesbyMLSalgorithm.Next
,thisalgorithmintroducedthepointpairssimilaritybasedonmultiplefeaturetoestablishthe
matchingpoints.Lastly
,itcomputedtherotationmatrixandtranslationmatrixtoachieveregistration.Experimentsshowthat
thisalgorithmcaneffectivelyimprovetheaccuracyofregistrationonthebasisofkeepingthepointcloudregistrationspeed
high.Andwiththenumberofpointsetsincreasing,thetrendofaccuracyforthismethodisincreasing.
Keywords:octree;MLS;curvature;pointcloudregistration;quaternion
三维点云重建技术已经广泛应用在文物数字化、工业制造
建模等模型构建领域
[1]
。点云获取通常采用激光扫描仪,但
由于物体的不可穿透性以及提高准确性的要求,目标表面完整
信息往往需要经过多角度、多次扫描获得,导致获取的点云数
据不在同一坐标系下,因此需要对不同角度、不同批次获取的
点云进行配准。点云配准的实质是求解待配准点云到目标点
云的刚性转换关系。
迄今为止,针对点云配准问题已提出了很多方法,
Besl等
人
[2]
提出的最近点迭代算法,即 ICP(iterativeclosestpoint),是
应用最广的一种。该算法取目标点云与待配准点云间欧氏距
离最小的点来构建匹配点对,求得匹配点对的旋转和平移变换
矩阵,变换后重新建立匹配点对进行迭代计算,达到收敛约束
条件后完成配准。该算法构建匹配点对的过程计算量非常大,
且特征不明显区域冗余的点大幅降低了其收敛效率。针对其
缺陷,国内外学者提出了众多改进
ICP算法。Sharp等人
[3]
以
点到邻域重心的距离作为特征进行点云配准,以重心描述单个
点在点云中的相对位置,但由于特征单一,准确度提升较小;韦
盛斌等人
[4]
以点面距离构建匹配点对,为点云特征的选择提
出了新思路,但由于曲面的拟合较差影响了准确度;杨小青等
人
[5]
采用主曲率约束和点云法向量夹角初步选取点集,然后
采用点间距离和高斯曲率进一步获取精确匹配点,但该方法在
匹配点选取过程中限定的阈值较多;Elbaz等人
[6]
引入深度神
经网络的方法进行配准,但离线训练阶段需要大量数据,更适
合大地形场景;王勇等人
[7]
通过多分辨率加快匹配速度,引入
匹配度概念改进
ICP匹配点的搜索,但是该方法匹配点的特征
单一,在点集较大时会产生错误匹配点对,准确度一般。
本文提出了一种基于多重特征匹配的点云配准算法。首
先,通过改进自适应八叉树算法将点云数据组织在空间单元
中,对每个单元采用移动最小二乘法拟合局部曲面后计算出点
的多重特征,然后利用多重特征代替文献[7]中单一的曲率特
征,并采用基于多重特征的点对相似度代替其中的匹配度建立
匹配点对,最后用四元数法完成点云配准。
1 改进自适应八叉树算法
11 自适应八叉树算法
点云分割中八叉树的划分策略直接影响着划分结果所占
的存储空间和构建时间。自适应八叉树通过设置阈值,可以将
每个节点中点的数量控制在合理范围内,同时减少分割次数,
是点云最常用的分割算法之一。但是其阈值的设定不够灵活,
如果阈值太大,无法体现分割的效果;如果阈值太小,每个节点
内的点太少。根据最小二乘法的原理———通过最小化误差的平
方和寻找数据的最佳函数匹配,由于选取的点少,放大了边缘
点、离群点以及噪声的误差对于曲面生成的影响,降低了拟合曲
面准确度。为了便于理解,图
1(a)(b)以二维曲线拟合说明了
离群点对不同数据集的影响,在采用移动最小二乘法拟合时,若
都增加离群点 A,其对图(a)中拟合曲线的影响将会明显大于图
(b)。同理,对于复杂的点云模型中,被分割物体表面常常会有
连续的平顺区域(如图 1(c)中矩形框区域),若阈值太小,分割
第 37卷第 2期
2020年 2月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.2
Feb.2020