论文标题：Performance Evaluation of 3D Correspondence Grouping Algorithms

作者：Jiaqi Yang, Ke Xian, Yang Xiao and Zhiguo Cao

译者：仲夏夜之星

下载地址：https://arxiv.org/pdf/1804.02085.pdf

摘要：本文针对几种广泛使用三维对应关系聚合算法进行了深入的评价，其目的在于他们在视觉任务中的意义依赖于正确的对应特征关系，一个良好的对应关系的聚合算法的期望是可以从初始的特征匹配中搜索到尽可能多的关系，从而提高准确率和召回率，就这个规则，本文从三个方面分别是处理形状检索、三维目标识别及点云配准来进行实验，该方法受噪音、不同点密度的细微差别、杂波、遮挡和部分重叠的影响，这将会导致内点和对应分布比率的不同而造成结果不同，基于定量结果分析，本文对其总结了优缺点并从性能和效率两方面进行了评估。

一 、引言

建立三维点云之间的正确匹配关系，也称为点云配准问题，这在三维计算机视觉中是一个基石。一个至关重要的原因是基于局部形状特征的匹配方式的应用，如三维对象识别，点云注册、形状检索和三维对象分类非常流行。基于局部特征的匹配方式如图1，首先检测表面上的一组独特的关键点并用特征描述符表示局部形状几何，然后生成原始初始匹配用于识别两种形状之间的相似性。然而，这个方式总会出现大量的虚假匹配，主要有两个原因，一个是加载前一个模块的残差，例如，关键点定位错误和重复结构中的特征描述符的不匹配，另一个是其他因素的干忧，包括噪音，不同点密度、杂波、遮挡和部分重叠。为了确保后续变换估计或假设生成的准确性，希望有更高的精度从原始特征匹配中过滤，突显出对应关系分组的重要性。

图1 基于局部特征匹配的算法流程

一种流行的对应分组算法是从最初的特征中找到尽可能多的内部线性匹配，可以增加精度和召回率[5]。类似于二维图像域的趋势，最近研究的热点话题是特征由三维对应分组相关算法来驱使特征匹配的视觉任务，如三维对象识别和三维重建。除了重新探索比较流行的二维对应分组技术，如三维领域的相似性分数(SS)，最近邻相似比（NNSR），随机抽样一致性(RANSAC)和光谱技术(ST)，我们也可以找到许多最近的三维目标算法，如几何一致性(GC)，聚类，博弈论，3D霍夫投****(3DHV)，和线性搜索(SI)等。随着广泛的三维对应分组算法的不断更新，这些算法的有效性通常在特定的数据集上进行评估有限数量的细微差别和比较，因此研究学者很难选择合适的算法并给出了一个特定的应用范围。为此，对于七种最先进的三维对应分组算法只要有SS、NNSR、RANSAC、ST、GC、3DHV和SI，本文提出了一个全面的评价，这是对三维对应关系分组算法的最新的全面的评估，据我们所知，它考虑了经典和最新的方法对涉及各种应用的基准和其他干扰进行评估。本文用精确率和召回率两个评价指标来测量定量性能，保证分组的对应关系和从原始特征匹配的大量线性关系的准确性来进行平衡的检查。此外，我们将应用的上下文考虑在内，具体来说，不同的应用将导致不同比例的差异和空间初始特征匹配的位置，主要是由于不同干扰的类别和程度来掩盖这些问题，我们分别对实验博洛尼亚三维检索(B3R)，UWA三维对象识别和UWA三维建模数据集进行实验来检查这些三维对应分组算法。B3R数据集测试了关于噪声和变化点的算法密度评估结果的鲁棒性，U3OR数据集测试了关于杂波和遮挡的性能，U3M数据集测试了部分重叠的数据的影响，这些干扰全部都已经被量化，以便进行详细的比较。总之，本文的贡献主要有：

（1）本文对七种主流的对应关系分组算法进行了定量评价，主要是关于不同干扰包括噪声、点密度变化、杂波、遮挡和部分重叠下的三个基准的比较，还测试了不同数量的初始匹配的时间效率。

（2）本为给出了针对不同算法的局限性以及优缺点。

本文的结构安排为：第二部分主要介绍七种最新算法中的每个核心计算步骤，第三部分主要验证不同数据集的评估方法以及算法的实施细则，第四部分为实现结果介绍，第五部分为本文的总结。

二 、三维对应关系分组算法

最近邻相似比：本文评估的算法的另一个基线为洛必达规则，它对应的关系是特征空间中最近点和第二最近点的距离，可以用独特的区域出口来匹配高分数，其类似于SS的阈值策略，如果满足：

三维霍夫投****：霍夫变换是一个比较流行的计算机视觉技术最初被用来检测图像的线性关系，在3DHV中，每个对应关系在基于霍夫变换空间的基础上投****。

线性内部搜索：该算法是最近一项旨在解决3D问题的对应关系配准的问题，其核心思想是结合局部和全局特征描述以确定是否应该投****，本文将该算法总结为三个主要步骤，初始化、局部投****和全局投****。

三 、评估方法

在第二部分中提到的所有算法已经在选定的三个基准上进行评价，其中包括不同水平的噪声、点密度变化、杂波、遮挡和局部重叠，所有算法的计算的内点线性关系使用精确率和召回率来进行测量，本节还介绍了每个算法的实现细节。

3.1 数据集

数据集主要包括B3R Dataset、U3OR Dataset、U3M Dataset，如图2所示。

3.2 评价标准

3.3 实施细节

本文评估算法的输入，即初始对应集C，通过Harris 3D关键点检测、SHOT特征描述和L2距离特征匹配生成。在默认设置中，我们将Harris三维探测器的Non Maxima-Suppression半径设为3pr，为包含十万个点的点云生成约1000个关键点。SHOT的支撑半径为15pr，而判断阈值等于4pr。关于每个算法的参数，我们将它们列入表1。值得注意的是，我们对tss进行自适应使用，因为一个固定值是很难转向不同质量的特征匹配。NNSR和SI算法中的阈值与其原始文献中的阈值保持一致。对于ST和GC算法，它们的阈值是通过调整实验确定的。在RANSAC算法中，考虑到初始对应集的大小，分配10000个循环在有效性和效率之间达到平衡。

四 、实验结果

4.1 B3R数据集上的性能

对噪声的鲁棒性：噪声对特征描述子的区分能力产生影响，从而产生一定量的虚假匹配。而在检索上下文中，由于B3R数据集中所使用的模型具有丰富的几何信息，inliers的比例通常较高。在这种情况下的结果如图3(a)所示。从图中可以看出，从总体查准率和召回性能来看，RANSAC和SI似乎是所有评估建议中最好的两个。一个有趣的发现是，在极端噪声的情况下，NNSR甚至超过GC和3DHV。这是因为NNSR倾向于选择不同的对应关系，这在该数据集上是特别充分的，因为模型具有丰富的独特结构。而NNSR的召回率则保持在除SS之外的其他算法的较低。SI算法在高斯噪声标准差小于0.15pr时具有良好的性能，当噪声进一步严重时，其性能会出现明显恶化，表明其对高高斯噪声的敏感性。

对点密度变化的鲁棒性：与噪声类似，这个术语也影响描述符的独特性。我们给出了图3(b)中不同点密度下的结果。我们可以观察到，这些算法在点密度变化影响下的性能与在噪声下的性能类似。例如，RANSAC和ST再次给出最好的整体性能，其次是NNSR，3DHV和GC，但不同的是，在精度方面，当降采样比达到0.3时，SS甚至优于SI，而在低分辨率情况下，NNSR和SI的召回性能均大幅下降，这是因为SHOT对不同的点密度非常敏感，使得对于高分辨率的数据，特征具有弱的区分性(如NNSR原理)，虽然SI的原因是SHOT的LRF (例如，SI的全球投****阶段的组成部分)在面对数据分辨率变化时的可重复性较小。

4.2 U3OR数据集的性能比较

对杂波的鲁棒性：杂波是场景中非模型表面斑块面积的百分比。在特征匹配过程中，杂波区域的表面贴片与模型中的贴片具有相似的几何特性，会引起异常值。杂波量化电平的结果如图3 (c)所示。由于三维目标识别场景比检索更具挑战性[2]，所有算法都会出现明显的性能下降，当杂波程度小于75%时，RANSAC达到最好的精度性能。随着杂波程度的进一步增大，3DHV给出的性能最好。值得注意的是，ST算法在B3R数据集上表现最好，在U3OR数据集上表现相当差，这是因为ST试图寻找大的等距保持的簇，这些簇很少在杂波百分比较高的场景中退出，在召回性能方面，SS、SI和GC表现优于其他，权衡精度和召回率，3DHV和GC是杂波影响下的两种最优越的算法。

对遮挡的鲁棒性：遮挡会导致形状补丁不完整，给精确的特征描述带来巨大挑战。遮挡程度给定为被遮挡模型表面贴片与模型总面积的比值，如图3（d）所示，当遮挡程度小于70 %时，RANSAC精度性能最好，随着遮挡程度增加到75%，GC优于RANSAC为最佳。当遮挡程度超过75%时，GC、SI和3DHV最终超过其他算法。在召回性能方面，对于所有级别的遮挡，SI均优于其他所有算法，特别是在高度遮挡的场景，SS和ST仍然是本测试中性能较差的两种算法。我们可以推断，基于一致性的算法，如RANSAC和GC等，更适合于有遮挡的场景，而基于初始特征匹配分数的算法，如SS和SI，在处理虚假匹配时具有较高的风险，因为从遮挡的场景块测量的特征匹配分数是可疑的。

4.3 U3W数据集的性能对比

对部分重叠的鲁棒性：U3M数据集提供了不同程度重叠的匹配对。重叠度度量为两个形状对应顶点数与最小顶点数之比，不同重叠度的结果如图3(e)所示。所有算法的共同特点是，它们的性能通常随着重叠程度的降低而下降。这是由于初始对应集中异常值的比率与重叠区域的比率密切相关。在精度性能方面，RANSAC在60%~80%的重叠度范围内，对于所有级别的重叠度，一般都会大幅度超过其他，GC和ST表现相当，其次是3DHV、NNSR、SI和SS，在召回率方面，SI优于其他，尤其是重叠度小于70%时。

4.4 可变阈值ε的性能比较

阈值决定了我们在多大程度上将通信判断为inlier。我们特此改变此阈值(默认设置为4pr )，以考察被评价算法的性能变化。具体而言，我们在整个U3OR数据集上进行实验，结果如图3(f)所示。正如预期的那样，所有算法都能以更宽松的方式获得更高精度的结果，特别是当阈值在[ 2pr，5pr ]和[ 6pr，10pr ]范围内时，GC和RANSAC分别达到了最高的精度，SS的精度有微弱的提高，说明其判断的多数inlier偏离了地面真实inliers，在召回率的inliers方面，随着阈值的增大，SI和SS呈现增加的趋势，而其他算法的性能几乎不变。

4.5 不同初始条件的性能对比

针对不同的应用，需要不同数量的初始对应，例如形状变形的密集匹配和粗扫描对齐的稀疏匹配。为此，我们在U3OR数据集上测试了这些算法对不同数量的初始对应的性能，如图3(g)所示。该图表明，不同的算法在改变初始特征匹配数量时给出的响应不同，一些算法，如GC，RANSAC和3DHV的性能随着初始匹配数目的增加而波动，同时，可以发现初始对应集的大小对SI和ST算法的影响相对较强。具体来说，当初始对应数小于1000时，这两种算法产生的精度较低，然而，随着初始特征匹配变得密集，即1000多个对应，SI和ST的精度性能迅速攀升，SI算法甚至以大约3000个初始对应达到了次优精度，这是由于密集的初始对应关系能够在SI的局部合并表决集中提供更可靠的成分，尽管如此，SI在初始对应集的所有测试尺寸下都取得了最好的召回性能，以较大的差距超过了其他所有尺寸。

图3 （a-g）7种对应分组算法在实验数据集上的准确率和召回率性能。(h) 同大小的初始对应集的时间效率性能，其中y轴取对数为最佳视图。

五、结论

本文在多种数据集上对三维对应分组算法进行了深入的评价，评价指标包括在不同噪声水平、点密度变化、杂波、遮挡、部分重叠、内点判断阈值、初始特征匹配大小和计算效率下的查准率和召回率。鉴于这些评价结果，总结如下：

（1）SS和NNSR作为依赖特征匹配相似性的两个基线，对杂波、遮挡和部分重叠等干扰非常敏感。给定具有丰富几何结构的高质量形状，NNSR可以是一个同时提供实时性能的有效选择。

（2）ST算法对含有大量内点的对应集是有效的，但在三维目标识别和2.5维视图匹配等挑战性环境下，ST算法的性能急剧下降。同样，ST也被证明非常耗时，特别是对于大规模的对应问题。

（3）RANSAC在多种干扰下表现出优越的精度性能，以牺牲相对较长的执行时间为代价。因此，RANSAC适用于依赖稀疏匹配的离线应用，如扫描配准和三维建模。

（4）3DHV是一种超高效的算法，在许多应用中同时返回可接受的inlier搜索性能。这些优点表明3DHV可以应用于时间关键的应用，如机器人的同步定位与地图构建( SLAM )、物体抓取和三维物体识别等。

（5）对于需要密集特征对应的应用，SI将是最佳选择。SI的一个核心缺点是在杂波和部分重叠的干扰下精度有限。在这种情况下，GC可以成为显示整体更高精度的替代方案。

参考文献

1.M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In Proceedings of the International Conference on Computer Vision,volume 2, pages 1482–1489. IEEE, 2005.

2.Y. Guo, M. Bennamoun, F. Sohel, M. Lu, J. Wan, and N. M.Kwok. A comprehensive performance evaluation of 3d local feature descriptors. International Journal of Computer Vision, 116(1):66–89, 2016.

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。