RANSAC｜SLAM 點雲圖鑑

Hypothesize-and-verify robust fitting originally applied to the Location Determination Problem; in registration it is the standard coarse-alignment baseline whose runtime grows exponentially with the outlier ratio (per Yang et al., 2021 Sec. I, footnote 1).

技術屬性

欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。

RANSAC 的技術屬性
感測輸入	aerial photograph from about 4,000 ft with a 6 in. lens, digitized on a 2,000 x 2,000 grid (about 2 ft per pixel)、synthetic landmark-to-image correspondences
原文測試平台	simulation、airborne camera (aerial image)
狀態估計	hypothesize-and-verify: randomly select a minimal subset of n data points to instantiate the model, collect the consensus set within an error tolerance, and if its size reaches threshold t refit the model (e.g., least squares) on the consensus set; otherwise resample; after k trials use the largest consensus set or fail; expected trials E(k) = w^(-n), and k = log(1-z)/log(1-w^n) for confidence z
資料關聯	original: landmark-to-image correspondences from error-prone feature detectors (cross correlation in the aerial test); consensus judged with image-plane error ellipses derived from perturbing the three selected points; point cloud registration use with putative 3D correspondences is a later application (secondary)
時間表示	不適用
去畸變	不適用
迴圈閉合	none
全域最佳化	none
地圖表示	不適用
先驗資訊	none
可輸出幾何	in the original LDP application: 3-D location of the centre of perspective with an error estimate, and the spatial orientation of the image plane
計算需求	about 1 s per camera position considered for the synthetic LDP program; hardware not reported

使用設備

原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。

原文使用的設備
類別	型號（原文寫法）	角色	資料集	原文規格	出處
相機	aerial camera with 6 in. lens	方法輸入	未標示	image taken from approximately 4,000 ft; digitized on a 2,000 x 2,000 pixel grid, about 2 ft per pixel ground resolution	(Fischler & Bolles, 1981, Sec. IV.E)

作者報告的優勢與限制

優勢

interprets and smooths data containing a significant percentage of gross errors (abstract)
in an LDP with 5 gross errors among 20 correspondences a least-squares pruning heuristic kept 3 gross errors, while RANSAC found the correct solution on the second triple with none (Sec. IV.C)
in 50 synthetic LDPs no gross error entered the final consensus set (Sec. IV.D, Table I)
real aerial image: consensus of 17 on the first triple, extended to all 22 good correspondences (Sec. IV.E)
closed-form P3P solution with up to four real solutions; unique solutions for coplanar P4P and general-position P6P (Sec. III, Appendices A-B)

限制

runtime grows exponentially with outlier ratio and performs poorly at high outlier rates (Yang et al., 2021 Sec. I, secondary)
three parameters must be set: error tolerance, number of trials and consensus threshold t (Sec. II)
expected trials rise as w^(-n), for example 16 for w = 0.5 and n = 4 but 625 for w = 0.2 and n = 4, and SD(k) is about equal to E(k), so two to three times E(k) trials may be needed (Sec. II.B)
multiple physically real solutions can exist for P3P, P4P and P5P, so a sample may yield ambiguous poses (Sec. III)

營建工程相關證據

原文未報告

原文驗證環境：模擬

報告的性能數據

以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。

本方法共出現在 11 個比較組，合計 75 筆紀錄。以下列出本方法紀錄最多的 4 組，其餘 7 組列在最後，並連到性能比較頁。

Fischler & Bolles, 1981 · Table I 本方法 30 筆

指標資料集與序列

表格設定（擷取紀錄原文）：Ten typical of 50 synthetic LDPs, 30 landmark-to-image correspondences each; gross errors at least 10 px off, good ones with 1 px std; RANSAC avoided gross errors in the final consensus set in all problems (Fischler & Bolles, 1981, Table I)

No. of correspondences in final consensus set，50 synthetic location determination problems · typical problem 1 (w=0.8)

這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Fischler & Bolles, 1981 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。

統計量：原文未報告；對齊方式：未對齊；單位：count；場景：simulation

數值與出處
方法（原文寫法）	報告值	出處
RANSAC/LD本方法原文提出	19 count	(Fischler & Bolles, 1981, Table I)

Yang et al., 2021 · Table II 本方法 18 筆

指標資料集與序列

表格設定（擷取紀錄原文，這些數值分屬表中不同部分）：(Yang et al., 2021, Table II)

3DMatch test scenes, 3DSmoothNet correspondences, success = rotation error < 10 deg and translation error < 30 cm; beta = 5 cm; CERT = subset certified with sub-optimality gap 3%; Xeon Platinum 8259CL, 12 threads
Same setting as other Table II rows

percentage of correct registration results，3DMatch · Kitchen

只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。

這些是 Yang et al., 2021 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。

統計量：原文未報告；對齊方式：未對齊；單位：%；場景：indoor RGB-D scans

資料來源作者報告值(Yang et al., 2021, Table II)

數值與出處
方法（原文寫法）	報告值	出處
RANSAC-1K本方法	91.3%	(Yang et al., 2021, Table II)
RANSAC-10K本方法	97.2%	(Yang et al., 2021, Table II)
TEASER++原文提出	98.6%	(Yang et al., 2021, Table II)
TEASER++ (CERT)原文提出	99.4%	(Yang et al., 2021, Table II)

Fischler & Bolles, 1981 · Text Sec. IV.E 本方法 8 筆

指標

資料集與序列real aerial image · single image

表格設定（擷取紀錄原文）：Aerial image from about 4,000 ft with 6 in. lens, digitized 2,000 x 2,000 px (about 2 ft per px); 25 landmarks found by cross correlation, 3 gross errors (Fischler & Bolles, 1981, Text Sec. IV.E)

consensus set size found on the first triple，real aerial image · single image

統計量：原文未報告；對齊方式：未對齊；單位：count；場景：aerial imagery

數值與出處
方法（原文寫法）	報告值	出處
RANSAC/LD本方法原文提出	17 count	(Fischler & Bolles, 1981, Sec. IV.E)

Zhang et al., 2024b · Table 1 本方法 6 筆

指標

資料集與序列ISPRS benchmark on indoor modelling · Models 01-05 (250 samples)

表格設定（擷取紀錄原文）：Coarse registration on 250 samples (50 per model) with random rigid perturbations (roll and pitch within 30 deg, yaw within 180 deg, translation within 10 m); only successful results with RE < 45 deg and TE < 10 m are included; A50, A75 and A95 quantiles of rotation and translation error against the benchmark alignment (Zhang et al., 2024b, Table 1)

RE_50, rotation error 50th percentile，ISPRS benchmark on indoor modelling · Models 01-05 (250 samples)

只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。

這些是 Zhang et al., 2024b 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。

統計量：中位數（median）；對齊方式：未對齊；單位：deg；場景：building interiors from the ISPRS indoor modelling benchmark (Models 01-05)

資料來源作者報告值(Zhang et al., 2024b, Table 1)

數值與出處
方法（原文寫法）	報告值	出處
GMMTree (initialised with FPFH-RANSAC)	4.466 deg	(Zhang et al., 2024b, Table 1)
FilterReg (initialised with FPFH-RANSAC)	3.59 deg	(Zhang et al., 2024b, Table 1)
GO-ICP	4.178 deg	(Zhang et al., 2024b, Table 1)
Super4PCS	2.208 deg	(Zhang et al., 2024b, Table 1)
FGR	27.139 deg	(Zhang et al., 2024b, Table 1)
RANSAC (FPFH features)本方法	5.477 deg	(Zhang et al., 2024b, Table 1)
RMMG	1.673 deg	(Zhang et al., 2024b, Table 1)
PLADE	0.424 deg	(Zhang et al., 2024b, Table 1)
DCP	34.865 deg	(Zhang et al., 2024b, Table 1)
PointNetLK	11.741 deg	(Zhang et al., 2024b, Table 1)
Ours (primitive-level coarse registration)原文提出	0.272 deg	(Zhang et al., 2024b, Table 1)

其他比較組

列出其餘 7 個比較組

Qin et al., 2023 · Table 5本方法 5 筆；Augmented ICL-NUIM
Fischler & Bolles, 1981 · Text Sec. IV.C本方法 2 筆；synthetic LDP (20 landmarks)
Yang et al., 2020b · Text Sec.V-A P-REG本方法 2 筆；Stanford 3D Scanning Repository Bunny
Fischler & Bolles, 1981 · Text Sec. IV.D本方法 1 筆；50 synthetic location determination problems
Yang et al., 2020b · Text Sec.V-A G-REG本方法 1 筆；PASCAL+ (car-2 mesh)
Yang et al., 2020b · Text Sec.V-C本方法 1 筆；FG3DCar
Zhang et al., 2024b · Text Sec.4.1.2本方法 1 筆；ISPRS benchmark on indoor modelling

來源

Fischler & Bolles, 1981
Martin A. Fischler, Robert C. Bolles（1981）Random sample consensusCommunications of the ACM, 24(6):381-395
DOI 10.1145/358669.358692
同儕審查已出版已讀全文經典查證後修正

回到方法圖鑑