RANSAC算法概述

一、RANSAC

  由Fischler和Bolles[1]提出的随机采样一致性 (RANSAC)算法是一种通用的参数估计方法，旨在处理输入数据中大量异常值的情况。与计算机视觉社区从统计文献中采用的许多常见的鲁棒估计技术(如M估计和最小中位数二乘)不同，RANSAC是从计算机视觉社区内部开发的。
  RANSAC是一种重新采样技术，它通过使用估计底层模型参数所需的最小观测值(数据点)来生成候选解决方案。正如Fischler和Bolles[1]所指出的那样，与使用尽可能多的数据来获得初始解然后进行异常值修剪的传统采样技术不同，RANSAC使用尽可能小的集合，并使用一致的数据点来扩大该集合[1]。

基本算法总结如下:

  选择足够高的迭代次数$N$，以确保至少一组随机样本中不包含异常值的概率$p$(通常设置为0.99)。设$u$表示所选数据点为内点的概率，$v=1-u$是观察到异常值的概率。需要对最小点数$m$进行$N$次迭代，其中
$$1-p=(1-u^m{)}^N\text{\hspace{1em}(1)}$$

因此，通过一些操作，
$$N=\frac{log(1-p)}{log(1-(1-v{)}^m)}\text{\hspace{1em}(2)}$$

有关基本RANSAC公式的更多详细信息，请参见[1,2]。RANSAC的扩展包括使用最大似然框架[4]和重要性抽样[3]。

二、References

[1] M.A. Fischler and R.C. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381–395, 1981.
[2] R. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. University Press, Cambridge, 2001.
[3] P. Torr and A. Zisserman. IMPSAC: A synthesis of importance sampling and random sample consensus to effect multi-scale image matching for small and wide baselines. In European Conference on Computer Vision, pages 819–833, 2000.
[4] P. Torr and A. Zisserman. MLESAC: A new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding,78(1):138–156, 2000.