1.提出問題

???????模型參數估計方法，如經典的最小二乘法，可以根據某種給定的目標方程估計并優化模型參數以使其最大程度適應于所有給定的數據集。這些方法都沒有包含檢測并排除異常數據的方法，他們都基于平滑假設：忽略給定的數據集的大小，總有足夠多的準確數據值來消除異常數據的影響。但是在很多實際情況下，平滑假設無法成立，數據中可能包含無法得到補償的嚴重錯誤數據，這時候此類模型參數估計方法將無法使用。例如如下情況：要求用直線擬合圖1.1中的綠色點，顯然，如果用最小二乘法擬合肯定不能得到準確的解，因為錯誤數據太多。如1.2中的藍色點就是經過RANSAC算法后得到的可靠數據點。這個例子就有點類似直線的hough變換，選擇一組投票率最高的點集作為直線擬合的候選數據。

圖1.1????????????????????????????????? ?????????????????????????????????????????????????????????????? 圖1.2

2.算法基本思想

?????? RANSAC為RANdom SAmple Consensus（隨機采樣一致性）的縮寫，它是根據一組包含異常數據的樣本數據集，計算出數據的數學模型參數，得到有效樣本數據的算法。它于1981年由Fischler和Bolles最先提出[1]。
??????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*。
??????RANSAC算法包括了3個輸入的參數：①判斷樣本是否滿足模型的誤差容忍度t。t可以看作為對內點噪聲均方差的假設，對于不同的輸入數據需要采用人工干預的方式預設合適的門限，且該參數對RANSAC性能有很大的影響；②隨機抽取樣本集S的次數。該參數直接影響SC中樣本參與模型參數的檢驗次數，從而影響算法的效率，因為大部分隨機抽樣都受到外點的影響；③表征得到正確模型時，一致集S*的大小N。為了確保得到表征數據集P的正確模型，一般要求一致集足夠大；另外，足夠多的一致樣本使得重新估計的模型參數更精確。
??????RANSAC算法經常用于計算機視覺中，主要解決特征點的匹配中的錯配問題。

轉載于:https://www.cnblogs.com/wl-v/p/5820481.html

總結

以上是生活随笔為你收集整理的RANSANC算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。