基于k近邻算法优化的最小二乘3D表面匹配算法

王 鹏，李少达，赵 雪

（1.成都理工大学 地球科学学院，四川 成都 610059；2.西南交通大学 地球科学与环境工程学院，四川 成都 611756）

点云匹配是激光点云重建三维模型的关键步骤。目前的匹配算法包括迭代最近邻点（ICP）[1]，最小二乘3D表面匹配算法（LS3D）[2]和三维正态分布变换算法（3D-NDT）[3]等。国内外学者对ICP、3D-NDT提出了很多改进优化方法[4-13]，但对LS3D的研究较少。

LS3D是一种高精度、高效率的点云匹配算法，可应用于任意三维表面数据，是二维图像最小二乘匹配的一种延伸。Gruen最早利用该技术解决了摄影测量中面片匹配的问题。Gruen和Acka将广义高斯 - 马尔科夫模型运用到LS3D算法中，以估算变换参数。其中，k近邻搜索花费的时间是影响LS3D算法计算效率的主要因素[14-15]。

LS3D使用盒子划分结构（BS）进行k近邻搜索，得到同名点进行三维坐标转换的参数（3个旋转角、3 个平移参数和1个尺度因子）。谭俊祥[16]将无序三维散乱点云的空间划分方法归为树结构划分法和空间分块策略法两类；同时提出一种正交轴格网划分（OGP）的搜索算法，在对比已有的k近邻算法中达到最优；在空间分块策略法中，主轴搜索树（PAT）在精度和效率上最优；但未对LS3D使用的BS算法进行实验分析。基于此，本文根据不同k近邻搜索算法（kNN）对LS3D进行实验，对比分析了不同搜索算法下的LS3D性能。

1 LS3D的算法原理

1.1 算法原理

f (x, y, z)和g (x, y, z)分别为待匹配数据与目标点云之间的重叠区域。三维表面配准其实就是估算变换参数，利用待匹配数据表面的点云f (x, y, z)调整目标表面g (x, y, z)上的点云。若两个表面点云的匹配建立，则应满足：

由式（1）可知，待匹配数据中包含与目标数据对应的点云。若假设e (x, y, z)为待匹配数据与目标数据间的一个真矢量误差，则可推导出：

式（2）为LS3D的观测方程。通过最小二乘算法最小化目标函数实现匹配过程，表示模板表面和搜索表面同名点之间的欧氏距离平方和：

式中，d为欧氏距离，根据g (x, y, z)的初始位置类估计最终位置。

1.2 LS3D的实现过程

1）搜索目标点云和待匹配点云间的同名点对。

2）利用同名点对，建立高斯—马尔科夫模型：

式中，A为设计矩阵；I为单位矩阵；l=f (x, y, z)-g0(x, y, z)为常数向量；lb为系统参数向量；x=[dtx dty dtz dm dω dφ dκ]T为参数向量；P为先验相关权重系数矩阵；Pb为系统参数相关权重系数矩阵。

3）求解参数向量x̂=(ATPA+Pb)-1(ATPl+Pblb)。

4）迭代求解参数向量，当参数向量小于设定阈值时，停止迭代。

2 实验与分析

本文以Matlab 2014a作为算法程序开发和实验平台，使用 Windows 7操作系统，Inter® Core(TM) i5-2450M CPU @ 2.5GHz处理器，采用在树结构划分法和空间分块策略法中最优的搜索算法PAT、OGP进行实验。实验数据采用模拟点云数据，如图1所示。

图1 实验采用点云数据

由表1可知，3种搜索算法对LS3D的迭代次数和精度几乎没有影响，但在迭代所花费的时间上却有很大差距。BS算法的迭代时间最短，优于OGP和PAT算法，但PAT算法与BS、OGP算法的迭代时间差距太大，因此在实验过程中，同时统计了3种算法每次迭代所需的时间。PAT算法第一次迭代消耗了400 s，而在剩下的迭代过程中，每次迭代所花时间与BS、OGP算法差距不是很大。综上所述，BS算法优于OGP算法，PAT算法迭代时间长的原因在于第一次迭代消耗大量时间，导致整体的匹配效率下降。

表1 不同搜索算法下的LS3D算法收敛效率与精度

3 结 语

本文通过树结构划分法和空间分块策略法中的典型算法与BS算法进行测试，对比分析了不同k近邻搜索算法下LS3D算法的性能。实验结果表明，不同搜索算法对LS3D算法的匹配精度几乎没有影响，BS算法优化的LS3D算法在相同迭代次数下效率最优，是PAT算法的4.5倍，而造成PAT算法效率较低的原因在于第一次迭代中消耗的时间过多，几乎达到了整个迭代过程的一半，在匹配过程中需要较好的初始值才能提高效率。匹配效率和精度是三维重建过程中的关键因素，期待能对点云匹配精度进行进一步研究。

[1] Besl P J, Mckay N D. A Method for Registration of 3D Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256

[2] Gruen A, Akca D. Least Squares 3D Surface and Curve Matching[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2005,59(3):151-174

[3] Magnusson M. The Three-dimensional Normal-distributions Transform :an Efficient Representation for Registration,Surface Analysis, and Loop Detection[J]. Renewable Energy,2012,28(4):655-663

[4] CHEN Y, Medioni G. Object Modeling by Registration of Multiple Range Images[J]. Image and Vision Computing,1991,10(3):145-155

[5] ZHANG Z.Iterative Point Matching for Registration of Freeform Curves and Surfaces[J]. International Journal of Computer Vision,1994,13(2):119-152

[6] 严剑锋,邓喀中.基于特征点提取和匹配的点云配准算法[J].测绘通报,2013(9):62-65

[7] 侯东兴,王耀华,李宗春.剔除误同名点的约束改进ICP算法[J].测绘科学,2015,40(8):103-107

[8] 钟莹,张蒙.基于改进ICP算法的点云自动配准技术[J].控制工程,2014,21(1):37-40

[9] 秦绪佳,徐菲,王建奇,等.基于法向量直方图特征描述的点云ICP拼接[J].小型微型计算机系统,2016,37(3):593-597

[10] 王瑞岩,姜光,高全学.结合图像信息的快速点云拼接算法[J].测绘学报,2016,45(1):96-102

[11] 周文振,陈国良,杜珊珊,等.一种聚类改进的迭代最近点配准算法[J].激光与光电子学进展,2016(5):202-208

[12] 张晓,张爱武,王致华.基于改进正态分布变换算法的点云配准[J].激光与光电子学进展,2014(4):100-109

[13] 胡修祥,张良,HUXiu-xiang,等.结合NARF特征的改进型3D-NDT多视点云配准[J].信号处理,2015,31(12):1 674-1 679

[14] LIU Y H. Constraints for Closest Point Finding[J].Pattern Recognition Letters,2008,29(7):841-851

[15] LI B, Holstein H. Using k-d Trees for Robust 3D Point Pattern Matching[C]. International Conference on 3D Digital Imaging and Modeling,2003:95-102

[16]谭骏祥.地面LiDAR散乱点云配准关键技术研究[D].成都:成都理工大学,2014:22-26