Mathematics of shape description: A morphological approach to image processing and computer graphics

MATHEMATICS OF SHAPE DESCRIPTION......Page 2
Contents......Page 10
Foreword......Page 16
Preface......Page 18
1.1 Shape Description: What It Means to Us......Page 20
1.2 Pure versus Pragmatic Approaches......Page 22
1.3 The In.uence of the Digital Computer on Our Approach to Shape Description......Page 24
1.4.1 A Mathematical Model for Shape Description and Associated Problems......Page 25
1.4.2 The Need for a Metamodel......Page 27
1.4.3 Reformulating the Metamodel to Adapt to the Pragmatic Approach......Page 31
1.5 The Metamodel within the Framework of Formal Language......Page 35
1.5.1 An Introduction to Formal Languages and Grammars......Page 36
1.5.3 An Exploration of Shape Description Schemes in Terms of Formal Language Theory......Page 39
1.6.2 A Few Guiding Principles......Page 44
1.7.1 Underlying Assumptions when Mapping from the Real World to a Mathematical System......Page 56
1.7.2 Fundamental Mathematical Structures and Their Various Compositions......Page 58
2.1.1 De.nition of Sets......Page 62
2.1.3 Speci.cations for a Set to Describe Shapes......Page 63
2.2 Equality and Inclusion of Sets......Page 64
2.3.1 The Power Set......Page 66
2.3.5 Set Complement......Page 67
2.3.7 Venn Diagrams......Page 68
2.3.8 Cartesian Products......Page 69
2.4.1 Fundamental Concepts......Page 71
2.4.2 The Properties of Binary Relations in a Set......Page 72
2.4.3 Equivalence Relations and Partitions......Page 74
2.4.4 Order Relations......Page 76
2.5.1 Fundamental Concepts......Page 78
2.5.2 The Graphical Representations of a Function......Page 81
2.5.3 The Range of a Function, and Various Categories of Function......Page 84
2.5.4 Composition of Functions......Page 85
2.5.5 The Inverse Function......Page 87
2.5.6 The One-to-One Onto Function and Set Isomorphism......Page 90
2.5.7 Equivalence Relations and Functions......Page 91
2.5.8 Functions of Many Variables, n-ary Operations......Page 93
2.5.9 A Special Type of Function: The Analytic Function......Page 94
3.1 What is an Algebraic Structure?......Page 96
3.1.1 Algebraic Systems with Internal Composition Laws......Page 98
3.1.2 Algebraic Systems with External Composition Laws......Page 100
3.2 Properties of Algebraic Systems......Page 102
3.2.3 Distributivity......Page 103
3.2.4 The Existence of the Identity/Unit Element......Page 104
3.2.5 The Existence of an Inverse Element......Page 105
3.3 Morphisms of Algebraic Systems......Page 106
3.4 Semigroups and Monoids: Two Simple Algebraic Systems......Page 111
3.5.1 Fundamentals......Page 113
3.5.2 The Advantages of Identifying a System as a Group......Page 119
3.5.3 Transformation Groups......Page 120
3.6.1 The Action of a Group on a Set......Page 122
3.6.2 Translations and the Euclidean Group......Page 124
3.6.3 The Matrix Group......Page 125
3.7.1 The Symmetry Groups of the Regular Solids......Page 126
3.8 Rings......Page 131
3.8.1 De.nitions and Examples......Page 132
3.8.2 Some Classes of Rings......Page 135
3.8.3 The Ring of Quaternions and Rotation of Objects......Page 137
4.1 The Objective of Shape Description Modeling......Page 144
4.2.1 The Model......Page 146
4.2.2 The Shape Operator......Page 147
4.3 The Mathematical Nature of the Shape Operators......Page 151
4.3.1 The Minkowski Addition Operator......Page 152
4.3.2 The Minkowski Decomposition Operator......Page 154
4.4.1 A Natural Description Tool......Page 158
4.4.2 The Large Domain of the Model......Page 159
4.4.3 Conciseness in Shape Representation......Page 162
4.4.4 The Geometric Nature of the Shape Operators......Page 163
4.5.1 Better Shape Representation......Page 164
4.5.2 A Procedural Model......Page 165
4.5.3 The Internal Structure of a Model......Page 166
4.5.4 Concise Representation......Page 167
4.6.1 Mathematical Morphology......Page 169
4.6.2 Morphological Operators......Page 170
4.6.3 Morphology of Multivalued Figures......Page 173
4.6.4 Morphological Expansion......Page 174
4.6.5 The Morphological Skeleton and its Properties......Page 175
4.6.6 Morphological Decomposition of Figures......Page 177
4.7.2 Minkowski Operations on Dynamically Varying Shapes......Page 182
4.7.3 Inverse Shapes......Page 183
5.1.1 Does Negative Shape Exist?......Page 184
5.1.2 What Form Must Negative Shapes Take?......Page 185
5.2.1 Morphology for High-Level Vision......Page 186
5.2.2 The Resemblance between Morphology and the Theory of Numbers......Page 187
5.3.1 The Support Function Representation......Page 188
5.3.2 The Support Function is a Signed Distance......Page 189
5.3.3 From Support Function Representation to Boundary Representation and Vice Versa......Page 191
5.3.4 Necessary and Suf.cient Conditions for a Function to be a Support Function......Page 192
5.4.1 MAX and MIN Operations (Convex Hull and Intersection)......Page 193
5.4.2 Morphological Operations in Boundary Representation......Page 196
5.5.1 Computation by Means of Support Function Vectors......Page 197
5.5.2 Computation by Means of Edges: The Emergence of the Boundary Addition Operation......Page 200
5.5.3 Computation by Means of Slope Diagrams: The Uni.cation of Minkowski Addition and Decomposition......Page 201
5.5.4 The Computation of Boundary Addition......Page 202
5.6.1 Computation by Means of Faces......Page 205
5.6.2 The Slope Diagram Representation of a Convex Polyhedron......Page 207
5.6.3 Computation by Means of Slope Diagrams......Page 211
6.1.1 A Localized De.nition of F(A, u)......Page 214
6.1.2 The Anomalous Behavior of the Outer Normals at the Nonconvex Faces......Page 215
6.1.3 The Need to Maintain Explicit Topological Information about the Operands......Page 216
6.2.1 The Boundary Addition of Nonconvex Polygons by Means of Slope Diagrams......Page 217
6.2.2 Boundary Operations on Nonconvex Polygons – More Complex Cases......Page 220
6.3.1 The Uni.ed Algorithm......Page 224
6.3.2 A Complexity Analysis of the Uni.ed Algorithm......Page 226
6.3.3 Simpli.cation of the Uni.ed Algorithm Depending on the Type of Input......Page 227
7.1.1 The Problem and its Motivation......Page 234
7.1.2 Earlier Works......Page 236
7.2.1 Transforming Binary Images into Polygons......Page 238
7.2.2 The Weakly Taxicab Convex Class of Polygons......Page 239
7.2.3 A Few Properties of WTC Polygons Related to Minkowski Operations......Page 242
7.3.1 Representation of WTC Polygons......Page 245
7.3.2 The Minkowski Addition of Two WTC Polygons......Page 248
7.4.1 The Number of Indecomposable Shapes......Page 253
7.4.2 Identifying Indecomposable Polygons within the WTC Domain......Page 255
7.4.3 Simple Indecomposability Tests......Page 260
7.5 A Brief Summing Up......Page 261
7.5.1 Why Does the Uniqueness of Shape Decomposition Fail?......Page 262
7.5.4 Can We Devise Laws of Exponents, and Eventually Binomial Formulas for Shapes?......Page 263
References......Page 266
Index......Page 270