SC2-PCR：高效鲁棒的点云配准方法基于二阶空间兼容性

132210SC2-PCR：一种用于高效和鲁棒的点云配准的二阶空间兼容性0Zhi Chen 1 Kun Sun 2 Fan Yang 1 Wenbing Tao 1 �01 多光谱信息处理科学与技术国家重点实验室，华中科技大学人工智能与自动化学院，中国2智能地理信息处理湖北省重点实验室，中国地质大学计算机学院，中国0{ z chen, fanyang, wenbingtao } @hust.edu.cn; sunkun@cug.edu.cn0摘要0在本文中，我们提出了一种基于二阶空间兼容性（SC2）度量的方法，用于高效和鲁棒的点云配准（PCR），称为SC2-PCR1。首先，我们提出了一种二阶空间兼容性（SC2）度量来计算对应关系之间的相似性。它考虑了全局兼容性而不是局部一致性，允许在早期阶段更具有区分性的聚类。基于这个度量，我们的配准流程采用全局光谱技术从初始对应关系中找到一些可靠的种子。然后，我们设计了一个两阶段策略，根据SC2度量矩阵将每个种子扩展到一个共识集。最后，我们将每个共识集输入加权SVD算法生成候选刚性变换，并选择最佳模型作为最终结果。我们的方法可以保证使用更少的采样找到一定数量的无异常值的共识集，使模型估计更加高效和鲁棒。此外，所提出的SC2度量是通用的，可以轻松插入基于深度学习的框架中。我们进行了大量实验来研究我们方法的性能。01. 引言0将同一场景的两个3D扫描对齐，称为点云配准（PCR），在同时定位和建图（SLAM）[7, 24, 40]、增强现实[4,11]和机器人应用[34]等领域起着重要作用。一个经典的解决方案首先建立特征对应关系，然后估计3D旋转0� 对应作者。1代码将在https://github.com/ZhiChen902/SC2-PCR上提供。0图1.（a）：一个玩具示例，红色和绿色线段分别表示异常值和内点。（b）：（a）的一阶兼容性矩阵。如黄色所示，异常值与一些内点具有非常高的兼容性得分。（c）：经过阈值处理后的（b）的二值化兼容性矩阵。（d）：（a）的提出的二阶兼容性矩阵。相比之下，异常值的行和列中的值较小。0并且翻译可以最好地对齐共享部分。然而，由于部分重叠或特征模糊等挑战，模型估计容易产生对应关系中的异常值，导致不准确或错误的对齐。RANSAC[25]是模型估计的迭代采样策略的先驱。然而，它需要更多的时间来收敛，有时由于大量的异常值无法保证准确的解决方案。空间兼容性（SC）[5, 35, 45,57]是一种广泛使用的刚性变换估计的相似性度量。它假设如果两个对应关系之间的空间距离差异，例如在图1（a）中的| d 12  −  d ′ 12 |或| d 16 −  d ′ 16|，较小，则它们的得分将更高。132220因此，从兼容的对应关系中进行采样增加了获取内点的概率。然而，这种一阶度量仍然受到局部性和模糊性的异常值的影响。图1（b）是图1（a）中对应关系的空间兼容性矩阵。从黄色单元格中可以看出，c6和c7是异常值，但它们与一些内点具有高的兼容性得分。因此，异常值将不可避免地参与模型估计过程，导致性能下降。0在本文中，我们提出了一种新的全局相似度度量方法，用于衡量两个对应关系之间的相似度。具体而言，我们首先将空间兼容性矩阵二值化为硬形式，如图1(c)所示。然后，对于两个兼容的对应关系，我们计算它们在全局集合中共同兼容的对应关系的数量。也就是说，我们计算同时与它们两者兼容的对应关系的数量作为它们之间的新相似度。对于任意两个不兼容的对应关系，全局共同兼容性设置为0。因此，两个内点的相似度至少是所有对应关系中除去它们自身的内点数量。然而，异常值没有这样好的性质。图1展示了一个玩具示例。图1(a)中有五个内点{c1,c2,c3,c4,c5}和两个异常值{c6,c7}。从图1(b)和图1(c)可以看出，异常值c6和c7与一些内点兼容，而内点彼此之间也兼容。但是从图1(d)可以看出，任意两个内点之间的相似度较大，而异常值与其他对应关系之间的相似度较小。具体而言，在图1(d)中，内点{c1,c2,c3,c4,c5}之间的相似度不少于3，而与异常值{c6,c7}相关的相似度不超过1。因此，图1(d)中的全局兼容性矩阵可以更好地区分内点和异常值。由于新的度量可以表示为传统一阶度量的矩阵乘积（参见公式8），我们将其命名为第二阶空间兼容性（SC 2）。0提出的第二阶空间兼容性度量SC 2具有几个优点。1）内点更容易与异常值区分开。假设我们有n个对应关系中的m个内点。任意两个内点之间的分数将不少于m-2。然而，异常值很难与多个对应关系同时兼容，其分数将小得多。2）传统算法如RANSAC及其变种[21,25,42,53]需要大量的随机采样来找到一个无异常值的集合以进行稳健的模型估计。然而，基于提出的SC 2矩阵，对于与内点对应的每个行向量，我们可以通过选择具有最高分数的前k个对应关系来轻松找到一个无异常值的集合。通过这种方式，可以通过遍历SC 2矩阵的所有n行来获得m个有效的采样。因此，我们可以通过0仅进行n次采样，使模型估计更高效和稳健。3）我们在理论上证明了SC 20矩阵从概率角度显著降低了错误采样的概率。我们定义了一个错误事件，其中两个内点之间的分数小于内点和异常值之间的分数。通过计算传统一阶度量和我们的二阶度量SC 2的此事件的概率分布，SC 2矩阵更能够稳定地获得可靠的采样（见图3）。基于SC 2度量，我们设计了一种完整的点云配准流程，称为SC 2-PCR。在[5,14,50]的基础上，首先选择几个可能是内点的种子点。然后，通过找到与每个种子点具有最高SC 2分数的那些点，为每个种子点选择一个一致集。为了进一步排除异常值，采用了一种从粗到细的两阶段采样策略。最后，使用加权SVD为每个种子点估计一个初步模型，并选择最佳模型作为最终输出。总之，本文在以下几个方面与现有方法有所不同。0• 第二阶空间兼容性度量SC 20提出了一种新的度量方法SC 2。我们在理论上证明了SC 2显著降低了异常值参与一致集的概率。由于所提出的方法在第一阶度量之外编码了更丰富的信息，因此增强了对异常值的鲁棒性。0• 与[5, 19, 35,43]等最先进的深度学习方法相比，我们的方法是一种轻量级的解决方案，不需要训练。它在不同数据集之间没有偏差，并且在各种场景中具有很好的泛化性能，这也在实验中得到了验证。0•所提出的方法是通用的。虽然我们以手工方式实现了它，但它可以很容易地插入其他深度学习框架，如PointDSC[5]。实验证明，将我们的方法与PointDSC结合使用可以获得更好的结果。02. 相关工作03D特征匹配。广泛使用的迭代最近点[10]及其变体[12, 46,49]通过在坐标空间中搜索最近邻来建立对应关系。而不是使用坐标空间中的距离，局部特征描述符旨在在特征空间中建立3D匹配。手工设计的描述符通过编码空间分布直方图[26, 28, 31, 52]、几何直方图[15, 47,48]或其他属性[61]来表示局部特征。最近，深度学习技术也被引入到学习3D局部描述符中。开创性的3DMatch[62]构建了一个Siamese网络来提取局部描述符。最近的一些网络尝试通过设计旋转不变模块[1, 22, 23, 58]、完全=� dthr0� l=� dthr0� l0.(6)132230卷积模块[20]，特征检测模块[6, 59]，粗到细模块[44,60]和重叠学习模块[29,55]。尽管这些方法取得了显著的性能改进，但很难建立一个完全无异常值的对应集。传统的模型拟合方法。模型拟合方法从噪声对应集中估计几何模型。经典的RANSAC[25]提供了最常用的用于鲁棒去除异常值的生成和验证流程。其许多变体[21, 42,53]引入了新的采样策略和局部优化[21]以加速估计或提高鲁棒性。最近，图割RANSAC[8]引入了图割技术以更好地执行局部优化。Magsac[9]提出了一种σ-一致性方法，用于构建一个无阈值的RANSAC方法。对于特定的3D模型拟合，FGR[66]使用Geman-McClure代价函数，并通过渐进非凸优化来估计模型。TEASER[56]使用截断最小二乘（TLS）代价重新定义了配准问题，并通过一般的图论框架来解决它。基于学习的模型拟合。最近的研究也采用了深度学习技术，这些技术首先在2D匹配领域进行了研究，用于模型拟合任务。2D对应选择网络CN-Net[41]及其变体[13, 16, 17, 37, 51,63-65]将模型拟合形式化为对应分类模块和模型估计模块的组合。最近的尝试[5, 18, 19, 35,43]还引入了用于3D对应修剪的深度学习网络。3DRegNet[43]将CN-Net[41]改为3D形式，并设计了一个回归模块来解决刚性变换。DGR[19]引入了完全卷积来更好地捕捉全局上下文。PointDSC[5]开发了一个基于空间一致性的非局部模块和神经谱匹配，以加速模型生成和选择。DetarNet[18]提出了解耦的平移和旋转解决方案。DHVR[35]利用深度Hough投票来识别Hough空间中的共识，从而预测最终的变换。03. 方法03.1. 问题描述0给定要对齐的两个点云：源点云X = {xi∈R3 | i = 1, ...,Nx}和目标点云Y = {yj∈R3 | j = 1, ...,Ny}，我们首先为它们提取局部特征。然后，对于源点云中的每个点，我们在目标点中找到其在特征空间中的最近邻，形成N对假设对应关系。所提出的方法估计两个点云之间的刚性变换，即旋转矩阵（R∈R3×3）和平移向量（t∈R3）。所提出方法的流程如图2所示。03.2.二阶空间兼容性0为了分析用于采样的度量的有效性，我们首先定义模糊事件的概率为：0P am ( M ) = P( M in,out > M in,in ) , (1)0其中M是用于测量对应相似性的特定度量。P(Z)是事件Z的概率（为方便起见，我们在后续部分中使用此符号表示）。M in,out是内点和外点之间的相似性，而Min,in是两个内点之间的相似性。当M in,out > Min,in时，外点是内点的近邻，因此基于度量的采样往往会失败。因此，这个概率越低，基于度量的采样就越鲁棒。我们首先介绍常用的一阶空间兼容性（SC）测量[ 5 , 35 , 36 ,45 ]。对应关系i和j之间的SC测量定义如下：0SC ij = φ ( d ij ) , d ij = | d ( x i , x j ) − d ( y i , y j ) | (2)0其中（xi，yi）和（xj，yj）是对应关系i和j的匹配点。φ(∙)是单调递减的核函数。d(∙,∙)是欧氏距离。如图1所示，两个内点之间的距离差din,in应该等于0，因为刚性变换具有长度一致性。然而，由于数据采集和点云降采样引入的噪声，din,in并不完全等于0，而是小于一个阈值dthr。为了方便起见，我们假设d in,in在dthr上均匀分布，并得到两个内点之间距离差的概率密度函数（PDF）如下：0PDF in,in ( l ) = 1 /d thr , 0 ≤ l ≤ d thr . (3)0不同的是，由于异常值的随机分布，两个无关点之间或一个内点和一个异常值之间没有相关约束。我们认为两个不相关点之间的距离差是相同分布的，并假设概率密度函数（PDF）为F(∙)：0PDF in,out ( l ) = F ( l ) , PDF out,out ( l ) = F ( l ); 0 ≤ l ≤ d r0(4)其中d r是d in,out和dout,out的范围。图3(a)展示了3DMatch数据集上的经验F函数。显然，d r远大于dthr。因此，我们可以近似认为F(l)在(0,dthr)内是一个常数，如下所示：0F ( l ) = f 0 , 0 ≤ l ≤ d thr . (5)0接下来，我们考虑SC的模糊概率，即式（1）中的P(SC in,out> SCin,in)。根据式（2），（3），（4）和（5），可以计算如下：0P(SC in,out > SC in,in) = P(d in,out < d in,in)00 PDF in,in ( l ) ∙ PDF in,out ( x ) dxdl0d thr ∙ f 0 dxdl = d thr ∙ f 0 .........R1,t1R2,t2RK,tK...R1,t1R2,t2RK,tK00.010.020.0300100200501500.020.01f0132240对应关系0对0相似性SC2可靠种子0选择0两阶0集合采样0局0匹配0假设选择0图2.我们方法的流程。1.计算对应关系-wise二阶空间兼容性测量。2.选择一些可靠的对应关系作为种子。3.在每个种子周围进行两阶段采样。4.执行局部谱匹配，为每个种子生成R和t的估计。5.选择最佳估计作为最终结果。0以3DMatch [ 62 ]数据集为例。根据[ 5 ]，我们设置d thr =10cm，那么SC测量的歧义概率约为0.1，如图3(a)所示。考虑到异常值的数量可能很大，即使在这个概率下，错误的数量也是不可忽视的。接下来，我们描述了提出的二阶空间兼容性测量（SC2∈RN×N）。具体来说，我们首先构建一个硬兼容性矩阵C（C∈RN×N）：0Cij = 1; dij ≤ dthr, 0; dij > dthr. (7)0C认为满足长度一致性的两个对应关系是兼容的（当i=j时，Ci,j设为0）。然后，SC2ij计算了当i和j兼容时的共同兼容对应关系的数量，如下所示：0SC2ij = Cij ∙0k=1 Cik ∙ Ckj. (8)0类似地，我们分析了这个度量的模糊概率，即P(SC2 in,out> SC2in,in)。假设有N对对应关系，内点比例为α。那么，我们可以证明P(SC2 in,out > SC2in,in)可以表示为（推导见补充材料）：0P(SC2 in,out > SC2 in,in) = p ∙ P(X > (N ∙ α - 2)),0X � S((Nα - 1)p + (N(1 - α) - 1)p2, N(1 - α)p2),0(9) 其中S(∙, ∙)是Skellam分布[30, 32,33]。根据Skellam分布的性质，当α增加时，P(SC2 in,out> SC2in,in)的值会迅速接近0。为了更清楚地比较提出的SC2度量和SC度量的模糊概率，我们根据公式(6)和(9)绘制了它们的模糊概率曲线。如图3(b)所示，提出的SC2度量的模糊概率明显低于SC度量，即使内点率接近0。这表明使用SC2度量作为采样的指导更容易获得一个无外点的集合。当内点率达到1%时，SC2度量的模糊概率接近0，这确保了对具有低内点率的数据进行鲁棒的采样。0点率0dthr 002p0(a) 经验F函数 (b) 模糊概率0SCSC2-5000SC2-2500SC2-10000图3. (a) d in,out和d out,out的经验概率密度函数(F)。(b)歧义概率。SC是空间兼容性度量。SC2-N(N=5000, 2500,1000)是具有N个对应关系的二阶空间兼容性度量。03.3. 可靠的种子点选择0如上所述，通过提出的SC2度量，内点对应关系之间存在很高的相似性。因此，只要我们找到一个内点对应关系，我们就可以通过在度量空间中找到其k个最近邻来构建一个共识集。显然，遍历所有的对应关系必定会找到一个内点，但这并非必要。我们只需要选择一些可靠的点作为种子点来加速配准过程。我们使用谱匹配技术[36]来选择种子点。具体来说，我们首先为所有的对应关系构建相似性矩阵，并将矩阵中的值归一化到0-1之间，按照[36]的方法。然后，按照[5,36]的方法，将每个对应关系与主特征向量的关联作为该对应关系的置信度。主特征向量是通过幂迭代算法[39]求解的。为了确保种子点的均匀分布，我们选择在半径为R的邻域内具有局部最大置信度得分的对应关系作为种子点。种子点的数量(Ns)由整个对应关系的数量的比例确定。03.4. 两阶段共识集采样0在选择了一些种子点之后，我们将每个种子点扩展为一个共识集。我们采用两阶段选择策略进行从粗到细的采样。在第一阶段，我们通过...为每个种子选择K1个对应关系。132250在SC2度量空间中找到其前K1个邻居。如前所述，模糊概率P(SC2 in,out > SC2in,in)非常小。因此，当种子是内点对应关系时，一致集主要也包含内点。同时，SC2度量所表示的相似性侧重于全局信息而不是局部一致性。因此，在SC2度量空间中选择的邻居更均匀地分布而不是聚集在一起，这有利于刚性变换的估计[5]。采用第二阶段采样操作进一步过滤第一阶段得到的潜在异常值。在第一阶段产生的每个集合内重建SC2矩阵，而不是整个集合内。我们通过新构建的局部SC2矩阵选择种子的前K2个（K2 10DGRICPFGRRANSACPointDSCOurs132270FPFH FCGF0配准召回率（%） 旋转误差（°） 平移误差（cm） 配准召回率（%）0DHVR [35] - - - 99.10 0.29 19.80 0.83 DGR [19] 77.12 1.64 33.10 96.90 0.3421.70 2.29 PointDSC [5] 98.20 0.35 8.13 98.02 0.33 21.03 0.450FGR [66] 5.23 0.86 43.84 89.54 0.46 25.72 3.88 RANSAC [25] 74.41 1.55 30.2080.36 0.73 26.79 5.43 CG-SAC [45] 74.23 0.73 14.02 83.24 0.56 22.96 0.73我们的方法 99.64 0.32 7.23 98.20 0.33 20.95 0.310表3.KITTI数据集上的定量结果。（对于DHVR，作者既没有发布KITTI数据集上的训练代码，也没有预训练模型，所以我们报告了他们论文中的结果。）0低重叠场景的结果：3DLoMatch [29]。在PointDSC[5]和DHVR [35]之后，我们采用FCGF[20]和Predator（有两个版本的Predator，我们使用更新的版本）[29]描述符生成对应关系。表2中报告了配准召回率（RR）、旋转误差（RE）和平移误差（TE）。从数据中可以看出，无论是与FCGF还是Predator描述符相结合，我们的方法都实现了最高的配准召回率。同时，我们还在3DLoMatch数据集上展示了一些定性结果。如图4所示，我们的方法可以成功地对齐两个点云，其中低重叠比例清晰可见。04.3. 室外场景评估0在这个实验中，我们在户外的KITTI[27]数据集上进行测试。我们将DHVR [35]、DGR[19]、PointDSC [5]、RANSAC [25]、FGR [66]、CG-SAC[45]的结果作为对比。DHVR、DGR和PointDSC是基于深度学习的方法，而其他方法是非学习方法。如表3所示，我们的方法明显优于非学习方法。当与FPFH描述符相结合时，我们的方法的配准召回率（RR）比RANSAC高出25.23%，与FCGF描述符相结合时高出17.84%。平移和旋转误差也比RANSAC要低得多。我们的方法与FPFH描述符获得了最高的配准召回率。对于学习网络，我们的方法可以达到接近它们的性能。04.4. 泛化和鲁棒性0泛化实验。如上所述，基于深度学习的方法在3DMatch、3DLoMatch和KITTI数据集上也取得了竞争性的性能。与这些基于深度学习的方法相比，我们方法的另一个优势是在不同数据集之间没有偏差，而基于深度学习的方法在不同数据集之间进行泛化时会出现性能下降。为了证明这一点，我们在3DMatch、3DLoMatch和KITTI数据集上进行了泛化实验。对于最近的基于学习的方法，包括DGR和PointDSC，我们报告了跨数据集的结果。具体来说，我们采用了它们在KITTI上预训练的模型来在3DMatch和3DLoMatch上进行测试，并使用3DMatch的0表4.泛化结果。报告了在3DMatch、3DLoMatch和KITTI数据集上的配准召回率(%)。0召回率(%)0内点比例(%)0图5. 在不同内点比例下的配准召回率。0模型在KITTI上的测试。如表4所示，我们的方法在配准召回率上显示出显著的改进，没有泛化问题。这进一步证明了我们方法的有效性。鲁棒性抗噪声。衡量模型拟合方法性能的一个重要因素是在低内点比例下的稳定性。为了进一步验证我们方法的性能，我们在图5中报告了不同内点比例下的结果。具体而言，我们首先使用FPFH为3DMatch数据集生成初始匹配对。然后，根据内点比例，将所有点云对分为6组：<1％，1％-2％，2％-4％，4％-6％，6％-10％和>10％。每组中的点云对数量分别为：141，208，346，252，323和353。如图5所示，当内点比例小于2％时，我们的方法明显优于其他方法。这证明了我们方法的鲁棒性抗噪声。04.5. 结合学习网络0为验证我们提出的方法的灵活性，我们将我们的方法与最近的深度学习方法PointDSC[5]相结合。它采用空间一致性矩阵来指导非局部模块。由于我们提出的SC2度量对于模糊性更加鲁棒，我们将PointDSC中的空间一致性矩阵替换为SC2。我们直接将我们的度量插入其中，而无需重新训练网络。其原始版本和组合版本的配准召回率如表5所示。可以看出，添加我们的度量可以显著提升网络的性能，特别是网络的泛化性能。这表明所提出的度量方法灵活性强，可以与其他方法结合使用。3DMatch3DLoMatchKITTIFPFHFCGFFCGFPredatorFPFHFCGFPointDSC77.5792.8556.0968.8998.2098.02PointDSC+SC283.2493.1057.0569.0499.1098.02PointDSC-gen68.1287.7440.6553.7990.2792.97PointDSC-gen+SC274.1289.5944.8156.7197.4898.02SCSC2TSLSMSeedRR(%)RE( )TE(cm)Time(s)FPFHFCGF132280表5. 将SC 2度量与基于学习的网络相结合的配准召回率。04.6. 消融研究0在本节中，我们在3DMatch数据集上进行了消融研究。我们分别使用FPFH和FCGF描述符进行匹配。我们采用经典的RANSAC作为基准，如表6的第1行和第7行所示。我们逐步将提出的模块添加到基准中并报告结果。二阶空间兼容性。我们首先将二阶空间兼容性（SC2）度量作为RANSAC采样的指导。通过在度量空间中搜索k个最近邻来将每个对应关系扩展为一致集。我们还使用先前工作[5, 45,57]采用的空间兼容性（SC）作为采样指导，并将结果作为比较报告。如表6的第1行、第3行和第7行、第9行所示，使用SC2度量作为指导时，与FPFH相结合时的配准召回率比RANSAC高出14.79％，与FCGF相结合时高出1.66％。同时，由于SC 2度量可以缩小采样空间，SC2度量的平均配准时间要小得多。此外，通过比较第2行、第3行和第8行、第9行，使用SC2度量作为指导可以获得比使用SC度量更好的性能。这是因为SC受到模糊性问题的干扰，而SC2度量可以消除模糊性。两阶段选择。我们进一步采用两阶段选择策略为每个种子生成一致集。当一个种子是内点对应关系时，它几乎消除了第一阶段形成的一致集中的大部分离群点。由于SC2在内点比例增加时变得更加稳定，我们构建了一个局部SC2矩阵来消除潜在的离群点。通过比较表6的第3行、第4行和第9行、第10行，使用两阶段选择策略与FPFH相结合时，召回率提高了1.96％，与FCGF相结合时提高了0.12％。局部谱匹配。当采样最小集时，RANSAC采用实例相等的SVD生成平移和旋转的估计，对错误非常敏感。我们用加权SVD[19, 43]替换了实例相等的SVD[3]，以便为鲁棒配准为可靠性较低的对应关系分配较低的权重。我们在每个一致集中构建了一个软SC2矩阵，然后使用局部谱匹配计算每个对应关系与主簇之间的关联。关联值被用作加权SVD的权重。01）66.10 3.95 11.03 2.86 2）� 71.56 2.07