006｜RANSAC：先找到可信的小群体，再估计几何模型

系列首页 · 上一篇 · 下一篇

原论文：Martin A. Fischler、Robert C. Bolles，Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography，1981，Communications of the ACM 24(6):381–395。SRI原论文。本文依据方法、概率分析和定位实验段落，区分原文设置与自构例子。

先接住前作的问题

Kalman滤波提醒我们统计模型失配会带来过度自信；RANSAC处理的是另一类问题：几何匹配中有些点根本不属于同一个模型。这是鲁棒估计的教学联系，不是把Kalman增益直接改成随机采样。

五个前置概念

五个前置概念是：内点服从目标模型；外点可能来自另一机制；最小求解器由少量数据提出假设；几何残差衡量一致性；退化意味着信息本身不足。

一、问题设定：粗大错误对应怎样避免主导几何拟合

视觉匹配中，一部分对应点根本不是同一个物体位置。把它们与正确点一起做最小二乘，得到的不是稍有噪声的答案，而可能是被错误匹配拖偏的模型。RANSAC先用很少的数据假设模型，再问其余数据是否同意这个假设。

噪声和错误对应不是同一件事

正确匹配可能有一两个像素的定位误差，这类误差通常围绕真实值波动。错误匹配可能偏几十像素，且不服从同一个小噪声模型。最小二乘的平方惩罚会让远处错误点拥有很大影响。

一致集合并不天然等于语义上正确的数据。如果场景中两面墙都能形成平面，更多点支持的平面可能不是任务需要的桌面。RANSAC只能依据所设模型与评分标准做选择。

二、从最小样本到一致集合，推算成功抽样概率

算法机制与概率直觉

设一个最小模型需要s个样本，随机点为内点的比例为w。理想独立抽样近似下，一次全部抽中内点的概率为$w^s$。做N次仍没有全内点样本的概率约为$(1-w^s)^N$。

要求至少一次成功概率达到p，可选：

$$N\ge\frac{\log(1-p)}{\log(1-w^s)}.$$

这是常见教学预算公式，原文还分析所需尝试次数的期望和离散性。注意“抽到全内点最小集”只是必要的好运：点若几何退化、噪声过大或模型不对，仍可能得到坏估计。

原始算法的接受策略与现代库的评分、局部优化和自适应迭代数可能不同。伪代码保留核心思想，不把后来的所有变体作为原始RANSAC定义。

概率公式还藏着两个容易省掉的条件。第一，$w^s$ 把样本内的选择当成独立抽取；若数据只有 $M$ 个，其中 $I$ 个内点，每轮抽 $s$ 个互异点，则精确的全内点概率为

$$b=\frac{\binom Is}{\binom Ms} =\frac IM\frac{I-1}{M-1}\cdots\frac{I-s+1}{M-s+1}.$$

只有每轮重新独立抽取这个子集时，跨轮失败概率才写成 $(1-b)^N$。原创教学例：10点中5个内点，每次取2点，精确 $b=2/9$，不是 $1/4$；要求99%至少抽中一次，需要19轮，而独立近似会给17轮。数据量大且 $s$ 很小时，两者才更接近。

第二，这个99%是“抽到全内点集”的事件概率，不是“输出模型正确”的后验概率。若全内点集中只有比例 $\gamma$ 具备足够几何条件，并假设这项成功率可固定估计，单轮可用假设的概率还要改为 $b\gamma$。重复纹理形成自洽外点、阈值太宽或只按最大支持数提前停止，都不在那条简单保证中。原文第384页本来就分别讨论期望次数、标准差与指定置信度；把期望次数当硬上限会丢失这一区别。

抽样预算中的指数由最小样本数决定，循环的内点判断又由残差阈值决定。下面把二点与八点假设放在同一内点比例下比较，避免把求解器和采样收益混在一起。

三、执行假设验证循环，比较不同最小样本数

输入：数据D，最小样本数s，求解器Fit，阈值t，预算N
best_model为空，best_support为0
重复最多N次：
    从D抽s个样本，拒绝明显退化的几何组合
    由Fit生成一个或多个候选模型
    对每个候选，计算全部数据的几何残差
    取残差小于t的一致集合C
    若支持度达到要求且优于当前最好：
        在C上重新拟合，保存模型及内点
返回模型与内点；若支持不足则报告未可靠求解

教学例子：样本数为什么如此重要

假设w=0.5，拟合直线只需两个点，单次全内点概率为0.25。若拟合某个模型需要八个点，概率降为1/256。在同样内点比例下，最小求解器越“省点”，通常越容易产生可信假设。

但不能为了减少s而使用不足以确定模型的点数。模型没有被唯一约束时，会出现连续无穷多解或多个离散解，应显式生成并检验候选，而不是随便选一个数值答案。

再想象一组激光点中，大多数来自地面，少数来自一块目标板。若目标是地面估计，最大一致集合合理；若任务是找目标板，需要位置、朝向或语义先验。鲁棒拟合解决的是数据污染，不替代任务定义。

四、读直线反例与相机定位实验的支持范围

读图：按列区分三种统计量：最终一致集的对应点数、考察过的三元组数，以及求出的相机位置数。内点比例 w 变低时，搜索负担会变大；一致集大小是点数，不是生成一致集的次数。

图 1、§I。 少量点的直线拟合，包含一个粗大错误；逐次最小二乘剔除最大残差也会误删好点。

读图：上方散点与下方逐次剔除记录要一起读：最大残差剔除会先删掉正确点，最后保留错误点7。

§II概率分析。 改变内点概率与最小样本数；抽样成本对这两个量非常敏感。

§IV.C定位例子。 20组地标对应中有5组粗错；该例中RANSAC与剔除式拟合行为不同。

§IV.D、表 I。 50组合成定位问题，每组30个对应；对所设像素噪声、错误对应与相机位置进行检验。

§IV.E。 航空图像的真实定位案例；方法可接入实际特征定位流程。

作者报告在§IV.C的构造例中，RANSAC第二次所选三点便找到了正确解；这不是平均运行时间保证。§IV.D的表只展示其中十个典型问题，不能把这十行误当全部实验样本。论文的历史实现耗时也不能与现代硬件直接相减得到“加速倍数”。

实验支持抵抗特定粗错设置的能力，不证明所有错误都能识别。错误若形成更强的自洽模型，一致性检验可能选择它。现代复现还应记录随机种子、成功率分布及超时比例，而不是只报最快一次。

五、检查残差单位、退化样本与多模型歧义

阈值t必须与残差单位匹配。图像重投影误差以像素计，归一化相机坐标和三维距离则是其他尺度。阈值过小会丢掉好点，过大把粗错也收入一致集合。相机畸变和测量不确定性变化还会让统一阈值不够合理。

退化几何是另一来源。例如共线点不能稳定确定某些三维关系，即使这些点都是真实对应也没有足够信息。因此内点率高不等于可估计性强。应检查基线、空间分布及求解器条件。

RANSAC找到的是某个得到较强支持的假设，不保证最终残差在全部合理模型中全局最小。常见做法是在内点上进一步优化，但内点集合如果已经选错，局部优化可能更精确地拟合错误答案。

如果抽样不是均匀独立，而是按匹配分数优先选择，预算公式中的概率也要重新解释。更好的平均速度不代表沿用原公式仍有相同的成功概率保证。

六、追问：若测量分辨率改变，RANSAC阈值和成功概率能否原样沿用？

七、把鲁棒采样接到具体几何求解器

• 模块组合：Horn 配准：把旋转最小二乘变成四维特征值问题。用已知对应的闭式配准作为假设拟合模块，鲁棒性仍来自外层一致性检验。
• 模块组合：五点法：用相机标定，把两帧匹配变成运动假设。把更省样本的五点求解器用于相对位姿假设，重新评估抽样预算。

八、自测与参考答案

问题1：内点比例不变，为什么模型需要的最小点数增大后计算可能急剧增加？

参考答案：一次全内点概率为$w^s$，随s指数下降。更多样本能提高单次拟合约束，却显著降低假设完全避开外点的机会，所以需要区分最小假设阶段和内点重拟合阶段。

问题2：抽到的全是内点，为什么还可能失败？

参考答案：这些点可能几何退化、覆盖太窄或噪声导致求解器不稳定。全内点只解决数据来源问题，没有保证模型可观测性与数值条件。

问题3：一致集合最大，为什么不一定是机器人需要的对象？

参考答案：评分衡量几何支持，不识别任务意图。一个更大背景平面可以胜过目标物体平面，必须通过先验、区域限制或额外识别步骤指定目标。