CLIPPER+: 一个快速最大团算法，用于稳健全局配准

摘要

我们提出了 CLIPPER+，一种用于无权图中寻找最大团的算法，适用于鲁棒的全局配准。配准问题可以被表述为图问题，并通过寻找其最大团来求解。该表述使得对离群值具有极高的鲁棒性；然而，寻找最大团是 NP 难题，因此在实际大规模问题中需要使用近似方法。近似算法的性能通过其计算复杂度（运行时间越低越好）和解的精度（解离最大团的距离）来评估。因此，CLIPPER+ 的主要贡献是在保持相对低运行时间的同时，优于现有技术的精度。CLIPPER+ 构建在先前工作（CLIPPER Lusk 等 (2021) 以及 PMC Rossi 等 (2015)）之上，并通过移除核心数小且无法构成最大团的顶点来裁剪图，从而得到更小的图，使得最大团的估计速度显著加快。我们在标准图基准以及合成和真实点云配准问题上评估了 CLIPPER+ 的性能。评估结果表明，CLIPPER+ 具有最高的精度，并能够在超过 99% 的关联为离群值的场景中完成点云配准。我们的代码和评测基准将发布在 https://github.com/ariarobotics/clipperp。

作者

Kaveh Fathian 科罗拉多矿山学院计算机科学系，科罗拉多州黄金，美国 ORCID: 0000-0003-4471-0867

Tyler Summers 德克萨斯大学达拉斯分校机械工程系，德克萨斯州理查森，美国 ORCID: 0000-0002-0113-8912

出版信息

期刊: IEEE Robotics and Automation Letters 年份: 2024 卷: 9 期: 4 页码: 3562-3569 DOI: 10.1109/LRA.2024.3368233 文章编号: 10440966 ISSN: Electronic ISSN: 2377-3766, CD: 2377-3774

指标

论文引用次数: 4 总下载次数: 498

资助

• 空军科学研究办公室（资助：FA9550-23-1-0424）

• 国家科学基金会（资助：ECCS-2047040）

• ARL SARA（资助：W911NF2420029）

关键词

IEEE 关键词： 点云压缩, 运行时, 近似算法, 三维显示, 同时定位与地图构建, 鲁棒性, 注册

Index Terms: 全局配准, 鲁棒配准, 团算法, 基准, 计算复杂度, 点云, NP难题, 点云配准, 无权图, 配准问题, 优化算法, 全局优化, 局部最优, 近似解, 一致关联, 极端离群点, 精确算法, 计算机视觉应用, 潜在关联, 贪心方法, 连续松弛, 梯度上升, 最坏情况复杂度, 迭代最近点, 准确率, 最大似然解, C++实现, 离群点拒绝, 一致性阈值, 最大整数

Author Keywords: 定位, SLAM, RGB-D 感知

未定义

第一节. 引言

数据关联被广泛定义为不同数据集合中相同/相似元素之间的对应关系，并且是许多机器人技术和计算机视觉应用的关键组成部分，例如定位和地图构建 ¹, ², ³, 点云配准 ⁴, ⁵, 形状对齐 ⁶, 目标检测 ⁷, 数据融合 ⁸, ⁹, 以及多目标跟踪 ¹⁰. 在这些应用中，正确且快速地解决数据关联至关重要。

在点云配准中，例如，我们需要寻找使两组3D点对齐的刚性变换（旋转/平移）。这需要将一组中的点与另一组中的对应点进行配对。局部配准技术，例如迭代最近点（ICP）算法 ¹¹，是根据最近邻来关联点的。当点云初始对齐不佳时，这些关联通常是错误的，从而导致配准错误。更好的关联可以通过匹配在点云中每个点周围计算的描述子来建立，这些描述子描述了点的局部几何和外观（例如，经典的 FPFH ¹² 或现代基于学习的 3DMatch ¹³）。然而，由于噪声、重复模式、点云间的重叠很小等因素，这些假设性关联可能具有极高的离群点比例（例如，第 V‑C 节中的 FPFH 关联有 99% 的离群/错误比例）。在这些高离群率的情况下，现有的离群点拒绝技术（如通用 RANSAC 框架 ¹⁴ 或专门用于点云配准的框架 ¹⁵）要么得到错误结果，要么运行时间不可行（例如，RANSAC 的运行时间随离群率呈指数增长 ¹⁶）。

为了解决这些问题，我们提出了 CLIPPER+ 算法。CLIPPER+ 将数据关联问题表述为图论问题，其中内点/正确关联构成最大团。该表述对高离群率具有鲁棒性，并且适用于任何接受invariants（参见第三节）的问题，例如点、线和面共配准 ¹⁷, ¹⁸, ¹⁹。为了解决寻找最大团的高计算复杂度（NP‑难度），CLIPPER+ 采用近似解法，其实现方式是将我们先前工作 CLIPPER ²⁰ 的改进版与 ²¹ 中的贪心最大团算法相结合。CLIPPER+ 的运行时间为多项式级，并且在最大团估计精度上优于最先进的算法（V‑A 节）。此外，CLIPPER+ 的解在超过 99% 的点云配准实验中被证明是精确的（即最大团）（V‑C 节）。

贡献: 总结而言，本工作的贡献如下：

• 一个改进的求解器（算法 2），在准确率上优于我们之前的工作 CLIPPER ²²。

• 新的 CLIPPER+ 算法将 ²³ 中的贪心算法与 CLIPPER ²⁴ 结合，进一步提升了运行时间和准确率。

• 评估表明 CLIPPER+ 在最大团问题上相较于最先进方法具有更高准确率，并且在超过 99% 异常值的情形下能够正确地对齐现实世界点云。

• 所有算法的高效 C++ 实现（开源代码将发布）。

第二节. 相关工作

鲁棒配准: 在机器人数据关联的应用中，例如配准，针对不确定性（如极端噪声和异常值）鲁棒的公式基于全局最优求解器，如 Branch and Bound ²⁵、²⁶、²⁷，以及最大一致性的组合方法 ²⁸。 这些方法能够容忍极高的异常值比例，但在最坏情况下具有指数级复杂度，在实际应用中速度较慢。 为了解决这个问题，使用了快速启发式方法，例如 RANSAC ²⁹ 及其变体 ³⁰，graduated non-convexity ³¹、³²、³³，或用于 M-estimation 的迭代局部求解器 ³⁴、³⁵，然而它们在高异常值比例的情形下容易失败 ³⁶、³⁷、³⁸。

图论公式化: 通过在某些接受“不变量”的数据关联设置中（参见第III节，以及 ³⁹, ⁴⁰, ⁴¹）采用图论框架，可以解决鲁棒性与运行时间之间的二分法。利用该框架的最新算法包括用于全局点云配准、能抵御超过99%离群点并适用于实时应用的 CLIPPER ⁴²、TEASER ⁴³ 和 ROBIN ⁴⁴，以及用于SLAM中成对一致闭环的 PCM ⁴⁵。该图论公式化可追溯到 Bailey 等人 ⁴⁶ 对二维激光雷达配准的最大公共子图问题的研究，其中最大团指示了正确的数据关联。Leordeanu 与 Hebert ⁴⁷ 将此图论框架扩展到加权一致性图。Enqvist 等人 [^31] 关注到 ⁴⁸ 的次优性，并提出了顶点覆盖公式化，本质上是对 ⁴⁹ 的最大团公式化的另一种替代。Parra 等人 [^32] 提出了一种基于分支定界和图着色的几何一致性实用最大团算法。最近，Zhang 等人 [^33] 展示了通过放宽最大团约束并使用最大团来解决配准问题。

最大团估计: 寻找最大团是一个众所周知的 NP-hard 问题，完整形式 [^34]，这意味着使用精确算法（例如 ⁵⁰）在图大小指数增长时求解的复杂度呈指数级，因而对数据关联应用不切实际。一个近似（最大团）解仍可通过多项式时间算法得到。在此设置中值得注意的算法包括 Pelillo [^35] 和 Ding 等人 [^36]，基于 Motzkin‑Straus 公式化 [^37]，Belachew 与 Gillis [^38] 基于对称秩一非负矩阵近似，以及我们之前的 CLIPPER 算法 ⁵¹，基于连续松弛。

第三节. 图论鲁棒配准

针对极端异常值比例实现鲁棒性的关键思路是寻找最大的一组联合一致的数据和/或关联。该问题可以被表述为一个图，其中该集合由最大团表示。接下来，我们介绍这一图论框架及其在点云配准中的应用案例。

点云配准: 点云配准的目标是寻找刚性变换，使一组点与另一组点的对应点对齐。主要挑战是找到正确的对应关系，因为通常只有部分点匹配，且由于噪声点并不完全对齐。一个 离群点 可以是某一集合中的点在另一集合中没有对应点，或者是错误匹配的关联。我们关注的是关联，因此 离群点 在此指 离群点关联。图 1 说明了一个点云配准例子，我们在杂乱的点云中寻找蓝色兔子。

图 1. 为鲁棒全局配准的最大团表述示例。 (左) 假定关联（红色：离群点，绿色：内点）。 (右) 图的表述，最大团指示内点关联。

Maximum likelihood solution: 在缺乏先验知识且异常值是随机、无偏且无结构时，最大联合一致关联集合 是最大似然解的内点。对于点云配准，如果两条关联的端点等距，则它们是一致，因此可以通过刚性变换对齐。在图 1 中，绿色关联对齐 3 个点，而红色关联对齐 2 个点。因此，绿色关联是内点，可用于计算正确的最大似然解。

图形公式化: 将最大的共同一致关联集合的寻找表述为最大团问题。给定 n 条关联，一致性图 是一个包含 n 个顶点的图，每个顶点代表一条关联。顶点之间的边表示这些关联是一致的。在图 1 中，一条显示在右侧的一致性图中两顶点之间的边表示对应关联的一致性。例如，顶点/关联 2 与 3 之间存在一条边，因为它们的端点等距 (d=d^{\prime })，而顶点/关联 1 与 3 之间没有边。给定两条关联，其端点距离为 d 和 d^{\prime }，由于噪声，通常使用一个 一致性阈值 \epsilon，当 |d-d^{\prime }|< \epsilon 时，这些关联被视为一致。

A 团 是一组顶点的子集，其中该子集内的每一对顶点都通过一条边相连。最大团 是顶点数最多的团。极大团 是不包含在更大团中的团。图 1 中的最大团由顶点 2、3 和 5 组成。顶点 1 和 4 形成一个极大团。

不变量: 基于图论的框架可以应用于机器人学中广泛的数据关联问题。不变量 是在各集合之间保持不变的量。上述点云配准示例中使用的不变量是端点之间的欧氏距离。不变量可用于注册线 ⁵²、平面 ⁵³、二维–三维视觉特征 ⁵⁴ 等。本工作中的示例，然而，聚焦于点云配准。

第四节：最大团算法

退化序排序贪心最大团算法。

1: 输入 A: 邻接矩阵； K: 核数

2: 输出 C: 构成极大团的顶点

3: C \gets \lbrace \rbrace; c_{\max } \gets 0

4: % 按核心数降序排序顶点：

5: (v_{1},\ldots, v_{n}) \gets 对顶点 v_{i} 进行排序，满足 K(v_{i}) \geq K(v_{j}) 若 i < j

6: 循环 i = 1 : n 执行

7: 如果 K(v_{i}) \geq c_{\max } 那么

8: % v_{i} 的邻居，核心数为 \geq c_{\max }:

9: S \gets \lbrace v_{j} : A(v_{i},v_{j})=1, K(v_{j})\geq c_{\max } \rbrace

10: (s_{1},\ldots, s_{k}) \gets 对 s_{i}\in S 按核心数降序排序

11: C^{\prime } \gets \lbrace \rbrace

12: for j=1:k do % 对排序后的 S 中的每个顶点

13: if A(c_{i},s_{j})=1 \,\forall _{c_{i} \in C^{\prime }} then % C^{\prime } \cup \lbrace s_{j}\rbrace 是团

14: C^{\prime } \gets \lbrace C^{\prime }, s_{j} \rbrace % 将 s_{j} 加入 C^{\prime }

15: if |C^{\prime }| > c_{\max } then % 找到更大的团

16: C \gets C^{\prime }; c_{\max } \gets |C^{\prime }| % 更新输出

我们在第 IV-B 和 IV-C 节中展示了本工作主要的算法贡献，在这些章节中我们讨论了基于连续松弛和 CLIPPER+ 的最大团算法。第 IV-A 节是对 ⁵⁵ 中方法的回顾，并非算法贡献。然而，我们对该算法的 C++ 实现相比其原始实现提升了性能和准确性。

A. 基于退化度排序的贪心最大团算法

算法 1 介绍了一种贪心方法用于寻找最大团。从空团（第 3 行）开始，我们通过循环遍历顶点（第 6 行）一次增大团。对于该循环检查的每个顶点 v，若它与当前团中已存在的每个顶点相连，则算法将 v 加入当前团；否则则舍弃 v（第 13-16 行）。该算法的总运行时间为 \mathrm{O}(\delta |E|)，其中 \delta 是最大顶点度数，|E| 是边数 ⁵⁶。

贪婪方法返回的最大团取决于用于扩展团的初始顶点选择，以及顶点的排序顺序（顶点被依次检查以决定是否加入当前团或被丢弃）。按核心数递减排序的顶点顺序大大提高了找到大最大团（甚至可能是最大团）的几率，正如算法 1（第 5 行和第 10 行）所利用的那样。数学上，顶点 v 的 core number（或 degeneracy）是最大的整数 k，使得当所有度数小于 k 的顶点被递归移除后，v 的度仍然不为零。顶点的核心数可以在 \mathrm{O}(|E|) 中通过 Batagelj 和 Zaversnik 的算法 [^39] 高效计算。

B. 连续松弛最大团算法

算法2：连续松弛最大团

1: 输入 A: 邻接矩阵； \bar{u}: 初始猜测

2: 输出 C: 构成最大团的顶点

3: 参数 \sigma \gets 0.01; \beta \gets 0.5; tol \gets 10^{-8}

4: M \gets A + I % 添加单位矩阵 I

5: \bar{M} \gets \mathbf {1} - M % 二进制补码为 M

6: u\gets \max (\bar{u}/\Vert \bar{u}\Vert,0); d\gets d_{0}; \alpha \gets 1

7: while u 不在二进制状态 do

8: M_{d} \gets M - d \, \bar{M}

9: F \gets u^\top M_{d} u

10: % 梯度投影到 S^{n} 切空间:

11: \nabla F_\perp (u) = 2 (I-uu^\top) M_{d} u

12: \Delta u \gets tol; \Delta F \gets tol

13: 当 \Delta u \nless tol 或 \Delta F \nless tol 执行

14: Armijo \gets \text{False}

15: while Armijo = \text{False} do % 回溯线搜索

16: u_+ \gets u + \alpha \nabla F_\perp (u) % 解更新

17: u_+ \gets \max (u_+/\Vert u_+\Vert,0) % 重新映射至 \mathbb {R}^{n}_+\cap S^{n}

18: F_+ \gets u_+^\top M_{d} u_+

19: \nabla F_\perp (u_+) = 2 (I-u_+ u_+^\top) M_{d} u_+

20: \Delta F \gets F_+ - F; \Delta u \gets u_+ - u

21: Armijo \gets (\Delta F \geq \sigma \nabla F_\perp (u)^\top \Delta u)

22: 如果 Armijo = \text{False} 那么

23: \alpha \gets \alpha \, \beta % 减少 \alpha

24: else \alpha \gets \alpha / \sqrt{\beta } % 增加 \alpha

25: u \gets u_+; \nabla F_\perp (u) \gets \nabla F_\perp (u_+); F \gets F_+

26: d\gets d + \Delta d % 增加 d

27: C \gets \lbrace i : u_{i} > 0\rbrace % 构成最大团的顶点

Optimization formulation: 在无向无权图中包含 n 个顶点的最大团问题可被表述为

\begin{align*} \begin{array}{ll}\underset{u \in \lbrace 0,1\rbrace ^{n}}{\text{maximize}} & \sum\limits _{i = 1}^{n}{u_{i}} \\ \text{subject to} & u_{i} \, u_{j} = 0 \quad \text{if}\, A(i,j)=0, \, \forall _{i,j} \end{array} \tag{1} \end{align*}

其中 A \in \lbrace 0,1\rbrace ^{n\times n} 是 邻接矩阵，当且仅当顶点 u_{i} 与 u_{j} 相连时对应元素为 A(i,j)=1。优化变量 u 是一个包含 n 元素的二进制向量，其中值为 1 的条目表示构成团的顶点。由于 u 为二进制，约束 u_{i} \, u_{j} = 0 在 A(i,j) = 0 成立时意味着如果顶点 u_{i} 或 u_{j} 断开，则最多只能选中它们之一。举例而言，考虑图 1，其邻接矩阵为 A，以及解候选 u, \bar{u} 如下

\begin{equation*} A = \begin{bmatrix}0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ \end{bmatrix}, \quad u = \begin{bmatrix}0 \\ 1 \\ 1 \\ 0 \\ 1 \\ \end{bmatrix}, \quad \bar{u} = \begin{bmatrix}1 \\ 0 \\ 0 \\ 1 \\ 0 \\ \end{bmatrix}. \tag{2} \end{equation*}

u 与 \bar{u} 均满足 (1) 中的约束。u 是全局最优解，目标值为 3（最大团的大小，即 u 中 1 的个数），而 \bar{u} 的目标值为 2。

通过定义 M \mathrel {\overset{{\text{ def}}}{=}}A + I，其中 I 是相应尺寸的单位矩阵，可以直观地证明问题 (1) 等价于

\begin{align*} \begin{array}{ll}\underset{u \in \lbrace 0,1\rbrace ^{n}}{\text{maximize}} & \frac{u^\top M \, u}{u^\top u} \\ \text{subject to} & u_{i} \, u_{j} = 0 \quad \text{if}\, M(i,j)=0, \, \forall _{i,j}. \end{array} \tag{3} \end{align*}

这可以通过观察 (1) 与 (3) 中的约束相同得出，即在解中不能同时选择相互不连通的顶点。进一步，如果 u^* 是 (3) 的一个最优解且其拥有 m 个条目，则 (3) 与 (1) 的目标值都将相同且等于 m（例如，在 (2) 中 u 与 \bar{u} 的目标值分别为 3 与 2，在 (3) 中亦为 3 与 2）。连续松弛: 为了克服问题 (3) 的 NP 难度，可以通过连续松弛获得近似解，其中二进域 {u \in \lbrace 0,1\rbrace ^{n}} 被放宽为非负实数集合 {u \in \mathbb {R}^{n}_+}。基于梯度的优化算法具有多项式时间复杂度，能够求解松弛后问题，并且松弛解可以投影/四舍五入为最近的二进解。此方法的问题在于无法保证二进化后的解满足原问题 (3) 的约束，因此可能不是可行解。

我们提出的针对该问题的 (3) 松弛是

\begin{align*} \begin{array}{ll}\underset{u \in \mathbb {R}^{n}_+}{\text{maximize}} & \frac{u^\top M_{d} \, u}{u^\top u}, \end{array} \tag{4}\\ M_{d}(i,j) \mathrel {\overset{{\text{ def}}}{=}}\left\lbrace \begin{array}{ll}M(i,j) & \text{if} \,\, M(i,j) \ne 0 \\ -d & \text{if} \,\, M(i,j) = 0 \end{array} \right. \tag{5} \end{align*}

其中 d > 0 是一个正标量。问题 (4) 可以等价地写为

\begin{align*} \begin{array}{ll}\underset{u \in \mathbb {R}^{n}_+}{\text{maximize}} & F(u) \mathrel {\overset{{\text{ def}}}{=}}u^\top M_{d} \, u \\ \text{subject to} & \Vert u \Vert = 1 \end{array} \tag{6} \end{align*}

其中 \Vert \cdot \Vert 是 \ell _{2} 向量范数。[^40] 我们的松弛 (6) 受到 Belachew 和 Gillis [^38] 的启发，它通过矩阵 M_{d} 将 (3) 中的约束整合到 (6) 中。与 [^38] 的区别在于，[^38] 中使用了松弛 \min _{u\in \mathbb {R}_+^{n}}\Vert M_{d} - u u^\top \Vert _{F}^{2}。直观上，任何条目 M_{d}(i,j) = -d 在目标函数中以 -2 \,d 的幅度惩罚相互不连通的顶点 u_{i} 与 u_{j} 的联合选择。因此，随着 d 的增加，违反团约束的 u 条目趋于零。

Optimality guarantees: 当 d\geq n（参见 (5)）时，所提出的松弛 (6) 的最优解理论上保证对应于原始最大团问题 (3) 的最优解。也就是说，(6) 的局部最优对应于最大团，(6) 的全局最优对应于最大团。证明这一陈述并不容易，感兴趣的读者应参考 [^38] 中的定理 3–5 以证明该松弛 \min _{u\in \mathbb {R}_+^{n}}\Vert M_{d} - u u^\top \Vert _{F}^{2} 的情况，以及 [^38] 中的定理 2 以建立我们所提出的松弛 (6) 的联系。

值得指出的是，(6) 的任何解都具有二元状态（这可见于 [^38] 的分析）。也就是说，解向量 u^* \in \mathbb {R}^{n}_+ 的每个元素要么为 0，要么等于正标量 c>0。这些正值表示形成最大团的顶点。需要注意的是，(6) 可以通过梯度基求解器在多项式时间内（局部）求解，并且 (6) 的最优解与（NP-hard）最大团问题 (3) 的最优解一一对应，人们可能认为最大团问题可以在多项式时间内解决。然而，请注意 (6) 是一个非线性优化问题，可能有许多局部最优点，且取决于初始猜测，求解器可能会收敛到局部最优而非全局最优。因此，寻找 (6) 的全局最优解仍然是 NP‑难问题。

算法 3：CLIPPER+

1: 输入 A: 邻接矩阵

2: 输出 C: 形成最大团的顶点

3: K \gets 计算顶点的核心数 % From [^39]

4: C \gets Algorithm1(A,K) % 按退化度排序的贪婪团

5: \mathcal {I}\gets \lbrace i : K(v_{i}) \geq |C|\rbrace % 核心数为 \geq 的顶点贪婪团大小

6: A^{\prime } \gets A(\mathcal {I},\mathcal {I}) % 裁剪图（仅保留 \mathcal {I} 中的顶点）

7: if A^{\prime } = \emptyset Terminate then % 已找到最大团

8: % pruned graph 中贪婪团的二进制补码:

9: \bar{u} \gets (\bar{u}_{i} : \bar{u}_{i}=0 \,\text{if}\, i \in C, \,\text{else},\, \bar{u}_{i}=1, \, \forall _{i\in \mathcal {I}})

10: C^{\prime } \gets Algorithm2(A^{\prime },\bar{u}) % 连续松弛团

11: if |C'| > |C| then C \gets C^{\prime } % 返回更大的团

优化算法: 我们提出了一个基于投影梯度上升方法的自定义求解器，用于 (6)，如算法 2 所述。我们的方法类似于我们之前工作 CLIPPER ⁵⁷ 的算法；然而，与 ⁵⁸ 相比，Algorithm 2 有了显著改进，并采用 Armijo 方法来选择合适的步长，从而得到更准确的结果（如我们在比较中所示）。

问题 (6) 是非线性的，通常具有许多局部最优点（对应于最大团）。为提高找到全局最优（最大团）并逃离局部最优的机会，Algorithm 2 采用了同伦方法，在外层循环（行 7-26）中逐步递增 d。随着惩罚参数 d 在外层循环的每一次迭代（第 26 行）中按 \Delta d 递增，违反团约束的 u 元素被进一步惩罚，u 收敛到一个可行解。该过程持续到 d 足够大（d\geq n）且 u 收敛到二进制状态，对应于最大团。\Delta d 的增量可以选择为一个小常数（如在 [^38] 中所做），然而，在我们的实现中，我们采用贪婪方案，逐步递增 d，直到违反团约束的 u 中最小的元素在下一次迭代中变为零。在最后一步（第 27 行）中，最大团的顶点被识别为 u 的非零元素。

内部循环（第13–25行）保证每一次 d 增量都能进行足够多的梯度上升迭代，使解 u 达到稳态。注意到优化问题（6）的约束流形是 \mathbb {R}^{n}_+ \cap S^{n}，其中 S^{n} 是单位球面，为了加快收敛，我们将梯度 \nabla F(u) \mathrel {\overset{{\text{ def}}}{=}}2 M_{d} \, u 投影到 S^{n} 在 u 处的切丛上，并沿着正交投影 \nabla F_\perp (u) = 2(I-u u^\top) M_{d} u 移动（第11行）。

为了在投影梯度方向上找到合适的步长 \alpha，我们采用回溯线搜索（第15–24行）配合 Armijo 步骤（第21–24行），这保证了每一次内循环迭代中目标函数足够的提升。该算法收敛到一阶最优点是由带 Armijo 步骤的投影梯度收敛性保证的 [^41]。解的更新在第16行计算，随后将其回退到约束流形（第17行），梯度上升过程继续进行，直至收敛。

Computational Complexity: Algorithm 2 的最坏情况时间复杂度为 \mathrm{O}(n^{4})。这是因为梯度计算（第19行）涉及矩阵-向量乘法，其复杂度为 \mathrm{O}(n^{2})，并且性能分析表明大部分时间都花在此处。回溯迭代次数（第15行）和梯度上升迭代次数（第13行）取决于参数和数据矩阵，但它们随问题规模呈线性增长（\mathrm{O}(n)），针对二次目标 F(u) = u^\top M_{d} u。最后，外循环迭代次数（第7行）取决于达到 d \geq n 所需的 \Delta d 步进（第26行），此时解必定收敛到二进制状态。这也随问题规模呈线性增长。

C. CLIPPER+ 最大团算法

Both Algorithms 1 和 2 是用于寻找最大团的算法。 The greedy approach of Algorithm 1 runs fast but gives relatively less accurate estimates of the maximum clique size when the graph is not sparse. 相反，Algorithm 2 的优化方法速度相对较慢，但更准确。 所提出的 CLIPPER+ 算法的主要动机是将这两种算法结合起来，从而结合它们各自的优势。

为实现这一组合，回想一下，core number 是一个顶点的最大整数 k，使得当移除所有度数小于 k 的顶点时，该顶点的度数仍非零。 If a graph contains a clique of size k, then each vertex in the clique must have a degree of k-1 or larger, and therefore a core number of k-1 or larger. 因此，如果我们希望找到更大的团，例如大小为 k+1 的团，则只有 core number 至少为 k 的顶点才可能成为候选。 Using this observation, CLIPPER+, detailed in Algorithm 3, first runs the greedy algorithm and obtains a maximal clique (line 4). 假设该团大小为 k，如果图中存在更大的团，则顶点的 core number 必须至少为 k。 Therefore, the algorithm prunes the graph by removing vertices with core numbers strictly less than k (line 6). 这种修剪通过减少顶点数来有效限制优化（line 10）的搜索空间，从而提升运行时间。

如果贪心算法恢复的团是最大团，则修剪图会移除所有顶点，从而我们可以提前终止（line 7）。 This early termination particularly occurs when the graph is sparse, which leads to a significant speed-up over running the optimization-based algorithm on the original graph.

当需要使用基于优化的算法时，用于优化的初始猜测可以被有策略地选择，以提高找到最大团的机会。这可以通过选择一个与贪心方法（第 9 行）找到的团的二进制补集相对应的初始猜测向量来实现，从而帮助算法收敛到不同的团解。最后，最佳解被选为最大的团（第 11 行）。

计算复杂度: 算法3的最坏情况复杂度是 O(n^{4})。这是因为它顺序组合了算法1和算法2，因此继承了其组成部分的最高最坏情况复杂度（算法3中的其他步骤复杂度更低）。这一基本的最坏情况复杂度分析与任何输入图结构无关。实验部分的数值结果很好地说明了该复杂度如何在实际应用中转换为不同图规模的运行时间。

第 V 节 实验评估

我们评估 CLIPPER+（算法 3）的性能，主要关注最大团估计精度和运行时间。此外，我们通过报告其独立的贪心（算法 1）和优化（算法 2）组件的结果，对 CLIPPER+ 进行了消融研究。我们证明，CLIPPER+ 通过组合这些组件，获得了优于单独组件的性能。

算法: 我们测试了经典方法和最先进的最大团估计算法。经典工作包括 Pelillo [^35] 和 Ding 等人 [^36]，它们基于 Motzkin‑Straus 形式化的松弛 [^37]。最先进的包括我们在算法 1 中实现的贪心并行最大团（PMC）算法 ⁵⁹（理论上等价于 ROBIN ⁶⁰）、Belachew 和 Gillis 的算法 [^38]，以及我们之前的 CLIPPER 算法 ⁶¹。

Benchmarks: 我们的评估研究在一般图上寻找最大团，以及从合成/真实世界点云配准问题的图形形式得到的图上寻找最大团。虽然一般图可以具有任意结构，但配准图具有某些模式（例如稀疏性），这会显著影响结果。幸运的是，正如我们将看到的，在配准得到的图上寻找最大团在经验上更容易。

Platform and implementations: 所有基准测试都在一台配备Intel Core i9处理器和32 GB RAM的机器上运行。Pelillo、Ding和Belachew的算法由其原作者在Matlab中实现。我们之前的工作CLIPPER也在Matlab中实现。 “Greedy”（算法1），“Optim”（算法2）以及CLIPPER+算法在C++中实现，并通过二进制MEX绑定器与Matlab接口进行基准测试。

A. 最大团基准—DIMACS

Dataset: 为了在一般图上评估算法，我们使用了DIMACS基准 [^42]，该基准于1996年首次提出，自那时起广泛用于最大团算法的基准测试。DIMACS数据集由寻找最大团具有挑战性的图组成。出于空间考虑，我们在该数据集中的一组较小图上展示结果，见表I。虽然DIMACS图相对较小（100–4000个顶点），但它们很密集，并且包含比配准得到的图更多的边。尽管该数据集已经存在超过25年，但某些图的最大团仍然未知，说明问题的难度。 例如，在C250.9图上，（多线程）PMC精确算法 ⁶²，用于本工作中的真值生成以及TEASER ⁶³ 的可认证配准， 在我们的机器上花费28分钟来找到最大团。

表 I

评价: 表 I 比较了算法的准确性和运行时间。图稀疏度定义为 s \mathrel {\overset{{\text{ def}}}{=}}1- \frac{|E|}{|E_{\max }|} \in [0,1]，其中 |E| 是图边的数量，|E_{\max }| 是可能的最大边数。s 的小值表明 DIMACS 图通常很密集。准确率通过 r\mathrel {\overset{{\text{ def}}}{=}}\hat{\omega }/\omega _{\text{gt}} 衡量，其中 \hat{\omega } 是算法找到的团大小，\omega _{\text{gt}} 是真实的最大团大小。比值为 1 表示已找到最大团，因此 r 越接近 1，算法的准确性越高。CLIPPER+ 在整体准确性方面优于所有算法。不出所料，贪婪算法由于其低计算复杂度具有最佳的整体运行时间；然而，它的准确性较低。通过结合贪婪算法和优化算法，CLIPPER+ 在准确性和整体运行时间上优于仅使用优化算法的方案（例如，\sim 将 brock200_2 上的运行时间从 29.4 毫秒减少 10 倍至 3.6 毫秒）。

B. 注册基准—Stanford Bunny

使用 Stanford Bunny 点云 [^43]（见图 2），我们评估 CLIPPER+ 作为在不同离群值范围内进行全局点云配准的算法。

图 2. 离群值对一致性图的影响。(左) 可能关联（红色：离群值；绿色：内点）。(右) 产生的一致性图。离群值比例越高，图越稀疏。

数据集： (下采样) 的兔子点云包含 1000 个点，适合放入尺寸为 0.2 \,\mathrm{m} 的立方体。为了生成第二个点云，我们在所有点上加入均匀噪声，范围为 [-\epsilon /2, \epsilon /2]，其中 \epsilon 被设为兔子点云中所有点到其最近邻点的平均距离。此外，还从半径为 1 \,\mathrm{m}、中心位于兔子点云的球体中随机抽取 1000 个离群点，用以模拟杂乱。在两点云之间所有可能的关联集合中，随机从内点和离群点关联集合中选取 200 个关联（我们保持此数目较小，以便能够找到真值最大团）。我们考虑不同的离群比例（从 0% 到 98%，每隔 2% 递增），以测试不同数据关联精度的场景， 如图 2 所示。我们使用噪声 \epsilon 作为阈值来生成一致性图（参照第 III 节）。真值最大团是通过在 ⁶⁴ 中运行精确 PMC 算法得到的。针对每个离群比例增量，进行 50 次蒙特卡罗运行/图的最大团估计准确性和运行时评估。

评估： 图 3 比较了所有运行和所有离群比例下算法的准确率比率 r。CLIPPER+ 明确展示了最高准确率，因为 r 的分布最接近 1。有趣的是，虽然贪婪和优化算法在某些情况下返回低准确率的解，但通过组合这些算法，CLIPPER+ 获得了超过这些单独组件的准确率。

图 3. 在斯坦福兔子基准上最大团估计准确率比率（越接近 1 越好）。每个点对应单次试验的准确率比率。CLIPPER+ 超越所有算法。

图 4 显示了准确率比率 r 的平均值（在每个离群百分比增量下平均 50 次蒙特卡罗运行）与离群百分比的关系。贪心方法在低离群比例区间的准确率较低（该区间拥有稠密的一致性图，见图 2）。随着离群百分比的增加并且图变得更稀疏，贪心方法的准确率提高。CLIPPER+ 与优化算法在所有离群百分比下都保持高准确率比率。

图 4. 在斯坦福兔子基准上，跨不同离群百分比的最大团估计准确率均值（越接近 1 越好）。

算法的平均运行时间如图 5 所示。优化方法的运行时间大致保持不变，而贪心方法的运行时间随离群比例增加并且图变得更稀疏而提升。CLIPPER+ 在低离群比例区间的运行时间大致等于其贪心和优化组件的合计运行时间，因为在此区间内基于核心数的图裁剪不会去除大量顶点（若有）。然而，随着离群比例的上升并且图变得更稀疏，裁剪会去除更多顶点，其加速效果更为明显。可见在约 20% 的离群比例处，CLIPPER+ 的速度超过优化方法，并且随着离群百分比的进一步增加，其速度还会进一步提升。

图 5. 在斯坦福兔子基准上，跨不同离群百分比的平均运行时间（越低越好）。

C. 注册基准 — 实际世界点云

Datasets: 我们使用真实世界的 7-Scenes [^44]、Sun3D [^45] 和 ETH [^46] 数据集（类似于 3DMatch ⁶⁵ 和 3DSmoothNet [^47] 的评估）。 Sun3D 和 7-Scenes 是密集的室内 RGB-D 点云，而 ETH 是户外 LiDAR 点云。 在每个序列中，我们考虑存在重叠的点云（或扫描）对。 为提高配准速度，我们通过将三维空间离散为尺寸为 \epsilon = 0.05 \, \mathrm{m} 的立方体来下采样 7-Scenes 和 Sun3D 数据集，并对 ETH 数据集使用尺寸为 \epsilon = 0.1 \, \mathrm{m} 的立方体，并使用每个立方体内点坐标的平均值作为单点代表。 对于每个下采样点，计算 FPFH 描述子向量 ⁶⁶，并根据其 l_{2} 范数距离使用 k 最近邻算法双向关联。 为生成我们评估的真值，我们使用 ⁶⁷ 的精确最大团算法，在这些潜在 FPFH 关联中找到最大的一组几何一致关联。 如果该最大团解根据数据集提供的真值正确地配准点云，我们将保存结果——最大团/似然解可能因实际限制（如重复模式（感知混淆）、点云间重叠不足以及由于下采样和 FPFH 不准确导致缺乏任何内点关联）而错误配准点。 在评估中，基于潜在 FPFH 关联，按第 III 节的方式生成一致性图，使用下采样阈值 \epsilon 作为一致性阈值。 评估实例如图 6 所示。

图 6. 7-Scenes 数据集两幅扫描的配准实例 [42]。从左到右：688 个假设的 FPFH 关联，其中 93.6% 为外点（红色线条）；对应的一致性图用于 CLIPPER+ 的输入（最大团被高亮显示）；对应最大团解的内点关联，由 CLIPPER+ 发现；使用 Arun 方法 [43] 计算得到的旋转/平移对齐的点云，利用内点.

评估: 表 II 介绍了所有数据集和算法的评估结果。CLIPPER+ 在所有数据集/序列上准确率上优于所有算法。 贪婪算法在牺牲整体最低准确率的前提下具有最短的运行时间。独立优化算法的准确率与 CLIPPER+ 相似。然而，除最后一序列外，其速度约慢两倍。这说明了 CLIPPER+ 相比其独立贪婪和优化组件的优势。

表 II

最后，我们指出 FPFH 关联的异常值比例很高（例如，wood_autumn 序列中平均有 99.4% 的关联为异常值）。由于最大团解法在我们的基准测试中正确对齐点云，准确率比率 r 显示了点云配准成功率。 于是，CLIPPER+ 在 99% 的试验中正确对齐点云，即使异常值比例极高。 这就是 CLIPPER+ 与现有稳健配准框架（如 RANSAC ⁶⁸）的区别，后者可能在这些高异常值环境下失败。

第六节：结论与未来方向

我们提出了 CLIPPER+，一种针对无权图的最大团寻找算法，可在机器人学和计算机视觉应用中实现稳健的全局配准。未来工作包括研究诸如二阶或拟牛顿方法等替代优化方法，以及基于我们之前的工作 ⁶⁹（为加权图设计）的加权图扩展和将核心数扩展到加权设置（在 [^48] 中研究）。我们还计划将该算法集成到点云配准管道 ⁷⁰ 中，作为异常值拒绝模块，以提高运行时性能和异常值拒绝能力。

脚注

1. 向量

u 可以写成 u = c u^{\prime } ，其中 c = \Vert u\Vert ，并且 u^{\prime } = u/c 是一个单位范数向量。将 u = c u^{\prime } 替换进 (4) 得到 \frac{u^\top M_{d} u}{u^\top u} = \frac{c^{2} {u^{\prime }}^\top M_{d} u^{\prime }}{c^{2} {u^{\prime }}^\top u^{\prime }} = {u^{\prime }}^\top M_{d} \, u^{\prime } ，证明与 (6) 等价。

. n : 图的顶点数。 s : 图的稀疏度。 \omega _{\text{gt}} : 真值最大团大小。 t : 运行时间（毫秒）；越低越好。 r : 最大团准确率比例（ \hat{\omega }/\omega_{\text{gt}} ），越接近1越好。

. N : 用于配准的重叠点云扫描总数。

. \bar{op} : 潜在关联中的离群比例平均值。

. \bar{n} : 平均图大小。

. \bar{s} : 平均图稀疏度。

. \bar{t} : 平均运行时间（毫秒）；越低越好。

. \bar{r} : 平均最大团准确率比例（ \hat{\omega }/\omega _{\text{gt}} ），越接近1越好。

参考文献

附加参考文献