Skip to content
Anima Mundi Anima Mundi

USAC：OpenCV 中随机采样一致性（RANSAC）的改进

这项工作作为 Google Summer of Code（2020 年 8 月）的一部分被集成进来。

贡献

Section titled “贡献”

集成到 OpenCV calib3d 模块中的部分是基于 RANSAC 的通用框架 USAC（namespace usac），用 C++ 编写。该框架包含用于采样、验证或局部优化的各种最先进方法。该框架的主要优点是独立于任何估计问题，且具有模块化结构。因此，可以轻松地添加/移除新的求解器或方法。目前它包含以下组件：

  1. 采样方法：

    1. Uniform——[FischlerRANSAC] 中提出的标准 RANSAC 采样，独立均匀随机地抽取最小子集。所提出的框架中的默认选项。

    2. PROSAC——[ChumPROSAC] 方法，它假设输入数据点已按质量排序，因此采样可以从最有希望的点开始。该方法的对应关系可以例如按从 SIFT 检测器获得的最佳匹配与次佳匹配的描述子距离之比来排序。推荐使用此方法，因为它能更快地找到好的模型并更早终止。

    3. NAPSAC——[MyattNAPSAC] 采样方法，它均匀随机地取一个初始点，而最小样本的其余点取自初始点的邻域。当模型是局部的时，此方法可能很有用，例如用于平面拟合。然而，在实践中它受困于退化问题和最优邻域大小的定义。

    4. Progressive-NAPSAC——[barath2019progressive] 采样器，它类似于 NAPSAC，但它从局部开始，并逐渐收敛到全局采样。如果预期存在局部模型但数据分布可以是任意的，则此方法会相当有用。所实现的版本假设数据点像 PROSAC 中那样按质量排序。

  2. 评分方法。USAC 与标准 RANSAC 一样，寻找使总损失最小的模型。损失可以用以下函数表示：

    1. RANSAC——二值 0/1 损失。外点为 1，内点为 0。如果目标是找到尽可能多的内点，这是一个不错的选择。

    2. MSAC——点到模型的截断平方误差距离。框架中的默认选项。模型可能不如使用 RANSAC 评分时拥有的内点多，但会更精确。

    3. MAGSAC——[BarathMAGSAC] 的无阈值评分方法。它使用最大 sigma（噪声标准差）级别将点的残差对 sigma 进行边际化。点的得分表示该点为内点的可能性。当图像噪声未知时推荐使用此选项，因为该方法不需要阈值。然而，仍然建议至少提供一个近似阈值，因为终止本身是基于误差小于阈值的点数。如果给定 0 阈值，该方法将在达到最大迭代次数后输出模型。

    4. LMeds——平方误差距离的最小中值。在框架中，使用快速排序算法以 O(n)O(n) 的复杂度高效地实现中值查找。注意，当内点比例低于 50% 时，LMeds 未必能正常工作；在其他情况下，该方法具有鲁棒性且不需要阈值。

  3. 误差度量，描述点到所估计模型的误差距离。

    1. 重投影距离——用于仿射、单应性和投影矩阵。对于单应性，也可以使用对称重投影距离。

    2. Sampson 距离——用于基础矩阵（Fundamental matrix）。

    3. 对称几何距离——用于本质矩阵（Essential matrix）。

  4. 退化：

    1. DEGENSAC——[ChumDominant] 方法，用于基础矩阵估计时，能高效地验证并恢复最小样本中至少有 5 个点位于主导平面上的模型。

    2. 共线性测试——用于仿射和单应性矩阵估计时，检查是否没有 3 个点共线。对于单应性矩阵，由于点是平面的，会应用一个测试来检查最小样本中的点是否相对于穿过样本中任意两点的任意直线位于同一侧（不假设镜像翻转）。

    3. 有向对极约束——[ChumEpipolar] 中用于对极几何的方法，它验证模型（基础矩阵和本质矩阵）使得点在相机前方可见。

  5. SPRT 验证——[Matas2005RandomizedRW] 方法，它利用内点概率、估计的相对时间、输出模型的平均数量等统计特性，通过对随机打乱的点进行评估来验证模型。它能显著加速框架，因为糟糕的模型可以很快被拒绝，而无需显式计算每个点的误差。

  6. 局部优化：

    1. 局部优化 RANSAC——[ChumLORANSAC] 方法，它通过非最小估计迭代地改进迄今为止最好的模型。框架中的默认选项。此过程是最快的，且不劣于其他局部优化方法。

    2. Graph-Cut RANSAC——[BarathGCRANSAC] 方法，它改进迄今为止最好的模型，但它利用了数据点的空间相干性。此过程相当精确，但计算上更慢。

    3. Sigma Consensus——[BarathMAGSAC] 方法，它通过应用非最小加权估计来改进模型，其中权重用与 MAGSAC 评分相同的逻辑来计算。此方法最好与 MAGSAC 评分一起使用。

  7. 终止：

    1. Standard——用于独立均匀采样的标准方程。

    2. PROSAC——用于 PROSAC 的终止。

    3. SPRT——用于 SPRT 的终止。

  8. 求解器。框架中有最小求解器和非最小求解器。在最小求解器中应用标准的估计方法。在非最小求解器中，通常会构建协方差矩阵，并将模型作为对应于最高特征值的特征向量来求得。

    1. Affine2D 矩阵

    2. 单应性矩阵——最小求解器使用 OpenCV 中的 RHO（高斯消元）算法。

    3. 基础矩阵——对于 7 点算法，使用高斯消元（消元为上三角矩阵并回代）而非 SVD 来找到两个零向量，然后求解 3 次多项式。对于 8 点求解器，同样使用高斯消元。

    4. 本质矩阵——使用高斯消元找到 4 个零向量。然后使用 [SteweniusRecent] 中描述的基于 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 是不确定的，因为它取决于每个线程运行的频率。使其确定的最简单方法是使用 PROSAC 采样器，且不使用 SPRT 和局部优化，并且不用于基础矩阵，因为它们内部使用了随机数生成器。

对于 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——使用哈希表将点分块到单元格中来查找点的邻域。该方法在 [barath2019progressive] 中描述。精度不如 NEIGH_FLANN_RADIUS，但速度快得多。

注意，NEIGH_FLANN_RADIUS 和 NEIGH_GRID 不能用于 PnP 求解器，因为存在三维物体点。

新标志

Section titled “新标志”

  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 验证。最后，最终迄今为止最好的模型会通过对所有找到的内点进行非最小估计来加以精化。

其他几个重要参数

Section titled “其他几个重要参数”

  1. randomGeneratorState——由于 OpenCV 中的每个 USAC 求解器都是确定性的（即对于相同的点和参数返回相同的结果），通过提供新的状态，它将输出新的模型。

  2. loIterations——局部优化方法的迭代次数。默认值为 10。增大 loIterations 可能使输出模型更精确，但计算时间也可能增加。

  3. loSampleSize——局部优化的最大样本数。默认值为 14。注意，增大 loSampleSize 会提高模型的精度，但也会增加计算时间。然而，建议将该值保持在 100 以下，因为在较少点上进行估计更快也更鲁棒。

示例

Section titled “示例”

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

  1. epipolar_lines.cpp——main 函数的输入参数是两个图像路径。然后使用 SIFT 检测器找到对应关系。从初步对应关系中用 RANSAC 求出基础矩阵，并绘制对极线。

  2. essential_mat_reconstr.cpp——输入参数是包含图像名和单个内参矩阵的数据文件路径，以及这些图像所在的目录。使用 SIFT 找到对应关系。用 RANSAC 估计本质矩阵，并将其分解为旋转和平移。然后通过用投影矩阵构建两个相对位姿，将图像点三角化为物体点。通过用三维平面拟合运行 RANSAC，将物体点以及对应关系聚类到各个平面中。

  3. essential_mat_reconstr.py——与 .cpp 文件功能相同，但不是将点聚类到平面，而是绘制物体点的三维地图。