Part III · 第 11 章 多视图几何 · 11.5

特征匹配与 RANSAC

本章的几何公式都默认你已经知道图 1 的哪个像素对应图 2 的哪个像素。现实里没人告诉你：机器人要自己找出值得追踪的点，给它们写上"身份证"（描述子），在另一张图里把它们认出来，而且认出来的结果里总有一成到五成是错的。本节把这条流水线整个跑一遍：为什么角点是好特征，描述子和比值检验怎么挑出可信的匹配，以及 RANSAC 怎样在大量错误匹配里仍然算出正确的单应或基础矩阵。

约 35 分钟 前置：1.13 最小二乘 · 3.5 Hessian · 4.1 随机变量 · 10.5 单应 · 11.1 对极几何 5 个交互

    1为什么机器人需要它

    10.5 节的单应、11.1 节的基础矩阵、11.4 节的 PnP 都从一份"对应点"出发：\(\mathbf x_1\leftrightarrow\mathbf x_2\)。机器人拿到的却只是两个由几十万个灰度值组成的矩阵。要走到对应点，必须依次做三件事：

    • 检测：在图 1 里挑出少数"在别的图里也能找回来"的点，也就是特征点（本节第一个实验：为什么是角点）。
    • 描述与匹配：给每个特征点算一个向量（描述子），在图 2 中找最像的那个（第二个实验）。
    • 鲁棒估计：匹配永远有错，光照、重复纹理、运动物体都会骗人。用 RANSAC 只让"相互一致"的那部分匹配去决定几何（第三到第五个实验）。

    这三步就是视觉里程计、运动恢复结构（SfM）和视觉 SLAM 的前端：每秒几十帧、每帧几百到几千个特征，后面的光束法平差（11.6）和位姿估计（11.4）都建立在它输出的干净匹配上。前端出错一次，后端再漂亮也救不回来。

    2直觉：什么样的点值得追踪

    想象你站在一个小窗口前，只能看到图像的一小块，别人把窗口平移了一点点，让你说出平移了多少。如果窗口里是平坦区域，你什么也看不出来，往哪个方向移动画面都一样。如果窗口里是一条边，沿着边移动你察觉不到，垂直于边移动立刻就能发现，所以你只能确定一个方向，这叫孔径问题。只有窗口里是角点时，向任何方向移动画面都会变，你才能唯一确定位置。

    把这个直觉量化：令 \(E(\boldsymbol\Delta)\) 是窗口平移 \(\boldsymbol\Delta\) 之后与原窗口的灰度差平方和（右图），对小的 \(\boldsymbol\Delta\) 它是一个二次型 \(E\approx\boldsymbol\Delta^\top M\boldsymbol\Delta\)，其中 \(M\) 是窗口内梯度外积之和，叫结构张量。它的两个特征值 \(\lambda_1\ge\lambda_2\)（1.11 节）告诉你两个正交方向上"画面变得有多快"。下面的实验把这些量都画了出来。拖动琥珀色的小方框，在平坦处、边上和角上各停一次。

    FIG 1窗口、梯度云与平移误差面
    绿圈 = 检测到的角点
    窗口内的梯度
    平移误差 E(Δ)
    左：合成图像（矩形、圆、三角形、棋盘格）。拖动琥珀色手柄移动 15×15 的窗口；上方切换可显示全图的 Harris 响应 \(R\)（琥珀色为正即角点，紫色为负即边）或 Shi–Tomasi 的 \(\lambda_{\min}\)，再按阈值与非极大值抑制画出角点。中：窗口内每个像素的梯度画成一个点，椭圆是这团点的形状，半轴 \(\propto\sqrt{\lambda_i}\)，也就是 \(M\) 的形状。右：把窗口平移 \(\boldsymbol\Delta\in[-5,5]^2\) 真实算出的灰度差平方和 \(E(\boldsymbol\Delta)\)（越亮越大），紫色虚线是二次型 \(\boldsymbol\Delta^\top M\boldsymbol\Delta\) 的一条等值线。注意边上的 \(E\) 沿边方向是一条平坦的山谷。
    试一试
    • 把窗口依次放到平坦处（矩形内部）、边上和角上，读数里的分类会跟着变。梯度云各是什么形状？
    • 把窗口放在矩形的一条直边上，再沿着边滑动至少 15 像素。右图的山谷有变化吗？这就是孔径问题：沿边方向无法定位。
    核心洞见

    好特征 = 窗口向任何方向移动，画面都明显变化 = 结构张量 \(M\) 的两个特征值都大。一个大一个小是边（只能定位一个方向），两个都小是平坦区域（无法定位）。Harris 用 \(\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2\) 打分，Shi–Tomasi 直接用 \(\min(\lambda_1,\lambda_2)\)。

    3动手玩：描述、匹配、数一数错了多少

    找到角点之后，要让图 2 里的同一个点"认出自己"。做法是给每个角点周围的小块图像算一个描述子：一个对光照、小旋转、噪声不敏感，却对不同位置的点差异明显的向量。下面的实验里，两张图是同一个合成世界的两个视角：图 2 是图 1 经过一个已知的单应（旋转、缩放、位移、一点透视）变形，再加上亮度对比度变化和噪声得到的，所以每一个匹配对错都能用真值判定。两种描述子都是在页面里从头实现的：

    • SIFT-lite（浮点，L2 距离）：先在角点周围统计梯度方向直方图，取主方向，把 16×16 的块转到主方向上，分成 4×4 个格子，每个格子统计 8 个方向的梯度幅值，得到 128 维向量，再做归一化、截断到 0.2、再归一化。这就是 Lowe 的 SIFT 去掉尺度空间的版本。
    • ORB-lite（二进制，汉明距离）：用灰度质心确定主方向，把 256 对随机采样点按主方向转一下，比较每一对的灰度大小，得到 256 个比特（真正的 ORB 用的是离线学出来的采样对，这里用随机对代替）。汉明距离就是两个比特串异或后 1 的个数，每个机器字一条 popcount 指令就能数完，所以 ORB 极快。

    匹配方法有四种：最近邻（每个点都配一个，不管好坏）；比值检验（最近邻距离 \(d_1\) 与次近邻距离 \(d_2\) 之比小于 \(\rho\) 才接受）；交叉检验（A 的最近邻是 B，B 的最近邻也必须是 A）；两者合用。试着把图 2 转得更厉害，再关掉主方向。

    FIG 2描述子、匹配与真值
    图 1 · 图 2
    最近邻匹配的比值 d₁/d₂ 分布
    精确率 / 召回率 vs 比值阈值 ρ
    绿线：与真值相符（映射后落在 3 像素内）的匹配；红线：错误匹配；紫色虚线：图 1 的边框经真实单应映射到图 2 的位置。直方图把所有最近邻匹配按 \(d_1/d_2\) 分箱，绿色是正确的、红色是错误的：正确匹配的比值集中在小值，错误匹配集中在 1 附近，所以比值检验有效。精确率 = 接受的匹配中正确的比例；召回率 = 正确匹配数 / 两张图都检测到的可重复角点数。重复纹理场景里"最近邻"和"次近邻"几乎一样近，比值检验会把大部分匹配（连同正确的）一起扔掉。
    试一试
    • 用"比值检验"把精确率提高到 90% 以上，同时仍保留至少 25 个匹配。比值阈值多大合适？与"最近邻"相比，召回率损失了多少？
    • 把图 2 旋转 35° 以上，先关掉主方向（精确率崩溃到 20% 以下），再打开（精确率恢复到 60% 以上）。
    • 切换到"重复纹理"场景，找到一种设置使精确率仍不低于 80%（至少 5 个匹配）。你付出了什么代价？

    4第二、第三视角：RANSAC

    先在一条直线上看清 RANSAC

    即使比值检验之后，匹配里仍有错的，而且错得离谱。最小二乘（1.13 节）对此毫无抵抗力：它最小化所有点残差的平方，一个远处的外点贡献的平方误差大得足以把整条线拽走。RANSAC（Fischler 和 Bolles，1981）的想法完全不同：别用所有点去拟合，随机取最少够用的几个点（直线 2 个）拟合一个假设，数一数有多少点支持它（残差小于阈值 \(\tau\) 的点，称为一致集或内点），重复很多次，保留支持者最多的假设，最后只用它的内点重新拟合。外点之间互不相容，所以它们几乎不可能凑出一个大的一致集。

    FIG 3直线上的 RANSAC
    数据与拟合
    每次迭代的内点数
    虚线青色：真值 \(y=0.6x+0.8\)。红线：对全部点的最小二乘。紫色：当前迭代的假设（圈出的两个样本点、阴影是 \(\pm\tau\) 的带）。绿色：目前最好的假设及其内点（绿点）与外点（红点）。右图：每次迭代数出的内点数，绿柱表示刷新了纪录。点"最终重拟合"后，粗绿线是只用内点做的最小二乘。数据由固定随机种子生成，改任何参数都会重新开始。
    试一试
    • 把外点比例拉到足以让红色最小二乘直线的斜率偏离真值 0.2 以上。要多少外点？
    • 保持外点比例 ≥ 40%，按"连续运行"，直到最好假设的斜率与真值相差不到 0.15。用了多少次迭代？
    • 阈值 \(\tau\) 取得太小（小于噪声 \(\sigma\) 的 0.7 倍）跑 8 次以上，再取得太大（≥ 2.5）跑 8 次以上，看内点数怎么变。

    要迭代多少次？

    RANSAC 只有在至少有一次抽到的样本全是内点时才可能成功。设内点比例为 \(w\)，每次抽 \(s\) 个点，一次全是内点的概率约为 \(w^s\)，所以抽 \(N\) 次一次都不成功的概率是 \((1-w^s)^N\)。要求成功的概率至少是 \(p\)，就得到 \(N=\ln(1-p)/\ln(1-w^s)\)。关键是指数 \(s\)：最小样本越大，\(N\) 增长得越快。这就是为什么人们费尽心思发明 5 点法、P3P 这样的"最小求解器"。下面用蒙特卡洛模拟检验这个公式：反复运行 RANSAC 的抽样，数一数多少比例在 \(N\) 次之内成功。

    FIG 4迭代次数：公式与蒙特卡洛
    所需迭代次数 N（对数）vs 内点比例 w
    成功概率 vs 迭代次数：公式与 2000 次模拟
    左：五条曲线对应最小样本 \(s=2,3,4,5,8\)（直线、P3P、单应、5 点法、8 点法）；圆点是当前 \((w,N)\)，竖直方向只画到 \(10^5\)。右：紫色曲线是 \(1-(1-w^s)^k\)；琥珀色阶梯是 2000 次模拟中"到第 \(k\) 次迭代时已经抽到过全内点样本"的比例；横虚线是目标 \(p\)，竖虚线是公式给出的 \(N\)。模拟在一个 5000 点的总体里无放回地抽样，不使用公式。\(N>6000\) 时不模拟。
    试一试
    • 选 \(s=8\)（基础矩阵的 8 点法），把 \(w\) 调到 0.5：\(N\) 是多少？再换成 \(s=5\)，少了多少倍？
    同一个想法的三种说法

    投票：每个最小样本给出一个模型，所有点来投票，票数最多者当选。假设—检验：先用最少的数据提出假设，再用其余数据检验，这样提出假设的过程不会被外点污染。鲁棒损失：最大化一致集等价于最小化截断损失 \(\sum_i\min(r_i^2,\tau^2)\)（把超过 \(\tau\) 的残差一律记为 \(\tau^2\)），一个残差再大也只贡献有限的代价。后一种说法正是光束法平差（11.6）里 Huber、Cauchy 等鲁棒核函数的出发点：RANSAC 负责给出好的初值并去掉明显的外点，鲁棒核负责处理剩下的轻微外点。

    5再看数学

    提示：把鼠标悬停在公式中带底色的符号上，FIG 1 或 FIG 4 中对应的元素会被高亮。

    结构张量：从平移误差到特征值

    窗口 \(W\)（高斯加权 \(g(\mathbf q)\)）平移 \(\boldsymbol\Delta\) 后的灰度差平方和，对 \(I\) 做一阶泰勒展开（3.1、3.2 节的梯度）：

    $$ \begin{aligned} E(\boldsymbol\Delta)&=\sum_{\mathbf q\in W} g(\mathbf q)\big[I(\mathbf q+\boldsymbol\Delta)-I(\mathbf q)\big]^2\approx\sum_{\mathbf q} g\,\big(\nabla I(\mathbf q)^\top\boldsymbol\Delta\big)^2=\boldsymbol\Delta^\top\,\hl{tensor}{M}\,\boldsymbol\Delta,\\ M&=\sum_{\mathbf q} g(\mathbf q)\begin{bmatrix}I_x^2&I_xI_y\\I_xI_y&I_y^2\end{bmatrix}. \end{aligned} $$

    \(M\) 是半正定对称矩阵，等于把梯度当作一团点时的"二阶矩"，所以 FIG 1 中间的椭圆就是 \(M\) 的形状。沿特征向量 \(\mathbf e_i\) 平移一个单位，误差恰为 \(\lambda_i\)（1.11 节）。\(E\) 在 \(\boldsymbol\Delta=\mathbf 0\) 处的 Hessian（3.5 节）是 \(2M\)：这就是高斯–牛顿法（6.6 节）用 \(J^\top J\) 近似 Hessian 的同一个结构，也是后面光流 KLT 跟踪要解的线性方程。三种情形：

    $$ \underbrace{\hl{lam}{\lambda_1\approx\lambda_2\approx0}}_{\text{flat}},\qquad \underbrace{\lambda_1\gg\lambda_2\approx0}_{\text{edge (aperture problem)}},\qquad \underbrace{\lambda_1\ge\lambda_2\gg0}_{\text{corner}}. $$

    Harris 与 Stephens（1988）避开开方求特征值，用 \(R=\det M-k\,(\operatorname{tr}M)^2=\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2\)，\(k\) 通常取 0.04 到 0.06。\(R>0\) 当且仅当 \(\lambda_2/\lambda_1\) 大于某个仅由 \(k\) 决定的数（\(k=0.04\) 时约 0.044），\(R\) 为很负的数是边。Shi 和 Tomasi（1994）指出对跟踪而言最自然的指标就是 \(\min(\lambda_1,\lambda_2)\)，FIG 1 与 FIG 2 的检测器用的是后者。实际流程是"阈值（占最大响应的比例）+ 非极大值抑制"，否则一个角点周围会冒出一大片相邻像素。

    尺度。\(M\) 的特征值在图像旋转下基本不变（窗口是各向同性的高斯时严格不变），但在缩放下会变：放大后同一个角点的"尖角"变成了一段平滑的弯，窗口里只剩一条边。所以真正的检测器（SIFT 的高斯差分 DoG、Harris–Laplace、ORB 的图像金字塔）会在多个尺度上找极值，并把找到的尺度记下来，用来决定描述子的窗口大小。本节为了简洁只用单一尺度，所以 FIG 2 把图 2 放大 25% 以上时，匹配会明显变差。

    描述子的不变性

    • 原始灰度块：什么都不变，光照变一点就失效。去均值、除以标准差的块（NCC）：对亮度的增益和偏置 \(I\mapsto aI+b\) 不变。
    • SIFT：用梯度，所以对偏置不变；向量归一化消去增益；截断到 0.2 削弱了饱和这类非线性光照变化的影响；主方向带来旋转不变；尺度空间极值带来尺度不变；格子内的软分配与高斯加权使它容忍 1 到 2 个像素的定位误差。
    • BRIEF / ORB：每一位只比较两个点的大小，所以对任何单调的灰度变换不变；ORB 用灰度质心定主方向（旋转不变），再用图像金字塔（尺度）。它没有 SIFT 的连续值，辨别力稍弱，但 256 位的汉明距离比 128 维浮点的 L2 快一到两个数量级。
    • 学习得到的描述子（SuperPoint 等）：不变性不靠设计而靠数据增强来学，在大视角、昼夜变化下往往优于手工特征，代价是需要 GPU 推理。

    没有哪种手工描述子能应付大视角变化（超过大约 30° 到 50° 就明显退化）：这时需要多视角综合、仿射不变的变体，或者学习得到的匹配器。

    比值检验为什么有效

    对图 1 的一个描述子 \(\mathbf f\)，设图 2 中距离最近的描述子为 \(\mathbf f_1\)，次近的为 \(\mathbf f_2\)。如果 \(\mathbf f_1\) 是真正的对应点，它应该比图 2 中任何"随机"的点都近得多，而 \(\mathbf f_2\) 是随机点中最近的，因此 \(d_1/d_2\) 很小。如果 \(\mathbf f\) 在图 2 中根本没有对应点（被遮挡、超出视野、检测器没检出），那么 \(\mathbf f_1\)、\(\mathbf f_2\) 都是随机点，\(d_1\approx d_2\)，比值接近 1。FIG 2 的直方图把这两个分布画了出来。Lowe（2004）在他的数据上统计到：阈值 \(\rho=0.8\) 可以去掉约 90% 的错误匹配，同时只丢掉不到 5% 的正确匹配；这个数字依赖场景和描述子，不是定理，所以要在自己的数据上看直方图。重复纹理是它最大的敌人：真正的对应点和它的"孪生兄弟"同样近，比值接近 1，被一起扔掉。

    RANSAC：算法、迭代次数、阈值

    算法。重复：（1）从 \(n\) 个匹配里随机抽 \(s\) 个（最小样本，并检查退化：单应的 4 个点不能有 3 点共线，抽到的点不能挤成一团）；（2）用最小求解器算出模型 \(\theta\)（直线 2 点，单应 4 点，基础矩阵 7 或 8 点，本质矩阵 5 点，PnP 的 P3P 3 点）；（3）数一致集 \(\mathcal C(\theta)=\{i: r_i(\theta)<\tau\}\)；（4）若比当前最好的大就保留；（5）按下面的公式用当前 \(\hat w=|\mathcal C|/n\) 更新所需的 \(N\)，抽够了就停。最后用一致集重新拟合（再重新数一次一致集，可以重复几轮）。

    迭代次数。一次抽样全是内点的概率是 \(\hl{w}{w}^{\,\hl{s}{s}}\)（总体很大时），\(N\) 次全失败的概率是 \((1-w^s)^N\)，令它等于 \(1-p\)：

    $$ (1-w^s)^N=1-p\quad\Longrightarrow\quad \hl{N}{N=\frac{\ln(1-p)}{\ln(1-w^{s})}}\;\approx\;\frac{-\ln(1-p)}{w^{s}}\ \ (w^s\ll1),\qquad\big(p=0.99:\ N\approx 4.6/w^s\big). $$

    这是 4.1、4.2 节的几何分布：第一次成功的等待时间。取整向上。例：\(w=0.5\)，\(p=0.99\)：\(s=2\) 要 17 次，\(s=4\) 要 72 次，\(s=5\) 要 146 次，\(s=8\) 要 1177 次，约八倍之差就在 5 点法与 8 点法之间。这个公式只算"抽到过全内点样本"的概率，而内点带噪声时，全内点样本拟合出的模型也可能不够好，所以实际常取 2 到 10 倍的余量，或用局部优化（LO-RANSAC）补救。\(w\) 事先不知道，所以用自适应停止：每次刷新最佳一致集就用新的 \(\hat w\) 重新算 \(N\)。

    阈值。设内点残差服从零均值高斯，每个坐标的标准差是 \(\sigma\)。一维残差满足 \(|r|<1.96\sigma\) 的概率是 95%（\(\chi^2_1\) 的 95% 分位数 3.84 开方）。二维残差（例如点到点的重投影误差）\(\|\mathbf r\|^2/\sigma^2\sim\chi^2_2\)，95% 分位数是 5.99，所以阈值是 \(2.45\sigma\)。Hartley 和 Zisserman 把这个思路写成表：模型的余维数为 1（基础矩阵的 Sampson 距离）时 \(t^2=3.84\sigma^2\)，余维数为 2（单应）时 \(t^2=5.99\sigma^2\)。\(\sigma\) 是特征点的定位误差，通常 0.5 到 1 个像素，FIG 5 里的"对称转移误差"是两个距离之和，所以阈值取得更大一些。

    为什么最小二乘经不起一个外点

    用最小二乘拟合直线 \(y=ax+b\)，若第 \(k\) 个点的 \(y\) 被改动 \(\delta\)，斜率会改变 \(\delta\,(x_k-\bar x)/\sum_i(x_i-\bar x)^2\)，随 \(\delta\) 线性无界地增长。所以最小二乘的崩溃点是 0：只要一个足够大的外点就能让估计任意糟。取中位数残差的 LMedS 崩溃点是 50%。RANSAC 没有固定的崩溃点，它的极限是计算量：\(w^s\) 太小时 \(N\) 爆炸（FIG 4），并且真模型的一致集必须比随机碰巧凑出的更大。变种：MSAC（用截断二次代价 \(\min(r^2,\tau^2)\) 代替计数，定位更准）、LO-RANSAC（发现好模型就地用内点优化）、PROSAC（按匹配质量排序，优先抽最好的匹配）、MAGSAC/MAGSAC++（对 \(\sigma\) 积分，不再需要手选阈值）；USAC（Raguram 等，2013）把它们整合成一个框架，OpenCV 的 USAC_MAGSAC 即源于此。

    鲁棒损失用来处理 RANSAC 之后还剩下的轻微外点。Huber 损失 \(\rho(r)=r^2/2\)（\(|r|\le\delta\)），\(\rho(r)=\delta(|r|-\delta/2)\)（\(|r|>\delta\)），大残差只增长线性；Cauchy 损失 \(\rho(r)=\tfrac{c^2}{2}\ln(1+r^2/c^2)\) 增长更慢。用迭代重加权最小二乘（6.9 节）求解时，每个残差得到权重 \(\rho'(r)/r\)。Cauchy 是非凸的，需要好的初值，这正是 RANSAC 提供的。

    6机器人中的它：从匹配到几何

    下面把整条流水线接起来。"单应"模式直接取用 FIG 2 的图像和匹配（在 FIG 2 里改视角、噪声、描述子，这里会跟着变）：放宽比值阈值得到更多匹配，再人为混入随机错配，RANSAC 用 4 点最小求解器 R101.Vision.dltHomography 反复抽样，用对称转移误差判内点，最后用全部内点重新拟合。因为变换是已知的，我们能直接量出估计的单应离真值有多远（图像网格点上的均方根误差，单位像素）。"基础矩阵"模式需要真正有深度的场景（平面场景的基础矩阵是退化的，见下面的误区 4），所以用两台虚拟相机观察 140 个随机三维点，投影加噪声后同样混入错配，用 8 点法 R101.Vision.fundamental8 抽样，用 Sampson 距离判内点。每次都和"对所有匹配直接做最小二乘"比较。

    FIG 5RANSAC 估计单应与基础矩阵
    最终模型下全部匹配的残差
    单应模式：绿线是 RANSAC 判定的内点，红线是外点，虚线其实是错配（真值），理想情况下只有虚线是红色。基础矩阵模式：两帧里的点按判定着色（绿 = 内点，红 = 外点），彩色圆圈是 6 个选定的点（4 个内点、2 个外点），右帧里同色的直线是它们在最终 \(F\) 下的极线 \(F\mathbf x_1\)：内点的对应点落在极线上，外点的偏离极线（虚拟噪声 \(\sigma=0.5\) px，所以 \(\tau=1\) px 约为 \(1.96\sigma\)）。直方图把最终模型下的残差分成"真正对的匹配"（绿）和"真正错的匹配"（红），竖线是阈值 \(\tau\)：好阈值把两堆分开。读数里"最小二乘（全部匹配）"是不做鲁棒处理直接拟合的误差。迭代预算很小时 RANSAC 会失败，把它调回去试试。
    试一试
    • 单应模式下，混入至少 25% 的随机错配：RANSAC 重拟合的误差应小于 1.5 像素，而"最小二乘（全部匹配）"的误差远大于 10 像素。
    • 把迭代预算降到 20 以下直到 RANSAC 失败（误差大于 5 像素，或者根本找不到模型），再升回 300 以上让它恢复。自适应规则说需要多少次？
    • 切换到"基础矩阵"，混入 40% 以上错配，让 RANSAC 的重拟合误差小于 2 像素。再把错配推到 80% 以上：8 个点的样本为什么一下子就失败了？
    真实系统里

    ORB-SLAM 系列（ORB-SLAM2/3）的前端：每帧提取 1000 到 2000 个 ORB 特征（FAST 角点 + 金字塔 + 汉明距离的 256 位二进制描述子），用词袋（DBoW2）做回环与重定位；单目初始化时同时拟合单应和基础矩阵并比较得分，选更合适的一个。VINS-Mono 一类的视觉惯性系统用 Shi–Tomasi 角点加 KLT 光流跟踪而不是描述子匹配（相邻帧运动小，光流更快更稳），再用基础矩阵 RANSAC 去掉外点。COLMAP 做 SfM：SIFT 特征、比值检验加交叉检验、然后对每一对图像做几何验证（用 RANSAC 估计 F、E 和 H，内点不够的图像对被丢弃）。OpenCV：BFMatcher（带 crossCheck）与 knnMatch 加比值检验、findHomography、findFundamentalMat、findEssentialMat（5 点法加 RANSAC）、solvePnPRansac。学习型方法：SuperPoint 检测加描述，SuperGlue、LightGlue 用注意力网络做匹配，LoFTR 不先检测而直接稠密匹配；它们在难场景下召回更高，但后面仍然接几何验证。地点识别用词袋或 NetVLAD 这样的全局描述子先找候选，再做特征匹配与 RANSAC 验证。机器人 VO 能每秒处理 30 到 60 帧，靠的是描述子便宜（汉明距离）、最小求解器的 \(s\) 小（5 点或 P3P）、以及自适应停止。

    7常见误区

    误区 1：阈值的单位错了、或者取得太紧

    阈值 \(\tau\) 的单位必须和残差一致：像素？归一化图像坐标（除以焦距，数量级 \(10^{-3}\)）？Sampson 距离的平方？把像素阈值直接用在归一化坐标的残差上（残差只有 \(10^{-3}\) 量级），所有点都成了内点；反过来把归一化尺度的阈值用在像素残差上，所有点都成了外点。取得太紧（小于 \(\sigma\)）则真内点被拒（FIG 3 的任务 3），太松则外点混进来，重拟合被拖偏。按 \(\sigma\) 和 \(\chi^2\) 分位数来定，而不是凭感觉。

    误区 2：最小求解器里不做坐标归一化

    8 点法和 DLT 单应的线性系统里，像素坐标的量级是 \(10^3\)，二次项是 \(10^6\)，常数项是 1，系统条件数极差，小噪声就能让解面目全非。必须先把点平移到质心为 0、平均距离 \(\sqrt2\)（Hartley 归一化），解完再变回去。R101.Vision.dltHomography 与 fundamental8 内部已经做了；自己写 RANSAC 时漏掉这一步，是"明明数据没问题，结果却随机"的常见原因。

    误区 3：退化样本，以及漏掉最后的重拟合

    单应的 4 个点里有 3 点共线，解不唯一；相距太近的两个点会让直线斜率毫无意义（FIG 3 里我们要求样本点至少相隔 0.2）。抽样时必须检查退化并重抽，否则一个"完美拟合"的假设可能毫无意义，还会数出一大堆内点。另一个常见失误是把最小样本拟合出来的模型直接当结果：那个模型把 \(s\) 个带噪点精确穿过，噪声没有被平均掉。用全部内点重新做最小二乘，精度大约提高 \(\sqrt{n_{\text{inl}}/s}\) 倍（FIG 5 的"RANSAC"与"重拟合"两个误差）。

    误区 4：特征分布不均、平面场景、动态物体

    如果全部匹配落在一个平面上（地面、墙），或者相机只做纯旋转，基础矩阵的 8 点法就是退化的：一族不同的 \(F\) 都能完美解释这些匹配，求出来的那个误差为零却毫无意义（这就是 FIG 5 的基础矩阵模式必须用有深度的场景的原因，也是 ORB-SLAM 同时算单应和 F 的原因）。特征全挤在图像一角，几何同样病态，所以检测器常常按网格限制每格的特征数。RANSAC 默认场景是静止的：如果匹配一半落在行驶的汽车上，另一半落在背景上，RANSAC 会选更大的一堆，另一堆被当作外点；若运动物体占了多数，机器人会得出"自己在动"的错误结论。需要的话要先做语义分割，或者对多个运动模型分别做 RANSAC。

    误区 5：迭代次数太少，或把不同模型的内点数直接比较

    固定迭代 100 次在 \(w=0.6\)、\(s=8\) 时成功概率只有 \(1-(1-0.6^8)^{100}\approx 82\%\)；\(w\) 掉到 0.4 时几乎必败。不要写死次数，要用自适应停止加一个上限。另外，单应约束的是点到点（残差是二维的），基础矩阵只约束点到线（残差是一维的，对极线两侧有一条很宽的带），所以同样的数据在 F 下几乎总能数出更多"内点"，随机错配也有机会碰巧落在极线附近：比较 H 和 F 谁更合适时不能直接比较内点数，ORB-SLAM 的做法是给每个模型算一个考虑残差大小和阈值的得分再比较。

    8小练习

    1. 内点比例 \(w=0.6\)，用 5 点法（\(s=5\)），要求成功概率 \(p=0.99\)。RANSAC 至少要迭代多少次？
    \(N=\ln(0.01)/\ln(1-0.6^5)=-4.605/\ln(0.92224)=-4.605/(-0.08095)=56.9\to57\)。选 6 是忘了指数 \(s\)（\(\ln0.01/\ln0.4\)）；33 是 \(s=4\) 时的 33.2 没有向上取整（应为 34）。
    2. 窗口恰好落在一条笔直的边上，它的结构张量 \(M\) 的特征值是？
    边上所有梯度都垂直于边，梯度云是一条线，\(M\) 的秩接近 1：垂直于边的方向特征值大（那个方向的平移立刻被察觉），沿边方向特征值约为 0（沿边平移图像不变）。FIG 1 中椭圆被压成线段。
    3. 一面砖墙上，每块砖的角看起来几乎一样。比值检验 \(d_1/d_2<0.8\) 会怎样处理这些角点的匹配？
    比值检验衡量的是匹配的独特性而不是距离本身。重复结构里正确的对应点与它的相似"孪生兄弟"一样近，\(d_1\approx d_2\)，被拒绝。这是正确的行为：宁可没有匹配，也不要给后端一个五五开的猜测（FIG 2 的重复纹理场景）。
    4. 内点比例 \(w=0.5\)。把基础矩阵从 8 点法换成 5 点的本质矩阵算法（其他条件不变），所需迭代次数大约变为原来的几分之一？
    \(N\approx4.6/w^s\)，所以比值约为 \(w^{5-8}=2^3=8\)：1177 次对 146 次（\(p=0.99\)）。最小样本每少一个点，所需迭代次数就少一半（\(w=0.5\) 时），这就是最小求解器值得花力气推导的原因。
    5. 单应的重投影误差是二维向量，每个坐标的噪声为 \(\sigma=1\) px 的高斯。要让 95% 的真内点通过，距离阈值应取多少？
    二维残差 \(\|\mathbf r\|^2/\sigma^2\sim\chi^2_2\)，95% 分位数是 \(-2\ln0.05=5.99\)，所以 \(\|\mathbf r\|<\sqrt{5.99}\,\sigma=2.45\) px。1.96 是一维残差的阈值；5.99 是平方距离的阈值，不是距离。

    9延伸阅读

    • M. A. Fischler & 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), 1981 — RANSAC 的原始论文
    • C. Harris & M. Stephens, A combined corner and edge detector, Alvey Vision Conference, 1988 — Harris 角点
    • J. Shi & C. Tomasi, Good features to track, CVPR 1994 — 用 \(\min(\lambda_1,\lambda_2)\) 选可跟踪的特征，KLT 的基础
    • D. G. Lowe, Distinctive image features from scale-invariant keypoints, IJCV 60(2), 2004 — SIFT 与比值检验
    • E. Rublee, V. Rabaud, K. Konolige & G. Bradski, ORB: an efficient alternative to SIFT or SURF, ICCV 2011 — 带方向的 FAST 与旋转 BRIEF，SLAM 的主力特征
    • R. Raguram, O. Chum, M. Pollefeys, J. Matas & J.-M. Frahm, USAC: a universal framework for random sample consensus, IEEE TPAMI 35(8), 2013 — RANSAC 的现代变种合集（PROSAC、LO-RANSAC、退化检测）
    • R. Hartley & A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., §4.7 (robust estimation) and §11.6 (automatic computation of F) — 阈值的 \(\chi^2\) 推导与自适应迭代次数
    • R. Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., Ch. 7 (feature detection and matching) — 特征检测、描述子与匹配的综述