这篇文章来自上海交通大学，发表于CVPR 2022。三维点云配准是三维视觉与点云相关任务中一个不可或缺的关键课题。早期最具代表性的工作当属ICP，它根据点匹配来估计输入点云之间的相对位姿。近年来，深度学习技术发展迅猛，基于学习的配准方法已成为主流，诞生了DeepVCP、DGR、Predator等一系列经典方法。然而，本文重新将目光投向非学习策略——通过聚类的方式，实现了相当先进的性能。更特别的是，它提出了一种新颖的问题设定：多实例点云配准（multi-instance point cloud registration），即同时估计某个实例的源点云与目标点云中多个实例的相对位姿。这听起来有点像多模态拟合，但区别在于，该方法对异常值鲁棒性更强，且时间效率极高。不过，非学习方法的通病它也没能完全避开——需要设置好几个阈值参数，这在实际应用中可能会带来一些不便。未来如果将深度学习技术与本文观察到的距离不变矩阵分布规律结合起来，或许是一个值得探索的方向。

论文标题：Multi-instance Point Cloud Registration by Efficient Correspondence Clustering

作者列表：Weixuan Tang and Danping Zou

摘要

我们解决的是多实例点云配准问题：源点云由一个实例的点云构成，目标点云由多个不同位姿的实例点云构成，同时求解多个相对位姿变换。现有方案需要对大量假设进行采样以检测可能的实例并排除异常值，但当实例和异常值数量增加时，鲁棒性和效率会显著下降。本文提出根据距离不变矩阵将带噪声的对应集合直接分组到不同的簇中——通过聚类自动识别实例和异常值。该方法鲁棒且快速。在合成和真实数据集上的评估表明：在存在70%异常值的情况下，可以正确配准多达20个实例，F1分数达90.46%，性能明显优于现有方法，速度至少快10倍。

主要贡献

1) 针对多实例点云配准问题提出了一种高效且鲁棒的解决方案，在准确性、鲁棒性和速度方面取得了卓越性能。
2) 提出三个指标（Mean Hit Recall、Mean Hit Precision、Mean Hit F1）来全面评估多实例点云配准的性能。
3) 该解决方案可潜在地用于3D目标检测。

问题建模

在多实例点云配准问题中，源点云X提供了一个3D模型的实例，目标点云Y包含该模型的K个实例，这些实例可能仅对3D模型的一部分进行采样。若将第k个实例记为，则目标点云Y可分解为。这里用表示点云中不属于任何实例的部分（异常值集合）。多实例三维点云配准的目标是找到将源点云实例X与每个目标实例点云对齐的刚性变换。如果能得到源实例与每个目标实例之间的对应关系，则第k个实例的位姿可通过最小化对齐误差之和从对应集合中求解：

假设已经获得源点云与目标点云之间的对应关系集合，那么多实例配准的关键是将这些对应关系分类到不同实例的单独集合中，即 ，其中表示异常值集合。可以看到，多实例配准不仅要排除异常对应，还要解决来自不同实例的对应之间的歧义。这并不容易，因为所有实例看起来一样，而且通常存在大量异常值对应。

Fig1：所提出的多实例点云配准方法的流程。从输入对应关系中构造距离不变矩阵，用于将对应关系聚类到不同簇并进行后续调整。最后，从每个对应集合中估计与每个实例的刚性变换。

方法介绍

所提方法的框架如图1所示。输入是点对应，然后通过检查对应关系之间的距离一致性构造不变的一致性矩阵。接着，把列或行向量视为这些对应关系的“特征”，将对应关系快速聚集到不同组中。聚类通过凝聚聚类高效完成——交替合并相似的刚性变换，并多次迭代重新分配聚类标签。如果对应数量很大，还可以应用下采样和上采样操作进一步处理。

一、不变性矩阵和兼容性向量

距离不变性在3D配准中已被充分探索，它描述了两点之间的距离经刚性变换后保持不变。即，若且是两个真正的对应，则应满足：

通过计算所有对应对之间的分数，获得距离不变矩阵（令）。该矩阵是对称的，每一列或每一行就是一个向量，描述给定对应关系与其他对应关系之间的兼容性。将列向量命名为对应c_i的兼容性向量。有意思的是，如果两个对应关系属于同一个实例，它们的兼容性向量具有相似的模式。考虑两个对应关系。对于任意对应，由于距离不变性有、。对于其他对应，很可能有、。换句话说，具有相似的0-1模式。相反，如果两个对应属于不同实例，它们的兼容性向量就会大不相同。图2给出了一个简单示例。兼容性向量可视为对应的特征表示。属于同一刚性变换的对应具有相似的特征。因此，基于这些兼容性向量，可以将对应关系聚类到不同组中——每组来自不同的实例，或者属于异常值。

Fig2. 距离不变矩阵中的列向量（兼容性向量）包含与实例相关的丰富信息。这里、表示第i个和第j个对应的兼容性向量，它们都在实例中。可以看到与相似。相比之下，与显著不同，因为第k个对应在不同的实例内。这里代表异常值集合。

二、快速对应关系聚类

采用自下而上的方式对对应进行聚类，这比现有的谱聚类方法快得多。一开始每个对应被视为一个单独的类，然后重复合并距离最小的两个类，直到两类之间的最小距离大于给定阈值。类间距离的定义方式会带来不同算法。这里定义如下：设为类i和j的表示向量，类间距离定义为

如果两个类合并，新类的表示向量通过更新，其中表示对两个向量的每个维度取最小值。聚类开始时，一个类（仅含一个对应）的表示向量设置为其兼容性向量。

三、迭代聚类调整

聚类之后，通过重复以下步骤进一步细化，直到不再变化：
Step1. 估计来自每个类的刚性变换（对应数量大于阈值α）。
Step2. 合并相似的变换。
Step3. 将类的标签重新分配给每个对应——每个对应分配给对齐误差最小的变换。如果对所有变换的最小对齐误差都大于内点阈值，则将该对应标记为异常值。
在迭代过程中，对应会越来越聚集，因此可以在Step1中调整α以增强异常值拒绝强度。使用以下策略在每次迭代中更新α：

其中表示第次迭代，N是对应数量，是取整操作。实验中设置和。实验表明，细化过程通常在三个迭代内收敛，因此非常高效。

四、合并相似的刚性变换

有时不同的对应类会产生相似的刚性变换，这意味着它们可能属于同一个实例，此时需要合并。给定两个估计的变换和，计算每个对应的对齐误差：。如果，则设置，否则设置。这样得到两个二元集合。合并两个变换的标准是

如果满足此标准，丢弃具有更多异常值的那个变换。然后根据所有变换中对齐误差最小的那个，将簇标签重新分配给每个对应。

五、从每一类提取刚性变换

聚类后需要从不同类的对应集合中提取刚性变换。由于不知道目标点云中实例的真实数量，需要自动选择内点对应类。首先选择元素数大于阈值的内点对应类，并估计这些类的刚性变换。接着按这些刚性变换的内点对应数，以降序排序——内点对应越多，与真实实例关联的机会越高。最后通过以下方式检查刚性变换与具有最多对应内点的刚性变换之间的内点对应数下降率：

其中表示第k个刚性变换的内点对应数。如果，则忽略第k个刚性变换之后的所有变换。此处的阈值可在召回率和精度之间灵活调整。