RANSAC
- 又称: Random Sample Consensus
- 类别: Sensing › Perception outputs
- 标签: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
随机抽样一致(Random Sample Consensus):一种鲁棒拟合方法,反复用数据的小随机子集拟合模型,并保留与最多点一致的模型,从而忽略离群点。
定义
RANSAC(随机抽样一致,Random Sample Consensus)由 Fischler 和 Bolles 于 1981 年提出,用于从包含大量离群点的数据中估计模型参数。最小二乘拟合使用每一个点,因此少数几个粗大误差就可能把结果拉得远离真值。RANSAC 则重复一个简单的循环:抽取定义模型所需的最少点数(直线两个、平面三个,相机位姿或基础矩阵则是一个较小的固定数目),用这些点拟合模型,然后统计全部数据点中有多少位于模型的阈值范围内。这些点就是一致集,即内点。经过若干次迭代后,保留一致集最大的模型,并且通常用最小二乘对其全部内点重新拟合。
迭代次数由概率决定。若 w 为内点比例,s 为样本大小,则一个随机样本只包含内点的概率为 wˢ,因此要以置信度 p 至少抽到一个干净样本,所需的迭代次数 k 为 k = log(1 − p) / log(1 − wˢ)。当内点比例下降或样本大小增加时,这个数会迅速增长,这就是为什么需要更少点的最小求解器(例如五点相对位姿)在视觉中很重要。内点阈值是另一个关键参数:它应当与真实内点的预期噪声相匹配,并且必须以所测量残差的单位来设定。
许多变体改进了基本循环。MSAC 和 MLESAC 用鲁棒代价而不是原始内点数为假设打分,PROSAC 优先抽取最有希望的匹配,LO-RANSAC 对好的假设做局部细化,自适应版本则随着内点比例被估计出来而更新 k。在机器人领域,RANSAC 用于点云中的平面和基本几何体分割、视觉里程计和 SLAM 中的特征匹配过滤、n 点透视(Perspective-n-Point)位姿估计、基于特征对应的点云配准,以及标定。由于该过程是随机的,除非固定随机种子,否则不同次运行的结果可能不同。
为何重要
真实的传感器数据充满离群点:错误的特征匹配、反射、移动物体,以及属于其他表面的点。RANSAC 是在这些离群点存在的情况下拟合几何模型的标准方法,它位于大多数视觉里程计、SLAM、标定和点云分割流程之中。
主要应用
- 点云中的平面、圆柱和球体分割
- 视觉里程计和 SLAM 中特征匹配的离群点剔除
- 用 n 点透视(Perspective-n-Point)估计相机位姿
- 估计基础矩阵、本质矩阵和单应矩阵
- 基于特征对应的全局点云配准
- 对含噪声的传感器数据拟合直线和标定模型
实际应用
一台移动机械臂在放置物体之前,需要在深度相机的点云中找到桌面。软件对点云降采样,然后运行 RANSAC 平面拟合:它反复选取三个点,计算通过它们的平面,并统计位于距离阈值内的点数,该阈值设定得略高于传感器的深度噪声。内点最多的平面用最小二乘重新拟合,移除其内点,再把平面上方剩余的点聚类为物体。工程师会检查平面的法向量是否大致朝上,因为当视野中有大面积的墙或地面时,RANSAC 可能返回那个表面;他们还在测试中固定随机种子,使结果可复现。
常见误解
- RANSAC 能找到最优模型 — 它返回的是它碰巧抽到的最佳假设,因此结果是概率性的,不同次运行可能不同
- 更多的迭代可以弥补糟糕的阈值 — 阈值决定什么算作一致,选得不好会使结果产生偏差,无论运行多少次迭代
- RANSAC 能应对任意比例的离群点 — 随着内点比例下降,所需迭代次数迅速增长;内点极少时,它可能失败或锁定一个虚假的结构
- RANSAC 只能找到一个模型 — 基本算法只找一个,但顺序变体和多模型变体通过移除内点并重复执行来提取多个结构
谁需要了解
- 感知和计算机视觉工程师
- SLAM 和视觉里程计开发者
- 为操作任务处理点云的工程师
- 标定和计量工程师
相关技术
- 最小二乘拟合(Least-Squares Fitting)
- M 估计(M-Estimators)
- MSAC 和 MLESAC
- PROSAC
- 霍夫变换(Hough Transform)
- Point Cloud Library
相关术语
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
相关项目
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
- MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
- PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
- OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying
视频
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision