Richards J.A., Jia X. Remote Sensing Digital Image Analysis: An Introduction
Подождите немного. Документ загружается.
References for Chapter 8 243
References for Chapter 8
The classification techniques used in remote sensing image analysis come from the field of
mathematical pattern recognition and, as a consequence, are covered extensively in the standard
treatments in that discipline. Particular references that could be consulted to obtain more
mathematical detail than has been provided above, and to see other variations on the algorithms
often used, include Nilsson (1965, 1990), Duda, Hart and Stork (2001), and Tou and Gonzalez
(1974). For each of these a strong mathematical background is required. The development
of classification techniques in Swain and Davis (1978) is far less mathematical and includes
introductory conceptual material on the probabilistic aspects of pattern recognition.
The classifiers treated in this chapter have all been single stage in that only one decision
is made about a pixel as a result of which it is labelled as belonging to one of the available
classes, or is left unclassified. Decision tree procedures are also possible. In these a series of
decisions is taken in order to determine the correct label for a pixel. As an illustration, the first
decision might allow a distinction to be made between water, shadow and fire burnt pixels on
the one hand, and vegetation, urban and cleared regions on the other. Subsequent decisions
then allow finer subdivisions leading ultimately to a single label for the pixel. Advantages of
this approach include the fact that different sets of features can be used at each decision stage
and indeed even different algorithms could be employed. Its use in remote sensing problems
is described by Swain and Hauska (1977). The decision tree is one special example of the set
of layered classification techniques (Nilsson, 1965, 1990). Section 11.8 treats decision trees.
Atkinson et al. (1985) discuss the value of image filtering prior to classification using
both mean and median value methods. Demonstrations of probabilistic relaxation for pixel
classification, and its comparison with simple maximum likelihood classification, will be
found in Harris (1985), Gong and Howarth (1989) and Zenzo et al. (1987a, 1987b); the latter
authors also introduce the concept of fuzzy relaxation. Development of the basic relaxation
algorithm will be found in Rosenfeld, Hummel and Zucker (1976). Statistical methods for
context classification have been developed by Swain et al. (1981), Kittler and Pairman (1985)
and Khazenie and Crawford (1990).A selection of context classification methods are compared
by Mohn et al. (1987).
For a first reading on neural networks, beyond the material presented here, the paper by
Lippmann (1987) is recommended.
The seminal papers for the Markov Random Field approach for incorporating context in
a labelling exercise are those by Geman and Geman (1984) and Besag (1986). One of the
earliest treatments in remote sensing was that of Jeon and Landgrebe (1992), while Solberg et
al (1996) have employed the method to incorporate spatial and temporal contexts. Jung and
Swain (1996) have shown how the use of better estimates for class statistics, along with MRF
for including spatial context, can lead to improved classification accuracy.
P. Atkinson, J.L. Cushnie, J.R. Townshend and A. Wilson, 1985: Improving Thematic Mapper
Land Cover Classification Using Filtered Data. International Journal of Remote Sensing,
6, 955–961.
J.A. Benediktsson, P.H. Swain and O.K. Esroy, 1990: Neural Network Approaches Versus
Statistical Methods in Classification of Multisource Remote Sensing Data. IEEE Trans
Geoscience and Remote Sensing, 28, 540–552.
J.A. Benediktsson, P.H. Swain and O.K. Esroy, 1993: Conjugate-Gradient Neural Networks
in Classification of Multisource and Very-High-Dimensional Remote Sensing Data. Int.
J. Remote Sensing, 14, 2883–2903.
J. Besag, 1986: On the Statistical Analysis of Dirty Pictures. J. Royal Statistical Soc. (B), 48,
259–302.
244 8 Supervised Classification Techniques
C.T.C. Burges, 1998: A Tutorial on Support Vector Machines for Pattern Recognition. Data
Mining and Knowledge Discovery, 2, 121–167.
B.V. Dasarathy, 1991: Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques.
IEEE Computer Society Press, Los Alamitos, California.
R.O. Duda, P.E. Hart and D.G. Stork, 2001: Pattern Classification, 2e, N.Y., Wiley.
B.C. Forster, 1982: The Derivation of Approximate Equations to Correct for the Landsat
MSS Point Spread Function. Proc. Commission 1 (Primary Data Acquisition) Int. Soc.
for Photogrammetry and Remote Sensing, Canberra, April, 6–10.
J.E. Freund, 1992: Mathematical Statistics, 5e, New Jersey, Prentice Hall.
S. Geman and D. Geman, 1984: Stochastic Relaxation, Gibbs Distributions, and the Bayesian
Restoration of Images. IEEE Trans Pattern Analysis and Machine Intelligence, PAMI-6,
721–740.
P. Gong and P.J. Howarth, 1989: Performance Analyses of Probabilistic Relaxation Methods
for Land-Cover Classification. Remote Sensing of Environment, 30, 33–42.
P. Gong and P.J. Howarth, 1990: The Use of Structural Information for Improving Land-Cover
Classification Accuracies at the Rural-Urban Fringe. Photogrammetric Engineering and
Remote Sensing, 56, 67–73.
J.A. Gualtieri and R.F. Cromp, 1999: Support Vector Machines for Hyperspectral Remote
Sensing Classification. Proc. SPIE, 3584, 221–232.
R. Harris, 1985: Contextual Classification Post-Processing of Landsat Data Using a Proba-
bilistic Relaxation Model. Int. J. Remote Sensing, 6, 847–866.
G.F. Hepner, 1990: Artificial Neural Network Classification Using a Minimal Training Set:
Comparison to Conventional Supervised Classification. Photogrammetric Engineering
and Remote Sensing, 56, 469–473.
C. Huang, L.S. Davis and J.R.G. Townshend, 2002:AnAssessment of SupportVector Machines
for Land Cover Classification. Int. J. Remote Sensing, 23, 725–749.
B. Jeon and D.A. Landgrebe, 1992: Classification with Spatio-Temporal Interpixel Class
Dependency Contexts. IEEE Trans. Geoscience and Remote Sensing, 30, 663–672.
Y. Jung and P.H. Swain, 1996: Bayesian Contextual Classification based on Modified M-
estimates and Markov Random Fields. IEEE Trans. Geoscience and Remote Sensing, 34,
67–75.
R.L. Kettig and D.A. Landgrebe, 1976: Classification of Multispectral Image Data by Extrac-
tion and Classification of Homogeneous Objects. IEEE Trans. Geoscience Electronics,
GE-14, 19–26.
N. Khazenie and M.M. Crawford, 1990: Spatial-Temporal Autocorrelation Model for Con-
textual Classification. IEEE Trans. Geoscience and Remote Sensing, 28, 529–539.
J. Kittler and D. Pairman, 1985: Contextual Pattern Recognition Applied to Cloud Detection
and Identification. IEEE Trans Geoscience and Remote Sensing, GE-23, 855–863.
B.-C. Kuo and D.A. Landgrebe, 2002: A Robust Classification Procedure Based on Mixture
Classifiers and Nonparametric Weighted Feature Extraction. IEEE Trans. Geoscience and
Remote Sensing, 40, 2486–2494.
T. Lee, 1984: Multisource Context Classification Methods in Remote Sensing. PhD Thesis,
The University of New South Wales, Kensington, Australia.
T. Lee and J.A. Richards, 1985: A Low Cost Classifier for Multitemporal Applications. Int. J.
Remote Sensing, 6, 1405–1417.
T. Lee and J.A. Richards, 1989: Pixel Relaxation Labelling Using a Diminishing Neighbour-
hood Effect. Proc. IGARSS’89. Vancouver, 634–637.
R.P. Lippmann, 1987: An Introduction to Computing with Neural Nets. IEEE ASSP Magazine,
April, 4–22.
References for Chapter 8 245
MATLAB, 1984–2004: Neural Network Toolbox. The Math Works, Inc, MA.
F. Melgani and L. Bruzzone, 2004: Classification of Hyperspectral Remote Sensing Images
with Support Vector Machines. IEEE Trans. Geoscience and Remote Sensing, 42, 1778–
1790.
E. Mohn, N.L. Hjort and G.O. Storvik, 1987: A Simulation Study of Some Contextual Classifi-
cation Methods for Remotely Sensed Data. IEEE Trans. Geoscience and Remote Sensing,
25, 796–804.
N.J. Nilsson, 1965: Learning Machines. N.Y., McGraw-Hill.
N.J. Nilsson, 1990: The Mathematical Foundations of Learning Machines. Palo Alto, Morgan
Kaufmann.
Y.H. Pao, 1989: Adaptive Pattern Recognition and Neural Networks. Reading, Addison-
Wesley.
J.D. Paola and R.A. Schowengerdt, 1995a: A Review and Analysis of Backpropagation Neural
Networks for Classification of Remotely-Sensed Multi-Spectral Imagery. Int. J. Remote
Sensing, 16, 3033–3058.
J.D. Paola and R.A. Schowengerdt, 1995b:A Detailed Comparison of Backpropagation Neural
Network and Maximum-Likelihood Classifiers for Urban Land Use Classification. IEEE
Trans. Geoscience and Remote Sensing, 33, 981–996.
S. Peleg and A. Rosenfeld, 1980: A New Probabilistic Relaxation Procedure. IEEE Trans.
Pattern Analysis and Machine Intelligence, PAMI-2, 362–369.
J.A. Richards, D.A. Landgrebe and P.H. Swain, 1981: On the Accuracy of Pixel Relaxation
Labelling. IEEE Trans. Systems, Man and Cybernetics, SMC-11, 303–309.
A. Rosenfeld, R. Hummel and S. Zucker, 1976: Scene Labeling by Relaxation Algorithms.
IEEE Trans. Systems, Man and Cybernetics, SMC-6, 420–433.
B. Schölkop and A Smola, 2002: Learning with Kernels. Mass., MIT Press.
A.H.S. Solberg, T. Taxt andA.K. Jain, 1996: A Markov Random Field Model for Classification
of Multisource Satellite Imagery. IEEE Trans. Geoscience and Remote Sensing, 34, 100–
113.
P.H. Swain and S.M. Davis (Eds.), 1978: Remote Sensing: The Quantitative Approach, N.Y.,
McGraw-Hill.
P.H. Swain and H. Hauska, 1977: The Decision Tree Classifier: Design and Potential. IEEE
Trans. Geoscience Electronics, GE-15, 142–147.
P.H. Swain, S.B. Varderman and J.C. Tilton, 1981: Contextual Classification of Multispectral
Image Data. Pattern Recognition, 13, 429–441.
J.T. Tou and R.C. Gonzalez, 1974: Pattern Recognition Principles, Mass., Addison-Wesley.
F.E. Townsend, 1986: The Enhancement of Computer Classifications by Logical Smoothing.
Photogrammetric Engineering and Remote Sensing, 52, 213–221.
A.G. Wacker and D.A. Landgrebe, 1972: Minimum Distance Classification in Remote Sensing.
First Canadian Symp. on Remote Sensing, Ottawa.
S.D. Zenzo, R. Bernstein, S.D. Degloria and H.G. Kolsky, 1987: Gaussian Maximum Likeli-
hood and Contextual Classification Algorithms for Multicrop Classification. IEEE Trans.
Geoscience and Remote Sensing, 25, 805–814.
S.D. Zenzo, S.D. Degloria, R. Bernstein and H.G. Kolsky, 1987: Gaussian Maximum Likeli-
hood and Contextual Classification Algorithms for Multicrop Classification Experiments
Using Thematic Mapper and Multispectral Scanner Sensor Data. IEEE Trans. Geoscience
and Remote Sensing, 25, 815–824.
246 8 Supervised Classification Techniques
Problems
8.1 Suppose you have the following training data for three spectral classes, in which each
pixel is characterised by only two spectral components λ
1
and λ
2
.
Develop the discriminant functions for a maximum likelihood classifier and use them to
classify the patterns
x
1
=
5
9
x
2
=
9
8
x
3
=
15
9
under the assumption of equal prior probabilities.
8.2 Repeat question 1 but with the prior probabilities
p(1) = 0.048
p(2) = 0.042
p(3) = 0.910
8.3 Using the data of question 1 develop the discriminant functions for a minimum distance
classifier and use them to classify the patterns x
1
, x
2
and x
3
.
8.4 Develop a parallelepiped classifier from the training data given in question 1 and compare
its classifications with those of the maximum likelihood classifier for the patterns x
1
, x
2
and
x
3
, and the new pattern
x
4
=
3
7
At the conclusion of the tests in questions 8.1, 8.3 and 8.4, it would be worthwhile sketching a
multispectral (pattern) space and then locating in it the positions of the training data. Use this to
form a subjective impression of the performance of each classifier in questions 8.1, 8.3 and 8.4.
8.5 The following training data represents a subset of that in question 1 for just two of the
classes. Develop discriminant functions for both maximum likelihood and minimum distance
classifiers and use them to classify the patterns
x
5
=
14
7
x
6
=
20
13
Classify these patterns also using the minimum distance and maximum likelihood classifiers
developed on the full training sets of question 1 and compare the results.
Problems 247
8.6 Suppose a particular scene consists of just water and soil, and that a classification into
these cover types is to be carried out on the basis of near infrared data using the maximum
likelihood rule. When the thematic map is produced it is noticed that some water pixels are
erroneously labelled as soil. How can this happen, and what steps could be taken to avoid
it? Hint: Sketch some typical one dimensional normal distributions to represent the soil and
water in infrared data, noting that soil would have a very large variance while that for water
would be small. Remember the mathematical distribution functions extend to infinity.
9
Clustering and Unsupervised Classification
9.1
Delineation of Spectral Classes
The successful application of maximum likelihood classification is dependent upon
having delineated correctly the spectral classes in the image data of interest. This is
necessary since each class is to be modelled by a normal probability distribution, as
discussed in Chap. 8. If a class happens to be multimodal, and this is not resolved,
then clearly the modelling cannot be very effective.
Users of remotely sensed data can only specify the information classes. Occa-
sionally it might be possible to guess the number of spectral classes in a particular
information class but, in general, the user would have little idea of the number of
distinct unimodal groups that the data falls into in multispectral space. Gaussian
mixture modelling can be used for this purpose (Sect. 8.7) but the complexity of es-
timating simultaneously the number of Gaussian components, and their parameters,
can make this approach difficult to use. Clustering procedures are practical alterna-
tives that can be used for that purpose; these are methods that have been applied in
many data analysis fields to enable inherent data structures to be determined.
Clustering can also be used for unsupervised classification. In this technique an
image is segmented into unknown classes. It is the task of the user to label those
classes afterwards.
There are a great number of clustering methods. In this chapter only those com-
monly employed with remote sensing data are treated.
9.2
Similarity Metrics and Clustering Criteria
Clustering implies a grouping of pixels in multispectral space. Pixels belonging to
a particular cluster are therefore spectrally similar. In order to quantify this rela-
tionship it is necessary to devise a similarity measure. Many similarity metrics have
been proposed but those used commonly in clustering procedures are usually simple
250 9 Clustering and Unsupervised Classification
Fig. 9.1. Two apparently acceptable clusterings of a set of two dimensional data
distance measures in multispectral space. The most frequently encountered are Eu-
clidean distance and L1 (or interpoint) distance. If x
1
and x
2
are two pixels whose
similarity is to be checked then the Euclidean distance between them is
d(x
1
, x
2
) =||x
1
− x
2
||
={(x
1
− x
2
)
t
(x
1
− x
2
)}
1
2
=
N
i=1
(x
1
i
− x
2
i
)
2
!
1
2
(9.1)
where N is the number of spectral components. The L1 distance between the pixels is
d(x
1
, x
2
) =
N
i=1
|x
1
i
− x
2
i
|. (9.2)
Clearly the latter is computationally faster to determine. However it can be seen as
less accurate than the Euclidean distance measure.
By using a distance measure it should be possible to determine clusters in data.
Often however there could be several acceptable clusters assignments of the data, as
depicted in Fig. 9.1, so that once a candidate clustering has been found it is desirable
to have a means by which the “quality” of clustering can be measured. The availability
of such a measure should allow one cluster assignment of the data to be chosen over
all others.
A common clustering criterion or quality indicator is the sum of squared error
(SSE) measure, defined as
SSE =
C
i
x∈C
i
(x − m
i
)
t
(x − m
i
)
=
C
i
x∈C
i
||x − m
i
||
2
(9.3)
9.3 The Iterative Optimization (Migrating Means) Clustering Algorithm 251
where m
i
is the mean of the ith cluster and x ∈ C
i
is a pattern assigned to that
cluster. The outer sum is over all the clusters. This measure computes the cumulative
distance of each pattern from its cluster centre for each cluster individually, and then
sums those measures over all the clusters. If it is small the distances from patterns to
cluster means are all small and the clustering would be regarded favourably.
Other quality of clustering measures exist. One popular one is to derive a “within
cluster scatter measure” by determining the average covariance matrix of the clusters,
and a “between cluster scatter measure” by looking at the means of the clusters
compared with the global mean of the data. These two measures are combined into
a single figure of merit as discussed in Duda, Hart and Stork (2001) and Coleman
and Andrews (1979). It can be shown that figures of merit such as these are similar
to the sum of squared error criterion.
It is of interest to note that SSE has a theoretical minimum of zero, which corre-
sponds to all clusters containing only a single data point. As a result, if an iterative
method is used to seek the natural clusters or spectral classes in a set of data then it
has a guaranteed termination point, at least in principle. In practice it may be too ex-
pensive to allow natural termination. Instead, iterative procedures are often stopped
when an acceptable degree of clustering has been achieved.
It is possible now to consider the implementation of an actual clustering algo-
rithm. While it should depend upon a progressive minimisation (and thus calculation)
of SSE this is impracticable since it requires an enormous number of values of SSE
for the evaluation of all candidate clusterings. For example, there are approximately
C
p
/C! ways of placing P patterns into C clusters (Duda, Hart and Stork, 2001).
This number of SSE values would require computation at each stage of clustering
to allow a minimum to be chosen. Rather than embark upon such a rigorous and
computationally expensive approach the heuristic procedure of the following section
is usually adopted in practice.
Similarity metrics for clustering can incorporate measures other than spectral
likeness. Spatial proximity might be important in some applications as might com-
ponents that account for categorical information. For example, clustering crop pixels
might be guided by all of multispectral measurements, soil type and spatial contiguity.
These more general metrics are not covered here.
9.3
The Iterative Optimization (Migrating Means)
Clustering Algorithm
The iterative optimization clustering procedure, also called the migrating means
technique, is essentially the isodata algorithm presented by Ball and Hall (1965).
It is based upon estimating some reasonable assignment of the pixel vectors into
candidate clusters and then moving them from one cluster to another in such a way
that the SSE measure of the preceding section is reduced.
252 9 Clustering and Unsupervised Classification
9.3.1
The Basic Algorithm
The iterative optimization algorithm is implemented by the following set of basic
steps:
1. The procedure is initialised by selecting C points in multispectral space to serve
as candidate cluster centres. Let these be called
ˆ
m
i
,i = 1,...C.
The selection of the
ˆ
m
i
at this stage is arbitrary with the exception that no two
may be the same. To avoid anomolous cluster generation with unusual data sets it
is generally wise to space the initial cluster means uniformly over the data. This
can also serve to enhance convergence.
Besides choosing the
ˆ
m
i
the number of clusters C, must be specified beforehand
by the user.
2. The location x of each pixel in the segment of the image to be clustered is examined
and the pixel is assigned to the nearest candidate cluster. This assignment would
be made on the basis of the Euclidean or even L1 distance measure.
3. The new set of means that result from the grouping produced in Step 2 are com-
puted. Let these be denoted
m
i
,i = 1,...C.
4. If m
i
=
ˆ
m
i
for all i, the procedure is terminated. Otherwise
ˆ
m
i
is redefined as
the current value of m
i
and the procedure returns to Step 2.
The iterative optimization procedure is illustrated for a simple set of two dimen-
sional patterns in Fig. 9.2.
9.3.2
Mergings and Deletions
Once clustering is completed, or at any suitable intervening stage, the clusters can
be examined to see whether
(i) any clusters contain so few points as to be meaningless (e.g. that they would
not give acceptable statistics estimates if used in training a maximum likelihood
classifier), or
(ii) some clusters are so close together that they represent an unnecessary or indeed
an injudicious division of the data, and thus they should be merged.
In view of the material of Sect. 8.2.6 a guideline exists for (i), viz that a cluster
would be of little value for training a maximum likelihood classifier if it did not
contain about 10 N points where N is the number of spectral components. In Chap. 10,
which deals with separability and divergence, means for deciding whether clusters
should be merged can also be devised.
9.3 The Iterative Optimization (Migrating Means) Clustering Algorithm 253
Fig. 9.2. An illustration of clustering by iterative optimization (or the isodata method). As
noted, the method leads to a progressive reduction in SSE