Image Processing Reference
In-Depth Information
16.3 Clustering Image Features—Perceptual Grouping
At the coarsest level of the pyramid, a
clustering
algorithm is used to find the differ-
ent classes and their prototypes. It is reasonable to assume that objects with similar
properties belong to the same group or cluster, i.e., they are gathered around the same
prototype. The problem is to find a partition of the feature space into
N
c
homoge-
neous subsets. To solve this problem, a suitable clustering criterion and a similarity
(or dissimilarity) measure have to be defined. Being a statistical tool for grouping,
clustering is also known as
vector quantization
. Advantages include:
•
No training is needed.
•
No statistical distribution of the data is to be estimated.
For the clustering to succeed, the features must be powerful enough to group the
data into
compact volumes
in the feature space, where compactness depends on the
choice of the used metrics in the feature space.
The choice of the number of classes
N
c
, required by most of the clustering al-
gorithms, is considered to be one of the most fundamental problems in cluster anal-
ysis [67]. Usually this information is not known, and partitions of the feature space
for different values of
N
c
are computed.
1
An overview of cluster validity and studies
of this nontrivial problem can be found elsewhere [16]. In the following, we will as-
sume that clustering algorithms in which the number of classes
N
c
(or its equivalent)
has to be given. We will, however, discuss reducing the problem of an exact estima-
tion of the class number by overestimating
N
c
and reassigning small and scattered
classes to a class in the spatial neighborhood.
Using a schematic example, we illustrate the
clustering flow chart
in the feature
space next. For completeness, in the next section we will summarize the fuzzy C-
means clustering algorithm proposed by Bezdek [16], which is an extension of the
idea discussed in the example [11], also known as the ISODATA algorithm. This
algorithm yields reasonable clustering results while being simple.
Example 16.1. We wish to cluster the data shown in the left graph of Fig. 16.3. We
followtheprocessingflowillustratedbythechartontheright.Thenumberofclasses,
N
c
, is assumed to be known. Here
N
c
=3, and the class labels are, circle, rectangle,
and square, for convenience.
1. Start: At random choose
N
c
objects, e.g., 2
,
3
,
8. These will be the initial class
centers(prototypes);assignthemalabeleach,e.g.,circle, rectangle,andsquare.
2. Update partitions: Given the current class centers, assign all objects to one of
the circle, rectangle, or star classes by use of the least distance criterion. This
will yield the current partitioning of the data.
3. Update centers: Given the current partitioning, find the class centers by com-
puting the class means. This will yield the current class centers.
1
Hierarchical clustering techniques do not require the number of classes to be known explic-
itly [28, 191], but they require it implicitly, e.g., they need an input threshold for maximum
within class variance.
