三维点云处理（十八）：RANSAC 随机采样一致性拟合
# 三维点云处理：RANSAC 鲁棒拟合——随机采样一致性算法
在三维激光雷达（LiDAR）点云预处理与三维重建中，地面剥离（Ground Plane Extraction）、建筑物墙面分割以及车道线/几何基元提取是核心步骤。原始点云中常常混杂着高达 50% 以上的离群噪点（Outliers）。最小二乘法（LSQ）会被严重扯偏，而霍夫变换在处理多参数模型时面临维度灾难。
RANSAC（RANdom SAmple Consensus，随机采样一致性） 凭借其简单、通用且高效的“假设-验证”范式，成为了三维点云几何拟合事实上的标准算法。
本文系统梳理 RANSAC 算法流程、基于卡方分布 的阈值确定、迭代次数 的完整数学推导，以及结合最小二乘微调的工程技巧。
一、 RANSAC 核心哲学：假设-验证 (Hypothesize & Verify)
RANSAC 放弃了对全量数据进行全局优化的传统思路，而是采用非确定性的随机采样与一致性投票机制。
1.1 最小样本点集 (Minimal Sample Size )
拟合不同的几何模型，解出方程所必须的最小不共线样本点数 各不相同：
| 几何模型 | 最小样本点数 | 拟合残差定义 |
|---|---|---|
| 2D / 3D 直线 | 点到直线的垂直欧氏距离 | |
| 3D 平面 (Plane) | 点到平面的垂直法向距离 | |
| 2D 圆 (Circle) | 点到圆心的距离与半径之差 $ | |
| 3D 球面 (Sphere) | 点到球心的距离与半径之差 | |
| 3D 圆柱面 (Cylinder) | (含法向量) 或 | 点到轴线的距离与圆柱半径之差 |
二、 内点残差阈值 的确定（基于卡方分布 ）
如何合理选择判定内点（Inlier）的距离阈值 ？
假设内点数据到拟合模型的正交测量误差服从均值为 0、方差为 的高斯分布 。
残差平方和归一化后服从自由度为 的卡方分布（Chi-Squared Distribution ）。为了保证 95% 置信度 的内点不被误剔除，查表选择阈值 ：
三、 采样迭代次数 的完整数学推导
RANSAC 是一个随机化算法。为了保证在至少 99% 的概率下抽到一组完全不含离群噪点的纯净最小样本集，需要迭代运行多少次 ？
3.1 推导过程
定义变量：
- ：数据集中离群点比例（Outlier Ratio），即内点比例为 ；
- ：求解模型的最小样本点数；
- ：RANSAC 的采样迭代次数；
- ：算法成功找到纯净样本集的期望置信度（通常设为 ）。
推导步骤：
- 一次随机抽样中，连续抽取 个点全为内点的概率为：
- 一次随机抽样中，至少包含 1 个离群点（采样失败）的概率为：
- 连续进行 次独立抽样，**全部 次都失败（全部污染）**的概率为：
- 要求 次抽样中至少有一次成功的概率大于等于期望置信度 ：
- 两边取自然对数 ：
最终导出 RANSAC 采样迭代次数 的闭式公式：
3.2 迭代次数 对照表 ()
下表展示了在置信度 下，不同离群点比例 与最小样本数 所需的最小迭代次数 ：
| 样本数 / 模型 | ||||||
|---|---|---|---|---|---|---|
| (直线) | 2 次 | 3 次 | 5 次 | 7 次 | 11 次 | 17 次 |
| (平面/圆) | 3 次 | 4 次 | 7 次 | 11 次 | 19 次 | 35 次 |
| (球面) | 3 次 | 5 次 | 9 次 | 17 次 | 34 次 | 72 次 |
| (圆柱面) | 4 次 | 6 次 | 12 次 | 26 次 | 57 次 | 146 次 |
| (基础矩阵) | 5 次 | 9 次 | 26 次 | 78 次 | 272 次 | 1177 次 |
- 规律总结：当离群点比例 增加或模型参数增多（ 变大）时，所需迭代次数 呈指数级增长。
四、 工程实用技巧 (Practical Tricks)
4.1 动态早停策略 (Dynamic Termination)
在实际运行中，离群点比例 通常是未知数。
- 算法：初始时假设 （即 ）。每次迭代中，若找到了包含最多内点的新模型，根据当前实际内点率重新估计 ，并动态下调更新剩余迭代次数 。
- 目标阈值：当内点数达到预估内点目标 时立即提前终止。
4.2 结合最小二乘精细微调 (LSQ Refinement)
- 局限：RANSAC 候选模型仅由最小点集 （如 3 个点）算出，容易受这 个点的测量微小噪声影响；
- 微调策略：在 RANSAC 选出包含最多内点的最佳集合 后，提取该集合内的所有内点，重新运行一次线性/非线性最小二乘 (LSQ)，拟合出全局最优解。
4.3 “内点率 (Inlier Ratio)”的工程调参经验与核心优势
为什么 RANSAC 能在 50% 甚至更高的噪声下存活？其核心数学优势在于解耦：LSQ 强迫所有点（包括噪点）参与模型计算，而 RANSAC 仅通过数学上求解方程所必需的最少点数 来构建模型，从而完美避开了全局噪点的污染。
在工程落地时，为了避免 RANSAC 陷入无尽的随机搜索，通常需要设置期望的最小内点率阈值 (Expected Inlier Ratio) 以实现早停：
- 结构化场景 (如室内墙面提取)：墙面往往占据大面积，内点率极高。可将期望内点率设为
60% ~ 80%，一旦找到满足条件的模型即刻终止。 - 非结构化/野外场景 (如树木、复杂地形)：目标可能被严重遮挡，内点率极低。此时需降低预期（例如设为
20%），并赋予更大的最大迭代次数 以确保不会遗漏。 - 防伪峰值机制：如果抽样得出的最大内点率依然低于设定的
min_inlier_ratio(例如 5%)，则应抛弃该结果，判定为“当前点云中不存在该几何目标”，这在点云语义分割中是极其重要的容错机制。
五、 算法总结与优缺点
| 维度 | 特性总结 |
|---|---|
| 计算复杂度 | ，其中 为迭代次数， 为样本数， 为点云总数 |
| 算法优点 | 1. 简单通用，适用于任意可建立方程的几何与物理模型； 2. 极度鲁棒，即使内点率低至 10%~20% 仍能高效收敛； 3. 计算开销小，无需离散化高维参数空间（避开了霍夫变换的维度灾难）。 |
| 算法缺点 | 1. 需设定内点距离判定阈值 ； 2. 属于非确定性算法（每次运行结果有极小概率随机波动）； 3. 当离群点比例极高（如 ）或模型复杂度极高（）时，所需迭代次数 会剧烈爆炸。 |