【IPMV】图像处理与机器视觉：Lec13 Robust Estimation with RANSAC

【IPMV】图像处理与机器视觉：Lec13 鲁棒估计方法：RANSAC算法

本系列为2025年同济大学自动化专业**图像处理与机器视觉**课程笔记
Lecturer: Rui Fan、Yanchao Dong

---

Lec0 Course Description

Lec3 Perspective Transformation

Lec7 Image Filtering

Lec8 Image Pyramid

Lec9 Laplace Blending

Lec10 Edges and Lines

Lec11 Keypoint Features and Corners

Lec12 Blob Detector

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;\mathbf{\alpha })$ 拟合到数据集 S = { x i } S = \{ \boldsymbol{x}_i \} S={xi​}中

RANSAC的实现基于投票机制，通过以下步骤寻找最优拟合模型：

1. 随机抽样：从输入数据集中随机选择包含 $n$ 个随机数据点 { x 1 , x 2 , … , x n } \{ \boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n \} {x1​,x2​,…,xn​} 的子集，该子集的大小需足够确定模型参数。
2. 模型拟合：仅使用该子集的数据计算模型参数 ${\mathbf{\alpha }}_{\text{tst}}$。
3. 内点验证：检查整个数据集中哪些元素与基于估计参数的模型一致。若数据点与模型偏差（距离）在误差阈值 $t$范围内的数据点构成内点集 $S_{\text{tst}}\subseteq S$，否则为外点。
4. 迭代优化：如果 $S_{\text{tst}}$ 是目前遇到的最大内点集，保留该模型，令 $S_{\text{IN}}=S_{\text{tst}}$ 且 $\mathbf{\alpha }={\mathbf{\alpha }}_{\text{tst}}$，重复上述过程，直至测试了 $N$ 个模型。

2.2 关键参数解析

• 随机样本数量 $\mathbf{n}$：通常为估计模型所需的最小数据点数量。
• 误差阈值$\mathbf{t}$：确定数据点是否符合模型的标准，通常根据应用需求和数据集特性（如噪声水平）设定，高斯噪声场景下可取 $2\sigma$。
• 迭代次数 $\mathbf{N}$：根据我们希望有多大把握能至少抽样得到一个不含外点的数据集合 { x 1 , x 2 , … , x n } \{x_1, x_2, \dots, x_n\} {x1​,x2​,…,xn​} 来选择。可通过公式 $N=\frac{\log (1-p)}{\log (1-w^n)}$计算，其中 $p$ 为期望成功概率（常用 0.99）， $w$ 为随机数据点为内点的概率。
• 内点概率 $\mathbf{\omega }$：$w=\frac{|S_{IN}|}{|S|}=\frac{数据中的内点数量}{数据点总数}$，通常是未知的，实际应用中常通过自适应方法动态更新。

2.3 自适应 RANSAC

Basic RANSAC 的一个局限是需要预先知道内点比例 $w$，而 Adaptive RANSAC 通过动态更新 $w$ 来优化迭代次数 $N$：

1. 初始化：$N=\infty$ 和空内点集 $S_{IN}=\varnothing$。
2. 迭代条件：迭代次数小于 $N$，重复执行步骤3~5。
3. 随机抽样与模型拟合：n 个随机数据点 { x 1 , x 2 , … , x n } \{ \boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n \} {x1​,x2​,…,xn​} 中确定一个测试模型 $y=f(x;{\mathbf{\alpha }}_{\text{tst}})$。
4. 内点验证
5. 迭代优化：如果$S_{\text{tst}}$是目前遇到的最大内点集，就保留该模型，并更新内点概率 $\omega$ 和迭代次数 $N$
   1. 令 $S_{\text{IN}}=S_{\text{tst}}$ 且 $\mathbf{\alpha }={\mathbf{\alpha }}_{\text{tst}}$；
   2. 每次迭代后根据当前最大内点集大小更新 $w=\frac{|S_{IN}|}{|S|}$；
   3. 重新计算 $N=\frac{\log (1-p)}{\log (1-w^n)}$，动态调整迭代次数。

---

3 RANSAC 算法的优缺点

3.1 优点

• 鲁棒性强：即使数据集中存在大量外点（可达 $50\%$），仍能准确估计模型参数。
• 模型适应性广：适用于直线、圆、单应性矩阵等多种数学模型的参数估计。
• 实现灵活：可与其他估计方法（如最小二乘法）结合，通过内点集优化模型精度。RANSAC先通过迭代等方式找出内点，然后基于内点，使用处理“干净”数据时效果好、但相对不那么鲁棒的估计方法（如最小二乘法）优化模型参数。

3.2 缺点

• 时间复杂度不确定：理论上迭代次数没有上限（除非进行穷举 ），可能导致计算时间不可控。若限制迭代次数，得到的解可能非最优，甚至无法良好拟合数据；增加迭代次数虽能提升获得合理模型的概率，但会耗费更多时间，存在计算成本与模型质量的权衡。
• 参数敏感性：需要设置问题特定的阈值，且只能估计单一模型。
• 初始假设依赖：若内点比例过低或抽样未覆盖足够内点，可能收敛到次优解。

---

4 RANSAC 算法应用实例：圆的拟合

1. 确定最小确定圆方程的参数：从 $3$ 个随机点估计圆参数$(x_0,y_0,r)$。
2. 评估内点的方法：点到圆的距离小于阈值，即 $d=|\sqrt{(x_i-x_0{)}^2+(y_i-y_0{)}^2}-r|<t$。

或者根据RANSAC返回的最大内点集合，使用better but less robust algorithm，如最小二乘法

---

5 RANSAC 算法的拓展与变种

1. 渐进抽样一致性（PROgressive Sample and Consensus, PROSAC）：优先选择可信度高的点进行抽样，减少无效迭代。
2. M估计抽样一致性（M-estimator Sample and Consensus, MSAC）：引入损失函数替代简单的阈值判定，提高模型精度。
3. 最小中位数平方（Least Median Squares, ）：通过最小化残差中位数来抵抗异常值。
4. 最大似然抽样一致性（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