RANSAC

RANSAC(Random Sample Consensus,随机采样一致性)由Fischler与Bolles于1981年提出,是SLAM与多视图几何中占主导地位的鲁棒估计方法。它将一个参数化模型(本质矩阵、单应矩阵、相机位姿、平面等)拟合到被离群点——错误的特征匹配、遮挡、运动物体——污染的数据中,方法是反复从小规模随机样本中假设模型,并按一致性对其打分。

算法

均匀随机抽取一个包含 $s$ 个对应关系的最小样本 $S$ ( $s$ 是确定该模型所需的最少数量：本质矩阵需要5点,单应矩阵需要4点,P3P需要3点,使用线性8点算法的基础矩阵需要8点)。
将模型 $\theta_S$ 拟合到该样本。
统计内点：在误差阈值 $\epsilon$ 内与 $\theta_S$ 一致的数据点(例如Sampson距离或几个像素的重投影误差)。
重复 $N$ 次迭代;保留内点集最大的模型。
可选地对所有内点用最小二乘重新拟合模型(通常还会迭代这一重新拟合过程)。

关键洞见：即使离群点占50%,经过足够多次尝试后,一个全内点的小样本也会以合理的概率被抽到,而正确的模型所获得的一致性支持,会远远超过基于受污染样本拟合出的模型。

需要多少次迭代?

设 $w$ 为内点比例。一个包含 $s$ 个点的样本全为内点的概率是 $w^s$ ,因此 $N$ 个样本中至少有一个全内点的概率是

P(\text{success}) = 1 - (1 - w^s)^N

要求 $P(\text{success}) \geq 1 - \eta$ (例如,99%置信度取 $\eta = 0.01$ ),可得

N = \frac{\log \eta}{\log(1 - w^s)}

在 $w = 0.5$ 、 $\eta = 0.01$ 下的例子：

求解器	$s$	$N$
5点法本质矩阵	5	$\approx 145$
8点法基础矩阵	8	$\approx 1177$

迭代次数随样本量呈指数增长——这正是为什么在RANSAC内部,最小求解器(5点法E、P3P)比更大的线性求解器更受青睐的原因。

自适应RANSAC不会预先固定 $N$ ：它根据目前找到的最优内点集重新估计 $w$ ,重新计算 $N$ ,并一旦为当前估计值抽取了足够多的样本就提前终止——在简单场景中通常所需迭代次数要少得多。

实践要点

阈值 $\epsilon$ 应反映测量噪声(像素级);过紧会拒绝好的数据,过松会放入离群点。
退化样本(某些模型下的共线/共面点)必须被检测出来并重新抽取。
变体：PROSAC(优先对高质量排名的匹配采样)、LO-RANSAC(对有希望的模型进行局部优化)、MLESAC(用似然而非内点数量打分),以及像MaxCon一致性最大化这样的全局最优替代方法。
RANSAC之后,剩余的小误差由非线性精细化过程中的M估计量/鲁棒核函数处理。

对SLAM的意义

在基于特征的流水线中,每一个几何估计步骤都运行在RANSAC内部：用于初始化和2D-2D运动估计的本质/基础矩阵,用于平面场景的单应矩阵,用于跟踪和重定位的PnP,ICP对应关系剔除,以及回环检测验证。
单纯的描述子匹配经常会产生20-50%的错误匹配;若没有RANSAC,最小二乘估计将被任意破坏(最小二乘对离群点的容错能力为零)。
来自场景识别的回环候选在被加入位姿图之前会用RANSAC进行几何验证——单个错误的回环约束就可能毁掉整个地图。

动手实践

RANSAC动手实践

RANSAC

算法

需要多少次迭代?

实践要点

对SLAM的意义

动手实践

相关条目