隨機抽樣一致 RANSAC ( Random Sample Consensus)

RANSAC

隨機抽樣一致（RANdom SAmple Consensus，RANSAC），是一種配對演算法，在1981年由Fischler、Bolles提出。利用隨機抽樣的方式降低離群點(outlier)的影響，可在包含雜訊的資料中尋找符合特徵的目標，並透過多次的迭代讓結果可以趨近於期望目標。

RANSAC是一種非確定性演算法，因為是採用隨機抽樣的方式，會存在成功率的問題，而每次迭代都會進一步提升機率。就像抽獎一樣，假設大獎機率1%，抽100次一定比抽1次容易中，但抽100次的代價比抽1次大。

因此當配對機率與迭代次數搭配達到平衡時，會讓RANSAC在尋找目標時的效率提高。

在這類數據的匹配上，最小平方法容易受到離群點的影響，很難找到符合的目標，使用RANSAC更容易找到數據的內群點(inlier)。

RANSAC動態展示

如圖有一組帶有雜訊的資料集，透過迭代隨機抽樣取集合內的任一兩點連成一線，計算在線段的範圍(d)內的資料點數量並記錄，視為一次循環。當執行多次(n)後，取最多資料點的線段為配對結果。

實際應用

RANSAC常用於機器視覺矯正，當有兩顆以上的相機鏡頭拍攝的影像，可以透過RANSAC找到鏡頭之間的轉換矩陣。因為影像中各種光影視角的變化，是一種雜訊多的資料，透過此方法可以有效地排除離群點。

參考資料

• Martin A. Fischler and Robert C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Comm. of the ACM. June 1981, 24 (6): 381–395. doi:10.1145/358669.358692.
• 拾人牙慧：RANSAC (RANdom SAmple Consensus)
• 演算法筆記：Fitting
• WiKI：隨機抽樣一致