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