Page 255 - Innovations in Intelligent Machines

248 J. Gaspar et al.
definitions of the distance between shapes. Two very well known are chamfer
distance and the the Hausdorff distance.

Localisation Based on the Chamfer Distance

The chamfer distance is based on the correlation of a template edge-image
with a distance transformed image. The distance transform of an edge-image
is an image of the same size as the original, that indicates at each point the
distance to the closest edge point [6, 36, 16].
9
The chamfer distance transform is computed from an edge-image using
the forward and backward masks shown in Fig. 9 [6, 36]. There are various
possible values for the constants in the masks. We use the values according to
Montanari’s metric [16].
The constants shown in the masks are added to each of the local values
and the resulting value of the mask computation is the minimum of the set.
Both masks are applied along the rows of the initialised image.
Figure 10 shows the distance transform of the edges of an omnidirectional
image. We remove the inner and outer parts of the omnidirectional image as
they contain artifact edges, i.e. edges not related to the scene itself, created
by the mirror rim and the robot plus camera self-occlusion.
Finally, given the distance transform, the chamfer distance of two shapes
is then computed as the correlation:

Fig. 9. Forward and backward masks for computing the distance transform. The
element in bold face indicates the centre of the mask

(a) (b) (c)
Fig. 10. Distance transform: (a) original omnidirectional image, (b) edges found
in an annular region of the omnidirectional image and (c) the distance transform of
the edge-image
9
Not to be confused with the chamfer distance between two shapes. The chamfer
distance transform is an image processing operation useful for computing the
chamfer distance of two shapes.