剧透: 它们现在好多了!
关于作者
Dmytro Mishkin 是捷克布拉格理工大学的博士后，在图像匹配和计算机视觉和深度学习咨询领域工作。
OpenCV RANSAC 已经死了。长寿的 OpenCV USAC!
去年，包括我在内的来自 UBC、谷歌、布拉格理工大学和 EPFL 的一组研究人员发表了一篇论文“跨越宽基线的图像匹配: 从论文到实践”，该论文除了其他信息外，还表明 OpenCV RANSAC 用于基本矩阵估计很糟糕: 它非常不准确而且很慢。从那时起，我的同事 Maksym Ivashechkin 在 2020 年的整个夏季都致力于改进 OpenCV RANSACs。他的工作作为 OpenCV 4.5.0 版本 的一部分发布。
现在是时候对它们进行基准测试了。让我们开始吧!
RANSAC
首先让我们回顾一下 RANSAC 是用来做什么的。这个缩写代表 RANdom SAmple Consensus，这是一种算法，于 1981 年被提出，用于在存在离群值的情况下对模型参数进行稳健估计——也就是说，存在噪声和错误的数据点。
该技术在计算机视觉中最广泛的应用是用于相对相机姿态和透视变换估计。显然，它在 OpenCV 中可用，并且在其 教程 中有介绍。
自从最初的论文发表以来，数百名研究人员提出了一系列改进，使 RANSAC 速度更快、更精确、更稳健。
基准测试
尽管有了这些改进，但没有“下游指标”评估，说明 RANSAC 如何影响相机姿态估计系统的性能。这就是“跨越宽基线的图像匹配: 从论文到实践”和一系列 CVPR 图像匹配挑战赛 的作用。它们使用最先进的运动结构算法从数千张图像重建场景，并获得每张图像的精确相机姿态。这些相机姿态被用作真值来评估图像匹配管道的不同部分，包括 RANSACs。
在我们的测试中，我们在 图像匹配挑战赛 2021 数据集的验证子集上运行了基准测试——PragueParks、GoogleUrban 和 Phottourism。我们检测了 RootSIFT 特征，使用最佳互斥 SNN 比例测试将其匹配，然后将它们馈送到经过测试的 RANSACs 中。将得到的基准矩阵转换为相对姿态，并与真值姿态进行比较。您可以在论文“跨越宽基线的图像匹配: 从论文到实践”中查看详细信息。
对于所有 RANSACs，我们首先通过网格搜索确定最佳内点阈值，而迭代次数 (max_iter) 设置为合理的 100k。然后，在修复此最佳阈值后，我们将迭代次数从 10 变化到 10M。这给了我们一条准确度-时间曲线。
评估的方法
在这里，我们主要评估了在 OpenCV 中实现的 RANSAC 方法，但也添加了一些基线。包含的非 OpenCV 方法如下：
- PyRANSAC – 来自 pydegensac 包的 LO-RANSAC 实现。它应该大致等效于基本的 OpenCV RANSAC。LO 代表“局部优化”，用于改进中间结果。
- DEGENSAC – 来自 pydegensac 包，基于该方法的原始实现，该方法在 CVPR 2005 年论文“不受主导平面影响的双视图几何估计”中提出。当 基准矩阵 的形式的相对相机姿态是从所有位于同一平面的对应关系中估计的时，结果通常不正确。DEGENSAC 检测并修复了此类情况。该算法是 Image Matching Challenge 2020 和 2021 的默认选择。
OpenCV 方法，以需要传递到 cv2.findFundamentalMatrix 函数的标志命名，如下所示
- RANSAC — OpenCV (原始) RANSAC 实现，来自库的先前版本，没有花哨的功能。
- USAC_DEFAULT – 在算法方面等同于上面的 DEGENSAC，但在实现细节上有所不同。
- USAC_FAST – 与上面的 USAC_DEFAULT 相同，但具有不同的硬编码参数，并且由于在局部优化步骤中使用的迭代次数少于 USAC_DEFAULT，因此可能工作速度更快——它还使用 RANSAC 分数来最大化内点数并更早地终止。
- USAC_ACCURATE — 实现最近的 图割 RANSAC。它使用能量最小化图割算法，而不是简单的局部优化。它有时允许从包含离群值的样本中估计正确的模型。
- USAC_MAGSAC — 它实现了另一种最近的算法: MAGSAC++。它受到深度学习解决方案的启发，使用迭代重新加权最小二乘优化与软阈值相结合，以利用大致正确但精度不高的对应关系。
所有 OpenCV USAC 方法还使用 SPRT 测试 来加速评估。
结果
以下是所有 3 个数据集的结果。曲线越左越高越好。虚线垂直线标记了 1/25 秒（“实时”）和 0.5 秒（挑战限制）时间预算。图例显示了方法名称以及数据集的最佳内点阈值: Phototourism、GoogleUrban 和 PragueParks。
1. 第一个也是最主要的结论——所有新标志都比旧的 OpenCV 实现 (绿色曲线，最差结果) 好得多，而旧的 OpenCV 实现仍然是默认选项。
2. 使用 10k 迭代次数和 USAC_ACCURATE (红色曲线) 可以在 0.01 秒内获得很好的结果。
3. 对于小型/中型时间预算 (小于 0.1 秒/图像)，所有 OpenCV 高级 USACs 都比 pydegensac (蓝色曲线) 更好。
4. 对于更高的预算，最好的方法是 OpenCV USAC_MAGSAC 和 pydegensac 包中的 DEGENSAC。
5. 使用“USAC_FAST”标志没有意义——始终使用 USAC_DEFAULT、USAC_ACCURATE 或 USAC_MAGSAC 更好。
6. USAC_MAGSAC 是唯一一种在所有数据集中最佳阈值都相同的方法。对于实践来说，这是一个宝贵的特性，因为它需要最少的调整。我建议将其用作默认解决方案
如果您对单个数据集的结果感兴趣，请继续阅读。
Phototourism
GoogleUrban
PragueParks
为什么在同一个集合上进行调整和评估?
确实，在同一个数据集上调整和评估方法没有任何意义。但是，请允许我为我的选择辩护。以下是论点：
1. 我不想损害测试集的完整性，测试集是正在进行的比赛 图像匹配挑战赛 2021 的基础，该比赛包含现金奖励。因此，我不想泄露上述测试集的信息，这是我的主要优化目标。我也不能在“训练子集”上调整阈值，因为 GoogleUrban 和 PragueParks 都没有这样的参数。
2. 我们更关注速度与准确度的粗略权衡，而不是方法的精确排名——您数据集上的数字无论如何都会不同。很可能这些方法在验证集上存在很小的准确度差距，但在测试集上会发生变化——正如我们 原始论文 中 DEGENSAC 和 MAGSAC 所发生的那样。但是，在验证集上表现不佳的方法神奇地在测试集上胜过所有人的可能性非常小。同样，请参阅原始论文中的 PyRANSAC 与 DEGENSAC。
结论
新的 OpenCV RANSACs 速度很快，并且具有可比的准确度，您可以放心地选择其中之一。我推荐 USAC_MAGSAC，因为它对内点阈值最不敏感。
使用正确的 RANSACs，享受快乐 🙂
