基于改进的ICP与主方向贴合的点云配准算法

朱锦杰

(山东省地质矿产勘查开发局八○一水文地质工程地质大队,山东 济南 250014)

0 引言

伴随着科学技术的发展,新的测绘技术也在慢慢崛起。其中,三维激光扫描仪的诞生为推动测绘朝着高新技术发展做出了贡献。三维激光扫描仪通过无接触式测量,获取大量具有三维坐标信息的点云数据,通过配准匹配构建三维点云模型,从而实现被测物体三维展示[1-5]。其中关键技术是点云如何实现高精度匹配配准,形成表面无噪点的点云模型,这是制约着点云模型大规模应用的一道障碍。关于配准算法的研究国内外专家学者做过深入分析探讨,常规模型如全局搜索思想的配准方法,随机抽样一致(random sample consensus,RANSAC)点云配准算法,主方向贴合算法,最近点迭代(iterative closest point,ICP)算法等。常规一种算法难以满足点云配准的要求,可将多种算法综合各自优点实现高精度配准,如文献[2]中提及利用向量夹角提取特征点后通过快速点特征直方图(fast point feature histograms,FPFH)描述特征点,并在ICP算法中加入KD-tree完成最终配准;文献[3]在ICP算法中利用二次搜索求出最近距离,提高传统ICP算法的效率;文献[4]中涉及在主成分分析法(principal component analysis,PCA)的基础上完成初始配准,但PCA算法要求待配准点云有较高的重叠度;综合已有研究资料表明配准过程一般包括两个步骤,粗配准与精配准。本文在研究了多种配准算法之后,尝试将主方向贴合算法与改进的ICP算法组合。将主方向贴合算法作为粗配准,得到粗配准之后的点云数据;利用改进的ICP算法作为精配准,最终实现点云三维模型的精确构建。以某三维激光扫描建模工程为例,通过外业获取的点云数据,经过粗配准与精配准两个过程,实现了三维模型的构建,同时验证该组合方法在点云配准方面的有效性。

1 配准算法原理

1.1 主方向贴合算法

该算法的基本思想是解算每个点的特征向量,特征向量中有两个成正交的分矩阵。这两个矩阵能够描述该点的主要位置信息,并能够保存主要信息以简化点云描述部分不对称存在[12-13]。为了提高主方向贴合算法的配准效果,在算法运行前先粗略地针对两站点云进行粗处理,剔除噪声点云并将重叠区域进行提取,其目的是为了提高点云的配准精度与效果。

1.2 最近点迭代算法

ICP算法经过这几十年的发展已日趋成熟,特别是国内外学者针对该算法提出了不同的改进算法。但是该算法使用起来还具有一定的局限性,如点云的重叠率较高,噪点点云数据不能太多。否则配准的点云效果较差,优势不明显[14]。这就需要在利用ICP算法之前,使用粗配准算法将点云数据粗略配准。上文中提及的主方向贴合算法的粗配准能够作为ICP算法的输入数据。从而充分发挥ICP算法的优势实现点云模型的精确配准。国外专家Besl等人提出了该算法无需控制点即可实现点云的配准,每一次迭代过程中都会重新计算迭代误差,直至迭代差值小于某一阈值。当这一数据值满足要求时,迭代结束,并且此时的特征向量及坐标转换配准参数是唯一解[15]。

针对数据点云X,这其中包括该数据集中计算的对应点云,利用ICP算法构成目标点云集合Yk。该过程就是ICP算法的核心思想,以下为描述该计算的主要过程

Yk=C(X,Y)

(1)

利用四元数算法Sysf估算点云集合X、Yk,计算出配准参数如式(2)所示。

(H,d)=Sysf(X,Yk)

(2)

通过变换矩阵H将点云集合X中每个数据点旋转平移变换,如式(3)所示:

H(X)=R(X)+T

(3)

式(1)～式(3)为经典ICP算法的主要流程,该算法搜寻最近点并不断逼近最佳值,通过四元数算法获取参考点云与目标点云之间的配准参数。

假设目标数据和参考数据分别为X、Y,其迭代的步骤如下:

1)寻找最近点。由公式Yk=C(X,Y)对点云数X中的每个数据点,计算其在点云数据Y中的最近点,构成点集Yk。

3)更新数据集。由公式H(X)=R(X)+T,利用变换矩阵H对数据集X进行更新[10]。

ICP算法还需要满足的要求是对于两个数据集,其中一个数据是另一个数据的严格子集,那么才能够使得两个待配准的点云数据总体上在某一种度量准则下达到最佳配准。在进行三维数据扫描时,无法一次性的获取物体表面的全部点云数据,往往要从不同的角度下采集物体的局部数据,这些数据仅仅是部分相互重叠的,所以,ICP算法得到的结果可能不会是全局最优化,这就需要对迭代初始相对位置的要求较高,不能够与真实的位置相差过大。

1.3 改进的ICP算法

经典ICP算法如上文介绍实现流程,以欧式距离为限制条件搜寻源点云P中的某个点pi在目标点云Q中的对应点qi,并将对应点计算的旋转矩阵R与平移矩阵T,使得按照式(4)计算的误差最小。

(4)

式中E(R,T)为误差函数。

按照式(4)的计算方式将目标点云与源点云所有数据参与计算,但存在噪点导致计算效率降低。为此在传统ICP算法基础之上,加入法向量夹角阈值删除未参加配准的噪点,来优化算法的执行效率。流程如下:

1)经过主方向贴合算法粗配准之后的源点云为P′,目标点云集合为Q′,分别计算出每个点的法向量。

2)针对P′中的每个点在Q′中查找对应的欧氏距离最近点,记为点对N,随后设置法向量阈值为fθ,假如N的法向量夹角小于阈值,保留该点对,否则视为匹配失败点对,将其剔除,剔除的点对记为N′。

3)根据点对集合N′利用奇异值分级法计算变换矩阵(R、T),并根据误差函数E(R,T)求出最优的变换旋转矩阵。

2 实验验证

文中评定最终配准结果精度采用均方根误差(RMSE),其计算公式为

(5)

其中,pj与qj分别表示目标源点与目标点中对应点;n表示对应点数量。

2.1 实验一

2.1.1粗配准

本文采用了主方向贴合法对点云数据进行粗配准,算法验证所采用的数据格式为asc,数据来自某数据库中的标准参考格式数据,目标点云数量为39 910个,参考点云数据量为39 930个。

由图1配准前的点云数据可知,目标点云与参考点云二者之间重叠率较高,无须进行预处理可对点云数据求解特征向量与特征值的计算。利用MATLAB软件编程实现主方向贴合算法,在编程实现过程中发现该算法思想简单易于实现。最终通过程序实现了主方向贴合算法,虽然数据量较大,但过程仅花费0.084 878 s,再次印证了该算法易于实现且较简单的优点。

(a)二维显示

(a)二维显示

主方向贴合法不同于RANSAC配准算法中要求点云数据中点的数量必须相同,它是对点云数据分别计算的,所以可以对不同大小的点云数据进行计算。

虽然主方向贴合法有上述种种优点,但是该算法的缺点也非常的明显。如该算法在配准之前,要求原始点云数据具有较大的重叠率,如重叠率较小则无法实现配准。且该算法受噪点影响也较大,时常配准效果不明显,精度较差。必须在配准之前去噪,本小节采用的标准库中的点云数据,是经过去噪之后处理,所以在算法运行中有一定优势。同时在外业中增加点云重叠率等一系列操作,这样才能打破该算法的局限性,提供应用场景。

采取了人机结合的方式,即对于重叠区域小的两个点云数据,粗略地选取其可以重叠的部分,然后再对这一部分进行配准,得出的旋转矩阵R、平移矩阵T再作用于原数据,可以达到预期的效果。这种方式需要判断出点云数据中重叠的区域,这就需要在采集数据同时收集相关的资料,方便在处理数据时判断点云数据重叠区域的大体位置。本文在实例部分所用的点云数据就是重叠率小的数据,需要在配准前粗略地选取点云可以重叠的部分。

2.1.2精配准

改进的ICP算法在主方向贴合算法运行之后的结果运行,设置阈值τ=0.000 000 1,经过9次迭代之后配准效果如3所示,精度统计如表1所示。改进的ICP迭代算法配准效率高且配准精度较传统ICP方法高。

表格1 配准耗时、误差对比

调试之后,将图像用Matlab显示,由图3可知,代码编写可行。整个运算过程中,每个数据的点的个数为40 000多个,迭代运行9次,一共耗时为0.190 162 s。不管是二维、三维配准效果均满足要求。同时由表1可知,改进的ICP迭代配准算法较传统ICP迭代算法在配准耗时与精度方面均有提高。其中在相同点云数量配准中,改进的ICP较传统ICP配准耗时缩减4倍有余,精度方面提高2倍有余,证明了本文的组合算法思想可信性。

(a)二维显示

改进的ICP迭代算法的精髓在于阈值设置的大小。该值设置的大小又决定了运算时间,二者之间看似矛盾。但可通过调整阈值并考虑计算时间来权衡。特别是过小的阈值,直接造成增加几何量级的迭代计算,带来的后果就是计算时间的增加。所以如何选取合适的阈值,成为改进的ICP迭代算法成功实现的关键因素,而确定阈值可通过实验经验确定,也可通过误差反向传播定律等方法实现。改进的ICP算法思想明确,简单且易编程实现,但是其特性也决定了该算法运行所需的条件较高,为了实现它就必须达到所规定的条件。因此,必须在运用改进的ICP算法之前,先对点云数据进行粗配准,给出一个比较理想的初始对应位置。

2.2 实验二

根据上文提及的外业采集数据流程,采集对象为某一大学正门。该校门高度12.3 m,宽度8.45 m,厚度2.70 m,为钢筋与混凝土结构。通过实地调查,采用四站全包围方式进行点云采集。可提前通过(real-time kinematic,RTK)测量方式施测图根点作为标靶,作为将点云模型转换至当地空间坐标系的参考点。将该校门点云数据去噪之后的背面效果展示,如图4(a)所示,正面效果如图4(b)所示。为运行IICP算法,利用专业的点云数据处理软件拼接,效果如图5(a)所示。为配准点云数据首先确定重叠区域为门内测;其次运用主方向贴合算法进行粗配准;最后利用IICP算法将粗配准之后的点云数据精确配准得到如图5(b)所示的效果。最终对配准的结果精度验证与评定工作,经过统计该次配准的误差为0.059 3。即在本文要求精度需要达到对应点之间的距离不大于30 mm的条件下,点云数据中未达到配准要求的点所占的比率为0.059 3。表2统计了改进ICP与传统ICP在配准耗时与精度两方面统计,与实验一结论相似。改进的ICP迭代配准算法在精度与耗时中均由于传统ICP算法,再次证明了改进的ICP算在配准中的优势性。

表格2 配准耗时、误差对比

(a)背面效果

(a)未配准前

3 结束语

本文在经典ICP算法的基础之上,研究了改进的ICP算法与主方向贴合算法的结合实现点云配准,并深入分析二者的适用条件,利用MATLAB编程软件实现了这两种算法。通过外业实测点云数据,并利用实验一与实验二过程。陈述了粗配准中利用主方向贴合算法,精配准中利用改进的ICP迭代算法。这两种实验的成功都是基于点云重叠率较大的情况下实现。两次实验的点云数据重叠率较大,这为粗配准与精配准提供了有利条件,下一步将尝试利用低重叠率实现点云的有效建模实验。