9.3 Initialization-Driven EEAs

Thus far, we have described two types of EEAs, SM-EEAs in Chapter 7 and SQ-EEAs in Chapter 8, both of which make use of initial endmembers randomly selected from the data. As demonstrated in experiments, the use of random initial endmembers results in inconsistent final selections of endmembers. An ID-EEA for PPI was first developed by Chang and Plaza (2006) to cope with this particular issue and more general issues were later investigated in Plaza and Chang (2006). Due to the natural difference in implementation of an SM-EEA and an SQ-EEA, how to find a specific set of initial endmembers for an SM-EEA and an SQ-EEA is also different. For a given number of endmembers, p, an initial set of endmembers for an SM-EEA needs p endmembers altogether to initialize an SM-EEA. On the other hand, an SQ-EEA produces one endmember at a time sequentially. In this case, an initial set of endmembers used to initialize an SQ-EEA is generally a singleton set which consists of only one endmember instead of p endmembers. As a result, finding an appropriate set of initial endmembers for an SQ-EEA is reduced to looking for a specific data sample that not only can speed up the endmember-searching process but also can produce consistent final results. So, an EEA which only requires the first endmember to be generated for its initial condition is called IED-EEA. When an EEA is an SQ-EEA using a specific data sample as an initial endmember, it is called IED-SQ-EEA. On the other hand, an SM-EEA requires a set of p initial endmembers to be specified. In this case, it needs an algorithm to produce a good set of initial endmembers which can speed up the search process implemented in an EEA to converge rapidly to the desired final results. An algorithm designed for this purpose is called EIA. An EEA makes use of an EIA to produce its initial condition called an EIA-driven (EIAD)-EEA. In particular, when an EEA is an SM-EEA using an EIA as an initialization algorithm to produce an initial set of p-specific endmembers, it is called an EIAD-SM-EEA. Interestingly, an SQ-EEA can also be used to serve as an EIA. This is because an SQ-EEA is not necessarily optimal but provides very close final results. Consequently, an SM-EEA using an SQ-EEA as an EIA may be the best way to produce a final set of desired endmembers in terms of computational complexity and consistency in final results.

9.3.1 Initial Endmember-Driven EEAs

In Chapter 8, six SQ-EEAs are developed, SC N-FINDR, SGA, VCA, UFCLS/IEA-EEA, ATGP-EEA, and HOS-EEAs, each of which represents a specific category associated with one particular criterion. These SQ-EEAs can be implemented as IED-EEAs by specifying their first initial endmember in two ways.

9.3.1.1 Finding Maximum Length of Data Sample Vectors

The idea of finding a data sample vector that yields the maximum length among all data sample vectors came from the automatic target detection and classification algorithm developed by Ren and Chang (2003), that is,

(9.1)

where r runs over all data sample vectors. Since there is no prior knowledge regarding what signatures of interest we are looking for, a best hope is to search for a data sample vector with the most spectrally distinct signature which may be more likely to be an endmember. Equation (9.1) provides such a signature t₀ that can be used to replace the randomly generated initial endmember by EEAs. Using (9.1) to specify their initial endmembers, EEAs of this type include ATGP-EEA, UNCLS, UFCLS-EEA, VCA, and HOS-EEAs, which result in IED-ATGP-EEA, IED-UNCLS, IED-UFCLS, IED-VCA, and IED-HOS-EEAs. However, there is a different way for IED-VCA and IED-HOS-EEAs to implement (9.1). In step 4 of the VCA algorithm described in Section 8.4, a Gaussian random vector is used to generate an initial vector to produce an initial endmember every time after an endmember is generated. As also shown, the VCA can also be implemented using a uniform random variable to replace the Gaussian random vector. To implement VCA as IED-VCA, the random variable used by VCA must be replaced by specifically chosen initial endmembers as described in the following.

IED-VCA (step 4 implemented in VCA is replaced by the following step):

1. At the nth iteration, the randomly generated Gaussian random vector, wⁿ, used in (8.1) is replaced by finding the maximum of r^Tr with , that is, .

As noted in the above IED-VCA, it requires a new random initial projection vector every time a new search is initiated for a new endmember. Compared to IED-VCA, IED-ATGP only needs one initial random projection vector for initialization. Once IED-ATGP is initialized, the algorithm automatically carries out the rest of orthogonal projections without any more random projection vectors. This difference sheds light on how to resolve the issue in the use of random projection vectors frequently occurred in projection pursuit (PP)-based algorithms including VCA in Section 8.4, high-order statistics-based EEA (HOS-EEA) in Section 8.6, and independent component analysis-based EEA (ICA-EEA) in Section 8.6.5. Using exactly the same ideas of extending VCA to IED-VCA in Section 9.3.1.1, HOS-EEA and ICA-EEA can also be extended in the same fashion. In other words, HOS-EEA and ICA-EEA can be extended to IED-HOS-EEA and IED-ICA-EEA by specifying the brightest pixel with the highest intensity as their initial projection vector every time they search for a new endmember.

Unlike VCA and HOS-EEA, which only need to specify one initial endmember, the SGA described in Section 8.3 requires two initial endmembers for initialization since the minimum number of forming a simplex is two vertices. In this case, a best pair of two initial endmembers that can be used to form a two-dimensional simplex is made up of two data samples (e⁽⁰⁾,e⁽¹⁾) that yield the maximum Euclidean distance among all possible pairs of data sample vectors in a reduced one-dimensional data space obtained by a DR transform. This is because such a pair represents the maximum volume of two-dimensional simplexes. Using this pair of data samples (e⁽⁰⁾,e⁽¹⁾) to replace the random initial endmember used in step 1 of SGA, we can obtain the following IED-SGA.

IED-2-SGA (step 1 in 1-SGA is replaced by the following step):

1. Initialization

a. Let p be the number of endmembers to be generated.

b. Find (e⁽⁰⁾,e⁽¹⁾) which produce the maximum distance in a one-dimensional data space obtained by any DR transform and set .

It should be noted that the above IED-SGA is slightly different from the SGA developed in Chang et al. (2006), which uses the first endmember selection process described below.

First Endmember Selection Process for 1-SGA.

1. Randomly generate a target sample vector, denoted by t.

2. Find a pixel e⁽⁰⁾ that yields the maximum of absolute determinant of the matrix, over all sample vectors r, that is, where PCA or MNF is required to reduce the original data dimensionality L to dimension 2 to find the maximum.

The generation of the above first endmember pixel e⁽⁰⁾ is determined by the randomly generated target sample vector t. A different target sample vector t may result in a different e⁽⁰⁾. Interestingly, such a generated e⁽⁰⁾ is always a sample vector that has either a maximum or a minimum value in the first component after dimensionality reduction transform. Therefore, the target sample vector t has no effect on the final set of endmembers. Furthermore, it also shows that the e⁽⁰⁾ which is generated by the above first endmember selection process and the e⁽¹⁾ which has the maximum distance from the e⁽⁰⁾ turn out to be exactly the same pair (e⁽⁰⁾, e⁽¹⁾) obtained by step 1(b) in IED-2-SGA. This indicates that the above IED-2-SGA is essentially the same SGA as developed in Chang et al. (2006). It is also interesting to note that the computational complexity of producing the first two endmembers by IED-1-SGA is compared to , which is the computational complexity of producing the first two endmembers by IED-2-SGA where N is the total number of data sample vectors. This also implies that IED-2-SGA only conducts half of searches required by IED-1-SGA. Consequently, IED-1-SGA and IED-2-SGA generally perform differently since initial conditions determine final results of extracted endmembers.

9.3.1.2 Finding Sample Mean of Data Sample Vectors

The IEA discussed in Section 8.5.4 is not really the one developed by Neville et al. (1999) since the initial endmember used by Neville et al.'s IEA was not selected randomly. As a matter of fact, Neville et al.'s IEA calculates the data sample mean as an initial target vector, e⁽⁰⁾, and find a set of pixels in R⁽⁰⁾ that are within the spectral angle θ and farthest from the obtained mean, t₀, denoted by R⁽⁰⁾(θ). Then they further calculate the average of pixels in R⁽⁰⁾(θ) and use it as the first endmember, denoted by e⁽¹⁾. So, according to its specific selection of an initial endmember, Neville et al.'s IEA is actually IED-IEA for consistency in notation. Since the sample mean is basically a mixture of all data sample vectors, it is expected that it cannot be an endmember in which case using the sample mean may not be a good candidate to be selected as an initial endmember.

9.3.2 Endmember Initialization Algorithm for SM-EEAs

As noted previously, an SQ-EEA may not be an optimal EEA as an SM-EEA is. So, its final endmembers produced may not be all desired endmembers. But according to experiments, many of SQ-EEA-generated endmembers eventually turn out to be the desired true endmembers. By taking advantage of this fact, an SQ-EEA can be also used as an effective EIA which provides a better set of initial endmembers that help an SM-EEA converge to final results rapidly. Nevertheless, the issue arising in inconsistency caused by randomness remains unsolved if an SQ-EEA also uses random initial endmembers.

In Section 9.3.1, an SQ-EEA is extended to an IED-SQ-EEA by specifying a particularly selected data sample as an initial endmember to initialize an SQ-EEA to avoid inconsistency resulting from the use of random initial endmembers. This is because an SQ-EEA finds one endmember at a time and only one sample is needed to initialize an SQ-EEA. However, the same strategy is not applicable to an SM-EEA due to the fact that an SM-EEA needs a set of p initial endmembers to initialize an SM-EEA instead of a single specific initial endmember only required by an SQ-EEA. In this case, we need to develop an algorithm, EIA, that allows us to produce a good set of candidates used for initial endmembers. Interestingly, an SQ-EEA, no matter whether it is an SQ-EEA using a random initial endmember or an IED-SQ-EEA, can also be used to serve as the purpose of EIA. Since an SQ-EEA may not be necessarily an optimal EEA, its extracted endmembers may not be all desired endmembers. But, according to experiments, many of its extracted endmembers turn out to be desired endmembers. Using a set of an SQ-EEA-extracted endmembers as an initial endmember to initialize an SM-EEA yields fast convergence to a final set of desired endmembers. In this section, we describe three types of algorithms, SQ-EEAs including IED-SQ-EEAs, Maxmin-distance algorithm (Tou and Gonzalez, 1974), and ISODATA (Duda and Hart, 1973) that can be used as EIAs.

9.3.2.1 SQ-EEAs

Despite the fact that all the SQ-EEAs developed in Chapter 8 are suboptimal EEAs, many of SQ-EEA-generated endmembers eventually turn out to be desired true endmembers. This suggests that an SQ-EEA can be used as an EIA with three benefits. One is to produce better sets of initial endmembers for an SM-EEA without random search in initialization. Another is to avoid unnecessary search for undesired endmembers so as to achieve fast convergence. The third benefit is that in many cases, the SQ-EEA-generated endmembers may actually end up as the final endmembers for an SM-EEA; this indicates that an SM-EEA, implemented in conjunction with an SQ-EEA used as an EIA, not only can produce optimal results, but also can reduce computational complexity tremendously in a significant order.

An EIA shares with an SQ-EEA some features which are not shared with an SM-EEA. First of all, when an SM-EEA is implemented, it assumes that the number of endmembers is known in advance and produces p endmembers simultaneously. So, for a different value of p, an SM-EEA generally produces a different set of endmembers. In other words, for any given number of endmembers, p, an SM-EEA must recalculate all the endmembers and cannot take advantage of a set of p − 1 endmembers previously generated by the same algorithm. Also, these p − 1 endmembers do not necessarily constitute a subset of the set of p endmembers generated in the end. On the other hand, an EIA produces a set of target pixels in sequential order. As a result, a set of p EIA-generated pixels always includes the set of previously generated p − 1 target pixels. This feature is highly desirable for an EIA because it can save tremendous computational time.

9.3.2.2 Maxmin-Distance Algorithm

In this subsection, we describe a very simple EIA called the Maxmin-distance algorithm, which has been commonly used in pattern recognition applications (Tou and Gonzalez, 1974). It can generate a reasonably good set of initial endmembers. Let the first initial endmember be obtained as the pixel vector with the maximum length, that is, . Then, for each , the jth endmember e_j with the largest distance to the set is defined and found by the following expression: , where the distance d(r, S_j−1) is defined by

(9.2)

It is worth noting that when , then , in which case . It should also be noted that the distance measure used in the Maxmin-distance algorithm can be any spectral similarity measure such as the Euclidean distance, SAM, or spectral information divergence (Chang, 2000, 2003b). In this work, we rely on SAM to produce a set of initial endmembers using the Maxmin-distance algorithm.

9.3.2.3 ISODATA

The ISODATA (Duda and Hart, 1973), also known as the k-means or c-means method, is an unsupervised clustering algorithm which has been widely used in image classification and segmentation. Its implementation can be briefly described as follows.

ISODATA Algorithm

1. Initialization

Determine the number of pattern classes p and randomly select p class means for and let .

2. At the iteration, compute the distance of each sample pixel vector from all class means, for and assign the sample vector to the class whose mean has the shortest distance to the sample vector.

3. Compute the means of reclustered sample vectors for each class, for .

4. If there is any mean changed, that is for some , let and . Go to step 2. Otherwise, the obtained are the desired class means and the algorithm is terminated.

Now, if we use obtained by ISODATA as an initial set of endmember to initialize an SM-EEA, the ISODATA becomes an EIA.

9.3.3 EIA-Driven EEAs

An EEA implemented in conjunction with an EIA to produce an appropriate set of initial endmembers is called EIA-EEA. When an EEA is an SM-EEA, it is referred to as EIA-SM-EEA. Similarly, when an EEA is an SQ-EEA, it is also referred to as EIA-SQ-EEA. As examples, using ATGP-EEA as an EIA SC N-FINDR and VCA can be extended to ATGP-SC N-FINDR and ATGP-VCA as follows.

ATGP-SC N-FINDR (step 2 implemented in the SC N-FINDR algorithm is replaced by the following step 2):

1. Initialization

Let be generated by ATGP-EEA and be a set of initial vectors randomly generated from the data.

ATGP-VCA (steps 3 and 4 implemented in VCA algorithm is replaced by the following steps 3 and 4):

2. Set the initial vector and let a auxiliary matrix A⁽⁰⁾ be . Also implement ATGP-EEA to produce a set of p initial endmembers, denoted by .

3. At the nth iteration, the randomly generated Gaussian random vector w^k used in (8.1) is replaced by , where are ATGP-generated target pixels.

Figure 9.5 shows results for the TI1 scenario with six endmembers extracted by various ID-EEAs, IED-VCA, IED-1-SGA, IED-2-SGA, IED-UFCLS-EEA, IED-ATGP-EEA, ATGP-PPI, Maximin-PPI, ISODATA-PPI, ATGP-N-FINDR, Maxmin-N-FINDR and ISODATA-N-FINDR. As we can see from the figure, all IED-EEAs were able to extract all five mineral signatures except PPI using IED and N-FINDR using Maxmin and ISODATA as IED. These experiments made sense. The reason that PPI using IED did not work was because PPI required a large number of skewers to find directions of endmembers. Using IED simply did not provide enough directions. Furthermore, the experiments in Figures 9.5(j) and 9.5(k) also showed that using the maxmin and ISODATA which are popular in traditional image processing as IED did not work. This implies that not any unsupervised method can be used for the purpose of IED.

Figure 9.5 Results for the TI1 scenario with six endmembers extracted by various ID-EEAs.

Generally, the ATGP-EEA used in step 3 of the above ATGP-VCA can be replaced by any EIA. However, the reason that the ATGP is chosen for EIA-VCA is simply based on the fact that both ATGP and VCA are OP-based techniques. It is very much likely that an ATGP-generated initial endmember t_n turns out to be the same as a VCA-generated endmember e^(k) solved by (8.5). As similar examples, HOS-EEA and ICA-EEA can also be extended to EIA-HOS-EEA and EIA-ICA-EEA in the same manner in which VCA is extended to EIA-VCA described above. If the EIA used in EIA-HOS-EEA and EIA-ICA-EEA is chosen to be ATGP-EEA to produce a set of p projection vectors that can be used as initial projection vectors for each of p searches for new endmembers, the EIA-HOS-EEA and EIA-ICA-EEA are referred to as ATGP -HOS-EEA and ATGP-ICA-EEA. Figure 9.6 provides a block diagram of SQ-EEAs in Chapter 8 which can be implemented as IED-EEAs and SM-EEAs in Chapter 7 which include an EIA as their initialization algorithm to become EIA-SM-EEAs.

Figure 9.6 Block diagram of various ID-EEAs.

Two comments are noteworthy: