PA170 Digital Geometry
Lecture 03: Metrics
Martin Maˇska (xmaska@fi.muni.cz)
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno
Autumn 2023
Motivation: How To Measure Distances in Digital Grids
City-block distance Euclidean distance Chessboard distance
2/22
INTRODUCTION TO METRICS
Norms
Let [S, +, ·, R] be an n-dimensional vector space over R. A norm · assigns to any
p ∈ S a nonnegative scalar p that satisfies the following three properties:
N1 Identity
∀p ∈ S : p = 0 iff p = (0, . . . , 0)
N2 Homogeneity
∀p ∈ S, ∀a ∈ R : a · p = |a| · p
N3 Triangle Inequality
∀p, q ∈ S : p + q ≤ p + q
4/22
Metrics
Let S be an arbitrary nonempty set. A function d : S × S → R is a distance function
(metric) on S iff it has the following three properties:
M1 Positive Definiteness
∀p, q ∈ S : d(p, q) ≥ 0 and d(p, q) = 0 iff p = q
M2 Symmetry
∀p, q ∈ S : d(p, q) = d(q, p)
M3 Triangle Inequality
∀p, q, r ∈ S : d(p, r) ≤ d(p, q) + d(q, r)
If · is a norm on [S, +, ·, R], d(p, q) = p − q (∀p, q ∈ S) defines a norm-induced
metric on S
A norm-induced metric has also the following two properties:
M4 Translation Invariance
∀p, q, r ∈ S : d(p + r, q + r) = d(p, q)
M5 Homogeneity
∀p, q ∈ S, ∀a ∈ R : d(a · p, a · q) = |a| · d(p, q)
5/22
Restricting and Combining Metrics
If [S, d] is a metric space and ∅ = A ⊆ S, [A, d] is also a metric space
Metrics on Rn define metrics on Zn, Gm,n, and Gl,m,n
If d is not a metric on A, d is not a metric on any set S containing A either
Any positive linear combination a · d1 + b · d2 and maximum max{d1, d2} of two
metrics d1 and d2 on a set S define a metric on S
The product d1 · d2 and minimum min{d1, d2} are not necessarily metrics on S
6/22
Minkowski Norms and Metrics
Let S = Rn and p = (x1, . . . , xn) ∈ Rn
The Minkowski norms p m on [S, +, ·, R] are defined as:
p m = m
|x1|m + · · · + |xn|m (m = 1, 2, . . . )
p ∞ = max{|x1|, . . . , |xn|}
The Minkowski norms p m on [S, +, ·, R] induce the Minkowski metrics Lm on S:
Lm(p, q) = m
|x1 − y1|m + · · · + |xn − yn|m (m = 1, 2, . . . )
L∞(p, q) = max{|x1 − y1|, . . . , |xn − yn|}
A sequence of Minkowski distances Lm for increasing m is nondecreasing:
∀p, q ∈ Rn
, 1 ≤ m1 ≤ m2 ≤ ∞ : Lm1
(p, q) ≥ Lm2
(p, q)
7/22
Common Metrics on 2D Grids
Let p = (xp, yp) ∈ Z2 and q = (xq, yq) ∈ Z2, we define
City-block metric d4(p, q) = |xp − xq| + |yp − yq| = L1(p, q)
Euclidean metric de(p, q) = (xp − xq)2 + (yp − yq)2 = L2(p, q)
Chessboard metric d8(p, q) = max{|xp − xq|, |yp − yq|} = L∞(p, q)
City-block metric Euclidean metric Chessboard metric
(d4 = L1) (de = L2) (d8 = L∞)
d8(p, q) ≤ de(p, q) ≤ d4(p, q) ≤ 2 · d8(p, q) (∀p, q ∈ Z2)
8/22
Unit Disks
Let S ⊆ R2, o = (0, 0) ∈ S, and d be a metric on S. The set {p ∈ S : d(p, o) ≤ 1} is
called a unit disk in [S, d]
Translation-invariant (M4) and homogeneous (M5) metrics can be compared via their
unit disks
City-block metric Euclidean metric Chessboard metric
(d4 = L1) (de = L2) (d8 = L∞)
9/22
e-Neighborhoods
Let 0 < e ∈ R and d be a metric on a grid G. The set Ne,d (p) = {q ∈ G : d(p, q) < e}
is called an e-neighborhood of a grid point p ∈ G for the metric d
Ne,d4
(p) Ne,de
(p) Ne,d8
(p)
10/22
Integer-Valued Metrics
In digital geometry, the measurements are often based on integer-valued metrics
In contrast to d4 and d8, de is not an integer-valued metric on digital grids
Let a ∈ R, we define
a is the largest integer less than or equal to a (floor)
a is the smallest integer greater than or equal to a (ceil)
[a] is the nearest integer to a if it is unique, and a otherwise (round)
11/22
Integer-Valued Metrics
In digital geometry, the measurements are often based on integer-valued metrics
In contrast to d4 and d8, de is not an integer-valued metric on digital grids
Let a ∈ R, we define
a is the largest integer less than or equal to a (floor)
a is the smallest integer greater than or equal to a (ceil)
[a] is the nearest integer to a if it is unique, and a otherwise (round)
Which of de , de , and [de] is a metric on Zn
?
12/22
Integer-Valued Metrics
In digital geometry, the measurements are often based on integer-valued metrics
In contrast to d4 and d8, de is not an integer-valued metric on digital grids
Let a ∈ R, we define
a is the largest integer less than or equal to a (floor)
a is the smallest integer greater than or equal to a (ceil)
[a] is the nearest integer to a if it is unique, and a otherwise (round)
Which of de , de , and [de] is a metric on Zn
?
de and [de] are not metrics on Zn (M3 is broken)
13/22
Integer-Valued Metrics
In digital geometry, the measurements are often based on integer-valued metrics
In contrast to d4 and d8, de is not an integer-valued metric on digital grids
Let a ∈ R, we define
a is the largest integer less than or equal to a (floor)
a is the smallest integer greater than or equal to a (ceil)
[a] is the nearest integer to a if it is unique, and a otherwise (round)
Which of de , de , and [de] is a metric on Zn
?
de and [de] are not metrics on Zn (M3 is broken)
de is a metric on Zn (If d is a metric on S, d is also a metric on S)
14/22
Regular Metrics
An integer-valued metric d on a set S is called regular iff, for all p, q ∈ S such that
d(p, q) ≥ 2, there exists r ∈ S (r = p and r = q) such that d(p, q) = d(p, r) + d(r, q)
It implies that for all distinct p, q ∈ S, there exists r ∈ S such that d(p, r) = 1 and
d(p, q) = 1 + d(r, q)
d4 and d8 are regular integer-valued metrics on Z2
de is a regular integer-valued metric on Rn but not on Zn (n > 1)
15/22
APPROXIMATION TO THE
EUCLIDEAN METRIC
Motivation: d4 and d8 Are Too Coarse Approximations to de
e-Neighborhoods of de e-Neighborhoods of d4 e-Neighborhoods of d8
17/22
Combining d4 and d8
We can combine d4 and d8 as
d(p, q) = max{d8,
2
3
· d4}
e-Neighborhoods of d(p, q) are upright octagons obtained by intersecting upright
squares of side 2 · e with diamonds of diagonal 3 · e
Regular octagons can be reached by choosing the pair of weights appropriately
e-Neighborhoods of de e-Neighborhoods of max{d8, 2
3 · d4}
18/22
Chamfer Distance
Let p, q ∈ Z2, and let ρ be a sequence of king’s moves from p to q
Let la,b(ρ) = a · m + b · n with m being the number of isothetic moves and n being the
number of diagonal moves
da,b(p, q) = min
ρ
la,b(ρ) is called the (a, b)-chamfer distance from p to q
Generalized chamfer distances can be defined using additional types of moves
e-Neighborhoods of de e-Neighborhoods of d1,
√
2
19/22
Chamfer Distance: Properties
The chamfer distance da,b is a metric if 0 < a ≤ b ≤ 2a
This metric is a nonnegative linear combination of d4 and d8
On a (k + 1)×(k + 1) grid, the chamfer distance d1,b that best approximates de has
b =
1
√
2
+
√
2 − 1 ≈ 1.351 ,
producing a maximum error of
|de − d1,b| ≤
1
√
2
−
√
2 − 1 k ≈ 0.06k
The optimal value of b is close to 4
3 , and thus d3,4 is a good approximation to 3 · de
20/22
Summary: Different Approximations to the Euclidean metric
de d4 d8
max{d8, 2
3 · d4} d1,
√
2 (chamfer distance)
21/22
Take-Home Messages
The city-block (d4) and chessboard (d8) metrics are regular, integer-valued metrics
on digital grids
de is an integer-valued metric on digital grids, but it is not regular
The chamfer distance d3,4 is a regular, integer-valued metric on 2D digital grids,
which provides a good approximation to 3 · de
22/22