8.5 Linear Spectral Mixture Analysis-Based SQ-EEAs

In Section 7.2.4, a linear spectral mixture analysis (LSMA)-based SM-EEA is developed on the basis of LSE, called FCLS-EEA, where a set of endmembers are found simultaneously by maximizing LSE among all possible subsets that contain the same number of samples. Since all the endmembers must be found simultaneously, full abundance constraints, ASC and ANC, should be imposed on the searching process. However, in a case of successive endmember extraction, there is no need for imposing both ASC and ANC on SQ-EEAs. So, in this section, three second-order statistics-based SQ-EEAs will be presented, all of which are LSE-based spectral unmixing techniques with/without abundance constraints.

The first LSMA-based SQ-EEA of interest is an unconstrained-abundance least-squares algorithm, called ATGP developed by Ren and Chang (2003), which makes use of a sequence of OSP to find target sample vectors successively. In other words, ATGP extracts endmembers from a sequence of nested orthogonal subspaces with reduced dimensionality. It can be considered an unsupervised OSP (UOSP) that extends OSP developed by Harsanyi and Chang (1994) to an unsupervised version of OSP (Chang et al., 1998a; Chang, 2003a). A second LSMA based SQ-EEA is an unsupervised abundance nonnegativity constrained least-squares algorithm, called UNCLS, which is based on nonnegativity constrained least-squares (NCLS) developed by Chang and Heinz (2000). Since it also uses OSP to perform linear unmixing, it can be considered a partially abundance constrained ATGP. A third LSMA-based SQ-EEA is a successive version of FCLS-EEA, called UFCLS-EEA, which imposes an additional abundance sum-to-one constraint on UNCLS. In this case, the UFCLS can also be considered a fully abundance constrained ATGP. An algorithm, recently developed by Neville et al. (1999), called the IEA, also uses LSE as a criterion, and is a fully abundance constrained linear spectral unmixing technique to find endmembers one by one sequentially. It turns out to be that both IEA and UFCLS-EEA are essentially the same technique in the sense that they use an LSE-based fully abundance constrained linear unmixing technique to find endmembers one at a time. So, in the context of OSP, all these LSE-based algorithms are actually OSP-based techniques. In what follows, the implementation of each of these SQ-EEAs is described.

8.5.1 Automatic Target Generation Process-EEA (ATGP-EEA)

ATGP is previously developed to find potential target pixels that can be used to generate a target signature matrix used in an OSP approach (Harsanyi and Chang, 1994; Chang, 2003a, 2003b). It is one of the two processes used in the automatic target detection and classification algorithm developed by Ren and Chang (2003). It repeatedly makes use of an orthogonal subspace projector defined by Harsanyi and Chang (1994) and Chang (2003a)

(2.78)

to find data sample vectors of interest from the data without prior knowledge regardless of what types of data sample vectors are. It can be described as follows.

Assume that t⁽⁰⁾ is an initial data sample vector. ATGP begins with the initial data sample vector t₀ by applying an orthogonal subspace projector , specified by (2.86) with U⁽⁰⁾ = [t⁽⁰⁾], to all data sample vectors. Then, it finds a data sample vector, denoted by t⁽¹⁾ with the maximum orthogonal projection in the orthogonal complement space, denoted by that is orthogonal to the space, spanned linearly by t⁽⁰⁾. The reason for this selection is that the selected t⁽¹⁾ has, in general, the most distinct features from t⁽⁰⁾ in the sense of orthogonal projection because t⁽¹⁾ has the largest magnitude of the projection in produced by . A second data sample vector t⁽²⁾ can be found by applying an orthogonal subspace projector with U⁽¹⁾ = [t⁽⁰⁾t⁽¹⁾] to the original data set, and a data sample vector that has the maximum orthogonal projection in is selected as t⁽²⁾.

The above procedure is repeated many times to find a third data sample vector t⁽³⁾, a fourth data sample vector t⁽⁴⁾, etc., until a certain stopping rule is satisfied. The stopping rule is determined by the number of data sample vectors required to generate, p, which is estimated by the VD. Using p as a stopping criterion, ATGP can be implemented in the following steps.

Algorithm for Automatic Target Generation Process-EEA (ATGP-EEA)

1. Initial condition:

Let p be the number of endmembers to be generated and t⁽⁰⁾ be a randomly generated initial endmember. Set .

2. At iteration, apply via (2.86) to all data sample vectors r and find the kth data sample vector t^(k) that has the maximum OP defined by

(8.6)

where is the data matrix and if .

3. Stopping rule:

If , let be the kth data matrix, go to step 2. Otherwise, continue.

4. At this stage, ATGP is terminated. At this point, the data matrix is U^{(p − 1)}, which contains p − 1 data sample vectors as its column vectors, that do not include the initial vector t⁽⁰⁾.

When ATGP is terminated, the final set of data sample vectors produced by ATGP at step 4 is the desired set of endmembers that comprises p data sample vectors, , found by repeatedly using (8.6).

8.5.2 Unsupervised Nonnegativity Constrained Least-Squares-EEA (UNCLS-EEA)

The UNCLS-EEA uses the NCLS method developed by Chang and Heinz (2000) for generating a set of potential data sample vectors, which can be considered endmembers. It first randomly picks an initial data sample vector denoted by t⁽⁰⁾. Then, it assumes that all other data sample vectors are pure data sample vectors consisting of t⁽⁰⁾ with 100% abundance. Of course, this is, in general, not true. Therefore, it next finds a data sample vector that has the largest LSE from the t⁽⁰⁾, and selects it as a first data sample vector denoted by t⁽¹⁾. Because the LSE between t⁽⁰⁾ and t⁽¹⁾ is the largest, it can be expected that t⁽¹⁾ is most distinct from t⁽⁰⁾. NCLS is then used to estimate the abundance fractions for t⁽⁰⁾ and t⁽¹⁾, denoted by and , for each data sample vector r, respectively. Here, r is included in the estimated abundance fractions and to emphasize that and are the functions of r and vary with r. The superscript indicates the number of iterations already executed. Now, we find an optimal constrained linear mixture of t₀ and t₁, , to approximate the r. Once again, it calculates the LSE between r and its estimated linear mixture for all data sample vectors r. A pixel that yields the largest LSE from its estimated linear mixture will be selected as a second data sample vector t⁽²⁾. As expected, such a selected data sample vector has the largest OP to the space linearly spanned by t⁽⁰⁾ and t⁽¹⁾. The same procedure of using the NCLS algorithm is repeated until the number of data sample vectors reaches the desired number of endmembers, p, which is preset in advance. The above-outlined procedure is called unsupervised NCLS (UNCLS)-EEA, which can be summarized as follows.

Algorithm for UNCLS-EEA

1. Initial condition:

Let p be the number of endmembers to be generated and t₀ be a randomly generated initial endmember. Set .

2. Let and find , where the kth least-squares error LSE^(k)(r) is defined by

(8.7)

3. Apply the NCLS method with the endmember matrix to estimate the abundance fraction of , . If , the algorithm is terminated; otherwise, go to step 2.

When the UNCLS algorithm is terminated at step 3, the final generated set is the desired endmembers .

8.5.3 Unsupervised Fully Constrained Least-Squares-EEA (UFCLS-EEA)

The UFCLS-EEA presented in the following is identical to UNCLS-EEA described in Section 8.5.2 with the exception that NCLS used in UNCLS-EEA is replaced by the FCLS method developed by Heinz and Chang (2001).

Algorithm for Unsupervised FCLS (UFCLS)-EEA

1. Initial condition:

Let p be the number of endmembers to be generated and t⁽⁰⁾ be a randomly generated initial endmember. Set .

2. Let and find , where the kth least-squares error LSE^(k)(r) is defined in (8.5).

3. Apply FCLS with the endmember matrix to estimate the abundance fraction of , . If , the algorithm is terminated; otherwise, go to step 2.

8.5.4 Iterative Error Analysis-EEA (IEA-EEA)

The IEA was originally proposed by Neville et al. (1999) for endmember extraction. In analogy with UFCLS-EEA, it also makes use of constrained linear spectral unmixing to search for possible endmembers. In addition, it does not produce all endmembers simultaneously as an SM-EEA does. It calculates the sample mean and uses it to initialize the algorithm. Then, it repeatedly performs constrained linear spectral unmixing procedures for producing a sequence of data sample vectors in succession, which are considered endmembers by IEA. Interestingly, there are major differences between IEA and UFCLS-EEA. One difference is the initial data sample vector generated by the algorithms. While the IEA calculates the sample mean vector for initialization, UFCLS-EEA finds a pixel with the largest vector length to be used as its initial pixel to start the algorithm. Another difference is that UFCLS-EEA generates a new data sample vector that has the largest least-squares error in terms of a fully constrained least-squares linear mixture described by (8.5). On the contrary, IEA uses an error image resulting from linear constrained linear unmixing after each spectral unmixing and finds the mean of the pixels with the largest least-squares error that are farthest from the previously selected endmembers. As a result, the endmembers sought by UFCLS-EEA are actually pixels, as opposed to signatures found by IEA that produces sample means as endmembers. In the latter case, the IEA-generated signatures are not necessarily image pixels. A third difference is that UFCLS-EEA does not need any prior knowledge, except the knowledge of the number of data sample vectors, p or a prescribed error threshold to terminate the algorithm. As for IEA, three parameters are required to be determined a priori, p, the desired number of endmembers, N_R(θ)^(k), the number of pixels in R^(k)(θ), where R^(k)(θ) is the set of data sample vectors with the largest errors in an error data set E^(k) after the kth spectral unmixing and θ is a spectral angle to be used to find data sample vectors that will be averaged to generate an endmember signature. Since no specific constrained spectral unmixing method was mentioned by Neville et al. (1999), the FCLS developed by Heinz and Chang (2001) will be used in IEA for our version of interpreting IEA.

Algorithm for IEA-EEA

1. Set values for three parameters p, R, and θ.

2. Initialization:

Generate randomly an initial endmember, denoted by t⁽⁰⁾.

3. Perform constrained linear spectral unmixing of t⁽⁰⁾ to find an error data set E⁽⁰⁾.

4. For , find a set of data sample vectors in R⁽ⁱ⁾ that are within the spectral angle θ and farthest from the obtained kth error data set E⁽ⁱ⁾ in terms of the Euclidean distance (i.e., vector length). Finally, calculate the average of data sample vectors in R^(k)(θ) and use it as the (k + 1)st endmember, denoted by t^(k+1).

5. If the used stopping rule is satisfied, the algorithm is terminated. Otherwise, perform constrained linear spectral unmixing on the kth endmember set, , and find its error data set E^(k). Let , and go to step 4. It should be noted that the stopping rule used in this step can be implemented in two ways. One way is to predetermine the number of endmember, p, in advance. Another way is to predetermine the unmixing error.

As noted, since the endmembers generated by the IEA-EEA are the averaged value of a set of data sample vectors in R^(k)(θ), they are not real data sample vectors in the data. In order to make a fair comparison with other EEAs, we set N_R^(k) = 1 and θ = 0 for our experiments. In this case, the IEA-generated endmembers are actually real data sample vectors in the data.