中央化基于 RANSAC 的点云配准，快速收敛且高精度
摘要
针对点云配准，本文旨在提出一种新的集中式随机抽样一致性（RANSAC）(C-RANSAC)注册方法，具有快速收敛和高精度。 在我们的算法中，创新点包括：首先，提出基于尺度直方图的异常值剔除方法，从初始线向量集 \mathbf {L} 中删除异常值，以构造精简后的线向量集 \mathbf {L}_{\text{red}}；其次，主机 RANSAC (H-RANSAC) 仅在 L 上工作，与仅在 \mathbf {L}_{\text{red}} 上工作的局部 RANSAC (LCL-RANSAC) 之间进行握手合作；第三，在每一次握手过程中，LCL-RANSAC 在收到来自 H-RANSAC 的全局配准解和全局迭代次数 x_{H} 后，将接收到的全局解作为改进版 TEASER++ (M-TEASER++) 方法的初始解，计算其第一局部配准解。 如果第一局部配准解满足全局迭代次数继承条件，LCL-RANSAC 将累积的迭代次数 x_{H} + 1 以及第一局部解直接返回给 H-RANSAC；否则，LCL-RANSAC 使用 M-TEASER++ 方法迭代细化其局部解，然后将得到的局部解和所需的局部迭代次数 x_{\text{LCL}} 发送给 H-RANSAC，以更新全局解、全局迭代次数至 x_{H} := x_{H} + x_{\text{LCL}} 以及全局置信度。 由于 |L_{\text{red}}| \ll |L| 并将全局迭代次数继承条件测试融入我们的算法，我们已在测试点云对上开展了广泛实验，展示了本算法相较于最先进方法在配准精度和执行时间方面的优势。
作者
Kuo-Liang Chung 计算机科学与信息工程系，台湾科技大学，台北，台湾 ORCID: 0000-0002-0946-7948
Wei-Tai Chang 计算机科学与信息工程系，台湾科技大学，台北，台湾 ORCID: 0009-0006-9083-9361
出版信息
期刊： IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing 年份： 2024 卷号： 17 页码： 5431-5442 DOI： 10.1109/JSTARS.2024.3365516 文章编号： 10433649 ISSN： 打印 ISSN: 1939-1404，电子 ISSN: 2151-1535
指标
论文引用： 7 总下载量： 1290
资助
- 台湾科学技术部 (资助号: MOST-111-2221-E-011-126- MY3)
关键词
IEEE关键词： 点云压缩, 估计, 收敛, 迭代方法, 特征提取, 鲁棒性, 三维显示
索引词： 点云, 更快收敛, 收敛精度, 点云配准, 置信水平, 全局解, 局部解, 异常值剔除, 全局测试, 配准精度, 全局数目, 随机采样一致性, 实验设计, 均方根误差, 随机采样, 性能精度, 可比精度, 估计问题, 迭代最近点, 点源, 对应点, 配准方法, 精度指标, 配准问题, 交叉验证均方根误差, 尺度误差, 一致性集合, 旋转误差
作者关键词： 执行时间, 线向量集, 异常值剔除, 点云配准 (PCR), 随机采样一致性 (RANSAC), 配准精度
SECTION I. 引言
3D 扫描技术，例如激光探测与测距扫描技术和结构光 3D 扫描仪，可以提供精确的几何信息，并已广泛应用于遥感 1, 2, 3, 4, 5 以及 3D 视觉 6, 7, 8。 为了生成多视角点云所能覆盖的完整场景，解决源点云集与目标点云集之间的点云配准（PCR）问题既具有挑战性又十分重要。 PCR 的目标是确定矩阵变换，包括尺度、旋转和平移，以对齐点集，同时考虑点数据采集过程中的噪声和变化，使不同扫描中对应点之间的差异最小化。 为了解决 PCR 问题，常用的技术包括基于迭代最近点（ICP）的方式 9 以及基于随机样本一致性（RANSAC）的方式 10。 Feng 等人 11 对遥感配准的最前沿方法进行了系统而全面的综述，这些方法包括基于强度的、基于特征的、基于光流的、基于深度学习的以及混合技术。
A. 相关工作
ICP 在目标点云中交替进行最近点搜索和已对齐源点与最近目标点之间距离最小化迭代，其中四元数方法 12 用于实现该过程。然而，ICP 常常收敛到局部最小值，并且对初始配准结果、离群点、缺失数据和部分重叠敏感，导致收敛缓慢 13。此外，ICP 无法处理点云对之间的尺度变化问题。为为 ICP 提供更好的初始配准结果，提出了主成分分析方法 14。为更好地确定 ICP 中对齐后的源点和相应的目标点，提出了角度不变特征方法 15 和曲率特征相似度方法 16。Super 4-points congruent set (4PCS) 方法 17 引入了一种智能索引机制，以减少 4PCS 方法 18 所需的执行时间。在快速全局配准方法 19 中，首先选择三个刚性对应关系以构建粗略的内点集。随后，渐进非凸性 (GNC) 函数 20、21 以及 Geman-McClure 惩罚函数结合使用高斯-牛顿方法求解变换矩阵。
为减轻ICP中异常值的影响，提出了稀疏ICP方法 22，该方法通过利用诱导稀疏的惩罚函数 23，自适应地为异常值分配权重。为加快ICP中迭代过程的收敛速度，提出了 Anderson 加速方法 24，该方法基于前几次迭代的行为来预测下一步迭代。为解决两个缺点——收敛盆地过小以及对异常值和部分重叠的敏感性，提出了稳健对称ICP 25，其采用对称的点到平面距离度量。在结构良好的环境中，提出了基于平面的方案 26，用于分割平面以进行配准。为改进稀疏ICP方法 27，首先将点到点配准问题转化为一个大化–最小化问题 28。随后使用 Anderson 加速方法来加速其收敛。随后提出了一种基于Welsch函数的误差度量，以提升性能。
与ICP相关方法不同，基于RANSAC的配准方法不需要初始配准解，但它确实需要一个初始对应集，以支持通过子集采样试验进行的迭代假设与验证（HAV）过程。由于实现了良好的配准鲁棒性，RANSAC方法在解决PCR问题方面受到越来越多关注。然而，初始对应集会受到噪声和离群点的影响。特别是当离群点比例高时，往往会导致大量的子集采样试验。快速点特征直方图（FPFH）方法 29 用于提取点的特征描述符。在FPFH中，通过比较这些特征描述符之间的相似性来构造初始对应集，然后采用一种简单称为FPFH+RANSAC的RANSAC方法来估计配准解。基于结合ResNet 30 与 UNet 31 的深度学习框架，首先以快速且节省内存的方式提取每个点的全卷积几何特征（FCGF）[^31]。随后，利用这些特征构建可靠的对应集，然后采用一种简单称为FCGF+RANSAC的RANSAC方法来估计配准解。实验数据表明，FCGF+RANSAC方法比FPFH+RANSAC、3DMatch [^32]和PPFNet [^33]更准确、更快。
Barath 和 Matas [^34] 提出了一种基于 Graph-Cut RANSAC 的配准方法，利用图割过程 [^35]。他们的配准方法考虑了点的空间连贯性，以区分共识集中的正确内点和错误内点，特别是通过在图割过程中局部最小化的能量函数纠正错误估计的内点。实验数据表明，Graph-Cut RANSAC 基础的配准方法既简单又有效。在 [^36] 中，结果显示，平均而言，结合 Graph-Cut RANSAC 与单一模型估计器 [^37]、[^38]，相较于 RANSAC、贝叶斯模型估计方法 [^37]、RANSAC 的通用框架 [^39] 和神经引导的 RANSAC [^40]，能够获得更好的配准结果。
基于给定的直线向量对应集 \mathbf {L}，杨等人 [^41] 提出了一种截断最小二乘估计与半正定松弛（TEASER）方法。随后，杨等人 [^42] 提出了 TEASER 的改进版本，称为 TEASER++。在 TEASER++ 方法中，PCR 问题首先被转化为成本最小化问题。接着，基于图模型，将 PCR 问题分解为尺度估计问题、旋转估计问题和位移估计问题。实验数据显示，TEASER++ 方法优于 RANSAC、分支限界方法 [^43] 以及启发式方法 [^44]。仅考虑旋转和位移估计时，TEASER++ 也优于 Fast-GlobReg 方法 32。为处理高外点率的情况，施等人 [^45] 提出了一种名为基于不变性的拒绝外点（ROBIN）的方法，以提升 PCR 的鲁棒性。与 TEASER++ 中使用的最大团思想不同，ROBIN 采用最大 k-核心思想去除外点，使其准确性与 TEASER++ 竞争，同时加速执行时间。
改进基于拓扑图模型的方法 [^46]，Li 等人 [^47] 首先将 PCR 问题分解为尺度、旋转和位移估计子问题。基于线向量对应集 {\mathbf {L}}，他们提出了一种单点 RANSAC 方法首先估计尺度解。随后，构造的最大一致集用于从 {\mathbf {L}} 中移除离群点。为了估计旋转解，采用尺度退火双权函数、微分技术和加权最小二乘回归方法共同使用。基于估计得到的尺度和旋转解，在投影对应集中的基于频率的潜在内点被获取。最后，估计位移解。实验数据表明，该单点 RANSAC 方法优于 FLORANSAC [^48]、K4PCS [^49]、TEASER++ [^42] 和 FMP+BnB [^50]。
与拒绝离群点的图论方法 [^45] 不同，Sun [^51] 提出了随机采样与不变性兼容性（RANSIC）方法。在 RANSIC 中，利用不变性与兼容性理论从初始对应集 \mathbf {C} 中提取内点候选，然后通过比较每个新候选（由三个对应组成）与所有旧候选之间的兼容性来确定一致集。上述迭代随机采样过程会重复进行，直至满足终止条件。实验结果表明，RANSIC 方法优于 Fast-GlobReg 33、GNC-TLS [^44]、基于奇异值分解的 RANSAC 方法 [^52]、保证离群点移除（GORE）方法 [^53] 和 TEASER [^41]。最近，基于两层随机采样操作，提出了一种双层采样与一致性最大化求解器，称为 DANIEL [^54]，在高离群率下实现了低计算成本和高鲁棒性。实验数据证明了 DANIEL 相比 GNC-TLS [^44] 与 GORE [^53] 的优越性。
B. 贡献
本文提出了一种新的集中式 RANSAC（C-RANSAC）配准算法，具有快速收敛和高精度的特点。我们的 C-RANSAC 配准算法的流程如图 1 所示，其中宿主 RANSAC（H-RANSAC）与局部 RANSAC（LCL-RANSAC）以握手方式协作。为阐明我们算法的新颖性与贡献，图 1 中各模块的功能说明如下。
图 1. 我们的 C-RANSAC 配准算法流程图.
在我们算法的第一个创新点中，提出了一种基于尺度直方图的异常值剔除方法，用以从初始线向量集 \mathbf {L} 中删除异常值，构造具有 |\mathbf {L}_{\text{red}}| \ll |\mathbf {L}| 的简化线向量集 \mathbf {L}_{\text{red}}。
与传统 RANSAC 方法不同，我们的 C-RANSAC 配准算法的第二个创新点是存在两个 RANSAC，H-SANSAC 与 LCL-RANSAC。H-SANSAC 在集合 \mathbf {L} 上工作，LCL-RANSAC 在集合 \mathbf {L}_{\text{red}} 上工作，两者以握手方式协同。
我们算法的第三个创新点是，在从 H‑SANSAC 接收全局配准解 (s, \mathrm{{R}}, t)_{H} 和全局迭代次数 x_{H} 后，LCL‑RANSAC 将 (s, \mathrm{{R}}, t)_{H} 用作改进 TEASER++（M‑TEASER++）方法（该方法将在附录中描述）的初始解，以计算其首个局部配准解 (s, \mathrm{{R}}, t)_{\text{LCL}}。随后，LCL‑RANSAC 检查全局迭代次数继承条件 “(s, \mathrm{{R}}, t)_{\text{LCL}} 接近 (s, \mathrm{{R}}, t)_{H}” 是否成立。若条件成立，则表示首个局部配准解 (s, \mathrm{{R}}, t)_{\text{LCL}} 似乎是通过使用 H‑SANSAC 执行 HAV 过程 x_{H} + 1 次得到的，因此 LCL‑RANSAC 将局部迭代次数设为 x_{\text{LCL}} = x_{H} + 1。此外，LCL‑RANSAC 将 (s, \mathrm{{R}}, t)_{\text{LCL}} 与 x_{\text{LCL}} 发送回 H‑SANSAC。否则，若全局迭代次数继承条件不满足，LCL‑RANSAC 通过 M‑TEASER++ 方法迭代地细化其局部解，最终将得到的局部配准解及局部迭代次数发送给 H‑SANSAC，用于更新全局解、迭代次数和置信度水平。
基于点云数据集：3DMatch [^55] 和 RGB-D [^56]，本文对所考虑的方法进行配准精度和执行时间的比较。使用的四项配准精度指标为尺度误差、旋转误差、平移误差和均方根误差（RMSE）。执行时间以秒为单位测量。综合实验数据证明了我们的 C-RANSAC 配准算法在配准精度和执行时间上的优势，与最先进的方法相比，例如 Graph-Cut RANSAC [^36]、TEASER++ [^42]、one-point RANSAC [^47] 和 RANSIC [^51]。
本文其余部分的组织如下。第二节中提出了基于尺度直方图的异常值移除方法，用以构建一个简化的线向量对应集。第三节介绍我们的 C-RANSAC 算法。第四节展示了详尽的实验结果，以证明我们算法的优越性。最后，第五节对本文进行总结。
第II节. 基于尺度直方图的异常值移除方法
如图 1 所示，提出的基于尺度直方图的异常值移除方法详细说明了如何从初始线向量集 \mathbf {L} 构建简化后的线向量集 \mathbf {L}_{\text{red}}。这两个集合 \mathbf {L} 与 \mathbf {L}_{\text{red}} 分别被 H-RANSAC 与 LCL-RANSAC 用作工作空间。
A. 初始线向量集
给定源点云集 \mathbf {P}^{s}、目标点云集 \mathbf {P}^{t}，以及初始对应集 C = \lbrace (x_{i}, y_{i}) \in \mathbb{R}^{3} \times \mathbb{R}^{3}\ |\ x_{i} \in {\mathbf {P}^{s}}\ {\text{and}}\ y_{i} \in {\mathbf {P}^{t}}\ {{\text{for}}}\ 1 \leq i \leq |{\mathbf {P}^{s}|\rbrace }，PCR 的目标是估计一个正尺度参数 s \in \mathbb{R}、一个正交旋转矩阵 R \in \text{SO}(3) 以及一个平移向量 t \in \mathbb{R}^{3}，使得对齐后的源点云集与原始目标点云集满足
\begin{equation*} \mathop{\text{Min}}\limits_{s, R, t}\sum _{i=1}^{{|{\mathbf {P}^{s}}|}}\ w_{i}||(s\mathrm {R}{\mathit{x_{i}}} + \mathit{t}) - y_{i}||^{2} \tag{1} \end{equation*}
其中 y_{i} 被建模为 y_{i} = s\mathrm{{R}}{{x_{i}}} + {t} + n_{i}，其中 n_{i} 表示受限测量噪声，可假设为零均值高斯噪声 [^42], [^47]。基于初始对应集 \mathbf {C}，很容易构造初始线向量集 \mathbf {L} = \lbrace (v^{x}_{i,j}, v^{y}_{i,j}) \ \text{for} \ 1 \leq i < j \leq |\mathbf {C}|\rbrace，其中 v^{x}_{i,j} = x_{i} - x_{j}、v^{y}_{i,j} = y_{i} - y_{j} 和 |\mathbf {L}| = \frac{|\mathbf {C}|(|\mathbf {C}|-1)}{2}。
B. 构造约简线向量集 \mathbf {L}_{\text{red}}
基于初始线向量集合 \mathbf {L}，我们以一个例子来帮助说明所提出的基于尺度直方图的异常值去除方法，以构建减小的线向量集合 \mathbf {L}_{\text{red}}。Fig. 2(a) 描绘了被标记为蓝色的源点集 \mathbf {P}^{s} 和被标记为绿色的目标点集 \mathbf {P}^{t}，其中 \mathbf {P}^{s} 采用自 “3DMatch” 数据集，该数据集可在网站 https://3dmatch.cs.princeton.edu/ [^55] 上获取，且 \mathbf {P}^{t} 随机变换自 \mathbf {P}^{s}。为模拟异常值及噪声对 \mathbf {P}^{s} 与 \mathbf {P}^{t} 之间对应关系的影响，高斯限值噪声被人为添加到 \mathbf {P}^{t} 中的所有目标点，并且随机平移被人为应用于 \mathbf {P}^{t} 中 90% 的目标点。人工测试点云的详细构建请参见第 IV-A-1 节。在 Fig. 2(b) 中，红色标记的线条表示初始对应关系集合 \mathbf {C}，其 |\mathbf {C}| = 1993，其中 90% 为异常值，且 \mathbf {L} 中初始线向量数等于 1 985 028 \left(= \frac{1993\times 1992}{2}\right)。
图 2. 基于尺度直方图的异常值剔除，用于构建简化的线向量集合 \mathbf {L}_{\text{red}}。 (a) 源点集合 \mathbf {P}^{s} 标记为蓝色，目标点集合 \mathbf {P}^{t} 标记为绿色。 (b) 初始对应集合 C，其中每个对应关系由红线标记。 (c) 初始线向量集合 L 的尺度直方图。 (d) \mathbf {L}_{\text{red}} 的尺度直方图。
考虑每个线向量 (v^{x}_{i,j},\ v^{y}_{i,j}) \in \mathbf {L}，令 s_{i,j} 表示 v^{y}_{i,j} 的欧几里得长度相对于 v^{x}_{i,j} 的正比例尺度，即 s_{i,j}={\frac{\Vert v^{y}_{i,j}\Vert }{\Vert v^{x}_{i,j}\Vert }}。图 2(c) 显示了图 2(b) 中所有线向量的尺度集合的尺度直方图，其中在尺度直方图 \mathbf {H}(s) 中，x 轴表示尺度参数 s，y 轴表示 s 的频率。在图 2(c) 中，x 轴上有 25 个量化尺度，每个量化尺度及其对应的频率构成一个宽度为 0.2 的箱。
为去除 \mathbf {L} 中的离群值，我们保留了峰值最高的箱以及其左右相邻箱中的线向量，用以构建缩减后的线向量集 \mathbf {L}_{\text{red}}。图 2(d) 展示了缩减后的尺度直方图，其中它使得 \mathbf {L}_{\text{red}} 与 |\mathbf {L}_{\text{red}}| = 411305 产生对应关系。对于本例，线向量集 \mathbf {L} 的离群值去除率为 79.3% \left(= {\frac{|\mathbf {L}|-|\mathbf {L}_{\text{red}}|}{|\mathbf {L}|}} = \frac{(1\,985\,028-411\,305)}{1\,985\,028}\right)。因此，缩减后的线向量集 \mathbf {L}_{\text{red}} 用作 LCL‑RANSAC 的工作空间，而线向量集 \mathbf {L} 用作 H‑RANSAC 的工作空间。
第 III 节。我们的 C-Ransac 注册算法
我们的 C-RANSAC 注册算法的流程已在图 1 中草绘，算法的贡献首先被列出。接下来，模拟了两个握手过程，以解释为什么如果初始全局解不正确，我们的算法如何得到更好的解，最终有效地逼近正确解。随后，展示了我们的算法流程图。最后，提供了算法快速收敛和高精度优势的分析。
A. 我们的 C-RANSAC 注册算法与流程图
提出的 C-RANSAC 注册算法列示如下。
算法 1：C-RANSAC 注册
输入： 线向量集 \mathbf {L}.
输出： \mathbf {L} 的注册解。
步骤 1: (构造缩减后的直线向量集 \mathbf {L}_{red})
使用基于尺度直方图的离群点剔除方法构造缩减后的直线向量集 \mathbf {L}_{red}。
步骤 2: (初始化 H-RANSAC)
H-RANSAC 将初始全局配准解设置为 (s, \mathrm{{R}}, t)_{H} = (1,\ \mathbf {I}^{3},\ (0,\ 0,\ 0)^{t}) 并将迭代次数设置为 x_{H} = 0。随后，H-RANSAC 将 (s, \mathrm{{R}}, t)_{H} 和 x_{H} 发送给 LCL-RANSAC。转至步骤 3。
步骤 3: (由 LCL-RANSAC 计算 \mathbf {L}_{sam} 的第一套配准解)
LCL-RANSAC 首先构造一个新的直线向量子集 \mathbf {L}_{sam}，该子集是从 \mathbf {L}_{red} 随机选取的。为方便记号，LCL-RANSAC 首先将收到的全局解 (s, \mathrm{{R}}, t)_{H} 重命名为 (s, \mathrm{{R}}, t)_{LCL}。接着，LCL-RANSAC 将已重命名为 (s, \mathrm{{R}}, t)_{LCL} 的收到的全局解作为 M-TEASER++ 方法（见附录）的初始解，用来基于新生成的基本直线向量集 \mathbf {L}_{bsc}（该集是从 \mathbf {L}_{sam} 随机抽样得到的）计算第一套局部配准解 (s, \mathrm{{R}}, t)_{new}。此外，LCL-RANSAC 将暂定迭代次数设置为 x_{LCL} = 1。转至步骤 4。
步骤 4: (全局迭代次数继承条件测试)
设 (s_{LCL}, \mathrm{{R}}_{LCL}, t_{LCL}) = (s, \mathrm{{R}}, t)_{LCL} 与 (s_{new}, \mathrm{{R}}_{new}, t_{new}) = (s, \mathrm{{R}}, t)_{new}。LCL-RANSAC 检查以下三个不等式：
\begin{gather*} |s_{new} - s_{LCL}| \leq 2^\tau \tag{2}\\ \mathrm {arccos}\left(\frac{tr(\mathrm{{R}}_{new}(\mathrm{{R}}_{LCL})^{T})-1}{2}\right) \leq {0.01} \tag{3}\\ \Vert t_{new} - t_{LCL}\Vert \leq {^\tau,} \tag{4} \end{gather*}
其中噪声界限 ^\tau 由用户设定。如果 (2)–(4) 中的三条不等式不成立，LCL-RANSAC 转至步骤 5；否则，LCL-RANSAC 将局部迭代次数设置为
\begin{equation*} x_{LCL} := {\begin{cases}x_{H} + 1 & \text{if}\ (s, \mathrm{{R}}, t)_{LCL}\ \text{is renamed} \\ &\text{from }(s, \mathrm{{R}}, t)_{H} \\ x_{LCL}; & \text{otherwise} \end{cases}} \tag{5} \end{equation*}
在 (5) 中，如果 (s, \mathrm{{R}}, t)_{LCL} 是从 (s, \mathrm{{R}}, t)_{H} 重命名而来，则表明 LCL-RANSAC 获得的第一套局部配准解与收到的全局配准解相近。随后，LCL-RANSAC 直接将 x_{LCL} 和 (s, \mathrm{{R}}, t)_{new} 返回给 H-RANSAC，并转至步骤 6。步骤 5: (局部置信度条件测试)
LCL-RANSAC 将其本地置信度更新为 Pr(LCL) = 1 - (1 - {Ir_{LCL})^{x_{LCL}}}，其中 Ir_{LCL} 表示 \mathbf {L}_{sam} 的当前最高内点率。 如果 {Pr(LCL)} \geq {99}{\%}，LCL-RANSAC 将当前最佳本地配准解 (s, \mathrm{{R}}, t)_{LCL} 和迭代次数 x_{LCL} 传回 H-RANSAC，随后转至步骤 6. 如果 Pr(LCL) 小于 99%，LCL-RANSAC 在新生成的基本线向量集合 \mathbf {L}_{bsc} 上执行 M-TEASER++ 方法，以细化 \mathbf {L}_{sam} 的本地配准解，记为 (s, \mathrm{{R}}, t)_{new}，并将本地迭代次数设为 x_{LCL}，即 x_{LCL} := x_{LCL} + 1。 转至步骤 4.
Step 6: (更新全局解和迭代次数)
H-RANSAC 利用收到的本地配准解来更新全局内点率和 \mathbf {L} 的全局配准解。 此外，H-RANSAC 将全局迭代次数更新为 x_{H} := x_{H} + x_{LCL}。 随后，H-RANSAC 将全局置信度更新为 Pr(H) = 1 - (1 - Ir_{H})^{x_{H}}，其中 Ir_{H} 表示 \mathbf {L} 的当前最高内点率。 转至步骤 7.
Step 7: (全局置信度条件测试)
如果 {Pr(H)} < 99\%，H-RANSAC 将当前最佳全局配准解 (s, \mathrm{{R}}, t)_{H} 和更新后的全局迭代次数 x_{H} 发送给 LCL-RANSAC 并转至步骤 3。 否则，如果 {Pr(H) \geq }\ 99\%，H-RANSAC 停止算法并报告最终配准解 (s, \mathrm{{R}}, t)_{H}。
在列出我们的 C-RANSAC 算法后，我们模拟前两次握手，以便更易于理解我们的算法。
在第一个握手过程中，完成步骤2后，初始全局配准解 (s, \mathrm{{R}}, t)_{H} 通常不正确，并且与最终正确解相差很远。在步骤3中，LCL-RANSAC 将收到的初始全局配准解作为 M-TEASER++ 方法的初始解，以基于新生成的基本线向量集合 \mathbf {L}_{\text{bsc}} 计算第一个局部配准解 (s, \mathrm{{R}}, t)_{\text{new}}，该集合是从 \mathbf {L}_{\text{sam}} 随机采样得到的。由于线向量子集 \mathbf {L}_{\text{sam}} 是从已去除异常值的减小线向量集合 \mathbf {L}_{\text{red}} 随机选取的，相比初始全局配准解 (s, \mathrm{{R}}, t)_{H}，第一个局部配准解 (s, \mathrm{{R}}, t)_{\text{new}} 应该更接近最终正确的配准解。在步骤4中，由于通常 (s, \mathrm{{R}}, t)_{\text{new}} 与 (s, \mathrm{{R}}, t)_{H} 差距很大，全局迭代次数继承条件测试将失败，然后在步骤5中，LCL-RANSAC 迭代细化 \mathbf {L}_{\text{sam}} 的局部配准解，直到局部置信水平达到指定阈值。在步骤6中，H-RANSAC 利用收到的局部配准解来更新全局配准解和 \mathbf {L} 的内点率。此外，H-RANSAC 利用收到的局部迭代次数更新累计全局迭代次数为 x_{H} + x_{\text{LCL}}，随后全局置信水平进一步更新。
在第二个握手过程中，收到 H-RANSAC 更新后的全局配准解和全局迭代次数后，LCL-RANSAC 将收到的全局配准解作为 M-TEASER++ 方法的初始解，再次计算 \mathbf {L}_{\text{sam}} 的第一个局部配准解 (s, \mathrm{{R}}, t)_{\text{new}}。此外，在步骤4中，LCL-RANSAC 检查全局迭代次数继承条件测试是否成立。如果继承条件成立，LCL-RANSAC 将第一个局部配准解和迭代次数 x_{H} + 1 发送回 H-RANSAC，以更新全局解、迭代次数、内点率和置信水平。否则，如果继承条件失败，LCL-RANSAC 将使用 M-TEASER++ 方法迭代细化 \mathbf {L}_{\text{sam}} 的局部配准。
为完整起见，我们算法的详细流程图如图3所示。
图3. 我们的C-RANSAC配准算法流程图.
B. 我们算法的快速收敛和高精度优势分析
我们先分析算法的快速收敛优势，然后分析高精度优势。
1) 快速收敛优势
当我们的算法，即算法1，终止时，H-RANSAC的全局置信水平满足
\begin{align*} \Pr (H) =& 1 - (1 - \text{Ir}_{H})^{\sum _{i = 1}^{m} x^{(i)}_{\text{LCL}}} \\ =& 1 - (1 - \text{Ir}_{H})^{M} \\ \geq &99\% \tag{6} \end{align*}
其中，“m”表示LCL-RANSAC被H-RANSAC调用了m次。“x^{(i)}_{\text{LCL}}，” 1 \leq i \leq m，指完成第i次LCL-RANSAC调用后返回到H-RANSAC的局部迭代编号。式(6)表明基于线向量集合\mathbf {L}，H-RANSAC仅更新全局置信水平、全局内点率以及全局配准解m次，而非M次。由于m\ \ll \ M，我们的算法相对于传统RANSAC方法具有快速收敛优势。我们以图2(b)中的点云对来说明我们算法的快速收敛优势。
根据图 2(b)，已知 |\mathbf {L}| = 1\,985\,028 和 |\mathbf {L}_{\text{red}}| = 411\,305。在从 \mathbf {L}_{\text{red}} 随机抽取 10% 的线向量构造 \mathbf {L}_{\text{sam}} 后，得到 |\mathbf {L}_{\text{sam}}| = 41\,130。此外，在从 \mathbf {L}_{\text{sam}} 随机抽取 30% 的线向量构造基本线向量 \mathbf {L}_{\text{bsc}} 后，得到 |\mathbf {L}_{\text{bsc}}| = 12\,339。在对图 2(b) 进行我们的 C-RANSAC 注册算法后，H-RANSAC 与 LCL-RANSAC 之间的握手过程数为五；另一方面，我们有 m = 5。在这五次握手中，我们的经验显示从 LCL-RANSAC 发送给 H-RANSAC 的五个局部迭代次数分别是 x^{(1)}_{\text{LCL}} = 2、x^{(2)}_{\text{LCL}} = 2、x^{(3)}_{\text{LCL}} = 5、x^{(4)}_{\text{LCL}} = 2 和 x^{(5)}_{\text{LCL}} = 12；全局迭代继承条件在第三次和第五次握手过程中成立。可以检查到 LCL-RANSAC 使用的 M-TEASER++ 方法所需的五个迭代次数分别是 2、2、1、2 和 1。由于 |\mathbf {L}_{\text{red}}| \ll |\mathbf {L}| 并将全局迭代次数继承条件测试纳入我们的算法，我们的算法具有快速收敛的优势，即执行时间缩短的收益。
2) 高注册精度优势
在我们的 C-RANSAC 算法中，每一次，当 LCL-RANSAC 从 H-RANSAC 接收到全局配准解 (s, \mathrm{{R}}, t)_{H} 后，LCL-RANSAC 将 (s, \mathrm{{R}}, t)_{H} 用作 M-TEASER++ 方法的初始解，以基于 \mathbf {L}_{\text{red}} 计算第一次局部解。因为在带有 |L_{\text{red}}| \ll |L| 的 \mathbf {L}_{\text{red}} 中，异常值已在一定程度上从初始线向量集合 \mathbf {L} 中移除，LCL-RANSAC 估计的局部配准解比在 \mathbf {L} 上使用传统 RANSAC 基础配准方法得到的解更精确。由于每一次 H-RANSAC 与 LCL-RANSAC 都以握手方式协作，这意味着 H-RANSAC 估计的全局配准解比使用传统 RANSAC 方法得到的解更精确。
SECTION IV. 实验结果
为评估我们命名为 “Ours” 的 C-RANSAC 配准算法以及对比方法的配准性能，提供了两种实验设计。
在考虑尺度解的第一次实验设计中，我们遵循与 [^42] 和 [^51] 相同的实验设计，比较我们的 C-RANSAC 算法、TEASER++ [^42]、one-point RANSAC [^47] 与 RANSIC [^51] 的精度性能和执行时间性能。
在第一次实验设计中，四个精度指标，即尺度误差 (s^{\text{err}})、旋转误差 (\mathrm{{R}}^{\text{err}})、平移误差 (t^{\text{err}}) 和 RMSE 34，被用于评估每个考虑方法的精度性能。令地面真值配准解记为 (s^{\text{gt}}, \mathrm{{R}}^{\text{gt}}, t^{\text{gt}})，考虑方法的估计配准解记为 (s^{\text{est}}, \mathrm{{R}}^{\text{est}}, t^{\text{est}})。这四个精度指标定义为
\begin{align*} {s^{\text{err}}} =& |s^{\text{gt}} - s^{\text{est}}| \tag{7}\\ {\mathrm{{R}}^{\text{err}}} =& \mathrm {arccos}\left(\frac{tr(\mathrm{{R}}^{gt}(\mathrm{{R}}^{est})^{T})-1}{2}\right) \tag{8}\\ {t^{\text{err}}} =&\Vert t^{\text{gt}} - t^{\text{est}}\Vert \tag{9}\\ \mathrm{{RMSE}} =& \sqrt{\frac{1}{|{\mathbf {P}^{s}}|}\sum_{i=1}^{{|{\mathbf {P}^{s}}|}}\Vert x^{\text{gt}}_{i} - x^{\text{est}}_{i}\Vert ^{2}} \tag{10} \end{align*}
其中，x^{\text{gt}}_{i} 表示通过执行地面真值配准解 (s^{\text{gt}}, \mathrm{{R}}^{\text{gt}}, t^{\text{gt}}) 于 x_{i} \in {\mathbf {P}^{s}} 所得到的映射点，x^{\text{est}}_{i} 表示通过执行估计配准解 (s^{\text{est}}, \mathrm{{R}}^{\text{est}}, t^{\text{est}}) 于 x_{i} \in {\mathbf {P}^{s}} 所得到的映射点，\mathrm{{tr}}(\cdot) 表示该矩阵的迹。测试点云的构建及性能比较结果在节 IV-A 中给出。在不考虑尺度解的第二次实验设计中，为比较我们的 C-RANSAC 算法、Graph-Cut RANSAC [^36]、TEASER++ [^42]、one-point RANSAC [^47] 与 RANSIC [^51] 的精度性能和执行时间性能，使用三项精度指标，即 \mathrm{{R}}^{\text{err}}、t^{\text{err}} 与 RMSE，来评估每种方法的精度表现。使用包含 1623 对点云的真实点云数据集 3DMatch。相关性能比较结果见节 IV-B。
为了公平起见，所有对比方法和所提方法都在配备 Intel Core i7-8700 CPU 3.2 GHz 和 32 GB RAM 的计算机上实现。操作系统为 Microsoft Windows 10 64 位操作系统。程序开发环境为 Windows Subsystem for Linux 与 MATLAB R2022b。我们的 C-RANSAC 注册方法的 C++ 源码可从网站 https://github.com/ivpml84079/C-RANSAC 获取。
A. 注册精度与执行时间比较：考虑尺度解
1) 构建人工测试点云
在第一个实验设计中，作为 22 个测试源点云，八个点云从 3DMatch 数据集选取，十四个点云从 RGB‑D 数据集选取。随后，我们采用体素网格下采样方法，即点云库中的 “Voxelgrid” [^57]，对每个源点云进行下采样，使得下采样后源点云的大小 \mathbf {P}^{s} 等于 |\mathbf {P}^{s}| = 2000。随后，我们通过对每个源点云 \mathbf {P}^{s} 进行随机变换，创建相应的目标点云 \mathbf {P}^{t}，并将变换后的点云视为 (7)–(10) 中使用的地面真值配准解。
具体而言，给定一个采样的源点云 \mathbf {P}^{s}，使用随机变换程序 [^42]，生成地面真实的目标点云 \mathbf {P}^{t}，使得生成的地面真实比例解 s^{\text{gt}}、旋转解 \mathrm{{R}}^{\text{gt}} 和平移解 t^{\text{gt}} 满足三个约束：1 \leq s^{\text{gt}} \leq 5、\Vert t^{\text{gt}}\Vert \leq 1 和 \mathrm{{R}}^{\text{gt}} \in \mathrm{{SO}}(3)。在对 {\mathbf {P}^{s}} 进行随机变换后，随机有界噪声 n_{i} 被添加到 {\mathbf {P}^{t}} 中的每个目标点，其中 n_{i} = ([-1, 1] * {\uptau}, [-1, 1] * {\uptau}, [-1, 1] * {\uptau})m 的噪声边界 \uptau 设置为 0.05 [^58]、[^59]，并且“m”表示单位“米”。沿用 [^42] 与 [^51] 中考虑的相同离群率，基于每个目标点云 \mathbf {P}^{t}，我们首先根据五个不同的离群率（即 0.5、0.6、0.7、0.8 和 0.9）随机采样目标点，从 \mathbf {P}^{t} 中采样，然后将这五个采样的目标点沿区间 (\pm [5, {10],} \pm [5, {10],} \pm [5, {10])}m 平移。随后构造初始对应集 \mathbf {C} 和初始线向量集 \mathbf {L}。
2) 注册精度比较与讨论
对于每一组测试点云对，所考虑的每种方法均测试 100 次。就 s^{\text{err}}、\mathrm{{R}}^{\text{err}}、t^{\text{err}} 和 RMSE 而言，所考虑方法的准确性表现分别展示在表 I 的前四个子表中。每个子表的最后一列，“avg”是 “average value”（平均值）的缩写。
表 I
在表 I 中，在某一特定异常值率下，在所考虑的方法中，最佳准确率结果（即误差最小）以黑色加粗标注，次优准确率结果以橙色加粗标注。 从表 I 可见，在两个准确率指标 s^{\text{err}} 和 t^{\text{err}} 上，我们的算法具有最佳准确率表现。 在旋转误差 \mathrm{{R}}^{\text{err}} 上，RANSIC 方法具有最佳准确率表现，而我们的算法则为第二佳。 在 RMSE 指标上，我们的算法拥有最佳准确率表现，TEASER++ 方法则为第二佳。
在整体准确率指标“RMSE”上，我们的算法具有最佳准确率表现，而 TEASER++ 方法则为第二佳。 正如在 III-B2 节讨论的那样，在我们 C-RANSAC 算法中 LCL-RANSAC 使用的简化线向量集 \mathbf {L}_{\text{red}} 中，已将异常值从初始线向量集 \mathbf {L} 中移除，使得 LCL-RANSAC 估计的局部配准解具有更高的准确率。 此外，由于 H-RANSAC 每次都以握手方式与 LCL-RANSAC 合作，导致得到全局配准解。
虽然 RANSIC 方法在旋转性能上表现最佳，但在 RMSE 上，其整体配准准确率排名第三，原因是平移准确率不足。主要原因在于 RANSIC 直接将源点集和目标点集内点集的均值向量差作为平移解。
3) 执行时间比较与讨论
以秒为单位，各考虑配准方法的执行时间表现显示在表 I 的最后一个子表中。
表 I 的最后子表显示 RANSIC 方法具有最佳的执行时间性能。我们的算法具有第二好的执行时间性能。由于 RANSIC 利用不变性与兼容性理论从初始对应集 \mathbf {C} 中提取内点候选，导致每次迭代中确定的共识集基数很小，从而实现最佳的执行时间性能。表 I 中我们良好的执行时间性能证明了 III‑B1 节中快速收敛收益分析的合理性。
总之，结合上述针对 22 对测试点云在考虑尺度解的情况下的配准精度与执行时间比较与讨论，我们的 C-RANSAC 配准算法的执行时间性能排名第二，而配准精度性能在与三种最先进配准方法对比时表现最佳。
B. 配准精度与执行时间比较：不考虑尺度解
在此实验设计中，未考虑尺度方案，使用包含1623对点云的3DMatch数据集作为测试数据集。与第一次实验设计类似，在第二次实验设计中，噪声边界 \uptau 也被设置为0.05。\mathrm{{R}}^{\text{err}}、t^{\text{err}}和RMSE（已在 (8)–(10) 中定义）用于比较Graph-Cut RANSAC、TEASER++、one-point RANSAC、RANSIC以及我们的算法之间的配准精度表现。
1) 注册精度比较与讨论
各个被考虑方法的精度表现展示在表 II 中。
表 II
从表 II 可知，在三项准确率指标方面，\mathrm{{R}}^{\text{err}}、t^{\text{err}} 与 RMSE，C-RANSAC 算法表现出最佳准确率，验证了第 III-B2 节分析的高准确率优势。在 \mathrm{{R}}^{\text{err}} 与 RMSE 方面，TEASER++ 方法具有第二佳准确率；在 t^{\text{err}} 方面，一点 RANSAC 方法具有第二佳准确率。
我们 C‑RANSAC 算法的感知效果如图 4 所示。图 4(a) 说明了四组测试点云对，即 hotel_uc、redkitchen、mit_lab 和 studyroom，均取自 3DMatch 数据集，其中源点集 \mathbf {P}^{s} 用蓝色标记，目标点集 \mathbf {P}^{t} 用绿色标记。图 4(b) 展示了使用我们算法得到的配准结果的对齐效果。从图 4(b) 我们可以看到，四个蓝色标记的对齐后源点云与相应的四个目标点云匹配良好，说明我们的配准算法具有良好的感知配准效果。
图 4. 我们的 C‑RANSAC 配准算法的感知效果。(a) 四组测试点云对，源点集 \mathbf {P}^{s} 用蓝色标记，目标点集 \mathbf {P}^{t} 用绿色标记。(b) 四个对齐结果.
2) 执行时间比较与讨论
按秒计，每种考虑的配准方法的执行时间表现如表 II 所示。
从表 II 可知，RANSIC 方法具有最佳的执行时间表现。Graph‑cut RANSAC 方法排名第二。由于 3DMatch 数据集中存在一定数量的异常值，它削弱了我们算法中基于尺度直方图的异常值剔除方法的剔除效果，导致我们的算法执行时间表现下降。
综上所述，针对未考虑尺度解的 3DMatch 数据集，上述配准精度与执行时间的比较与讨论表明，虽然我们 C‑RANSAC 配准算法的执行时间表现尚可，但在配准精度方面，优于四种最先进的配准方法。
第 V 节. 结论
已提出适用于 PCR 的 C-RANSAC 算法。在我们的算法中，第一项创新是提出基于尺度直方图的异常值去除方法，以从初始线向量集合 \mathbf {L} 中删除异常值，构造出精简后的线向量集合 \mathbf {L}_{\text{red}}。第二项创新是 H-RANSAC 与 LCL-RANSAC 以握手方式协同工作。H-RANSAC 仅在初始线向量集合 \mathbf {L} 上工作，而 LCL-RANSAC 仅在由从 \mathbf {L} 中去除异常值后构造的精简线向量集合 \mathbf {L}_{\text{red}} 上工作。第三项创新是，一旦 LCL-RANSAC 从 H-RANSAC 接收到全局配准解，第一份局部配准解便由 M-TEASER++ 方法获得。如果全局迭代次数继承条件成立，似乎第一份局部配准解已通过 H-RANSAC 运行 HAV 过程 x_{H} + 1 次得到，然后 LCL-RANSAC 将第一份局部配准解和迭代次数 x_{H} + 1 返还给 H-RANSAC，以更新全局解、迭代次数和置信度。即使全局迭代次数继承条件不成立，LCL-RANSAC 仍使用 M-TEASER++ 方法迭代细化其局部解，然后将得到的局部解和所需的局部迭代次数 x_{\text{LCL}} 发送给 H-RANSAC，以更新全局解、全局迭代次数到 x_{H} := x_{H} + x_{\text{LCL}} 以及全局置信度。我们在测试点云对上进行了广泛实验，以展示我们的算法相较于 Graph-Cut RANSAC、TEASER++、one-point RANSAC 和 RANSIC 的配准精度和执行时间优势。
未来的工作是提高设定的置信度等级，但牺牲执行时间，以实现配准精度与执行时间需求之间更好的平衡。
附录 M-TEASER++ 方法
附录M-TEASER++ 方法
在每一次迭代中，LCL-RANSAC 在新构造的基本线向量集合 \mathbf {L}_{\text{bsc}} 上执行 M-TEASER++ 方法，以估计 \mathbf {L}_{\text{bsc}} 的局部配准。TEASER++ 与 M-TEASER++ 之间的差异如下所示。
章节 A. 估计局部尺度解
LCL-RANSAC 随机从 \mathbf {L}_{\text{bsc}} 中挑选一个线向量 s，然后计算 \mathbf {L}_{\text{bsc}} 的新内点率，记为 \text{Ir}_{\text{new}}^{s}。如果 \text{Ir}_{\text{new}}^{s} > \text{Ir}_{\text{LCL}}^{s}，则执行赋值操作：\text{Ir}_{\text{LCL}}^{s} := \text{Ir}_{\text{new}}^{s}。\mathbf {L}_{\text{bsc}} 的局部置信水平被更新。上述 s 的选择、局部内点率更新以及置信水平更新会重复进行，直到达到指定的置信水平 99%，然后确定最大共识集 \subseteq \mathbf {L}_{\text{bsc}}。最后，在最大共识集上执行最小二乘技术，以获得 \mathbf {L}_{\text{bsc}} 的局部尺度解。
在求解 \mathbf {L}_{\text{bsc}} 的旋转参数之前，基于已获得的 \mathbf {L}_{\text{bsc}} 的尺度解，记为 s，对于 \mathbf {L}_{\text{bsc}} 中的每个线向量 (v^{x}_{i,j}, v^{y}_{i,j})，我们将 v^{x}_{i,j} 按尺度解 s 缩放得到一个缩放后的线向量。为方便起见，缩放后的线向量集合记为 \mathbf {L}_{\text{bsc}}^{s}。
章节 B. 估计局部旋转解
在使用迭代 GNC-TLS 方法 [^44] 计算 \mathbf {L}_{\text{bsc}}^{s} 的旋转解 R 之前，GNC 替代函数被用作惩罚函数，通过为 \mathbf {L}_{\text{bsc}}^{s} 中残差更小（更大）的线向量设定更大（更小）的权重来实现。在 TLS 中，当权重低于指定阈值（该阈值在每次迭代中递减更新）时，权重被设为零，以截断 \mathbf {L}_{\text{bsc}}^{s} 中不可靠的线向量。
基于 \mathbf {L}_{\text{bsc}}^{s} 中的可靠线向量，使用 SVD 技术得到初步旋转解，并反复进行旋转解更新和权重更新，直至加权残差之和收敛。对于 LCL-RANSAC，初始旋转矩阵设为 \mathrm{{R}}_{\text{LCL}}，该矩阵由 H-RANSAC 发送。此修改后的初始旋转矩阵设定策略可实现更快收敛并获得更好的旋转精度。
在解决平移参数之前，基于已得到的 \mathbf {L}_{\text{bsc}}^{s} 的旋转解（记作 R），对于 \mathbf {L}_{\text{bsc}}^{s} 中的每个线向量 (v^{x}_{i,j}, v^{y}_{i,j})，我们将 v^{x}_{i,j} 按旋转解 R 旋转得到一个旋转后的源向量。收集所有这些旋转后的源向量及其对应的目标向量，重新构建对应关系集，即 \mathbf {C}_{\text{bsc}}^{s\mathrm{{R}}}。
SECTION C. 估计局部平移解
基于 \mathbf {C}_{\text{bsc}}^{s\mathrm{{R}}}，采用 [^42] 中的自适应投票方法求解平移参数 t = (t_{1}, t_{2}, t_{3})。在求解每个独立的平移参数 t_{i}, 1 \leq i \leq 3 时，使用最大冲刺法 [^60] 来枚举所有可能的一致子集，并选取最大的作为最大一致集。注意，对于 LCL-RANSAC，收到的全局初步平移解 t_{\text{LCL}}（由 H-RANSAC 发送）用于协助实现最大冲刺法以确定最大一致集。此外，使用最小二乘法计算 \mathbf {C}_{\text{bsc}}^{s\mathrm{{R}}} 的平移解。
完成 M-TEASER++ 方法后，\mathbf {L}_{\text{bsc}} 的局部配准解，即 (s, \mathrm{{R}}, t)_{\text{new}}，被返回给 LCL-RANSAC。
脚注
. 最佳结果用黑色粗体标记，次佳结果用橙色粗体标记。