C H A P T E R 6
Maps and Distances between
is chapter deals with shape transformations: a transformation, or map, is any function map-
ping a set X to another set Y (or to the set X itself ). e simplest examples are Euclidean trans-
formations: rotation, translation, scaling. A more elaborate question concerns the eﬀect of maps
on shape properties: indeed, transformations can be categorized according to the properties they
preserve while moving from one space to the other. For example, isometries preserve the space
metric structure, meaning that they preserve the distance computed between points: the distance
between two points on the input space X is equal to the distance between the point images in
Y (section 6.1.1). Analogously, aﬃnities are transformations that preserve straight lines (sec-
tion 6.1.2), and Möbius transformations (section 6.1.3) preserve angles.
Strictly related to shape transformations is the concept of distances between shapes. Indeed,
one of the cornerstone problems in shape analysis is how to deﬁne a notion of shape (dis)similarity.
Computing distances between shapes has fundamental applications in shape matching, recogni-
tion and retrieval. Well known examples of distances are the Hausdorﬀ distance (section 6.2.1)
and the bottleneck distance (section 6.2.2), which measure how far two subsets of a metric space
are from each other; the Gromov-Hausdorﬀ distance (section 6.2.3), which casts the comparison
of two metric spaces as a problem of comparing pairwise distances on the spaces. Finally, the
natural pseudo-distance (section 6.2.4) is a measure of how much shape properties are preserved
while transforming a shape into another. Indeed, we may want to analyze to what extent two
spaces represent two instances of some common class, up to a certain notion of invariance. Are an
upright and a downright arrow instances of a common class? Are a standing woman and a sitting
one similar, though their pose is diﬀerent? e answer depends on the application, and on the
properties we want to preserve.
6.1 SPACE TRANSFORMATIONS
An isometry between metric spaces is a distance-preserving transformation: the distance between
points in the image metric space equals the distance between points in the original metric space.
Formally, let .X; d
/ and .Y; d
/ be two metric spaces. A map W X ! Y is called an isometry