从零开始掌握概率算法模型RANSAC

1. 概述

在许多现实世界的应用中，获得的数据是“脏”的，直接用所有数据点，采用最小二乘法这类方法进行拟合，结果会被外点严重带偏，得到一个完全错误的模型，RANSAC全称是 RANdom SAmple Consensus（随机抽样一致）， 就是为了解决这类问题而诞生的，是一种鲁棒估计算法，用于从一组包含大量外点（噪声、错误数据）的观测数据中，高效地估计出一个数学模型的最佳参数。

核心思想：与其用所有数据（包含大量脏数据）去拟合一个可能很差的模型，不如通过反复随机抽样，用小部分干净的数据来拟合模型，然后找出哪个模型被最多“好数据”所支持，比如如下场景：

• 计算机视觉：从两幅图像中匹配特征点（SIFT, ORB等），总会产生一定比例的错误匹配。
• 传感器数据处理：激光雷达点云中可能包含来自移动物体（如行人、汽车）的噪点。
• 曲线拟合：从一堆数据点中拟合一条直线，但很多点偏离了主线。

2. RANSAC 的核心原理

RANSAC 通过一种迭代的、随机采样的方式来进行模型估计，工作原理可以分解为以下几个步骤：

1. 随机抽样：从整个数据集中随机抽取最少数量的点（记为 n），例如，拟合一条直线需要 2 个点 (n=2)，拟合一个圆需要 3 个点 (n=3)，估算一个单应性矩阵需要 4 个点 (n=4)，而估算五点法的本质矩阵需要 5 个点 (n=5)。
2. 模型估计：使用第一步抽出的这 n 个点，计算出一个初始模型 M_i（例如，用两个点算出直线的斜率和截距）。
3. 共识集划分：将数据集里所有其他未被抽到的点，都用当前这个模型 M_i 来测试，通过定义一个距离阈值 t，如果一个点与模型 M_i 的误差小于 t，则认为该点与模型 M_i 一致，将其归入共识集，也称为“内点集”，统计共识集中内点的数量 S_i。
4. 迭代与评估：多次重复步骤 1-3 （比如 K 次），每次都会得到一个模型 M_i 和其对应的内点数量 S_i，记录下拥有最多内点的那个模型 M_best 和其对应的共识集。

5：模型精炼：在所有的迭代完成后，使用最终找到的 M_best 所对应的全部内点（而不仅仅是初始的 n 个点），通过最小二乘法等方法重新精炼计算出一个更优的、更精确的最终模型。

在这里插入图片描述

图示：RANSAC通过多次随机抽样最终找到被最多内点（绿色点）支持的模型（线）。

3. 关键参数

距离阈值 t： 用于判断一个点是内点还是外点，通常根据具体问题和数据噪声水平凭经验设定，或通过统计方法计算。t 设置得太小，会找不到足够内点；太大，则模型会不够精确。

迭代次数 K： 抽样的次数，可以通过概率来估算，迭代次数公式：

其中：

• p：期望的成功概率（如 0.99）
• w：内点占整个数据集的比例（先验未知，初始时可粗略估计一个值，算法运行过程中可以动态更新）。
• n：一次抽样所需的最小点数。

从这个公式可以看出，如果内点比例 w 很低，所需的迭代次数 K 会呈指数级增长。

4. 应用示例：从匹配点中估计相机位姿

问题： 两张同一个场景的不同角度拍摄的照片，通过特征提取算法（如SIFT）得到了数百对匹配点，但其中约30%的错误匹配（外点），目标是估算相机从一个位置移动到另一个位置的旋转和平移（即相对位姿），通过RANSAC + 五点法的解决方案步骤如下：

1. 确定最小子集大小 n： 要估算本质矩阵 E（进而得到 R 和 t），需要至少 5 对点，所以 n = 5。
2. 模型估计： 在RANSAC的每一次循环中，随机抽出5对点，使用五点法计算出一个本质矩阵 E_i 的候选解（可能有多组，需要逐一验证）。
3. 误差度量与阈值 t： 对于每一对未抽中的匹配点，计算一个点到另一个视图对应的极线的距离，如果这个距离小于阈值 t（例如 0.5 像素），则认为该点对是当前模型 E_i 的内点。
4. 共识集： 统计所有与模型 E_i 一致的点对数量 S_i。
5. 迭代： 重复上述过程 K 次（K 根据内点比例动态调整），记录下拥有最大内点集 S_best 的模型 E_best。
6. 精炼： RANSAC循环结束后，我们得到了一个纯净的、正确的内点集。此时，用所有的内点（可能有成百上千对），通过一个非线性优化算法（LM）对 E_best 进行精炼，得到最精确的本质矩阵 E_final。
7. 分解位姿： 最后，从精炼后的 E_final 中通过SVD分解恢复出相机的旋转矩阵 R 和平移向量 t。

如果没有RANSAC： 我们直接使用所有匹配点（包含30%的错误点）用八点法或五点法求解，计算出的 E 矩阵可能会是错误的，导致后续恢复出的 R 和 t 也毫无意义。