Week 04: Features & Matching 学习笔记

Week 04: Features & Matching 学习笔记

本章的核心目标不是单纯“检测边缘”或“找角点”，而是建立一条完整的传统视觉匹配流水线：从图像中的局部变化出发，提取可重复、可区分的局部锚点，再用描述子进行跨图像匹配，最后用几何一致性过滤错误匹配。课件前半部分从 Sobel、Canny、Contour 说明“如何把像素变化变成结构边界”，后半部分进入真正的 matching problem：两张图像中同一物理点在亮度、颜色、视角、尺度、旋转下会变化，因此我们需要寻找跨变化仍稳定存在的 invariants。

—

1. 本章进化树：从边缘检测到几何匹配

可以把本章理解成如下技术演进链：

图像像素 I(x, y)
 ↓
局部亮度变化：Sobel gradient
 ↓ 解决：找边缘候选
 ↓ 问题：边缘厚、噪声敏感、无明确判定
Canny edge detection
 ↓ 解决：平滑 + 梯度 + NMS + 双阈值 + hysteresis
 ↓ 问题：边缘点不适合匹配，沿边方向不可定位
Corner / Harris
 ↓ 解决：找二维方向上都发生变化的点
 ↓ 问题：无尺度、无方向、无描述子
SIFT
 ↓ 解决：DoG 尺度空间 + 主方向对齐 + 128-D 梯度直方图描述子
 ↓ 问题：局部描述子匹配仍有假匹配
KNN + Lowe Ratio Test
 ↓ 解决：过滤最近邻不够独特的匹配
 ↓ 问题：单个匹配正确不代表全局几何一致
RANSAC + Homography
 ↓ 解决：用全局投影几何筛选 inliers
 ↓
应用：panorama stitching, localization, large-scale visual search / BoW

这条链条的核心逻辑是：先从图像中找到“哪里有结构”，再判断“哪些结构适合跨图像重识别”，最后用几何约束判断“这些局部相似是否共同解释同一个场景变换”。

—

2. Sobel：从像素到梯度

2.1 要解决的问题

原始图像只是灰度或颜色值。边缘检测的第一步是问：图像在哪些位置发生剧烈变化？Sobel 用卷积近似图像在 (x) 和 (y) 方向的偏导数，从而得到局部亮度变化方向和强度。课件中强调，Sobel X 检测左右方向亮度变化，即垂直边缘；Sobel Y 检测上下方向亮度变化，即水平边缘；梯度幅值把所有方向的边缘合并起来。

2.2 Sobel 卷积公式

设灰度图像为

其中：

• (I(x,y))：坐标 ((x,y)) 处的像素强度；
• (x)：水平坐标，通常向右增加；
• (y)：垂直坐标，通常向下增加。

Sobel 在两个方向上的卷积核通常写为：

于是：

其中：

• (*)：二维卷积操作；
• (G_x)：图像在水平方向的梯度响应，亮度从左到右变化越剧烈，(|G_x|) 越大；
• (G_y)：图像在垂直方向的梯度响应，亮度从上到下变化越剧烈，(|G_y|) 越大。

梯度幅值为：

梯度方向为：

其中：

• ：图像梯度向量；
• ：边缘强度；
• ：亮度上升最快的方向，也就是梯度方向；
• ：带象限信息的反正切函数。

直觉上，边缘不是“线本身”，而是强度函数的陡坡。Sobel 的输出告诉我们：哪里有坡，以及坡朝哪个方向。

2.3 Sobel 的局限

Sobel 的问题不是完全不能找边缘，而是它只完成了“梯度估计”，没有完成“边缘决策”。课件列出三个核心痛点：边缘厚，不是单像素精度；仍然对噪声敏感；没有阈值机制，不告诉我们哪些像素最终应被认为是边缘。

因此 Sobel 的定位是：它是 Canny 的一个组件，而不是完整的边缘检测系统。

—

3. Canny：从梯度图到干净、连续、单像素边缘

3.1 Canny 为什么出现

Sobel 给出梯度，但实际边缘检测还需要解决三个问题：噪声会造成虚假梯度；真实边缘常常是几像素宽的带状区域；单阈值会在“断边”和“假边”之间两难。Canny 的贡献是把边缘检测变成一条完整 pipeline：Gaussian smoothing → gradient computation → non-maximum suppression → dual threshold → hysteresis tracking。

3.2 Step 1: Gaussian smoothing

噪声往往表现为高频变化，也会产生大梯度。Canny 首先用高斯滤波平滑图像：

其中：

符号定义：

• (I)：原始图像；
• ：经过尺度 平滑后的图像；
• ：二维高斯核；
• ：高斯标准差，控制平滑强度；
• (x,y)：相对卷积中心的坐标。

直觉上， 越大，噪声越少，但细节也越容易被抹掉。因此 Canny 的第一步已经引入了检测稳定性与细节保留之间的 trade-off。

3.3 Step 2: Gradient computation

在平滑图像上计算梯度：

其中：

• (M(x,y))：梯度幅值，即候选边缘强度；

• ：梯度方向；

• 真正的边缘方向与梯度方向垂直。

3.4 Step 3: Non-Maximum Suppression

Canny 的核心创新之一是 NMS。课件中的表述是：沿梯度方向，只保留局部最大值，其余抑制，使厚边缘变成单像素边缘。

数学上，对每个像素 (p=(x,y))，沿梯度方向 找到前后两个邻居 (p+) 和 (p-)。NMS 的规则为：

其中：

• (p)：当前像素；
• (p+,p-)：沿梯度方向的两个相邻采样点；
• (M(p))：当前像素梯度幅值；
• )：NMS 后的边缘强度。

实际实现中，连续角度 通常量化为四个方向：

| 梯度角度范围 | 量化方向 | 比较邻居 | | ————————— | ———-: | —– | | ([−22.5^circ,22.5^circ]) | (0^circ) | 左、右 | | ([22.5^circ,67.5^circ]) | (45^circ) | 左下、右上 | | ([67.5^circ,112.5^circ]) | (90^circ) | 上、下 | | ([112.5^circ,157.5^circ]) | (135^circ) | 左上、右下 |

这里的直觉是：边缘是梯度幅值曲面上的 ridge。NMS 只保留 ridge 顶点。

3.5 Step 4: Dual threshold

单阈值的问题是两难：阈值太高，真实边缘断裂；阈值太低，噪声边缘太多。课件明确指出：单阈值无法同时保证 noise suppression 和 edge continuity，所以使用两个阈值。

设高阈值为 ，低阈值为 ，且

对 NMS 后的响应 )，分类为：

其中：

• strong edge：强边缘，直接保留，是后续连接的 anchor；
• weak edge：弱边缘，是否保留取决于是否连接到 strong edge；
• non-edge：直接丢弃。

3.6 Step 5: Edge tracking by hysteresis

Hysteresis 的逻辑是：强边缘作为种子，弱边缘只有在与强边缘 8-connected 时才被保留。课件特别强调，强边缘是 seeds，弱边缘靠近 seeds 则生长，孤立弱边缘死亡。

形式化地，设：

最终边缘集合为：

其中：

• (S)：强边缘像素集合；
• (W)：弱边缘像素集合；
• (E)：最终保留的边缘集合；
• 8-connected：允许上下左右和四个对角方向连接。

Canny 的根本思想是：边缘是否真实，不只由局部强度决定，还由结构连续性决定。

—

4. Contour extraction：从边缘像素到边界对象

Canny 给出边缘像素，但很多任务需要的是“一个完整物体边界”。课件用 “Blind Person Touching a Wall” 类比 contour tracing：在二值图中找到边界起点，沿边界逐像素追踪，回到起点得到一条完整轮廓，然后重复直到所有边界都被找到。

可以把 contour extraction 理解为从 pixel-level edge map 到 object-level boundary representation 的转换。

设二值图为：

其中：

• (B(x,y)=1)：前景；
• (B(x,y)=0)：背景。

一个边界像素可以定义为：

其中：

• ：前景区域；
• ：前景边界；
• )：像素 (p) 的 8 邻域；
• (q)：邻域像素。

轮廓是一条有序边界序列：

满足：

即相邻边界点连通，并最终闭合。

—

5. Matching challenge：为什么边缘不够，为什么需要角点

5.1 本章后半部分的核心问题

课件从这里转向 matching：给定同一场景的两张图像，需要找对应点：

其中：

• ((x_i,y_i))：第一张图像中的点；
• ((x_i’,y_i’))：第二张图像中对应同一物理点的投影；
• (i)：第 (i) 个匹配点编号。

困难在于：像素强度、颜色会变，视角和透视几何也会变。目标是找到 invariants，即在这些变化下仍能稳定识别的 anchor。

5.2 为什么不能直接用边缘匹配

边缘的根本问题是 aperture problem：在一个小窗口内，边缘只提供垂直于边缘方向的变化；沿着边缘方向滑动，局部图像几乎不变。因此边缘点无法区分自己和同一条边上的邻居。课件明确指出：edge points cannot be distinguished from their neighbours。

局部窗口的变化可以粗略理解为：

如果是边缘，只有一个方向梯度大。沿边缘方向的位移 满足：

因此窗口几乎不变，位置不可唯一确定。

5.3 好 feature 的两个硬要求

课件给出两个核心要求：repeatability 和 distinctiveness。

| 要求 | 含义 | 如果不满足会怎样 | | ————— | ————– | ————– | | Repeatability | 不同视角、光照下仍能被检测到 | 同一物理点在另一张图里找不到 | | Distinctiveness | 不容易和附近或其他区域混淆 | 匹配到错误位置 |

角点优于边缘，因为角点在二维方向上都有明显变化，可以提供完整的位置约束。课件总结为：flat region 有 0 个变化方向，edge 有 1 个变化方向，corner 有 2 个变化方向。

—

6. Harris corner：用二阶矩阵刻画“二维变化”

6.1 Harris 要解决的问题

Harris 的目标是数学化定义 corner。直觉上，如果一个小窗口无论往哪个方向移动，像素内容都会明显变化，那么中心点就是角点；如果只有某一个方向变化，则是边缘；如果各方向都不变，则是平坦区域。课件从 window shift 出发，用一阶 Taylor 展开推导 structure tensor。

6.2 Window shift energy

设窗口中心在 ((x,y))，考虑窗口平移 ((u,v)) 后的强度变化：

符号定义：

• (E(u,v))：窗口平移 ((u,v)) 后的总强度变化；
• (W)：当前局部窗口内的像素集合；
• (w(x,y))：窗口权重，常用 Gaussian 权重，越靠近中心权重越大；
• (I(x,y))：原图像强度；
• (u,v)：窗口在水平和垂直方向上的小位移。

判别逻辑：

• 对所有方向 ((u,v))，(E(u,v)) 都小：flat；
• 某些方向大，某些方向小：edge；
• 所有方向都大：corner。

6.3 一阶 Taylor 展开推导

对小位移 ((u,v))，有：

其中：

所以：

代入 (E(u,v))：

展开平方：

写成矩阵形式：

其中 structure tensor / second-moment matrix 为：

也可写成：

其中：

• ：窗口内 (x) 方向梯度能量；
• ：窗口内 (y) 方向梯度能量；
• ：两个方向梯度的相关性；
• (M)：局部梯度分布的二阶统计矩阵。

物理直觉：(M) 描述局部窗口在不同方向移动时的变化强度。它不是直接保存像素值，而是保存局部梯度能量的形状。

6.4 特征值解释

设 (M) 的两个特征值为：

它们表示窗口沿两个主轴方向移动时的变化强度。课件中用这两个特征值分类 flat、edge、corner。

| 情况 | (lambda_1) | (lambda_2) | 解释 | | —— | ———-: | ———-: | ————— | | Flat | 小 | 小 | 任意方向移动都几乎不变 | | Edge | 大 | 小 | 一个方向变化大，沿边方向变化小 | | Corner | 大 | 大 | 两个方向变化都大 |

更严格地说：

其中 ) 是位移向量在 (M) 的特征向量坐标系下的表示。若两个特征值都大，则任何非零位移都会造成明显变化。

6.5 Harris response：避免显式求特征值

直接求 需要解特征方程。Harris 用 determinant 和 trace 近似分类。课件强调：不用解特征值，直接由矩阵元素计算。

定义：

Harris response：

展开为：

其中：

• (R)：Harris 角点响应；
• (k)：经验常数，通常 ；

• ：两个方向变化强度的乘积；

• ：总梯度能量；
• (A,B,C)：上文定义的 structure tensor 元素。

6.6 为什么 (det) 和 (op(“trace”)) 等于特征值的积和

对 矩阵

特征方程为：

即：

展开：

另一方面，如果两个根是 ，则：

比较系数得：

这就是课件中用 Vieta’s formulas 证明 det 和 trace 的原因。

6.7 Harris 如何分类

若 flat：

若 edge，例如 ：

若 corner：

所以 Harris 的核心判据是：

6.8 Harris 后处理：NMS、threshold、minDistance

Harris 得到的是一个 response map，需要工程后处理。课件中列出三步：NMS、threshold、spatial uniformity。

NMS

局部邻域 ) 中只保留最大 (R)：

Threshold

课件给出的阈值形式为：

其中：

• ：整张图最大 Harris response；
• ：保留角点质量比例；
• (R)：当前点 response。

OpenCV 中常见：

cv2.goodFeaturesToTrack(gray, maxCorners, qualityLevel, minDistance)

课件建议：

minDistance

按 (R) 从大到小排序，贪心选择角点；每选择一个角点，就删除其半径 内的候选点：

这个步骤的目的不是提高单点质量，而是让角点空间分布更均匀，避免大量角点挤在同一个纹理区域。

—

7. Harris 到 SIFT：为什么 keypoint 还不够

7.1 Harris 的三个 fatal gaps

课件明确指出 Harris 有三个致命缺口：没有尺度、没有方向、没有描述子。

| Harris 缺口 | 具体症状 | SIFT 的解决方案 | | ————– | ——————- | ————————————– | | No scale | 远近变化导致固定窗口看到的内容不同 | DoG scale space，keypoint 携带尺度 (sigma) | | No orientation | 图像旋转后 patch 对不齐 | 主方向估计，描述前旋转对齐 | | No descriptor | 只有位置，无法验证是否为同一 3D 点 | 128-D gradient histogram descriptor |

Harris 回答的是 “where is a corner?”；SIFT 回答的是 “where is a stable keypoint, at what scale and orientation, and what does its neighborhood look like?”

—

8. SIFT：尺度、旋转、光照鲁棒的局部特征

8.1 SIFT 的三大问题与三大解决方案

课件总结得非常清楚：DoG scale space 解决尺度不变性；dominant orientation alignment 解决旋转不变性；gradient orientation histogram 解决光照鲁棒性并形成 128-D descriptor。

8.2 Problem 1: scale invariance

同一个角点在远处和近处看起来不同。如果用固定大小窗口，远处可能看到整栋楼，近处只看到一块砖。所以 SIFT 构建尺度空间。

高斯尺度空间定义：

其中：

• )：尺度 下的平滑图像；
• )：标准差为 的高斯核；
• (I(x,y))：原图像；
• ：尺度参数。

Difference of Gaussians：

其中：

• (D)：DoG 响应；
• (k)：相邻尺度之间的倍数；

• ：下一层尺度。

SIFT 在 DoG 体中寻找三维极值：

或：

其中：

• ：当前尺度同层 8 个邻居，上下尺度各 9 个邻居，总计 26 个邻居；
• 极大值或极小值都可作为候选 keypoint；
• 每个 keypoint 记录其尺度 。

课件强调：同一个 corner 在不同距离下会在自己的 “natural scale” 被匹配。

8.3 Lowe’s keypoint sieve：过滤低质量点

初始 DoG 会找到很多点，课件说约 90% 是 junk，需要过滤。

低对比度过滤

若 DoG 响应太小，则认为不稳定：

其中：

• )：尺度空间中的点；
• (T_c)：contrast threshold；

• ：该点 DoG 响应。

边缘响应过滤

DoG 的边缘极值也可能很强，但沿边方向定位不稳定。SIFT 使用 Hessian 的主曲率比值过滤边缘点。

令 Hessian 为：

其中：

• ：DoG 在 (x,y) 方向的二阶导；
• ：混合二阶导；
• (H)：局部二阶曲率矩阵。

设 Hessian 特征值为 ，且 。如果点是边缘，则一个曲率很大，一个曲率很小，即 很大。令：

Lowe 使用：

作为保留条件。若左侧过大，则说明主曲率比例过大，是边缘响应，应丢弃。

推导如下：

若 ，则：

这个逻辑与 Harris 很相似：Harris 用两个方向都大来定义 corner；SIFT 用主曲率比例过大来排除 edge-like unstable extrema。

8.4 Problem 2: rotation invariance

若图像旋转，patch 也旋转。SIFT 的解决方案是给 keypoint 分配主方向，再在该方向对齐后的坐标系中提取描述子。课件给出三步：计算 36-bin 梯度直方图；取峰值方向为 dominant orientation；旋转坐标系对齐该方向。

每个像素的梯度为：

其中：

• (m(x,y))：尺度图像 (L) 上的梯度幅值；

• ：梯度方向；

• (L)：keypoint 所在尺度的高斯图像。

方向直方图：

其中：

• (h(b))：第 (b) 个方向 bin 的累积权重；
• ，每个 bin 覆盖 ；
• ：keypoint 周围圆形邻域；
• (w(x,y))：距离中心越近越大的高斯权重；
• ：指示函数。

主方向：

然后将局部坐标旋转：

其中：

• ：keypoint 坐标；
• )：旋转矩阵；
• ：主方向对齐后的局部坐标。

直觉是：不要使用图像全局的“上方”作为方向，而是使用 feature 自己的主方向作为参考系。

8.5 Problem 3: lighting invariance

课件指出 raw pixels 在光照变化下会彻底改变，pixel differences 也仍然敏感，而 gradient directions 更稳定。SIFT 因此使用梯度方向直方图。

SIFT descriptor 的标准构造：

1. 在尺度归一化、方向对齐后的 keypoint 周围取 邻域；
2. 划分为 个 cell；
3. 每个 cell 统计 8-bin 梯度方向直方图；
4. 拼接得到：

维向量：

L2 归一化：

clip：

再归一化：

其中：

• ：SIFT descriptor；
• (f_i)：descriptor 第 (i) 维；
• clip at 0.2：减少强梯度或局部光照突变对描述子的支配；
• re-normalize：恢复单位长度。

这一步的核心是把局部 patch 从 raw appearance 转成 gradient distribution。它损失了一些精细像素信息，但换来了对亮度、对比度、微小形变更强的鲁棒性。

—

9. Feature matching：从描述子相似到几何一致

9.1 Brute-force matching

给定图像 A 的描述子集合：

图像 B 的描述子集合：

brute-force matching 对每个 ，寻找最近邻：

匹配为：

复杂度：

课件指出，brute-force 会产生许多 false matches，并且存在 scalability wall；移动 AR 等场景需要更快的检索。

9.2 KNN + Lowe Ratio Test

单纯最近邻的问题是：最近的不一定可靠，尤其在重复纹理中，第一近邻和第二近邻可能都很像。因此 Lowe Ratio Test 找 (k=2) 个最近邻，比较距离比值。课件给出 OpenCV 代码：

if m.distance < 0.75 * n.distance:
 good.append(m)

数学形式：