贡献

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

采样方法
1. 均匀采样 – 在[90]中提出的标准RANSAC采样，它独立地从均匀分布中随机抽取最小子集。这是所提出框架中的默认选项。
2. PROSAC – 方法[57] 假设输入数据点按质量排序，因此采样可以从最有希望的点开始。此方法的对应点可以例如按从SIFT检测器获得的最佳匹配与次佳匹配的描述符距离比率进行排序。推荐使用此方法，因为它可以找到好的模型并更早终止。
3. NAPSAC – 采样方法[201]，它从均匀随机的初始点开始，其余最小样本中的点位于初始点的邻域内。当模型是局部化的时，这种方法可能很有用。例如，用于平面拟合。然而，在实践中，它难以处理退化问题和定义最佳邻域大小。
4. 渐进式NAPSAC – 采样器[17]，类似于NAPSAC，尽管它从局部开始，并逐渐收敛到全局采样。如果预期局部模型但数据分布可以是任意的，则此方法非常有用。实现的版本假设数据点按质量排序，如PROSAC中一样。
评分方法。USAC以及标准RANSAC查找最小化总损失的模型。损失可以用以下函数表示：
1. RANSAC – 二元 0/1 损失。异常值为1，内点为0。如果目标是找到尽可能多的内点，这是一个不错的选择。
2. MSAC – 点到模型的截断平方误差距离。框架中的默认选项。该模型的内点数可能不如使用RANSAC评分多，但会更准确。
3. MAGSAC – 无阈值方法[18] 用于计算分数。然而，使用最大sigma（噪声的标准差）水平来边缘化点相对于sigma的残差。点的分数表示该点为内点的可能性。当图像噪声未知时，推荐使用此选项，因为该方法不需要阈值。但是，仍然建议至少提供一个近似的阈值，因为终止本身是基于误差小于阈值的点数。如果给出0阈值，则该方法将在达到最大迭代次数后输出模型。
4. LMeds – 平方误差距离的中位数最小值。在框架中，使用O(n)复杂度的快速排序算法有效地实现中位数查找。请注意，当内点比率小于50%时，LMeds可能无法正常工作，在其他情况下，此方法很稳健，不需要阈值。
误差度量，描述点到估计模型的误差距离。
1. 重投影距离 – 用于仿射、单应性和投影矩阵。对于单应性，也可以使用对称重投影距离。
2. 桑普森距离 – 用于基础矩阵。
3. 对称几何距离 – 用于本质矩阵。
退化
1. DEGENSAC – 方法[60]，对于基础矩阵估计，它有效地验证和恢复在最小样本中至少有5个点位于主要平面上的模型。
2. 共线性检验 – 对于仿射和单应性矩阵估计，检查是否有3个点位于同一条线上。对于单应性矩阵，由于点是平面的，因此应用检验来检查最小样本中的点是否位于相对于穿过样本中任意两点的任何线的同一侧（不假设反射）。
3. 定向极线约束 – 方法[59] 用于极几何，它验证模型（基础矩阵和本质矩阵）使点位于摄像机前方可见。
SPRT验证 – 方法[184]，通过使用内点概率、估计的相对时间、输出模型的平均数量等统计属性，在其对随机洗牌点进行评估的基础上验证模型。显著加快了框架速度，因为可以非常快速地拒绝错误模型，而无需显式计算每个点的误差。
局部优化
1. 局部优化RANSAC – 方法[58]，通过非最小估计迭代地改进到目前为止最好的模型。框架中的默认选项。此过程最快，并且不比其他局部优化方法差。
2. 图割RANSAC – 方法[16]，它细化到目前为止最好的模型，但是，它利用数据点的空间相干性。此过程非常精确，但计算速度较慢。
3. Sigma一致性 – 方法[18]，通过应用非最小加权估计来改进模型，其中权重与MAGSAC评分中的逻辑相同。此方法最好与MAGSAC评分一起使用。
终止
1. 标准 – 独立和均匀采样的标准方程。
2. PROSAC – PROSAC的终止条件。
3. SPRT – SPRT的终止条件。
求解器。在框架中，存在最小和非最小求解器。在最小求解器中，应用标准估计方法。在非最小求解器中，通常构建协方差矩阵，并将模型找到为对应于最高特征值的特征向量。
1. 仿射2D矩阵
2. 单应矩阵 – 最小求解器使用OpenCV中的RHO（高斯消元）算法。
3. 基础矩阵 – 对于7点算法，使用高斯消元法（消元为上三角矩阵并进行回代）而不是SVD找到两个零向量，然后求解3次多项式。对于8点求解器，也使用高斯消元法。
4. 本质矩阵 – 使用高斯消元法找到4个零向量。然后使用文献[251]中描述的基于Gröbner基的求解器。只有安装LAPACK或Eigen才能计算本质矩阵，因为它需要具有复特征值的特征分解。
5. 透视n点法 – 最小求解器是经典的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、渐进式NAPSAC或图割方法，需要构建邻域图。在框架中，有3种方法可以做到这一点

NEIGH_FLANN_KNN – 使用OpenCV FLANN K近邻估计邻域图。KNN的默认值为7。KNN方法可能适用于采样，但不适用于GC-RANSAC。
NEIGH_FLANN_RADIUS – 与前一种情况类似，查找距离小于20像素的邻近点。
NEIGH_GRID – 使用哈希表在单元格中平铺点以查找点的邻域。该方法在文献[17]中进行了描述。虽然速度显著提高，但精度不如NEIGH_FLANN_RADIUS。

注意，NEIGH_FLANN_RADIUS和NEIGH_FLANN_RADIUS无法用于PnP求解器，因为存在3D目标点。

新标志

USAC_DEFAULT – 具有标准LO-RANSAC。
USAC_PARALLEL – 具有LO-RANSAC，并且RANSAC并行运行。
USAC_ACCURATE – 具有GC-RANSAC。
USAC_FAST – 具有LO-RANSAC，局部优化步骤中的迭代次数较少。使用RANSAC分数来最大化内点数量并尽早终止。
USAC_PROSAC – 具有PROSAC采样。注意，必须对点进行排序。
USAC_FM_8PTS – 具有LO-RANSAC。仅对具有8点求解器的基础矩阵有效。
USAC_MAGSAC – 具有MAGSAC++。

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

其他一些重要参数

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

示例

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

epipolar_lines.cpp – main函数的输入参数是两张图像的路径。然后使用SIFT检测器找到对应关系。使用RANSAC从初步对应关系中找到基础矩阵，并绘制极线。
essential_mat_reconstr.cpp – 输入参数是包含图像名称和单个内参矩阵的数据文件的路径以及这些图像所在的目录。使用SIFT找到对应关系。使用RANSAC估计本质矩阵并将其分解为旋转和平移。然后通过使用投影矩阵构建两个相对位姿，将图像点三角化成目标点。通过运行RANSAC进行3D平面拟合目标点以及对应关系被聚类成平面。
essential_mat_reconstr.py – 与.cpp文件具有相同的功能，但是它不将点聚类到平面，而是绘制目标点的3D地图。


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