Classical features, descriptors, matching

经典特征、描述子与匹配

Lesson 02 gave us convolution and, with it, image gradients — but an edge map only tells us where intensity changes, not which point in photo A is the same physical point in photo B. This lesson turns local structure into correspondences: detect repeatable keypoints (using the very gradient operators we just built), describe their neighborhoods invariantly, match by nearest neighbor with a ratio test, and reject the inevitable bad matches with RANSAC. This is the classical pipeline behind panorama stitching, SLAM, and retrieval — and the mental model we still debug learned systems with.

第 02 课给了我们卷积，以及随之而来的图像梯度——但一张边缘图只能告诉我们强度在哪里发生变化，而不能告诉我们照片 A 中的哪个点与照片 B 中同一个物理点相对应。本课把局部结构转化为对应关系：检测可重复的关键点（就用我们刚刚造出的那些梯度算子），对其邻域做不变性描述，用最近邻加比值检验来匹配，再用 RANSAC 剔除那些不可避免的错误匹配。这就是全景拼接、SLAM 与检索背后的经典流水线——也是我们至今仍在用来调试学习型系统的思维模型。

The plan计划

Four moves. (1) Which pixels are even localizable? — flat loses, edges are ambiguous, corners win, made rigorous by the structure tensor behind Harris. (2) How to describe a patch so it survives rotation and lighting — the gradient-orientation histogram (SIFT's core idea) and where invariance comes from. (3) Matching: nearest neighbor in descriptor space plus Lowe's ratio test to kill ambiguous matches. (4) RANSAC: fit geometry from a minimal random sample, count inliers, and the iteration-count math that says how many tries you need. 四步走。(1) 到底哪些像素是可定位的？——平坦区输了、边缘有歧义、角点获胜，这一点由 Harris 背后的结构张量严格化。(2) 如何描述一个图块，使它在旋转和光照变化下仍然成立——梯度方向直方图（SIFT 的核心思想）以及不变性从何而来。(3) 匹配：在描述子空间中做最近邻，再加上 Lowe 比值检验来剔除有歧义的匹配。(4) RANSAC：从一个最小的随机样本拟合几何，统计内点，以及告诉你需要试多少次的迭代次数公式。

1 · Which points are localizable? The structure tensor

1 · 哪些点是可定位的？结构张量

A keypoint is only useful if we can re-find it from another viewpoint — it must be repeatable and localizable. Ask: if I shift a small window by a tiny amount (Δx, Δy), how much does the patch's appearance change? The change in sum-of-squared intensity differences, for a window W, is

一个关键点只有在我们能从另一个视角重新找到它时才有用——它必须是可重复的且可定位的。设问：如果我把一个小窗口平移一个微小的量 (Δx, Δy)，图块的外观会变化多少？对于一个窗口 W，强度差平方和的变化为

E(Δx, Δy) = ∑_(x,y)∈W [ I(x+Δx, y+Δy) − I(x, y) ]² .

Linearize with a first-order Taylor expansion — I(x+Δx,y+Δy) ≈ I + I_xΔx + I_yΔy, where I_x, I_y are the image gradients (the Sobel responses from lesson 02). The difference becomes I_xΔx + I_yΔy, and squaring and summing gives a tidy quadratic form:

用一阶泰勒展开做线性化——I(x+Δx,y+Δy) ≈ I + I_xΔx + I_yΔy，其中 I_x, I_y 是图像梯度（第 02 课的 Sobel 响应）。差值变成 I_xΔx + I_yΔy，平方再求和便得到一个整洁的二次型：

E(Δx,Δy) ≈ [Δx Δy] · M · [Δx Δy]^T, M = ∑_W [ I_x² I_xI_y ; I_xI_y I_y² ] .

That 2×2 matrix M is the structure tensor (a.k.a. the second-moment matrix). It summarizes how gradient energy is distributed around the point. Its two eigenvalues λ₁, λ₂ are the strength of intensity variation along the two principal directions — and they classify the point completely:

那个 2×2 矩阵 M 就是结构张量（又称二阶矩矩阵）。它概括了梯度能量在该点周围是如何分布的。它的两个特征值 λ₁, λ₂ 是沿两个主方向的强度变化强度——而它们能把这个点完全分类：

Eigenvalues特征值	Geometry几何	Localizable?可定位？
λ₁ ≈ λ₂ ≈ 0	flat region — no gradient in any direction平坦区——任何方向都没有梯度	No — the window looks the same wherever it slides.否——窗口无论滑到哪里看起来都一样。
λ₁ ≫ λ₂ ≈ 0	edge — variation across, none along边缘——横跨方向有变化，沿边方向没有	Only across the edge; it slides freely along the edge (the aperture problem).只有横跨边缘时才能定位；它可以沿着边缘自由滑动（孔径问题）。
λ₁, λ₂ both large都很大	corner — variation in two directions角点——两个方向都有变化	Yes — any shift changes the patch, so it pins down a unique location.是——任何平移都会改变图块，因此它能钉死一个唯一的位置。

This is exactly why corners beat edges beat flat: a corner is the only structure that constrains both Δx and Δy. The 2×2 eigenvalues are closed-form, but extracting them needs a per-pixel square root (the discriminant √(tr²/4 − det)) and gives you two numbers to threshold. Harris instead combines the determinant and trace — which are cheap, smooth functions of M's entries with no square root — into a single threshold-friendly cornerness score:

这正是为什么角点胜过边缘、边缘胜过平坦：角点是唯一同时约束 Δx 和 Δy 的结构。2×2 的特征值虽有闭式解，但提取它们需要逐像素开一次平方根（判别式 √(tr²/4 − det)），而且给你两个数要去设阈值。Harris 转而把行列式和迹——它们是 M 各元素的廉价、平滑、无需开方的函数——合成一个便于设阈值的单一角点度（cornerness）分数：

R = det(M) − κ·trace(M)² = λ₁λ₂ − κ(λ₁+λ₂)², κ ≈ 0.04–0.06.

Worked intuition. For a corner both eigenvalues are large, so det (their product) is large and dominates → R is large positive. For an edge one eigenvalue is ≈ 0, so det ≈ 0 but trace² is large → R goes negative. For flat, both terms ≈ 0 → R ≈ 0. Threshold R high and keep local maxima and you have your corners. (Blob detectors like SIFT's difference-of-Gaussians find a complementary kind of repeatable point — a bright/dark spot at a characteristic scale — but the localizability logic is the same. Difference-of-Gaussians = subtract a more-blurred copy of the image from a less-blurred one; the result peaks at blob-like spots of a size set by the blur difference — an efficient stand-in for the scale-detecting operator SIFT needs.)

直觉推演。对角点而言，两个特征值都很大，所以 det（二者之积）很大并占主导 → R 为大正数。对边缘而言，一个特征值 ≈ 0，所以 det ≈ 0，但 trace² 很大 → R 变负。对平坦区而言，两项都 ≈ 0 → R ≈ 0。把 R 设一个高阈值并保留局部极大值，你就得到了角点。（像 SIFT 的高斯差分那样的斑点检测器，找到的是一类互补的可重复点——某个特征尺度下的亮/暗斑——但可定位性的逻辑是一样的。高斯差分 = 用图像一份模糊较少的拷贝减去一份模糊较多的拷贝；结果会在尺寸由模糊差决定的斑点状位置处出现峰值——这是 SIFT 所需的那个尺度检测算子的一个高效替身。）

Worked by hand — an edge patch. Let us build M on a concrete 3×3 vertical-edge patch (dark left, bright right), using the lesson-02 Sobel operators to get the gradient at each pixel:

手算一遍——一个边缘图块。让我们在一个具体的 3×3 竖直边缘图块（左暗右亮）上构造 M，用第 02 课的 Sobel 算子求出每个像素处的梯度：

intensity patch I Sobel-x at center → Ix Sobel-y at center → Iy ┌──────────────┐ │ 10 10 80│ row 1: (10·-1)+(10·0)+(80·+1) = 70 a purely vertical edge has │ 10 10 80│ row 2 (center, ×2): ×2 → 140 NO vertical intensity change, │ 10 10 80│ row 3: (10·-1)+(10·0)+(80·+1) = 70 so Iy ≈ 0 everywhere. └──────────────┘ sum = 70+140+70 = 280, ÷4 = +70

The Sobel-x kernel [−1 0 1; −2 0 2; −1 0 1] weights the center row twice as heavily (the ±2), so the three row sums are 70, 140, 70; adding them and applying the widget's ÷4 normalization gives (70+140+70)/4 = 280/4 = +70. Every pixel in this window therefore has roughly I_x ≈ 70 (strong left→right gradient) and I_y ≈ 0. Summing the outer products [I_x², I_xI_y; I_xI_y, I_y²] over the 9 pixels:

Sobel-x 卷积核 [−1 0 1; −2 0 2; −1 0 1] 对中间行的加权是两倍（那个 ±2），所以三行的行和是 70, 140, 70；把它们加起来并施加小部件的 ÷4 归一化，得到 (70+140+70)/4 = 280/4 = +70。因此这个窗口里的每个像素大致都有 I_x ≈ 70（强烈的从左到右梯度）和 I_y ≈ 0。把外积 [I_x², I_xI_y; I_xI_y, I_y²] 在这 9 个像素上求和：

M = ∑_W [ I_x² I_xI_y ; I_xI_y I_y² ] ≈ [ 9·70² 0 ; 0 0 ] = [ 44100 0 ; 0 0 ] .

Because M is already diagonal, its eigenvalues are read straight off the diagonal: λ₁ = 44100 (huge) and λ₂ = 0. One large, one zero → the textbook edge signature. Check the Harris score with κ = 0.04: det(M) = 44100·0 = 0, trace(M) = 44100, so R = 0 − 0.04·44100² ≈ −7.8×10⁷ — strongly negative, exactly the "edge" verdict. Add a second, perpendicular gradient (a corner) and the off-diagonal/second eigenvalue fills in, det turns positive, and R flips positive. The widget below recomputes this same M live as you move a window over a real corner.

由于 M 已经是对角阵，它的特征值可以直接从对角线上读出：λ₁ = 44100（巨大）和 λ₂ = 0。一大一零 → 教科书式的边缘特征。用 κ = 0.04 检查 Harris 分数：det(M) = 44100·0 = 0，trace(M) = 44100，于是 R = 0 − 0.04·44100² ≈ −7.8×10⁷——强烈为负，正好是"边缘"的判定。加上第二个垂直方向的梯度（一个角点），非对角元/第二个特征值就填补进来，det 变正，R 翻转为正。下面的小部件会在你把窗口移过一个真实角点时，实时重新计算这同一个 M。

The zero eigenvalue is the aperture problem made numeric: looking at a moving straight edge through a small window (an "aperture"), you can measure motion across the edge but motion along it is invisible — the patch looks identical as it slides that way — which is precisely the direction in which M has no eigenvalue energy.

那个为零的特征值正是被数值化了的孔径问题：透过一个小窗口（一个"孔径"）看一条运动的直边，你能测出横跨边缘的运动，但沿着边缘的运动是不可见的——图块沿那个方向滑动时看起来一模一样——而这恰恰就是 M 没有特征值能量的那个方向。

1.5 · Interactive · the structure-tensor scope

1.5 · 交互 · 结构张量示波镜

This is the heart of the detector. Move the window over a small grayscale image with a bright square in it, and watch the structure tensor M, its eigenvalues, and the Harris response R recompute live from the Sobel gradients — exactly the by-hand arithmetic above, on real numbers. The ellipse drawn at the window has axes proportional to √λ₁, √λ₂: a fat circle over a corner, a thin sliver over an edge, a dot over flat. Read the verdict and confirm it matches where you are.

这是检测器的核心。把窗口移过一张带有亮方块的小灰度图，看着结构张量 M、它的特征值以及 Harris 响应 R 从 Sobel 梯度实时重新计算出来——就是上面手算的那套运算，只不过用的是真实数字。窗口处画出的椭圆，其轴长与 √λ₁, √λ₂ 成正比：在角点上是一个胖圆、在边缘上是一条细缝、在平坦区是一个点。读出判定结果，并确认它与你所在的位置相符。

Structure-tensor scope — flat vs edge vs corner, live

结构张量示波镜——平坦、边缘、角点，实时对比

Left: a 16×16 grayscale image with a bright square (corners, edges, and flat interior/exterior). Hover (or it auto-scans) to place the analysis window. Right: the 2×2 tensor M = ∑[I_x², I_xI_y; I_xI_y, I_y²] from Sobel gradients, its eigenvalues, the gradient ellipse (axes ∝ √λ), and Harris R = det − κ·trace². Verdict: λ₁,λ₂ both small = flat; one large = edge; both large = corner.

左：一张 16×16 的灰度图，中间有一个亮方块（含角点、边缘以及平坦的内部/外部）。悬停（或让它自动扫描）来放置分析窗口。右：由 Sobel 梯度得到的 2×2 张量 M = ∑[I_x², I_xI_y; I_xI_y, I_y²]、它的特征值、梯度椭圆（轴长 ∝ √λ），以及 Harris R = det − κ·trace²。判定：λ₁、λ₂ 都小 = 平坦；一个大 = 边缘；两个都大 = 角点。

window size:窗口大小： κ: 0.04

λ₁ (large)

λ₁（大）

—

λ₂ (small)

λ₂（小）

—

Harris R

—

Verdict

判定

—

Show the core JS查看核心代码

// gx,gy are precomputed Sobel gradients; (r,c) is the window center, h = half-width
function structureTensor(gx, gy, r, c, h){
  let Sxx=0, Sxy=0, Syy=0;                 // accumulate outer products over the window
  for (let u=-h; u<=h; u++)
    for (let v=-h; v<=h; v++){
      const ix = gx[r+u][c+v], iy = gy[r+u][c+v];
      Sxx += ix*ix; Sxy += ix*iy; Syy += iy*iy;
    }
  return [[Sxx, Sxy], [Sxy, Syy]];         // M = [[Ix^2, IxIy],[IxIy, Iy^2]]
}
function eigvals(M){                        // closed-form 2x2 symmetric eigenvalues
  const a=M[0][0], b=M[0][1], d=M[1][1];
  const tr=a+d, det=a*d - b*b;
  const disc=Math.sqrt(Math.max(0, tr*tr/4 - det));
  return [tr/2 + disc, tr/2 - disc];        // [λ1, λ2], λ1 >= λ2
}
const R = det - kappa*tr*tr;                // det(M) - κ·trace(M)^2

2 · Describing a patch invariantly

2 · 对图块做不变性描述

Detecting a repeatable point is half the job; we also need a descriptor — a vector summarizing the neighborhood — that reads the same from a different viewpoint, so the same physical point produces nearby vectors in both images. The enemies of sameness are: a change in overall brightness, a rotation of the camera, and a change in scale. SIFT (Scale-Invariant Feature Transform) earns invariance to each with a specific construction; understanding it explains every learned descriptor that followed.

检测出一个可重复的点只完成了一半工作；我们还需要一个描述子——一个概括邻域的向量——它从不同视角读出来是相同的，从而让同一个物理点在两张图像中都产生彼此邻近的向量。破坏这种一致性的敌人有：整体亮度的变化、相机的旋转，以及尺度的变化。SIFT（尺度不变特征变换，Scale-Invariant Feature Transform）用一套具体构造对每一种都赢得了不变性；理解了它，也就理解了此后出现的每一个学习型描述子。

Use gradients, not raw pixels. The descriptor is built from gradient magnitudes and orientations, not intensities. Adding a constant to every pixel (a brightness shift) leaves gradients unchanged → automatic illumination invariance to additive changes; normalizing the final vector handles multiplicative ones.用梯度，而非原始像素。描述子是从梯度幅值和方向构建的，而不是强度。给每个像素加上一个常数（一次亮度平移）不会改变梯度 → 对加性变化自动获得光照不变性；对最终向量做归一化则处理乘性变化。
Histogram the orientations. Split the patch into a 4×4 grid of cells; in each cell, build a histogram of gradient orientations (e.g. 8 bins), weighted by gradient magnitude. The result is a 4×4×8 = 128-dimensional vector. Histogramming over a cell means small spatial wobbles just move energy within a bin → robustness to small deformations and localization error.对方向做直方图。把图块划分成 4×4 的单元格网格；在每个单元格里，构建一个以梯度幅值加权的梯度方向直方图（例如 8 个 bin）。结果是一个 4×4×8 = 128 维的向量。在单元格上做直方图意味着微小的空间抖动只是让能量在一个 bin 内部移动 → 对小形变和定位误差的鲁棒性。
Rotate to a canonical orientation. Find the dominant gradient direction of the patch and measure all orientations relative to it. Now if the camera rotates, every orientation rotates by the same amount and the relative histogram is unchanged → rotation invariance.旋转到一个规范方向。找出图块的主梯度方向，并把所有方向都相对于它来度量。这样一来，如果相机旋转，每个方向都旋转相同的量，而相对直方图保持不变 → 旋转不变性。
Pick a characteristic scale. Detect the keypoint in a Gaussian scale-space (lesson 02's blur, applied at many strengths) and describe the patch at that scale, so a zoomed-in copy is described identically → scale invariance. Scale-space = the stack of images you get by blurring the original by increasing amounts (simulating zooming out); the characteristic scale of a keypoint is the blur level at which its blob response is strongest — the scale at which it "looks most like itself".选取一个特征尺度。在高斯尺度空间（第 02 课的模糊，以多种强度施加）中检测关键点，并在那个尺度上描述图块，这样一个放大的拷贝会被描述得一模一样 → 尺度不变性。尺度空间 = 把原图以逐渐增大的量模糊所得到的一叠图像（模拟缩小拉远）；一个关键点的特征尺度是其斑点响应最强的那个模糊级——也就是它"看起来最像自己"的那个尺度。

The invariance recipe, distilled不变性的配方，提炼版

Invariance to a transformation = measure the thing in a frame that the transformation does not move. Brightness shift → use gradients (it cancels). Rotation → measure angles relative to the dominant one. Scale → measure at the detected characteristic scale. This is the exact same logic lesson 12 will use for learned embeddings, and lesson 14 for self-supervised augmentation invariance — only the frame is learned rather than hand-built. 对某个变换的不变性 = 在一个该变换不会移动的参照系里去度量目标。亮度平移 → 用梯度（它会抵消）。旋转 → 相对于主方向来度量角度。尺度 → 在检测到的特征尺度上度量。这与第 12 课用于学习型嵌入、第 14 课用于自监督数据增强不变性的逻辑一模一样——只不过参照系是学出来的，而非手工搭建的。

Binary descriptors like ORB (Oriented FAST + Rotated BRIEF) trade some distinctiveness for speed: they store a string of bits, each the outcome of a brightness comparison between two sampled points, so matching is a Hamming-distance XOR-and-popcount instead of a float dot product — orders of magnitude cheaper, at the cost of robustness in hard matching regimes.

像 ORB（Oriented FAST + Rotated BRIEF）这样的二值描述子，用一些区分度换取速度：它们存储一串比特，每一位都是两个采样点之间一次亮度比较的结果，因此匹配是汉明距离的异或再计数（XOR-and-popcount），而不是浮点点积——便宜好几个数量级，代价是在困难匹配场景下的鲁棒性。

3 · Matching — nearest neighbor and the ratio test

3 · 匹配——最近邻与比值检验

With a descriptor per keypoint in each image, a match is found by nearest neighbor: for each descriptor in image A, find the closest descriptor in image B (Euclidean distance for SIFT floats, Hamming for ORB bits). But many keypoints look alike — repeated windows, texture, foliage — so the nearest neighbor is often wrong. Lowe's ratio test is the classic filter: compare the distance to the nearest neighbor against the second-nearest, and accept the match only if the best is decisively better:

每张图像的每个关键点都有一个描述子后，匹配通过最近邻来找到：对图像 A 中的每个描述子，在图像 B 中找到距离最近的描述子（SIFT 浮点用欧氏距离，ORB 比特用汉明距离）。但很多关键点长得很像——重复的窗口、纹理、树叶——所以最近邻常常是错的。Lowe 比值检验是经典的过滤器：把到最近邻的距离与到次近邻的距离作比较，仅当最优者明显更优时才接受这个匹配：

accept match ⟺ d₁ / d₂ < 0.75 (d₁ = nearest, d₂ = second-nearest distance).

Why it works. If a keypoint is distinctive, its true match is much closer than any other candidate, so d₁ ≪ d₂ and the ratio is small. If the region is ambiguous (a repeated pattern), several candidates are about equally close, d₁ ≈ d₂, the ratio approaches 1, and we discard the match rather than guess. The threshold 0.75 trades recall for precision: lower keeps fewer, cleaner matches. The output is a set of candidate correspondences that is cleaner but still contains outliers — wrong matches that survived the test. That residual contamination is what RANSAC exists to handle.

它为什么有效。如果一个关键点很有辨识度，它的真实匹配会比任何其他候选都近得多，于是 d₁ ≪ d₂，比值很小。如果这个区域有歧义（一个重复图案），会有好几个候选几乎同样近，d₁ ≈ d₂，比值趋近于 1，我们就丢弃这个匹配而不去瞎猜。阈值 0.75 是用召回率换精确率：取得越低，保留下来的匹配越少、越干净。输出是一组更干净但仍含有外点（outlier）的候选对应——那些通过了检验的错误匹配。这些残留的污染，正是 RANSAC 存在要处理的东西。

4 · RANSAC — fitting geometry despite outliers

4 · RANSAC——在有外点的情况下拟合几何

The surviving matches should obey a single geometric relationship (e.g. a homography for a planar scene, or the epipolar constraint of lesson 05). A homography here is the 3×3 projective transform that maps one image of a flat scene to another view of it: the 3×3 projective matrix has 9 entries but overall scale is free (it acts in homogeneous coordinates), leaving 8 degrees of freedom; each point match contributes 2 equations (one per pixel coordinate), so 4 matches give the 8 equations that fix it. But ordinary least-squares fitting is hopeless here: a single gross outlier drags the fit arbitrarily far, because squared error rewards the model for partially appeasing the outlier. RANSAC (RANdom SAmple Consensus) flips the logic — instead of fitting all points and hoping, it repeatedly fits a minimal sample and trusts the model that the most points agree with:

存活下来的匹配应当服从单一的几何关系（例如平面场景的一个单应矩阵，或第 05 课的对极约束）。这里的单应矩阵是把一个平面场景的一张图像映射到它的另一视图的 3×3 射影变换：这个 3×3 射影矩阵有 9 个元素，但整体尺度是自由的（它作用在齐次坐标上），因此剩下 8 个自由度；每对点匹配贡献 2 个方程（每个像素坐标一个），所以 4 对匹配给出确定它所需的 8 个方程。但普通最小二乘拟合在这里毫无希望：单一一个严重外点就能把拟合拖到任意远的地方，因为平方误差会奖励模型去部分迁就那个外点。RANSAC（随机抽样一致性，RANdom SAmple Consensus）把逻辑反了过来——它不去拟合所有点然后碰运气，而是反复拟合一个最小样本，并信任那个被最多点认同的模型：

Sample minimally. Randomly pick the fewest points needed to define the model — 2 points for a line, 4 correspondences for a homography.最小采样。随机挑选定义模型所需的最少点数——直线取 2 个点，单应矩阵取 4 对对应。
Fit the model to just that sample.仅用那个样本拟合模型。
Count inliers. Count how many of all points lie within a distance threshold t of the model — the consensus set.统计内点。统计所有点中有多少落在模型的距离阈值 t 之内——即一致集（consensus set）。
Keep the best. Remember the model with the largest inlier count. Repeat for k iterations, then optionally re-fit using all inliers of the winner.保留最优者。记住内点数最多的那个模型。重复 k 次迭代，然后可选地用胜出者的全部内点重新拟合一次。

The threshold t encodes how much noise an inlier may have; too tight rejects good matches, too loose lets outliers sneak in. The deep question is how many iterations k you need. Suppose a fraction w of points are inliers and the minimal sample is n points. The probability that one random sample is all inliers is wⁿ; the probability it contains at least one outlier is 1 − wⁿ; the probability that all k samples are contaminated is (1 − wⁿ)^k. We want that failure probability below some small 1 − P (say P = 0.99 confidence of one clean sample):

阈值 t 编码了一个内点可以带多少噪声；太紧会拒掉好的匹配，太松会让外点混进来。更深层的问题是：你需要多少次迭代 k。设有比例为 w 的点是内点，且最小样本为 n 个点。一次随机采样全部是内点的概率是 wⁿ；它至少含一个外点的概率是 1 − wⁿ；所有 k 次采样都被污染的概率是 (1 − wⁿ)^k。我们希望这个失败概率低于某个很小的 1 − P（比如取 P = 0.99 作为得到一次干净样本的置信度）：

1 − (1 − wⁿ)^k ≥ P ⟹ k ≥ log(1 − P) / log(1 − wⁿ) .

Worked number. Line fit (n=2), 50% inliers (w=0.5), want P=0.99: wⁿ=0.25, so k ≥ log(0.01)/log(0.75) ≈ −4.6 / −0.288 ≈ 16 iterations. Now a homography (n=4) at the same inlier rate: wⁿ = 0.0625, k ≥ log(0.01)/log(0.9375) ≈ 71. The lesson: required iterations explode with the sample size n and with the outlier fraction — which is why we work so hard upstream (ratio test) to raise w before RANSAC ever runs. Try it below: scatter with outliers, step RANSAC, and compare the consensus line to a least-squares fit that the outliers wreck.

算个具体数。直线拟合（n=2）、50% 内点（w=0.5）、想要 P=0.99：wⁿ=0.25，所以 k ≥ log(0.01)/log(0.75) ≈ −4.6 / −0.288 ≈ 16 次迭代。现在换成单应矩阵（n=4），同样的内点率：wⁿ = 0.0625，k ≥ log(0.01)/log(0.9375) ≈ 71。这里的教训是：所需迭代次数随样本大小 n 和外点比例而爆炸式增长——这正是我们为什么要在上游（比值检验）如此卖力地在 RANSAC 运行之前抬高 w。在下面试一试：撒一些带外点的散点，单步执行 RANSAC，并把一致性直线与被外点搞垮的最小二乘拟合作比较。

RANSAC line fit — consensus beats least-squares under outliers

RANSAC 直线拟合——有外点时一致性胜过最小二乘

Blue dots are inliers (near a hidden true line); red dots are outliers. Each RANSAC step samples 2 points, fits a line, and counts inliers within the threshold band. The green line is the best consensus model so far; the dashed orange line is ordinary least-squares over all points — watch the outliers drag it off. Raise the threshold to admit noisier inliers.

蓝点是内点（靠近一条隐藏的真实直线）；红点是外点。每一次 RANSAC step 采样 2 个点、拟合一条直线，并统计阈值带内的内点。绿线是目前为止最好的一致性模型；橙色虚线是对所有点做的普通最小二乘——看着外点把它拖偏。抬高阈值可以纳入噪声更大的内点。

inlier threshold t: 内点阈值 t： 14

Iteration k

迭代 k

Best inliers

最佳内点数

RANSAC inliers

RANSAC 内点

—

Least-sq inliers

最小二乘内点

—

Show the core JS查看核心代码

function ransacStep(pts, t){
  const [p,q] = sampleTwo(pts);             // minimal sample: 2 points
  const line = lineThrough(p, q);           // fit a line to them
  let inliers = 0;
  for (const pt of pts)
    if (distToLine(pt, line) < t) inliers++; // consensus: count agreers within t
  if (inliers > best.inliers) best = {line, inliers}; // keep the best
  return best;
}
// expected iterations for P=0.99, n=2, inlier fraction w:
//   k = log(1-0.99) / log(1 - w**2)

Trap陷阱

RANSAC fails silently when the model is wrong (fitting a line to a curve), when the outlier fraction is so high that wⁿ is tiny and k would need to be enormous, or when the threshold is mistuned. It finds the model with the most agreers — that is not the same as the correct model if your assumptions are off. Always sanity-check the final inlier count and residuals. 当模型本身就错了（用直线去拟合曲线）、当外点比例高到 wⁿ 变得极小以致 k 需要大得离谱、或者当阈值没调好时，RANSAC 会悄无声息地失败。它找到的是认同者最多的模型——如果你的假设不对，那与正确模型并不是一回事。永远要对最终的内点数和残差做一次合理性检查。

Connection to learned systems

与学习型系统的联系

Modern matching swaps SIFT/ORB descriptors for learned embeddings (lesson 12) and even learns the matching step itself (SuperGlue and its lineage), but the four questions are unchanged: what makes a point repeatable, what makes a representation invariant to the nuisance you care about, how do you reject ambiguous matches, and what geometric constraint should the survivors satisfy? When a learned model breaks under a viewpoint or lighting shift, the classical decomposition is the diagnostic: name the invariance you are missing — scale, rotation, illumination, nonrigid deformation, or projective geometry — and you know which part of the pipeline to fix.

现代的匹配把 SIFT/ORB 描述子换成了学习型嵌入（第 12 课），甚至连匹配这一步本身也学出来（SuperGlue 及其一脉），但那四个问题始终没变：是什么让一个点可重复、是什么让一个表示对你关心的干扰因素不变、你如何剔除有歧义的匹配，以及存活者应满足什么几何约束？当一个学习型模型在视角或光照变化下失效时，这套经典分解就是诊断工具：说出你缺失的是哪种不变性——尺度、旋转、光照、非刚性形变，还是射影几何——你就知道该修流水线的哪一部分。

Where this points next

这将指向何处

We can now produce clean 2D correspondences: "this point in image A is that point in image B." But a correspondence is still just a pair of pixel coordinates — it does not, by itself, tell us where either point is in 3D, or how the two cameras were posed. To turn matches into geometry — depth, structure, camera motion — we need a model of how 3D points became pixels in the first place. Lesson 04 builds that: the pinhole camera, projection from similar triangles, the intrinsics matrix K, the extrinsics [R|t], homogeneous coordinates, lens distortion, and calibration. With the camera model in hand, lesson 05 will finally promote our 2D matches to 3D via epipolar geometry and triangulation.

现在我们能够产出干净的二维对应了："图像 A 中的这个点就是图像 B 中的那个点。"但一组对应仍然只是一对像素坐标——它本身并不能告诉我们任一点在三维中的位置，也不能告诉我们两台相机是如何摆放的。要把匹配变成几何——深度、结构、相机运动——我们需要一个模型来刻画三维点当初是如何变成像素的。第 04 课就来构建它：针孔相机、由相似三角形导出的投影、内参矩阵 K、外参 [R|t]、齐次坐标、镜头畸变以及标定。有了相机模型在手，第 05 课终将通过对极几何与三角化，把我们的二维匹配提升到三维。

Takeaway要点

The classical correspondence pipeline is detect → describe → match → verify. Detect: a point is localizable only if its structure tensor M = ∑[I_x², I_xI_y; I_xI_y, I_y²] has two large eigenvalues — that is a corner; Harris scores it cheaply as det(M) − κ·trace(M)². Describe: build a gradient-orientation histogram and earn invariance by measuring in a frame the nuisance does not move (gradients for brightness, dominant-orientation for rotation, characteristic-scale for zoom). Match: nearest neighbor + Lowe's ratio test (d₁/d₂ < 0.75) to drop ambiguous pairs. Verify: RANSAC fits a minimal sample, keeps the largest consensus set, and needs k ≥ log(1−P)/log(1−wⁿ) iterations. The output is 2D correspondences — which lesson 04's camera model turns into 3D. 经典的对应流水线是检测 → 描述 → 匹配 → 验证。检测：一个点只有当它的结构张量 M = ∑[I_x², I_xI_y; I_xI_y, I_y²] 有两个大特征值时才是可定位的——那就是一个角点；Harris 用 det(M) − κ·trace(M)² 廉价地给它打分。描述：构建一个梯度方向直方图，并通过在干扰因素不会移动的参照系里度量来赢得不变性（用梯度对付亮度、用主方向对付旋转、用特征尺度对付缩放）。匹配：最近邻 + Lowe 比值检验（d₁/d₂ < 0.75）以丢弃有歧义的配对。验证：RANSAC 拟合一个最小样本、保留最大的一致集，需要 k ≥ log(1−P)/log(1−wⁿ) 次迭代。输出是二维对应——第 04 课的相机模型会把它变成三维。

Interview prompts

面试题

Why are corners better keypoints than edges? (§1 — only a corner gives the structure tensor two large eigenvalues, constraining both Δx and Δy; an edge slides freely along itself — the aperture problem.)为什么角点是比边缘更好的关键点？(§1 —— 只有角点才让结构张量有两个大特征值，同时约束 Δx 和 Δy；边缘会沿自身自由滑动——即孔径问题。)
What does the SIFT descriptor try to be invariant to, and how? (§2 — illumination (gradients + normalization), rotation (relative to dominant orientation), scale (describe at characteristic scale); a 4×4×8 = 128-d orientation histogram.)SIFT 描述子力图对什么保持不变，又是如何做到的？(§2 —— 光照（梯度 + 归一化）、旋转（相对于主方向）、尺度（在特征尺度上描述）；一个 4×4×8 = 128 维的方向直方图。)
How does the ratio test reject bad matches? (§3 — accept only if nearest/second-nearest distance ratio < ~0.75, so ambiguous regions where d₁ ≈ d₂ are discarded.)比值检验如何剔除错误匹配？(§3 —— 仅当最近/次近距离之比 < ~0.75 时才接受，于是 d₁ ≈ d₂ 的歧义区域被丢弃。)
How does RANSAC tolerate outliers, and how many iterations does it need? (§4 — fit minimal samples, keep the largest consensus set; k ≥ log(1−P)/log(1−wⁿ), e.g. ≈16 for a line at 50% inliers, P=0.99.)RANSAC 如何容忍外点，又需要多少次迭代？(§4 —— 拟合最小样本、保留最大的一致集；k ≥ log(1−P)/log(1−wⁿ)，例如直线在 50% 内点、P=0.99 时约为 16。)
How would you debug a feature-matching pipeline producing many false matches? (§2–§4 — check the needed invariance, tighten the ratio test to raise inlier fraction w, then RANSAC on the geometric constraint; verify final inlier count and residuals.)你会如何调试一个产生大量错误匹配的特征匹配流水线？(§2–§4 —— 检查所需的不变性、收紧比值检验以抬高内点比例 w，然后在几何约束上跑 RANSAC；核验最终的内点数和残差。)