CVPR 2022 | 二阶相似性测度,让传统配准方法取得比深度学习更好的性能,并达到深度学习的速度…

关注公众号,发现CV技术之美

本文分享 CVPR 2022 论文『SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration』,二阶相似性测度,让传统配准方法取得比深度学习更好的性能,并达到深度学习的速度。

详情如下:

4e5d08daf491cfd086c36a87956a7e12.png

  • Authors: Chen Zhi, Sun Kun, Yang Fan, Tao Wenbing
  • 对应单位:华中科技大学、中国地质大学
  • 论文链接:https://arxiv.org/abs/2203.14453
  • 项目链接:https://github.com/ZhiChen902/SC2-PCR

      01      

introduction

针对3D点云配准中的误匹配消除任务,来自华中科技大学的研究团队提出了一种基于二阶空间兼容性度量的点云配准方法。具体来说,算法提出了一种二阶空间兼容性度量来计算匹配对之间的相似度,考虑了匹配对之间的全局兼容性而不是局部一致性,从而能够更加准确地度量正确匹配和错误匹配之间的差异。

论文从概率的角度分析了采样的有效性,证明了所提出的二阶度量可以大大提高采样入点集的概率。与传统的随机采样策略相比,只需少量采样即可获得有效的内部点集,从而估计点集之间的几何变换。基于所提出的二阶空间相容性度量,本文设计了一种基于种子点的快速匹配方法。与当前基于学习的方法和非学习方法相比,取得了更好的性能。

该方法最大的特点是不需要样本进行学习,因此不存在深度学习方法通​​常存在的泛化问题,但性能优于深度学习方法。它在计算效率方面也有突出的表现,接近目前最快的算法。同时,论文还通过实验验证了所提出的度量具有良好的可扩展性,可以直接与深度学习框架相结合。

      02      

研究动机

三维刚体点云配准旨在恢复两个具有重叠区域的点云之间的刚体变换。它是三维重建、即时定位与地图构建(SLAM)、虚拟现实等领域的重要基础,是计算机视觉中的基本问题。当前最常用的方法通过两步法进行点云配准:1、先为点云中的每个点提取局部特征描述子,并通过特征匹配建立粗略的点云对应关系;2、通过稳健的模型估计算法,从含有误匹配(外点)的粗匹配关系中寻找正确匹配(内点)并估计刚体变换。本研究主要关注如何在粗匹配中含有大量错误匹配的情况下进行点云配准。

RANSAC[1]最早采用迭代的策略来进行模型估计。然而,它需要大量的采样来保证算法的收敛,并且在内点率过低的情况下并不能保证一定能找到正确解。一些方法通过空间兼容性来解决RANSAC的问题,它利用刚体变换的一个性质:空间中任意两个点经过刚体变换之后长度不变。

因此,一阶空间兼容性度量认为如果两个匹配对之间的空间距离差(如图1(a)中的 或 )越小,他们的相似度越大。由于正确匹配对(内点)之间的空间距离差理论上应为0,这样两个内点的相似性就会比较大,从而在内点之间形成聚类效应。

eabde792055adffdb73ad0098ef58dd1.png

   图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节)。

a8c837cd7683bc9fac750324c299a690.png

 图2:方法总体流程图

3.1 二阶兼容性度量

为了分析用于抽样的度量的有效性,我们定义了歧义事件的概率:

83d92eb6ff73a332a824bc6c06a61f27.png

其中是事件发生的概率,是一个特定的度量。内部点和异常点之间的相似性,但是两个内部点之间的相似性。在这一点上,异常值成为内点的邻居,使得基于度量的采样不太稳定。因此,概率值越小,基于度量的采样越稳定。

我们首先介绍常用的一阶兼容性度量SC,它通常被定义为如下形式:

5a2f9ca71a9a52090cecbd572983dbdb.png

其中为一个单调递减函数,为两个匹配对之间的距离差。如前所述,由于刚体变换不改变任意两点的长度,因此两个内点之间的距离差理论应为0。然而,由于数据获取或点云采样时引入的噪声,不是绝对等于0,而只是可能小于一个阈值。为了方便推导,我假设在0到之间均匀分布,并且得到对应的概率密度函数如下:

1f63d97188e944fe379ffc7229aabfc1.png

同时,由于外点是随机分布的,因此任何两个外点或外点和内点之间都没有关系。对于两个不相关点之间的距离差(或),我们认为它们是同分布的,并将它们的分布表示为:

06f00e168602fa05f7ff1e74f8dc445a.png

其中为和的最大变化范围。为了直观地展示它们的分布,我们做出了在3DMatch数据集上函数的经验曲线,如图3所示:

735ef423e2c1d3b77b13af0c0cefff25.png

图3:F函数在3DMatch数据集上的经验分布图

显然,远远大于,因此我们可以近似在,之间是不变的,假设值为。接下来,我们计算一阶兼容性的模糊性概率。根据公式2,3,4可以得出:

bb4f0ba4a4aef5795ef20c92bab1f833.png

以3DMatch数据集为例。近似为10cm,那么一阶兼容性的模糊性概率约为0.1。考虑到外点的数量一般十分庞大,这样的模糊概率在采样时不能被忽略。

接下来,我们介绍所提出的二阶相容性,其形式为:

0f1123d5f8d96d4d242a1f84388dd65f.png

我们可以类似地推导出它的歧义概率。由于推导过程复杂,我们只写出我们推导的公式。具体推导过程请参考原论文附录:

91f6c828b8c35799a523e346fc5273b7.png

其中为内点率,为匹配对个数。为概率学中的Skellam分布。根据式5,7中的结论,我们分别做出了一阶和二阶度量的模糊性概率图,如图4所示:

3c3f1777a1023d466f26bdd5c248fefb.png

图4:一阶和二阶度量模糊性概率对比(SC^2-N,N=5000,2500,1000为匹配对个数)

从图中可以看出,所提出的方法可以大大降低歧义概率值,从而提高采样的稳定性。

3.2 种子点选取

如上所述,在矩阵中,内点之间有很高的相似性,那么只要我们找到一个内点,就可以通过找它的k个近邻来得到一个一致性集合。显然,遍历所有的匹配对一定可以找到一个内点,但是这是不必要的。我们只需要寻找一些可靠的种子匹配对来加速采样的过程。我们通过谱分解技术来进行种子点的查找。具体来说,我们首先构造匹配之间的相似度矩阵,然后通过谱分解技术确定每个匹配点是正确匹配的一个粗略的置信度,并将这个置信度结合局部极大值抑制操作确定一些种子点。

3.3 两阶段采样

在选择一些种子点过后,我们采用一个两阶段采样的方式将每个种子点扩充成一个一致性集合。在第一阶段,我们在 矩阵中寻找每个种子点的Top-K1近邻。由于所提出的度量发生模糊性的概率很小,因此当种子点是内点时,它对应的一致性集合里也主要都是内点。

第二个阶段进一步剔除第一个阶段中可能引入的误匹配。我们重新在每个一致性集合中构造了一个局部 矩阵,并选择每个种子点的Top-K2(K2

值得一提的是,我们只考虑种子点是内点的情况。当种子点为异常值时,也可以形成局部一致性,特别是在初始匹配中存在一些错误匹配的补丁时。我们在采样期间保留这些结果,并在最终模型选择期间过滤正确的刚体模型。这可以防止过于严格的种子点策略导致某些正确的模型被忽略。

3.4 模型生成与选择

在得到一些一致性匹配集合后,我们采用加权奇异值分解(SVD)来为每个集合估计一个刚体变换。我们在每个集合中构建局部相似度矩阵,并利用谱匹配技术为每个匹配对分配一个权重。然后将这个权重用于SVD分解,从而得到估计的旋转变换和平移变换。对于每个估计出来的变换,我们使用和RANSAC同样的内点计数准则来评价模型的质量:

b8614e8a77d0a6e2222c4e85eb619629.png

其中 [] 是艾弗森括号。最后我们选择得分最高的模型作为最终的刚体变换结果。

      04      

实验结果

4.1 数据集和评价指标

我们分别在室内配准数据集3DMatch,室内低重叠率配准数据集3DLoMatch和室外数据集KITTI上对方法进行了评测。为了更充分地对方法进行验证,我们分别将方法与不同的描述子结合,所采用的描述子包括FPFH、FCGF和Predator。评价指标包括配准召回率(RR)、旋转误差(RE)、平移误差(TE)、分类精度(IP)、分类召回率(IR)、分类F1-measure(F1)和运行时间。

4.2 总体结果

所提出的方法与其他方法的在三个数据集上的对比结果如表1,2,3所示。从表中可以看出,所提出的方法优于传统方法和基于深度学习的方法,并且在效率上也可以达到接近深度学习方法的速度。

表1:3DMatch数据集上的结果 

8dcef41c2726864d6e80b470b21f20f5.png

表2:3DLoMatch数据集上的结果   

43d8ca5bd4cb9a3379cddb33763c3b80.png

表3:KITTI数据集上的结果   

1816675055772f1a5678a9e0a4e54123.png

4.3 低内点率配准   

5275fe8a27d4a6d791a88201d16b7e58.png

图5:低内点率下的配准召回率

在某些极端情况下,描述子建立的匹配中会含有大量的误匹配,正确匹配的比例可能低于1%。为了验证在不同内点率下算法的稳定性,我们根据内点率将数据集划分为六组,并统计了不同方法在这些内点率下的配准召回率,如图5所示。从图中可以看出,我们的方法对于低内点率更稳定,尤其是在内点率低于2%时。

4.4 与深度学习框架结合   

表4:与深度学习框架结合的性能对比(*-gen表示泛化性实验)

c692d3b25d0cd60804e91b917601ffe9.png

为了验证所提出的二阶兼容性度量的可扩展性,我们将它与当前最好的深度学习方法PointDSC结合。从表4中可以看出,度量可以提升深度学习方法的性能,尤其是泛化性。

4.5 消融实验

所提出所有模块的消融实验如表5所示。我们以传统的RANSAC为baseline,逐步添加所提出的模块。其中:SC为一阶兼容性引导的采样;为二阶兼容性引导的采样;TS为二阶段采样方式;LSM为基于局部谱匹配的姿态估计方式;Seed为引入种子点提高算法效率。

表5:消融实验   

36921ac048528c14bc3e7c1ea7311c8f.png

4.6 定性实验结果

图6中展示了一些可视化的配准结果对比。

31eeb3af9b5116e5904127af442fd1de.png

图6:定性配准结果对比

references

[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.

059feabca9135e4075983010d0ddbd71.png

END

欢迎加入“点云”交流群👇 注:点云

d4a81215a05937845969937435809340.png

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2022年5月8日
下一篇 2022年5月8日

相关推荐