Richards J.A., Jia X. Remote Sensing Digital Image Analysis: An Introduction

Подождите немного. Документ загружается.

284 10 Feature Reduction

Using the values for Σ

and Σ

above this is



8.00 −3.25λ 5.50 −2.80λ

5.50 −2.80λ 3.78 − 5.46λ



= 0

which gives λ = 2.54 or 0. Thus there is only one canonical axis deﬁned by the vector

d corresponding to λ = 2.54. This is given as the solution to

[Σ

− 2.54Σ

]d = 0

i.e.



−0.26 − 1.61

−1.61 − 10.09





= 0

whereupon d

=−6.32d

At this stage we use (10.18), which for one vector d in D is

[

]



3.25 2.80

2.80 5.46





= 1

i.e. 3.25 d

+ 5.60 d

+ 5.46 d

= 1.

Using d

=−6.32 d

gives

= 0.632,d

=−0.100

so that

d =



0.632

−0.100



This vector is shown plotted in Fig. 10.10 wherein the projections of the patterns

onto the axis deﬁned by that vector show the classes to be separable. The brightness

values of the pixels in that ﬁrst axis are given by

y = d

=[0.632 − 0.100]x.

Fig. 10.10. The ﬁrst canonical axis for the

two class data of Fig. 10.9 showing class dis-

crimination

10.4 Feature Reduction by Data Transformation 285

10.4.3

Discriminant Analysis Feature Extraction (DAFE)

A variation on the canonical analysis development of the previous section is to form

the Fisher criterion

J = Tr



−1

w,y

A,y



(10.19)

rather than the measure of (10.15). We want to ﬁnd an axis transformation that

minimises J . Let the transformation be y = D

x. Then (10.19) can be written

J = Tr



w,x

−1

A,x



It is shown by Fukunaga (1990) that differentiating this last expression to ﬁnd the

transformation matrix D

that minimises J leads to

−1

w,x

A,x

D = DΣ

−1

w,y

A,y

. (10.20)

Consider the transformation z = B

y that diagonalises the transformed among class

covariance Σ

A,y

B = M.

in which M is diagonal. Thus

A,y

= B

−1

so that (10.20) becomes

−1

w,x

A,x

D = DΣ

−1

w,y

−1

(10.21)

As with canonical analysis we now introduce the additional criterion that the within

class covariance matrix be unity after the transformation to z space, so that the classes

then appear hyperspherical. This requires

w,y

B = I

or B

−1

w,y

−1

= I

so that Σ

−1

w,y

−1

= B which, when substituted into (10.21),

gives Σ

−1

w,x

A,x

D = DBMB

−1

or Σ

−1

w,x

A,x

DB = DBM

which we recognise as an eigenfunction equation in which M is a diagonal matrix of

the eigenvalues of Σ

−1

w,x

A,x

and (DB) is the matrix of eigenvectors of Σ

−1

w,x

A,x

Eigenanalysis of Σ

−1

w,x

A,x

can be carried out by analysis of Σ

−1

w,x

and Σ

A,x

sepa-

rately (Fukunaga, 1990).

The axis along which the data has maximum separability is that corresponding to

the largest eigenvalue of Σ

−1

w,x

A,x

, and so on. Deriving the transformed axes based

on minimisation of (10.19) is referred to as discriminant analysis feature extraction

(DAFE).

286 10 Feature Reduction

10.4.4

Non-parametric Discriminant Analysis

and Decision Boundary Feature Extraction (DBFE)

As with canonical analysis the application of DAFE requires good estimates of the

relevant co-variance matrices. In the case of the within-class matrices, that could be

difﬁcult when the dimensionality of the data is high, as with hyperspectral imagery,

but is often acceptable with data of multispectral order (i.e. several wavebands).

Even when the dimensionality of the data is acceptable, though, there is still an

assumption that the various spectral classes are in some sense “clusters” of similar

pixel vectors so that within class-covariance adequately describes how they spread

about their mean positions, and that between-class covariance, computed from the

means, is also meaningful. Provided spectral classes have been appropriately de-

lineated beforehand, that should not present much of a concern in image labelling

since, by deﬁnition, we try to segment the available data into groups whose properties

match the supervised classiﬁcation algorithm to be employed.

If, however, one or more of the classes were unusual in distribution, such as an

(unresolved spectral) class that might encompass a range of dark and light soil types

and a separate class of vegetative stubble, recorded in the visible and near infrared

region, then feature reduction methods that depend on class means and covariance

matrices may not work well. A class distribution such as that depicted in Fig. 10.11

is an example.

Should those types of class be suspected then it is better to avoid separability

criteria that depend on class statistics and instead try to ﬁnd a method that is non-

parametric. Non-parametric Discriminant Analysis (NDA) (Fukunaga, 1990), and

class 1

class 2

visible red

near infrared

Fig. 10.11. Situation in which DAFE would not be expected to perform well since the mean

of class 2 would be little different from that of class 1, and the within class covariance matrix

of class 2 would not reﬂect the actual scatter of the data

10.4 Feature Reduction by Data Transformation 287

its extension to Decision Boundary Feature Extraction (Landgrebe, 2003) is such

an approach. Rather than use class-based measures of mean and covariance, it uses

local statistical properties, in the following manner.

In its simplest form NDA examines the relationship between the training pixels

from one class (in a two class example) and their nearest neighbour training pixels

from the other class. For example, let x

j∈s,NNi ∈r

be the pixel (j ) from class s that

is the nearest neighbour of the ith pixel from class r: x

j∈s,NNi ∈r

is going to take the

role of the mean vector in the usual type of covariance calculation as far as pixels

from class r are concerned; in this case however the “mean” is different for each

pixel of class r (it is its nearest neighbour – which has to be computed). We can

describe the distribution of the class r pixels with respect to their nearest neighbours

by a covariance like calculation. However, because we are now not describing the

distribution of pixels around a class mean (a parametric description), it is better to

talk about the scatter of pixels with respect to each other, and thus use the term scatter

matrix to describe the measure.

For example, the scatter of (all of) the training pixels from class r about their

nearest neighbours from class s, x

j∈s,NNi ∈r

,is

= E{(x

i∈r

− x

j∈s,NNi ∈r

)(x

i∈r

− x

j∈s,NNi ∈r

)

|ω

}

where x

i∈r

is the ith pixel from class r, E is the expectation operator and the |ω

conditionality reminds us that the calculation is determined by the training pixels in

class r.

We perform a similar calculation for the scatter of the training pixels from class s

about their class r nearest neighbours, and then average the two measures – usually

weighted by the prior probabilities (or relative training sample abundances) of the

classes:

+ S

=p(ω

i∈r

− x

j∈s,NNi ∈r

)(x

i∈r

− x

j∈s,NNi ∈r

)

|ω

+p(ω

j∈s

− x

i∈r,NNj ∈s

)(x

j∈s

− x

i∈r,NNj ∈s

)

|ω

More often than not NDA uses not just the nearest neighbour in these calculations,

but instead deﬁnes a nearest neighbourhood of k class s training pixels to each class r

training pixel, and then uses the local mean over that neighbourhood in the calculation

of the between class scattering matrix. Let x

l∈s,kNNi ∈r

denote the lth of the k nearest

neighbours from class s of pixel i from class r. Then the local (class s) mean is

deﬁned as

s,kNNi ∈r



l=1

l∈s,kNNi ∈r

(10.22)

in which case the expression for the between class scattering matrix becomes

=p(ω

i∈r

− m

s,kNNi ∈r

)(x

i∈r

− m

s,kNNi ∈r

)

|ω

+p(ω

j∈s

− m

r,NNj ∈s

)(x

j∈s

− m

r,NNj ∈s

)

|ω

(10.23)

288 10 Feature Reduction

class r

band 2

band 1

class t

class s

i∈

s,kNNi∈ r

t,kNNi∈ r

k nearest neighbours in class s to

i∈

Fig. 10.12. The k nearest neighbours of the ith pixel from class r in each of two other classes.

Note from (10.22) that if k, the size of the neighbourhood, is the same as the total

number of training pixels available in class s then the “local” mean becomes the

class mean, and the between-class scatter matrices do indeed look like covariance

matrices, although taken around the mean of the opposite class rather than the mean

of their own class.

Generalisation of (10.23) requires a little thought because there are as many

weighted means of the pixels “from the other class” as there are “other classes.” This

is illustrated in Fig. 10.12 for the case of three classes: r, s and t. It is therefore easier

to express the expectations in (10.23) in algebraic form so that for C total classes



r=1

p(ω

)



c=1,c=r



i=1

i∈r

− m

c,kNNi ∈r

)(x

i∈r

− m

c,kNNi ∈r

)

(10.24)

in which the inner sum computes the expected scatter between the N

training pixels

from class r and the mean of the nearest neighbours in class c (different for each

training pixel), the middle sum then changes the class (c), still relating to the training

pixels from class r, and the outer sum changes the class (r) for which the training

pixels are being considered; the latter computation is weighted by the prior probability

for the class.

Having determined a non-parametric expression for among-class scatter we now

need to consider the within-class scatter properties, in order to be able to use a crite-

rion such as that in (10.19) to guide feature reduction. Fukunaga suggests using the

usual form of the within-class scatter matrix (10.11), although with a data transfor-

10.4 Feature Reduction by Data Transformation 289

mation that maps it to the identity matrix. Based on this assumption he shows that

the NDA transformation that ranks the transformed features by decreasing value in

separability is

z = 



−1/2

where  is the matrix of eigenvectors of S

, and  is the diagonal eigenvalue matrix

and Φ is the eigenvector matrix of the within-class scatter matrix.

An alternative non-parametric expression for the within-class scatter has been

proposed by Kuo and Landgrebe (2004), based on the local neighbourhood concept

above in which the mean of the k neighbours from class r of the ith pixel also from

class r is

r,kNNi ∈r



l=1,l=i

l∈r,kNNi ∈r

so that the within-class scatter matrix in the two class case is

=p(ω

i∈r

− m

r,kNNi ∈r

)(x

i∈r

− m

r,kNNi ∈r

)

|ω

+p(ω

j∈s

− m

s,kNNj ∈s

)(x

j∈s

− m

s,kNNj ∈s

)

|ω

The procedures of Sect. 10.4.3 can then be used to ﬁnd the required transformation.

It is clear that this process might lead to a better outcome if only those training

pixels in the vicinity of the decision boundaries were used in the computation of the

scatter matrices. Accordingly, the calculations can be weighted to lessen the inﬂuence

of neighbours further away from each other.

There are several limitations with the NDA approach, including the need both to

specify the size of the neighbourhoods and the need to identify the neighbours to be

used in each calculation. In contrast, even though canonical analysis is parametric in

its basis, the computational demand is relatively straightforward.

Another feature reduction procedure that uses training pixels only in the vicinity

of the decision boundary is Decision Boundary Feature Extraction (DBFE), sum-

marised by Landgrebe (2003).

Brieﬂy, it is based on the notion that (transformed) feature vectors normal to

decision boundaries are discriminantly informative, whereas feature vectors that lie

parallel to a decision boundary do not aid in class separation. Figure 10.13 illustrates

this point with a two dimensional, two class example. The problem, therefore, is to

ﬁnd an effective representation of the normals to the portion of the decision boundary

that is used in discrimination (even though a decision boundary may be inﬁnite in

extent theoretically, in practice only that portion in the vicinity of the training data

is signiﬁcant).

DBFE is a parametric procedure. It commences by estimating the class condi-

tional means and covariance matrices, which are used to deﬁne the actual decision

surface and then to classify the training pixels. Outlying pixels from each class are

then removed using a Chi-squared test (see Sect. 8.2.5), and a sample of each class

in the vicinity of the decision surface is selected by applying the Chi-squared test to

the pixels of the opposite class, using the statistics of the ﬁrst class.

290 10 Feature Reduction

band 2

band 1

discriminantly

informative feature

this feature

does not

contribute to

discrimination

Fig. 10.13. Transformed axes in which one of the new features is of value in separating the

classes shown. The other feature, being parallel to a likely decision boundary or separating

surface does not assist in discrimination.

From the sample identiﬁed, the decision surface normals are estimated in the

vicinity of the training data, from which an effective decision boundary feature

matrix is computed. While the dimensionality of the matrix will be the same as the

original feature space, its rank may be smaller, indicating the (reduced) number of

discriminantly informative features.

DBFE has a number of drawbacks, including, again, the large number of calcula-

tions required and the need to obtain reliable estimates of the original class signatures

and the decision boundary feature matrix. Those parameter estimates are not reliable

if the dimensionality is high and the number of training samples (especially in the

vicinity of the decision surface) is limited.

10.4.5

Non-parametric Weighted Feature Extraction (NWFE)

NWFE is a variation on the weighted version of DAFE above. It weights the samples

used in the calculations of the local means and uses slightly different deﬁnitions of

the among-class and within-class scattering matrices.

First, consider the calculation of a local mean for class r pixels in the vicinity

of pixel i from that same class. Rather than using a set of k nearest neighbours, all

the training pixels are used, but their inﬂuence on the computed value of the mean

is diminished the further they are from x

i∈r

. Thus the weighted r class mean about

10.4 Feature Reduction by Data Transformation 291

the ith pixel from class r is

r,i ∈r



l=1

l∈r,i∈r

l∈r

where N

is the number of training pixels in class r, and the weight w

l∈r,i∈r

is de-

ﬁned by

l∈r,i∈r

−1

i∈r

, x

l∈r

)



l=1

−1

i∈r

, x

l∈r

)

in which d

−1

is the inverse of the distance between the pixel vectors in its argument.

In a similar manner, the “local” mean of the class s pixels as far as the ith pixel from

class r, x

i∈r

, is concerned is

s,i∈r



l=1

l∈s,i∈r

l∈s

where the weight now is

l∈s,i∈r

−1

i∈r

, x

l∈s

)



l=1

−1

i∈r

, x

l∈s

)

Using these new deﬁnitions of the means, the among class and within class scatter

matrices are now computed, for the multiclass case, as



r=1

p(ω

)



c=1,c=r



i=1

i∈r,c

i∈r

− m

c,i∈r

)(x

i∈r

− m

c,i∈r

)

(10.25a)



r=1

p(ω

)



i=1

i∈r,r

i∈r

− m

r,i ∈r

)(x

i∈r

− m

r,i ∈r

)

(10.25b)

where the weights are deﬁned by

i∈r,ξ

−1

i∈r

ξ,i∈r

)



l=1

−1

i∈r

ξ,i∈r

)

with ξ = c or r, in (10.25a) and (10.25b) respectively.

To avoid problems with reliable estimation, or even singularity, the within-

class scatter matrix of (10.25b) is sometimes replaced by an approximate form (see

Sect. 13.7). In particular, Kuo and Landgrebe (2004) use



= 0.5S

+ 0.5 diag S

292 10 Feature Reduction

Having established the form of the among-class and within-class scatter matrices,

the required features can be found by using the eigenvectors corresponding to the

largest eigenvalues of

J = Σ

−1

w,y

A,y

With the newly deﬁned scatter matrices, the use of this criterion for ﬁnding the

transformation that gives best separability is tantamount to using (10.17).

10.4.6

Arithmetic Transformations

Depending upon the application, feature reduction prior to classiﬁcation can some-

times be carried out using simpler arithmetic operations than the transformations

treated in the foregoing sections. As an illustration, taking the differences of multi-

spectral imagery from different dates can yield difference data that can be processed

for change, by comparison with the need to classify all the data if the preprocessing

step is not adopted.

A second example is the use of the simple ratio of infrared to visible data as a

vegetation index. This allows vegetation classiﬁcation to be performed on the ratio

data alone. More sophisticated vegetation indices exist and these can be considered as

data reduction transformations. The most commonly encountered are the following

in which the bands designated are those from the multispectral scanners on Land-

sats 1–3. The band numbers need to be redeﬁned to refer to Landsats 4 onwards, and

other sensors.

VI = (band 7 − band 5)/(band 7 + band 5) (vegetation index)

TVI =

√

VI + 0.5 (transformed vegetation index)

These and others are discussed in Myers (1983).

References for Chapter 10

For more mathematical details on measures of divergence and Jeffries-Matusita distance the

reader is referred to Duda, Hart and Stork (2001) and Kailath (1967). A detailed discussion

on transformed divergence will be found in Swain and King (1973).

A good introductory discussion on canonical analysis in remote sensing is given in the

paper by Jensen and Waltz (1979). More detailed descriptions from a remote sensing viewpoint

have been given by Merembeck et al. (1977), Merembeck and Turner (1980) and Eppler (1976).

These also contain results that illustrate its suitability as a feature reduction tool.

Detailed mathematical descriptions of canonical analysis, as a statistical tool, will be found

in Seal (1964) and Tatsuoka (1971). Seal in particular gives the results of hand calculations

on two and three dimensional data sets.

N.A. Campbell and W.R. Atchley, 1981: The Geometry of Canonical Variate Analysis. Sys-

tematic Zoology, 30, 268–280.

Problems 293

R.O. Duda, P.E. Hart and D.G. Stork, 2001: Pattern Classiﬁcation, 2e, N.Y., Wiley.

W. Eppler, 1976: CanonicalAnalysis for Increased Classiﬁcation Speed and Channel Selection,

IEEE Trans. Geoscience Electronics, GE-14, 26–33.

K. Fukunaga, 1990: Introduction to Statistical Pattern Recognition, London, Academic.

S.K. Jensen and F.A. Waltz, 1979: Principal Components Analysis and Canonical Analysis in

Remote Sensing, Proc. American Soc. of Photogrammetry 45th Ann. Meeting, 337–348.

T. Kailath, 1967: The Divergence and Bhattacharyya Distance Measures in Signal Selection,

IEEE Trans. Communication Theory, COM-15, 52–60.

B.-C. Kuo and D.A. Landgrebe, 2004: Nonparametric Weighted Feature Extraction for Clas-

siﬁcation. IEEE Trans. Geoscience and Remote Sensing, 42, 1096–1105.

D.A. Landgrebe, 2003: Signal Theory Methods in Multispectral Remote Sensing, N.Y., Wiley.

P.W. Mausel, W.J. Kramber and J.K. Lee, 1990: Optimum Band Selection for Supervised

Classiﬁcation of Multispectral Data. Photogrammetric Engineering and Remote Sensing,

56, 55–60.

B.F. Merembeck, F.Y. Borden, M.H. Podwysocki and D.N. Applegate, 1976: Application

of Canonical Analysis to Multispectral Scanner Data, Proc. 14th Symp. Applications of

Computer Methods in the Mineral Industries, 867–879.

B.F. Merembeck and B.J. Turner, 1980: Directed Canonical Analysis and the Performance

of Classiﬁers under its Associated Linear Transformation, IEEE Trans. Geoscience and

Remote Sensing, GE-18, 190–196.

V.I. Myers, 1983: Remote Sensing Applications in Agriculture. In: R.N. Colwell (Ed.): Manual

of Remote Sensing, 2e, American Soc. of Photogrammetry, Falls Church.

H. Seal, 1964: Multivariate Statistical Analysis for Biologists. London, Menthuen.

P.H. Swain and S.M. Davis, (Eds.), 1978: Remote Sensing: The Quantitative Approach, N.Y.,

McGraw-Hill.

P.H. Swain and R.C. King, 1973: Two Effective Feature Selection Criteria for Multispectral

Remote Sensing, Proc. First Int. Joint Conf. on Pattern Recognition, 536–540, November.

P.H. Swain, T.V. Robertson andA.G. Wacker, 1971: Comparison of Divergence and B-Distance

in Feature Selection, Information Note 020871, Laboratory for Applications of Remote

Sensing, Purdue University, West Lafayette.

M.M. Tatsuoka, 1971: Multivariate Analysis, N.Y., Wiley.

A.G. Wacker, 1971: The Minimum Distance Approach to Classiﬁcation, Ph.D. Thesis, Purdue

University, West Lafayette.

Problems

10.1 Kailath (1967) shows that the probability of making an error in labelling a pattern as

belonging to one of two classes with equal prior probabilities is bounded according to

(2 −J

)

≤ P

≤

(2 −J

)

where J

is the Jeffries-Matusita distance between the classes. Determine and plot the upper

and lower bounds on classiﬁcation accuracy for a two class problem, as a function of J

.You

may wish to compare this to an empirical relationship between classiﬁcation accuracy and J

found by Swain and King (1973).

10.2 Consider the training data given in problem 8.1. Suppose it is required to use only one

feature to characterise each spectral class. By computing pairwise transformed divergence

measures ascertain the best feature to retain if: