关注公众号，发现CV技术之美
本文分享 CVPR 2022 论文『SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration』，二阶相似性测度，让传统配准方法取得比深度学习更好的性能，并达到深度学习的速度。
详细信息如下：
- 论文作者：陈志，孙琨，杨帆，陶文兵
- 通讯单位：华中科技大学，中国地质大学
- 论文链接：https://arxiv.org/abs/2203.14453
- 项目链接：https://github.com/ZhiChen902/SC2-PCR
01
引言
针对3D点云配准中的误匹配消除任务，来自华中科技大学的研究团队提出了一种基于二阶空间兼容性度量的点云配准方法。具体来说，算法提出了一种二阶空间兼容性度量来计算匹配对之间的相似度，考虑了匹配对之间的全局兼容性而不是局部一致性，从而能够更加准确地度量正确匹配和错误匹配之间的差异。
论文从概率的角度来分析采样的有效性，并证明了所提出的二阶度量能够大幅度提高采样内点集合的概率。相比传统的随机采样策略而言，仅通过少数几次采样就能够得到有效的内点集合估计出点集之间的几何变换。基于所提出的二阶空间兼容性度量，论文设计了一套基于种子点的快速匹配方法。与当前基于学习的方法和非学习的方法相比，均取得了更好的性能。
该方法最大的特点是不需要样本进行学习，因此没有深度学习方法通常存在的泛化性问题，但具有比深度学习方法更好的性能。在计算效率方面也表现突出，接近当前最快的算法。同时，论文也从实验验证了所提出的度量具有很好的可扩展性，可以直接与深度学习框架相结合。
02
研究动机
三维刚体点云配准旨在恢复两个具有重叠区域的点云之间的刚体变换。它是三维重建、即时定位与地图构建（SLAM）、虚拟现实等领域的重要基础，是计算机视觉中的基本问题。当前最常用的方法通过两步法进行点云配准：1、先为点云中的每个点提取局部特征描述子，并通过特征匹配建立粗略的点云对应关系；2、通过稳健的模型估计算法，从含有误匹配（外点）的粗匹配关系中寻找正确匹配（内点）并估计刚体变换。本研究主要关注如何在粗匹配中含有大量错误匹配的情况下进行点云配准。
RANSAC[1]最早采用迭代的策略来进行模型估计。然而，它需要大量的采样来保证算法的收敛，并且在内点率过低的情况下并不能保证一定能找到正确解。一些方法通过空间兼容性来解决RANSAC的问题，它利用刚体变换的一个性质：空间中任意两个点经过刚体变换之后长度不变。
因此，一阶空间兼容性度量认为如果两个匹配对之间的空间距离差（如图1（a）中的 或 ）越小，他们的相似度越大。由于正确匹配对（内点）之间的空间距离差理论上应为0，这样两个内点的相似性就会比较大，从而在内点之间形成聚类效应。
图1：一阶与二阶兼容性度量对比。（a）两对点云之间的匹配关系（红色为错误匹配，绿色为正确匹配）（b）一阶兼容性矩阵；（c）二值化一阶兼容性矩阵；（d）二阶兼容性矩阵
然而一阶兼容性存在模糊性，即外点也有可能与内点有很高的相似度。为了直观地说明这个问题，我们在图1（a）中展示了两对点云之间的匹配关系（红色为错误匹配，绿色为正确匹配）。同时，我们在图1（b）中展示了任意两对匹配对之间的一阶兼容性。从图中可以看出，外点和内点之间可能会存在着很高的相似性（黄色底纹的方格），这就是一阶兼容性的模糊性问题。
当前一些研究通过传统方法（如三元组约束）[2,3]或深度学习框架[4,5]来减轻模糊性带来的问题，虽然一定程度上缓解了这一问题，但是在内点率很低的情况下有时也会失效。在我们的研究中，我们提出一个新的全局测度来度量两个匹配对之间的相似性。具体来说，我们首先二值化一阶空间兼容性测度（1代表两个匹配对是兼容的），如图1（c）。
然后对于任意两个兼容的匹配对，我们计算与它们共同兼容的匹配对的个数作为它们的相似性。换句话说，我们计算同时与这两个匹配对都兼容的匹配的数量作为它们之间新的相似性，而如果它们本身不兼容，那么就认为它们的相似性为0。由于内点之间都是相互兼容的，因此任意两个内点之间的相似度至少为所有匹配对中内点的个数（除去这两个匹配对自身），而内点和外点之间并没有这样的性质。如图1所示，{c1,c2,c3,c4,c5}是内点，而{c6,c7}为外点。
从图1（b）和（c）中可以看出，外点{c6,c7}与某些内点有很高的相似性，而图1（d）中则抑制了这种情况。具体来说，在图1（d）中，{c1,c2,c3,c4,c5}之间的相似性不小于3，而外点{c6,c7}与其他点的相似性均小于1。因此，新提出的测度可以更好的区分内点和外点。由于新提出的测度可以被表示为一阶测度的乘积形式，因此我们称这种新提出的测度为二阶相似性测度。
所提出二阶测度有三个优点：
- 利用二阶测度可以更好地区分内外点。假设在对匹配中有对正确匹配，内点之间的相似性应大于，而外点与内点之间的相似性很小；
- 传统的算法如RANSAC需要大量的随机采样来得到一组没有外点的集合，而利用所提出的二阶兼容性矩阵，在每个内点所对应的行中，我们可以通过寻找top-k个近邻来得到一个一致性集合。这样，只要遍历N行就可以找到M个没有外点的集合，从而大大提升采样的稳定性和效率。
- 我们从概率的角度证明了所提出的二阶兼容性可以减少错误采样的概率。具体来说，我们定义了一个模糊事件，即外点和内点的相似性比内点之间相似性高这一事件。我们分析了一阶兼容性和所提出的二阶兼容性的模糊事件概率，可以证明所提出的度量更稳定。
03
方法介绍
方法流程图如图2所示。具体来说，方法的输入是利用特征描述子生成的粗匹配。我们首先构建逐匹配的矩阵（3.1节）。然后，我们通过谱分解的方式结合局部极大值抑制选择一些可靠的匹配作为种子点，目的是减少采样次数来提升算法效率（3.2节）。
在这之后，我们通过一个两阶段的采样方式为每个种子点构造一个一致性集合（3.3节）。最后，我们通过局部谱匹配的方式结合可微的奇异值分解来为每个一致性集合求解一个刚体变换，并选择最好的估计作为最终结果（3.4节）。
图2：方法总体流程图
3.1 二阶兼容性度量
为了分析用于采样的度量的有效性，我们定义了一个模糊性事件的概率：
其中是事件发生的概率，是一个具体的度量。内点和外点之间的相似度，而是两个内点之间的相似度。当时，外点就会变成内点的近邻，从而基于度量的采样就越不稳定。因此该概率值越小，则基于度量的采样越稳定。
我们首先介绍常用的一阶兼容性度量SC，它通常被定义为如下形式：
其中为一个单调递减函数，为两个匹配对之间的距离差。如前所述，由于刚体变换不改变任意两点的长度，因此两个内点之间的距离差理论应为0。然而，由于数据获取或点云采样时引入的噪声，不是绝对等于0，而只是可能小于一个阈值。为了方便推导，我假设在0到之间均匀分布，并且得到对应的概率密度函数如下：
同时，由于外点是随机分布的，因此任意两个外点或者一个外点和一个内点之间是没有任何关联的。对于两个没有关联的点之间的距离差（或），我们认为它们是同分布的，并且将它们的分布记为:
其中为和的最大变化范围。为了直观地展示它们的分布，我们做出了在3DMatch数据集上函数的经验曲线，如图3所示：
图3：F函数在3DMatch数据集上的经验分布图
显然，远远大于，因此我们可以近似在，之间是不变的，假设值为。接下来，我们计算一阶兼容性的模糊性概率。根据公式2，3，4可以得出：
以3DMatch数据集为例。近似为10cm，那么一阶兼容性的模糊性概率约为0.1。考虑到外点的数量一般十分庞大，这样的模糊概率在采样时不能被忽略。
接下来，我们介绍所提出的二阶兼容性，它具有如下形式：
我们可以同样的推导出它的模糊性概率。由于推导过程比较复杂，因此我们仅写出我们推导出的公式，具体推导过程可以参考原论文的附录部分：
其中为内点率，为匹配对个数。为概率学中的Skellam分布。根据式5，7中的结论，我们分别做出了一阶和二阶度量的模糊性概率图，如图4所示：
图4：一阶和二阶度量模糊性概率对比（SC^2-N,N=5000,2500,1000为匹配对个数）
从图中可以看出，所提出的方法可以大大降低模糊性概率值，从而提升采样的稳定性。
3.2 种子点选取
如上所述，在矩阵中，内点之间有很高的相似性，那么只要我们找到一个内点，就可以通过找它的k个近邻来得到一个一致性集合。显然，遍历所有的匹配对一定可以找到一个内点，但是这是不必要的。我们只需要寻找一些可靠的种子匹配对来加速采样的过程。我们通过谱分解技术来进行种子点的查找。具体来说，我们首先构造匹配之间的相似度矩阵，然后通过谱分解技术确定每个匹配点是正确匹配的一个粗略的置信度，并将这个置信度结合局部极大值抑制操作确定一些种子点。
3.3 两阶段采样
在选择一些种子点过后，我们采用一个两阶段采样的方式将每个种子点扩充成一个一致性集合。在第一阶段，我们在 矩阵中寻找每个种子点的Top-K1近邻。由于所提出的度量发生模糊性的概率很小，因此当种子点是内点时，它对应的一致性集合里也主要都是内点。
第二个阶段进一步剔除第一个阶段中可能引入的误匹配。我们重新在每个一致性集合中构造了一个局部 矩阵，并选择每个种子点的Top-K2（K2<K1）近邻作为新的一致性集合。如图4所示，在 度量中，内点率越高模糊性事件发生的概率越低。所以第二阶段在第一阶段滤除一部分外点之后进行选择，可以得到更好的结果。
值得一提的是，我们只考虑了种子点是内点的情况。当种子点是外点时，它也可以形成局部的一致性，尤其是在初始匹配中有一些成片的错误匹配时。我们在采样时保留这些结果，并在最后的模型选择时再筛选正确的刚体模型。这样可以防止太严格的种子点策略导致有些正确的模型被忽略了。
3.4 模型生成与选择
在得到一些一致性匹配集合后，我们采用加权奇异值分解（SVD）来为每个集合估计一个刚体变换。我们在每个集合中构建局部相似度矩阵，并利用谱匹配技术为每个匹配对分配一个权重。然后将这个权重用于SVD分解，从而得到估计的旋转变换和平移变换。对于每个估计出来的变换，我们使用和RANSAC同样的内点计数准则来评价模型的质量：
其中[]是艾弗森括号。最后我们选择得分最高的模型作为最终的刚体变换结果。
04
实验结果
4.1 数据集和评价指标
我们分别在室内配准数据集3DMatch，室内低重叠率配准数据集3DLoMatch和室外数据集KITTI上对方法进行了评测。为了更充分地对方法进行验证，我们分别将方法与不同的描述子结合，所采用的描述子包括FPFH、FCGF和Predator。评价指标包括配准召回率（RR）、旋转误差（RE）、平移误差（TE）、分类精度（IP）、分类召回率（IR）、分类F1-measure（F1）和运行时间。
4.2 总体结果
所提出的方法与其他方法的在三个数据集上的对比结果如表1，2，3所示。从表中可以看出，所提出的方法优于传统方法和基于深度学习的方法，并且在效率上也可以达到接近深度学习方法的速度。
表1：3DMatch数据集上的结果
表2：3DLoMatch数据集上的结果
表3：KITTI数据集上的结果
4.3 低内点率配准
图5：低内点率下的配准召回率
在某些极端情况下，描述子建立的匹配中会含有大量的误匹配，正确匹配的比例可能低于1%。为了验证在不同内点率下算法的稳定性，我们根据内点率将数据集划分为六组，并统计了不同方法在这些内点率下的配准召回率，如图5所示。从图中可以看出，我们的方法对于低内点率更稳定，尤其是在内点率低于2%时。
4.4 与深度学习框架结合
表4：与深度学习框架结合的性能对比（*-gen表示泛化性实验）
为了验证所提出的二阶兼容性度量的可扩展性，我们将它与当前最好的深度学习方法PointDSC结合。从表4中可以看出，度量可以提升深度学习方法的性能，尤其是泛化性。
4.5 消融实验
所提出所有模块的消融实验如表5所示。我们以传统的RANSAC为baseline，逐步添加所提出的模块。其中：SC为一阶兼容性引导的采样；为二阶兼容性引导的采样；TS为二阶段采样方式；LSM为基于局部谱匹配的姿态估计方式；Seed为引入种子点提高算法效率。
表5：消融实验
4.6 定性实验结果
图6中展示了一些可视化的配准结果对比。
图6：定性配准结果对比
参考文献
[1] Martin A Fischler and Robert C Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM.
[2] Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun. Fast global registration. In European Conference on Computer Vision, pages 766–782. Springer, 2016.
[3] Siwen Quan and Jiaqi Yang. Compatibility-guided sampling consensus for 3-d point cloud registration. IEEE Transactions on Geoscience and Remote Sensing, 58(10):7380–7392, 2020.
[4] Xuyang Bai, Zixin Luo, Lei Zhou, Hongkai Chen, Lei Li, Zeyu Hu, Hongbo Fu, and Chiew-Lan Tai. Pointdsc: Robust point cloud registration using deep spatial consistency. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15859–15869, 2021.
[5] Junha Lee, Seungwook Kim, Minsu Cho, and Jaesik Park. Deep hough voting for robust global registration. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15994–16003, 2021.
