隨機抽樣一致演算法

RANSAC，即隨機抽樣一致（Random Sample Consensus），由 Martin Fischler 與 Robert Bolles 於 1981 年提出，是一種在資料被離群值（outlier，即根本不服從模型的點）污染時，仍能穩健地對資料擬合模型的方法。這正是特徵比對之後的情況：所提出的對應中有很大一部分是錯的，而普通的最小平方擬合會被它們毀掉，因為最小平方試圖滿足每一個點，包括那些胡言亂語的點。RANSAC 的洞見是把策略反轉：不去擬合全部資料並寄望離群值彼此抵銷，而是反覆擬合微小的隨機子集，讓資料投票決定哪個擬合最好。

這個演算法是一個迴圈。隨機挑選定義模型所需的最少點數（直線是 2 點；單應矩陣是 4 組點對應）。對那個最小樣本精確地擬合模型。然後拿其餘每一個資料點來檢驗這個候選模型，計算有多少點在容差內與它相符；相符的點是內群值（inlier），其數目就是該模型的一致度（consensus）。對許多隨機樣本重複，保留一致集最大的模型。最後，用該模型的全部內群值（以最小平方）重新擬合，得到精確的估計。勝出的模型就是最多點背書的那個，而離群值因為彼此不一致且不相關，絕不會偶然形成一個大的一致集。

美妙之處在於所需的迭代次數是可預測且不多的。若資料中有某個比例是內群值，則隨機最小樣本完全不含離群值的機率是可計算的，由此可算出要以高信心（比方說 99%）抽到至少一個乾淨樣本所需的試驗次數。關鍵是，這取決於內群值比例與樣本大小，而非點的總數，因此 RANSAC 能擴展到大型資料集。較小的最小樣本（需要較少的點）會讓乾淨樣本的機率大得多，這就是為什麼最小解算器（minimal solver）如此受重視。

RANSAC 有幾個支配其行為的旋鈕：內群值門檻（一個點要多接近才算相符）、信心水準，以及最大迭代次數。門檻設得太緊會剔除好的內群值；太鬆則讓離群值溜進來。存在許多改良變體：MLESAC 以似然度而非僅靠計數來為內群值加權，PROSAC 先抽樣有希望的配對以更快收斂，LO-RANSAC 加入局部最佳化步驟，而 MAGSAC++ 則免去選擇硬門檻的需要。RANSAC 及其後裔在任何需要穩健幾何估計之處都不可或缺，包括單應與基本矩陣估計、相機姿態（PnP）、點雲配準與 SLAM。