一、传统ML基础

1.1 核心算法概览

算法	类型	CV应用	特点
kNN	监督-分类/回归	图像分类(简单)	无训练，需存储所有样本
SVM ⭐	监督-分类	行人检测/HOG分类	小样本强，核函数强大
决策树/RF	监督-分类/回归	特征选择/人脸检测	集成学习，抗过拟合
K-Means	无监督-聚类	图像分割/特征量化	简单但需指定K
GMM	无监督-聚类	背景建模/运动分割	软聚类
PCA	无监督-降维	人脸识别(Eigenface)	线性降维最佳
LDA	监督-降维	FisherFace	有监督降维
t-SNE	无监督-降维	特征可视化	非线性可视化
HMM	时序模型	动作识别/手势	时间序列建模
CRF	结构化预测	图像分割	上下文建模

1.2 SVM (支持向量机) ⭐⭐⭐

核心思想: 找到最大间隔超平面

        原始空间              核空间(高维)
     ───●───●─○──       φ(●) ● ●     φ(○) ○
     ──●──○─────    →    ─────────    ────────
        ○──○───              ● ●        ● ○
     (不可分)           (线性可分)

核函数:

核	公式	参数	特点
线性	K(x,y) = x·y	-	无映射，快速
多项式	K(x,y) = (x·y + c)^d	c, d	有限维度映射
RBF	K(x,y) = exp(-γ)		x-y
Sigmoid	K(x,y) = tanh(a(x·y)+b)	a, b	类似神经网络

from sklearn import svm

# HOG + SVM 行人检测
clf = svm.SVC(kernel='rbf', C=1.0, gamma='scale')
clf.fit(X_train, y_train)

# OpenCV 内置 SVM + HOG
hog = cv2.HOGDescriptor()
hog.setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())

1.3 K-Means 与 图像量化

# 颜色量化 (压缩)
Z = img.reshape((-1, 3))  # RGB像素作为特征
Z = np.float32(Z)
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
_, labels, centers = cv2.kmeans(Z, K=16, None, criteria, 10, cv2.KMEANS_RANDOM_CENTERS)
centers = np.uint8(centers)
res = centers[labels.flatten()]
quantized = res.reshape((img.shape))

特征量化: K-Means构建视觉词典 (Bag-of-Visual-Words)

SIFT特征 → K-Means → 视觉单词(Codebook) → 直方图 = 每张图表示
   N×128       K=1000        1000个中心           1×1000

1.4 PCA (主成分分析) ⭐

本质: 找到数据方差最大的方向（特征向量）

输入: X (N×D, N个D维样本)
中心化: X̃ = X - μ
协方差: C = X̃ᵀX̃ / (N-1)  (D×D)
SVD:   C = UΣUᵀ
投影: Y = X̃ · Uₖ           (降维到k维)

# Eigenface 人脸识别
from sklearn.decomposition import PCA
pca = PCA(n_components=100)  # 降到100维
X_pca = pca.fit_transform(X)
# explained_variance_ratio_ 查看信息保留比例

1.5 Bag of Visual Words (BoVW)

流程: 图像 → 特征提取(SIFT) → 词典构建(K-Means) → 量化 → 直方图 → SVM分类

图像1: {SIFT₁, SIFT₂, ..., SIFTᵢ}  →  [2, 0, 1, ..., 5]   SVM → 类别A
图像2: {SIFT₁, SIFT₂, ..., SIFTⱼ}  →  [0, 3, 0, ..., 1]   SVM → 类别B
                    │                        ↑
              K-Means (K=500)          空间金字塔
              视觉词典                     (SPM)

---

二、传统视觉应用

2.1 人脸检测 - Viola-Jones

论文: Rapid Object Detection using a Boosted Cascade of Simple Features (2001)
开创性: 第一个实现实时人脸检测

三大创新:

1. Haar-like特征（矩形特征，积分图加速）
2. AdaBoost（级联弱分类器）
3. 级联结构（逐级过滤背景）

Haar特征:
     ████░     ██░░     ██░█░     █░░░
     ████░     ██░░     ░░██░     ██░░
     (边缘)  (水平)  (中心)  (对角线)

级联检测: 输入 → C1 → C2 → C3 → ... → 目标
                     ↓回绝检测    ↑ 每一级拒绝大部分背景

face_cascade = cv2.CascadeClassifier(cv2.data.haarcascades + 'haarcascade_frontalface_default.xml')
faces = face_cascade.detectMultiScale(gray, scaleFactor=1.1, minNeighbors=5, minSize=(30,30))

2.2 行人检测 - HOG + SVM（2.1节已详述）

2.3 图像检索

Pipeline:

查询图像 → 特征提取(SIFT/VLAD) → 特征向量 → 相似度搜索(余弦距离) → 排序结果

大规模检索: VLAD (Vector of Locally Aggregated Descriptors)

• 比BoVW更紧凑
• 存储每个视觉单词的残差和
• 配合近似最近邻搜索 (FLANN/IVF)

2.4 背景建模

方法	原理	适用场景
帧差法		frame(t) - frame(t-1)
MOG/MOG2	高斯混合模型建模像素	动态背景（树/水）
KNN	核密度估计	更鲁棒的背景建模
GMG	贝叶斯推断	快速初始化

backSub = cv2.createBackgroundSubtractorMOG2(history=500, varThreshold=16, detectShadows=True)

2.5 光流 (经典方法)

方法	类型	特点
Lucas-Kanade	稀疏	跟踪特征点，假设小运动
Horn-Schunck	稠密	全局平滑约束
Farneback	稠密	多项式展开，OpenCV实现

# Lucas-Kanade 稀疏光流
lk_params = dict(winSize=(15,15), maxLevel=2,
                 criteria=(cv2.TERM_CRITERIA_EPS|cv2.TERM_CRITERIA_COUNT, 10, 0.03))
p1, st, err = cv2.calcOpticalFlowPyrLK(old_gray, gray, p0, None, **lk_params)

# Farneback 稠密光流
flow = cv2.calcOpticalFlowFarneback(prev, next, None, 0.5, 3, 15, 3, 5, 1.2, 0)

---

三、特征选择与评估

方法	原理	特点
Filter	统计指标(卡方/互信息)	独立于分类器
Wrapper	RFE(递归消除)	依赖分类器
Embedded	Lasso/Ridge	训练时选择

# 卡方检验特征选择
from sklearn.feature_selection import SelectKBest, chi2
selector = SelectKBest(chi2, k=100)
X_selected = selector.fit_transform(X, y)

---

📺 推荐视频

内容	链接
李航《统计学习方法》讲解	B站搜索
SVM详解 (StatQuest)	https://www.youtube.com/watch?v=efR1C6CvhmE
PCA主成分分析 (StatQuest)	https://www.youtube.com/watch?v=FgakZw6K1QQ
Viola-Jones人脸检测	https://www.youtube.com/watch?v=uEJ71VlVmMQ
Bag of Visual Words	https://www.youtube.com/watch?v=uxkhqPBIQ5Y

📚 推荐书籍

书名	作者	说明
统计学习方法 (第2版)	李航	经典ML必读
The Elements of Statistical Learning (ESL)	Hastie et al.	统计ML标准教材
Pattern Recognition and Machine Learning (PRML)	Bishop	概率视角ML
Machine Learning: A Probabilistic Perspective	Murphy	全面系统
Computer Vision: Algorithms and Applications	Szeliski (第14-15章)	CV中的ML应用

---

附录：深层补充

1. SVM完整数学推导

1.1 硬间隔SVM（从原始问题到对偶问题的KKT推导）

原始问题：给定线性可分的数据 $\{(x_i,y_i){\}}_{i=1}^N$， y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1}，寻找最大间隔超平面 $w^{T}x+b=0$。

几何间隔：点 $x_i$ 到超平面的距离为 $\frac{y_i(w^T{x}_i+b)}{\Vert w\Vert }$。

优化问题（最大化最小几何间隔）：
$$\underset{w,b}{\max }\frac{1}{\Vert w\Vert }\underset{i}{\min }{y}_i(w^T{x}_i+b)$$

令 ${\min }_i{y}_i(w^T{x}_i+b)=1$，转化为等价形式：
$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{s.t.}{y}_i(w^T{x}_i+b)\ge 1,\forall i$$

Lagrange函数：引入 ${\alpha }_i\ge 0$：
$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^N{\alpha }_i[y_i(w^T{x}_i+b)-1]$$

KKT条件：

1. 平稳性：$\frac{\partial L}{\partial w}=0\Rightarrow w=\sum {\alpha }_i{y}_i{x}_i$，$\frac{\partial L}{\partial b}=0\Rightarrow \sum {\alpha }_i{y}_i=0$
2. 原始可行：$y_i(w^T{x}_i+b)-1\ge 0$
3. 对偶可行：${\alpha }_i\ge 0$
4. 互补松弛：${\alpha }_i[y_i(w^T{x}_i+b)-1]=0$

对偶问题：代入KKT条件消除 $w,b$：
$$\underset{\alpha }{\max }\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$
$$\text{s.t.}\sum {\alpha }_i{y}_i=0,{\alpha }_i\ge 0$$

支持向量：只有 ${\alpha }_i>0$ 的样本才是支持向量（在间隔边界上）。

决策函数：
$$f(x)=\text{sign}\left(\sum _{i\in SV}{\alpha }_i{y}_i{x}_i^{T}x+b\right)$$

1.2 软间隔SVM（松弛变量 $\xi$）

当数据不完全线性可分时，允许部分样本违反间隔约束：

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i$$
$$\text{s.t.}{y}_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\forall i$$

其中 $C$ 是惩罚参数（$C\to \infty$ 退化为硬间隔）。

对偶形式：
$$\underset{\alpha }{\max }\sum {\alpha }_i-\frac{1}{2}\sum \sum {\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$
$$\text{s.t.}\sum {\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$$

1.3 核函数与SMO算法

核技巧：将 $x_i^T{x}_j$ 替换为 $K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$。

核	公式
线性核	$K(x_i,x_j)=x_i^T{x}_j$
多项式核	$K=(x_i^T{x}_j+c{)}^d$
RBF核	$K=\exp (-\gamma |x_i-x_j{|}^2)$
Sigmoid核	$K=\tanh (a{x}_i^T{x}_j+b)$

SMO（Sequential Minimal Optimization）：每次选择两个$\alpha$ 优化（因 $\sum {\alpha }_i{y}_i=0$ 约束），有解析解。收敛 $O(N^2)-O(N^{2.3})$。

---

2. K-Means与GMM深入对比

2.1 K-Means的EM视角

K-Means是GMM的极限情况（$\sigma \to 0$）。

E步（分配中心）：$c_i=\arg {\min }_k\Vert x_i-{\mu }_k{\Vert }^2$（硬分配）
M步（更新中心）：${\mu }_k=\frac{1}{N_k}{\sum }_{i:c_i=k}{x}_i$

数学实质：最小化总类内平方和 $J={\sum }_{k=1}^K{\sum }_{i\in C_k}\Vert x_i-{\mu }_k{\Vert }^2$

2.2 GMM（高斯混合模型）

模型：$p(x)={\sum }_{k=1}^K{\pi }_k\mathcal{N}(x|{\mu }_k,{\Sigma }_k)$，$\sum {\pi }_k=1$。

E步（责任度）：${\gamma }_{ik}=\frac{{\pi }_k\mathcal{N}(x_i|{\mu }_k,{\Sigma }_k)}{{\sum }_{j=1}^K{\pi }_j\mathcal{N}(x_i|{\mu }_j,{\Sigma }_j)}$（软分配）

M步（更新）：${\mu }_k=\frac{{\sum }_i{\gamma }_{ik}{x}_i}{{\sum }_i{\gamma }_{ik}}$，${\pi }_k=\frac{{\sum }_i{\gamma }_{ik}}{N}$

2.3 BIC/AIC选择K值

AIC $=2k-2\ln (L)$，BIC $=k\ln (N)-2\ln (L)$。选择最小值对应的K。

---

3. PCA的完整数学推导

3.1 最大方差视角

PCA寻找第一个主轴的方向 $w_1$（$\Vert w_1\Vert =1$）以最大化投影方差：
$$\underset{w_1}{\max }\text{Var}(X{w}_1)=\underset{w_1}{\max }{w}_1^T\Sigma w_1$$
使用Lagrange：$\mathcal{L}=w_1^T\Sigma w_1-\lambda (w_1^T{w}_1-1)$
求导得：$\Sigma w_1=\lambda w_1$ → $w_1$ 是协方差矩阵的最大特征值对应的特征向量。

后续主成分依次为第2、第3大特征向量（正交约束下）。

3.2 最小重构误差视角

将数据投影到k维子空间后再重构，最小化重构误差：
$$\underset{W}{\min }\sum _i\Vert x_i-W{W}^T{x}_i{\Vert }^2$$

解同样为协方差矩阵的前k个特征向量。这两个视角等价。

3.3 SVD实现PCA

对中心化数据矩阵 $\tilde{X}\in {\mathbb{R}}^{N\times D}$ 做SVD：$\tilde{X}=U\Sigma V^T$

• 协方差矩阵：${\Sigma }_X=\frac{1}{N-1}{\tilde{X}}^T\tilde{X}=\frac{1}{N-1}V{\Sigma }^T\Sigma V^T$
• 主方向：$V$ 的列（右奇异向量）
• 投影：$Y=\tilde{X}{V}_k=U_k{\Sigma }_k$（降至k维）
• 方差占比：$\frac{{\sum }_{i=1}^k{\sigma }_i^2}{{\sum }_{i=1}^D{\sigma }_i^2}$

SVD方法的数值优势：比直接计算协方差矩阵的EVD更稳定，尤其当 $D\gg N$ 时。

3.4 核PCA（Kernel PCA）

将数据映射到高维空间再做PCA：$\varphi (x_i)\in \mathcal{F}$。

对映射后数据 $\Phi =[\varphi (x_1),...,\varphi (x_N)]$，协方差矩阵特征向量满足：$\Phi {\Phi }^{T}v=\lambda v$。

由表示定理：$v={\sum }_i{\alpha }_i\varphi (x_i)$。代入得：$K\alpha =\lambda \alpha$，其中 $K_{ij}=\varphi (x_i{)}^T\varphi (x_j)$。

---

4. Bag of Visual Words（BoVW）

4.1 完整流程

def bovw_pipeline(images, K=500):
    # Step 1: 特征提取（从每张图像提取SIFT描述子）
    sift = cv2.SIFT_create()
    all_descriptors = []
    for img in images:
        kp, des = sift.detectAndCompute(img, None)
        if des is not None:
            all_descriptors.append(des)
    all_des = np.vstack(all_descriptors)  # (N_total, 128)
    
    # Step 2: 码本构建（K-Means聚类生成视觉词汇）
    from sklearn.cluster import MiniBatchKMeans
    kmeans = MiniBatchKMeans(n_clusters=K, batch_size=10000)
    kmeans.fit(all_des)  # 学习K个码本中心
    codebook = kmeans.cluster_centers_  # (K, 128)
    
    # Step 3: 直方图编码（将每张图的特征量化为直方图）
    histograms = []
    for img_idx, des in enumerate(all_descriptors):
        if des is None:
            hist = np.zeros(K)
        else:
            assigned = kmeans.predict(des)
            hist = np.bincount(assigned, minlength=K)
        # 归一化（L1或L2）
        hist = hist.astype(float) / (np.linalg.norm(hist, 1) + 1e-10)
        histograms.append(hist)
    
    # Step 4: SVM分类
    from sklearn.svm import SVC
    clf = SVC(kernel='rbf', C=100, gamma='scale')
    clf.fit(np.array(histograms), labels)
    return clf, codebook

4.2 空间金字塔匹配（SPM）

Lazebnik et al., 2006。解决BoVW丢失空间信息的缺陷。

原理：将图像递归划分为更细的网格，在每个层次独立量化编码，最后拼接所有层次的直方图。

Level 0 (1×1):  [直方图(256D)]
Level 1 (2×2):  [直方图] [直方图]
                  [直方图] [直方图]
Level 2 (4×4):  [16个直方图]

最终向量 = [L0:256] + [L1:4×256] + [L2:16×256] = 21×256 = 5376D

金字塔匹配核：两个图像的特征向量在每层的匹配数为：
$${\mathcal{K}}^L(X,Y)=\sum _{l=0}^L\frac{1}{2^{L-l}}\cdot ({\mathcal{I}}^l-{\mathcal{I}}^{l-1})$$

其中 ${\mathcal{I}}^l$ 是第l层的匹配数。越精细的层权重越大。

---

5. HOG的完整实现细节

5.1 梯度计算

使用中心差分（1D离散导数的简单核 $[-1,0,1]$）：
$$G_x(x,y)=I(x+1,y)-I(x-1,y)$$
$$G_y(x,y)=I(x,y+1)-I(x,y-1)$$

幅值：$M(x,y)=\sqrt{G_x^2+G_y^2}$
方向：$\theta (x,y)=\arctan (G_y/G_x)$，$\theta \in [0^{\circ },180^{\circ })$（无符号梯度）

为什么用无符号梯度：Dalal & Triggs实验表明，$[0^{\circ },180^{\circ })$（9个bin）比$[0^{\circ },360^{\circ })$（18个bin）效果更好，因为行人轮廓的左右子对称性使得有符号方向意义不大。

5.2 Cell/Block划分

Cell（细胞单元）：8×8像素区域，每个cell生成9维直方图。

Block（块）：2×2 cells = 16×16像素区域，每个block生成36维特征。

Block步长：1个cell（8像素），与HOG检测窗口64×128对应：

• 水平方向：$(64/8-1)=7$ 个位置
• 垂直方向：$(128/8-1)=15$ 个位置
• 总block数：$7\times 15=105$
• 特征向量：$105\times 36=3780$ 维

5.3 归一化（L2-Hys）

Step 1：对block的36D向量做L2归一化：$v\leftarrow v/\sqrt{\Vert v{\Vert }_2^2+{ϵ}^2}$
Step 2：截断（clipping）：$v_i=\min (v_i,0.2)$（限制梯度幅值不能过大）
Step 3：再次L2归一化

为什么L2-Hys最好：截断操作使HOG对局部光照变化更鲁棒——强梯度不会过度主导整个block的归一化。

5.4 为什么HOG适合行人检测

1. 边缘形状描述：行人轮廓以垂直边缘为主（腿、手臂、躯干），HOG的cell直方图能捕捉方向分布
2. 局部对比度归一化：Block归一化使HOG对局部光照变化不敏感
3. 空间信息保留：不像BoVW丢失空间信息，HOG在各cell中保留位置
4. 多尺度检测：检测窗口滑动 + 图像金字塔
5. Dalal & Triggs实验：在INRIA行人数据集上达到接近100%的检测率（当时最优）

Dalal & Triggs的关键发现：筛选出的最佳参数组合

• 梯度方案：$[-1,0,1]$ 无符号梯度（> 有符号、高斯平滑方向）
• Cell大小：8×8（> 4×4或16×16）
• Block大小：2×2 cells（> 1×1或3×3）
• 归一化：L2-Hys（> L1-norm或L2-norm）
• 重叠：50% block重叠表现最好