Overview of Image Processing
69
2.6.2
Unsupervised Classification
Supervised classification may be impractical in various situations such as due to
imprecise knowledge of number and type of classes, for example. Unsupervised
approaches permit the formation of classes from the input data. While several
methods have been developed, we focus here on the issue of clustering which
forms the basis of many of these approaches. In any clustering approach, the
final output is a set of clusters with each input pixel assigned uniquely to
a cluster. Most clustering approaches are iterative. Obviously, there has to be
a logical basis for the clustering and this is provided by the principle that a pixel
belongs to that cluster whose representative value is closest to the pixel with
respect to a distance measure. Thus, at the end of the clustering process, we
should be presented with a representative value for each cluster formed.
A classic approach for cluster formation is the K-means algorithm, which is
described next. Suppose we set a target for the number of clusters, say K. Then,
K pixels are randomly chosen. Let their corresponding values be x~, ... , xk
where the superscript 1 indicates that these are the initial values. Each of the
remaining pixels is assigned uniquely to the closest of these initial pixels to
form the initial clusters. The most popular distance measure in practice is the
absolute distance or LI-distance which, for a pair of N-dimensional vectors
x = [Xl ... XN] and y = [YI .. . YN], is defined as
Ix - yl = IXI - YII + ... + IXN - YN I .
(2.23)
This distance measure is easy to calculate and is robust with respect to
outliers. Thus, cluster Ck is formed initially as
Ck = {x: Ix - xli < Ix - xJ I for all j t- k} ; 1::::: j, k ::::: K .
(2.24)
The next step is the location of the centroid within each cluster. The centroid
is defined as that value for which the sum of its distances from each member
of the cluster is minimized. For the LI-distance this turns out to be the vector
each of whose components is the median of that component taken over the
members of the cluster. For example, suppose we are working with just two
bands and there is a cluster with three members, say, al = [2,34], az = [10,22]
and a3 = [17,36]. Then the centroid is the vector [10,34], which is obtained as
the median of the two components of these three vectors. Notice that the centroid of a cluster may not be an actual input value. Following the calculation of
the centroids, the clustering process is repeated as in (2.24) with the centroids
replacing the initial values. A new set of centroids is then calculated following
the clustering. The two steps of clustering and centroid calculations are performed until either the clusters are stable or there is no significant change in
clusters.
If the Euclidean or Lz -distance is used instead of the absolute distance, then
the centroid simply becomes the arithmetic mean of all vectors. This measure
is appropriate if the distribution is Gaussian. It is close to the ML rule in that
69
2.6.2
Unsupervised Classification
Supervised classification may be impractical in various situations such as due to
imprecise knowledge of number and type of classes, for example. Unsupervised
approaches permit the formation of classes from the input data. While several
methods have been developed, we focus here on the issue of clustering which
forms the basis of many of these approaches. In any clustering approach, the
final output is a set of clusters with each input pixel assigned uniquely to
a cluster. Most clustering approaches are iterative. Obviously, there has to be
a logical basis for the clustering and this is provided by the principle that a pixel
belongs to that cluster whose representative value is closest to the pixel with
respect to a distance measure. Thus, at the end of the clustering process, we
should be presented with a representative value for each cluster formed.
A classic approach for cluster formation is the K-means algorithm, which is
described next. Suppose we set a target for the number of clusters, say K. Then,
K pixels are randomly chosen. Let their corresponding values be x~, ... , xk
where the superscript 1 indicates that these are the initial values. Each of the
remaining pixels is assigned uniquely to the closest of these initial pixels to
form the initial clusters. The most popular distance measure in practice is the
absolute distance or LI-distance which, for a pair of N-dimensional vectors
x = [Xl ... XN] and y = [YI .. . YN], is defined as
Ix - yl = IXI - YII + ... + IXN - YN I .
(2.23)
This distance measure is easy to calculate and is robust with respect to
outliers. Thus, cluster Ck is formed initially as
Ck = {x: Ix - xli < Ix - xJ I for all j t- k} ; 1::::: j, k ::::: K .
(2.24)
The next step is the location of the centroid within each cluster. The centroid
is defined as that value for which the sum of its distances from each member
of the cluster is minimized. For the LI-distance this turns out to be the vector
each of whose components is the median of that component taken over the
members of the cluster. For example, suppose we are working with just two
bands and there is a cluster with three members, say, al = [2,34], az = [10,22]
and a3 = [17,36]. Then the centroid is the vector [10,34], which is obtained as
the median of the two components of these three vectors. Notice that the centroid of a cluster may not be an actual input value. Following the calculation of
the centroids, the clustering process is repeated as in (2.24) with the centroids
replacing the initial values. A new set of centroids is then calculated following
the clustering. The two steps of clustering and centroid calculations are performed until either the clusters are stable or there is no significant change in
clusters.
If the Euclidean or Lz -distance is used instead of the absolute distance, then
the centroid simply becomes the arithmetic mean of all vectors. This measure
is appropriate if the distribution is Gaussian. It is close to the ML rule in that