隨機抽樣一致

维基百科,自由的百科全书
跳转至: 导航搜索

随机抽样一致算法(RANdom SAmple Consensus,RANSAC)。它采用迭代的方式从一組包含離群的被觀測數據中估算出數學模型的參數。 RANSAC是一個非確定性算法,在某種意義上說,它會產生一個在一定概率下合理的結果,而更多次的迭代会使这一概率增加。此RANSAC算法在1981年由Fischler和Bolles首次提出。

RANSAC的基本假設是

  1. 內群」數據可以通過幾組模型的參數來敘述其分佈,而「離群」數據則是不適合模型化的數據。
  2. 數據會受雜訊影響,雜訊指的是離群,例如從極端的雜訊或錯誤解釋有關數據的測量或不正確的假設。
  3. RANSAC假定,給定一組(通常很小)的內群,存在一個程序,這個程序可以估算最佳解釋或最適用於這一數據模型的參數。

範例[编辑]

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

概述[编辑]

  1. 在數據中隨機選擇幾個點設定為內群
  2. 計算適合內群的模型
  3. 把其它剛才沒選到的點帶入剛才建立的模型中,計算是否為內群
  4. 記下內群數量
  5. 重複以上步驟多做幾次
  6. 比較哪次計算中內群數量最多,內群最多的那次所建的模型就是我們所要求的解

這裡有幾個問題

  1. 一開始的時候我們要隨機選擇多少點(n)
  2. 以及要重複做多少次(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

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

應用[编辑]

RANSAC常被用在電腦視覺 ,例如,對應點問題 和 估算立體攝影機雙眼相對點的基本矩陣。

参考资料[编辑]

  • Martin A. Fischler and Robert C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Comm. of the ACM. 1981.June, 24 (6): 381–395. doi:10.1145/358669.358692. 
  • David A. Forsyth and Jean Ponce. Computer Vision, a modern approach. Prentice Hall. 2003. ISBN 0-13-085198-1. 
  • Richard Hartley and Andrew Zisserman. Multiple View Geometry in Computer Vision 2nd. Cambridge University Press. 2003. 
  • P.H.S. Torr and D.W. Murray. The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix. International Journal of Computer Vision. 1997, 24 (3): 271–300. doi:10.1023/A:1007927408552. 
  • Ondrej Chum. Two-View Geometry Estimation by Random Sample and Consensus. PhD Thesis. 2005. 
  • Sunglok Choi, Taemin Kim, and Wonpil Yu. Performance Evaluation of RANSAC Family. In Proceedings of the British Machine Vision Conference (BMVC). 2009. 

外部链接[编辑]