针对低质量点云的点云配准算法

吴 振 慧

(扬州职业大学, 江苏 扬州 225009)

三维点云作为一种通过非接触方式采集得到的数据,信息量丰富,可反映物体三维信息,目前常用于工程、医学、建筑、环境等诸多领域[1]。然而,在三维点云数据的采集过程中,由于采集设备、采集视角、采集过程等原因,采集得到的点云通常无法达到设备理论的最高精度,会存在如点云稀疏、噪声、不完整等缺陷。因此,与完整点云相比,低质量点云会带来特征点稀疏、特征数目差距较大等问题,给配准带来较大挑战[2]。近年来,点云配准算法的研究不断发展,第一类方法是对传统ICP算法进行改进和优化,这些方法旨在解决ICP算法易于陷入局部最优的缺点,但速度比传统ICP算法慢,且通用性受限[3]。第二类方法是基于深度学习方法,注入基于三维卷积神经网络的点云分割和配准方法PointNet[4],以及在此基础上衍生出的诸多方法,这类方法在处理低质量点云时需要提供诸多训练集,网络训练耗费时间很长,且配准精度难保证[5]。针对低质量点云的配准问题,笔者提出一种粗匹配和精匹配相结合的点云配准算法,即基于PPF特征进行点云的粗匹配,得到配准结果后,将其作为ICP精匹配方法的迭代初值,从而解决ICP方法容易因初值设定不佳而落入局部最优解的问题。最终将整套配准算法在低质量的点云上进行实验验证,证明了方法的有效性和鲁棒性。

1 粗-精匹配结合的点云配准算法

传统ICP方法在迭代初值设定合适时,可以完成点云的精确配准,但因为迭代过程较慢,通常作为精匹配算法。为解决其初值选择的问题,本文采用基于PPF特征的粗匹配方法,形成了粗精匹配结合的点云配准算法。

1.1 基于PPF特征的粗匹配算法

PPF特征是一种三维点云的特征描述子,基于Hough Voting的思想,摆脱了传统特征描述子依赖于局部特征的缺点,对于轻微变形或部分遮挡的情况,具有鲁棒性好的优点,抗噪声能力较强,且一次可以计算出多个结果[6]。

PPF特征描述的是两个有向点的相对位姿,假设两个点为p1和p2,其法向量分别是n1和n2,定义矢量d=p1-p2,则将PPF定义为一个四元数:F(p1,p2)=(‖d‖d2,∠(n1,d),∠(n2,d),∠(n1,n2)),这是一个非对称的特征描述子,其中∠(a,b)∈[0,π]表示两个矢量的夹角,其定义示意如图1所示。

图1 Point Pair Feature定义

在完成三维点云的PPF特征构建后,构建全局模型描述,具体方式为:计算三维点云表面所有点对的特征描述子,并构建哈希表,将具有相同描述子的点对作为哈希表的值(Value),将其描述子F作为哈希表的键(Key)[7]。哈希表构建见图2。

图2 PPF哈希表构造

完成哈希表的构造后,即可进行点云的粗匹配,其基本流程为:

流程一:定义模型点云为M={mi},i=1,2,…,M,真实点云为N={ni},i=1,2,…,N,其中mi,ni∈R3表示各个点的三维坐标。首先给定N中的参考点对(ni,nj),并在M中选取与参考点对具有相似特征的点对(mi,mj)。需要将匹配的两点进行配准,则需要将点的位置和其法向量对齐。

流程二:通过变换矩阵Tn→g将ni移动到局部坐标系原点,并转动其法向量与局部坐标系X轴重合,对真实点云也进行移动和转动。同理,通过Tm→g对mi和模型点云也进行相同操作。

流程三:将模型点云中的mj绕着X轴转动Rx(α)使其与nj配准。

采用PPF进行粗匹配的一大特点在于,每个参考点可能返回多个位姿,对于多个可能位姿,需要进行聚类,最终提取出得分最高的类包含的位姿均值,即为PPF粗匹配最终结果。这一结果根据机器人学原理,也可以表示为位姿矩阵的形式:

(1)

其中R∈R3×3表示旋转矩阵,t∈R3×1表示平移向量。

1.2 基于ICP的精匹配算法

ICP(迭代最近点)方法通常分为点到点和点到面两种[8]。本文采用点到点的ICP方法,此时匹配问题可以理解为一个优化函数的求解问题,该目标函数为:

(2)

其中mj*表示在模型点云M中和真实点云中的(Rni+t)欧氏距离最近的点。

采用迭代最近点算法进行点云精匹配的流程概括如下:第一,在模型点云M中查找真实点云N各点的最近点,根据最近点的配对结果,采用奇异值分解计算旋转矩阵R和平移向量t。第二,根据计算的旋转矩阵和平移向量通过(Rni+t)移动真实点云N。第三,反复重复步骤1—步骤2,直到真实点云N中各点与其最近点的距离误差小于阈值,完成迭代。

采用ICP进行精匹配之前,需要对点云进行预处理。首先,对大型点云进行降采样,保留有效信息即可完成点云匹配,因为过多的点会导致算法时间大大延长,但效率提高甚微。接着,构建如八叉树或K-D树的数据结构存储点云数据,因为在ICP算法计算过程中,运算量最大的一步在于查找模型点云中每个点的最近点,若数据量较大且采用暴力搜索的方式,将会导致算法时间过长,因此需构建加快最近点查找的数据结构[9]。最后,对模型点云和真实点云均进行去中心化,即将用于配准的模型和真实点云坐标均分别减去其质心坐标,直观地可以理解为将点云质心均移至坐标系原点,这一步可大大加快最近点查找的速度。

1.3 整体算法流程

由上文可知,采用PPF进行粗匹配可以得到一个评分最高的位姿矩阵,而采用ICP进行精匹配需要一个较好的迭代初值避免其陷入局部最优解,因此本文设计将粗匹配计算出的结果作为精匹配的迭代初值,粗精匹配结合的点云配准算法流程如图3所示:

图3 整体算法流程图

本文粗精匹配结合的点云配准算法核心步骤在于通过粗匹配的结果对模型点云M中各点的坐标进行更新:

mi′=R0mi+t0

(3)

其中R0和t0分别是从PPF计算的位姿矩阵T中提取出的旋转矩阵和平移向量。通过该步骤对模型点云进行更新后,模型点云已经大致移动到和真实点云一致的位置,即R0和t0已经接近最终的配准结果,但精度不一定满足需求。此时,将移动后的模型点云和真实点云进行ICP精匹配,实际上就是将R0和t0作为ICP精匹配的迭代初值,相较于直接用真实点云N进行匹配,这种方法可以有效避免匹配结果出现局部最优解,并可以减少精匹配过程中的迭代次数,从而提高算法的整体速度。

此外,本文为提高匹配算法的计算速度,在采用PPF进行粗匹配后,首先对已完成粗匹配的模型点云和真实点云计算其最近点之间的欧氏距离,当距离小于某一阈值,则判断已完成匹配,即粗匹配精度达到要求,无需进行精匹配。根据公式(2)可知,本文设定模型点云不动,通过移动真实点云完成最终匹配,在实际计算过程中,将真实点云固定不动,移动模型点云也是可行的。由于本文考虑到点云有残缺,若固定真实点云N不动,则需要查找模型点云M各点的最近点,会导致模型点云中对应残缺部分的点始终无法找到最近点,由此ICP算法迭代误差保持很大,难以完成公式(2)的计算收敛。

2 算法实验验证和分析

为验证本文提出的针对低质量点云的点云配准算法,本文采用斯坦福大学的点云配准数据集,该数据集为点云匹配算法验证的经典公开数据集。本文对其中一组点云进行人为处理,分别构造稀疏点云、含噪声点云以及残缺点云这三类低质量点云,对其进行算法的实验验证。本文采用Matlab编写算法程序,计算平台硬件为i7-10750H处理器、16G内存的电脑。

首先,人为设定真实点云和模型点云在X、Y、Z轴均存在10°的转角偏差,即位姿变换矩阵为:

R=Rz(10°)Rx(10°)Ry(10°)

(4)

(5)

其中Rx(α)、Ry(α)、Rz(α)分别表示绕X轴、Y轴、Z轴旋转α角度的三维旋转矩阵。初始情况下,真实点云和模型点云的位姿偏差如图4所示,其中浅色为真实点云,深色为模型点云。在实验过程中,考虑到点云总尺度以及匹配精度的要求,本文设定ICP算法迭代收敛条件为:模型点云和真实点云中对应最近点的距离小于2 mm(该精度满足绝大部分的工业应用场景),若迭代3步仍无法达到收敛条件,则退出迭代过程。配准结果中浅色和深色表示配准后的真实点云及模型点云。

图4 初始位姿偏差

2.1 稀疏点云配准

针对点云稀疏的情况,对真实点云中的点进行降采样,模拟在点云数据采集过程中采集点数目较少的情况。在实验过程中,本文随机删去真实点云中的部分数据点,选用原始点云50%、20%、10%数目的点作为稀疏点云进行配准,在ICP算法、PPF算法以及本文提出的粗精匹配结合的算法上进行匹配,结果如图5、图6、图7所示。

图5 50%稀疏点云配准结果

图6 20%稀疏点云配准结果

图7 10%稀疏点云配准结果

由上图可见,在进行稀疏点云配准时,采用传统ICP方法难以完成准确的点云配准,存在较大误差,采用PPF方法配准结果较好,采用粗精匹配结合的方法验证了PPF配准结果的准确性,最终输出结果匹配精度高。

2.2 含噪声点云配准

针对真实点云无法避免的采集噪声,本文给真实点云人为添加均值为0,方差不同的高斯噪声,模拟点云数据存在噪声波动的情况,分别设定标准差为0.5 mm、0.7 mm、1 mm,其数值越大表示点云的噪声越强烈。点云配准结果如图8、图9、图10所示。

图8 方差0.5 mm噪声点云配准结果

图9 方差0.7 mm噪声点云配准结果

图10 方差1 mm噪声点云配准结果

由上图可见,在对含噪声的点云进行配准时,传统ICP算法在三种噪声情况不同的点云上均无法完成准确配准。在方差0.5 mm噪声点云上,采用PPF粗匹配即可完成准确配准;在方差0.7 mm噪声点云上,采用PPF粗匹配仅可完成大致定位,在此基础上采用ICP精匹配可实现对点云的准确配准;在方差1 mm噪声点云上,采用粗精匹配结合的方法虽然无法完成非常准确的配准,但配准精度高于仅采用PPF或ICP匹配方法。

2.3 残缺点云配准

考虑到点云在采集过程中会因存在遮挡而导致点云残缺的情况,笔者在X、Y、Z三个方向上分别模拟点云残缺的情况,需要注意的是,残缺点云虽然表现的也是点云数据的缺少,但和稀疏点云存在区别:残缺点云缺少集中的部分区域,造成点云整体形状变化;稀疏点云数据量虽少,但点云整体形状与原始点云接近,缺乏的是点云表面的细节特征。本文实验采用的残缺点云如图11所示,其中深色部分为原始点云,浅色部分为删去部分区域后的残缺点云。

图11 残缺点云示意图

分别针对三种残缺点云的配准结果如图12、图13、图14所示。

图12 X方向残缺点云配准结果

图13 Y方向残缺点云配准结果

图14 Z方向残缺点云配准结果

由上图可见,针对Y方向和Z方向残缺的点云,采用ICP算法配准效果一般,这是因为剩余部分的点云保留了大部分显著特征,可支持ICP算法完成迭代计算。针对X方向残缺的点云,采用ICP算法难以完成配准,采用PPF算法配准效果一般,采用本文提出的粗精匹配结合的方法配准准确。

2.4 配准速度分析

由上述三类实验已知,本文提出粗精匹配结合的配准算法可完成对低质量点云的准确配准。此外,为验证本文提出的方法快速性,本文对上述三类共九组实验的计算时间进行了统计,见表1。

表1 计算时间 单位:s

分析上表可知,采用本文提出的粗精匹配点云配准算法,其计算时间通常小于传统ICP算法。此外,因为PPF算法的计算时间包含在本文算法中,所以单独采用PPF进行配准的时间较短。综上所述,采用本文的点云配准算法,不仅可以对低质量点云完成精确配准,其配准时间也小于传统ICP点云配准方法,做到了速度和精度两方面的提高。

3 结语

针对低质量点云配准存在的困难,本文提出了一种粗精匹配结合的点云配准算法,基于PPF的粗匹配方法和ICP的精匹配方法设计了整套算法流程。实验验证了对稀疏点云、含噪声点云以及残缺点云的配准结果,配准精度高、速度快,可用于对工业现场采集的真实点云的配准。