5.RANSAC算法原理 | MengHaoの博客

type

status

date

slug

summary

1.RANSAC 直线拟合流程

（RANdom SAmple Consensus，随机抽样一致算法

1. 问题背景

假设你有一组二维点其中大部分点大致分布在一条直线上，但有一些异常点（outliers），它们不符合这条直线。你的目标是找到最能代表大多数点的直线。

其中一些点可以近似拟合出一条直线，这些点称为内点，而其他点则称为外点。如果我们采用简单的最小二乘法来解决这一问题，则不能找到一个比较优的解，原因是最小二乘法会尽量去拟合所有点，而不仅仅是拟合内点，结果被外点严重干扰。

2.设定模型

在这个例子中，我们的模型是直线方程：

其中 a 是斜率，b 是截距。

3.设定超参数

最大迭代次数（max_iterations）：例如 100 次

内点误差阈值（threshold）：例如 2（即点到直线的距离小于 2 被认为是“内点”）

内点最小数量（min_inliers）：只有当某个模型的内点数大于某个阈值（如 50% 数据点），才会被认为是好的模型

4. 迭代 RANSAC

重复以下步骤（最多 max_iterations 次）：

随机选取最少数量的数据点

这里，我们需要两点来确定一条直线

例如，随机选取点 A(2,3) 和 B(6,7)

计算模型（直线方程）

计算斜率

计算截距

得到直线方程

计算所有数据点到该直线的距离

例如，对于数据点，理论值，误差 ∣5.2−5∣=0.2，小于阈值，属于内点

如果某个点距离直线的误差大于阈值 2，则认为它是异常点

统计内点数量

计算有多少点的误差小于阈值（属于内点）

记录内点最多的直线模型

更新最佳模型（如果当前直线的内点数多于历史最佳）

5. 终止条件

迭代满最大次数

找到了足够多的内点（如超过 80% 数据点）

6. 计算最终模型

使用这些内点重新拟合最终的直线（可以用最小二乘法）

得到最终的最佳直线

2.点云粗配准中RANSAC的应用

1.数学本质

RANSAC是一种鲁棒参数估计方法，其优化目标可表示为：

剔除误差较大的对应点，即寻找使内点数量最大化的变换

2.具体实例

1.初始数据

源点云 P（坐标系A）

点ID	X	Y	Z
p1	1.0	2.0	3.0
p2	2.0	3.0	4.0
p3	3.0	4.0	5.0
p4	0.0	1.0	0.0
p5	4.0	5.0	6.0

目标点云 Q（坐标系B）

点ID	X	Y	Z
q1	1.1	2.1	3.1
q2	2.1	3.1	4.1
q3	3.1	4.1	5.1
q4	10.0	10.0	10.0
q5	4.1	5.1	6.1

初始匹配对 M

匹配ID	源点	目标点
1	p1	q1
2	p2	q2
3	p3	q3
4	p4	q4
5	p5	q5

2.参数设定

阈值（threshold）：0.3（误差小于0.3的匹配视为内点）。

最大迭代次数（N）：5次（实际中需按公式计算，这里简化）

3.迭代

迭代1：

随机选择匹配对 {1, 2, 3}（均为内点）

选取点对：

计算变换（参考基于SVD求解变换矩阵）

统计内点：

对全部匹配对 M应用 T：

，误差（内点）。
，误差（外点）。

………….

内点集合：{1, 2, 3, 5}（共4个）。

迭代2：

选取点对：

（p4-q4是噪声）。

计算变换：

因是外点，计算的 T 会偏离真实值，内点数量较少（如仅2个）。

丢弃当前模型，保留迭代1的结果

迭代3~5

类似过程，可能采样到其他组合（如 {1, 3, 5}、{2, 3, 5} 等），但内点数不会超过迭代1的4个。

4.最终结果

最优变换：

内点：{1, 2, 3, 5}（匹配4被剔除）。

配准效果：源点云平移 (0.1,0.1,0.1)(0.1,0.1,0.1) 后与目标点云对齐。

5.具体案例说明

若直接用最小二乘法： •所有匹配点平等参与计算，外点q4=[10,10,10]会大幅拉偏变换结果，导致配准失败。

3.RANSAC的作用：

通过随机采样和投票机制，自动筛选出正确的匹配（内点），仅用内点计算变换，排除外点干扰。

参考论文：

[硕士论文]王海荣计算机技术工程天津大学2017

万方数据知识服务平台