The N-FINDR algorithm extracts endmember signatures from a hyperspectral data cube. Its core idea is to search the data set for the simplex of maximum volume, whose vertices are the desired endmembers. The mathematical principle and the concrete steps are as follows.
Mathematical Principle
Consider an \(M \times N \times C\)-dimensional hyperspectral data cube \(\mathbf{X}\). From it we need to find \(p\) endmember signatures \(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_p\). The matrix formed by these signature vectors is written \(\mathbf{E} = [\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_p]^T \in \mathbb{R}^{C \times p}\).
Under the linear mixing model, each pixel \(\mathbf{x}_i\) in the data cube \(\mathbf{X}\) can be expressed as a linear combination of the endmember signatures:
\[ \mathbf{x}_i = \sum_{j=1}^p a_{ij} \mathbf{e}_j + \mathbf{n}_i \]where \(a_{ij}\) is the corresponding abundance fraction, subject to the constraints \(\sum_{j=1}^p a_{ij} = 1\) and \(a_{ij} \geq 0\), and \(\mathbf{n}_i\) is an additive noise term.
The goal of N-FINDR is to find a set of endmember signatures \(\mathbf{E}\) such that the \(p\)-dimensional simplex formed by these signature vectors has maximum volume. The volume of that simplex can be expressed as the absolute value of the determinant of the endmember matrix \(\mathbf{E}\):
\[ \mathrm{vol}(\mathbf{E}) = |\det(\mathbf{E})| \]The algorithm iteratively updates the endmember matrix \(\mathbf{E}\) until it finds the solution that maximizes the determinant above.
Algorithm Steps
Initialization: Randomly select \(p\) pixels from the data cube as the initial endmember signature vectors, form the initial endmember matrix \(\mathbf{E}^{(0)}\), and compute the absolute value of its determinant, \(\mathrm{vol}(\mathbf{E}^{(0)})\).
Iteration:
For each endmember signature vector \(\mathbf{e}_i^{(t)}\), replace it with another pixel \(\mathbf{x}_j\) from the data cube to form a new endmember matrix \(\mathbf{E}_{ij}^{(t+1)}\).
Compute \(\mathrm{vol}(\mathbf{E}_{ij}^{(t+1)})\). If it is greater than \(\mathrm{vol}(\mathbf{E}^{(t)})\), update \(\mathbf{E}^{(t+1)} = \mathbf{E}_{ij}^{(t+1)}\).
Repeat the steps above until the volume can no longer be increased.
Output: The final endmember matrix \(\mathbf{E}\) is the solution.
Implementation
| |
The advantage of this algorithm is that the idea is clear: it can effectively extract the endmember signatures corresponding to the maximum-volume cluster. Its disadvantage is that the computation is heavy, and large data sets take a long time. In practice, the data are therefore usually reduced first with PCA, MNF, or a similar method, and N-FINDR is then run on the reduced data to cut the computational cost.
Overall, N-FINDR extracts endmembers from the data by maximizing the volume of the simplex formed by the endmember signature vectors. It is a classic unsupervised endmember-extraction algorithm.
