淺談ransac算法

n  RANSAC算法

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

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

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

二維點(diǎn)直線擬合

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

直線的魯棒擬合

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

n  Ransac優(yōu)缺點(diǎn)

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

缺點(diǎn)：

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

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

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

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

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

n  RANSAC和最小二乘法

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