@
Appl. Gen. Topol. 23, no. 1 (2022), 69-77

doi:10.4995/agt.2022.15893

© AGT, UPV, 2022

Beyond the Hausdorff metric in digital topology

Laurence Boxer

Department of Computer and Information Sciences, Niagara University, USA; and

Department of Computer Science and Engineering, State University of New York at Buffalo, USA

(boxer@niagara.edu)

Communicated by J. Rodŕıguez-López

Abstract

Two objects may be close in the Hausdorff metric, yet have very differ-
ent geometric and topological properties. We examine other methods
of comparing digital images such that objects close in each of these
measures have some similar geometric or topological property. Such
measures may be combined with the Hausdorff metric to yield a metric
in which close images are similar with respect to multiple properties.

2020 MSC: 54B20.

Keywords: digital topology; digital image; Hausdorff metric.

1. Introduction

A key question in digital image processing is whether two digital images
A and B represent the same object. If, after magnification or shrinking and
translation, copies A′ and B′ of the respective images have been scaled to ap-
proximately the same size and are located in approximately the same position,
a Hausdorff metric H may be employed: if H(A′,B′) is small, then perhaps A
and B represent the same object; if H(A′,B′) is large, then A and B probably
do not represent the same object. However, the Hausdorff metric is very crude
as a measure of similarity. In this paper, we consider other comparisons of
digital images.

Received 06 July 2021 – Accepted 27 September 2021

http://dx.doi.org/10.4995/agt.2022.15893


L. Boxer

2. Preliminaries

Much of this section is quoted or paraphrased from [10].
We use N to indicate the set of natural numbers, Z for the set of integers,

and R for the set of real numbers.

2.1. Adjacencies. A digital image is a graph (X,κ), where X is a subset of
Zn for some positive integer n, and κ is an adjacency relation for the points
of X. The cu-adjacencies are commonly used. Let x,y ∈ Zn, x 6= y, where we
consider these points as n-tuples of integers:

x = (x1, . . . ,xn), y = (y1, . . . ,yn).

Let u ∈ Z, 1 ≤ u ≤ n. We say x and y are cu-adjacent if
• There are at most u indices i for which |xi −yi| = 1.
• For all indices j such that |xj −yj| 6= 1 we have xj = yj.

Often, a cu-adjacency is denoted by the number of points adjacent to a given
point in Zn using this adjacency. E.g.,

• In Z1, c1-adjacency is 2-adjacency.
• In Z2, c1-adjacency is 4-adjacency and c2-adjacency is 8-adjacency.
• In Z3, c1-adjacency is 6-adjacency, c2-adjacency is 18-adjacency, and
c3-adjacency is 26-adjacency.

We write x ↔κ x′, or x ↔ x′ when κ is understood, to indicate that x and
x′ are κ-adjacent. Similarly, we write x -κ x′, or x - x′ when κ is understood,
to indicate that x and x′ are κ-adjacent or equal.

A subset Y of a digital image (X,κ) is κ-connected [17], or connected when
κ is understood, if for every pair of points a,b ∈ Y there exists a sequence
{yi}mi=0 ⊂ Y such that a = y0, b = ym, and yi ↔κ yi+1 for 0 ≤ i < m.

2.2. Digitally continuous functions. The following generalizes a definition
of [17].

Definition 2.1 ([5]). Let (X,κ) and (Y,λ) be digital images. A single-valued
function f : X → Y is (κ,λ)-continuous if for every κ-connected A ⊂ X we
have that f(A) is a λ-connected subset of Y .

When the adjacency relations are understood, we will simply say that f is
continuous. Continuity can be expressed in terms of adjacency of points:

Theorem 2.2 ([17, 5]). A function f : X → Y is continuous if and only if
x ↔ x′ in X implies f(x) - f(x′).

See also [11, 12], where similar notions are referred to as immersions, grad-
ually varied operators, and gradually varied mappings.

2.3. Pseudometrics and metrics.

Definition 2.3 ([13]). Let X be a nonempty set. Let d : X2 → [0,∞) be a
function such that for all x,y,z ∈ X,

• d(x,y) ≥ 0;

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 70



Beyond the Hausdorff metric in digital topology

• d(x,x) = 0;
• d(x,y) = d(y,x); and
• d(x,z) ≤ d(x,y) + d(y,z).

Then d is a pseudometric for X. If, further, d(x,y) = 0 implies x = y then d is
a metric for X.

Pseudometrics that can be applied to pairs (A,B) of nonempty subsets of a
digital image X include the absolute values of the differences in their

• deviations from convexity. Several such deviations are discussed in [19,
4], for each of which it was shown that two objects can be “close” in
the Hausdorff metric yet quite different with respect to the deviation
from convexity. These can be adapted to digital images with respect
to digital convexity as defined in [7].
• Euler characteristics. I.e., the function

sχ(A,B) = |χ(A) −χ(B)|,

where χ(X) is the Euler characteristic of (X,κ), is a pseudometric for
digital images in Zn. An improper definition of the Euler characteristic
for digital images was given in [15]. An appropriate definition is given
in [8].
• Lusternik-Schnirelman category catκ(X) [1]. I.e., the function

sLS,κ(A,B) = |catκ(A) − catκ(B)|,

where catκ(X) is the Lusternik-Schnirelman category of (X,κ), is a
pseudometric for digital images in Zn.
• diameters. This is discussed below.

The following is easily verified and extends an assertion of [4].

Lemma 2.4. Let ∆i : X
2 → [0,∞) be a pseudometric, 1 ≤ i ≤ n. Then

D =
∑n
i=1 ∆i : X

2 → [0,∞) is a pseudometric. Further, if at least one of the
∆i is a metric, then D is a metric.

Here we mention metrics we use in this paper for Rn or Zn. Let x =
(x1, . . . ,xn), y = (y1, . . . ,yn).

• Let p ≥ 1. The `p metric for Rn is given by

dp(x,y) =

(
n∑
i=1

|xi −yi|p
)1/p

.

The special case p = 1 gives the Manhattan or city block metric d1 :
(Rn)2 → [0,∞), given by

d1(x,y) =

n∑
i=1

|xi −yi|.

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 71



L. Boxer

The special case p = 2 gives the Euclidean metric d2 : (Rn)2 → [0,∞),
given by

d2(x,y) =

(
n∑
i=1

(xi −yi)2
)1/2

.

• The shortest path metric [14]: Let (X,κ) be a connected digital image.
For x,y ∈ X, let

dκ(x,y) = min{n | there is a κ-path of length n in X from x to y.}

• The Hausdorff metric based on a metric d [16]: Let d : X2 → [0,∞) be
a metric where X ⊂ Rn. The Hausdorff metric for nonempty bounded
and closed subsets A and B of X (hence, in the case X ⊂ Zn, finite
subsets of X) based on d is

H(A,B) = min

{
ε > 0 | ∀(a,b) ∈ A×B, ∃ (a′,b′) ∈ A×B
such that ε ≥ d(a,b′) and ε ≥ d(a′,b)

}
.

We make the following modification of the Hausdorff metric based on dκ as
presented in [20].

Definition 2.5. Let X ⊂ Zn, ∅ 6= A ⊂ X, ∅ 6= B ⊂ X. Let κ be an adjacency
on X. Then

H(X,κ)(A,B) = min




ε ≥ 0 | ∀(a,b) ∈ A×B, ∃(a′,b′) ∈ A×B
such that there are κ-paths in X of length ≤ ε
from a to b′ and from b to a′


 .

In the version of the Hausdorff metric based on dκ in [20], X = Zn. We
show below that we can get very different results for the more general situation
∅ 6= X ⊂ Zn.

We use the notations Hd for the Hausdorff metric based on the metric d,
Hp for the Hausdorff metric based on the `p metric dp (i.e., Hp = Hdp), and
H(X,κ) for the Hausdorff metric based on dκ for subsets of X (i.e., Hκ = Hdκ).

Another metric from classical topology that is easily adapted to digital topol-
ogy is Borsuk’s metric of continuity [2, 3] based on a metric d which is typically,
but not necessarily, the Euclidean metric. For digital images (X,κ) and (Y,κ)
in Zn, define the metric of continuity δd(X,Y ) as the greatest lower bound of
numbers t > 0 such that there are κ-continuous f : X → Y and g : Y → X
with

d(x,f(x)) ≤ t for all x ∈ X and d(y,g(y)) ≤ t for all y ∈ Y.

Proposition 2.6. Given finite digital images (X,κ) and (Y,κ) in Zn and a
metric d for Zn, Hd(X,Y ) ≤ δd(X,Y ).

Proof. This is largely the argument of the analogous assertion in [2]. Let u =
Hd(X,Y ). Since X and Y are finite, without loss of generality, there exists
x0 ∈ X such that u = min{y ∈ Y | d(x0,y)}. Then for all κ-continuous
f : X → Y , d(x0,f(x0)) ≥ u. Therefore, δd(X,Y ) ≥ u. �

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 72



Beyond the Hausdorff metric in digital topology

An example for which the inequality of Proposition 2.6 is strict is given in
the following.

Theorem 2.7. Let X = {(x,y) ∈ Z2 | |x| = n or |y| = n}. Let Y =
X \ {(n,n)}. Then, using the Manhattan metric for d and κ = c1, we have
H1(X,Y ) = 1 and δd(X,Y ) ≥ 2n− 1.

Proof. It is clear that H1(X,Y ) = 1.
Notice there is an isomorphism F : (Y,c1) to a subset of (Z,c1). Let f :

X → Y be c1-continuous. By [6], there is a pair of antipodal points P,−P ∈ X
such that |F ◦ f(P) − F ◦ f(−P)| ≤ 1. Since F is an isomorphism, we must
have f(P) -c1 f(−P). We will show that either d(P,f(P)) ≥ 2n − 1 or
d(−P,f(−P)) ≥ 2n− 1, as follows.

If P = (n,u) then −P = (−n,−u). Then:
• If f(P) = (n,−n) then f(−P) ∈{(n−1,−n), (n,−n), (n,−n + 1)}, so
d(−P,f(−P)) ≥ 2n− 1.

• Note (n,n) 6∈ Y so f(P) cannot equal (n,n).
• If f(P) = (n,v) for |v| < n then f(−P) ∈{(n,v−1), (n,v), (n,v + 1)},

so d(−P,f(−P)) ≥ 2n.
The cases P = (−n,u), P = (w,n), and P = (w,−n) are similar. Thus
δd(X,Y ) ≥ 2n− 1. �

We say the diameter of a nonempty bounded set A ⊂ Rn with respect to a
metric d is

diamd(A) = max{d(a,b) |a,b ∈ A}.
We will use the notations diamp for diamdp, and diamκ for diamdκ.

We define a function sd for pairs of nonempty bounded sets in Rn by
sd(A,B) = |diamd(A) −diamd(B)|.

We use notations sp for sdp, and sκ for sdκ.
The following is easily verified.

Lemma 2.8. The function sd is a pseudometric.

3. Comparing (pseudo)metrics on digital images

In this section, we compare the use of some of the (pseudo)metrics discussed
above.

Theorem 3.1. Let A and B be nonempty, bounded subsets of Rn. Let Hp be
the Hausdorff metric based on the `p metric dp and suppose Hp(A,B) ≤ m.
Then sp(A,B) ≤ 2m.

Proof. There exist a,a′ ∈ A such that dp(a,a′) = diamp(A). There exist
b,b′ ∈ B such that dp(a,b) ≤ m and dp(a′,b′) ≤ m. So
diamp(A) = dp(a,a

′) ≤ dp(a,b) + dp(b,b′) + dp(b′,a′) ≤ m + diamp(B) + m
= diamp(B) + 2m.

Similarly, diamp(B) ≤ diamp(A) + 2m. The assertion follows. �

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 73



L. Boxer

Figure 1. Left: Q = [0,n]2Z (here, n = 6).
Right:
S = Q\

[
(
⋃
k∈Z{4k + 1}× [1,n]Z) ∪ (

⋃
k∈Z{4k + 3}× [0,n− 1]Z)

]
(here, n = 6).
Q and S are within 1 with respect to the Hausdorff metric
based on the Manhattan metric; however, they differ consid-
erably with respect to diameter in the shortest path metric.

By contrast, we have the following.

Example 3.2. Let n ∈ N such that n is even. Let Q = [0,n]2Z. Let

S = Q\

[
(
⋃
k∈Z
{4k + 1}× [1,n]Z) ∪ (

⋃
k∈Z
{4k + 3}× [0,n− 1]Z)

]
.

(See Figure 1.) Then s1(Q,S) = 0, but while diamc1 (Q) = 2n, we have
diamc1 (S) = n + n(1 + n/2). Thus sc1 (Q,S) = n

2/2.

Proof. It is easy to see that both Q and S have diagonally opposed points that
are maximally distant in the d1 metric. Therefore, diam1(S) = diam1(Q) = 2n,
so s1(Q,S) = 0.

Diagonally opposed points of Q are maximally separated with respect to dc1 ,
so diamc1 (Q) = 2n. Maximally separated points of S with respect to dc1 are

(0,n) and (n,n) if n = 4k + 2 for some k ∈ Z;
(0,n) and (n, 0) if n = 4k for some k ∈ Z.

In either case, the unique shortest c1-path between maximally separated points
requires n horizontal steps. The number of vertical steps is computed as follows.
There are 1 + n/2 vertical line segments that must be traversed, each of length
n, so the number of vertical steps is n(1 + n/2). Thus the number of steps
between maximally separated members of S is diamc1 (S) = n + n(1 + n/2).

Hence for κ = c1 we have sκ(Q,S) = |n + n(1 + n/2) − 2n| = n2/2. �

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 74



Beyond the Hausdorff metric in digital topology

Figure 2. Digital images A (left) and B (right) for Exam-
ple 3.3, using n = 5. Using the shortest path metric and
either κ = c1 or κ = c2, maximally distant points in A are
(0, 0) and (n, 2), and maximally distant points in B are (n, 0)
and (n, 2).

We do not get an analog of Theorem 3.1 by using the Hausdorff metric based
on an adjacency κ instead of Hp. This is shown in the following example.

Example 3.3. Let A = [0,n]Z × [0, 2]Z. Let B = A \ ([1,n]Z ×{1}). (See
Figure 2.) Then H1(A,B) = 1. However, we have the following.

• For κ = c1, diamκ(A) = n+2 and diamκ(B) = 2n+2, so sκ(A,B) = n.
• For κ = c2, diamκ(A) = n and diamκ(B) = 2n, so sκ(A,B) = n.

Theorem 3.4. Let A and B be finite, nonempty cu-connected subsets of a cu-
connected subset X of Zn, where 1 ≤ u ≤ n. Suppose we have H(X,cu)(A,B) ≤
m for some m ∈ N. Then Hp(A,B) ≤ mu1/p.

Proof. By hypothesis, given x ∈ A and y ∈ B, there exist x′ ∈ A, y′ ∈ B,
and cu-paths P from x to y

′ and Q from y to x′ in X such that each of
P and Q has length of at most m. Since each cu-adjacency corresponds to
a Euclidean distance of at most u1/p, it follows that dp(x,y

′) ≤ mu1/p and
dp(y,x

′) ≤ mu1/p. It follows that Hp(X,Y ) ≤ mu1/p. �

We do not get a converse for Theorem 3.4, as the following shows.

Example 3.5. Let B = [0,n]Z × [0, 2]Z \ ([1,n]Z ×{1}) as in Example 3.3.
(See Figure 2.) Let C = [0,n]Z ×{0} ⊂ B. Then H1(B,C) = H2(B,C) = 2.
However, H(B,c1)(B,C) = n + 2 and H(B,c2)(B,C) = n + 1.

Proof. It is easy to see that H1(B,C) = H2(B,C) = 2.
Since C ⊂ B, finding a Hausdorff distance between B and C comes down to

considering a furthest point of B from C. With respect to κ = c1 and also with
respect to κ = c2, the furthest point of B from C in the shortest path metric
is b = (n, 2) and its closest point of C is c = (0, 0). Since dc1 (b,c) = n + 2 and
dc2 (b,c) = n + 1, the assertion follows. �

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 75



L. Boxer

Roughly, it appears that the great differences found in Examples 3.3 and 3.5,
between measures based in `p metrics and measures based on the shortest
path metric, are due to significant deviations from convexity. If we consider
H(X,ci)(A,B) for a set X such as a digital cube, we may find Hp and H(X,cp)
are more alike, as we see below.

Proposition 3.6. Let A 6= ∅ 6= B, A∪B ⊂ J = [0,m]2Z. Then H1(A,B) =
H(J,c1)(A,B).

Proof. Let n = H1(A,B). Let x ∈ A. Then there exists y ∈ B such that
d1(x,y) ≤ n. By definition of d1, it follows that there is a c1-path in J of length
at most n from x to y. Similarly, given u in B, there is a c1-path in J of length
at most n from u to a point v ∈ A. Therefore, H(J,c1)(A,B) ≤ n = H1(A,B).

Now let n = H(J,c1)(A,B). Then given x ∈ A, there is a c1-path in J of
length at most n from x to some y ∈ B. Similarly, given u ∈ B, there is a c1-
path in J of length at most n from u to some v ∈ A. Since every c1 adjacency
represents a d1 distance of 1, it follows that d1(x,y) ≤ n and d1(u,v) ≤ n.
Thus H1(A,B) ≤ n = H(J,c1)(A,B). The assertion follows. �

Using the observation that a cu-adjacency in Zr, 1 ≤ u ≤ r, represents a
dp distance between the adjacent points that is between 1 and u

1/p, we can
generalize the argument used to prove Proposition 3.6, getting the following.

Theorem 3.7. Let A 6= ∅ 6= B, A ∪ B ⊂ J = [0,m]vZ. Then for 1 ≤ u ≤ v,
H(J,cu)(A,B) ≤ u

1/p ·H(J,cu)(A,B).

4. Further remarks

The Hausdorff metric is often used to compare objects A and B. It is easy
to compute efficiently [18, 9] and gives a good indication of how well each of
its arguments approximates the other with respect to location.

However, two objects may be close in the Hausdorff metric and yet have
very different geometric or topological properties. Lemma 2.4 tells us that by
adding other pseudometrics or metrics, such as those we have discussed, to the
Hausdorff metric, we can get another metric in which closeness is more likely
to validate the parameters as digital images representing the same physical
object.

Acknowledgements. The suggestions and corrections of an anonymous re-
viewer are gratefully acknowledged.

References

[1] A. Borat and T. Vergili, Digital Lusternik-Schnirelmann category, Turkish Journal of
Mathematics 42 (2018), 1845–1852.

[2] K. Borsuk, On some metrizations of the hyperspace of compact sets, Fundamenta Math-

ematicae 41 (1954), 168–202.

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 76



Beyond the Hausdorff metric in digital topology

[3] K. Borsuk, Theory of Retracts, Polish Scientific Publishers, Warsaw, 1967.

[4] L. Boxer, Computing deviations from convexity in polygons, Pattern Recognition Letters

14 (1993), 163–167.
[5] L. Boxer, A classical construction for the digital fundamental group, Journal of Mathe-

matical Imaging and Vision 10 (1999), 51–62 .

[6] L. Boxer, Continuous maps on digital simple closed curves, Applied Mathematics 1
(2010), 377–386.

[7] L. Boxer, Convexity and freezing sets in digital topology, Applied General Topology 22,

no. 1 (2021), 121–137.
[8] L. Boxer, I. Karaca and A. Oztel, Topological invariants in digital images, Journal of

Mathematical Sciences: Advances and Applications 11, no. 2 (2011), 109–140.

[9] L. Boxer and R. Miller, Coarse grained gather and scatter operations with applications,
Journal of Parallel and Distributed Computing 64 (2004), 1297–1320.

[10] L. Boxer and P. C. Staecker, Fundamental groups and Euler characteristics of sphere-like
digital images, Applied General Topology 17, no. 2 (2016), 139–158.

[11] L. Chen, Gradually varied surfaces and its optimal uniform approximation, SPIE Pro-

ceedings 2182 (1994), 300–307.
[12] L. Chen, Discrete Surfaces and Manifolds, Scientific Practical Computing, Rockville,

MD, 2004.

[13] J. Dugundji, Topology, Allyn and Bacon, Boston, 1966.
[14] S.-E. Han, Non-product property of the digital fundamental group, Information Sciences

171 (2005), 73–91.

[15] S.-E. Han, Digital fundamental group and Euler characteristic of a connected sum of
digital closed surfaces, Information Sciences 177 (2007), 3314–3326.

[16] S. B. Nadler, Jr., Hyperspaces of Sets, Marcel Dekker, New York, 1978.

[17] A. Rosenfeld, ‘Continuous’ functions on digital images, Pattern Recognition Letters 4
(1987), 177–184.

[18] R. Shonkwiler, An image algorithm for computing the Hausdorff distance efficiently in
linear time, Information Processing Letters 30, no. 2 (1989), 87–89.

[19] H. I. Stern, Polygonal entropy: a convexity measure, Pattern Recognition Letters 10,

no. 4 (1989), 229–235.
[20] T. Vergili, Digital Hausdorff distance on a connected digital image, Communications

Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics 69, no.

2 (2020), 76–88.

© AGT, UPV, 2022 Appl. Gen. Topol. 23, no. 1 77