RANSAC 是在一群資料中，隨機選取數筆資料，用以計算出符合這數筆資料的模型，並以此模型將這群資料作分類，資料符合該模型的為 inlier，否則為 outlier，因為是隨機選取數筆資料，所以是一個非確定性的算法，但經過多次的選取，根據機率，其建立出來的模型，有一定機率符合大部分或全部的資料，此時即為最佳解，也就是該群資料所能代表的最佳模型。
原本的資料群分佈可能如下，看似沒什麼規律性：
經由 RANSAC 演算法，嘗試找尋一直線方程式，以符合較多數的資料群，可能得到如下結果：
在線上的藍色資料群即為該直線方程式的 Inlier，紅色資料群則視為該直線方程式的 Outlier。
RANSAC 的成功機率
在一群資料中，假設總共有 K 筆，任意的一筆資料，其 inlier 的機率為 p，則其 outlier 的機率為 (1-p)，且需要 8 筆資料才能計算出該 8 筆資料所代表的模型，則：
任選 8 筆資料，皆為 inlier 的機率大約為 p8 (在 K >> 8 的情況下)
而任選 8 筆資料，有任一筆資料不為 inlier 的機率為 (1 - p8)
假設 RANSAC 會作 T 次 - 任選 8 筆資料來計算其所代表的模型，則其每次都有任意 1 筆資料不為 inlier 的機率為 (1 - p8)T，所以其 8 筆資料皆為 inler 的機率(也就是可以成功計算出正確模型的機率) 為：
P = 1 - (1 - p8)T
推算出：
=> 1 - p = (1 - p8)T
=> T = log(1 - P) / log(1 - p8)
也就是說，利用上式，可以推算出如果要求可以正確計算出模型的機率為 0.99，則其所需要任選 8 筆資料來作計算求模型的次數為何，才能達到要求。
Reference
文字內容 或 影像內容 部份參考、引用自網路，如有侵權，請告知，謝謝。
全站熱搜
留言列表
硬體 (1)