Digital Geometry and Mathematical Morphology

February through May, 2004

Christer Kiselman

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 geometry.

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 02, 2003).

The meetings were devoted to the following topics.

1. 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).
2. February 20. Infimal convolution (cont'd). Dilations and erosions.
3. 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.
4. 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.
5. 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 distance transforms.
6. March 18. Chamfer distances on an abelian group. How to construct them using infimal convolution.
7. 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.
8. 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 them?
9. March 30. Definition of skeletons. Zorn's lemma. Existence of skeletons in Zⁿ and Rⁿ. Properties of skeletons. A characterization of skeletons.
10. 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 Rⁿ. Upper and lower inverses of mappings between lattices.
11. 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 interesting topology.
12. April 22. Connectedness. Quotient topologies on Z making it a connected topological space. Separation axioms: T₀ (Kolmogorov's axiom), T₁, T₂ (Hausdorff's axiom). Smallest-neighborhood spaces.
13. April 23. Fixed-point theorems for topological spaces and ordered sets. Fixed-point theorems for the Khalimsky topology (beginning).
14. 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).
15. 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 Z² possessing the chord property is the digitization of a straight line segment.
16. May 06. Hania Uscka-Wehlou and Erik Melin present their latest results on digitization of straight lines.
17. 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 participants.

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