隨機抽樣一致性算法籽暇。
在對應點估計或者stereo matching中常常在用温治。這里進行一些知識點的歸納
先看基本思想，以下大部分翻譯自wikipedia戒悠。
RANSAC算法是采用迭代的算法從一組包含離群點的被觀測數(shù)據(jù)中估計一個數(shù)學模型的參數(shù)熬荆。RANSAC算法只會產(chǎn)生一個在一定概率下合理的結(jié)果，而更多次的迭代會使得這一概率增加绸狐。
RANSAC算法的基本假設是：
- “inliers”（內(nèi)群）數(shù)據(jù)可以通過幾組模型的參數(shù)來敘述其分布卤恳，而“outliers”（離群）數(shù)據(jù)則是不適合模型化的數(shù)據(jù)。
- 數(shù)據(jù)會受到噪聲的影響六孵，噪聲指的是離群，例如從極端的噪聲或錯誤解釋有關(guān)數(shù)據(jù)的測量或不正確的假設幅骄。
- RANSAC假定劫窒，給定一組（通常很小）的內(nèi)存拆座，存在一個程序主巍，可以估算最適用于這一組數(shù)據(jù)模型的參數(shù)。
RANSAC算法的基本步驟是：
- 在數(shù)據(jù)中隨機選擇幾個點設定為內(nèi)群 - hypothetical inliers
- 計算擬合內(nèi)群的模型挪凑。
- 把其他剛才沒選到的點帶入剛才建立的模型中孕索，計算是否為內(nèi)群。
根據(jù)一些模型特定的損失函數(shù)(model specific loss function)躏碳，符合估計模型的那些點被認為是內(nèi)群(consensus set)的一部分 - 記下內(nèi)群數(shù)量搞旭。
- 重復以上步驟多做幾次。
- 比較哪次計算中內(nèi)群數(shù)量最多菇绵，內(nèi)群最多的那次所建的模型就是所要求的解肄渗。
小結(jié)：RANSAC是一種使用了投票機制（voting scheme）來尋找最佳結(jié)果的學習技術(shù)（learning technique）。
以從下圖數(shù)據(jù)的擬合直線問題來看RANSAC：
若使用Least squares method（最小二乘法）咬最，那么outliers會影響到最后的估計結(jié)果翎嫡。
若使用RANSAC算法則不會有這樣的問題。
Pesudo-code
Given:
data - a set of observed data points
model - a model that can be fitted to data points
n - the minimum number of data values required to fit the model
k - the maximum number of iterations allowed in the algorithm
t - a threshold value for determining when a data point fits a model
d - the number of close data values required to assert that a model fits well to data
Return:
bestfit - model parameters which best fit the data (or nul if no good model is found)
iterations = 0
bestfit = nul
besterr = something really large
while iterations < k {
maybeinliers = n randomly selected values from data
maybemodel = model parameters fitted to maybeinliers
alsoinliers = empty set
for every point in data not in maybeinliers {
if point fits maybemodel with an error smaller than t
add point to alsoinliers
}
if the number of elements in alsoinliers is > d {
% this implies that we may have found a good model
% now test how good it is
bettermodel = model parameters fitted to all points in maybeinliers and alsoinliers
thiserr = a measure of how well model fits these points
if thiserr < besterr {
bestfit = bettermodel
besterr = thiserr
}
}
increment iterations
}
matlab code: click here
最后永乌，討論一下RANSAC中的參數(shù)：
t和d需要結(jié)合實際的實驗數(shù)據(jù)以及具體應用來決定惑申。迭代次數(shù)k具伍，可以從進行一定的理論分析。
假設數(shù)據(jù)集中每個點是真正內(nèi)群的概率是w圈驼， 即：
w = 真正內(nèi)群點的數(shù)目/數(shù)據(jù)總共的數(shù)量
假設不知道w的值人芽，那么選擇n個點都是內(nèi)群點的概率為w^n，那么選擇n個點至少有一個是非內(nèi)群點的概率為 1-w^n碗脊；重復k次都沒有全部的n個點都是內(nèi)群的概率是 (1-w^n)^k是表示重復k次啼肩，都至少有一個點是離群點，因此衙伶，RANSAC迭代k次后祈坠，n個點都是內(nèi)群點的概率p的值是：
1 - p = (1-w^n)^k
p = 1 - (1-w^n)^k
若希望成功率高的話，p = 0.99矢劲，當n不變赦拘，那么k越大，p越大芬沉；但w不變躺同，n越大，那么k越大丸逸。
