22.4 Coding Techniques for Determining DDA

Finding signature discriminatory probabilities only accomplishes half the task. The other half task is to design a technique to allocate DDA required for each of signatures, based on their signature discriminatory probabilities. Suppose that each spectral dimension (i.e., spectral component) or spectral band can be only used to accommodate one and only one signature, then a binary value “1” can be used to indicate whether a spectral dimension or spectral band is being used for signature accommodation, “1” for being used and “0” for remaining “unused”. Consequently, DDA can be addressed by bit allocation where the number of spectral dimensions, q and the number of spectral bands, required for each signature corresponds to the coding length used to encode a source alphabet in source coding. This implies that finding variable-length code words using bit allocation is equivalent to finding variable spectral dimensions of q and variable spectral bands of for using DDA. The following three well-established coding schemes are readily applied to determine DDA.

22.4.1 Shannon Coding-Based DDA

An earliest and well-known coding scheme was developed by Shannon who introduced self- information to account for information provided by each source alphabet. For each source alphabet a_j with probability p_j, the self-information of a_j, I(a_j) is defined in Fano (1961) as

(22.2)

Using (22.2) a Shannon coding-based scheme to determine DDA can be described as follows.

Shannon coding for dynamic dimensionality allocation

1. Find the self-information of s_j, for all .

2. Find q_j for the signature s_j by

(22.3)

where is defined by the smallest integer .

3. Define the jth dimensionality allocation assigned to the signature s_j where .

It should be noted that in step 3 the dimensionality allocation is broken down into two values. The first value n_S is the number of spectral dimensions/bands required to specify the n_S signatures where one spectral dimension/band is required to accommodate each signature. When one spectral dimension/band is being used for signature accommodation, it is encoded by “1” and “0” otherwise. According to the definition of VD in Chapter 5, n_S is the number of spectrally distinct signatures if there is no prior signature knowledge available. So, there are at least n_VD bits required to accommodate all the n_S = n_VD signatures, one bit for an individual signature. Such bits can be considered as information bits. The second value q_j is the number of spectral dimensions/bands required for s_j to distinguish itself from other signatures, . In this case, the self-information I(s_j) defined by (22.2) is used to calculate additional q_j bits that represent q_j spectral dimensions/bands required to discriminate the signature s_j from other signatures, . Since the may be very large when π_j is very small in which case, it is set by the total number of spectral bands, L. To address this issue the Shannon coding is replaced by the Huffman coding as described in the following.

22.4.2 Huffman Coding-Based DDA

From a theoretical point of view the Shannon code is an asymptotic optimal code. But practically, it is not an optimal code. It is well-known that the only practical optimal code is the one developed by Huffman (Cover and Thomas, 1991), referred to as Huffman coding. It is a variable-length coding technique which is based on a simple fact that the smaller probability the source alphabet is, the longer its coding length. By replacing Shannon code with the Huffman code, the Shannon coding for DDA becomes the following Huffman coding for DDA.

Huffman coding for dynamic dimensionality allocation

1. Find the Huffman code words for and let l_j be the coding length of s_j using the probability π_j.

2. Define dimensionality allocation assigned to the signature s_j where .

22.4.3 Hamming Coding-Based DDA

Both the Shannon coding and Huffman coding described above are variable-length coding. This section presents an interesting fixed-length coding for finding DDA. It is derived from the Hamming code which uses 7 bits comprising of four information bits and three parity check bits to correct a single encoding error. As before, each of the n_S signatures requires one spectral dimension/band for its accommodation. In this case, the spectral dimensions/bands to specify these n_S signatures are referred to as information spectral dimensions/bands. Now the variable lengths, used by the Huffman coding can be replaced with a fixed length coding using n_S as information spectral dimensions/bands and as parity check spectral dimensions/bands for s_j for all . Then steps 1 and 2 in the above Huffman coding can be merged into one step as follows. This resulting coding is called Hamming coding in which case DDA becomes static dimensionality allocation (SDA).

Hamming coding for static dimensionality allocation

Define dimensionality allocation assigned to the signature s_j for all .

It should be noted that the Hamming coding for SDA assigns the same dimensionality allocation to all signatures with which is bounded above from 2n_VD. Since the Hamming coding involves no signature discriminatory probabilities of , it does not require prior knowledge of signatures of interest, as the Shannon coding and Huffman coding do. Therefore, its determined DDA is a constant regardless of what applications are. In this case, DDA is reduced to SDA.

22.4.4 Notes on DDA

In the above three coding schemes for finding DDA, the generic notation of n_S is used to indicate the number of signatures of interest that indeed varies with different applications. For example, if the considered application is endmember extraction or linear spectral mixture analysis (LSMA), the n_S can be set to n_VD. On the other hand, if the unsupervised target detection is considered as an application, the desired signature of interest are those virtual signatures generated by the unsupervised virtual signature finding algorithm (UVSFA) derived in Chapter 17. In this case, the n_S is the number of virtual signatures and is shown to be in the range of [n_VD, 2n_VD], that is, . Finally, a very important note on DDA is worthwhile. The effectiveness of DDA is more visible and evidential in applications of BS than that in DR. One is that BS is derived from the pigeon-hole principle where one bit represents one spectral band being used for signature accommodation. However, this may not quite fit DR because each spectral dimension produced by DR is a transformed dimension not the original band dimension. Another is mainly due to the fact the projection index components (PICs) produced by a DR transform are generally orthogonal. However, this is not true for BS that uses spectral bands that are generally highly correlated and not necessarily orthogonal. So, a spectral band is highly prioritized, so are its neighboring spectral bands. That explains why DR can gain little benefit from DDA as shown in Safavi (2010).