基于局部约束线性编码的图像分类系统

资 源 简 介

本项目主要实现了一种高效的图像特征编码方法——局部性约束线性编码（Locality-constrained Linear Coding, LLC），并将其应用于图像分类任务。LLC可以被视为局部坐标编码（LCC）的快速近似实现，它通过利用局部坐标系将每个视觉描述符投影到局部流形上，强制该描述符仅由其特征空间中的K个最近邻基底表示，从而引入了局部性约束。该项目的功能涵盖了完整的图像分类管道：首先进行图像底层特征（如SIFT）的提取；其次利用聚类算法（如K-means）生成视觉词典；然后应用核心的LLC算法进行特征编码，LLC通过解析解直接求解优化问题，避免了传统稀疏编码中昂贵的迭代计算，将每个描述符的计算复杂度降低至O(M+K)级别；接着采用空间金字塔匹配（SPM）结合最大池化（Max Pooling）策略汇聚生成图像的最终特征表示；最后使用线性支持向量机（Linear SVM）完成分类预测。该系统验证了LLC在保持计算高效性的同时，能够生成具有高判别力的特征表示，配合线性分类器即可获得令人印象深刻的分类精度。

详 情 说 明

项目：基于局部性约束线性编码(LLC)的图像分类系统

项目介绍

本项目是一个完整的图像分类系统 MATLAB 实现，核心算法基于局部性约束线性编码（Locality-constrained Linear Coding, LLC）。LLC 是一种高效的图像特征编码方法，它利用局部坐标系将每个视觉描述符投影到局部流形上，仅使用 K 个最近邻基底来表示特征，从而在保持高判别力的同时显著降低了计算复杂度。

该项目不仅仅是一个算法的实现，更是一个包含数据生成、特征提取、字典学习、特征编码、空间汇聚和分类预测的全流程演示系统。代码设计为自包含（Self-contained），无需外部数据集，直接运行即可通过模拟数据验证算法的有效性。

功能特性

• 全流程管道：涵盖从图像生成、特征提取、字典构建、编码池化到分类评估的完整计算机视觉任务流程。
• 模拟数据生成：内置数据生成模块，自动生成包含不同纹理和几何特征（水平纹理、垂直纹理、圆形）的合成图像数据集，无需下载 Caltech-101/256 等大型数据集即可运行。
• 密集特征提取：实现基于网格的密集采样（Dense Sampling），提取模拟 SIFT/HOG 的梯度幅值特征。
• 高效 LLC 编码：使用解析解（Analytical Solution）直接求解局部约束优化问题，避免了稀疏编码中耗时的 L1 范数迭代优化。
• 空间金字塔匹配（SPM）：结合 Max Pooling 策略，利用空间金字塔结构（1x1 和 2x2 层级）捕捉图像的空间布局信息。
• 线性 SVM 分类：使用多类线性支持向量机完成最终的分类任务。
• 可视化评估：提供混淆矩阵图表和基于 PCM 降维的字典基底可视化演示。

系统要求

• MATLAB：推荐 R2018b 或更高版本。
• Statistics and Machine Learning Toolbox：用于 K-Means 聚类 (kmeans)、SVM 训练 (fitcecoc) 和 PCA 分析 (pca)。

使用方法

1. 确保 MATLAB 路径中包含 main.m 文件。
2. 直接运行 main 函数。
3. 系统将自动执行以下步骤：

* 生成模拟训练集和测试集。 * 提取特征并学习视觉词典。 * 执行 LLC 编码和 SPM 池化。 * 训练 SVM 模型并预测。 * 输出分类准确率并在新窗口显示混淆矩阵。

代码实现详解 (基于 main.m)

main.m 文件集成了系统的所有功能模块，以下是其内部逻辑和关键算法的详细分析：

1. 参数初始化

系统首先定义了关键超参数：

• KNN (K=5)：LLC 编码中使用的最近邻个数。
• Codebook Size (M=50)：视觉词典的大小（聚类中心数）。
• Pyramid Levels：空间金字塔层级，设置为 [1, 2]，即全图（1x1）和四分格（2x2）。
• Grid Spacing/Patch Size：密集采样的步长（8像素）和块大小（16像素）。

2. 数据准备 (generate_synthetic_dataset)

代码没有读取外部文件，而是通过 generate_synthetic_dataset 函数动态生成数据。

• 生成 3 类图像：水平条纹 (Horz)、垂直条纹 (Vert)、圆形/高斯块 (Circ)。
• 每类包含 30 张训练图像和 10 张测试图像。
• 图像加入随机噪声以增加分类难度，并归一化到 [0, 1] 区间。

3. 特征提取 (extract_dense_descriptors)

模拟了经典的 Dense SIFT 提取过程：

• 在图像上按固定步长（Grid Spacing）滑动窗口。
• 对于每个 16x16 的 patch，计算简单的梯度幅值（Gradient Magnitude）。
• 将特征展平并进行 L2 归一化，生成描述符向量。
• 同时记录每个描述符的 (x, y) 坐标，用于后续的空间金字塔匹配。

4. 视觉词典生成 (K-Means)

• 为了提高速度，从所有训练图像的描述符中随机抽取一部分样本。
• 调用 MATLAB 内置的 kmeans 函数对样本进行聚类，生成大小为 50 的视觉词典（Dictionary）。

5. LLC 编码与 SPM 池化 (compute_llc_spm)

这是本系统的核心部分，包含两个连续步骤：

#### A. LLC 编码 (llc_coding_core) 实现了 LLC 论文中的核心算法：

1. KNN 搜索：计算当前描述符与词典中所有基底的欧氏距离，找到最近的 K 个基底。
2. 构建局部协方差矩阵：计算偏移矩阵的协方差 $C = (B - x)(B - x)^T$。
3. 正则化与求解：为了数值稳定性，对 C 加上正则项 ($lambda cdot trace(C) cdot I$)，然后解析求解线性方程组 $Ccdot w = mathbf{1}$。
4. 归一化：对权重向量 $w$ 进行归一化 ($w / sum w$)，保持仿射不变性。编码结果是稀疏的，只有 K 个非零值。

#### B. SPM 池化 (spm_pooling) 利用特征的空间分布增强判别力：

1. 网格划分：根据 Level 1 (1x1) 和 Level 2 (2x2) 将图像划分为不同的空间区域。
2. 最大池化 (Max Pooling)：在每个网格区域内，提取落入该区域的所有描述符的 LLC 编码，计算每一维度的最大绝对值。相比平均池化，最大池化对稀疏编码特征更鲁棒。
3. 特征拼接：将不同层级、不同网格的特征串联，形成最终的长特征向量。
4. 最终归一化：对拼接后的特征向量进行 L2 归一化。

6. SVM 分类器 (fitcecoc)

• 使用 fitcecoc 函数构建多类分类器（基于 One-vs-One 策略）。
• 内部使用线性学习器模板 (templateLinear)，求解器指定为 sparsa (Sparse Reconstruction by Separable Approximation)，并使用 Lasso 正则化，适合处理高维稀疏特征。

7. 评估与可视化

• 使用训练好的模型对测试集特征进行预测。
• 计算总体准确率并打印。
• 绘制 混淆矩阵 (Confusion Matrix)，直观展示各类别的分类性能。
• 演示可视化 (visualize_demo)：展示一张测试图像，并利用 PCA 将高维词典投影到 3D 空间进行可视化，展示特征空间的分布情况。

总结

该代码通过纯 MATLAB 实现展示了现代图像分类中的经典 "Feature Extraction -> Coding -> Pooling -> Classification" 架构。其中 LLC 算法通过利用特征的局部性，在保证分类精度的同时，极大地提升了编码速度，非常适合作为理解稀疏编码和局部约束编码机制的学习范例。