Open Source Robotics

精选高质量开源机器人项目、工具和软件,推动机器人社区发展。

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

本网站需要 JavaScript 才能正常运行。请启用 JavaScript 以浏览我们的开源机器人项目。