基于稀疏编码的线性空间金字塔匹配ScSPM实现

资 源 简 介

该项目是对CVPR 2009经典论文Linear Spatial Pyramid Matching using Sparse Coding for Image Classification中ScSPM算法的MATLAB语言实现。其核心任务是改进图像分类中的特征提取与表示流程，将传统的基于矢量量化（VQ）的空间金字塔匹配方法替换为稀疏编码（Sparse Coding）框架。功能上，程序首先对输入的图像进行密集SIFT特征提取，随后利用坐标下降法或预定义的算法学习过完备字典，将每个局部描述子投影为稀疏线性组合

详 情 说 明

基于稀疏编码的线性空间金字塔匹配算法 (ScSPM)

项目介绍

本项目是针对经典计算机视觉论文 Linear Spatial Pyramid Matching using Sparse Coding for Image Classification (CVPR 2009) 的 MATLAB 算法实现。ScSPM 算法是对传统空间金字塔匹配 (SPM) 的重要改进，它将矢量量化 (VQ) 编码替换为稀疏编码 (Sparse Coding)，并采用最大池化 (Max Pooling) 代替传统的平均池化或直方图统计。

这种改进使得算法能够更精确地捕捉局部图像特征的显著性，并允许直接使用线性分类器处理高维特征，在保持极高分类准确率的同时，大幅降低了大规模图像分类任务中的计算开销。

功能特性

1. 稀疏表示框架：采用稀疏编码技术将局部特征向量投影到过完备字典上，获取比传统硬分配更丰富的特征描述。
2. 空间布局建模：实现多尺度空间金字塔结构（1x1, 2x2, 4x4），有效捕捉图像的全局与局部空间几何信息。
3. 最大池化机制：在金字塔每一层的网格内利用最大池化统计稀疏响应，增强了特征对微小位移和形变的鲁棒性。
4. 线性高效分类：生成的 ScSPM 特征由于具有高度线性可分性，可直接配合线性岭回归或线性 SVM 分类器使用。
5. 完整 Pipeline 实现：涵盖了从模拟数据生成、字典训练到特征提取、编码、聚合及最终评估的全流程。

系统要求

1. 运行环境：MATLAB R2016b 或更高版本。
2. 核心依赖：无需第三方工具箱，仅需 MATLAB 基础数学运算库。

实现逻辑说明

程序的执行逻辑严格遵循 ScSPM 论文的核心架构，分为以下六个阶段：

1. 模拟数据集准备：程序首先生成一个包含多类别的合成数据集。每一类图像通过特定的正弦纹理函数产生，模拟真实场景中不同类别的视觉模式。

1. 密集特征提取：对输入图像进行滑动窗口式采样。计算每个补丁 (Patch) 的梯度方向直方图，生成类似 SIFT 的描述子。逻辑上将 Patch 划分为 4x4 的单元格，并计算 8 个方向的梯度权重累加，最后进行 L2 归一化。

1. 过完备字典训练：从训练集中随机抽取特征点，利用坐标下降法 (Coordinate Descent) 交替更新稀疏系数和字典基原子。字典更新阶段采用逐列残差法，并对每个原子进行单位长度正则化，确保学习到的基向量能有效重构原始特征。

1. 稀疏编码求解：对于每一张图像的每一个局部描述子，通过坐标下降法解决 Lasso 问题（含 L1 正则化的最小二乘法）。该过程将 128 维的特征投影为对应字典大小的稀疏系数向量。

1. 空间金字塔最大池化：这是 ScSPM 的核心步骤。程序将图像划分为三个层级（1x1, 2x2, 4x4，共 21 个子区域）。在每个子区域内，对所有稀疏编码取绝对值的最大值，形成该区域的特征表达。最后将所有区域的特征拼接并进行全局归一化。

1. 分类与评估：使用 One-vs-All 策略训练线性分类器。通过正则化线性岭回归求解权重矩阵，对测试集进行预测，并输出最终的准确率和混淆矩阵可视化图表。

算法细节分析

一、密集 SIFT 模拟逻辑 本实现通过计算图像梯度场并进行空间加权，模拟了密集 SIFT 提取。相比于传统的单点特征，这种密集提取方式配合 4 像素间距的网格，能为后续的稀疏编码提供充足的样本分布。

二、坐标下降法 (Coordinate Descent) 在稀疏编码和字典更新中均采用了坐标下降策略。在求解 Lasso 问题时，程序通过软阈值算子逐个更新系数分量，这种方法在处理大规模稀疏优化问题时具有极高的收敛效率和数值稳定性。

三、最大池化的数学优势 与传统直方图统计不同，代码中实现的 max(abs(codes), [], 2) 操作能够筛选出在该区域内对特定视觉单词响应最强的特征。这种非线性聚合方式极大地弥补了稀疏编码在量化过程中的信息损失。

四、线性回归分类器 利用 (X'X + lambda*I) X'Y 的闭式解快速训练多分类模型。这种线性分类方法在处理由 ScSPM 生成的高维特征（如 120原子 * 21区域 = 2520维）时，计算速度远快于非线性核函数分类器。

使用方法

1. 启动 MATLAB 并进入项目所在文件夹。
2. 直接在命令行输入主程序入口函数名称。
3. 程序将依次在命令行显示执行进度：从初始化数据、特征提取、字典训练，到最后的特征池化与分类。
4. 运行结束后，程序会自动弹出一个 figure 窗口，展示分类的混淆矩阵以及最终的百分比准确率。
5. 如需调整模型性能，可修改函数内部的字典大小 (dict_size)、稀疏系数 (lambda) 或金字塔层级 (pyramid_levels) 参数。