茶年 · 中文维基百科

隨機抽樣一致

Wikipedia · 2026-06-19 维基百科 👁 1 阅读

随机抽样一致算法（RANdom SAmple Consensus，RANSAC）是一种迭代方法，用于从一组包含异常值的观测数据中估计数学模型的参数，也可以被解释为一种异常值检测方法。RANSAC是一個非确定性算法，它會產生一個在一定概率下合理的結果，而迭代的次数增加会使这一概率上升。此RANSAC算法最初在1981年最初由Fischler和Bolles首次在国际斯坦福研究所上发表。

RANSAC的基本假設是
#「內群」（inlier，似乎譯為內點群更加妥當，即正常數據，正確數據）數據可以通過幾組模型的參數來敘述其分佈，而「離群」（outlier，似乎譯為外點群更加妥當，異常數​​據）數據則是不適合模型化的數據。
#數據會受雜訊影響，雜訊指的是離群，例如從極端的雜訊或錯誤解釋有關數據的測量或不正確的假設。
#RANSAC假定，給定一組（通常很小）的內點群，存在一個程序，這個程序可以估算最佳解釋或最適用於這一數據模型的參數。

範例
這裡用一個簡單的例子來說明：在一組數據點中找到一條最適合的線。假設，此有一組集合包含了內點群以及外點群，其中內點群包含可以被擬合到線段上的點，而外點群則是無法被擬合的點。如果我們用簡單的最小二乘法來找此線，我們將無法得到一條適合於內點群的直線，因為最小二乘法會受外點群影響而影響其結果。而用RANSAC，可以只由內點群來計算出模型，而且概率還夠高。然而，RANSAC無法保證結果一定最好，所以必須小心選擇參數，使其能有足夠的概率。

Image:Line_with_outliers.svg|包含許多離群的一組數據，要找一條最適合的線。
Image:Fitted_line.svg|RANSAC找到的線，離群值對結果沒影響（藍色點為內群，紅色點為離群）

概述
#在數據中隨機選擇若干個點設定為內點群
#計算拟合內點群的模型
#把其它剛才沒選到的點帶入剛才建立的模型中，計算是否屬於內點群
#記下內點群數量
#重複以上步驟
#比較哪次計算中內點群數量最多，內點群最多的那次所建的模型就是我們所要求的解

這裡有幾個問題
#一開始的時候我們要隨機選擇多少點（n）
#以及要重複做多少次（k）

參數決定
假設每個點是真正內點群的機率是 w，则：

:w = 真正內點群的數目 / 數據總數

通常我們不知道 w 是多少，w^n 是所選擇的 n 個點都是內點群的機率，1-w^n 是所選擇的 n 個點至少有一個不是內點群的機率，(1-w^n)^k 是表示重複 k 次都沒有全部的 n 個點都是內點群的機率，假設算法跑 k 次以後成功的機率是 p，那麼：

:
1-p=(1-w^n)^k \,

:
p=1-(1-w^n)^k \,

:
k = \frac{\log(1 - p)}{\log(1 - w^n)}

所以如果希望成功機率高，p=0.99，
當 n 不變時，k 越大，p 越大，
當 w 不變時，n 越大，所需的 k 就越大，
通常 w 未知，所以 n 選小一點比較好。

應用
RANSAC算法经常用在计算机视觉领域，例如，对于一对立体相机，同时求解其和估计它们之间的基础矩阵。

参考资料
*
*
*
*
*
*

外部链接

#穩健統計學 #計算機視覺 #統計演算法

评论 (0)

  • 还没有评论，来抢沙发吧。