CVPR 2024 | FastMAC将获奖的MAC无损加速80倍

本文介绍了来自CVPR 2024的最新科研成果 - FastMAC。这是一种基于3D对应关系图的完整点云配准算法，通过引入图信号处理，成功地实现了对对应关系图的随机谱采样，从而大幅提高了运算速度，同时几乎不降低性能。FastMAC 能够将CVPR23最佳学生论文奖Maximal Clique算法的速度提升80倍，同时保持高水平的配准成功率。

论文标题：FastMAC: Stochastic Spectral Sampling of Correspondence Graph
论文链接：https://arxiv.org/abs/2403.08770
代码链接：https://github.com/Forrest-110/FastMAC

一、动机

在传统的三维点云配准方法中，目前最精确的方案MAC（Maximal Clique）面临着处理大量输入对应关系时效率低下的挑战，使其无法满足实时应用的需求。高精度配准算法与实时运行速度之间存在着权衡与平衡。现有的随机采样方法（如最远点采样FPS）虽然能够加速配准过程，但通常会导致不稳定性和性能下降。这是由于MAC基于对应关系图的最大团搜索，而传统的降采样方法无法维持利于最大团搜索的图结构。因此，研究者们需要一种更快速且有效的降采样算法，以提高算法的运行速度并保持较高的性能水平。

为了解决这一关键问题，研究团队引入了图信号处理的框架，并提出了一种新的三维配准算法——FastMAC。该算法利用图信号处理技术，在对应关系图上创新性地提出了广义度信号，通过高频图滤波器过滤出广义度信号的高频分量，基于随机谱采样实现了对对应关系的降采样，从而在不降低性能的情况下，实现了对MAC算法的80倍加速，使其能够达到实时性要求。

FastMAC算法的开发是为了解决现有配准方法在处理大规模数据时的效率问题，从而使其更适用于实时应用，如SLAM。通过这项研究，研究团队为三维点云配准领域的发展贡献了重要的技术进步，为实现更广泛的应用提供了有力支持。

二、方法

FastMAC概述：右上方模块展示了从输入对应关系构建对应图的过程。该图通过邻接矩阵在数学上表示。在该矩阵中，高值表示两个对应关系之间的高兼容性。在底部模块中，图上的广义度信号定义为与节点连接的边上的兼容性分数的聚合。通过拉普拉斯高通图滤波器（从邻接矩阵构造）传递信号，以获取其高频成分。滤波后，响应高的节点被称为高频节点。左上方模块介绍了一种随机采样策略，其中节点的采样概率与响应幅度成正比。该采样策略是一种快速的近似最优确定性采样策略。最后，使用MAC配准算法处理输出对应关系。

该论文的目标是在快速而准确地进行3D点云配准，其准确性基于CVPR 2023最佳学生论文提出的最大团（MAC）方法。MAC的关键直觉是放宽最大团约束，并使用更多的最大团候选者来生成潜在准确的姿态假设。然而，当输入对应关系很多时，MAC变得非常慢，由于指数复杂度，最大团搜索成为最大的瓶颈。因此，该论文的目标是设计一个减少图大小但不牺牲最大团配准性能的采样模块。目前广泛使用的采样模块，如随机采样和最远点采样，对于MAC的加速表现不佳。因此，作者转向了图信号处理理论。

首先，作者构建了一个对应图 和邻接矩阵 ，其中SOG表示二阶图，这些设定遵循MAC的设定。值得注意的是， 中的值表示两个对应关系之间的兼容性。

广义度信号 ：为了利用图信号处理理论，需要在对应图上定义一个信号。对于一个节点，常规度信号是它连接的边的数量。在加权图中，对于一个节点，广义度信号定义为它连接的边权重的总和。接下来的章节中将解释为什么这个信号可以帮助构建一个适合于最大团搜索的图滤波器。

2.1 图滤波：核心观点

该论文所提出方法的目标是提取广义度信号（简称为度）的高频成分，这样就可以在度快速变化的图节点中进行采样。本节将强调这样做的原因。该论文首先分析度分布的频率，特别是它与团的关系，如下图所示。

度信号对连通洞穴图上的高通滤波器的响应。节点大小表示响应幅度。这说明了为什么高通滤波器适用于MAC。

为了探索度信号频率与团之间的关系，作者研究了度信号对高通滤波器的响应，该滤波器是用上述提到的拉普拉斯矩阵实现的，应用于连通洞穴图。需要注意的是，度频率是一个仅由邻近节点确定的局部特征。通过优先考虑这一局部特征，可以将其他类型的图简化为连通洞穴图，这将在后面进行解释。

正如上图所示，具有高响应的节点表现出某些特性。如果将每个团视为一个社区，则：

1. 在每个社区中，必须存在一个节点产生强烈的响应。
2. 在每个社区中有足够数量的节点可以引发强烈的响应。
3. 具有显著响应的节点位于每个社区的边缘，并且容易形成切点。它们不仅与其各自社区内的节点有联系，还与其他社区的节点有联系。

这些特性促使了对高频节点进行采样的想法。最大团配准过程涉及在对应图中搜索所有最大团，为每个最大团生成假设并选择最佳的一个。假设输出样本包含高频节点，则：

1. 由于这样的节点在每个社区中必须存在，它们可以覆盖几乎每个最大团。
2. 每个团中足够数量的样本可确保生成假设的能力。
3. 考虑节点之间的连接表示兼容性，所选的对应关系不仅与其所属团内的对应关系兼容，还与其他一些对应关系兼容，表明这些对应关系更可靠，从而生成更好的假设。

现在解释为什么在连通洞穴图中看到的特征可以适用于其他图。在典型的图中，团要么相互连接，要么不连接。相互连接的团保持了连通洞穴图的类似局部特性，而孤立的团则表现出不同的特征。然而，在基于图的配准场景中，孤立的团很少并且通常可以忽略不计。

2.2 图滤波：形式化表述

有了上述的理解，作者首先形式化图滤波器，然后提出通过选择性地采样高频节点来实现目标。有三种典型的图滤波器：高通滤波器、低通滤波器和全通滤波器。

一个简单的高通滤波器设计是Haar-like的高通图滤波器：

在这里， 是一个归一化的图移位， 和 分别是对应的特征向量和特征值。请注意， ，并且如果按降序排列 ，那么有 ，表明低频响应减弱，而高频响应增强。

与之相反的是Haar-like 低通图滤波器。

一个全通图滤波器很简单： 。全通滤波器保留了所有度信号的信息，并直观地对具有较大度的节点进行采样。

当涉及到对应图上的滤波器时，作者首先计算广义度信号 ，其中 ， 是对应集合的大小。然后采用高通图滤波器来滤波 的高频信息。对于 ，作者将高通图滤波器定义为：

或者是对应图的拉普拉斯矩阵。在图顶点域中，对于信号 ， 反映了节点与其邻居的组合之间的差异。

然后就能得到信号 对应于 的响应为 。进一步计算响应幅度： ，它量化了经过高通图滤波后每个节点上信号的能量。这反映了从图中的邻居那里了解到的有关节点上信号值的信息量。

2.3 随机采样

采样算子定义 ： 在获得每个节点对图滤波器响应幅度后，作者根据这些响应幅度进行采样。假设目标是从图信号 中采样 个分量，得到采样信号 ，其中 是采样索引集，则采样算子 被定义为从 到 的线性映射， ，插值算子 被定义为从 到 的线性映射。一个设计良好的采样算子 的目标是最小化重构误差 。

非随机方法 试图创建一个设计良好的确定性采样算子 。之前的工作找到了最优的采样算子：

其中 表示最小奇异值， 表示图移位 的特征向量 中独立的列。在具体实践中使用了一种贪婪算法 来找到一个近似解。它维护了 ， 的一组行，并循环查找另一个行 在 中以最大化由 形成的矩阵的 ，直到 满足终止条件。然而，当处理大型矩阵时，这种算法的速度非常慢，因为它涉及大量的奇异值分解，总复杂度为 ，其中 是样本大小， 是原始大小。

随机采样 ：相比之下，作者采用了一种随机策略。该文将从图滤波中获取的 视为采样分布，并在初始对应集上应用概率采样，得到一个采样集，记为 。 近似于采样算子 ，它在最小化重构误差方面是最优的，并且速度更快。

三、实验

3.1 时间-精度权衡比较

该文在下图中进行了广泛的比较。为了比较，论文展示了基于对应关系的配准方法。所有方法都在使用FCGF作为对应关系生成描述符的KITTI数据集上进行了测试。

下图展示了不同方法的RR性能。该论文提出FastMAC甚至在采样比率低至5%时也能胜过所有其他方法。它的运行速度几乎比具有相似RR性能的方法快80倍，并且与几乎与其一样快的方法相比，其RR高出40%。此外，当采样比率下降到20%时，该方法运行在实时水平，单次配准只需要不到35毫秒。

左图：FastMAC可以将MAC的速度提高80倍，同时保持类似的高配准成功率。这是通过在对应图上对5%的节点进行随机谱形式的采样实现的。该图还显示了其他采样比例，并且当比例低于20%时，FastMAC实现了实时性。 中图: MAC和FastMAC在不同采样比例下的时间分布比较。 FastMAC显著加速了MAC的所有阶段。 右图: MAC和FastMAC中每个组件的详细运行时分析。 最大团搜索不再是瓶颈。

3.2 采样策略比较

该论文还将提出的方法与不同的采样策略进行了比较。这表明MAC本身对于对应关系的数量仍然敏感，从而表明提出的方法优越并适用于最大团配准。用于比较的采样策略包括随机采样和最远点采样（FPS）。值得注意的是，对应关系不是传统的3D点，作者将它们的距离定义为6D空间中的欧几里得距离。该论文测试了FPFH和FCGF描述符。

KITTI数据集上的结果： 下图显示了在KITTI数据集上FPFH和FCGF设置的结果。FastMAC在采样比率从100%下降到5%时保持了一致的RR、RE和TE，并且在1%时仅略微变差。相比之下，随机采样和FPS策略的性能迅速恶化。值得注意的是，FPS的表现甚至比随机策略更糟，这表明一个具有欧几里得距离的6维向量空间不适合于对应关系集。另一个值得注意的是，FPS的性能表现出剧烈的波动，表明缺乏鲁棒性。

在KITTI数据集上的采样性能。每一列代表TE、RE和RR中的一个度量，每一行代表由数据集和描述符组成的设置。阴影区域表示来自多次运行的方差。

3DMatch数据集上的结果： 如下图所示，该论文提出的方法仍然表现良好。尽管随机策略在RE和TE上的表现接近我，但其成功率要低得多。这意味着随机策略在只有少数点云对上表现良好，这限制了它在具有挑战性的实际问题中的使用。

3DMatch 的采样性能。每列代表 TE、RE 和 RR 中的一个指标，每行代表由数据集和描述符组成的一个设置。

3DLoMatch数据集上的结果 ：如下图所示，当采样比率减小时，3DLoMatch的RR下降速度比3DMatch更快，这是由于该数据集的低重叠性造成的。尽管如此，该论文提出的方法在1%采样比率下仍然明显超过其他两种方法的性能，考虑到它们几乎为零的成功率。

3DLoMatch数据集上的采样性能。每一列代表TE、RE和RR中的一个度量，每一行代表由数据集和描述符组成的设置。

3.3 时间分析

为了展示FastMAC的时间效率，该论文进行了设备上的时间分析，报告了时间消耗情况。使用MAC进行比较。

下表展示了在3DMatch上的结果。采样带来的加速抵消了采样过程本身所花费的时间。在不同的采样率下，采样所需时间基本一致。

3DMatch数据集上使用FCGF描述符的时间分析。将MAC与FastMAC进行比较。时间消耗以毫秒为单位进行测量。GC：图构建；MCS：最大团搜索；NCS：节点引导的团选择；PE：姿态估计

3.4 与最先进技术的比较

该论文提出的方法与 3DMatch、3DLomatch 和 KITTI 数据集上的基准方法进行了比较，结果见下列表。当按不同比例采样时，FastMAC 的性能没有明显下降，与其他最先进的方法相比仍具有竞争力。这证明了该论文的采样技术的有效性，它在保持准确性的同时加快了最先进的 MAC 方法的速度。

在KITTI数据集上与基线方法的比较。基线方法的最佳和次佳结果分别用粗体和下划线标记。FastMAC@x 表示以 x% 的比例进行采样。

在3DMatch数据集上与基线方法的比较。

在3DLoMatch数据集上与基线方法的比较。

3.5 描述符的鲁棒性

由于该论文方法接受对应关系作为输入，因此展示其能够处理由不同描述符生成的对应关系的能力至关重要。作者对各种描述符进行了广泛的实验，包括FPFH、FCGF、Predator、Spinnet、Cofinet和Geotransformer。这些描述符用于生成点特征，随后用于获取对应关系。采用KITTI作为数据集，结果如下图所示。

对于RR度量，像Geotransformer、Cofinet、Spinnet和Predator这样更强大的描述符表现出了惊人的优异性，它们的RR不受采样比例的影响，而当采样比例降至1%时，FCGF和FPFH的表现略有下降。对于RE和TE，大多数描述符的行为类似。随着采样率的降低，这些度量首先稳定，然后慢慢增加。因此可以得出结论，该论文的方法对不同描述符产生的对应关系非常鲁棒。

四、消融研究

本节主要关注方法的核心部分的分析，即高通图滤波和随机采样。由于点云的xyz坐标也可以作为图信号，并且以前已经被广泛使用过，作者进一步将xyz信号与该论文提出的广义度信号进行比较，以展示广义度信号的优势。

4.1 高通滤波器、低通滤波器和全通滤波器

在这部分中，作者将该论文提出的高通滤波器与低通滤波器和全通滤波器进行比较，以展示其有效性。对于 Haar-like 低通滤波器，作者选择图移位 为 ，其中 是广义度矩阵， 是邻接矩阵，则采样分布 ，其中 是广义度信号。对于全通滤波器，相应的采样策略是 。

作者使用这些类型的滤波器对对应关系进行采样，并将输出发送到MAC模块。结果如下表所示。高通滤波器更加有效。事实上，全通滤波器仅对具有高度的节点进行采样，而低通滤波器对位于团内的节点进行采样。如果团的大小很大，低通和全通滤波器的功能方式类似于随机采样。这就是为什么这两种滤波器效果不佳的原因。

基于KITTI FCGF数据集的高通、低通和全通滤波器之间的比较配准结果。

4.2 随机与非随机采样

为了阐明该论文提出的随机方法的效率，作者进行了理论分析和实验分析。

理论分析

由于随机和非随机方法都涉及在滤波后计算信号，因此只需分析之后的操作。假设从原始的 个节点中采样 个节点。

非随机 ：首先需要为图移位 计算 ，其复杂度为