It is easy to show that, in this case, any disc that contains the disc of radius
DT(p) centred at p is not totally included in the set P (e.g. the disc whose
border is shown as a dashed circle in Figure 5.1(B)). This is in contradiction
with Proposition 5.4(ii) and, therefore, (iii) holds. [::]
These properties will be revisited when developing algorithms for the so-
lution of the distance mapping problem and when detailing the relationship
between distance transformations and particular structures found in computa-
tional geometry (see Section 5.4). These properties will prove useful for the
development of models for image representations and will be fully exploited by
algorithms presented in later chapters.
Remark 5.6:
In binary digital image processing, P represents the image, or a part of it (e.g.
the foreground), and is composed of discrete points (i.e. the pixels). For such
a set the definition of the border is given in Definition 1.11. In this case, the
distance map can be represented by a grey-level image where the grey-level at a
pixel represents the value of the distance transformation of the image at this pixel
(see Section 5.~).
5.2 Discrete distance transformations
The case where the distance d(.,.) used in Definition 5.1 is a discrete
distance (as defined in Section 1.4) is studied in this section. Based on the con-
clusions derived in Section 1.4.4, we will mostly concentrate on discrete distances
defined on square lattices. Extensions to hexagonal partitions (i.e. triangular
lattices) will also be developed in this section.
Discrete distances and their properties were studied in Sections 1.4 and
1.5. Clearly, using Definition 5.1, any discrete distance may be used for the
discrete distance mapping [111]. However, chamfer distances are typically sim-
ple to compute and have been shown to be more accurate than other discrete
distances, such as hexagonal and octagonal distances, in the approximation of
the Euclidean distance. The generation of discrete distance maps will therefore
mostly be detailed using chamfer distances. Such discrete distance transforma-
tions and distance maps are also referred to as chamfer distance transformations
and chamfer distance maps, respectively. Note that, in Remark 1.37, it was
pointed out that the d4 and d8 distances can be seen as particular cases of cham-
fer distances.
Two approaches for the computation of discrete distance maps are pre-
sented here. The first approach was introduced in [141,142] and relies on the
definition of a mask corresponding to the neighbourhood around each pixel and

Get Binary Digital Image Processing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.