高鲁棒性Normalized Cut图像分割与谱聚类算法实现

资 源 简 介

本项目实现了一个完整且高鲁棒性的Normalized Cut（归一化割）图像分割算法。程序基于图论和谱聚类思想，将图像分割问题转化为图的最优划分问题。系统首先根据像素点的亮度和空间位置信息构建加权无向图，计算像素间的相似度矩阵（Affinity Matrix）；随后构建对角度矩阵（Degree Matrix）和拉普拉斯矩阵，并通过求解广义特征值问题，获得用于分割的特征向量；最后利用K-Means等聚类算法在特征空间中完成对像素的归类，实现图像区域的精准分割。该程序经过长时间的深度调试与优化，代码结构极其清晰，逻辑严密，有效解决了传统实现中可能出现的数值不稳定和运算效率低的问题，能够准确地将图像中具有相似纹理或亮度的区域分离出来，适用于目标提取、背景分离及计算机视觉算法研究。

详 情 说 明

基于Normalized Cut的图像分割与谱聚类系统

项目介绍

本项目旨在提供一个完整、高鲁棒性的基于归一化割（Normalized Cut）的图像分割算法实现。项目利用图论和谱聚类思想，通过构建像素间的相似度图，将复杂的图像分割任务转化为求解图的最优划分问题。不同于简单的阈值分割或边缘检测，该系统能够综合利用图像的亮度、颜色信息以及空间位置信息，有效地将具有相似纹理或亮度的区域分离出来。

本程序经过深度调试与优化，采用稀疏矩阵运算大幅提升了计算效率，能够精准处理合成图像中的几何形状、重叠区域及噪声干扰，适用于目标提取、背景分离及计算机视觉算法研究。

功能特性

• 内置合成图像生成：程序不依赖外部图像文件，内置测试图像生成器，可自动产生包含几何形状（圆形、矩形）、颜色渐变、重叠区域及高斯噪声的复杂合成图像，便于即时验证算法效果。
• 高效的稀疏矩阵构建：针对谱聚类中Affinity Matrix（相似度矩阵）巨大的问题，采用基于邻域半径（Radius Neighbor）的稀疏矩阵构建策略，仅计算局部像素间的连接，极大地降低了内存消耗和计算复杂度。
• 多特征融合权重：相似度计算同时融合了颜色/亮度特征（Color Feature）和空间位置特征（Spatial Feature），通过高斯核函数加权，保证了分割结果在颜色一致性和空间连续性上的平衡。
• 数值稳定的拉普拉斯计算：实现了标准化的对称拉普拉斯矩阵（Normalized Symmetric Laplacian），有效解决了广义特征值求解过程中的数值不稳定问题。
• 完整的可视化流水线：提供从原始图像、Fiedler特征向量可视化、聚类分割结果到边界叠加的全流程展示。

系统要求

• MATLAB R2016a 或更高版本
• Image Processing Toolbox（图像处理工具箱）
• Statistics and Machine Learning Toolbox（统计与机器学习工具箱，用于K-Means）

使用方法

1. 直接在MATLAB环境中运行主程序。
2. 程序将自动执行以下流程：生成图像 -> 下采样 -> 构建图 -> 特征分解 -> 聚类 -> 显示结果。
3. 运行结束后，系统将弹出一个包含四个子图的窗口，分别展示原始输入、特征空间向量、最终分割色块图以及带有红色边界的叠加图。
4. 如需调整分割粒度，可修改代码顶部的 k 参数（默认为3类）。
5. 如需调整计算速度或精度，可修改 resize_dim 参数（默认64x64像素）。

核心算法与实现逻辑

本系统的核心代码逻辑包含严密的六大步骤，具体实现细节如下：

1. 图像预处理与特征提取

程序首先调用内部函数生成带有噪声的合成图像，随后为了克服谱聚类算法对图像尺寸极其敏感（计算复杂度随像素数呈立方级增长）的特性，将图像缩放至较小尺寸（如64x64）。 在此阶段，程序将图像数据归一化到 [0, 1] 区间，并分别提取两类特征：

• 颜色特征：将图像展平为 N x C 的矩阵，利用RGB通道数值。
• 空间特征：生成网格坐标矩阵，记录每个像素的 (x, y) 坐标。

2. 构建稀疏相似度矩阵 (Affinity Matrix)

这是算法最耗时的部分之一，本实现进行了专门优化：

• 程序不计算全连接图，而是遍历每个像素，仅搜索其空间半径 r（默认5）内的邻域像素。
• 权重计算：对于具有连接关系的像素对 (i, j)，计算其颜色欧氏距离和空间欧氏距离。
• 高斯核函数：利用公式 W_ij = exp(-dist_color^2 / sigma_I^2) * exp(-dist_spatial^2 / sigma_X^2) 计算权重。这确保了颜色越相近、距离越近的像素权重越大。
• 最终生成的矩阵 W 被存储为MATLAB的 sparse 格式，并强制对称化以消除计算误差。

3. 计算标准化拉普拉斯矩阵

为了求解Normalized Cut问题，程序构建了标准化对称拉普拉斯矩阵 L_sym。

• 首先计算度矩阵 D（相似度矩阵 W 的行和）。
• 计算 D 的平方根倒数矩阵 D^(-1/2)，并在计算过程中加入了极小值 eps 防止除零错误。
• 依据公式 L_sym = I - D^(-1/2) * W * D^(-1/2) 构建矩阵。相较于未标准化的拉普拉斯矩阵，这种形式在后续特征值分解中具有更好的数值稳定性。

4. 求解广义特征值问题

谱聚类的核心是将图分割转化为特征向量求解问题。

• 程序目标是求解 L_sym * y = lambda * y 的前 k 个最小特征值对应的特征向量。
• 使用 eigs 函数（基于Arnoldi/Lanczos算法）专门针对稀疏矩阵进行求解，参数设定为 'sm' (Smallest Magnitude)。
• 求解后得到的特征向量根据特征值从小到大排序。

5. 特征空间变换与K-Means聚类

• 提取前 k 个特征向量构成特征矩阵 U（N x k）。通常忽略第一个特征值接近0的特征向量（常数向量），或将其包含在内由K-Means处理（本代码提取前k个）。
• 行归一化：在聚类前，对特征矩阵的每一行进行L2范数归一化，将样本点投影到单位超球面上。这是谱聚类算法（如NJW算法）的关键步骤。
• 聚类：在归一化后的特征空间中运行 K-Means 算法，将 N 个像素点聚类为 k 个类别。为了避免局部最优，设置了多次重复运行 (Replicates)。

6. 结果后处理与可视化

• 标签映射：将聚类得到的索引向量 reshape 回图像的二维矩阵形式。
• 颜色编码：使用 label2rgb 将不同的分割区域渲染为不同的颜色。
• 边界提取：利用 boundarymask 函数计算分割区域的二值边界掩膜，并将边界染成红色叠加在原始图像上，直观展示分割效果。
• Fiedler向量展示：单独可视化第二个特征向量（即使 k>2），该向量通常包含最有价值的二分分割信息。

关键参数说明

• k: 期望分割的区域数量。
• resize_dim: 图像处理的分辨率，直接影响运行速度。过大的尺寸会导致内存溢出或计算时间过长。
• sigma_I: 颜色相似度的敏感性参数。值越小，对颜色差异越敏感。
• sigma_X: 空间距离的敏感性参数。值越大，允许相距较远的像素被归为同一类。
• r: 构建稀疏时的邻域半径，决定了图的连接密度。