Vertex Component Analysis (VCA) is a fast unsupervised algorithm for extracting endmembers from hyperspectral images. Its main idea is to use the property that endmembers form the vertices of the data cloud in a high-dimensional feature space. By iteratively searching for spectra that lie on the boundary of the data cloud, the algorithm extracts the endmembers. The mathematical principle and the solution procedure are presented in detail below.
Problem Statement
Consider a hyperspectral image with \(L\) bands. The spectral vector of each pixel is \(\mathbf{r} \in \mathbb{R}^{L}\), and the whole image can be written as \(\mathbf{R} = [\mathbf{r}_1, \mathbf{r}_2, \dots, \mathbf{r}_N] \in \mathbb{R}^{L \times N}\), where \(N\) is the number of pixels. Under the linear mixing model, each spectral vector \(\mathbf{r}_i\) is a linear combination of \(p\) endmembers \(\mathbf{m}_1, \mathbf{m}_2, \dots, \mathbf{m}_p \in \mathbb{R}^{L}\):
\[ \mathbf{r}_i = \sum_{j=1}^{p} a_{ij} \mathbf{m}_j + \mathbf{n}_i \]where \(a_{ij} \geq 0\) are the endmember abundance coefficients satisfying
\(\sum_{j=1}^{p} a_{ij} = 1\),
and \(\mathbf{n}_i\) is white Gaussian noise. In matrix form,
\[ \mathbf{R} = \mathbf{M} \mathbf{A} + \mathbf{N} \]where \(\mathbf{M} = [\mathbf{m}_1, \mathbf{m}_2, \dots, \mathbf{m}_p] \in \mathbb{R}^{L \times p}\) is the endmember matrix, \(\mathbf{A} \in \mathbb{R}^{p \times N}\) is the abundance matrix, and \(\mathbf{N} \in \mathbb{R}^{L \times N}\) is the noise matrix.
The goal of VCA is to extract the endmember matrix \(\mathbf{M}\) unsupervised from the hyperspectral data \(\mathbf{R}\).
Principle of the VCA Algorithm
Vertex Property of the Data Cloud
Suppose there are \(p\) endmembers. Then every spectral vector lies inside the \((p-1)\)-dimensional simplex spanned by these \(p\) endmembers. In the absence of noise, a spectral vector on the boundary of the simplex must be an endmember. The core idea of VCA is therefore to find spectral vectors on the boundary of the data cloud and take them as the extracted endmembers.
Projection Method
To find the boundary spectra, VCA uses projection to map the high-dimensional data into a lower-dimensional space, so that the geometry of the boundary spectra becomes clearer.
First, singular value decomposition (SVD) is used to compute an order-\(p\) projection matrix \(\mathbf{U}_d \in \mathbb{R}^{L \times d}\) (\(d=p\) or \(d=p-1\), depending on the signal-to-noise ratio SNR), and the data \(\mathbf{R}\) are projected into a \(d\)-dimensional space:
\[ \mathbf{X} = \mathbf{U}_d^T \mathbf{R} \]where \(\mathbf{X} \in \mathbb{R}^{d \times N}\) is the projected data.
The boundary spectra then have to be found in \(\mathbf{X}\). Observe that, in a \(p\)-dimensional simplex, the distance from a point to the boundary is greater than the distance from a point to the interior. The farthest boundary point can therefore be found by maximizing the cosine of the angle between a row vector \(\mathbf{x}_i^T \in \mathbb{R}^{1 \times N}\) of the projected matrix and all of the points:
\[ \max_{\|\mathbf{y}\|=1} \frac{\|\mathbf{y}^T \mathbf{x}_i\|}{\sqrt{\sum_{j=1}^{N} (\mathbf{y}^T \mathbf{x}_j)^2}} \]By the Cauchy-Schwarz inequality, the expression above reduces to finding the entry of \(\mathbf{x}_i\) with the largest absolute value:
\[ \max_{1 \leq j \leq N} |\mathbf{x}_{ij}| \]VCA therefore finds the boundary spectra by the following iteration:
For an arbitrary nonzero vector \(\mathbf{w} \in \mathbb{R}^{p}\), let \(\mathbf{f} = \mathbf{w} - \mathbf{A} (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{w}\) be the projection of \(\mathbf{w}\) onto the orthogonal complement of the vectors obtained so far, and normalize \(\mathbf{f}\).
For the normalized \(\mathbf{f}\), compute \(\mathbf{v} = \mathbf{f}^T \mathbf{Y}\), where \(\mathbf{Y} = [\mathbf{X}; \mathbf{c}]\) and \(\mathbf{c}\) is a scale constant.
Find the index \(k\) of the entry of \(\mathbf{v}\) with the largest absolute value, and set the \(i\)-th column of \(\mathbf{A}\) to the \(k\)-th column of \(\mathbf{Y}\).
Repeating these steps yields \(p\) vertex vectors, that is, the extracted endmember matrix \(\mathbf{U}\).
Solution Procedure
From the principle above, the concrete steps of VCA are as follows:
Compute the mean vector \(\overline{\mathbf{r}} = \frac{1}{N} \sum_{i=1}^{N} \mathbf{r}_i\), and center the data: \(\widetilde{\mathbf{R}} = \mathbf{R} - \overline{\mathbf{r}} \mathbf{1}_N^T\).
Compute the order-\(p\) projection matrix \(\mathbf{U}_d\) of the noise covariance matrix:
Project the data into a \(d\)-dimensional space: \(\mathbf{X} = \mathbf{U}_d^T \widetilde{\mathbf{R}}\).
Decide from the SNR whether a scale constraint is required:
If \(\mathrm{SNR} > \mathrm{SNR}_\mathrm{th}\), set \(\mathbf{Y} = \mathbf{X}\).
If \(\mathrm{SNR} \leq \mathrm{SNR}_\mathrm{th}\), set \(\mathbf{Y} = [\mathbf{X}; c]\), where \(c = \max_i \|\mathbf{x}_i\|_2\).
Initialize the \(p \times p\) matrix \(\mathbf{A}\):
Set the first column to \([1, 0, \dots, 0]^T\).
Set the remaining columns to zero.
Iterate once for each endmember:
Generate a random vector \(\mathbf{w}\).
Compute \(\mathbf{f} = (\mathbf{I} - \mathbf{A} (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T) \mathbf{w}\), and normalize \(\mathbf{f}\).
Compute \(\mathbf{v} = \mathbf{f}^T \mathbf{Y}\), and find the index \(k\) of the entry of \(\mathbf{v}\) with the largest absolute value.
Set the current column of \(\mathbf{A}\) to the \(k\)-th column of \(\mathbf{Y}\).
Estimate the endmember matrix \(\mathbf{U}\):
If \(\mathrm{SNR} > \mathrm{SNR}_\mathrm{th}\), then \(\mathbf{U} = \mathbf{U}_d \mathbf{X}_\mathrm{indicies}\).
If \(\mathrm{SNR} \leq \mathrm{SNR}_\mathrm{th}\), then \(\mathbf{U} = \mathbf{U}_d \mathbf{X}_\mathrm{indicies} + \overline{\mathbf{r}} \mathbf{1}_p^T\).
Here \(\mathbf{X}_\mathrm{indicies}\) is the matrix formed by the column vectors that correspond to the extracted endmembers.
The steps above are the complete solution procedure of VCA. The algorithm makes careful use of data projection and the vertex property. By iteration, it extracts the endmembers of a hyperspectral image without supervision, and it is both efficient and robust.
Code Implementation
| |
