11.1.1 从像素到特征向量#

一张 1000×1000 图像有 (10^6) 个像素，不可能直接比较。

特征提取 (Feature Extraction)：把图像（或局部区域）压缩成一个低维向量，使得：

• 相同物体的图像 → 相近的向量
• 不同物体 → 远离的向量

11.1.2 理想特征的六大性质#

1. 独特性 (Distinctive)：不同位置特征向量差异大
2. 重复性 (Repeatable)：同一点在不同图像上都能被检测到
3. 尺度不变 (Scale-invariant)：缩放图像特征不变
4. 旋转不变 (Rotation-invariant)：旋转图像特征不变
5. 光照鲁棒：亮度/对比度变化不影响
6. 计算高效：实时应用需求

历史：从简单（角点）到复杂（SIFT、HOG），再到深度学习（CNN 特征），每一步都在追求上述性质。

11.1.3 特征的两个层次#

1
特征 = 检测 (Detection) + 描述 (Description)
2
       ↑                   ↑
3
     "哪里是关键点"         "它长什么样"

检测器 (Detector)：找到”显著”位置（角点、斑点） 描述子 (Descriptor)：在该位置生成一个向量描述邻域

许多经典算法把两者结合（SIFT 既检测又描述），也有专门的检测器（Harris、FAST）和描述子（SIFT、BRIEF）。

11.2.1 角点的直觉#

角点 = 灰度在两个方向都剧变的位置：

1
平坦区:         边缘:          角点:
2
▓▓▓▓▓          ▓▓▓▓▓          ▓▓░░░
3
▓▓▓▓▓          ▓▓▓▓▓          ▓▓░░░
4
▓▓▓▓▓          ░░░░░          ▓▓░░░
5
(零变化)       (一个方向)     (两个方向都变)

为什么角点好？

• 边缘：沿边缘移动小窗不变 → 匹配时有滑动歧义
• 角点：任何方向移动都变 → 定位唯一

11.2.2 Moravec 算法（1977，入门）#

对每个点，计算 8 方向滑动窗口的灰度差平方和 (SSD)： [ E(u, v) = \sum_{(x, y) \in W} [I(x + u, y + v) - I(x, y)]^2 ]

只考虑 ((u, v) \in {(1,0), (0,1), (1,1), (1,-1)}) 等 8 方向，取最小值： [ C = \min_{u, v} E ]

• 平坦：所有 (E) 都小 → C 小
• 边缘：沿边缘方向 (E) 小 → C 小
• 角点：所有方向都大 → C 大

局限：

• 只考虑离散 8 方向 → 各向异性
• 对噪声敏感

11.2.3 Harris 角点检测（1988，经典必会）#

1
平坦:  ───（无椭圆，E≈0）
2
边缘:  ─────────── （长椭圆）
3
角点:  ⭕           （小椭圆）

1
dst = cv2.cornerHarris(gray, blockSize=2, ksize=3, k=0.04)
2
# NMS + 阈值
3
corners = np.where(dst > 0.01 * dst.max())

11.2.4 Shi-Tomasi（1994）#

直接用最小特征值 (\min(\lambda_1, \lambda_2) > T)，比 Harris 略优。

1
corners = cv2.goodFeaturesToTrack(gray, maxCorners=100, qualityLevel=0.01, minDistance=10)

11.2.5 FAST 角点（2006，实时之王）#

Features from Accelerated Segment Test。核心思想：极简 + 极快。

1
        16  1  2
2
     15        3
3
    14          4
4
    13    p     5
5
    12          6
6
     11        7
7
        10  9  8

1
fast = cv2.FastFeatureDetector_create(threshold=30)
2
kp = fast.detect(gray)

11.3.1 动机#

角点是一维特征（位置点）。有时我们想检测小圆点、圆形物体（细胞、水滴、星星）。

11.3.2 LoG 斑点检测#

回忆第 10 章：LoG = (\nabla^2 G_\sigma)。

关键：对半径 (r) 的亮斑，LoG 在 (\sigma = r/\sqrt{2}) 时响应最强。

算法：

1. 对不同 (\sigma) 计算 LoG 响应
2. 找 3D (x, y, σ) 局部极值 → 斑点位置与尺度

11.3.3 DoG 近似 SIFT 前身#

(\text{LoG} \approx G_{k\sigma} - G_\sigma)（(k = 1.6)），速度更快。

11.3.4 Hessian 斑点#

(H) 矩阵（二阶导）： [ H = \begin{bmatrix} I_{xx} & I_{xy} \ I_{xy} & I_{yy} \end{bmatrix} ] 行列式 (\det(H) = I_{xx} I_{yy} - I_{xy}^2)，在斑点中心最大。

SURF 使用 Hessian 近似加速。

11.4.1 四大步骤#

1
1. 尺度空间构建       (DoG 金字塔)
2
2. 关键点定位         (DoG 极值 + 亚像素精化)
3
3. 方向分配            (主方向 + 辅方向)
4
4. 特征描述子          (128 维 HOG-like)

11.4.2 Step 1：尺度空间#

高斯金字塔 + 每组内多尺度：

1
Octave 1: σ, kσ, k²σ, k³σ, k⁴σ   (5 层)
2
下采样 2
3
Octave 2: 2σ, 2kσ, 2k²σ, ...
4
...

取相邻层差分得 DoG： [ D(x, y, \sigma) = G_{k\sigma} * I - G_\sigma * I ]

11.4.3 Step 2：关键点定位#

11.4.4 Step 3：方向分配#

在关键点邻域计算梯度幅值与方向，建立 36 bin 方向直方图：

• 每像素投票（加权按幅值 + 高斯距离）
• 选最大 bin → 主方向
• 若有其他 bin > 80% 最大 → 增加一个关键点副本（辅方向）

这一步使描述子旋转不变（后续都以主方向为参考）。

11.4.5 Step 4：描述子#

以关键点为中心、按主方向旋转，取 16×16 邻域，分成 4×4 子块，每块算 8 方向直方图： [ 16 \text{ blocks} \times 8 \text{ bins} = 128 \text{ 维向量} ]

归一化：

• L2 归一化
• 限制每维 < 0.2（防止光照突变影响）
• 再 L2 归一化

最终 128 维、L2-norm=1 的单位向量。

11.4.6 性质#

• 尺度不变 ✅（多尺度 DoG）
• 旋转不变 ✅（方向对齐）
• 光照鲁棒 ✅（直方图 + 归一化）
• 部分视角不变 ✅（~ 30°）

11.4.7 使用（OpenCV）#

1
sift = cv2.SIFT_create()
2
kp, des = sift.detectAndCompute(gray, None)
3
# des: (N, 128) float32

性能：一张 1000×800 图约 1000-3000 个关键点，CPU 上几百毫秒。

11.5.1 SURF（Bay 2006）#

Speeded Up Robust Features。

• 用 Hessian 行列式 代替 DoG（但用盒滤波 + 积分图近似 → 快）
• 64 维描述子（比 SIFT 短一半）
• 速度 3-5 倍 SIFT
• 已过专利期

11.5.2 BRIEF（Calonder 2010）#

Binary Robust Independent Elementary Features。

思想：描述子直接是 256 bit 二进制串，由 256 对邻域像素比较决定： [ \tau(p; x, y) = \begin{cases} 1 & I(x) < I(y) \ 0 & \text{otherwise} \end{cases} ]

优点：

• 比较用 XOR + popcount（汉明距离），极快
• 存储小（32 字节）

缺点：

• 对旋转敏感（没有方向对齐）

11.5.3 ORB（Rublee 2011）#

Oriented FAST and Rotated BRIEF。OpenCV 默认的 SIFT 替代（免费）。

• 检测：FAST + Harris 评分筛选
• 方向：用灰度质心法（灰度重心相对几何中心的方向）
• 描述：旋转版 BRIEF（用主方向旋转 BRIEF 采样对）

特点：

• 速度比 SIFT 快 100 倍
• 精度略低于 SIFT
• 嵌入式 / SLAM 首选

1
orb = cv2.ORB_create(nfeatures=500)
2
kp, des = orb.detectAndCompute(gray, None)
3
# des: (N, 32) uint8

11.5.4 对比总结#

11.6.1 暴力匹配 (Brute Force)#

对图像 A 的每个描述子，在图像 B 中找最近的。

距离度量：

• 浮点描述子 (SIFT/SURF)：L2 距离
• 二进制描述子 (BRIEF/ORB)：汉明距离

1
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
2
matches = bf.match(des1, des2)

Cross-check：A→B 最近 ⇔ B→A 最近，双向一致才保留。

11.6.2 Lowe’s Ratio Test（必会）#

SIFT 论文建议：对每个查询，看最近与次近距离比。若比值 < 0.75：

• 最近明显优于次近 → 可信匹配
• 否则 → 有歧义，丢弃

1
knn = bf.knnMatch(des1, des2, k=2)
2
good = [m for m, n in knn if m.distance < 0.75 * n.distance]

效果：大幅降低错误匹配率。

11.6.3 FLANN 加速（KD 树 / LSH）#

大规模匹配暴力 (O(MN)) 太慢。FLANN (Fast Library for Approximate Nearest Neighbors)：

• 浮点描述子：KD-Tree（近似最近邻）
• 二进制描述子：LSH（Locality Sensitive Hashing）

1
index_params = dict(algorithm=1, trees=5)    # KD-Tree
2
search_params = dict(checks=50)
3
flann = cv2.FlannBasedMatcher(index_params, search_params)

11.7.1 问题#

特征匹配后，大量外点 (outliers)（错误匹配）仍存在。直接用所有点估计变换 → 结果被噪声污染。

11.7.2 RANSAC（Random Sample Consensus）#

Fischler & Bolles 1981 的经典算法。

1
RANSAC for Homography:
2
  最优 H = None
3
  最大内点数 = 0
4
  for i in 1..N:
5
      随机采样 4 对匹配
6
      计算单应 H
7
      统计 inliers: 投影误差 < ε 的点数
8
      若 > 最大内点数 → 更新最优 H
9
  最终用所有 inliers 重新估计 H

迭代次数公式： [ N = \frac{\log(1 - p)}{\log(1 - w^s)} ]

• (p)：期望至少一次采样全为内点的概率（0.99）
• (w)：内点比例
• (s)：每次采样点数（单应是 4）

例：(w = 0.5, s = 4, p = 0.99) → (N \approx 72)

1
H, mask = cv2.findHomography(pts1, pts2, cv2.RANSAC, 5.0)

11.7.3 RANSAC 的变体#

• MLESAC：最大似然估计（非硬阈值）
• MSAC：M-estimator 变体
• LO-RANSAC：每次迭代后做局部优化
• USAC：统一框架，许多预处理和后处理

11.8.1 什么是纹理？#

纹理 = 像素灰度的空间排列模式。草地、布料、木纹、石墙等。

11.8.2 灰度共生矩阵 (GLCM)#

Haralick 1973 提出。对距离 (d)、角度 (\theta)，统计 [ G(i, j) = #{像素对 (p_1, p_2) : I(p_1) = i, I(p_2) = j, 位移 (d, \theta)} ]

归一化为概率。基于 GLCM 定义纹理描述量：

• 能量 (Energy)：(\sum G^2)（越大越规则）
• 对比度 (Contrast)：(\sum (i-j)^2 G)（越大变化越强）
• 相关性：(\sum (i - \mu_i)(j - \mu_j) G / (\sigma_i \sigma_j))
• 同质性：(\sum G / (1 + |i - j|))

1
from skimage.feature import graycomatrix, graycoprops
2
glcm = graycomatrix(patch, distances=[1], angles=[0], levels=256)
3
contrast = graycoprops(glcm, 'contrast')

应用：织物分类、遥感、医学病理。

11.8.3 LBP (Local Binary Pattern)#

Ojala 1996，极简但强大。

对每像素：

1
3×3 邻域:            二值化 (> 中心):        按顺时针转 8 位:
2
70  90  85           0  1  1
3
40  60  45    →      0  ★  0    →      01100010   → 十进制 98
4
55  30  25           0  0  0

LBP 直方图：256 bin（8 位），作为纹理特征向量。

改进：

• Uniform LBP：只考虑 “至多两次 0-1 跃迁” 的模式（涵盖 90% 自然纹理）
• Rotation-Invariant LBP：取 8 种旋转中字典序最小
• 多尺度 LBP：不同半径

应用：人脸识别、表情识别、动态纹理。

11.8.4 Gabor 滤波器#

[ G(x, y; \lambda, \theta, \psi, \sigma, \gamma) = \exp\left(-\frac{x’^2 + \gamma^2 y’^2}{2 \sigma^2}\right) \cos\left(\frac{2\pi x’}{\lambda} + \psi\right) ]

(x’, y’) 是沿 (\theta) 方向旋转后的坐标。

直觉：局部化的正弦波。模仿人类视觉皮层 V1 层简单细胞。

不同 (\lambda, \theta) 组合的 Gabor 滤波器排成一个 filter bank，对图像响应构成多通道特征。

与小波的关系：Gabor = 高斯 × 正弦，是连续小波变换的实例之一。

11.9.1 几何矩#

[ m_{pq} = \sum_x \sum_y x^p y^q f(x, y) ]

• (m_{00})：面积
• (m_{10}/m_{00}, m_{01}/m_{00})：重心
• 二阶矩：方向椭圆

中心矩： [ \mu_{pq} = \sum (x - \bar{x})^p (y - \bar{y})^q f(x, y) ] → 平移不变

归一化中心矩： [ \eta_{pq} = \mu_{pq} / \mu_{00}^{(p+q)/2 + 1} ] → 尺度不变

11.9.2 Hu 不变矩（7 个）#

由 (\eta_{pq}) 组合出的 7 个不变量，满足平移、尺度、旋转不变。部分对翻转也不变。

[ \phi_1 = \eta_{20} + \eta_{02} ] [ \phi_2 = (\eta_{20} - \eta_{02})^2 + 4 \eta_{11}^2 ] …（共 7 个）

1
moments = cv2.moments(binary)
2
hu = cv2.HuMoments(moments).flatten()

应用：形状识别（数字、符号、简笔画）。

11.9.3 傅里叶描述子#

轮廓 ({(x_k, y_k)}) 看成复数序列 (z_k = x_k + j y_k)，DFT： [ Z_n = \sum_k z_k e^{-j 2\pi n k / N} ]

• (Z_0)：重心（去平移）
• (|Z_1|)：尺度
• (Z_n) 相位：旋转

保留前几个低频 (Z_n) → 压缩形状描述（自然形状主要在低频）。

11.9.4 链码 (Chain Code)#

记录轮廓沿 4/8 方向的走势：

1
 0 1 2
2
 7 ★ 3
3
 6 5 4

轮廓 → 方向码序列。Freeman 链码经典。

11.9.5 基本形状量#

• 周长 (P)、面积 (A)
• 圆度 (Circularity)：(4 \pi A / P^2)（圆 = 1）
• 矩形度：(A / A_{\text{bbox}})
• 凸度：(A / A_{\text{convex hull}})
• 长宽比、实心度 (Solidity)

11.10.1 流程#

1
1. Gamma 归一化
2
2. 计算梯度 g_x, g_y, 幅值 M, 方向 θ
3
3. 分 cells (8×8)，每 cell 内建 9 bin 方向直方图（按 M 加权）
4
4. 分 blocks (2×2 cells)，L2 归一化
5
5. 滑动 block 拼接所有直方图 → 特征向量

对一张 64×128 行人图，HOG 向量维度 3780。

11.10.2 用途#

• HOG + SVM = 行人检测（2005-2012 业界标杆）
• 车辆、人脸检测（Viola-Jones 后续）
• 与 SIFT 的差别：HOG 面向整图分类（固定尺寸模板），SIFT 面向局部匹配

1
hog = cv2.HOGDescriptor()
2
hog.setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())
3
rects, weights = hog.detectMultiScale(img)

11.11.1 问题#

视频中相邻帧之间，像素怎么运动？

光流 (Optical Flow) ((u, v))：每个像素的位移向量。

11.11.2 亮度恒常假设#

[ I(x, y, t) = I(x + u dt, y + v dt, t + dt) ]

一阶泰勒： [ I_x u + I_y v + I_t = 0 ]

一个方程两个未知 → 孔径问题 (Aperture Problem)：只能恢复沿梯度方向的分量。

11.11.3 Lucas-Kanade（1981）#

假设：小邻域 (W) 内 ((u, v)) 相同。

对 (W) 内每点写方程组： [ \begin{bmatrix} I_{x1} & I_{y1} \ \vdots & \vdots \ I_{xn} & I_{yn} \end{bmatrix} \begin{bmatrix} u \ v \end{bmatrix} = -\begin{bmatrix} I_{t1} \ \vdots \ I_{tn} \end{bmatrix} ]

最小二乘： [ \begin{bmatrix} u \ v \end{bmatrix} = (A^T A)^{-1} A^T b ]

其中 (A^T A = M) 就是 Harris 结构张量！特征值大（角点）的点最适合光流跟踪——所以常称为 “good features to track” + LK 流。

1
p_new, status, err = cv2.calcOpticalFlowPyrLK(prev, curr, p_prev, None)

11.11.4 稠密光流#

LK 只在稀疏角点处估计。稠密光流（每像素）：

• Horn-Schunck（1981）：变分框架
• Farnebäck（2003）：基于多项式展开
• FlowNet / RAFT（深度学习）：当前 SOTA

1
flow = cv2.calcOpticalFlowFarneback(prev, curr, None, 0.5, 3, 15, 3, 5, 1.2, 0)
2
# flow.shape = (H, W, 2)

应用：

• 视频稳像
• 视频插帧
• 动作识别
• SLAM 跟踪

11.12.1 单应 (Homography)#

两张同一平面（或纯旋转下）的图像间的 (3 \times 3) 变换： [ \begin{bmatrix} x’ \ y’ \ 1 \end{bmatrix} \sim H \begin{bmatrix} x \ y \ 1 \end{bmatrix} ]

8 自由度（9 个元素减 1 尺度）。4 对点即可求解。

1
H, mask = cv2.findHomography(pts1, pts2, cv2.RANSAC)
2
warped = cv2.warpPerspective(img1, H, (w, h))

11.12.2 本质矩阵 E、基础矩阵 F#

对一般（非平面）场景的立体对： [ x’^T F x = 0 \quad \text{（极线约束）} ]

• F（基础矩阵）：像素坐标系
• E（本质矩阵）：归一化坐标系，(E = K’^T F K)

用途：从 E 可分解出相机相对旋转 (R) 和平移 (t)（相差尺度）。

1
E, mask = cv2.findEssentialMat(pts1, pts2, K)
2
_, R, t, _ = cv2.recoverPose(E, pts1, pts2, K)

11.12.3 三角化与 3D 重建#

已知两相机位姿 + 匹配点 → 求 3D 点坐标： [ X = \arg\min |x - P X|^2 + |x’ - P’ X|^2 ]

线性法（DLT）+ 非线性细化（Bundle Adjustment）。

应用：SLAM、SfM（Structure from Motion）、3D 建模。

11.12.4 全景拼接完整流程#

1
1. 读两张图 A, B
2
2. 各自提取 SIFT/ORB 特征
3
3. 特征匹配 (BF + Lowe Ratio)
4
4. RANSAC 估 Homography
5
5. 把 B 投影到 A 坐标系 (warpPerspective)
6
6. 融合（羽化/Laplacian 金字塔）
7
7. 输出拼接图

OpenCV 的 cv2.Stitcher 一键完成。

11.13.1 内参与外参#

相机模型： [ s \begin{bmatrix} u \ v \ 1 \end{bmatrix} = K [R | t] \begin{bmatrix} X \ Y \ Z \ 1 \end{bmatrix} ]

• K：内参（焦距 (f_x, f_y)、主点 (c_x, c_y)）
• [R | t]：外参（世界到相机的变换）

11.13.2 张正友法（2000）#

用棋盘格拍多张，每张给出 3D-2D 对应：

1
ret, K, dist, rvecs, tvecs = cv2.calibrateCamera(obj_pts, img_pts, size, None, None)

输出 K 和畸变系数，可用于 cv2.undistort 做畸变校正（回顾第 5 章）。

✅ 必须掌握#

• Harris 结构张量 (M) 及其特征值意义
• FAST / ORB 快速检测的加速技巧
• SIFT 四步流程（尤其方向分配和 128 维描述子）
• Lowe’s ratio test
• 汉明距离 vs L2 距离（对应二进制 / 浮点描述子）
• RANSAC 原理与迭代次数公式
• LBP 编码规则
• Hu 不变矩
• HOG 流程（Cell / Block / 归一化）
• LK 光流与孔径问题
• 单应 H 的 4 点求解

💡 高频面试题#

Q1. Harris 角点响应函数为什么是 (\det(M) - k \text{tr}(M)^2)？

答：

• 角点 = (\lambda_1, \lambda_2) 都大
• (\det = \lambda_1 \lambda_2)（都大才大）
• (\text{tr} = \lambda_1 + \lambda_2)（一大一小也大）
• (\det - k \text{tr}^2) 在两者都大时才大，平坦/边缘都小。避免了直接特征分解，计算快。

Q2. SIFT 为什么用 DoG 而不是 LoG？

答：(\text{DoG} = G_{k\sigma} - G_\sigma \approx (k - 1)\sigma^2 \nabla^2 G)（一阶近似 LoG）。DoG 只需两次高斯卷积相减，计算量小，在尺度金字塔上几乎”免费”。

Q3. Lowe’s ratio test 的思想？

答：对每个查询描述子，在目标图像中找最近 (d_1) 与次近 (d_2)。若 (d_1 / d_2 > 0.75)，说明最近和次近太接近（歧义），可能是错误匹配 → 丢弃。这个经验阈值使 90% 正确匹配被保留、90% 错误匹配被剔除。

Q4. RANSAC 迭代多少次合适？

答：取决于期望置信度 (p)、内点率 (w)、每次采样大小 (s)： [N \ge \log(1 - p) / \log(1 - w^s)] 例：求单应 (s=4, w=0.5, p=0.99) → (N \approx 72) 次。

Q5. 为什么 ORB 比 SIFT 快这么多？

答：

1. FAST 检测（圆 16 点试验）代替 DoG 金字塔（多尺度卷积）
2. 二进制 BRIEF 描述子（256 bit）代替 128 维浮点
3. 匹配用汉明距离（XOR + popcount，硬件指令）

Q6. 光流的孔径问题？

答：亮度恒定给出一个方程 (I_x u + I_y v + I_t = 0)，两个未知数。单个像素只能恢复沿梯度方向的分量，沿边缘的运动不可观测。解决：用邻域所有点联立（Lucas-Kanade），角点处邻域梯度方向丰富 → 可解。

Q7. HOG 和 SIFT 的区别？

答：

• 目的：HOG 面向整图分类（固定模板滑窗）；SIFT 面向关键点匹配
• 结构：HOG 是网格的 8×8 cells；SIFT 是关键点周围 16×16 分成 4×4 子块
• 维度：HOG 几千（整图）；SIFT 128 / 关键点
• 不变性：SIFT 尺度/旋转都做对齐；HOG 不做（依赖滑窗解决）

Q8. 特征匹配出现大量错误怎么办？

答：

1. Lowe ratio test（第一道过滤）
2. Cross-check（双向最近）
3. RANSAC + 几何模型（单应或基础矩阵）
4. 最后用 inliers 重新估计模型

Q9. LBP 为什么鲁棒？

答：LBP 只比较相对大小（是否 > 中心），对整体亮度/对比度变化不敏感，具有单调光照不变性。同时 256 维直方图保留统计结构。