Three-Dimensional Pose Estimation and Segmentation Methods - 3D Computer Vision: Efficient Methods and Applications - page 121

2.3.1 General Overview

Segmentation of a point cloud corresponds to the subdivision of the cloud into sub-
parts that likely represent different objects. Without a priori knowledge about the
sizes and shapes of the objects encountered in the scene, i.e. in the absence of
model information, an appropriate approach to scene segmentation is clustering,
which corresponds to the subdivision of a set of points into parts consisting of mu-
tually similar points (Press et al., 2007 ; Marsland, 2009 ). These points may e.g.
be three-dimensional points extracted by a scene reconstruction method or three-
dimensional points enriched by velocity information such as optical flow or scene
flow (cf. Sect. 1.5.2.5 ), but may also be data points defined in an abstract feature
space, where the position in the feature space is associated with certain properties.
According to Marsland ( 2009 ), the similarity between the points is measured by
an appropriately defined metric, where the most common choice is the Euclidean
distance between the points. It is important to note that the subdivision of the data
set into clusters is performed without information about the class to which each of
the individual data points belongs, such that clustering is also termed 'unsupervised
learning' (Press et al., 2007 ).

2.3.1.1 The k -Means Clustering Algorithm

An important hierarchical clustering algorithm is the k -means algorithm introduced
by MacQueen ( 1967 ). According to Marsland ( 2009 ), the number k of clusters has
to be given, and k random points are selected as cluster centres. In the first step,
each data point is assigned to the cluster centre with the smallest distance. In the
second step, the new cluster centres are computed as the averages of the data points
according to their assignments in the first step. These two steps are repeated until
the assignment of the data points to the established cluster centres (and thus also the
cluster centres themselves) remains constant. A new, unknown data point is assigned
to the cluster with the smallest distance. Notably, as a consequence of the random
initialisation, the k -means algorithm does not necessarily yield the same result for
different initialisations.

2.3.1.2 Agglomerative Clustering

According to Press et al. ( 2007 ), agglomerative clustering starts with each data
point representing a cluster and combines small clusters into larger ones until a
dissimilarity criterion between the clusters is met. Press et al. ( 2007 ) describe sev-
eral approaches to determine the distances d pk between a newly formed cluster
k and a reference cluster p in comparison to the distances d pi and d pj of the
previous cluster pair (i, j ) to the same reference cluster as a criterion to com-
bine the cluster pair into a new single cluster. Here, the 'weighted pair group
method using arithmetic averages' (WPGMA) implies d pk =

d kp = (d pi + d pj )/ 2,