OpenCV 4.12.0
开源计算机视觉
加载中...
搜索中...
无匹配项
USAC：OpenCV 中随机样本一致性的改进

目录

上一篇教程: 交互式相机校准应用

原始作者Maksym Ivashechkin
兼容性OpenCV >= 4.0

这项工作是 Google Summer of Code (2020 年 8 月) 的一部分集成进来的。

贡献

集成到 OpenCV calib3d 模块的部分是基于 RANSAC 的通用框架 USAC (namespace usac)，用 C++ 编写。该框架包括不同的最先进的采样、验证或局部优化方法。该框架的主要优点是它独立于任何估计问题和模块化结构。因此，可以轻松地添加/删除新的求解器或方法。到目前为止，它包括以下组件

  1. 采样方法
    1. Uniform – [92] 中提出的标准 RANSAC 采样，独立地均匀随机地抽取最小子集。拟议框架中的默认选项。
    2. PROSAC – 方法 [59]，假设输入数据点按质量排序，因此采样可以从最有希望的点开始。此方法的对应关系可以按例如 SIFT 检测器获得的最佳匹配与第二佳匹配的描述符距离之比排序。建议使用此方法，因为它能更快地找到好的模型并终止。
    3. NAPSAC – 采样方法 [204]，它均匀随机地选取初始点，并在初始点附近选取最小样本的其余点。当模型是局部模型时，这种方法可能很有用。例如，对于平面拟合。然而，在实践中，它受到退化问题和定义最佳邻域大小的困扰。
    4. Progressive-NAPSAC – 采样器 [18]，类似于 NAPSAC，但它从局部开始，逐渐收敛到全局采样。如果期望局部模型，但数据分布可以是任意的，则此方法可能非常有用。实现的版本假设数据点按质量排序，如 PROSAC 中一样。
  2. 评分方法。USAC 以及标准 RANSAC 找到的模型可以最大限度地减少总损失。损失可以用以下函数表示
    1. RANSAC – 二进制 0 / 1 损失。1 表示异常值，0 表示内点。如果目标是找到尽可能多的内点，这是一个不错的选择。
    2. MSAC – 点到模型的截断平方误差距离。框架中的默认选项。使用 RANSAC 分数时，模型可能没有那么多内点，但会更准确。
    3. MAGSAC – 无阈值方法 [19] 来计算分数。使用最大 sigma（噪声的标准偏差）水平来对点的残差进行边缘化。点的分数表示点作为内点的可能性。当图像噪声未知时，建议使用此选项，因为该方法不需要阈值。但是，仍然建议提供至少近似的阈值，因为终止本身基于误差小于阈值的点的数量。通过给出 0 阈值，该方法将在达到最大迭代次数后输出模型。
    4. LMeds – 平方误差距离的最小中位数。在该框架中，使用快速排序算法以 $O(n)$ 的复杂度有效地实现中位数查找。请注意，当内点比率小于 50% 时，LMeds 不必正常工作，在其他情况下，此方法是稳健的，不需要阈值。
  3. 描述点到估计模型的误差距离的误差度量。
    1. 重投影距离 – 用于仿射、单应性和投影矩阵。对于单应性，也可以使用对称重投影距离。
    2. Sampson 距离 – 用于基本矩阵。
    3. 对称几何距离 – 用于本质矩阵。
  4. 退化
    1. DEGENSAC – 方法 [62]，用于基本矩阵估计，有效地验证和恢复在主平面上至少有 5 个点的最小样本的模型。
    2. 共线性测试 – 对于仿射和单应性矩阵估计，检查是否没有 3 个点位于直线上。对于单应性矩阵，由于点是平面的，因此应用测试检查最小样本中的点是否位于相对于穿过样本中任意两个点的任何线的同一侧（不假设反射）。
    3. 定向外极约束 – 方法 [61]，用于外极几何，验证模型（基本矩阵和本质矩阵），以使点在相机前方可见。
  5. SPRT 验证 – 方法 [187]，通过在随机打乱的点上评估模型，使用由内点概率、估计的相对时间、输出模型的平均数量等给出的统计属性来验证模型。显着加快了框架的速度，因为可以非常快速地拒绝不良模型，而无需显式计算每个点的误差。
  6. 局部优化
    1. 局部优化 RANSAC – 方法 [60]，通过非最小估计迭代地改进目前为止的最佳模型。框架中的默认选项。此过程是最快的，并且不比其他局部优化方法差。
    2. Graph-Cut RANSAC – 方法 [17]，改进目前为止的最佳模型，但是，它利用了数据点的空间相干性。此过程非常精确，但计算速度较慢。
    3. Sigma Consensus – 方法 [19]，通过应用非最小加权估计来改进模型，其中权重以与 MAGSAC 分数相同的逻辑计算。此方法最好与 MAGSAC 分数一起使用。
  7. 终止
    1. 标准 – 用于独立和均匀采样的标准方程。
    2. PROSAC – PROSAC 的终止。
    3. SPRT – SPRT 的终止。
  8. 求解器。在该框架中，有最小求解器和非最小求解器。在最小求解器中，应用标准的估计方法。在非最小求解器中，通常构建协方差矩阵，并且模型被找到为对应于最高特征值的特征向量。
    1. 仿射 2D 矩阵
    2. 单应性矩阵 – 对于最小求解器，使用来自 OpenCV 的 RHO（高斯消元）算法。
    3. 基本矩阵 – 对于 7 点算法，使用高斯消元（消除到上三角矩阵和回代）而不是 SVD 找到两个零向量，然后求解 3 次多项式。对于 8 点求解器，也使用高斯消元。
    4. 本质矩阵 – 使用高斯消元找到 4 个零向量。然后使用 [254] 中描述的基于 Gröbner 基的求解器。只有在安装了 LAPACK 或 Eigen 时才能计算本质矩阵，因为它需要具有复杂特征值的特征分解。
    5. Perspective-n-Point – 最小求解器是经典的 3 个点，最多有 4 个解。对于 RANSAC，样本大小的低数量起着重要的作用，因为它需要的迭代次数更少，此外，平均 P3P 求解器大约有 1.39 个估计模型。此外，在新版本的带有 UsacParams 的 solvePnPRansac(...) 中，可以选择传递空内部矩阵 InputOutputArray cameraMatrix。如果矩阵为空，则使用直接线性变换算法（带有 6 个点的 PnP）框架不仅输出旋转和平移向量，还输出校准矩阵。

此外，该框架可以并行运行。并行化以创建多个 RANSAC 的方式完成，并且它们共享两个原子变量 bool success 和 int num_hypothesis_tested，它们确定何时所有 RANSAC 必须终止。如果其中一个 RANSAC 成功终止，则所有其他 RANSAC 也将终止。最后，从所有线程同步最佳模型。如果使用 PROSAC 采样器，则线程必须共享相同的采样器，因为采样是按顺序完成的。但是，使用框架的默认选项，并行 RANSAC 不是确定性的，因为它取决于每个线程的运行频率。使其具有确定性的最简单方法是使用没有 SPRT 和局部优化的 PROSAC 采样器，而不是用于基本矩阵，因为它们内部使用随机生成器。

对于 NAPSAC、Progressive NAPSAC 或 Graph-Cut 方法，需要构建邻域图。在框架中，有 3 个选项可以执行此操作

  1. NEIGH_FLANN_KNN – 使用 OpenCV FLANN K 最近邻估计邻域图。KNN 的默认值为 7。KNN 方法可能对采样有效，但对 GC-RANSAC 不利。
  2. NEIGH_FLANN_RADIUS – 与前一种情况类似，找到距离小于 20 像素的邻近点。
  3. NEIGH_GRID – 为了找到点的邻域，使用哈希表将点平铺在单元格中。该方法在 [18] 中进行了描述。比 NEIGH_FLANN_RADIUS 的精度低，但速度明显更快。

请注意，NEIGH_FLANN_RADIUS 和 NEIGH_GRID 不能用于 PnP 求解器，因为存在 3D 对象点。

新标志

  1. USAC_DEFAULT – 具有标准的 LO-RANSAC。
  2. USAC_PARALLEL – 具有 LO-RANSAC，并且 RANSAC 并行运行。
  3. USAC_ACCURATE – 具有 GC-RANSAC。
  4. USAC_FAST – 具有 LO-RANSAC，在局部优化步骤中迭代次数较少。使用 RANSAC 分数来最大限度地提高内点的数量并提前终止。
  5. USAC_PROSAC – 具有 PROSAC 采样。请注意，点必须排序。
  6. USAC_FM_8PTS – 具有 LO-RANSAC。仅对具有 8 点求解器的基本矩阵有效。
  7. USAC_MAGSAC – 具有 MAGSAC++。

每个标志都使用 SPRT 验证。最后，目前为止的最佳模型通过对所有找到的内点的非最小估计进行优化。

一些其他重要的参数

  1. randomGeneratorState – 由于每个 USAC 求解器在 OpenCV 中都是确定性的（即，对于相同的点和参数返回相同的结果），因此通过提供新的状态将输出新的模型。
  2. loIterations – 局部优化方法的迭代次数。默认值为 10。通过增加 loIterations，输出模型可能会更准确，但是，计算时间也可能会增加。
  3. loSampleSize – 局部优化的最大样本数。默认值为 14。请注意，通过增加 loSampleSize，模型的准确性和计算时间都会增加。但是，建议将值保持在 100 以下，因为对少量点进行估计更快且更稳健。

示例

在 opencv/samples 目录中有三个新的示例文件。

  1. epipolar_lines.cpp – main 函数的输入参数是图像的两个路径。然后使用 SIFT 检测器找到对应关系。使用来自初步对应关系的 RANSAC 找到基本矩阵，并绘制外极线。
  2. essential_mat_reconstr.cpp – 输入参数是包含图像名称和单个内部矩阵的数据文件的路径，以及这些图像所在的目录。使用 SIFT 找到对应关系。使用 RANSAC 估计本质矩阵，并将其分解为旋转和平移。然后，通过构建具有投影矩阵的两个相对姿势，将图像点三角化为对象点。通过使用 3D 平面拟合对象点运行 RANSAC，对应关系也被聚类到平面中。
  3. essential_mat_reconstr.py – 与 .cpp 文件中的功能相同，但是，不是将点聚类到平面，而是绘制对象点的 3D 地图。
为 OpenCV 于 2025 年 7 月 3 日星期四 12:14:34 生成，作者为  doxygen 1.12.0