0%

随机抽样一致算法(RANdom SAmple Consensus,RANSAC)

一、RANSAC介绍
   随机抽样一致算法(RANdom SAmple Consensus,RANSAC),采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。RANSAC算法假设数据中包含正确数据和异常数据(或称为噪声)。正确数据记为内点(inliers),异常数据记为外点(outliers)。同时RANSAC也假设,给定一组正确的数据,存在可以计算出符合这些数据的模型参数的方法。该算法核心思想就是随机性和假设性,随机性是根据正确数据出现概率去随机选取抽样数据,根据大数定律,随机性模拟可以近似得到正确结果。假设性是假设选取出的抽样数据都是正确数据,然后用这些正确数据通过问题满足的模型,去计算其他点,然后对这次结果进行一个评分。
二、算法基本思想
(1)要得到一个直线模型,需要两个点唯一确定一个直线方程。所以第一步随机选择两个点。
(2)通过这两个点,可以计算出这两个点所表示的模型方程y=ax+b。
(3)将所有的数据点套到这个模型中计算误差。
(4)找到所有满足误差阈值的点。
(5)然后我们再重复(1)~(4)这个过程,直到达到一定迭代次数后,选出那个被支持的最多的模型,作为问题的解。如下图所示

img

可以发现,虽然这个数据集中外点和内点的比例几乎相等,但是RANSAC算法还是能找到最合适的解。这个问题如果使用最小二乘法进行优化,由于噪声数据的干扰,我们得到的结果肯定是一个错误的结果,如下图所示。这是由于最小二乘法是一个将外点参与讨论的代价优化问题,而RANSAC是一个使用内点进行优化的问题。经实验验证,对于包含80%误差的数据集,RANSAC的效果远优于直接的最小二乘法。

img