RANSAC基本原理

大家好，欢迎来到IT知识分享网。

Reference：
1.计算机视觉基本原理——RANSAC

1. RANSAC简介

RANSAC(RAndom SAmple Consensus,随机采样一致) 算法是从一组含有 外点(outliers) 的数据中正确估计数学模型参数的迭代算法。“外点”一般指的是数据中的噪声，比如说匹配中的误匹配和估计曲线中的离群点。所以，RANSAC 也是一种“外点”检测算法。RANSAC 算法是一种不确定算法，它只能在一种概率下产生结果，并且这个概率会随着迭代次数的增加而加大（之后会解释为什么这个算法是这样的）。

RANSAC 主要解决样本中的外点问题，最多可处理50%的外点情况。

2. 基本思想

RANSAC 通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：

1. 一个模型适用于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
2. 用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
3. 如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。
4. 然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。
5. 最后，通过估计局内点与模型的错误率来评估模型。

• N：样本个数
• K：求解模型需要的最少的点的个数（对于直线拟合来说就是两个点，对于计算Homography矩阵就是四个点）

1. 随机采样K个点
2. 对该K个点拟合模型
3. 计算其他点到拟合模型的距离。如果小于一定阈值，该点被当作内点，统计内点个数
4. 将上面步骤重复M次，选择内点数最多的模型
5. 利用所有的内点重新估计模型（可选）

3. 范例

4. 迭代次数推导