RANSAC指Random sample consensus，随机采样一致性。算法流程如下：
- 随机选择数据点的一个子集
- 通过数据子集优化模型
- 在模型拟合结果附近的数据点将为该模型参数投票
- 重复以上操作，直到找到一个最优模型，有最多的数据点为他投票
迭代示意图如下。
拟合直线的流程如下图。其中s，d是超参数。拟合直线的流程如下图。其中s，d是超参数。在最后得到票数最高对应的直线时，一般会用该直线和周围的d个点再做一次最小二乘，使拟合更精确。
关于N的选择也是一个重要问题，需要兼顾准确率和效率。通过以下公式可以对给定准确率的情况下预估次数N。其中e是外点率，需要给定，s是每次循环的采样点个数，N是循环个数，p是准确率。
$$
(1-(1-e)^s)^N = 1-p
$$
当然N也可以使用自适应的方法确定。算法流程如下图。N初始化为无穷大，当拟合到一个更好的曲线时，重新估计N的大小(N会越来越小)，作为循环的终止条件。内点率外点率可以通过设定一个阈值t来计算。
下图是RANSAC的总结。
补充：指纹配对
RANSAC也可以做指纹的配对，通过拟合两个指纹之间的仿射变换，最后通过投票最大值来判断两个指纹是否来自同一个人。
评论