随机样本共识帮助你过滤那些讨厌的离群值

我们都应该感谢古希腊人给了我们民主。尽管它有所有的缺陷，但在有人提出更好的想法之前，它仍然是可用的最好的系统，可以最大化共同的利益-或者最小化共同的不满，这取决于你选择的看待它的方式。

这一政治体系的核心在于这样一种观点，即越多的人在天平中权衡自己的权重，大多数人出错的可能性就越低。这是一种启发式方法，只在大部分时间内有效。我相信你能想出几个大多数选民走上歧途的例子。然而，大多数情况下，询问人们他们想要什么-例如通过全民公投-会产生不错的结果。

自动拟合模型(直线、圆、平面、抛物线…)噪声数据是计算机视觉中普遍存在的问题。假设您有一个描述数据分布的参数化模型，并且您想要使用一些数据来优化模型参数值，那么RANSAC将提供一种自动的方法来过滤剔除数据中的异常值。RANSAC算法的最大洞察力在于将这个问题看作是一个全民公决，多个模型参数集竞争最大数量的观测值的一致性。个人观察就是选民。它们根据候选模型参数与候选参数的匹配程度，为候选参数集分配投票分数。主要思想是这样的事实，即内部值会与相同的参数集一致，而异常值将在它们与损坏的参数集的一致性中被隔离。内部支持者的一致性将允许一组参数来建立大量选票，并成为赢家。

在本文中，我们将研究RANSAC算法，并通过代码了解它的运行情况。see it in action through code

让我们考虑一个简单的例子。您收集了二维数据，并在平面上绘制了点云。这是您获得的信息：Let’s consider a simple example

在瞬间内，您的内部模式匹配机器就发现了沿对角线的点的集中度。您的数据中有一个有趣的趋势！这不是你所希望的吗？让我们使用我们所有的观测数据，用线性回归来描述我们模型的(ρ，θ)参数。

那不是很顺利。正如您可能知道的，最小二乘法(如这里使用的方法)对异常值很敏感，并且在此云中有很多异常值(只要我们只对高密度的对角线线性区域感兴趣)。当然，您可以手动遍历观测，确定它们是否属于感兴趣区域的一部分，并仅对内点运行线性回归。这将是乏味的，但在这种情况下是可行的。但是，在某些情况下，模型拟合是设计为自动执行的算法中的一个步骤。过滤离群值必须是自动化的，这就是RANSAC的意义所在。

RANSAC由Fischler和Bolles于1981年首次提出。他们的激励应用与我们刚才描述的问题类似。该算法的基本思想是从多个随机选择的观测元组(在我们的例子中是成对的观测)生成候选模型(在我们的例子中是候选线)。元组包含唯一确定模型参数所需的最小观测值。然后，对于每个候选参数集，每个观测必须通过将一些距离测量与阈值进行比较来检查它们是否与候选模型一致。如果给定的观测值与候选模型一致，则它会向候选参数集贡献投票分数。如果距离低于阈值，则投票分数可以是1，否则可以是零(二元投票)，或者随着距离从零到阈值，投票分数可以是连续的单调递减值。一个观测值可以为多个候选参数集贡献肯定的投票分数。在候选人创建试验结束时，累计投票得分最高的候选人模型为获胜者。作为额外的好处，RANSAC还可以输出内值和异常值之间的观测值的划分。有了这些信息，就可以使用所有的内嵌器来计算最终的模型。was first introduced by Fischler and Bolles, in 1981

让我们将RANSAC算法应用于我们的点云，拟合线模型。除了假设我们可以在此点云中拟合直线模型之外，我们还需要两个参数：试验次数(即将生成的候选参数集的数目)和可接受的误差(即候选线和给定观测之间的阈值距离)。

如果我们绘制共识模型以及内异值和异常值之间的划分，我们会得到更好的结果：

由于RANSAC是基于随机抽样的观测值，我们不能保证我们会找到满足最大观测值的参数集。如果我们假设只要我们抽样至少一次n个ₘᵢₙᵢₘᵤₘ内嵌对象，就会找到足够好的候选模型，并且选择内嵌内嵌对象的概率为pᵢₙₗᵢₑᵣ？，则成功的概率将为：

…其中nₘᵢₙᵢₘᵤₘ是由我们拟合的模型类别确定的常数。它是定义模型参数所需的最小观测次数。

对于我们的示例，当pᵢₙₗᵢₑᵣ=0.5，nₘᵢₙᵢₘᵤₘ=2(我们需要两个点来定义一条线)和nₜᵣᵢₐₗₛ=100时，我们得到

我们是为了安全起见。我们还可以使用上面的等式来分离作为期望成功概率和估计的嵌入者比例的函数的nₜᵣᵢₐₗₛ。

不用谢!例如，您可能有一个应建模为圆的点云。甚至可能有多个圆隐藏在点云中，RANSAC将返回满足最多观测数量的圆模型。point cloud that should be modeled as a circle

如果您还对识别较小圆的参数感兴趣，则可以删除第一个找到的模型满足的观测结果(换句话说，只保留离群值)，然后再次运行RANSAC算法。

RANSAC算法已有40年的历史。与古希腊人的民主相比，这并不算多，但它已经被证明是非常有用的，特别是在计算机视觉方面。例如，边缘检测器可以生成假设为线性段的对象的边缘像素的掩码。由于遮罩不可能没有误报，RANSAC将通过只保留对齐的像素来帮助我们拟合对象边缘。

您可以随意尝试这些代码。我很高兴听到您心目中RANSAC可以在计算机视觉领域内外使用的应用程序。experiment with the code

？忽略了这样一个事实，即我们在选择观察后不会替换它