II

Endmember Extraction

Due to significantly improved high spatial and spectral resolution provided by hyperspectral imaging sensors endmember extraction has become increasingly important in hyperspectral image analysis. According to the definition given in Schwengerdt (1997), an endmember is an idealized, pure signature for a class, more specifically, spectral class. For multispectral imagery, an endmember may be difficult to find, due to the fact that many image pixels are generally heavily mixed because of its low spatial and spectral resolution. As a result, endmember extraction has received little interest in the past and its importance has been overlooked. By contrast, with recent advances in hyperspectral imaging sensors many subtle material substances that cannot be resolved by multispectral imagery can now be uncovered by hyperspectral imagery. These substances are generally not known a priori and can be only diagnosed by high spectral resolution. Endmembers are considered to be one of such substances. Their existence in image data cannot be generally detected by human eye. Most importantly, once endmembers are present, they may be very likely to appear as anomalies and their sample pools may be relatively small. Because of such characteristics, finding endmembers is very challenging. Many algorithms have been developed for this purpose, such as pixel purity index (PPI) (Boardman et al., 1995), N-finder algorithm (N-FINDR) (Winter, 1999a,b), iterative error analysis (IEA) (Neville et al., 1999), automated morphological endmember extraction algorithm (AMEEA) (Plaza et al., 2004), unsupervised fully constrained least squares (UFCLS) (Heinz and Chang, 2001), minimum volume transform (MVT) (Crag, 1994), convex geometry (Boardman, 1994), convex cone analysis (CCA) (Ifarraguerri and Chang, 1999), vertex component analysis (VCA) (Nascimento and Dias, 2005), simplex growing algorithm (SGA) (Chang et al., 2006) and independent component analysis-based endmember extraction algorithm (ICA-EEA) (Wang and Chang, 2006b), standardized principal components analysis (SPCA)-EEA, fully constrained least squares-EEA (FCLS-EEA), an alternative N-FINDR (AN-FINDR) (Ji, 2006), and statistics-based EEAs (Chu et al., 2007) that include PCA-EEA and high-order statistics-based EEA.

From an algorithmic implementation point of view, algorithms designed for endmember extraction can be performed in two different ways, simultaneous endmember extraction algorithms (SM-EEAs) and sequential endmember extraction algorithms (SQ-EEAs), as depicted in Figure II.1 where SM-EEA includes PPI, N-FINDR, MVT, CCA, SPCA-EEA, FCLS-EEA, and AMEEA, while the SQ-EEA includes IEA, VCA, SGA, UFCLS-EEA, and HOS-EEA.

Figure II.1 Categorization of EEAs.

Technically speaking, an optimal endmember extraction algorithm (EEA) must be an SM-EEA since all the endmembers should be selected at the same time rather than sequentially by SQ-EEAs. In general, finding all endmembers simultaneously requires tremendous computational complexity as a result of exhaustive search. On the other hand, an SQ-EEA may not be as optimal as an SM-EEA, but it may perform as well as an SM-EEA if the SQ-EEA is well-designed. Most advantageously, an SQ-EEA can reduce computations significantly.

For endmember extraction, two major criteria are of interest: convexity geometry and statistics. The criterion of convexity geometry can be further categorized into orthogonal projection (OP) and simplex volume. The criterion of OP is to orthogonally project data samples on a set of selected vectors so that the data samples whose orthogonal projections fall at the end (extreme) points of these selected vectors will be considered as endmember candidates. Such OP-based EEAs include PPI and VCA. The simplex volume criterion is to assume that a simplex formed by a set of pure signatures as vertices should yield the maximum volume among all simplexes formed by the same number of signatures as vertices. In this case, the vertices of the found simplex with the maximum volume will be considered as desired endmembers. Such simplex-based EEAs include MVT, CCA, N-FINDR, and SGA. Figure II.2 delineates various EEAs according to convexity geometry-based criteria.

Figure II.2 Categorization of convexity geometry.

The criterion of statistics has shown success in a variety of applications such as the dimensionality reduction (DR) in Chapter 6. The use of these statistics-based criteria for endmember extraction relies on the fact that a set of endmembers constitute the most uncorrelated sample pool among the same number of signatures where the correlation is measured by various statistics. Figure II.3 categorizes criteria of statistics into second-order statistics, statistical correlation and least squares error (LSE), and high-order statistics (HOS), skewness by third-order statistics, kurtosis by fourth-order statistics, kth moment by kth-order statistics, entropy specified by infinite order of statistics, and statistical independency measured by mutual information.

Figure II.3 Categorization of statistics.

From a perspective of algorithmic initialization, an EEA can be implemented and initialized by two types of initial conditions: random initial endmembers and specific algorithm-generated initial endmembers. In endmember extraction, most EEAs use randomly generated vectors as initial endmembers for initialization, such as PPI, N-FINDR, VCA, ICA-EEA, etc. Unfortunately, due to randomness a final set of endmembers produced by such an EEA is generally not repeatable. That is, if the same EEA is implemented in different runs with one run defined as one implementation of the EEA using one set of random initial endmembers, the final endmembers extracted by the same EEA will be different. In order to avoid such inconsistency in the final selection of endmembers, two approaches have been investigated and explored recently. One is to develop a custom-designed endmember initialization algorithm (EIA) to find an appropriate set of initial endmembers for an EEA, to eliminate uncertainty caused by randomness resulting from the use of random initial endmembers (Chang and Plaza, 2006a, 2006b). Such an EEA implemented in conjunction with an initialization algorithm is called initialization-driven EEA (ID-EEA). Another is to make the disadvantage of random initial endmembers an advantage. The idea is to consider an EEA that uses random initial endmembers as a random EEA where a single run resulting from a set of random initial endmembers is viewed as a realization of such a random EEA. If there is an endmember present in the data, it should eventually appear in the final set of endmembers generated by each run regardless of what initial endmembers are used by an EEA. In other words, if an EEA is implemented repeatedly with different sets of randomly generated initial endmembers, the desired endmembers should be among the common members in their final selection sets of endmembers generated by all runs. An REEA is terminated once the final generated endmember set remains unchanged in two consecutive runs. Such an EEA is called random EEA (REEA), also referred to as automatic EEA (AEEA) in Chaudhry et al. (2006) and Wu and Chang (2006). Figure II.4 categorizes various EEAs according to initial conditions used in their algorithm design where IED-EEA is referred to as initial endmember-driven EEA.

Figure II.4 Categorization of initial conditions, IED-EEA and REEA.

PART II includes four chapters (Chapters 7–10) presented in the order of SM-EEA, SQ-EEA, ID-EEA, and REEA, and an additional chapter, Chapter 11, that is a comparative study and analysis among EEAs. Chapter 7 is focused on SM-EEA that generates all endmembers simultaneously. Algorithms of this type are PPI, N-FINDR, SPCA-EEA, FCLS-EEA, MVT, CCA, and AMEE. Chapter 8 deals with the other type of algorithms, SQ-EEA, that generates endmember one at a time sequentially, that is, one by one in succession. The group of this type is made up of UFCLS, IEA, VCA, SGA, and HOS-EEA. Since initial endmembers play a key role in the final selection of endmembers, two chapters, Chapters 9 and 10, are devoted to this issue. Chapter 9 develops custom-designed EIAs to produce an appropriate set of initial endmembers that can be used for an EEA. As a result, all the EEAs developed in Chapters 7 and 8 that make use of random initial endmembers can be extended to their counterpart ID-EEAs to resolve the inconsistency issue in their final selected endmembers. Contrary to Chapter 9, Chapter 10 makes the disadvantage of using random initial endmembers an advantage by extending all the EEAs using random initial endmembers developed in Chapters 7 and 8 to their random counterparts where a realization of an REEA is considered as an EEA using a particular set of random initial endmembers. By running an REEA as many times as possible all realizations should eventually converge to a common set of endmembers that should be the final set of desired endmembers.

Chapter 11 describes experiment-based comparative studies and analyses among EEAs and further investigates their relationships. Of particular interest is a comprehensive study on PPI where three versions of PPI, MATLAB-based PPI, ID-PPI, and RPPI are evaluated and an exploration of relationships among the three algorithms, PPI, VCA, and ATGP that provides interesting sights into rationales of algorithm design for EEA. More details are also discussed in Wu (2006, 2009).

In spite of an effort to categorize EEAs in what is believed to be logical, it is by no means the only way to do so. For example, PPI and N-FINDR are the most commonly used algorithms developed for endmember extraction. Many algorithms in the current literature, along with those discussed in PART II, are sort of their variants in one form or another. Therefore, using these two algorithms as a base for categorization many EEAs can be further categorized in Figures II.5 and II.6 where both PPI and N-FINDR can be implemented in accordance with their algorithmic implementations laid out in Chapters 7–10.

Figure II.5 Various versions of PPI.

Figure II.6 Various versions of N-FINDR.

Table II.1 summarizes all the EEAs presented in Chapters 7–10 in terms of categorization of SM-EEA, SQ-EEA, ID-EEA, and REEA.

Table II.1 Categories of various EEAs.

Finally, since details of implementing the original versions of PPI and N-FINDR are not available in the literature, the PPI and the N-FINDR used to carry out all the experiments are those developed in this book, referred to as MATLAB-PPI in Section 7.2.1 and iterative N-FINDR (IN-FINDR) in Section 7.2.3.2. In particular, when the term of “N-FINDR” is used without specification in this book, it is indeed the IN-FINDR, not the original version of N-FINDR developed by Winter (1999a, b). As matter of fact, the two terms of “N-FINDR” and “IN-FINDR” are used interchangeably. Specifically, when IN-FINDR is referenced, it is the version of the single-replacement IN-FINDR (1-IN-FINDR) derived in Section 7.2.3.3.1.