RANSAC 演算法




RANSAC 是 ”RANdom SAmple Consensus” 的縮寫,他是一個從包含許多 outliers 的資料點集合裡面,估計出實際 model 的參數的演算法。

假設
data: 所有資料點
n: 計算 model 的參數所需的最少點數
k: number of iterations
t: 估計資料點是否 fit 一個 model 的 threshold
d: 如果超過 d 個點 fit 這個 model (即誤差小於 t),表示這個 model 已經初步符合需求

我們希望找出下面幾個東西:
1. 最好的 model 的參數?
2. 最小的誤差是多少?
3. 最佳的 consensus set (符合 model 的資料點的集合) 包含哪些點?

RANSAC 演算法大致上是下面這樣的:

1. 從 data 裡面隨機挑選 n 個點
2. 計算出 model 的參數
3. 將每一個資料點依序的計算跟 model 的誤差,如果誤差小於 t ,則將資料點放進去 Consensus set 中,表示這個資料點是 inliers 。
4. 如果最後超過 d 個點被放在 Consensus set 裡面,表示這個 model 是可行的。記錄下 model 的誤差,重複 1~4 計算擁有最小的誤差的 model ,直到迴圈的次數等於 k 。

Reference:
http://en.wikipedia.org/wiki/RANSAC




Be the first to comment

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.