Digital Geometry and Mathematical Geometry
Digital Geometry and
February through May, 2004
This was a course for undergradute students and beginning graduate
students in mathematics and related subjects.
Straight lines and planes have been studied during more than two
thousand years, and curves like circles, ellipses, parabolas and
hyperbolas for almost as long. Other curves, like lemniscates and
cardioids, have been subjects of our curiousity for several centuries.
For these studies we have been relying on drawings by pens on paper.
The visualization by means of drawings has been essential for our
perception of all kinds of geometric objects.
Nowadays more and more images are created by computers and viewed
on a screen rather than on paper. Then every figure consists of a
finite number of pixels. This means that the role of coordinates is
no longer played by real numbers but by integers, serving as addresses
of the pixels. It also means that the geometry of the computer screen
no longer is that of Euclid, equipped with the coordinates of
Cartesius, but something very different, called digital
One might think that digital geometry is but an approximation of
the Euclidean. In fact it is a geometry in its own right and quite
exact. However, it stretches our intuition. For instance, how can a
curve consist of only finitely many points? What continuity
properties can such a curve have? Can it enclose points? Is that not
as vane as trying to build a fence out of poles and no wires? In this
course I shall try to clarify and illustrate these and other aspects
of digital geometry.
Mathematical morphology can be described as the science
of transforming images. Perhaps one could say that it serves for
images as Fourier analysis serves for sounds. Using Fourier analysis
one can analyze and manipulate sounds, e.g., remove noise. Using
mathematical morphology one can in a similar way analyze and
manipulate images. Why are two different techniques relevant for
sounds and images? The reason is very simple: our eyes behave
differently from our ears. The foundations of this technique will
also be studied during the course.
The course plan has been approved
by the Faculty of Science and Technology on May 13, 2002 (revised June
The meetings were devoted to the following topics.
- February 17. Introduction. Ola Weistrand introduces the lab
assignments. Why digital geometry? Why mathematical morphology?
Morphological operations on sets and functions. Minkowski addition of
sets. Infimal convolution (beginning).
- February 20. Infimal convolution (cont'd). Dilations and
- March 02. Duality of dilations and erosions. Preordered sets,
ordered sets, equivalence relations, closings and openings in ordered
sets. Closings and openings as compositions of dilations and erosions.
- March 05. Matheron's first structure theorem: erosions and
dilations as building blocks for more general mappings. The smallest
and largest extensions of an increasing mapping from a subset of
P(X) to P(X). An opening g as the
smallest extension of the identity on the g-invariant elements.
Matheron's second structure theorem: the elementary openings and
closings as building blocks for all openings and closings. Definition
of distance transforms.
- March 17. Lipschitz continuity of distance transforms: the
Lipschitz constant is 2, but the positive and negative parts have
Lipschitz constant 1. In a normed space the Lipschitz constant is 1.
Distance transforms as infimal convolutions. The sublevel sets of
- March 18. Chamfer distances on an abelian group. How to
construct them using infimal convolution.
- March 23. Comparing distances: three criteria for comparing a
distance with the Euclidean metric (Borgefors 1984, Verwer 1991, and a
new measure). The calculus of balls: when is a ball contained in
another ball? Remarks on the calculus of balls in a space such that
all open balls are closed.
- March 24. Distance transforms in normed vector spaces. The
supporting function of a set in a vector space. The Fenchel transform
of a function defined on a vector space. Relations between distance
transforms and supporting functions. Skeletons: what do we want from
- March 30. Definition of skeletons. Zorn's lemma. Existence of
skeletons in Zn and
Rn. Properties of skeletons. A
characterization of skeletons.
- April 01. Lattices: definitions and simple properties. Complete
lattices. The notions of sublattice and sub-complete-lattice.
Examples: the lattices of compact (respectively convex and compact,
respectively closed) subsets of Rn. Upper
and lower inverses of mappings between lattices.
- April 15. Notions of topology: open sets, closed sets,
neighborhoods, topological closure, interior. To pull back a
topology; to push forward a topology. The set of integers Z
viewed as a subspace of R yields the discrete topology; if we
view it instead as a quotient space of R, we get a much more
- April 22. Connectedness. Quotient topologies on
Z making it a connected topological space. Separation axioms:
T0 (Kolmogorov's axiom),
T1, T2 (Hausdorff's axiom).
- April 23. Fixed-point theorems for topological spaces and ordered
sets. Fixed-point theorems for the Khalimsky topology (beginning).
- April 28. The continuous dependence of fixed points on
parameters. Khalimsky intervals, Khalimsky circles. Digital Jordan
curves as homeomorphic images of Khalimsky circles. The digital
Jordan curve theorem (with an idea of the proof).
- April 29. Digitization. Voronoi cells. Digital lines. Azriel
Rosenfeld's theorem: The digitization of a line segment possesses the
chord property. Conversely, a finite subset of Z2
possessing the chord property is the digitization of a straight line
- May 06. Hania Uscka-Wehlou and Erik Melin present their latest
results on digitization of straight lines.
- May 11. Ola Weistrand discusses the lab assignments. Division of
mappings between lattices. Structure theorems in lattice morphology.
Inf-filters, sup-filters and strong filters in lattices.
I have written lecture notes entitled Digital Geometry and Mathematical
Morphology, 95 pages, and distributed them to all
Det finns en populärvetenskaplig
uppsats på svenska om digital geometri.
Ekzistas popularscienca artikolo en
esperanto pri di^gita geometrio.
There are two lab assignments
constructed by Ola Weistrand: 1. Mathematical morphology and
2. Distance transformations.
They can be downloaded from
the address indicated.
There is also be a set of exercises after each chapter in the lecture notes.
To be approved, a student must complete successfully both lab
assignments as well as a reasonable number of the exercise problems,
with a fair distributions over the chapters.
Christer Kiselman 2004-01-14. Last update 2005-06-11.