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:隨機抽樣一致
發佈留言