Elements of Digital Geometry, Mathematical Morphology, and Discrete Optimization

Contents
Preface
Acknowledgments
List of Figures
List of Tables
1. Introduction
1.1 Why digital geometry?
1.2 Why mathematical morphology?
1.3 How is image processing at all possible?
1.4 Why discrete optimization?
1.5 Notes
1.5.1 History of discreteness
1.5.2 Digital geometry and mathematical morpho
1.5.3 Origin the terms in the title of this book
1.6 Exercises
2. Sets, mappings, and order relations
2.1 Introduction
2.2 Sets
2.3 Notation for sets of numbers
2.4 Counting with infinities
2.5 The floor and ceiling functions
2.6 Relations and mappings
2.6.1 Linear and affine mappings
2.7 Preorders
2.8 Mappings between preordered sets
2.9 Epigraphs and hypographs
2.10 Calculating with sets and functions
2.11 Cleistomorphisms and anoiktomorphisms
2.12 How to measure distribution of sizes?
2.13 Notes
2.14 Exercises
3. Morphological operations: Set-theoretical duality
3.1 Groups and semigroups
3.2 Dilations and erosions: Set-theoretical duality
3.3 Convolution
3.4 Infimal convolution
3.5 Approximation using infimal convolution
3.6 Iterated infimal convolutions
3.7 A more general infimal convolution
3.8 Restricted Minkowski addition
3.9 Combining dilations and erosions
3.10 Commuting with translations
3.11 Matheron's structural theorems
3.12 Notes
3.12.1 The most fundamental concepts
3.12.2 Addition and subtraction
3.12.3 Terms used, and their origin
3.12.4 Notation
3.13 Exercises
4. Complete lattices
4.1 Introduction
4.2 Definitions and examples
4.2.1 Distributive, modular and complemented lattices
4.3 Moore families and dual Moore families
4.4 Dilations and erosions in complete lattices
4.5 Notes
4.5.1 The sources
4.5.2 Terms used
4.6 Exercises
5. Inverses and quotients of mappings
5.1 Introduction
5.2 Defining inverses of mappings
5.3 First properties of inverses
5.4 Left inverses
5.5 Right inverses
5.6 Inverses of inverses
5.7 Special cases of inverses
5.7.1 Galois connections
5.7.2 Residuation
5.7.3 Adjunctions
5.7.4 Asplund distances
5.7.5 Rådström's definition of smooth functions on arbitrary sets
5.8 Examples of upper and lower inverses
5.9 Quotients of mappings
5.10 Pullbacks and pushforwards
5.11 Notes
5.11.1 Inverses and their relatives
5.11.2 Infimal convolution
5.11.3 Fuzzy sets
5.12 Exercises
6. Structure theorems for mappings
6.1 Set-theoretical representation of dilations, erosions, cleistomorphisms, and anoiktomorphisms
6.2 Anoiktomorphisms as quotients
6.3 Increasing mappings as suprema of elementary erosions
6.4 Anoiktomorphisms as suprema of elementary anoiktomorphisms
6.5 Strong ethmomorphisms
6.6 Notes
6.7 Exercises
7. Digitization
7.1 Introduction
7.2 Serra's four principles on gathering information
7.3 Distances and metric spaces
7.4 Discrete sets and uniformly discrete sets
7.5 To discretize a function
7.6 Discretization by balayage
7.7 Voronoi cells
7.8 Difficulties in logic
7.9 Comparing differences and derivatives
7.10 Notes
7.11 Exercises
8. Digital straightness and digital convexity
8.1 Introduction
8.2 Digital lines and Rosenfeld's chord property
8.3 Difference operators
8.4 Real-valued functions on the integers
8.5 Functions taking real values on Zn
8.6 Characterization of straightness: The chord property
8.7 Characterization of straightness: Balanced words
8.8 Hyperplanes in the sense of Reveillès
8.9 Refined digital hyperplanes
8.10 Extending rectilinear segments
8.11 Notes
8.11.1 Difference operators
8.11.2 Sources
8.11.3 Etymology
8.12 Exercises
9. Convexity in vector spaces
9.1 Introduction
9.2 Defining convex sets
9.3 Properties of convex sets
9.4 The convex hull
9.5 The Hahn–Banach theorem
9.6 Supporting hyperplanes
9.7 Caratheodory's theorem
9.8 Approximation of the convex hull
9.9 Defining convex functions
9.10 Properties of convex functions
9.11 Strict and strong convexity
9.12 Functions taking the value minus infinity
9.13 The convex envelope
9.14 Approximation of the convex envelope
9.15 Separating hyperplanes
9.16 Normed spaces
9.17 Duality in convex analysis
9.17.1 The support function
9.17.2 The Fenchel transformation
9.18 Duality of infimal convolution and addition
9.19 Comparing two convolution operations
9.20 Coppel's axioms
9.21 Three fundamental properties
9.21.1 Property 1: Images of convex sets
9.21.2 Property 2: Local minima are global
9.21.3 Property 3: Separating hyperplanes
9.22 Notes
9.22.1 Sources for convexity theory
9.22.2 The Kuratowski–Zorn lemma
9.22.3 Terms used
9.23 Exercises
10. Discrete convexity
10.1 Introduction
10.2 Restrictions and extensions of functions
10.3 Convexity with respect to a subset of a vector space
10.4 The integer neighborhood and the canonical extension
10.5 Properties of the canonical extension
10.6 Integral convexity
10.7 Lateral convexity: Definitions
10.8 Lateral convexity: Morphological aspects
10.9 Lateral convexity: Examples
10.10 Representations in terms of elementary convex functions
10.11 Separating partially discretized sets
10.12 Separating completely discretized sets
10.13 Possible future studies
10.14 Notes
10.14.1 Other convexity properties
10.14.2 Difference operators and discrete convexity
10.14.3 Invariance properties
10.14.4 Discrete convexity, symmetry, and asymmetry
10.14.5 Terms used
10.15 Exercises
11. Discrete convexity in two dimensions
11.1 Jensen's inequality in the discrete case
11.2 Discrete convexity and the chord property
11.3 Submodular and separable functions
11.4 The piecewise separately ane extension
11.5 Rhomboidal convexity
11.6 Conditions for rhomboidal convexity
11.7 Independence of the conditions for rhomboidal convexity
11.8 The maximal set of pairs which defines rhomboidal convexity
11.9 (Z × R)-convexity and separate (Z × R)-convexity
11.10 Smooth rhomboidally convex functions
11.11 Extending functions from integer points
11.11.1 Extension of separately (Z × R)-convex functions
11.11.2 Extension of (Z2 × R)-convex functions
11.11.3 Extension of rhomboidally convex functions
11.12 Conditions for digital straightness
11.13 What is the result when we digitize a Euclidean line?
11.14 Discretizations of a function
11.14.1 Convexity of a discretized function
11.14.2 Regular and irregular points
11.15 Extending convex extensible functions
11.16 Possible future studies
11.17 Notes
11.17.1 Digital lines have many expressions
11.17.2 Another definition of convexity
11.17.3 Digital hyperplanes
11.17.4 Recognizing digital lines and finding the convex hull
11.17.5 Terms used
11.18 Exercise
12. Three problems in discrete optimization
12.1 Introduction
12.2 Three fundamental problems
12.2.1 Problem 1: Wild marginal functions
12.2.2 Problem 2: Local minima are not global
12.2.3 Problem 3: No separating plane
12.3 Solution to Problem 1: Marginal functions
12.4 Solution to Problem 2: Local minima
12.5 Solution to Problem 3: Separating hyperplanes
12.5.1 Separating planes in dimension three
12.5.2 Separating planes in dimension four
12.6 The marginal function of a function of integer variables
12.7 Convolution and convex extensibility
12.8 The set where the infimum is attained
12.9 Lateral convexity of marginal functions
12.9.1 Arbitrary dimensions
12.9.2 The case of two variables
12.9.3 Symmetric and asymmetric conditions
12.10 Necessity of lateral convexity
12.11 Possible future studies
12.12 Notes
12.13 Exercises
13. Duality of convolution operators
13.1 Introduction
13.2 Properties of convolution
13.2.1 Associativity is problematic
13.2.2 Convolution in some special cases
13.2.3 Associativity does hold under stringent conditions
13.3 Families of functions under duality
13.3.1 Duality for functions of one variable
13.3.2 Duality for functions of several variables
13.4 Duality between classes of functions and second-order di erence operators
13.5 More general convolution operators
13.6 Discrete convexity defined by convolution
13.7 Possible future studies
13.8 Notes
13.8.1 Ubiquity of duality
13.8.2 Convexity of marginal functions
13.8.3 The supremum of a family of functions
13.9 Exercises
14. Topology
14.1 Introduction
14.2 Mappings
14.3 Defining topologies
14.4 Transporting topologies
14.5 Continuous mappings
14.6 Connectedness
14.7 Quotient spaces
14.8 Separation axioms
14.9 Continuous mappings vs. increasing mappings
14.10 Matheron's hit-or-miss topology
14.11 Notes
14.12 Exercises
15. The Khalimsky topology
15.1 Introduction
15.2 Smallest-neighborhood spaces
15.3 Continuity for the Khalimsky topology
15.4 Digitization of straight lines in the Khalimsky plane
15.5 Fixed-point theorems
15.6 Jordan curve theorems
15.6.1 Adjacency
15.6.2 Paths, arcs and Jordan curves in the Khalimsky plane
15.6.3 Khalimsky's digital Jordan curve theorem
15.6.4 The Jordan curve theorem for the Wyse–Marcus topology
15.6.5 Tessellation by hexagons
15.7 Notes
15.8 Exercises
16. Distance transformations
16.1 Defining distances
16.2 Translation-invariant distances
16.3 Distance transforms
16.4 Distance transforms and sublevel sets
16.5 Finitely generated distances
16.6 Comparing distances
16.7 The calculus of balls
16.7.1 Identifying balls with a common center
16.7.2 Three concepts of regularity for metrics
16.7.3 Identifying balls with different centers
16.7.4 Strict and non-strict balls
16.8 Distance transforms in normed vector spaces
16.8.1 The distance transform of a convex set
16.8.2 Distance transforms under duality
16.9 Notes
16.9.1 Sources
16.9.2 Terms used
16.10 Exercises
17. Skeletonizing
17.1 Introduction
17.2 Defining skeletons, medial axes, and nervures
17.3 Comparing medial axes, nervures, and skeletons
17.4 Existence of skeletons
17.5 Properties of skeletons
17.6 Notes
17.6.1 Sources
17.6.2 Terms used
17.7 Exercises
18. Solutions
Chapter 2: Sets, mappings, and order relations
Chapter 3: Morphological operations: Set-theoretical duality
Chapter 4: Complete lattices
Chapter 5: Inverses and quotients of mappings
Chapter 6: Structure theorems for mappings
Chapter 7: Digitization
Chapter 8: Digital straightness and digital convexity
Chapter 9: Convexity in vector spaces
Chapter 10: Discrete convexity
Chapter 11: Discrete convexity in two dimensions
Chapter 12: Three problems in discrete convexity
Chapter 13: Duality of convolution operators
Chapter 14: Topology
Chapter 15: The Khalimsky topology
Chapter 16: Distance transforms
Chapter 17: Skeletonizing
Bibliography
Author Index
Subject Index