推荐大家关注3DCV，一个关注3D技术，更关注3D产业的公众号。点击下方卡片，关注3DCV公众号：

本文作者：3D视觉工坊@Vallee | 来源：3D视觉工坊

GitHub代码：https://github.com/zhangxy0517/3D-Registration-with-Maximal-Cliques (暂未开源)

3D点云配准(PCR)是计算机视觉中的一个基本问题，其目的是寻找对齐点云对的最优位姿。本文提出了一种基于极大团(Maximal cliques, MAC)的3D配准方法，其关键思想是放宽先前的最大团(Maximum clique)约束，在图中挖掘更多的局部共识信息，以准确地生成位姿假设: 1)构建相容性图，表示初始对应之间的亲和关系；2)在图中搜索极大团，每个团代表一个共识集。然后，执行节点引导的团选择，其中每个节点对应于具有最大图权值的极大团；3)利用奇异值分解(SVD)算法对选取的团计算位姿变换假设，并利用最佳假设进行配准。在U3M, 3DMatch, 3DLoMatch和KITTI上的大量实验表明，MAC有效地提高了配准精度，优于各种最先进的方法，并提高了深度学习方法的性能。MAC结合深度学习方法在3DMatch / 3DLoMatch上实现了95.7% / 78.9%的配准召回率。

注：团、极大团(maximal cliques)与最大团(maximum clique)的区别参见https://www.jianshu.com/p/dabbc78471d7。

1 引言

点云配准是3D计算机视觉中的一个重要而基本的问题，在3D定位、3D目标检测和3D重建中有着广泛的应用。给定同一物体(或场景)的两次3D扫描，PCR的目标是估计6-DoF位姿变换，该变换精确地对齐两个输入点云。使用点对点特征对应是解决PCR问题的一种流行且稳健的解决方案。然而，由于现有3D关键点检测器和描述符的限制，点云和数据噪声之间的有限重叠，由特征匹配产生的对应关系通常含有离群点，这给精确的3D配准带来了巨大的挑战。

通过处理具有离群对应关系的3D配准问题已经研究了几十年，我们将它们分为纯几何方法和深度学习方法。对于纯几何方法，随机样本一致性(RANSAC)及其变体执行迭代抽样策略进行配准。尽管基于RANSAC的方法简单高效，但当离群比例增加时，其性能非常脆弱，并且需要大量迭代才能获得可接受的结果。同时，提出了一系列基于分枝定界(BNB)的全局配准方法，用于搜索6D参数空间并获得最优解。这些方法的主要缺点是计算复杂度高，特别是当对应集规模很大且离群比例极高时。对于深度学习方法，一些方法关注于提升配准过程中的某个模块，例如研究更具区分性的关键点特征描述符或更有效的对应关系选择技术，而其他一些方法则关注以端到端的方式配准。然而，基于深度学习的方法需要大量的数据进行训练，并且通常缺乏对不同数据集的泛化。目前，在存在严重异常值和跨数据集的情况下，实现准确的配准仍然是非常具有挑战性的。

本文提出了一种基于极大团(Maximal cliques, MAC)的纯几何3D配准方法。关键的洞察是放松先前的最大团(maximum clique)约束，在图中挖掘更多的局部共识信息，以生成准确的位姿假设。我们首先将初始对应关系集建模为相容图，其中每个节点表示单个对应关系，两个节点之间的每条边表示一对相容对应关系。然后，我们在图中搜索极大团，使用节点引导的团过滤来匹配每个图节点与包含它的适当的极大团。与最大团相比，极大团(MAC)是一个更松的约束，能够在图中挖掘更多的局部信息。 这有助于我们从图中获得大量正确的假设。最后，利用SVD算法对选定的团计算位姿变换假设，使用RANSAC家族中流行的假设评估度量来选择最佳假设来执行配准。

本文的主要贡献如下：

• 提出了一种称为极大团（MAC）的假设生成方法。与以前的最大团约束相比，极大团能够在图中挖掘更多的局部信息。我们证明，即使在存在严重异常值的情况下，MAC生成的假设也具有高精度。

• 在MAC的基础上，提出了一种新的PCR方法，该方法在U3M、3DMatch、3DLoMatch和KITTI数据集上取得了最好的性能。值得注意的是，纯几何的MAC方法的性能优于几种最先进的深度学习方法。MAC还可以作为模块插入到多个深度学习框架中，以提升它们的性能。MAC结合GeoTransformer在3DMatch/3DLoMatch上实现了95.7%/78.9%的SOTA配准召回率。

2 方法

2.1  问题描述

对于要对齐的两个点云和，我们首先使用几何或学习描述符来提取它们的局部特征。设和分别表示和中的点。通过匹配特征描述符来得到初始对应集合，式中。MAC从估计和之间的6-DoF位姿变换。

所提出的方法在技术上非常简单，其流程见图2。

2.2  图的构建

图空间比欧氏空间更能准确地刻画对应关系之间的亲缘关系。因此，我们将初始对应关系建模为一个相容图，其中对应关系由几何相容的节点和连接节点的边来表示。在这里，我们考虑两种构建相容性图的方法。

• 一阶图(FOG)：一阶图(FOG)基于对应对之间的刚性距离约束来构建，即：和之间的相容性分数为:其中，是距离参数。值得注意的是，如果大于阈值，和形成边，并且是的权重，否则将被设置为0。因为相容图是无向的，所以权重矩阵是对称的。

• 二阶图(SOG)：SC-PCR中提出了一种二阶相容性度量，它与全局集合中共同相容的对应关系的数量有关。二阶图 (SOG) 从 FOG 演变而来，其权重矩阵 可以计算为：其中表示矩阵的逐元素相乘。

两种图构建方法都可以用于本文的框架。与 FOG 相比，

• SOG 具有更严格的边构造条件以及相邻节点的相容性程度更高；

• SOG 更稀疏，这有助于更快地搜索团。在 MAC 框架中通过实验对比了 FOG 和 SOG。

2.3  搜索极大团

给定一个无向图 ，团 是 的子集，其中任意两个节点有边连接。极大团是一个无法通过添加任何节点来扩展的团。特别地，节点数最多的极大团是图的最大团。

搜索极大团：为了生成假设，基于RANSAC的方法反复从对应关系集合中随机抽取样本。然而，它们不能充分挖掘对应关系之间的亲和关系。从理论上讲，内点会在图中形成团，因为内点通常在几何上是相容的。以前的工作侧重于寻找图中的最大团，然而，最大团是一个非常严格的约束，只关注图中的全局共识信息。相反，我们放松了约束，利用极大团来挖掘更多的局部图信息。通过使用igraph C++库中的igraph_maximal_cliques函数，该函数利用修改的Bron-KerBosch算法，可以非常高效地搜索极大团，其最差时间复杂度为，其中是图的退化度。请注意，在我们的问题中，通常很小，因为在处理点云对应关系时，图通常是稀疏的。

节点引导的团选择：在执行极大团搜索过程后，我们得到极大团集合。在实际应用中，通常包含数以万计的极大团，如果我们考虑所有极大团，这将使其非常耗时。我们提出一种节点引导的团选择方法，以减少。首先，我们计算每个团在中的权重。给定一个团 ，权重为：其中，表示边在中的权重。一个节点可能被多个极大团包含，我们只保留权重最大的那个极大团。然后，从剩余的团中删除重复的团，得到。这背后的动机是使用关于图节点周围的局部几何结构的信息来找到对应节点的最佳一致集合。显然，极大团的数目不会超过。我们可以将这些极大团直接送到后续阶段进行3D配准。然而，当相当大时，保留的极大团的数量仍然可能很大。在这里，我们提出了几种技术来进一步过滤极大团。

• 法向量一致性：在极大团中，我们发现每个对应之间满足法向量一致性。给定两个对应和这四个点上的法向量，则可以计算出这四个点上的法向量之间的角度差：。如果和法向量相容，则以下等式应成立：其中是用于确定角度差是否相似的阈值。

• 团排序：用团的权重按降序组织。排名前的应该更有可能产生正确的假设，这使得控制假设的数量变得灵活。

2.4 假设生成和评估

从上一步过滤的每个极大团代表一组一致的对应关系。对每个一致性集使用SVD，可以获得一组 6-DoF 位姿假设。

• 等实例SVD：从对应关系估计位姿变换通常使用 SVD 实现, 实例相等意味着所有对应的权重相等。

• 加权SVD：给对应关系加权在最近的PCR方法中很常用。可以通过求解相容性图构造的相容矩阵的特征向量来得到对应权重。在这里我们将 的主特征值作为对应权重。

MAC的最终目标是估计最优6-DoF刚体变换(由旋转和平移组成)，使以下目标函数最大化：其中，而表示的分数。我们在这里考虑了几个RANSAC假设评估指标，包括平均误差(MAE)、均方误差(MSE)和内点数。实验中将对不同指标的表现进行比较。选出来的最好的假设将被用来进行3D配准。

3 实验

3.1 实验设定

数据集：考虑了四个数据集，即物体尺度的数据集U3M、场景尺度的室内数据集3DMatch和3DLoMatch以及场景尺度的室外数据集KITTI。U3M有496个点云对。3DLoMatch是3DMatch的子集，其中点云对的重叠率在10%到30%范围，这是非常具有挑战性的。对于KITTI，我们遵循PointDSC和SC-PCR，得到555对点云进行测试。评估准则：我们遵循SAC-COT的方法，使用均方根误差(RMSE)度量来评估U3M物体尺度数据集上的3D点云配准性能。此外，我们还使用旋转误差(RE)和平移误差(TE)来评价场景数据集上的配准结果。通过参考Deep Global Registration中的设置，当3DMatch和3DLoMatch数据集上的RE≤15°，TE≤30 cm，以及KITTI数据集上的RE≤5°，TE≤60 cm时，认为配准成功。我们将数据集的配准准确率定义为成功案例与待配准的点云对数量的比例。实现细节：用C++实现，基于点云库(PCL)和igraph库。对于U3M，我们使用Harris3D(H3D)关键点检测器和方向直方图(SHOT)描述符来进行初始对应生成，与[42]中一样。对于3DMatch和3DLoMatch数据集，我们使用快速点特征直方图(FPFH)描述符和全卷积几何特征(FCGF)描述符来生成初始对应集。对比实验部分的主要步骤是构建SOG，搜索节点引导的极大团，用等实例SVD生成假设，用MAE进行评估。3.2小节中的相容性阈值和距离参数的默认值分别为0.99和10pr；如果输入匹配超过5000，则将设置为0.999以减少计算量。这里‘pr’是一种叫点云分辨率的距离单位[42]。法向量是使用PCL的NormalEstment类用20个最近邻点计算的。在搜索极大团时，团大小的下界被设置为3，没有定义上限。所有实验均使用Intel 12700H CPU和32 GB RAM。

3.2 U3M数据集结果

我们在图 3 中进行了大量的比较。在这里，测试了以下方法，包括 SAC-COT、OSAC、SAC-IA、RANSAC、SC-PCR、FGR、GO-ICP 和 PPF，其中前四个是基于 RANSAC 的方法。RMSE 阈值范围为 0.5 pr 到 5 pr，步长为 0.5 pr。结果表明，MAC 表现最好，并且明显优于所有测试的 基于RANSAC的估计器，例如 SAC-COT、OSAC、SAC-IA 和 RANSAC。基于 MAE 评估准则的MAC 的配准性能在 U3M 上是最好的。

3.3 3DMatch & 3DLoMatch数据集结果

PCR方法对比：对纯几何和深度学习方法都做了对比，包括SM、FGR、RANSAC、TEASER++、CG-SAC、SC-PCR、3DRegNet、DGR、DHVR和PointDSC。结果如表1和表2所示。可以得出以下结论:

• 无论使用哪种描述符，MAC在3DMatch和3DLoMatch数据集上的性能都优于所有对比的方法，表明它在室内场景点云的配准能力很强;

• 与深度学习方法相比，MAC在没有任何数据训练的情况下仍能获得更好的性能;

• 除了配准召回(RR)指标外，MAC还获得了最好的RE和TE指标。这表明 MAC 的配准非常准确，MAC 能够对齐重叠率很低的数据。

用 MAC 增强深度学习方法：将几种最先进的深度学习方法与 MAC 集成以进行评估。所考虑的方法是 FCGF、SpinNet、Predator、CoFiNet 和 GeoTransformer，每种方法都在不同数量的样本（即不同数量的采样点或对应关系）下进行测试，结果见表3。MAC 在 3DMatch 和 3DLoMatch 数据集上显著提高了所有测试方法的配准召回率。值得注意的是，SpinNet、Predator和CoFiNet经过MAC提升后的性能超过了GeoTransformer。MAC与GeoTransformer结合，在3DMatch / 3DLoMatch上实现了95.7% / 78.9%的SOTA配准召回。结果表明:

• MAC可以极大地增强现有的深度学习方法;

• MAC对样本数量不敏感。

3.4 KITTI数据集结果

表4中对比了DGR、PointDSC、TEASER++、RANSAC、CG-SAC、SC-PCR和MAC的结果。MAC在配准召回性能方面表现最好，无论是使用FPFH还是FCGF描述符。MAC的TE也比最先进的纯几何方法SC-PCR低。请注意，室外点云非常稀疏且分布不均匀。

在物体、室内场景和室外场景数据集上的配准实验一致地验证了MAC在不同的应用场景下具有良好的泛化能力。

3.5 分析实验

执行特征匹配选择：在3D配准之前，一种流行的方法是执行离群点拒绝以减少对应集。这里我们使用几何一致性(GC)，它独立于特征空间，并且将最大的一致集群与对应关系之间的相容性关联起来。

通过对表5的第1行和第2行进行比较，GC对MAC性能产生了负面影响，这可能是因为在此过程中也会去除一些内点。这表明，即使在不经过任何过滤的情况下直接利用初始对应集作为输入，MAC仍然可以很好地工作。

图构造的选择：通过使用不同的图构造方法来测试MAC的性能。如表5中第1和第3行所示，在3DMatch上，SOG与FPFH结合时比FOG的配准召回率高1.6%，与FCGF结合时比FOG高0.06%。在3DLoMatch上，SOG与FPFH结合使用比FOG高0.12%，与FCGF结合使用比FOG高0.56%。因此，SOG更适合MAC，详见补充材料。

最大团与极大团对比：为了证明极大团的优势，我们将 MAC 的搜索策略更改为最大团并测试配准性能。如表 5 中的第 1 行和第 9 行所示，与 FPFH 结合时，应用极大团比最大值高 9.8%，在 3DMatch 上与 FCGF 结合时提高了 5.55%。此外，在3DLoMatch上，使用极大团的配准召回率比使用最大团的配准召回率高8.03%，与FCGF结合的配准召回率高10.45%。这有几个原因：

• 极大团包括最大团，且额外考虑了局部图约束，因此搜索极大团可以利用相容性图中的局部和全局信息；

• 最大团是一个非常严格的约束，需要最大化相互兼容的对应关系的数量，但不能保证最优的结果。

节点引导的团选择：我们对比了使用和不使用节点引导(NG)团选择进行极大团搜索的性能。对比表5中的第1行和第4行，在3DMatch上，使用NG在与FPFH结合时召回率提高0.37%，与FCGF结合时提高0.5%。此外，在3DLoMatch上，使用NG可以使FPFH的召回率提高0.23%，FCGF的召回率提高0.73%。值得注意的是，在NG提高召回率的同时，平均RE和平均TE也在下降。例如，在3DLoMatch上，使用FPFH，NG使平均RE减少0.1°，平均TE减少0.11 cm。NG有效地减少了后续步骤中的计算次数，并保证了准确的假设。

团过滤的不同方法：我们测试了两种过滤方法的有效性，法向量一致性和团排序。

• 法向量一致性（NC）：对比表5中的第1行和第8行，NC略微降低了MAC的性能。

• 团排序：第10行到第14行表明，配准召回率随着的增加而增加，这表明越大，产生的团的子集生成的假设越正确。值得注意的是，将设置为100已经可以获得很好的性能。

采用等实例或加权的SVD：表5的第1行和第5行显示了等实例和加权SVD的比较。加权SVD略逊于等实例的SVD，这表明MAC中的样本已经非常一致，不需要额外的加权策略。

不同的假设评估指标：这里我们比较了三种评价指标，包括MAE、MSE和Inlier count，用于MAC假设的评价。如第1、6、7行所示，MAC和MAE的性能最佳。在表5中，与常用的Inlier计数指标相比，MAE在与FPFH结合时召回率提高了0.24%，在3DMatch上与FCGF结合时提高了0.31%。此外，MAE在与FPFH结合时有1.74%的改善，在3DLoMatch上与FCGF结合时与Inlier Count相比有0.05%的改善。MAE在降低RE和TE方面也非常有效。例如，在3DLoMatch上，MAE与FPFH相比，平均RE降低0.35°，平均TE降低0.49 cm。

与RANSAC的假设进行比较：我们通过将RANSAC和MAC的假设与真实变换进行比较来评估生成的假设的质量。结果如表6所示。与RANSAC随机选择对应关系并从没有几何约束的对应关系集生成假设相比，MAC有效地从相容图中的极大团生成更令人信服的假设，充分利用了图中的共识信息。

MAC的性能上限：给定一个理想的假设评估度量，只要能够生成正确的假设，就可以对齐点云对，这可以测试MAC的性能上限。我们改变生成正确假设的数量的判断阈值，并在表7中报告结果。

令人印象深刻的是，MAC-1在3DMatch/3DLoMatch上的配准召回率为98.46%/91.24%。这表明，即使在低重叠的数据集上，MAC也能够为大多数点云对产生正确的假设。此外，我们还可以推断，通过更好的假设评估度量，可以进一步提高MAC的性能。

MAC的时间消耗：我们使用Predator生成不同大小的对应关系来测试MAC的时间消耗，如表8所示。可以看到：

• 一般情况下，当对应数小于1000个时，MAC只需几十毫秒即可完成3D配准。即使使用2500个对应关系的输入，时间消耗也约为0.29秒。请注意，MAC仅在CPU上实现。

• 随着对应关系数量从250个增加到2500个，由于计算花费的时间增加了，构建图的时间成本也增加了。

• 当对应关系数量达到5000个时，MAC配准的时间开销会大幅增加。输入大小的显著增加使得寻找极大团的过程更加耗时。然而，MAC对输入对应集合的势（元素个数）不敏感，如表3所示。因此，使用稀疏输入作为MAC可以在提高配准效率的同时产生出色的性能。

4 总结

本文提出了MAC，用极大团约束从对应关系中生成精确的位姿假设来求解PCR问题。在所有测试的数据集上都达到了最先进的性能，并且可以结合到深度学习的方法中来提高它们的性能。

局限：如表7和表1所示，MAC产生的假设准确，但可能找不到它们。在未来，可以开发一种利用语义信息的更令人信服的假设评估技术。

参考文献：3D Registration with Maximal Cliques