淺談ransac算法

n  RANSAC算法

RANdom SAmple Consensus（隨機抽樣一致）的縮寫，它是根據(jù)一組包含異常數(shù)據(jù)的樣本數(shù)據(jù)集，通過迭代方式估計數(shù)學(xué)模型的參數(shù)，計算出數(shù)據(jù)的數(shù)學(xué)模型參數(shù)，得到有效樣本數(shù)據(jù)的算法。

對于RANSAC算法有一個基本的假設(shè)：樣本中包含正確數(shù)據(jù)(inliers，符合模型的數(shù)據(jù))和異常數(shù)據(jù)(Outliers，不符合模型的數(shù)據(jù))，即數(shù)據(jù)集中含有噪聲。這些異常數(shù)據(jù)可能是由于錯誤的測量、錯誤的假設(shè)、錯誤的計算等產(chǎn)生的。

RANSAC全名為RANdom SAmple Consensus，一般譯作隨機抽樣一致算法，是一種通用且非常成功的估計算法，它能夠應(yīng)付大比例野值的情況。為了可視化，我們先考慮一個簡單的例子，估計一組二維點的直線擬合。具體問題可以看下圖。

二維點直線擬合

RANSAC的目的就是排除掉那些在變換過程中出錯了的那些野值點（上圖中的空心點）。由于是直線擬合，故可以隨機選擇兩個點，這兩點定義一條直線，這條線的支集由在一定距離閾值內(nèi)的點數(shù)來度量，隨機采樣重復(fù)多次，具有最 大支集的線就是魯棒擬合，而此時在距離閾值內(nèi)的點就是內(nèi)點，并組成一致集。

直線的魯棒擬合

上圖是一條魯棒的擬合直線，我們選定的線<a,b>的支集有9個點，它是點數(shù)最 高的直線之一，通過點數(shù)度量可以讓我們排除掉直線外的野值點。更一般地說，我們希望用模型去擬合數(shù)據(jù)，隨機采樣出足以確定模型的最小數(shù)據(jù)集。

n  Ransac優(yōu)缺點

優(yōu)點：它能魯棒的估計模型參數(shù)。例如，它能從包含大量局外點的數(shù)據(jù)集中估計出高精度的參數(shù)。

缺點：

?  它計算參數(shù)的迭代次數(shù)沒有上限；如果設(shè)置迭代次數(shù)的上限，得到的結(jié)果可能不是最優(yōu)的結(jié)果，甚至可能得到錯誤的結(jié)果。

?  RANSAC只有一定的概率得到可信的模型，概率與迭代次數(shù)成正比。

?  它要求設(shè)置跟問題相關(guān)的閥值。

?  RANSAC只能從特定的數(shù)據(jù)集中估計出一個模型，如果存在兩個（或多個）模型，RANSAC不能找到別的模型。

?  要求數(shù)學(xué)模型已知

n  RANSAC和最小二乘法

隨機抽樣算法（RANSAC），采用迭代的方式從一組包含離群的被觀測數(shù)據(jù)中估算出數(shù)學(xué)模型的參數(shù)。區(qū)別于最小二乘法，最小二乘法是考慮了所有的樣本點擬合的曲線。而RANSAC是從樣本點中選出幾個點，擬合曲線方程，根據(jù)容忍范圍來判斷所“夾”住的點數(shù)，不斷迭代，最終來確認(rèn)目標(biāo)曲線。它是根據(jù)曲線周邊的樣本點數(shù)，和閾值來確定的。在一定程度上，排除了最遠的樣本點影響。