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

undirected graph, where each node is assigned to a pixel while an edge of the graph
is defined by a pair of pixels. The similarity between the pixel pair determines the
weight of an edge. Removing the edges connecting the segments out of which the
image consists leads to a segmentation of the image into disjoint sets. The optimal
subdivision is the configuration with the minimal removed edge weights, which is
termed the 'cut'. Hence, such techniques are also known as 'graph cut' methods.
They have become fairly popular in the domain of image segmentation.
Fowlkes et al. ( 2004 ) assume that a number of N image pixels is given by their
previously determined properties such as position, grey value, texture, or depth. The
basis of spectral clustering is the N N symmetric similarity matrix W of the graph.

The set of nodes is denoted by V . When a bipartition of V is given by A and B with
A

×

∪ B = V and A ∩ B = 0, the 'cut' is defined by

cut (A, B) = W ij . (2.33)

i ∈ A j ∈ B

The degree d i of node i corresponds to d i = j W ij , and the volumes of A and B

are given by vol (A) = i ∈ A d i and vol (A) = i ∈ B d i . The 'normalised cut' is then
defined according to

2 cut (A, B)
vol (A)

ncut (A, B) = (2.34)

vol (B)

with the harmonic mean a b) . At this point it is desired to determine

the graph bipartition which minimises the value of ncut (A, B) . A solution of this
complex optimisation problem based on an eigenvalue decomposition of the Lapla-
cian matrix

b = 2 ab/(a +

W)D − 1 / 2 with the diagonal matrix D containing the
values d i as diagonal elements is proposed by Shi and Malik ( 2000 ). Fowlkes et al.
( 2004 ) extend the clustering framework towards more than two groups. The compu-
tational effort of the graph cut approach may become considerable, as it increases
quadratically with the number of pixels. Hence, Fowlkes et al. ( 2004 ) suggest that
one utilise the Nyström method to obtain an approximate solution of the eigensys-
tem.

D − 1 / 2 (D L = −

2.3.1.5 The ICP Algorithm

A method to register a point cloud to a geometric object model is the iterative closest
point (ICP) algorithm introduced by Besl and McKay ( 1992 ). Given an initial esti-
mate of the object pose, the pose parameters are updated by minimising the mean
squared distance between the measured data and the model, and a new assignment
of measured points to model points is performed. This procedure is applied in an it-
erative manner. As a result, the algorithm yields the three-dimensional object pose.
Besl and McKay ( 1992 ) apply this method to point clouds, parametric and non-
parametric curves, and to parametric, non-parametric, and triangulated (tessellated)
surfaces. In the ICP algorithm proposed by Zhang ( 1992 ), the scene points as well
as the object model are represented as connected ('chained') points. During each