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 以瀏覽我們的開源機器人專案。