ransac

RANSAC為Random Sample Consensus的縮寫，它是根據一組包含異常數據的樣本數據集，計算出數據的數學模型參數，得到有效樣本數據的算法。它於1981年由Fischler和Bolles最先提出。

RANSAC算法經常用於計算機視覺中。例如，在立體視覺領域中同時解決一對相機的匹配點問題及基本矩陣的計算。

基本介紹

• 外文名：Random Sample Consensus
• 提出者：Fischler，Bolles
• 提出時間：1981年
• 簡稱：RANSAC

算法簡介

RANSAC算法的基本假設是樣本中包含正確數據(inliers，可以被模型描述的數據)，也包含異常數據(outliers，偏離正常範圍很遠、無法適應數學模型的數據)，即數據集中含有噪聲。這些異常數據可能是由於錯誤的測量、錯誤的假設、錯誤的計算等產生的。同時RANSAC也假設，給定一組正確的數據，存在可以計算出符合這些數據的模型參數的方法。

基本思想描述

RANSAC基本思想描述如下：

①考慮一個最小抽樣集的勢為n的模型(n為初始化模型參數所需的最小樣本數)和一個樣本集P，集合P的樣本數#(P)>n，從P中隨機抽取包含n個樣本的P的子集S初始化模型M；

②余集SC=P\S中與模型M的誤差小於某一設定閾值t的樣本集以及S構成S*。S*認為是內點集，它們構成S的一致集(Consensus Set)；

③若#(S*)≥N，認為得到正確的模型參數，並利用集S*(內點inliers)採用最小二乘等方法重新計算新的模型M*；重新隨機抽取新的S，重複以上過程。

④在完成一定的抽樣次數後，若未找到一致集則算法失敗，否則選取抽樣後得到的最大一致集判斷內外點，算法結束。

算法最佳化策略

①如果在選取子集S時可以根據某些已知的樣本特性等採用特定的選取方案或有約束的隨機選取來代替原來的完全隨機選取；

②當通過一致集S*計算出模型M*後，可以將P中所有與模型M*的誤差小於t的樣本加入S*，然後重新計算M*。