Graphics Reference
In-Depth Information
the 'unweighted pair group method using arithmetic averages' (UPGMA) yields
d
pk
=
d
kp
=
(n
i
d
pi
+
n
j
d
pj
)/(n
i
+
n
j
)
with
n
i
and
n
j
as the number of data points
in the clusters
i
and
j
, respectively, the 'single linkage clustering method' relies on
the minimum distance
d
pk
=
min
(d
pi
,d
pj
)
, and the 'complete linkage clus-
tering method' on the maximum distance
d
pk
=
d
kp
=
max
(d
pi
,d
pj
)
. For segmen-
tation of a three-dimensional point cloud, the object detection and tracking method
by Schmidt et al. (
2007
) described in Sect.
2.3.4
relies on the complete linkage
clustering method.
d
kp
=
2.3.1.3 Mean-Shift Clustering
The mean-shift clustering approach is a non-parametric clustering technique which
estimates local density maxima of the data points. It is described in detail by Co-
maniciu and Meer (
2002
), who mention as precursors to their approach the works
by Fukunaga and Hostetler (
1975
) and Cheng (
1995
). According to Comaniciu and
Meer (
2002
), the mean-shift algorithm relies on a kernel-based estimation of the
density gradient of the distribution of the
N
data points
x
i
}
i
=
1
,...,N
. The function
k(x)
is termed the 'profile' of the kernel function. Several kernel functions are dis-
cussed by Cheng (
1995
). Comaniciu and Meer (
2002
) state that two important ker-
nel profiles are the Epanechnikov kernel with
k
E
(x)
{
=
1
−
x
for 0
≤
x
≤
1 and
1
k
E
(x)
=
0 otherwise, and the normal kernel
k
N
=
exp
(
−
2
x)
with
x
≥
0. The ker-
2
)
, where
d
is the feature space dimension and
c
k,d
>
0 normalises the kernel function such
that its integral over the complete feature space amounts to unity. To estimate the
density gradient, Comaniciu and Meer (
2002
) define
g(x)
=−
dk(x)/dx
as the pro-
file of the kernel
G(
x
)
=
c
g,d
g(
nel function is assumed to be radially symmetric with
K(
x
)
=
c
k,d
k(
x
2
)
. The mean-shift algorithm is then initialised
with the position
y
0
in the feature space, and the kernel width
h
needs to be given.
The position in the feature space is then updated iteratively for
j>
0 according
to
x
i
=
1
x
i
g(
y
j
−
x
i
2
)
h
y
j
+
1
=
.
(2.32)
i
=
1
g(
y
j
−
x
i
h
2
)
Comaniciu and Meer (
2002
) show that
y
j
converges towards a local maximum of
the point density as long as the profile
k(x)
of the kernel
K(
x
)
is convex and de-
creases monotonically with increasing values of
x
.
2.3.1.4 Graph Cut and Spectral Clustering
A more recent approach to the clustering problem is the normalised graph cuts
method introduced by Shi and Malik (
1997
,
1998
,
2000
), which is closely related
to the method of spectral clustering (Fowlkes et al.,
2004
). In the context of image
segmentation, Shi and Malik (
2000
) model the image in the form of a weighted
Search WWH ::
Custom Search