Elements of Digital Geometry, Mathematical Morphology, and Discrete Optimization

Description

The author presents three distinct but related branches of science in this book: digital geometry, mathematical morphology, and discrete optimization. They are united by a common mindset as well as by the many applications where they are useful. In addition to being useful, each of these relatively new branches of science is also intellectually challenging. The book contains a systematic study of inverses of mappings between ordered sets, and so offers a uniquely helpful organization in the approach to several phenomena related to duality. To prepare the ground for discrete convexity, there are chapters on convexity in real vector spaces in anticipation of the many challenging problems coming up in digital geometry. To prepare for the study of new topologies introduced to serve in discrete spaces, there is also a chapter on classical topology. The book is intended for general readers with a modest background in mathematics and for advanced undergraduate students as well as beginning graduate students. 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