【IPMV】图像处理与机器视觉：Lec13 鲁棒估计方法：RANSAC算法
本系列为2025年同济大学自动化专业**图像处理与机器视觉**课程笔记
Lecturer: Rui Fan、Yanchao Dong
Lec3 Perspective Transformation
Lec11 Keypoint Features and Corners
Lec13 Robust Estimation with RANSAC
持续更新中
文章目录
Lec13 Robust Estimation with RANSAC
- Basic RANSAC
- Adaptive RANSAC
1 概述
随机抽样一致性（RANdom SAmple Consensus, RANSAC）是一种在包含大量异常值的数据中稳健估计模型参数的迭代方法。
- 基本假设：数据由 “内点” （Inliers）和 “外点” （Outliers）组成。内点符合某种模型分布（可能包含噪声），而外点则不满足该模型；
- 核心思想：通过随机抽样和模型验证来区分数据中的内点和外点，从而避免异常值对模型估计的影响
2 核心原理与实现步骤
2.1 基础算法流程
目标：鲁棒地将模型 y = f ( x ; α ) y = f(x; \boldsymbol{\alpha}) y=f(x;α) 拟合到数据集 S = { x i } S = \{ \boldsymbol{x}_i \} S={xi}中
RANSAC的实现基于投票机制，通过以下步骤寻找最优拟合模型：
- 随机抽样：从输入数据集中随机选择包含 n n n 个随机数据点 { x 1 , x 2 , … , x n } \{ \boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n \} {x1,x2,…,xn} 的子集，该子集的大小需足够确定模型参数。
- 模型拟合：仅使用该子集的数据计算模型参数 α tst \boldsymbol{\alpha}_{\text{tst}} αtst。
- 内点验证：检查整个数据集中哪些元素与基于估计参数的模型一致。若数据点与模型偏差（距离）在误差阈值 t t t范围内的数据点构成内点集 S tst ⊆ S S_{\text{tst}} \subseteq S Stst⊆S，否则为外点。
- 迭代优化：如果 S tst S_{\text{tst}} Stst 是目前遇到的最大内点集，保留该模型，令 S IN = S tst S_{\text{IN}} = S_{\text{tst}} SIN=Stst 且 α = α tst \boldsymbol{\alpha} = \boldsymbol{\alpha}_{\text{tst}} α=αtst，重复上述过程，直至测试了 N N N 个模型。
2.2 关键参数解析
- 随机样本数量 n \boldsymbol{n} n：通常为估计模型所需的最小数据点数量。
- 误差阈值 t \boldsymbol{t} t：确定数据点是否符合模型的标准，通常根据应用需求和数据集特性（如噪声水平）设定，高斯噪声场景下可取 2 σ 2σ 2σ。
- 迭代次数 N \boldsymbol{N} N：根据我们希望有多大把握能至少抽样得到一个不含外点的数据集合 { x 1 , x 2 , … , x n } \{x_1, x_2, \dots, x_n\} {x1,x2,…,xn} 来选择。可通过公式 N = log ( 1 − p ) log ( 1 − w n ) N = \frac{\log(1-p)}{\log(1-w^n)} N=log(1−wn)log(1−p)计算，其中 p p p 为期望成功概率（常用 0.99）， w w w 为随机数据点为内点的概率。
- 内点概率 ω \boldsymbol{\omega} ω： w = ∣ S I N ∣ ∣ S ∣ = 数据中的内点数量 数据点总数 w = \frac{|S_{IN}|}{|S|}=\frac{数据中的内点数量}{数据点总数} w=∣S∣∣SIN∣=数据点总数数据中的内点数量，通常是未知的，实际应用中常通过自适应方法动态更新。
2.3 自适应 RANSAC
Basic RANSAC 的一个局限是需要预先知道内点比例 w w w，而 Adaptive RANSAC 通过动态更新 w w w 来优化迭代次数 N N N：
- 初始化： N = ∞ N = \infty N=∞ 和空内点集 S I N = ∅ S_{IN}=\emptyset SIN=∅。
- 迭代条件：迭代次数小于 N N N，重复执行步骤3~5。
- 随机抽样与模型拟合：n 个随机数据点 { x 1 , x 2 , … , x n } \{ \boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n \} {x1,x2,…,xn} 中确定一个测试模型 y = f ( x ; α tst ) y = f(x; \boldsymbol{\alpha}_{\text{tst}}) y=f(x;αtst)。
- 内点验证
- 迭代优化：如果 S tst S_{\text{tst}} Stst是目前遇到的最大内点集，就保留该模型，并更新内点概率 ω \omega ω 和迭代次数 N N N
- 令 S IN = S tst S_{\text{IN}} = S_{\text{tst}} SIN=Stst 且 α = α tst \boldsymbol{\alpha} = \boldsymbol{\alpha}_{\text{tst}} α=αtst；
- 每次迭代后根据当前最大内点集大小更新 w = ∣ S I N ∣ ∣ S ∣ w = \frac{|S_{IN}|}{|S|} w=∣S∣∣SIN∣；
- 重新计算 N = log ( 1 − p ) log ( 1 − w n ) N = \frac{\log(1-p)}{\log(1-w^n)} N=log(1−wn)log(1−p)，动态调整迭代次数。
3 RANSAC 算法的优缺点
3.1 优点
- 鲁棒性强：即使数据集中存在大量外点（可达 50 % 50\% 50%），仍能准确估计模型参数。
- 模型适应性广：适用于直线、圆、单应性矩阵等多种数学模型的参数估计。
- 实现灵活：可与其他估计方法（如最小二乘法）结合，通过内点集优化模型精度。RANSAC先通过迭代等方式找出内点，然后基于内点，使用处理“干净”数据时效果好、但相对不那么鲁棒的估计方法（如最小二乘法）优化模型参数。
3.2 缺点
- 时间复杂度不确定：理论上迭代次数没有上限（除非进行穷举 ），可能导致计算时间不可控。若限制迭代次数，得到的解可能非最优，甚至无法良好拟合数据；增加迭代次数虽能提升获得合理模型的概率，但会耗费更多时间，存在计算成本与模型质量的权衡。
- 参数敏感性：需要设置问题特定的阈值，且只能估计单一模型。
- 初始假设依赖：若内点比例过低或抽样未覆盖足够内点，可能收敛到次优解。
4 RANSAC 算法应用实例：圆的拟合
- 确定最小确定圆方程的参数：从 3 3 3 个随机点估计圆参数 ( x 0 , y 0 , r ) (x_0, y_0, r) (x0,y0,r)。
- 评估内点的方法：点到圆的距离小于阈值，即 d = ∣ ( x i − x 0 ) 2 + ( y i − y 0 ) 2 − r ∣ < t d = |\sqrt{(x_i - x_0)^2 + (y_i - y_0)^2} - r|<t d=∣(xi−x0)2+(yi−y0)2−r∣<t。
或者根据RANSAC返回的最大内点集合，使用better but less robust algorithm，如最小二乘法
5 RANSAC 算法的拓展与变种
- 渐进抽样一致性（PROgressive Sample and Consensus, PROSAC）：优先选择可信度高的点进行抽样，减少无效迭代。
- M估计抽样一致性（M-estimator Sample and Consensus, MSAC）：引入损失函数替代简单的阈值判定，提高模型精度。
- 最小中位数平方（Least Median Squares, ）：通过最小化残差中位数来抵抗异常值。
- 最大似然抽样一致性（Maximum Likelihood Estimation Sampleand Consensus, MLESAC）：基于概率模型计算最优参数。
6 总结
RANSAC
- A robust iterative method for estimating the parameters of a mathematical model from a set of observed data containing outliers
- Separates the observed data into“inliers”and“outliers”which is very useful if we want to use better, but less robust, estimation methods