另一方面,RANSAC介绍随机抽样一致算法(RANdom SAmple Consensus,RANSAC),采用迭代方式根据包括离群点在内的一系列观测数据估计数学模型的参数。 RANSAC算法假设数据包含正确和异常的数据或噪声)。 正确的数据标记为内点inliers,异常数据标记为外点) outliers。 另外,RANSAC假设有一种方法,只要给出正确的数据集,就能够计算出适合这些数据的模型参数。 该算法为核心思想就是随机性和假设性,随机性是指根据正确数据的出现概率随机选择采样数据,根据大数定律,随机性仿真可以近似得到正确的结果假设性是假设提取的样本数据都是正确的数据,并通过使用这些正确数据满足问题的模型计算其他点来评价这次的结果。
RANSAC算法广泛应用于计算机视觉领域和数学领域,如直线拟合、平面拟合、计算图像或点云间的变换矩阵、计算基础矩阵等,使用非常广泛。 本文在介绍RANSAC后,附上两级直线拟合和平面拟合的matlab码。 关于计算机视觉中基于RANSAC框架的矩阵求解问题,有与OpenCV相对应的函数接口。
二、算法的基本思想1)得到一个直线模型,需要两点唯一确定一个直线方程。 所以选择第一步随机个积分。
2)根据这两点,可以计算出这两点表示的模型方程式y=ax b。
)3)将所有数据点应用于该模型来计算误差。
4)找出所有满足误差阈值的点。
5)并且,直到达到一定的反复次数)1) ) )之后,选择其最受支持的模型作为问题的解。 如下图所示。
发现在该数据集中外点和内点的比例基本相等,而RANSAC算法可以找到最佳解。 如果用最小二乘法优化这个问题,由于噪声数据的干扰,一定会得到如下图所示的错误结果。 这是因为最小二乘法是使外点参加讨论的成本优化问题,RANSAC是使用内点进行优化的问题。 实验验证,对于误差为80%的数据集,RANSAC的效果远远优于直接最小二乘法。