特征匹配与 RANSACFeature Matching & RANSAC
本章的几何公式都默认你已经知道图 1 的哪个像素对应图 2 的哪个像素。现实里没人告诉你：机器人要自己找出值得追踪的点，给它们写上"身份证"（描述子），在另一张图里把它们认出来，而且认出来的结果里总有一成到五成是错的。本节把这条流水线整个跑一遍：为什么角点是好特征，描述子和比值检验怎么挑出可信的匹配，以及 RANSAC 怎样在大量错误匹配里仍然算出正确的单应或基础矩阵。 Every formula of this chapter assumed you already know which pixel in image 1 corresponds to which pixel in image 2. Nobody tells a robot that. It has to find points worth tracking, give them an "identity card" (a descriptor), recognise them in the other image, and live with the fact that 10 to 50 percent of what it recognises is wrong. This lesson runs the whole pipeline: why corners make good features, how descriptors and the ratio test pick trustworthy matches, and how RANSAC still recovers the right homography or fundamental matrix from a pile of bad matches.
1为什么机器人需要它Why robots need this
10.5 节的单应、11.1 节的基础矩阵、11.4 节的 PnP 都从一份"对应点"出发：\(\mathbf x_1\leftrightarrow\mathbf x_2\)。机器人拿到的却只是两个由几十万个灰度值组成的矩阵。要走到对应点，必须依次做三件事：
- 检测：在图 1 里挑出少数"在别的图里也能找回来"的点，也就是特征点（本节第一个实验：为什么是角点）。
- 描述与匹配：给每个特征点算一个向量（描述子），在图 2 中找最像的那个（第二个实验）。
- 鲁棒估计：匹配永远有错，光照、重复纹理、运动物体都会骗人。用 RANSAC 只让"相互一致"的那部分匹配去决定几何（第三到第五个实验）。
这三步就是视觉里程计、运动恢复结构（SfM）和视觉 SLAM 的前端：每秒几十帧、每帧几百到几千个特征，后面的光束法平差（11.6）和位姿估计（11.4）都建立在它输出的干净匹配上。前端出错一次，后端再漂亮也救不回来。
The homography of 10.5, the fundamental matrix of 11.1 and the PnP of 11.4 all start from a list of correspondences \(\mathbf x_1\leftrightarrow\mathbf x_2\). A robot only receives two matrices of a few hundred thousand gray values each. Getting to correspondences takes three steps in a row:
- Detect: pick a few points in image 1 that "can be found again in other images", the keypoints (first lab: why corners).
- Describe and match: compute a vector (descriptor) for each keypoint and find the most similar one in image 2 (second lab).
- Robust estimation: matches are always partly wrong; lighting, repeated texture and moving objects all cheat. RANSAC lets only the mutually consistent matches decide the geometry (labs three to five).
These three steps are the front end of visual odometry, structure from motion (SfM) and visual SLAM: tens of frames per second, hundreds to thousands of features per frame, and everything downstream (bundle adjustment in 11.6, pose estimation in 11.4) trusts the clean matches that come out of it. If the front end fails once, no back end can rescue the result.
2直觉：什么样的点值得追踪Intuition: which points are worth tracking
想象你站在一个小窗口前，只能看到图像的一小块，别人把窗口平移了一点点，让你说出平移了多少。如果窗口里是平坦区域，你什么也看不出来，往哪个方向移动画面都一样。如果窗口里是一条边，沿着边移动你察觉不到，垂直于边移动立刻就能发现，所以你只能确定一个方向，这叫孔径问题。只有窗口里是角点时，向任何方向移动画面都会变，你才能唯一确定位置。
把这个直觉量化：令 \(E(\boldsymbol\Delta)\) 是窗口平移 \(\boldsymbol\Delta\) 之后与原窗口的灰度差平方和（右图），对小的 \(\boldsymbol\Delta\) 它是一个二次型 \(E\approx\boldsymbol\Delta^\top M\boldsymbol\Delta\)，其中 \(M\) 是窗口内梯度外积之和，叫结构张量。它的两个特征值 \(\lambda_1\ge\lambda_2\)（1.11 节）告诉你两个正交方向上"画面变得有多快"。下面的实验把这些量都画了出来。拖动琥珀色的小方框，在平坦处、边上和角上各停一次。
Imagine looking through a small window onto the image. Someone shifts the window a little and asks you how far. If the window shows a flat region you can tell nothing: every shift looks the same. If it shows an edge, sliding along the edge goes unnoticed while sliding across it is obvious, so you can pin down only one direction: the aperture problem. Only when the window holds a corner does every shift change the picture, so the position is unique.
To make this quantitative, let \(E(\boldsymbol\Delta)\) be the sum of squared gray-value differences between the window and the window shifted by \(\boldsymbol\Delta\) (right panel). For small \(\boldsymbol\Delta\) it is a quadratic form \(E\approx\boldsymbol\Delta^\top M\boldsymbol\Delta\), where \(M\) is the sum of gradient outer products over the window, the structure tensor. Its two eigenvalues \(\lambda_1\ge\lambda_2\) (Lesson 1.11) say how fast the picture changes along two orthogonal directions. The lab below draws all of these. Drag the amber box and park it once on a flat area, once on an edge and once on a corner.
- 把窗口依次放到平坦处（矩形内部）、边上和角上，读数里的分类会跟着变。梯度云各是什么形状？Park the window on a flat area (inside the rectangle), on an edge and on a corner; the classification in the readout follows. What shape does the gradient cloud take in each case?
- 把窗口放在矩形的一条直边上，再沿着边滑动至少 15 像素。右图的山谷有变化吗？这就是孔径问题：沿边方向无法定位。Put the window on a straight side of the rectangle and slide it at least 15 pixels along that side. Does the valley in the right panel change? That is the aperture problem: you cannot localise along the edge.
好特征 = 窗口向任何方向移动，画面都明显变化 = 结构张量 \(M\) 的两个特征值都大。一个大一个小是边（只能定位一个方向），两个都小是平坦区域（无法定位）。Harris 用 \(\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2\) 打分，Shi–Tomasi 直接用 \(\min(\lambda_1,\lambda_2)\)。
A good feature = the picture changes noticeably when the window moves in every direction = both eigenvalues of the structure tensor \(M\) are large. One large and one small is an edge (localisable in one direction only); both small is a flat region (not localisable). Harris scores with \(\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2\), Shi–Tomasi simply with \(\min(\lambda_1,\lambda_2)\).
3动手玩：描述、匹配、数一数错了多少Play: describe, match, count the lies
找到角点之后，要让图 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 转得更厉害，再关掉主方向。
Once corners are found, the same point in image 2 must "recognise itself". Each corner gets a descriptor computed from the small patch around it: a vector that is insensitive to lighting, small rotations and noise, yet differs clearly between different locations. In the lab below the two images are two views of one synthetic world: image 2 is image 1 warped by a known homography (rotation, scale, shift, a touch of perspective) plus a brightness/contrast change and noise, so every match can be judged right or wrong against the truth. Both descriptors are implemented from scratch in this page:
- SIFT-lite (floating point, L2 distance): build a histogram of gradient orientations around the corner and take the peak as the dominant orientation, rotate a 16×16 patch to it, split it into 4×4 cells, and accumulate gradient magnitude in 8 orientation bins per cell: 128 numbers, normalised, clipped at 0.2, normalised again. This is Lowe's SIFT without the scale space.
- ORB-lite (binary, Hamming distance): find the dominant orientation from the intensity centroid, rotate 256 random sampling pairs by it, and compare the gray values of each pair: 256 bits (the real ORB uses sampling pairs learned offline; random pairs stand in for them here). The Hamming distance is the number of ones in the XOR of two bit strings, one machine instruction per word, which is why ORB is so fast.
There are four ways to match: nearest neighbour (every point gets a partner, good or bad); the ratio test (accept only if the nearest distance \(d_1\) over the second-nearest distance \(d_2\) is below \(\rho\)); cross-check (A's nearest neighbour is B and B's nearest neighbour must be A); and both together. Try rotating image 2 further, then switch the orientation off.
- 用"比值检验"把精确率提高到 90% 以上，同时仍保留至少 25 个匹配。比值阈值多大合适？与"最近邻"相比，召回率损失了多少？Use the "ratio test" to push precision above 90% while keeping at least 25 matches. What threshold does it take, and how much recall do you lose compared with plain nearest neighbour?
- 把图 2 旋转 35° 以上，先关掉主方向（精确率崩溃到 20% 以下），再打开（精确率恢复到 60% 以上）。Rotate image 2 by 35° or more. First switch the orientation off (precision collapses below 20%), then on (precision recovers above 60%).
- 切换到"重复纹理"场景，找到一种设置使精确率仍不低于 80%（至少 5 个匹配）。你付出了什么代价？Switch to the "repetitive" scene and find a setting that keeps precision at 80% or more (at least 5 matches). What did it cost you?
4第二、第三视角：RANSACSecond and third views: RANSAC
先在一条直线上看清 RANSACSee RANSAC on a line first
即使比值检验之后，匹配里仍有错的，而且错得离谱。最小二乘（1.13 节）对此毫无抵抗力：它最小化所有点残差的平方，一个远处的外点贡献的平方误差大得足以把整条线拽走。RANSAC（Fischler 和 Bolles，1981）的想法完全不同：别用所有点去拟合，随机取最少够用的几个点（直线 2 个）拟合一个假设，数一数有多少点支持它（残差小于阈值 \(\tau\) 的点，称为一致集或内点），重复很多次，保留支持者最多的假设，最后只用它的内点重新拟合。外点之间互不相容，所以它们几乎不可能凑出一个大的一致集。
Even after the ratio test, some matches remain wrong, and wrong by a lot. Least squares (Lesson 1.13) has no defence: it minimises the squares of all residuals, and one far-away outlier contributes a squared error large enough to drag the whole line. RANSAC (Fischler and Bolles, 1981) does something entirely different: do not fit to all points; draw the smallest sample that suffices (2 points for a line), fit a hypothesis, count how many points support it (residual below a threshold \(\tau\): the consensus set, the inliers), repeat many times, keep the hypothesis with the most supporters, and finally refit using only its inliers. Outliers disagree with each other, so they can hardly assemble a large consensus set.
- 把外点比例拉到足以让红色最小二乘直线的斜率偏离真值 0.2 以上。要多少外点？Raise the outlier fraction until the red least-squares slope is off by more than 0.2. How many outliers does it take?
- 保持外点比例 ≥ 40%，按"连续运行"，直到最好假设的斜率与真值相差不到 0.15。用了多少次迭代？With the outlier fraction at 40% or more, press "Run" until the best hypothesis' slope is within 0.15 of the truth. How many iterations did it take?
- 阈值 \(\tau\) 取得太小（小于噪声 \(\sigma\) 的 0.7 倍）跑 8 次以上，再取得太大（≥ 2.5）跑 8 次以上，看内点数怎么变。Set the threshold \(\tau\) too small (below 0.7σ) and run 8+ iterations, then too large (2.5 or more) and run 8+ iterations; watch what happens to the inlier count.
要迭代多少次？How many iterations?
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\) 次之内成功。
RANSAC can only succeed if at least one drawn sample consists entirely of inliers. With inlier ratio \(w\) and \(s\) points per sample, one sample is all-inlier with probability about \(w^s\), so the probability that \(N\) samples all fail is \((1-w^s)^N\). Demanding success with probability at least \(p\) gives \(N=\ln(1-p)/\ln(1-w^s)\). The key is the exponent \(s\): the larger the minimal sample, the faster \(N\) grows. That is why so much effort went into "minimal solvers" like the 5-point and P3P algorithms. The lab below checks the formula by Monte Carlo: simulate the sampling of RANSAC many times and count the fraction that succeed within \(N\) iterations.
- 选 \(s=8\)（基础矩阵的 8 点法），把 \(w\) 调到 0.5：\(N\) 是多少？再换成 \(s=5\)，少了多少倍？Pick \(s=8\) (the 8-point algorithm for the fundamental matrix) and set \(w\) to 0.5: what is \(N\)? Switch to \(s=5\): by what factor does it shrink?
投票：每个最小样本给出一个模型，所有点来投票，票数最多者当选。假设—检验：先用最少的数据提出假设，再用其余数据检验，这样提出假设的过程不会被外点污染。鲁棒损失：最大化一致集等价于最小化截断损失 \(\sum_i\min(r_i^2,\tau^2)\)（把超过 \(\tau\) 的残差一律记为 \(\tau^2\)），一个残差再大也只贡献有限的代价。后一种说法正是光束法平差（11.6）里 Huber、Cauchy 等鲁棒核函数的出发点：RANSAC 负责给出好的初值并去掉明显的外点，鲁棒核负责处理剩下的轻微外点。
Voting: every minimal sample proposes a model, all points vote, the most voted wins. Hypothesise and verify: propose with the least possible data, then test with the rest, so proposals are never poisoned by outliers. Robust loss: maximising the consensus set is equivalent to minimising the truncated loss \(\sum_i\min(r_i^2,\tau^2)\) (any residual beyond \(\tau\) costs just \(\tau^2\)), so one huge residual can only cost a bounded amount. This last view is the starting point of the Huber and Cauchy kernels in bundle adjustment (11.6): RANSAC supplies a good initialisation and removes the gross outliers, the robust kernel handles the mild ones that remain.
5再看数学The math
提示：把鼠标悬停在公式中带底色的符号上，FIG 1 或 FIG 4 中对应的元素会被高亮。Tip: hover the highlighted symbols in the formulas; the matching element in FIG 1 or FIG 4 lights up.
结构张量：从平移误差到特征值The structure tensor: from the shift error to eigenvalues
窗口 \(W\)（高斯加权 \(g(\mathbf q)\)）平移 \(\boldsymbol\Delta\) 后的灰度差平方和，对 \(I\) 做一阶泰勒展开（3.1、3.2 节的梯度）：
The weighted (Gaussian \(g(\mathbf q)\)) sum of squared gray-value differences of window \(W\) after a shift \(\boldsymbol\Delta\), with a first-order Taylor expansion of \(I\) (the gradients of Lessons 3.1 and 3.2):
\(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 跟踪要解的线性方程。三种情形：
\(M\) is a symmetric positive semi-definite matrix, the second moment of the gradient cloud, which is why the ellipse in the middle of FIG 1 is the shape of \(M\). A unit shift along an eigenvector \(\mathbf e_i\) costs exactly \(\lambda_i\) (Lesson 1.11). The Hessian of \(E\) at \(\boldsymbol\Delta=\mathbf 0\) (Lesson 3.5) is \(2M\): the same \(J^\top J\) structure that Gauss–Newton (Lesson 6.6) uses to approximate a Hessian, and the linear system that KLT optical-flow tracking solves. Three cases:
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 的检测器用的是后者。实际流程是"阈值（占最大响应的比例）+ 非极大值抑制"，否则一个角点周围会冒出一大片相邻像素。
Harris and Stephens (1988) avoid computing eigenvalues with \(R=\det M-k\,(\operatorname{tr}M)^2=\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2\), usually with \(k\) between 0.04 and 0.06. \(R>0\) exactly when \(\lambda_2/\lambda_1\) exceeds a number fixed by \(k\) alone (about 0.044 for \(k=0.04\)); a very negative \(R\) is an edge. Shi and Tomasi (1994) argued that for tracking the natural score is simply \(\min(\lambda_1,\lambda_2)\); the detector in FIG 1 and FIG 2 uses it. In practice you threshold (as a fraction of the maximum response) and apply non-maximum suppression, otherwise a whole blob of neighbouring pixels fires around every corner.
尺度。\(M\) 的特征值在图像旋转下基本不变（窗口是各向同性的高斯时严格不变），但在缩放下会变：放大后同一个角点的"尖角"变成了一段平滑的弯，窗口里只剩一条边。所以真正的检测器（SIFT 的高斯差分 DoG、Harris–Laplace、ORB 的图像金字塔）会在多个尺度上找极值，并把找到的尺度记下来，用来决定描述子的窗口大小。本节为了简洁只用单一尺度，所以 FIG 2 把图 2 放大 25% 以上时，匹配会明显变差。
Scale. The eigenvalues of \(M\) are essentially unchanged by image rotation (exactly so with an isotropic Gaussian window) but not by scaling: zoom in and the sharp corner turns into a smooth bend, leaving only an edge in the window. Real detectors (SIFT's difference of Gaussians, Harris–Laplace, ORB's image pyramid) therefore look for extrema over several scales and remember the scale, which sets the descriptor's window size. For brevity this lesson uses a single scale, which is why matching in FIG 2 degrades visibly once image 2 is zoomed by 25% or more.
描述子的不变性What each descriptor is invariant to
- 原始灰度块：什么都不变，光照变一点就失效。去均值、除以标准差的块（NCC）：对亮度的增益和偏置 \(I\mapsto aI+b\) 不变。
- SIFT：用梯度，所以对偏置不变；向量归一化消去增益；截断到 0.2 削弱了饱和这类非线性光照变化的影响；主方向带来旋转不变；尺度空间极值带来尺度不变；格子内的软分配与高斯加权使它容忍 1 到 2 个像素的定位误差。
- BRIEF / ORB：每一位只比较两个点的大小，所以对任何单调的灰度变换不变；ORB 用灰度质心定主方向（旋转不变），再用图像金字塔（尺度）。它没有 SIFT 的连续值，辨别力稍弱，但 256 位的汉明距离比 128 维浮点的 L2 快一到两个数量级。
- 学习得到的描述子（SuperPoint 等）：不变性不靠设计而靠数据增强来学，在大视角、昼夜变化下往往优于手工特征，代价是需要 GPU 推理。
没有哪种手工描述子能应付大视角变化（超过大约 30° 到 50° 就明显退化）：这时需要多视角综合、仿射不变的变体，或者学习得到的匹配器。
- Raw gray patch: invariant to nothing, a small lighting change breaks it. Mean-subtracted, std-normalised patch (NCC): invariant to gain and bias \(I\mapsto aI+b\).
- SIFT: uses gradients, so it ignores a bias; vector normalisation removes the gain; clipping at 0.2 weakens the effect of nonlinear lighting changes such as saturation; the dominant orientation gives rotation invariance; scale-space extrema give scale invariance; soft cell assignment and Gaussian weighting tolerate a localisation error of a pixel or two.
- BRIEF / ORB: each bit only compares two pixels, so it is invariant to any monotonic gray-level transform; ORB takes the orientation from the intensity centroid (rotation) and uses an image pyramid (scale). It lacks SIFT's continuous values and is slightly less discriminative, but a 256-bit Hamming distance is one to two orders of magnitude faster than an L2 distance over 128 floats.
- Learned descriptors (SuperPoint and others): invariance is not designed in but learned through data augmentation, and often beats hand-crafted features under large viewpoint or day/night changes, at the cost of GPU inference.
No hand-crafted descriptor survives large viewpoint change (they degrade beyond roughly 30° to 50°): that calls for multi-view aggregation, affine-invariant variants or learned matchers.
比值检验为什么有效Why the ratio test works
对图 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，被一起扔掉。
For one descriptor \(\mathbf f\) from image 1, let \(\mathbf f_1\) be the nearest descriptor in image 2 and \(\mathbf f_2\) the second nearest. If \(\mathbf f_1\) is the true correspondence it should be much closer than any "random" point of image 2, while \(\mathbf f_2\), the closest of the random ones, is farther, so \(d_1/d_2\) is small. If \(\mathbf f\) has no counterpart in image 2 at all (occluded, out of view, missed by the detector), then \(\mathbf f_1\) and \(\mathbf f_2\) are both random and \(d_1\approx d_2\): the ratio is near 1. The histogram in FIG 2 shows the two distributions. Lowe (2004) measured on his data that \(\rho=0.8\) removes about 90% of the false matches while discarding fewer than 5% of the correct ones; this depends on the scene and the descriptor and is not a theorem, so look at the histogram on your own data. Repetitive texture is its worst enemy: the true counterpart and its "twin" are equally close, the ratio is near 1, and both are thrown away.
RANSAC：算法、迭代次数、阈值RANSAC: algorithm, iteration count, threshold
算法。重复：（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\)：
Algorithm. Repeat: (1) draw \(s\) of the \(n\) matches at random (the minimal sample; check for degeneracy: the 4 points of a homography must not contain 3 collinear points, the points must not be bunched together); (2) solve for the model \(\theta\) with a minimal solver (line 2 points, homography 4, fundamental matrix 7 or 8, essential matrix 5, PnP via P3P 3); (3) count the consensus set \(\mathcal C(\theta)=\{i: r_i(\theta)<\tau\}\); (4) keep it if it beats the best so far; (5) update the required \(N\) from the formula below with the current \(\hat w=|\mathcal C|/n\) and stop once enough samples were drawn. Finally refit on the consensus set (and re-count it, possibly for a few rounds).
Iteration count. One sample is all-inlier with probability \(\hl{w}{w}^{\,\hl{s}{s}}\) (for a large population), all \(N\) samples fail with probability \((1-w^s)^N\); set it equal to \(1-p\):
这是 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\)。
This is the geometric distribution of Lessons 4.1 and 4.2: the waiting time to the first success. Round up. Example, \(w=0.5\), \(p=0.99\): \(s=2\) needs 17, \(s=4\) needs 72, \(s=5\) needs 146, \(s=8\) needs 1177, the factor of about eight between the 5-point and the 8-point algorithm. The formula counts only "drew an all-inlier sample"; with noisy inliers even an all-inlier sample can give a poor model, so practice adds a factor of 2 to 10 of margin or repairs the model by local optimisation (LO-RANSAC). Since \(w\) is unknown in advance, use adaptive stopping: whenever the best consensus set improves, recompute \(N\) with the new \(\hat w\).
阈值。设内点残差服从零均值高斯，每个坐标的标准差是 \(\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 里的"对称转移误差"是两个距离之和，所以阈值取得更大一些。
Threshold. Suppose inlier residuals are zero-mean Gaussian with standard deviation \(\sigma\) per coordinate. A one-dimensional residual satisfies \(|r|<1.96\sigma\) with probability 95% (the square root of the 95% quantile 3.84 of \(\chi^2_1\)). For a two-dimensional residual (e.g. a point-to-point reprojection error) \(\|\mathbf r\|^2/\sigma^2\sim\chi^2_2\), whose 95% quantile is 5.99, so the threshold is \(2.45\sigma\). Hartley and Zisserman tabulate this: for a model of codimension 1 (the Sampson distance to a fundamental matrix) \(t^2=3.84\sigma^2\), for codimension 2 (a homography) \(t^2=5.99\sigma^2\). \(\sigma\) is the keypoint localisation error, typically 0.5 to 1 pixel; the "symmetric transfer error" in FIG 5 is a sum of two distances, so its threshold is chosen somewhat larger.
为什么最小二乘经不起一个外点Why least squares cannot survive one outlier
用最小二乘拟合直线 \(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 即源于此。
Fit \(y=ax+b\) by least squares and change the \(y\) of point \(k\) by \(\delta\): the slope changes by \(\delta\,(x_k-\bar x)/\sum_i(x_i-\bar x)^2\), linearly and without bound in \(\delta\). So the breakdown point of least squares is 0: a single large enough outlier makes the estimate arbitrarily bad. LMedS, which minimises the median residual, has a breakdown point of 50%. RANSAC has no fixed breakdown point; its limit is computation: when \(w^s\) is tiny \(N\) explodes (FIG 4), and the true model's consensus set must be larger than what chance assembles. Variants: MSAC (score with the truncated quadratic \(\min(r^2,\tau^2)\) instead of counting, better localisation), LO-RANSAC (optimise promising models on their inliers on the spot), PROSAC (sort by match quality and draw the best matches first), MAGSAC/MAGSAC++ (marginalise over \(\sigma\), no hand-picked threshold); USAC (Raguram et al., 2013) integrates them into one framework, and OpenCV's USAC_MAGSAC descends from it.
鲁棒损失用来处理 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 提供的。
Robust losses handle the mild outliers that remain after RANSAC. The Huber loss is \(\rho(r)=r^2/2\) for \(|r|\le\delta\) and \(\rho(r)=\delta(|r|-\delta/2)\) beyond, so large residuals grow only linearly; the Cauchy loss \(\rho(r)=\tfrac{c^2}{2}\ln(1+r^2/c^2)\) grows even slower. Solved by iteratively reweighted least squares (Lesson 6.9), every residual gets the weight \(\rho'(r)/r\). The Cauchy loss is non-convex and needs a good initial guess, which is exactly what RANSAC provides.
6机器人中的它：从匹配到几何In robotics: from matches to geometry
下面把整条流水线接起来。"单应"模式直接取用 FIG 2 的图像和匹配（在 FIG 2 里改视角、噪声、描述子，这里会跟着变）：放宽比值阈值得到更多匹配，再人为混入随机错配，RANSAC 用 4 点最小求解器 R101.Vision.dltHomography 反复抽样，用对称转移误差判内点，最后用全部内点重新拟合。因为变换是已知的，我们能直接量出估计的单应离真值有多远（图像网格点上的均方根误差，单位像素）。"基础矩阵"模式需要真正有深度的场景（平面场景的基础矩阵是退化的，见下面的误区 4），所以用两台虚拟相机观察 140 个随机三维点，投影加噪声后同样混入错配，用 8 点法 R101.Vision.fundamental8 抽样，用 Sampson 距离判内点。每次都和"对所有匹配直接做最小二乘"比较。
Now the whole pipeline is connected. The "homography" mode takes FIG 2's images and matches directly (change the view, noise or descriptor in FIG 2 and this updates): loosen the ratio threshold to get more matches, add random mismatches by hand, and RANSAC draws samples with the 4-point minimal solver R101.Vision.dltHomography, judges inliers by the symmetric transfer error, and refits on all inliers at the end. Since the transform is known we can measure how far the estimated homography is from the truth (RMS error on a grid of image points, in pixels). The "fundamental matrix" mode needs a scene with real depth (the fundamental matrix of a planar scene is degenerate, see pitfall 4 below), so two virtual cameras observe 140 random 3D points, projections get noise, mismatches are mixed in, the 8-point algorithm R101.Vision.fundamental8 does the sampling and the Sampson distance judges inliers. Each time the result is compared with "plain least squares on all matches".
- 单应模式下，混入至少 25% 的随机错配：RANSAC 重拟合的误差应小于 1.5 像素，而"最小二乘（全部匹配）"的误差远大于 10 像素。In homography mode, mix in at least 25% random mismatches: RANSAC's refit should be below 1.5 px of error, while "least squares (all matches)" is far above 10 px.
- 把迭代预算降到 20 以下直到 RANSAC 失败（误差大于 5 像素，或者根本找不到模型），再升回 300 以上让它恢复。自适应规则说需要多少次？Drop the iteration budget below 20 until RANSAC fails (error above 5 px, or no model found at all), then raise it back to 300 or more so it recovers. How many iterations does the adaptive rule ask for?
- 切换到"基础矩阵"，混入 40% 以上错配，让 RANSAC 的重拟合误差小于 2 像素。再把错配推到 80% 以上：8 个点的样本为什么一下子就失败了？Switch to "fundamental matrix" and mix in 40% or more mismatches so that RANSAC's refit error is below 2 px. Then push the mismatches to 80% or more: why does an 8-point sample suddenly fail?
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）、以及自适应停止。
The ORB-SLAM family (ORB-SLAM2/3) front end: 1000 to 2000 ORB features per frame (FAST corners + pyramid + 256-bit binary descriptors with Hamming distance), a bag-of-words (DBoW2) for loop closure and relocalisation; monocular initialisation fits a homography and a fundamental matrix in parallel and compares their scores to pick the better one. VINS-Mono-style visual-inertial systems track Shi–Tomasi corners with KLT optical flow instead of matching descriptors (motion between frames is small, flow is faster and steadier), then reject outliers with a fundamental-matrix RANSAC. COLMAP for SfM: SIFT features, ratio test plus cross-check, then geometric verification of each image pair (RANSAC estimates of F, E and H; pairs with too few inliers are discarded). OpenCV: BFMatcher (with crossCheck) and knnMatch plus the ratio test, findHomography, findFundamentalMat, findEssentialMat (5-point + RANSAC), solvePnPRansac. Learned methods: SuperPoint detects and describes, SuperGlue and LightGlue match with attention networks, LoFTR matches densely without detecting first; they recall more in hard scenes, but geometric verification still follows. Place recognition first finds candidates with a bag of words or a global descriptor such as NetVLAD, then verifies by feature matching and RANSAC. A robot's VO runs at 30 to 60 frames per second because descriptors are cheap (Hamming distance), the minimal solvers have small \(s\) (5-point or P3P) and the stopping rule is adaptive.
7常见误区Common pitfalls
阈值 \(\tau\) 的单位必须和残差一致：像素？归一化图像坐标（除以焦距，数量级 \(10^{-3}\)）？Sampson 距离的平方？把像素阈值直接用在归一化坐标的残差上（残差只有 \(10^{-3}\) 量级），所有点都成了内点；反过来把归一化尺度的阈值用在像素残差上，所有点都成了外点。取得太紧（小于 \(\sigma\)）则真内点被拒（FIG 3 的任务 3），太松则外点混进来，重拟合被拖偏。按 \(\sigma\) 和 \(\chi^2\) 分位数来定，而不是凭感觉。
The threshold \(\tau\) must be in the same units as the residual: pixels? normalised image coordinates (divided by the focal length, of order \(10^{-3}\))? the squared Sampson distance? A pixel threshold applied to residuals in normalised coordinates (which are only of order \(10^{-3}\)) makes every point an inlier; a normalised-scale threshold applied to pixel residuals makes every point an outlier. Too tight (below \(\sigma\)) rejects true inliers (task 3 of FIG 3), too loose lets outliers in and drags the refit. Set it from \(\sigma\) and the \(\chi^2\) quantile, not by feel.
8 点法和 DLT 单应的线性系统里，像素坐标的量级是 \(10^3\)，二次项是 \(10^6\)，常数项是 1，系统条件数极差，小噪声就能让解面目全非。必须先把点平移到质心为 0、平均距离 \(\sqrt2\)（Hartley 归一化），解完再变回去。R101.Vision.dltHomography 与 fundamental8 内部已经做了；自己写 RANSAC 时漏掉这一步，是"明明数据没问题，结果却随机"的常见原因。
In the linear systems of the 8-point algorithm and the DLT homography, pixel coordinates are of order \(10^3\), quadratic terms \(10^6\) and the constant term 1, so the system is terribly conditioned and small noise can wreck the solution. First translate the points to zero centroid and mean distance \(\sqrt2\) (Hartley normalisation) and undo it after solving. R101.Vision.dltHomography and fundamental8 do this internally; forgetting it in your own RANSAC is a classic reason for "the data are fine but the result is random".
单应的 4 个点里有 3 点共线，解不唯一；相距太近的两个点会让直线斜率毫无意义（FIG 3 里我们要求样本点至少相隔 0.2）。抽样时必须检查退化并重抽，否则一个"完美拟合"的假设可能毫无意义，还会数出一大堆内点。另一个常见失误是把最小样本拟合出来的模型直接当结果：那个模型把 \(s\) 个带噪点精确穿过，噪声没有被平均掉。用全部内点重新做最小二乘，精度大约提高 \(\sqrt{n_{\text{inl}}/s}\) 倍（FIG 5 的"RANSAC"与"重拟合"两个误差）。
If 3 of the 4 points of a homography are collinear the solution is not unique; two points very close together make a line's slope meaningless (in FIG 3 we require the sample points to be at least 0.2 apart). Check for degeneracy while sampling and redraw, otherwise a "perfect fit" can be meaningless and still count a crowd of inliers. Another common slip is returning the model fitted to the minimal sample: it passes exactly through \(s\) noisy points and the noise is never averaged. Refit by least squares on all inliers; precision improves by roughly \(\sqrt{n_{\text{inl}}/s}\) (compare the "RANSAC" and "refit" errors in FIG 5).
如果全部匹配落在一个平面上（地面、墙），或者相机只做纯旋转，基础矩阵的 8 点法就是退化的：一族不同的 \(F\) 都能完美解释这些匹配，求出来的那个误差为零却毫无意义（这就是 FIG 5 的基础矩阵模式必须用有深度的场景的原因，也是 ORB-SLAM 同时算单应和 F 的原因）。特征全挤在图像一角，几何同样病态，所以检测器常常按网格限制每格的特征数。RANSAC 默认场景是静止的：如果匹配一半落在行驶的汽车上，另一半落在背景上，RANSAC 会选更大的一堆，另一堆被当作外点；若运动物体占了多数，机器人会得出"自己在动"的错误结论。需要的话要先做语义分割，或者对多个运动模型分别做 RANSAC。
If all matches lie on one plane (the ground, a wall), or the camera only rotates, the 8-point algorithm for F is degenerate: a whole family of different \(F\) explain the matches perfectly, and the one returned has zero error and no meaning (that is why FIG 5's fundamental mode needs a scene with depth, and why ORB-SLAM fits both a homography and an F). Features bunched in one corner of the image make the geometry ill-conditioned too, so detectors often cap the number of features per grid cell. RANSAC assumes a static scene: if half the matches sit on a driving car and half on the background, RANSAC picks the bigger pile and the other becomes "outliers"; if moving objects are the majority, the robot concludes that it is moving. Segment semantically first if needed, or run RANSAC separately for several motion models.
固定迭代 100 次在 \(w=0.6\)、\(s=8\) 时成功概率只有 \(1-(1-0.6^8)^{100}\approx 82\%\)；\(w\) 掉到 0.4 时几乎必败。不要写死次数，要用自适应停止加一个上限。另外，单应约束的是点到点（残差是二维的），基础矩阵只约束点到线（残差是一维的，对极线两侧有一条很宽的带），所以同样的数据在 F 下几乎总能数出更多"内点"，随机错配也有机会碰巧落在极线附近：比较 H 和 F 谁更合适时不能直接比较内点数，ORB-SLAM 的做法是给每个模型算一个考虑残差大小和阈值的得分再比较。
A fixed 100 iterations at \(w=0.6\), \(s=8\) succeeds with probability only \(1-(1-0.6^8)^{100}\approx 82\%\); at \(w=0.4\) it almost always fails. Do not hard-code the count: use adaptive stopping plus a cap. Also, a homography constrains point to point (a 2D residual), while a fundamental matrix constrains only point to line (a 1D residual, with a wide band around each epipolar line), so the same data almost always count more "inliers" under F, and a random mismatch can land near its epipolar line by chance. When deciding between H and F you therefore cannot compare raw inlier counts; ORB-SLAM scores each model with a function of the residuals and the threshold and compares the scores.
8小练习Check yourself
9延伸阅读Further reading
- 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 的原始论文The original RANSAC paper
- C. Harris & M. Stephens, A combined corner and edge detector, Alvey Vision Conference, 1988 — Harris 角点The Harris corner detector
- J. Shi & C. Tomasi, Good features to track, CVPR 1994 — 用 \(\min(\lambda_1,\lambda_2)\) 选可跟踪的特征，KLT 的基础Choosing trackable features by \(\min(\lambda_1,\lambda_2)\); the basis of KLT
- D. G. Lowe, Distinctive image features from scale-invariant keypoints, IJCV 60(2), 2004 — SIFT 与比值检验SIFT and the ratio test
- E. Rublee, V. Rabaud, K. Konolige & G. Bradski, ORB: an efficient alternative to SIFT or SURF, ICCV 2011 — 带方向的 FAST 与旋转 BRIEF，SLAM 的主力特征Oriented FAST and rotated BRIEF, the workhorse feature of 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、退化检测）Modern RANSAC variants in one framework (PROSAC, LO-RANSAC, degeneracy checks)
- 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\) 推导与自适应迭代次数The \(\chi^2\) threshold derivation and adaptive iteration count
- R. Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., Ch. 7 (feature detection and matching) — 特征检测、描述子与匹配的综述A survey of keypoint detection, descriptors and matching