SUCOFT：基于保证的超级核心最大化与灵活阈值化的鲁棒点云配准
摘要
点云配准（PCR）是遥感、摄影测量和计算机视觉中的基本问题。由于在通过 3‑D 特征技术进行对应匹配时不可避免地会出现离群点，鲁棒的 PCR 在实际应用中变得必要。然而，现有的鲁棒 PCR 方法仍难以在保持高度对离群点鲁棒的同时实现高效。此外，虽然已有许多方法用于解决已知尺度 PCR，但能以时间效率高的方式处理未知尺度且存在大量或极端离群点的问题的求解器相对较少。为了解决这些限制，本文提出了一种基于兼容性图上超级核心最大化（SUCOM）和灵活阈值化进行离群点拒绝的、同时适用于已知尺度和未知尺度 PCR 的新型且高度鲁棒的方法。首先，我们定义了 K‑超级核心和最大超级核心的概念，并证明最大超级核心在 PCR 问题中进行离群点拒绝时，优于最大团和最大 k‑核心。随后，我们设计了一种保证 SUCOM 算法，通过采用快速裁剪式超级核心检测子程序，来高效地剔除大量离群点。此外，我们通过提出一种有效的方法来建立未知尺度问题的兼容性图，从而将此 SUCOM 算法扩展到未知尺度 PCR。最后，我们设计了一个使用灵活阈值技术的快速离群点拒绝框架，以在 SUCOM 后细化对应关系，并且仅需 2–3 次迭代即可收敛。基于上述四项贡献，我们提出了鲁棒求解器 SUCOM 与灵活阈值化（SUCOFT），能够在存在离群点的已知尺度和未知尺度 PCR 中进行求解。通过对多组真实数据集进行全面的基准测试和实验，我们证明 SUCOFT 在已知尺度和未知尺度 PCR 问题中能对超过 99% 的离群点保持鲁棒，并优于其他最先进的鲁棒求解器。
作者
Lei Sun 宾夕法尼亚大学工程与应用科学学院，费城，PA，USA ORCID: 0000-0003-4135-6858
出版信息
期刊： IEEE Transactions on Geoscience and Remote Sensing 年份： 2024 卷号： 62 页码： 1-21 DOI: 10.1109/TGRS.2024.3404959 文章编号： 10538286 ISSN： Print ISSN: 0196-2892, Electronic ISSN: 1558-0644
指标
总下载量： 386
关键词
IEEE 关键词： 三维显示, 点云压缩, 鲁棒性, 特征提取, 探测器, 太阳, 算法
索引词： Point Cloud, Point Cloud Registration, Robust Point Cloud Registration, Robust Method, Real-world Applications, High Robustness, Photogrammetry, Outlier Rejection, Root Mean Square Error, Maximum Size, Undirected, Residual Error, Real Problems, 3D Scanning, Transformer Model, Binary Matrix, Maximum Iteration, Proof Of Proposition, Armadillo, Small Residues, Common Neighbors, Root Mean Square Error Of Cross-validation, Keypoint Detection, Unknown Scale, Theoretical Guarantees, Pair Of Vertices, Heritage Buildings, Registration Problem, Contributions Of This Article, Largest Value
作者关键词： Compatibility graph, flexible thresholding, outlier rejection, point cloud registration (PCR), supercore maximization (SUCOM)
未定义
第 I 节. 引言
点云配准（PCR）是遥感 1、2、摄影测量和三维计算机视觉的基石，在城市建模与制图 3、室外与室内三维重建 4、[^5]、数字高程建模 5、三维目标检测 6、7、机器人学 [^9] 和 SLAM 8、9、[^12] 中得到广泛应用。它旨在估计最佳对齐两组三维点云的变换。通常情况下，PCR 在实践中是必要的，因为点云通常由具有有限视场（FOV）的激光扫描仪获取，无法在实际使用中捕获整个场景。因此，需要 PCR 来根据不同扫描对点云进行对齐和融合，形成统一的三维场景，通过寻找它们之间的最优变换（姿态）实现。
迭代最近点（ICP）10 是一种经典的 PCR 方法，并已广泛应用于许多现实工程问题。然而，ICP 已知容易收敛到局部最小值或次优解，如果初始化不足（不幸的是，好的初始姿态在现实中通常难以获得）。
解决 PCR 的一种越来越普遍的方法是先使用 3‑D 键点检测器以及特征描述符（例如 11、[^15]、[^16]）在点云之间建立潜在对应关系，然后根据这些对应关系计算最优变换（例如使用 12）。然而，这些对应关系往往会被离群点（也称为错误匹配）破坏，原因包括传感器噪声、重复或相似模式、低重叠度以及密度变化等实际问题。此类离群点的存在可能显著增加基于对应关系的 PCR 的难度，从而迫切需要鲁棒估计方法。
传统方案 RANSAC 13 是一种流行的稳健启发式算法，它通过基于随机采样的共识最大化来拒绝离群点，而其相对于离群比例呈指数级的计算成本限制了其在许多场景中的使用。非最小化稳健估计器，包括 M-估计（例如 FGR [^19] 和 GNC [^20]）以及共识最大化（例如 ADAPT [^21]）方法，也被采用用于稳健 PCR，但当离群比例很高（例如 90% 或以上）时，它们的稳健性会变得非常脆弱。
近年来，利用配对对应兼容性进行离群点拒绝的图基 PCR 方法 [^22]、[^23]、[^24]、[^25]、[^26] 正在获得越来越多关注。最大团 [^27]、[^28]、[^24] 和 k-核心 [^23] 经常被用于 PCR 的离群点拒绝，其中前者已被证明能够在理想情况下有效切除大量离群点，同时保留所有真实内点（假设真实内点集构成最大的团 [^24]）。然而，求解最大团的算法耗时很长，因为它们需要寻找所有最大团，这源于最大团 NP‑hard 的问题。此外，最大 k-核心缺乏理论保证，因为它并不证明包含最大团。
换句话说，我们可以发现，大多数稳健 PCR 求解器仍然难以同时获得高鲁棒性和高效率。
此外，虽然已有许多聚焦于已知尺度 PCR 的稳健方法，但相对较少的求解器能够以高度稳健和高效的方式解决基于对应的未知尺度 PCR（通常用于不同尺度点云之间的跨源配准）问题。一些先前的未知尺度 PCR 方法在对异常值的鲁棒性 [^29]（如将在实验中在 V-A 节中展示）或相对于异常值比例 [^30] 或对应数目 [^24] 的运行时间呈指数增长方面存在限制，从而在处理现实问题时大幅限制了其功能性和适用性。
在本文中，为了高效解决既有已知尺度又有未知尺度 PCR 问题并同时处理大量异常值，我们提出了一种新颖且实用的稳健方法，称为带灵活阈值的超级核心最大化（SUCOFT），其功能在图 1 中进行了示例和说明。我们的核心贡献可总结如下。
图 1. ETH LiDAR 扫描数据集 [62] 上的 PCR 问题。 (左) 可能的对应关系（绿色线条：内点，红色线条：外点）。 (右) 使用所提议的求解器 SUCOFT 对齐的点云。 (a) 已知尺度 PCR。 (b) 未知尺度 PCR。
我们的第一步是引入并定义一个新概念：图论中的 K-超核心，随后我们发现图的最大超核心保证包含最大团，同时对“有缺陷”的内点（不严格满足刚度兼容性）提供更多灵活性，使其成为基于图的异常值拒绝的理想数学结构。
随后，基于最大超核心的异常值拒绝特性，我们构造了一种保证时间效率的超核心最大化（SUCOM）算法，采用对 PCR 兼容图的迭代修剪操作，能够有效拒绝已知尺度 PCR 问题中大多数异常值。
此外，我们成功将SUCOM方法扩展到处理稳健的未知尺度PCR，通过我们所知的第一种针对未知变换尺度的兼容图构造方法实现，并因此使我们的SUCOM框架适用于已知尺度和未知尺度问题。
随后，为了进一步细化SUCOM后的对应关系并获得真正的内点，我们发明了一种新的离群点剔除框架，能够自行消除多达80%的离群点，并且具有卓越的收敛速度，完全适合与我们的SUCOM范式结合使用。
上述贡献最终导致了可应用于已知尺度和未知尺度问题的稳健PCR求解器SUCOFT。我们在室外和室内真实数据集上进行了广泛的基准测试和实验，以验证所提出方法相较于其他先进稳健PCR求解器，在鲁棒性和效率方面的优越性能。
第二节：相关工作
A. 关键点检测、特征描述与匹配
除了直接将最近点作为对应关系的 ICP 14 及其变体（例如 [^31]、[^32]），当初始化不佳时，它们很容易陷入局部最优，但使用 3D 键点检测器和局部特征描述符进行特征匹配是建立潜在对应关系的关键步骤.
键点检测器倾向于筛选出具有显著局部空间特性的高度代表性的键点（亦称兴趣点或显著点），以降低后续对应匹配的计算负担。一些传统（数学）检测器包括使用局部表面补丁的加速检测器 15、Harris 3D 运算符 [^34]，以及内在形状签名（ISS）方法 [^16]。此外，一些基于学习的检测器如端到端几何推理模型 KeypointNet [^35] 和无监督稳定兴趣点（USIP）检测器 [^36] 已出现于 3D 键点检测领域.
作为 3-D 特征描述子，我们拥有基于形状上下文的传统描述子 16、[^38]、[^39]，以及基于几何特征直方图的描述子 [^15]、[^40]。近年来，为了提升性能，提出了深度学习描述子，例如基于孪生网络的 3DMatch [^41]、使用平滑密度值体素化的 3DSmoothNet 17、采用全卷积网络的 FCGF 18、基于注意力的 predator [^43]，以及使用超点匹配模块的 GeoTransformer [^44]。
随后，假设对应关系通常根据从检测到的关键点中选择的特征（通过描述子测量）在点云之间进行匹配。尽管关键点检测和特征描述过程非常庞大，3-D 特征的本质只能提供有限的鲁棒性 19，因此在假设对应关系中仍然不可避免存在离群值，这使得鲁棒 PCR 求解器显得尤为必要。
B. 基于对应关系的鲁棒 PCR
1) 传统鲁棒 PCR:
RANSAC 20 被认为是最常用的鲁棒求解器，它使用随机样本寻找最大一致集，其变体通过局部优化（如 LO-RANSAC 21、FLO-RANSAC [^47]，以及 Graph-cut RANSAC 22）或更智能的采样策略（如 NAPSAC [^49] 和 GroupSAC [^50]）来增强鲁棒性。此外，1-point RANSAC [^29] 用于估计未知尺度 PCR 的比例，RANSAC 还与四点对应集（4PCS）23 协同实现配准。然而，基于 RANSAC 的方法通常会受到最坏情况下随着离群率指数级增长的运行时间影响，这给它们的实际使用带来巨大的劣势。
非最小化的鲁棒估计器 如使用 Geman‑McClure 损失的 FGR [^19] 在 M‑估计类别中采用截断最小二乘损失的 GNC [^20] 以及在共识最大化类别中的 ADAPT [^21] 都可能与标准的非最小化朴素（无外点）求解器一起工作 并且能够容忍大约 80%–90% 的离群点， 但它们有限的鲁棒性似乎不足以满足许多实际应用。
Branch-and-Bound (BnB) [^52] 的目标是搜索参数空间以寻找最优变换，但它随问题规模呈指数级增长。GORE 24 是一种保证求解器，它将 BnB 作为子例程，虽然在大规模问题上也可能运行缓慢；随后提出 QGORE [^53]，它是一个速度更快且几乎保持相同紧致度的版本。一些其他传统方法包括投票引导的求解器，例如使用三层投票和排序策略的 TriVoC [^54]，以及松紧几何投票（LT-GV） [^25]，后者在对应关系打分中应用松散与紧致的几何约束，VBReg [^55] 使用变分贝叶斯，以及改进版的 4PCS 求解器，如 keypoint 4PCS [^56] 和 super 4PCS [^57]。
2) 兼容性/基于图的鲁棒 PCR:
在已知尺度的 PCR 中，可以利用成对对应的互相兼容性构建兼容性图。图论算法如 TEASER [^24] 与 LT-GV [^25]，通过最大团作为子程序，以及采用最大 k-核心的 ROBIN [^23]，被用于在兼容性图的基础上移除大量异常值。CG-SAC [^58] 提出了通过结合常规约束的兼容性引导假设策略。RANSIC [^30] 探索基于图的不变性以解决已知尺度与未知尺度 PCR 的挑战。SC2-PCR 25 提出二阶兼容性以强化兼容性矩阵，[^26] 进一步采用节点引导的最大团来提升性能。除此之外，CLIPPER [^22] 是一个快速近似求解器，用于在鲁棒问题中寻找最大团，但它没有理论保证，并且在极端异常值比例下失败。 据我们所知，兼容性图仅被应用于已知尺度的 PCR 问题，尚未应用于未知尺度。值得注意的是，本文的主要贡献之一是首次将兼容性图推广到未知尺度。
3) 基于学习的鲁棒 PCR:
深度学习框架也广泛用于 PCR 问题。典型的基于学习的 PCR 示例包括：3DRegNet [^60] 基于回归模块，DGR 26 结合 6-D 卷积网络与加权 Procrustes，PointDSC 27 操作非局部特征聚合模块加上谱匹配模块，DHVR [^63] 在 Hough 空间使用学习投票技术，PointDifformer [^64] 利用神经扩散网络和热核签名，IMFNet [^65] 使用注意力融合模块提取 3-D 描述和 PCR 的结构与纹理信息，SACF-Net [^66] 使用基于跳跃注意力的对应过滤网络，结合几何和上下文感知信息提升 PCR 性能，MCPT [^67] 作为点云变换器，使用改进的自注意机制和残差网络以提升多尺度特征融合。
第III节. 前提
A. 问题表述
给定两个 3-D 点云：\mathcal {P}=\{\boldsymbol {p}_{i}\in \mathbb {R}^{3}\}_{i=1}^{N} 和 \mathcal {Q}=\{\boldsymbol {q}_{i}\in \mathbb {R}^{3}\}_{i=1}^{N}，其中每个 (\boldsymbol {p}_{i}, \boldsymbol {q}_{i})（i\in \{1,\ldots ,N\}）是一个假设对应关系，广义 PCR 的目标是求解最佳变换（s^{\star }、\mathbf {R}^{\star } 和 \boldsymbol {t}^{\star }），以最佳对齐 \mathcal {P} 与 \mathcal {Q}，其中标量 s\gt 0 是比例，\mathbf {R}\in \text {SO}(3) 是旋转矩阵，\boldsymbol {t}\in \mathbb {R}^{3} 是平移向量。在许多情况下，比例 s 总是 1，因此我们称其为已知比例 PCR，其中 (R 和 \boldsymbol {t}) 构成刚性变换。但在某些其他情况下，比例 s 可能是未知的，我们称其为未知比例 PCR（这可能发生在点云由不同传感器捕获时，例如一个由 LiDAR，另一个由深度相机捕获）。
在最理想的情况下，如果所有假设对应关系都是内点，闭式方法（例如 SVD 28）可以直接计算最优变换。然而，在实践中，假设对应关系往往被异常值污染（其数量通常未知），因此需要更具挑战性的鲁棒 PCR 来拒绝异常值并得到正确的变换。
B. 基于刚度的兼容性图
我们首先回顾基于已知尺度 PCR 问题中的刚度约束的兼容性图和矩阵。
众所周知 [^23]、[^30]、[^24]，即：对于任意两个对应关系（例如 i 和 j），若它们均为真正的内点，则它们应满足以下刚度（亦称尺度不变）兼容性约束：
\begin{equation*} \left |{{ \left \|{{\boldsymbol {p}_{i}-\boldsymbol {p}_{j}}}\right \|-\left \|{{\boldsymbol {q}_{i}-\boldsymbol {q}_{j}}}\right \| }}\right | \leq 2\tau \tag {1}\end{equation*}
其中 \tau =c\cdot \sigma 是内点阈值（通常我们将系数 c=3 - 5 设为满足 [^68] 所述的足够置信度），\sigma 表示噪声的标准差。此约束直观地意味着两内点之间的距离在刚性变换后几乎保持不变（仅因噪声略有扰动）。基于此刚性兼容性约束，我们可以构建一个二值对称兼容性矩阵 \mathbf {A}\in \mathbb {R}^{N\times N}，它表示每一对应对的兼容性条件，即：若条件（1）对 i 与 j 成立，则 \mathbf {A}(i,j)=1；否则，\mathbf {A}(i,j)=0。在图论中，A 本质上是邻接矩阵，其中每个对应关系表示一个顶点，满足条件（1）的每一顶点对形成一条边，如图 2(a) 所示。
图 2. (a) 鲁棒 PCR 问题及其兼容性图和矩阵的示意图。绿色和红色线/点分别表示内点和异常值。(b) 2-超级核心和 3-超级核心的示例。(c) 图及其内部 3-超级核心的示例。(d) 例子图，其最大超级核心为 3-超级核心，且包含三个 4-团，其中 de、df 和 ef 是“缺陷”内点对。(e) 例子图，其最大超级核心为 4-超级核心，且包含两个 5-团，其中 ef 是“缺陷”内点对。
第四节 方法论
A. K-超级核心与最大超级核心
1) K-超级核心：定义与性质：
我们首先定义无向图的 K-超级核心。
定义 1（K-超级核心）：
如果在一个 最大子图 中任意两个相互连通的顶点至少共享 K - 1 个公共邻居（不包括这两个顶点自身），我们将该子图定义为 K-超级核心。
这里 “maximal subgraph” 的意思是我们不能再添加任何顶点或边，使得该子图仍然满足“至少共享 K - 1 个公共邻居”的属性。图 2(c) 给出了一个特殊 3-超级核心的例子。我们可以看到 K-超级核心不一定是内部连通的实体，因为图 2(c) 中的 3-超级核心可能是两个不相连的 4-团的并集。
随后我们给出一个关于 K-超级核心的重要命题。
命题 1（K-超级核心中的最大团大小）：
一个 K-超级核心中最大团的基数（大小）至少为 K + 1。
证明 1（命题 1 的证明）：
基于定义 1，很明显一个 (K + 1)-团是具有最少顶点数的 K-超级核心，因此任何大小大于 (K + 1) 的团都有可能存在于 K-超级核心中。
现在，我们可以通过证明以下内容来证明命题 1：不可能构造一个最大团大小（基数）为 K 的 K-超级核心。
假设我们有一个 K-团，其顶点记为：\mathcal {V}=\{v_{1}, v_{2},\ldots , v_{K}\}，我们证明：不可能在其基础上通过添加额外的顶点和边而不引入 (K + 1)-团来构建一个 K-超级核心。
由于兼容图中的所有顶点和边是并行的（等权重，没有顺序或先后），我们可以将添加顶点和边简化为一次添加一个顶点（以及其关联的边）。
根据定义 1，我们知道图（或子图）成为 K-supercore 的必要条件是该图中的每个顶点至少具有 K 度（连边）。因此，对于 \mathcal {V} 中的每个顶点，为成为 K-supercore 至少还需要多一度，所以我们必须添加一个新顶点 v'_{1} 并将其连接到 \mathcal {V} 中的顶点。然而，在这种情况下，我们不能把 v'_{1} 连接到 \mathcal {V} 中的所有顶点，因为这会使图变成一个 (K + 1)-clique。因此，总会存在一个顶点 v_{i}~(i\in \{1,\ldots ,K\}) 与 v'_{1} 未连通，所以它仍然缺少至少 1 度才能成为 K-supercore。现在，我们必须再次添加一个新顶点 v'_{2} 并将其与 v'_{1} 连接。虽然 v'_{1} 现在满足 K-degree 条件，但根据定义 1，新添加的顶点 v'_{2} 必须与 v'_{1} 共享 K - 1 个邻居。现在，v'_{1} 只有 K - 1 个邻居（不包括 v'_{2}），如果 v'_{2} 与这些 K - 1 个邻居全部相连，图中将再次形成一个 (K + 1)-clique。此时，解决这个两难的唯一办法是再添加一个新顶点（例如 v'_{3}），但这会触发无限添加新顶点的循环，以防止图出现 (K + 1)-clique。请注意，图 3 直观地说明了这个两难的一个例子。
图 3. Proof 1 中困境的直观例子。假设 K=4，我们有一个 4‑团（3‑超核）与顶点 \mathcal {V}=\{v_{1}, v_{2},v_{3}, v_{4}\}，并且我们想添加新顶点 $v'{1},v'{2},\ldots $ 来构建一个 4‑超核而不引入 5‑团。对于第一个添加的顶点 v'_{1}，我们可以看到在将 v'_{1} 与 v_{1},v_{2} 和 v_{3} 连接后，不能再将 v'_{1} 与 v_{4} 连接，否则会形成 5‑团：\{v_{1}, v_{2},v_{3},v_{4},v'_{1}\}。然后，我们必须引入另一个新顶点 v'_{2}，它必须与 v'_{1} 再共享三个邻居，并且 v'_{1} 仅有三个邻居：v_{1},v_{2} 和 v_{3}，但在将 v'_{1} 与 v_{1} 和 v_{2} 连接后，就无法再将其与 v_{3} 连接，因为这将导致另一个 5‑团：\{v_{1}, v_{2},v_{3},v'_{1},v'_{2}\}，因此顶点/边的添加将陷入无限循环。
到目前为止，我们可以得出结论，构建一个最大团大小为 K 的 K-超核是不切实际的（显然也表明其最大团大小不能小于 K）。因此，K-超核不能在不包含 (K + 1)-团的情况下形成。
因此，命题 1 已被证明。
命题 1 表明，任何 K-超核至少必须包含一个 (K + 1)-团。实际上，可能存在多个 (K + 1)-团，如图 2(c)–(e) 所示，并且最大团大小也可能大于 K + 1，因为图的 K-超核通常是 K'-超核（K'\lt K）的子图。
2) 最大超核:
现在，我们给出最大超核的定义。
定义 2（最大超核）:
无向图的最大超核是具有最大可能超核大小 K^{\star } 的 K^{\star }-超核。
根据定义 2，我们知道在此图中无法找到任何 (K^{\star } +1)-supercore。除此之外，如果图中包含多个 K^{\star }-supercore，则最大 supercore 应该是它们的 union，如图 2(c)–(e)所示。
命题 2（最大 Supercore 与最大 Clique）:
在无向图中，最大 supercore 必须包含最大 clique（换句话说，最大 clique 必须是最大 supercore 的子图）。
Proof 2（命题 2 的证明）:
假设最大 clique 是一个 J^{\star }-clique，最大 supercore 是一个 K^{\star }-supercore，基于 Proposition 1，我们可以推导出：K^{\star } \leq J^{\star } - 1（否则最大 clique 的大小会大于 J^{\star }）。因此，我们可以得出这个 J^{\star }-clique 必须是 K^{\star }-supercore 的子图（因为 K^{\star }-supercore 是按 Definition 1 定义的极大子图），这正是本图的最大 supercore，因此命题 2 得到满足。
现在，我们讨论最大 clique、最佳最大 clique、最大 k-core 与提出的最大 supercore 之间的区别。在此之前，我们需要先回顾两个概念：1）最大 clique 是指不能通过添加相邻顶点来扩展的 clique，2）图的最大 clique 指的是具有最大基数（clique 大小）的最大 clique。请注意，这里的“最佳最大 clique”特指在 [^26] 所提出的估计误差最低的最大 clique。
a) 最大 supercore 与最大 clique 对比：
与最大团相比，最大超核心对“缺陷”内点具有更高的容忍度，'缺陷'内点指的是无法满足条件（1）中刚性兼容性的内点对应对。我们知道，从理论上说，条件（1）并不一定在所有内点之间始终严格满足，因为我们只能通过设置足够大的阈值 \tau =c\cdot \sigma 来开启高置信度（例如 p=0.99+），该阈值用于区分内点与外点。感兴趣的读者可以在 [^68] 中找到关于该阈值设置的更多概率推导。然而，这种置信度永远无法达到 1，意味着要使该条件以概率方式严格满足所需的阈值将是无穷大（显然在实际中不可行）。因此，在实际问题中，仍可能出现一些“缺陷”内点（例如，由于偶发的高局部噪声），尤其当对应集很大时，它们会被从最大团中移除，导致真正的内点缺失。但如果改用最大超核心，这些“缺陷”内点仍然可以得到保留。例如，在图 2(e) 中，假设所有给出的顶点：a,b,c,d,e 和 f 都是真正的内点，而顶点对 ef 是这样一对“缺陷”内点，最大超核心（一个 4-超核心）仍然可以保留这六个顶点，而最大团 [无论是团 (a,b,c,d,f) 还是团 (a,b,c,d,e)] 必须在 e 与 f 之间放弃其中一个顶点。同样，最大超核心的这一优势也适用于图 2(d) 的情况。更重要的是，寻找最大超核心在实际和计算上都很方便，第四节 B 将提供一种快速且有保证的算法。
b) 最大超核心与最佳最大团：
与上一段的讨论类似，最佳最大团仍然无法很好地处理“缺陷”内点的问题。按照图2(e)中的例子，最佳最大团应该是团 (a,b,c,d,e) 或团 (a,b,c,d,f)（因为真实内点集合 (a,b,c,d,e,f) 根本不是一个团）。在这种情况下，为了根据 [^26] 中的方法估计最终变换，必须排除点 f 或 e。换句话说，使用最佳最大团无法防止此类“缺陷”内点被抛弃。因此，最大超核心相比最佳最大团仍显示出更好的灵活性和对“缺陷”内点的容忍度。
c) 最大超核心 与 最大 k-核心：
与已知缺乏理论保证能够内部包含最大团的最大 k-核心不同，最大超核心理论上保证能够包含最大团（如命题2所示）。
B. SUCOM 与已知尺度PCR
我们接下来的目标是在保证但时效高效的方式下，从 PCR 的兼容图中寻找最大超核心。为此，我们将问题拆分为两步：1）对于给定 K，通过裁剪（见第IV-B1节）从兼容图中获取 K-超核心；2）寻找最大 K-超核心（见第IV-B2节）。
1) 基于裁剪的快速 K-超核心检测：
我们首先关注如何在给定（固定）K 的无向图中高效地寻找 K-超核心。
按照第III-B节，我们可以使用成对刚性约束计算二进制兼容矩阵 \mathbf {A}\in \mathbb {R}^{N\times N}。
我们设计了一种易于操作的算法，称为快速迭代裁剪 K-超核心（FITK），它通过迭代裁剪兼容图得到给定 K 的 K-超核心，其伪代码见算法1。接下来，我们按以下方式详细描述 FITK 过程。
算法1 快速迭代裁剪 K-超核心
a) 第1行和第2行以及第4–8行：
我们首先初始化一个全零矩阵 \mathbf {A}^{\text {last}}，用于存储最后一轮的兼容性矩阵，以帮助确定迭代过程中的收敛条件。然后，我们开始迭代，并且不会停止，直到连续两轮的兼容性矩阵完全相同（这表示已收敛）。
b) 第3行：
在每一次迭代中，我们通过一系列简单的矩阵运算来修剪矩阵 A。这里，\odot 表示两个矩阵的Hadamard（逐元素）乘积，\mathbf {BoolMat}[\mathbf {X}\geq \gamma] 表示与 X 同尺寸的二进制矩阵，其中满足条件 (\geq \gamma) 的每个元素为真（1），否则为假（0）。具体而言，在 \mathbf {A}^{2} 中，元素 (i,j) 将是列 i 与 j 的点积，即 \mathbf {A}(:,i)^{\top } \mathbf {A}(:,j)，它计算对应对 (i,j) 的共同邻居数量。然后，\mathbf {BoolMat}[\mathbf {A}^{2}\geq (K-1)] 用来检查对应对 i 与 j 是否共享足够多的邻居，如定义1所示。若满足，则元素 (i,j) 在下一轮保持为1；否则为0（表示对应对或边 (i,j) 被修剪）。Hadamard乘积 \odot \mathbf {A} 确保已修剪的对应对（边）不会重新出现。
我们可以观察到：在FITK的每一次迭代中，共享少于 K - 1 个邻居的“坏”对应对将被修剪，而仍有可能保持在最终 K-supercore 的“好”对应对将继续生存以供后续迭代。 因此，随着迭代次数的增加，矩阵 A 的密度（非零元素数量）将因修剪操作而下降，这使得更多新的“坏”对应对在后续轮次中被检测到并修剪。以此方式，随着算法收敛，即不再检测到任何“坏”对应对时，A 就是我们所期望得到的 K-supercore 的兼容性矩阵。
此处，我们引入一个命题来验证所提出的FITK算法的最优性与正确性。
命题3（FITK的正确性）：
使用给定的 K 运行 FITK (算法 1) 直到收敛，输出矩阵 \mathbf {A}_{K} 是输入图的 K-超核心。
证明 3（命题 3 的证明）：
我们可以通过反证法轻松证明这一点。如果在 \mathbf {A}_{K} 中存在一对顶点（例如顶点 \lambda 和 \epsilon）仅拥有 d（其中 d\lt K-1）个公共邻居（不包括它们自身），那么我们必须有：\mathbf {A}(:,\lambda)^{\top } \mathbf {A}(:,\epsilon) =d\lt K-1。显然，这与 FITK 算法的终止条件相矛盾（因为如果存在 \mathbf {A}(:,\lambda)^{\top } \mathbf {A}(:,\epsilon)\lt K-1，FITK 将不会停止）。换句话说，在 FITK 之后图中每对剩余顶点必须至少拥有 K - 1 个额外公共邻居；此外，FITK 仅对不合格的边/顶点进行修剪，因此输出确实是满足此属性的最大子图（因为 FITK 过程中永不修剪任何额外的合格边/顶点）。因此，\mathbf {A}_{K} 是表示输入图 K-超核心的兼容性矩阵。
命题 3 表明，如果已知最大超核心大小 K^{\star }，FITK 能够从兼容性图中找到 K^{\star }-超核心（换言之，我们想要的最大超核心）。因此，接下来的问题是如何实现最大超核心大小 K^{\star }。
2) 有保证且快速的 SUCOM：
我们现在的目标是从兼容性图中寻找最大超核心大小 K^{\star }。我们设计了一种高效且理论上有保证的算法，能够通过将 FITK 算法作为子程序来快速寻找 K^{\star } 以及最大超核心。伪代码如算法 2 所示，称为 SUCOM。
算法 2 超核心最大化
a) 第 1 行：
给定兼容性图 A，我们首先使用预设的 K_{\min } 运行 FITK 算法，该算法将修剪掉大量“粗糙”离群点，并强制所有剩余的对应对至少拥有 K_{\min }-1 个公共邻居（例如，如果我们设置 K_{\min }=0.01N-1，则假设离群点比例不超过 99%）。
b) 第 2–8 行:
下一步是获取所有可能的候选 K 值列表，其中最优（最大）K^{\star } 必须包含在其中。 这可以通过计算矩阵 \mathbf {A}_{K_{\min }} 的列和（或等价的行和）向量 \boldsymbol {f}\in \mathcal {R}^{N} 来实现。 这里，\sum \mathbf {A}_{K_{\min }}(:,x) 表示 \sum _{i=1}^{N} \mathbf {A}_{K_{\min }}(i,x)。 然后，我们将 \boldsymbol {f} 按降序排列得到向量 \boldsymbol {s}。 通过检查 \boldsymbol {s} 中的 j{\text {th}} 点是否至少有 j-1 个邻居，并取第一个不满足此条件的 j 的前两步位置的值作为 K_{\max }，我们可以得到 K_{\max }。 这里的直觉在于：既然 x=(j-1) 是满足 x-1\leq \boldsymbol {s}(x) 的最大可能值，最大可行的 K 值应该是 (j-2)，因为仍然至少有 (j-1) 个可用顶点，其邻居数不少于 (j-2)（这是 K-supercore 存在的必要条件）。
c) 第 9–15 行:
算法亮点在于：通过迭代应用 FITK 来剔除“坏”对应对，大小 K 从上限 K_{\max } 减小到下限 K_{\min }。 如果当前 K 大于真正的最大 supercore 大小 K^{\star }，这意味着兼容性图中不存在 K-supercore，那么整个矩阵 \mathbf {A}_{K} 最终会根据 FITK 的机制被逐步裁剪至空，迫使 \mathbf {A}_{K} 中的所有元素变为零。 但当我们遇到第一个能够使 \mathbf {A}_{K} 不是全零的 K 时，意味着其中存在一个 K-supercore，此时该 K 必须是我们寻找的最优（最大）K^{\star }。 最后，我们收集所有满足 \sum \mathbf {A}_{K}(:,\rho)\gt 1 的合格对应对 \rho \in \{1,2,\ldots ,N\}，得到相对于最大 supercore 的纯净对应集 \mathcal {L}。
由于我们从上限到下限尝试每个可能的 K 值，并保留能使输出图非空的最大值，SUCOM 能够保证找到最大 supercore 大小 K^{\star }。 并且根据 FITK 的命题 3，最大 supercore 可以通过 SUCOM 最优地求解。
d) SUCOM 算法的直观示例：
为更好地阐明 SUCOM 的机制（参见算法 2），图 4 为 SUCOM 算法中的迭代修剪过程（以 FITK 为子程序）提供了一个简单、具体且直观的示例。在图 4 中，兼容性图及其在修剪过程中的相关矩阵逐步显示。我们首先使用 K=2 在图上运行 FITK，因而边 ae 和 ab 被修剪，因为它们没有共同邻居。随后，我们使用 K=3 对剩余图再次运行 FITK，且边 bc、bd 和 bf 仅共享一个公共邻居，因而它们会被 FITK 修剪，最终得到的图即为我们所需的最大超核心（也是 3-超核心）。
图 4. SUCOM 机制的直观示例.
算法 3 未知尺度注册的兼容性图.
C. 强健的未知尺度 PCR
除了使用 SUCOM 对已知尺度 PCR 问题进行异常值剔除外，我们还将其扩展到未知尺度 PCR，作为本文的另一项贡献。
1) 未知尺度 PCR 的兼容性图：
我们的基于最大超核心的鲁棒方法的构建块必须是兼容性图的建立。对于已知尺度 PCR，兼容性图可以通过成对刚度约束轻松构建，但对于未知尺度 PCR，刚度不再适用，导致构建兼容性图相当困难。
作为本文另一项关键创新，我们设计了一种基于尺度兼容性的新兼容性图构建方法，用于处理未知尺度 PCR 问题。
首先，我们构建一个矩阵 \mathbf {S}\in \mathbb {R}^{N\times N}，存储所有对应对的尺度，
\begin{equation*} \mathbf {S}\left ({{i,j}}\right )=s_{ij}=\frac {l^{q}_{ij}}{l^{p}_{ij}}=\frac {\left \|{{\boldsymbol {q}_{i}-\boldsymbol {q}_{j}}}\right \|}{\left \|{{\boldsymbol {p}_{i}-\boldsymbol {p}_{j}}}\right \|}. \tag {2}\end{equation*}
此外，我们还需要另一个矩阵 \mathbf {L}\in \mathbb {R}^{N\times N}，其中
\begin{equation*} \mathbf {L}\left ({{i,j}}\right )=\frac {\tau }{l^{p}_{ij}}=\frac {\tau }{\left \|{{\boldsymbol {p}_{i}-\boldsymbol {p}_{j}}}\right \|} \tag {3}\end{equation*}
它存储所有对应对的噪声边界尺度化距离数据，以方便后续进行基于尺度的兼容性检查操作。
根据 [^30]，我们知道：对于由两对对应关系计算出的两个尺度，例如来自对应对 (i,j) 的 s_{ij} 和来自对应对 (a,b) 的 s_{ab}，基于尺度的兼容性可以表述为
\begin{equation*} \left |{{s_{ij}-s_{ab}}}\right | \leq \frac {\tau }{\left \|{{\boldsymbol {p}_{i}-\boldsymbol {p}_{j}}}\right \|} + \frac {\tau }{\left \|{{\boldsymbol {p}_{a}-\boldsymbol {p}_{b}}}\right \|}. \tag {4}\end{equation*}
该基于尺度的兼容性不等式可以重写为 S 和 L 矩阵元素的简单运算
\begin{equation*} \left |{{\mathbf {S}\left ({{i,j}}\right )-\mathbf {S}\left ({{a,b}}\right )}}\right | \leq \mathbf {L}\left ({{i,j}}\right )+\mathbf {L}\left ({{a,b}}\right ). \tag {5}\end{equation*}
现在，我们可以展示构建兼容性矩阵的完整算法，该算法被称为未知尺度配准的兼容性图（COGUR），如算法 3 所示。以下给出说明
算法 4：使用灵活阈值的快速异常值拒绝
a) 第 1–4 行和 15–16 行：
我们首先应该根据 (2) 和 (3) 构建矩阵 S 和 L。然后，使用两层嵌套循环遍历每一对顶点（对应关系），以检查 (4) 的基于尺度的兼容性
b) 第 5–14 行：
在 COGUR 中构建兼容性图的关键是使用每对对应关系的最小公共邻居数（由 SUCOM 中之前的 K_{\min } 定义）来确定兼容性。具体而言，在两层嵌套循环中，如果顶点 i 与 j 能够保留在最大超核心内，则它们必须共享至少 K_{\min }-1 个邻居（这基于内点比例不低于 (K_{\min }+1/N) 的条件）。因此，我们可以通过引入另一层循环遍历所有候选邻居（假设为 k）来计数共享邻居数，并检查对应对 (i,j)、(i,k) 和 (j,k) 是否全部满足 (5) 中的基于尺度的兼容性条件。如果 (i,j) 共享的邻居数至少为 K_{\min }-1，则 (i,j) 被视为有资格在兼容性图中形成连接边（这意味着条目 \mathbf {A}(i,j) 和 \mathbf {A}(j,i) 应为 1）
通过这种方式，我们可以为未知尺度 PCR 问题建立兼容性矩阵 A
2) 未知尺度 PCR 的最大超核心：
在使用 COGUR 获得初始兼容性矩阵 A 后，我们可以直接在 A 上运行 SUCOM 以获得最大 supercore，且该过程与算法 2 中已知尺度版本完全相同。
在采用 SUCOM 对已知尺度或未知尺度的 PCR 进行处理后，可以剔除大量离群点。根据 [^24]，最大团后离群点比例通常低于 10%，在 V-A 节中我们也经验上证明最大 supercore 后的离群点比例在 V-D2 节中同样不超过 10%。到目前为止，我们稳健 PCR 求解器的最终步骤是将剩余的对应关系集合 \mathcal {L} 交给一个能够快速移除 \mathcal {L} 中小部分离群点并精确估计变换的稳健估计器，正如在 IV-D 节所示。
D. 快速对应关系细化与可变阈值的离群点拒绝
作为本文的第四项贡献，我们进一步提出了一种快速且新颖的异常值剔除方法，称为使用可变阈值的快速异常值剔除（ROFT），用于在SUCOM之后细化\mathcal {L}中的对应关系。
阈值处理技巧已广泛应用于多种数学问题的异常值剔除，例如 29、30、[^71]、[^21]。基于这样一种直觉：残差更小的对应关系更可能成为内点（可从 31 与 [^20] 推断），我们设计了一种特殊的灵活阈值策略，该策略与迭代模型估计与残差计算框架协同工作，智能地持续寻找低残差对应关系并改进变换模型，最终得到的鲁棒估计器 ROFT 可以直接 operate 与任何标准的简单非最小化 PCR 求解器配合使用，并迅速剔除异常值（这里，简单求解器指仅在无异常值条件下工作的求解器，非最小化求解器则指能接受任意数量对应关系作为输入的求解器）。
在完全引入 ROFT 之前，我们首先需要确定用于估计变换参数的非最小化简易 PCR 求解器。由于我们的鲁棒求解器通过迭代运作，我们假设在第 t 次迭代中，当前对应集合为 {\mathcal {L}}^{t}。对于未知尺度的 PCR，我们首先基于 [^24] 中的尺度估计方法求解尺度。
\begin{equation*} {s^{t}}=\underset {s}{\arg \min } \sum _{j,k \in {\mathcal {L}}^{t}}\left ({{\frac {s_{jk}-s}{\zeta _{jk}}}}\right )^{\!\!2}=\frac {\sum _{j,k \in {\mathcal {L}}^{t}} \frac {1}{\zeta _{jk}^{2}}\cdot s_{jk}} {\sum _{j,k \in {\mathcal {L}}^{t}} \frac {1}{\zeta _{jk}^{2}}} \tag {6}\end{equation*}
where \zeta _{jk}={2\tau }/{\|\boldsymbol {p}_{j}-\boldsymbol {q}_{k}\|_{2}} 和 j\neq k. 在 s^{t} 求解后，我们可以使用 Arun 的最小二乘法 32（也称为使用 SVD 进行旋转估计和基于质心的方程进行平移估计）来计算旋转和平移。
算法 5：SUCOM 的灵活阈值化
输入:
点云 \mathcal {P}=\{\boldsymbol {p}_{i}\}_{i=1}^{N}，点云 \mathcal {Q}=\{\boldsymbol {q}_{i}\}_{i=1}^{N}，噪声上界 \tau =c\cdot \sigma，最小超核心大小 K_{min};
输出:
最优变换模型 \mathcal {M}^{\star } 和最终内点集合 \mathcal {L}^{\star };
1
对于 已知尺度 PCR，基于 (1) 构建兼容矩阵 A；对于未知尺度 PCR，构建兼容矩阵：\mathbf {A}\leftarrow \textit {GOGUR}(\mathcal {P},\mathcal {Q},\tau ,K_{min});
2
获得净化后的对应集合：\mathcal {L}\leftarrow \textit {SUCOM}(\mathbf {A},K_{min});
3
优化净化后的对应集合并计算最优变换模型和内点集合：(\mathcal {M}^{\star } , \mathcal {L}^{\star }) \leftarrow \textit {ROFT}(\mathcal {P},\mathcal {Q},\tau ,\mathcal {L});
4
返回 \mathcal {M}^{\star } 和 \mathcal {L}^{\star };
然后，令 {\mathcal {M}}^{t}=(s^{t},\mathbb {R}^{t},\boldsymbol {t}^{t}) 表示当前变换模型（已知尺度 PCR 为 s^{t}=1）。我们可以根据此模型 {\mathcal {M}}^{t} 对每个对应计算残差误差，使得
\begin{equation*} r^{t}_{i}=r^{t}_{i}\left ({{{\mathcal {M}}^{t},\mathcal {P},\mathcal {Q}}}\right )=\left \|{{ s^{t} \mathbf {R}^{t} \boldsymbol {p}_{i} +\boldsymbol {t}^{t} - \boldsymbol {q}_{i} }}\right \|_{2}, \quad i\in \left [{{N}}\right ] \tag {7}\end{equation*}
where [N]=\{1,2,3,\ldots ,N\}。使用上述非最小化求解器，我们可以在算法 4 中呈现我们的鲁棒估计器 ROFT。
a) 行 1 和 2:
第一步是设置初始参数，包括最大迭代次数 t_{\max } = 100 和最小阈值比率 \gamma = 0.1，然后我们在第一次迭代中使用 SUCOM 获得的经过净化的对应集 \mathcal {L} 初始化对应集。
b) 第3–8行和第14行:
该框架的第一部分会在估计变换模型和用该模型计算残差误差之间迭代交替。在每一次迭代（假设为迭代 t）中，我们首先使用当前对应集 {\mathcal {L}}^{t} 根据 Arunas 方法 33 和 (6)（若 PCR 为未知比例）估计变换模型 {\mathcal {M}}^{t}，然后根据 (7) 用当前模型 {\mathcal {M}}^{t} 计算相对于所有对应集 i\in [N] 的残差误差 r_{i}^{t}。这个迭代过程一直持续到收敛，即在连续两次迭代中残差和的收敛（\lt 1e-6），如第6行所示。
c) 第9–13行:
这里是我们灵活阈值设定步骤，作为该框架的第二部分。我们的灵活阈值设定包含两种潜在策略，可根据残差情况灵活使用。第一种是将所有残差误差不超过内点阈值 \tau 的对应点作为对应集 \mathcal {L}^{t+1} 用于下一次迭代。在低离群点场景下，这种策略通常效果良好，因为一些显著的内点会出现较小的残差，并被选入下一次迭代的模型估计。然而，当离群点比例升高时，残差不超过 \tau 的对应点会变得稀疏，不足以进行准确的模型估计。在这种情况下，我们准备了一个“备份”阈值设定策略，如果合格对应点的数量小于 \gamma \cdot N，该策略将被激活。该策略是直接按升序排序残差误差，并挑选与前 \lceil \gamma \cdot N \rceil 个残差相关的对应点（其中 \lceil \cdot \rceil 表示上取整函数）。在此，我们始终将最小阈值比例设为 \gamma =0.1，因为我们已经用多个 \gamma 值（从 0.01 到 0.5）进行了测试，经验发现 \gamma =0.1 能实现最高的整体鲁棒性（过小或过大的 \gamma 值只会削弱鲁棒性）。通过这种方式，下一次迭代的对应集 \mathcal {L}^{t+1} 至少包含 0.1N 个对应点（所有潜在对应点的 10%），这些点要么残差不大于 \tau，要么是前 \lceil \gamma \cdot N \rceil 个最小残差对应点。总之，所采用的灵活阈值设定范式能够成功确保每次迭代中选取足够数量的残差足够小的对应点进行模型估计。
直观上，我们的鲁棒估计器 ROFT 能够在存在离群点的情况下，通过迭代净化残差较小的内点对应关系集，有效地逼近并最终达到最优变换模型。在第 V-D1 节中，我们将展示 ROFT 作为独立的鲁棒 PCR 求解器（甚至不与 SUCOM 一起工作）时，能够容忍多达 80% 的离群点，并且通常在 2–10 次迭代内收敛，比其他非最小鲁棒估计器（如 GNC [^20]、FGR [^19] 和 ADAPT [^21]）显著更快，显示出其优越性能。 此外，当 ROFT 在 SUCOM 之后运行（后者将离群点比例降低至 ≤10%）时，在第 V-D3 节中显示 ROFT 仅需 2–3 次迭代即可收敛，极大地加速了 SUCOM 之后的对应关系细化过程。
E. 完整算法展示
在本节中，我们总结了用于鲁棒已知尺度和未知尺度 PCR 的完整算法 SUCOFT。伪代码展示在算法 5 中。
我们的流程按顺序包括：1）构建兼容矩阵 A（使用已知尺度 PCR 的配对刚性条件 (1)，或在未知尺度 PCR 中调用 COGUR）；2）通过调用 SUCOM 求解最大超核心以获得净化后的对应关系集 \mathcal {L}；3）通过调用 ROFT 估计最优变换 \mathcal {M}^{\star } 以及最终内点集 \mathcal {L}^{\star }。
第 V 节 实验
在本节中，所有实验都在 MATLAB 中使用单线程在配备 i9-12900H CPU 和 32 GB RAM 的笔记本电脑上实现。
我们使用的估计误差评估指标如下（下标 gt 表示真实值）：
- 旋转误差 (RE)（以等距测地距离 34 衡量）
\begin{equation*}\text {RE}=\left |{{\arccos \left ({{\left ({{{\text {tr}}\left ({{{\mathbf {R}^{\star }}^{\top } \mathbf {R}_{\text {gt}}}}\right )-1}}\right )/2}}\right )}}\right |\cdot \frac {180}{\pi }\end{equation*}
以度为单位。
- 平移误差 (TE)（以 L2-范数衡量）
\begin{equation*}\text {TE}=\left \|{{\boldsymbol {t}^{\star }-\boldsymbol {t}_{\text {gt}}}}\right \|_{2}\end{equation*}
以米为单位。
- 缩放误差 (SE) 对于未知尺度 PCR 问题（以绝对误差衡量）
\begin{equation*}\text {SE}=\left |{{s^{\star }-s_{\text {gt}}}}\right |.\end{equation*}
此外，为了更全面地评估室外和室内扫描配准真实世界实验中的 PCR 错误，我们进一步采用注册点的均方根误差 (RMSE)，使得
\begin{equation*}\text {RMSE}=\sqrt {\frac {1}{\left |{{{\mathcal {I}}_{\text {gt}}}}\right |}\sum _{i\in {\mathcal {I}}_{\text {gt}}} \left ({{s^{\star }\mathbf {R}^{\star }\boldsymbol {p}_{i}+\boldsymbol {t}^{\star }-\boldsymbol {q}_{i}}}\right )^{2}}\end{equation*}
以米为单位测量，集合 {\mathcal {I}}_{\text {gt}} 表示地面真值内点对应集（满足 \|s_{\text {gt}}\mathbf {R}_{\text {gt}}\boldsymbol {p}_{i} + \boldsymbol {t}_{\text {gt}} - \boldsymbol {q}_{i}\|_{2}\leq \tau , \forall i\in {\mathcal {I}}_{\text {gt}}）。此外，在 3DMatch [^41] 和 3DLoMatch [^43] 数据集的室内扫描配准实验中，我们还采用配准召回率 (RR) 作为额外的评估指标（类似于 35），其中成功配准的准则定义为：\text {RE}\leq 15^{\circ }、\text {TE}\leq 0.3~\text {m}、\text {RMSE}\leq 0.4~\text {m}（加上 \text {SE}\leq 0.1 用于未知尺度 PCR）。
对于内点阈值（噪声边界）\tau 的设置，我们对所有已知尺度 PCR 实验统一设置 \tau =3.5\sigma（c=3.5），对所有未知尺度 PCR 实验统一设置 \tau =4\sigma（c=4）。
A. 基准测试标准数据集
我们采用来自斯坦福3-D扫描存储库的 bunny 和 armadillo 点云模型 36，以彻底基准测试所提出的 SUCOFT 与其他最先进的鲁棒 PCR 求解器在已知尺度和未知尺度场景中的性能。
1) 用于基准测试的求解器:
我们列出以下最先进的 PCR 求解器以进行比较。
对于已知尺度的 PCR:
GNC-TLS 和 GNC-GM [^20]: 两个非最小化基于 M-估计的鲁棒估计器；我们将更新控制参数设置为 \mu =1.4（与 [^20] 中相同），并将最大迭代次数设为 1000。
ADAPT [^21]: 一个最大一致性非最小化求解器；我们按默认值设置所有参数（与 [^21] 中相同），并将最大迭代次数设为 1000。
FGR [^19]: 一个基于高斯-牛顿优化和 Geman-McClure 损失函数的稳健 PCR 求解器；我们将退火速率设为 0.5（每次迭代中为 \mu \leftarrow \mu /2），并将最大迭代次数设为 1000。
RANSAC 37: 一个经典的稳健估计启发式；我们使用 Horn’s 方法 38 作为子集大小为 3 的最小解算器，并使用 Arun’s 方法 39 作为共识集优化的非最小解算器；我们将置信度设为 p=0.99，并将最大迭代（采样）次数设为 10000。
FLO-RANSAC [^47]: 在 RANSAC 的基础上添加加速局部优化策略的一种变体；我们默认按 [^47] 中的设置来配置所有参数，并将最大迭代（采样）次数设为 10000。
GORE 40 和 GORE + FLO-RANSAC: 一个基于 BnB 的保证最优 PCR 方法，此外还有在 GORE 之后对剩余对应集应用 FLO-RANSAC 的鲁棒化版本。
TEASER [^24]: 一个基于最大团的稳健 PCR 解决方案；由于其全局最优版本运行速度过慢，我们采用了 [71, Sec. X] 中的 GNC 版；我们在最大团后采用 GNC-TLS 对对应关系进行细化，并在最大团算法中使用 41。
RANSIC [^30]: 一个基于不变量的稳健 PCR 求解器，适用于已知尺度和未知尺度的 PCR；所有参数均默认按 [^30] 源代码中的设置。
TriVoC [^54]: 一个基于投票与排序的稳健 PCR 算法；所有参数均默认按 [^54] 源代码中的设置。
SC2-PCR 42: 一个使用两阶段采样和局部光谱匹配的二阶兼容性 PCR 方法；我们将种子数量设为 0.2N，并将采样数设为 K_{1}=30 和 K_{2}=15。
MAC [^26]: 基于图的鲁棒 PCR 方法，使用二阶兼容性和最佳（误差最低）最大团来拒绝离群点；实现细节上，我们采用节点引导团选择、均方误差（MAE）（作为 RANSAC 指标）以及常规 SVD，因为根据 [^26]，该版本可能获得最佳性能。
GROR [^76]: 一个鲁棒 PCR 求解器，将旋转估计拆解为 1-DOF 与 2-DOF 几何问题，以实现一致性最大化；请注意，由于原始版本在 MATLAB 的低离群点情形下运行缓慢（因为太多对应对被纳入一致性最大化的迭代中），我们随机化边对选择过程，并像 RANSAC 一样强加收敛条件来加速算法。
CLIPPER [^22]: 一个快速近似最大团求解器，随后使用 GNC-TLS 来估计最优变换；所有参数均按 [^22] 源代码默认设置。
对于未知尺度的 PCR:
GNC-TLS and GNC-GM: 与已知尺度版本相同。
ADAPT: 与已知尺度版本相同。
RANSAC: 与已知尺度版本相同。
FLO-RANSAC: 与已知尺度版本相同。
RANSIC: 与已知尺度版本相同。
1-Point RANSAC [^29]: 一个解耦的鲁棒 PCR 算法，使用单点 RANSAC 计算尺度与平移，并采用尺度退火双重权重方法求解旋转；所有参数均按 [^29] 源代码默认设置。
对于我们的求解器 SUCOFT，我们设置了 K_{\min }=(0.01N - 1)，目标是处理多达 99% 的离群点。
2) 设置:
对于每个点云模型（bunny 和 armadillo），我们的基准测试在 30 次 Monte Carlo 运行中进行。在每一次运行中，点云被缩放为一个 1 \times 1 \times 1‑m 的立方体，并下采样到 N=1000，作为源点集 \mathcal {P}。随后，我们使用随机生成的变换（条件为：\|\boldsymbol {t}_{\text {gt}}\|\in (0,5]~\text {m}，以及 s_{\text {gt}}\in (1,10] 用于未知尺度 PCR）来变换 \mathcal {P}，并用随机高斯噪声 \sigma =0.005~\text {m} 损坏变换后的点，得到带噪声的目标点集 \mathcal {Q}。为创建类似真实场景的异常点，我们将 \mathcal {Q} 中的一部分点替换为靠近点云表面的随机 3-D 点，如图 5 所示。请注意，我们的异常点设置比之前的工作 [^22]、[^30]、[^24] 更具挑战性，因为内点和异常点更加“混杂”（都接近表面），更难以区分，从而使鲁棒求解器更容易失败。随后，我们将这些带噪声和异常点扰乱的对应关系输入 PCR 求解器并跟踪性能。
Fig. 5. 我们的 PCR 基准实验设置演示。绿色和红色线分别表示内点和异常点。(a) 已知尺度下 90% 异常点。(b) 未知尺度下 99% 异常点.
基准结果以箱线图方式展示在 Fig. 6（已知尺度 PCR）和 Fig. 7（未知尺度 PCR）中，统计数据基于对 bunny 的 30 次 Monte Carlo 运行以及对 armadillo 的 30 次 Monte Carlo 运行（总计 60 次运行）。
Fig. 6. 已知尺度 PCR 在 bunny 和 armadillo 上的基准测试，以 N=1000 对抗不断增加的异常点比例。(a) 低异常点比例下的估计误差。(b) 极端异常点比例下的估计误差。(c) 所有异常点比例下的平均运行时间.
Fig. 7. 未知尺度 PCR 在 bunny 和 armadillo 上的基准测试，以 N=1000 对抗不断增加的异常点比例。(a) 低异常点比例下的估计误差。(b) 极端异常点比例下的估计误差。(c) 所有异常点比例下的平均运行时间.
结果分析: 就如 Fig. 6 所示的已知尺度 PCR 结果而言，我们可以观察到：1) 非最小化求解器：GNC、ADAPT、FGR 以及 RANSAC 和 FLO-RANSAC 在极端外点情况下全部失败，表现出有限的鲁棒性；2) CLIPPER 在 98%–99% 的外点时失效（由于其非保证的最大团估计机制）；3) SC2-PCR 在 99% 时变得脆弱（因为当外点比例很高时，所选的种子对应关系会被破坏）；4) TriVoC 和 RANSIC 在 99% 时也会得到少量错误结果（因为局部最优可能主导它们的最大共识集）；5) GORE、GORE + FLO-RANSAC、GROR 以及我们的 SUCOFT 是唯一能够容忍高达 99% 外点的求解器。 在已知尺度 PCR 上进行时间效率基准测试时，我们发现：所有 99% 鲁棒的求解器都比我们的 SUCOFT 慢，这意味着，换句话说，所有比 SUCOFT 更快的求解器无法拥有同样的鲁棒性。 此外，SUCOFT 的运行时间几乎与外点无关（几乎不受外点比例增加的影响），这在实际应用中是一个非常理想的特性。 因此，公平地说，我们的 SUCOFT 在已知尺度 PCR 上展示了最先进的整体性能。
就如 Fig. 7 所示的未知尺度 PCR 结果而言，我们可以推断出：1) GNC、ADAPT、RANSAC 以及 FLO-RANSAC 在极端外点 regime 下失去了鲁棒性；2) 1 点 RANSAC 在 96%–97% 的外点时开始失败（原因见下文）；3) 仅 RANSIC 和我们的 SUCOFT 能够准确处理 99% 的外点，而 SUCOFT 在 99% 时几乎比 RANSIC 快一个数量级。 虽然 SUCOFT 在较低外点比例时似乎比某些求解器慢，但它仍以 99% 鲁棒的求解器身份，在未知尺度问题上表现出更好的效率和更少的外点无关计算时间，超越其他竞争者。
请注意，1点RANSAC在极端异常值案例中脆弱的主要原因在于：由于1点RANSAC策略分别用于尺度估计，而旋转和平移估计在很大程度上依赖于尺度估计，1点RANSAC找到的最大一致性对应的尺度实际上与完整变换模型（该模型不仅包含尺度，还包含旋转和平移）对应的最大一致性是独立的。因此，这种“伪”子最优尺度可能导致旋转和平移的错误估计，尤其是在高异常值比例导致更子最优尺度在所有潜在尺度中占优时。
B. 实际应用：户外激光扫描配准
我们在户外激光扫描配准的真实世界应用问题上测试了所提出的求解器SUCOFT。我们采用了著名的ETH数据集 [^77]，该数据集包含五个不同真实场景的多幅LiDAR扫描：Arch、Courtyard、Facade、Office和Trees。此外，我们还采用了WHU数据集 43，该数据集包含11个不同场景的真实激光扫描，并在实验中使用了七个场景，包括：Campus、Heritage Building、High-Speed Railway、Park、Residence、Tunnel和Mountain。
为减轻计算负担，我们首先对ETH数据集的点云（激光扫描）使用0.1 m体素网格进行下采样，对WHU数据集使用0.2 m。为生成潜在对应关系，我们首先应用ISS [^16]检测关键点，然后使用FPFH [^15]描述符匹配特征并在扫描间建立对应关系。除了常规已知尺度的PCR之外，我们还在特征检测与匹配步骤之前，使用随机尺度 s\in (1,5]对目标激光扫描进行缩放，以生成未知尺度的配准问题进行测试。
更为详细的信息（例如扫描仪设备、平均对应数和平均离群率）关于 ETH 和 WHU 数据集分别在表 I(a) 和 (b) 中给出。我们可以注意到：在 ETH 数据集的 Arch 和 Trees 场景以及 WHU 数据集的 Campus、High-Speed Railway 和 Residence 场景中，已知尺度和未知尺度问题的平均离群率都高达约 99%，同时平均对应数大约在 800–3000 之间（鉴于如此高的离群率，这似乎并不充足），这将为 PCR 求解器正确注册激光扫描提供相当具有挑战性的条件。此外，即使在相对低离群率的场景如 Facade、Heritage Building 和 Tunnel 中，平均对应数也变得更稀疏（例如仅数百），这也会显著增加成功注册的难度，因为真正内点的数量仍然相当少。
表 I
为与 SUCOFT 进行完整比较，我们在已知尺度配准中采用 FGR、FLO-RANSAC、GORE + FLO-RANSAC、TEASER、TriVoC、MAC 和 GROR，在未知尺度配准中采用 GNC-TLS、FLO-RANSAC、RANSIC、1-point RANSAC。关于 SUCOFT 的设置，我们设定 K_{\min }=(0.005N-1)，考虑到某些场景中的离群点可能非常高。
ETH 和 WHU 数据集的定量结果分别报告在图 8 和图 9 中。请注意，对于估计误差，我们直接使用箱线图展示整体场景的拼接结果；而对于运行时间，我们分别使用条形图报告每个场景的平均运行时间。此外，这两个数据集的定性结果补充在图 10（已知尺度情况）和图 11（未知尺度情况）中，能够具体展示不同 PCR 方法在每个场景中的配准结果。
图 8. 对 ETH 数据集（[62]）的已知尺度和未知尺度激光扫描配准（PCR）问题的定量结果。请注意，运行时间表示针对每个场景的平均运行时间。(a) 已知尺度 PCR。(b) 未知尺度 PCR.
图 9. 在 WHU 数据集 [17] 上已知尺度和未知尺度激光扫描配准（PCR）问题的定量结果。请注意，运行时间表示相对于每个场景的平均运行时间。(a) 已知尺度 PCR。(b) 未知尺度 PCR.
图 10. 在 ETH [62] 和 WHU [17] 数据集上已知尺度激光扫描配准（PCR）问题的定性结果。
图 11. 在 ETH [62] 和 WHU [17] 数据集上未知尺度激光扫描配准（PCR）问题的定性结果。
根据图 8(a)（ETH 数据集上的已知尺度案例），我们可以看到：我们的 SUCOFT 以及 GORE + FLO‑RANSAC、TEASER、TriVoC 和 GROR，能够稳健且精确地完成所有估计；然而，在图 9(a)（WHU 数据集上的已知尺度配准）中，TEASER、GROR 和 TirVoC 在一些场景中产生零星失败结果，而我们的 SUCOFT 在所有测试中仍保持稳定的鲁棒性。就平均运行时间而言，SUCOFT 是在大多数场景中表现出最短时间的求解器。这些已知尺度测试充分验证了 SUCOFT 在实际问题中具有高度鲁棒性以及卓越的时间效率。
基于图 8(b) 和 9(b) 中的未知尺度结果，我们可以观察到：SUCOFT 是唯一能够稳健解决两个数据集中所有场景的未知尺度配准问题的求解器。GNC‑TLS、FLO‑RANSAC 和 1‑point RANSAC 产生大量错误估计，而 RANSIC 则返回若干失败估计。此外，SUCOFT 的平均运行时间在大多数场景中低于 RANSIC，这进一步验证了 SUCOFT 在未知尺度 PCR 中的卓越效率。
C. 实际应用：室内扫描配准
我们使用 3DMatch 数据集 [^41] 以及 3DLoMatch 数据集 [^43] 对真实世界室内扫描配准应用评估 SUCOFT，在其中我们可以找到不同室内场景中由 RGB‑D 摄像头捕获的多序列 3‑D 扫描。请注意，3DMatch 数据集中成对扫描之间的重叠比例通常不低于 30%，而 3DLoMatch 数据集中的重叠比例显著更低，范围从 10% 到 30%（根据 [^43]），因此可以在此测试中创建大量极端离群比例的配准问题。在我们的实验中，我们直接使用 FPFH 来描述特征并匹配跨扫描的潜在对应关系。我们还通过随机尺度 s\in (1,5] 对目标点云进行重采样，以生成未知尺度的测试问题。我们为 SUCOM 设置 K_{\min }=(0.01N-1)，因为对应关系的数量通常比户外场景更少，所以最小内点比例应该提高。
这两个数据集上的定量结果如表 II（3DMatch 数据集）和表 III（3DLoMatch 数据集）所示，其中估计误差、RMSE 和时间均为平均结果。与此同时，定性示例结果在图 12 中展示（包括两个数据集上的已知尺度和未知尺度情况）。我们可以得出以下结论：1）对于已知尺度配准，我们的 SUCOFT 展示了最佳整体性能，特别是表现出最高的 RR、最低的 TE、最低的 RE 之一、最低的 RMSE 之一以及最先进的时间效率；2）对于未知尺度配准，SUCOFT 在两个数据集上成功超过了所有其他比较求解器，表现出最高的 RR、最低的估计误差以及最快的运行时间。因此，我们可以发现 SUCOFT 能够高效且准确地解决即使在低重叠比例下的真实世界扫描配准问题。
表 II
表 III
Fig. 12. 对已知尺度和未知尺度扫描配准（PCR）问题的定性结果，涵盖 3DMatch [74] 和 3DLoMatch [31] 数据集，其中前三行是 3DMatch，后三行是 3DLoMatch.
D. 消融研究
在本节中，我们基于斯坦福的 bunny 和 armadillo 点云模型，采用与基准实验相同的设置，进行更具体的消融研究。
1) ROFT在鲁棒估计中的性能:
由于 ROFT 本身可以作为一个鲁棒估计器直接去除离群值，我们有兴趣在不同方面评估它在鲁棒离群值拒绝（已知尺度 PCR）中的性能，并将其与其他最先进的鲁棒 PCR 估计器进行比较。基于对 bunny 进行 20 次实验以及对 armadillo 进行 20 次实验，离群率从 10% 增加到 90%，我们绘制了相应的估计误差和迭代次数在 Fig. 13 中。我们用于比较的非最小解算器是 GNC-TLS、GNC-GM、ADAPT 和 IMOT，它们都设置为最大迭代 100 次，我们还包括 RANSAC（最大 100 次迭代，以保证公平）进行比较。
Fig. 13. 对比其他鲁棒估计器，关于已知尺度和未知尺度 PCR 的 ROFT 鲁棒性消融研究。(a) 已知尺度 PCR。(b) 未知尺度 PCR.
根据结果，我们可以观察到 ROFT 本身对多达 80% 的离群值具有鲁棒性，与 GNC、ADAPT 和 IMOT 一致，并优于在 80% 时失效的 RANSAC (100)。此外，ROFT 与 IMOT 一起显示了在 10%–80% 迭代中收敛所需迭代次数最少。这充分证明 ROFT 作为 PCR 的鲁棒估计器，兼具高效性和鲁棒性。因此，它一定能很好地与 SUCOM 一起工作，精炼纯净对应集，成为 SUCOFT 算法的最终步骤。
2) SUCOM 的离群值去除:
我们还评估了 SUCOM 方法（即 SUCOM 算法）在我们的 SUCOFT 求解器中的异常值剔除效果。Fig. 14 显示了在已知尺度和未知尺度情况下，使用 SUCOM 对潜在对应关系前后的异常值比例。请注意，Fig. 14 基于在 bunny 上进行的 20 次 Monte Carlo 运行以及在 armadillo 上进行的另外 20 次运行。i 我们可以观察到，在 20%–98% 的异常值比例下，SUCOM 能够删除所有异常值并保留纯内点集。即使在 99% 异常值的情况下，SUCOM 之后的净化对应集中的异常值也不超过 10%。这证实了 SUCOM 在为 PCR 问题剔除大部分异常值方面的有效性。
Fig. 14. 已知尺度和未知尺度 PCR 下 SUCOM 前后异常值比例的消融研究.
3) ROFT 在 SUCOFT 中的迭代次数:
随后，我们深入探讨 ROFT 作为 SUCOFT 子程序的收敛效率。在基准环境中，在使用 SUCOM 获得净化后的对应集后，我们记录了 ROFT 在对应关系细化过程中收敛所需的迭代次数，结果显示在 Fig. 15（基于在 bunny 上进行的 20 次运行以及在 armadillo 上进行的 20 次运行）。
Fig. 15. 已知尺度和未知尺度 PCR 下 SUCOM 后 ROFT 迭代次数的消融研究.
从结果来看，我们可以看到 ROFT 在所有 20% 至 99% 的异常值比例下都能在 2–3 次迭代内迅速收敛。其背后的原因有两点：1）在 Section V-D2 中测试的 SUCOM 之后，异常值比例通常相当低，因此 ROFT 可以快速并迅速收敛到最优解；2）即使作为一个鲁棒估计器本身，ROFT 也非常高效，不需要太多迭代即可达到收敛，后文将在 Section V-D1 讨论。
SECTION VI. 结论
本文提出了一种快速且高度鲁棒的估计方法 SUCOFT，适用于已知尺度和未知尺度的 PCR。通过引入 K-supercore 及最大 supercore 并将其与最大 clique 和 k-core 进行比较，我们提出了一个快速、保证收敛的 SUCOM 求解器 SUCOM，用以处理已知尺度 PCR，采用基于修剪的 K-supercore 检测策略。该框架同样扩展到未知尺度鲁棒 PCR，通过为未知尺度问题发明一种新的兼容图构建方法。我们进一步引入了一种新颖、简单但高效的鲁棒 PCR 估计器 ROFT，能够自行拒绝多达 80% 的离群点，以细化对应关系并在 SUCOM 之后获得真实内点。对标准基准和真实数据应用（包括户外和室内扫描配准）的实验表明，所提出的方法可容忍超过 99% 的离群点，并实现了（至少）最先进的性能。
关于所提出方法 SUCOFT 的局限性，主要局限在于：其成功取决于 SUCOM 所获得的最大 supercore。因此，如果离群点能够形成一个比所有真实内点所构成的 supercore 更大的 supercore，则 SUCOM 所寻找的最大 supercore 将不再包含足够的真实内点，进而会破坏 SUCOFT 的最终估计结果（根据算法 5）。
未来的工作可以聚焦于将我们基于兼容性的 SUCOM 框架推广到其他摄影测量或计算机视觉问题。我们的演示源代码可在以下位置获取：https://github.com/LeiSun-98/SUCOFT-master.