43

C H A P T E R 6

Maps and Distances between

Spaces

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

6.1.1 ISOMETRIES

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

X

/ and .Y; d

Y

/ be two metric spaces. A map W X ! Y is called an isometry

Get *Mathematical Tools for Shape Analysis and Description* now with O’Reilly online learning.

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