Image Processing Reference
In-Depth Information
L
∞
. The number of distances to compute grows
quadratically. For 1000 feature vectors, one would need to compute over half a mil-
lion distances in a multidimensional space. This is one of the limitations making clus-
tering algorithms not so practical for large number of features in high-dimensional
spaces. The other and more serious limitation is that the convergence problem of
the partitioning, which once achieved, is usually not as meaningful as a partitioning
obtained in a (unkown) lower-dimensional subspace. This provides yet another mo-
tivation to dimension reduction followed by image feature smoothing in a pyramid,
before attempting to group image features automatically.
L
1
,
(but very well can be), e.g.,
16.4 Fuzzy C-Means Clustering Algorithm
E
M
, and
N
c
be an
integer
2
representing the number of classes to which the feature vectors can belong.
The
N
c
partitioning of the feature space is represented by the
N
c
×
Let
F
=
f
1
, ...,
f
K
be a finite set of feature vectors with
f
k
∈
K
matrix
U
=
[
u
nk
], consisting of the elements
u
nk
, which represent the membership of feature
vector
vecf
k
to the class
n
. There are
K
feature vectors and
N
c
classes, so that
k
and
n
are integer indices in the ranges 1
,
,N
c
, respectively. In the
hard (or crisp) case, the degree of “belongingness” of feature vector
f
k
to a class
n
is either 1 or 0, i.e.,
···
,K
and 1
,
···
u
nk
=
1
,
f
k
∈
class
n,
0
,
otherwise.
(16.4)
In the fuzzy case,
u
nk
gives the “strength” of the membership of feature vector
f
k
to
class
n
(
u
nk
∈
[0
,
1]). The
degree of belongingness
u
nk
can be intuitively seen as a
distance from feature vector
k
to the class
n
normalized by the sum of distances to
all class centers. This representation is in many cases closer to the physical reality
in the sense that feature vectors almost never fully belong to one class i.e., there is
always a suspicion that an object could have been classified to a different class, albeit
with a lower certainty. The two following conditions have to be respected:
N
c
n
=1
u
nk
=1
,
for all
f
k
,
(16.5)
0
<
k
=1
u
nk
<K,
for all classes
n.
(16.6)
In the crisp case, Eq. (16.5) simply means that feature vector k belongs to one class
only. The second condition Eq. (16.6) means that no class is empty and no class is
all of
F
. The fuzzy C-means algorithm belongs to the class of objective function
methods. Such methods minimize a clustering criterion which is, in this case, the
total within-group sum of squared error (WGSS). The fuzzy C-means is the fuzzy
extension of the hard C-mean. It minimizes the objective function
K
N
c
(
u
nk
)
κ
(
d
nk
(
v
n
,
f
k
))
2
e
κ
(
U
,
V
)=
(16.7)
n
=1
k
=1
2
Evidently we assume that
N
c
∈
2
..K −
1 because if
N
c
=1or
N
c
=
K
, then one would
obtain trivial partitionings.
