A Fast and Accurate Similarity-Constrained Subspace

一种快速准确的高光谱图像相似性约束子空间聚类算法

abstract

子空间聚类方法，如稀疏子空间聚类（SSC），由于其高性能，已成为无监督学习的流行工具。

但是 计算机复杂性、忽略空间信息阻碍聚类结果的空间均匀性

为了解决这两个相关问题，提出了一种快速算法，通过首先选择一组最能代表其邻域的像素来获得稀疏表示系数矩阵。然后，它执行空间滤波以增强相邻像素的连通性，并使用快速光谱聚类来获得最终的聚类图。

introduction

高光谱图像（HSI）通常被视为三维数据集或数据立方体，在空间域（x，y）有两个维度，在光谱域（λ）有一个维度

HSI中的每个空间位置都由一个向量表示，其值对应于不同光谱带的强度。这些矢量也称为像素或光谱像素的光谱特征。

稀疏子空间聚类（SSC）算法是文献中最成功的无监督学习方法之一。SSC利用了高维数据可以很好地表示为低维子空间的联合这一事实。在此假设下，SSC通过利用自表达特性捕获所有数据点之间的关系.这个特性表明，子空间并集中的每个数据点都可以写成来自其自身子空间的其他点的线性组合。然后，通过最小化1范数，将解集限制为稀疏。最后，使用获得的稀疏系数构建亲和矩阵，并应用归一化谱聚类算法[18]来实现最终聚类图。

假设具有相似光谱的光谱像素大致属于相同的低维结构，SSC算法已成功应用于HSI。

尽管SSC在HSI聚类中取得了巨大成功，但两个主要问题是众所周知的:

1. SSC的总体计算复杂性限制了其在大型HSI数据集上的使用
2. 在HSI的背景下，SSC模型仅通过分析光谱特征而不考虑空间信息来捕获像素之间的关系

本文贡献：

在这篇文章中，我们对使用SSC对HSI的无监督分类感兴趣。由于SSC方法需要将每个数据点表示为数据集中所有其他点的线性组合，因此我们的主要观察结果是可以利用HSI的空间-光谱特性在小区域上选择最具代表性的光谱像素，然后将剩余的数据点约束为它们的线性组合。这显著减少了聚类时间并提高了准确性。提出了一种通过最小化数据的最大表示成本来选择每个子集中最具代表性的像素的有效算法。在这个过程之后，我们将获得的最具代表性的光谱像素连接起来形成矩阵。我们使用该矩阵来解决优化问题，以获得编码关于每个子集的最具代表性的光谱像素和整个HSI之间的相似性的信息的系数。最后，我们建议在应用快速谱聚类算法之前，通过2-D平滑卷积来增强所获得的系数矩阵，该算法在显著更少的时间内提供最终聚类图。使用这种2-D卷积的动机是在系数矩阵中强制分段平滑。本质上，所提出的方法强制亲和矩阵中的连通性，然后有效地获得谱嵌入，而无需计算特征值分解，其计算复杂度为O（N3）。

所提出的方法比SSC快三个数量级

related work

$X=x_1,\dots ,x_N$是$R^D$的k个子空间的线性组合 SSC将每个数据点xj表示为X中所有其他点的线性组合。$x_j={\sum }_{i\ne j}{c}_{ij}{x}_i$

其中，仅当xi和xj来自同一子空间时，cij才非零 这种表示{cij}称为子空间保持。

一旦获得{cij}表示，任意点对xi和xj之间的亲和矩阵定义为：$A_{ij}=|c_{ij}|+|c_{ji}|$,并且它被用作光谱聚类算法的输入以推断数据的聚类

尽管SSC产生的表示保证是子空间保持的，但亲和矩阵可能缺乏连通性，即，由于连接的稀疏性，来自相同子空间的数据点可能不会形成亲和图的连通分量。

基于SSC的HSI聚类方法

一些基于SSC的方法已经被提出用于无监督HSI分类，这些方法利用了相邻的空间信息，但仍然存在SSC的效率问题。在HSI的背景下,$Nr\times Nc\times L$三维图像数据立方体可以重新排列成二维矩阵$X\in R^{D\times N}$应用SSC算法，

其中N=NrNc，D

考虑到属于相同土地覆盖材料的光谱像素被布置在共同区域，不同的工作旨在获得分段平滑稀疏系数矩阵，以结合这种上下文相关性。

快速准确的相似约束子空间聚类（SC-SSC）

本节介绍了我们提出的用于无监督HSI分类的子空间聚类算法，该算法结合了两个特性：它是有效的，并利用HSI的空间信息来提高聚类精度。通常，我们利用相邻相似像素子集内的自表示特性来选择整个HSI中最具代表性的数据点。然后，我们增强稀疏表示并执行快速谱聚类以获得分割结果。我们在图3中展示了所提出方法的完整工作流程。

相似度约束的光谱像素选择

由于相邻的空间像素通常属于相同的土地覆盖材料，我们提出的方法旨在选择最能代表其邻域的像素子集。在这方面，我们首先建议将具有相似光谱的所有光谱像素分组为小空间区域。通常，这个预处理步骤可以以不同的方式完成。

由于其效率，我们特别采用了简单线性迭代聚类（SLIC）算法来生成制导区域地图。

特别地，我们执行PCA来检索X的三个主分量并形成矩阵$X_{PCA}\in R^{3\times N}$。然后，我们使用SLIC算法从$X_{PCA}$获得区域映射$\tilde{m}\in R^N$, m ~ ∈ { 1 , … , E } \tilde{m} \in \{1,\dots,E \} m~∈{1,…,E} 其中E是分段的数量。例如，如果${\tilde{m}}_j=e$，则表示光谱像素xj属于段e

PCA仅用于通过SLIC从$X_{PCA}$获得$\tilde{m}$ 我们使用$\tilde{m}$从每个段内的X中选择最具代表性的光谱像素xj。

让$p_e\in R^{N_e}$是包含属于子集e的Ne个最相似光谱像素的索引的向量。

我们倾向于从每个子集中选择$M_e=\lfloor \rho N_e\rfloor$ 个最有代表性的点。

利用自表达特性，通过搜索最小化的子集$X_e^{\ast }\subseteq X$来获得每个邻域e内像素的选择:

其中$F_{\tau }$是自表示代价函数，定义为

度量函数$f_{\tau }(x_j,X_e)$在几何上测量了数据$x_j\in X:j\in p_e$可以用子集Xe表示的程度，我们将其定义为

$\tau \in (1,+\infty )$ 是一个参数，对于（2），我们将使用向量$p_e$约束（1）仅搜索子集e内的像素xj

为了有效地求解每个子集e的（1），我们提出了算法1中描述的算法。注意，我们没有使用随机初始化，而是选择质心光谱像素${\overline{x}}_e$作为初始化，因为它是欧几里德距离中与e中所有其他数据点最相似的点。通过将HSI划分为子集并选择质心光谱像素，搜索空间约束加快了代表性光谱像素的获取。

提高快速光谱聚类的稀疏表示系数

一旦从每个子集获得最具代表性的光谱像素，我们通过将结果堆叠为列来构建矩阵$\hat{X}=[X_1,\dots ,X_E]$，

然后，大小为M×N的稀疏系数矩阵C，其中$M_e=\lfloor \rho N_e\rfloor$，可以通过解决以下优化问题来获得：

C编码关于$\hat{X}$和X之间相似性的信息,除此之外，C的每一行包含整个图像相对于单个代表像素的代表系数分布

考虑到属于同一土地覆盖材料的光谱像素应在图像中区域分布，即，HSI中的两个空间相邻像素通常具有属于同一类的高概率。然后，根据自我表达的特性，在相同的基础上，它们的表示系数也应该非常接近；因此，C的每一行应该是分段平滑的。

因此，为了进一步改进矩阵C的结构，我们建议对其系数应用二维平滑卷积。这是一个后处理过程，在光谱聚类之前执行。

给定大小为Ks×Ks的模糊核矩阵IKs，我们将二维卷积过程表示为$\hat{C}=G(C，IKs)$。具体而言，如图3所示，在蓝色虚线内，我们建议通过首先将C的每一行重塑为大小为Nr×Nc的窗口来执行G,其对应于HSI的空间维度，然后与IK进行卷积。最后，卷积结果重新排列为分段平滑系数矩阵的行向量$\hat{C}=[\widehat{c_1},\dots ,\widehat{c_N}]R^{M\times N}$

最后，我们使用快速谱聚类来有效地获得输入数据的谱嵌入，具体来说，让我们考虑$\tilde{C}=[\widetilde{c_1},\dots ,\widetilde{c_N}]R^{M\times N}$的列向量，其中$\widetilde{c_j}=|{\hat{c}}_j|/||\widehat{c_j}|{|}_2$,计算D的第i个元素为：

其中$\alpha ={\sum }_{j=1}^N\widetilde{c_j}\in R^M$ 通过计算$\tilde{C}{D}^{-1/2}\in R^{M\times N}$的奇异值分解我们可以找到$D^{-1/2}A{D}^{1/2}$的特征值分解

最后，可以通过对$\tilde{C}{D}^{-1/2}=U\sum P^T$的k个右奇异向量运行k-means算法来获得数据的分割 因此，在我们的框架中，频谱聚类的计算复杂度与数据N的大小成线性关系 算法2中总结了我们提出的SC-SSC方法。

过对$\tilde{C}{D}^{-1/2}=U\sum P^T$的k个右奇异向量运行k-means算法来获得数据的分割 因此，在我们的框架中，频谱聚类的计算复杂度与数据N的大小成线性关系 算法2中总结了我们提出的SC-SSC方法。