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*。