# Mathematics of Shape Description: A Morphological Approach to Image Processing and Computer Graphics

# Mathematics of Shape Description: A Morphological Approach to Image Processing and Computer Graphics

ISBN: 978-0-470-82309-5

Jan 2010

264 pages

## Description

Image processing problems are often not well defined because real images are contaminated with noise and other uncertain factors. In*Mathematics of Shape Description*, the authors take a mathematical approach to address these problems using the morphological and set-theoretic approach to image processing and computer graphics by presenting a simple shape model using two basic shape operators called Minkowski addition and decomposition.

This book is ideal for professional researchers and engineers in Information Processing, Image Measurement, Shape Description, Shape Representation and Computer Graphics. Post-graduate and advanced undergraduate students in pure and applied mathematics, computer sciences, robotics and engineering will also benefit from this book.

**Key Features**

- Explains the fundamental and advanced relationships between algebraic system and shape description through the set-theoretic approach
- Promotes interaction of image processing geochronology and mathematics in the field of algebraic geometry
- Provides a shape description scheme that is a notational system for the shape of objects
- Offers a thorough and detailed discussion on the mathematical characteristics and significance of the Minkowski operators

**Foreword.**

**Preface.**

**1 In Search of a Framework for Shape Description.**

1.1 Shape Description: What It Means to Us.

1.2 Pure versus Pragmatic Approaches.

1.3 The Influence of the Digital Computer on Our Approach to Shape Description.

1.4 A Metamodel for Shape Description.

1.4.1 A Mathematical Model for Shape Description and Associated Problems.

1.4.2 The Need for a Metamodel.

1.4.3 Reformulating the Metamodel to Adapt to the Pragmatic Approach.

1.5 The Metamodel within the Framework of Formal Language.

1.5.1 An Introduction to Formal Languages and Grammars.

1.5.2 A Grammar for the Constructive Part of the Metamodel.

1.5.3 An Exploration of Shape Description Schemes in Terms of Formal Language Theory.

1.6 The Art of Model Making.

1.6.1 What is the Meaning of ""Model""?

1.6.2 A Few Guiding Principles.

1.7 Shape Description Schematics and the Tools of Mathematics.

1.7.1 Underlying Assumptions when Mapping from the Real World to a Mathematical System.

1.7.2 Fundamental Mathematical Structures and Their Various Compositions.

**2 Sets and Functions for Shape Description.**

2.1 Basic Concepts of Sets.

2.1.1 Definition of Sets.

2.1.2 Membership.

2.1.3 Specifications for a Set to Describe Shapes.

2.1.4 Special Sets.

2.2 Equality and Inclusion of Sets.

2.3 Some Operations on Sets.

2.3.1 The Power Set.

2.3.2 Set Union.

2.3.3 Set Intersection.

2.3.4 Set Difference.

2.3.5 Set Complement.

2.3.6 Symmetric Difference.

2.3.7 Venn Diagrams.

2.3.8 Cartesian Products.

2.4 Relations in Sets.

2.4.1 Fundamental Concepts.

2.4.2 The Properties of Binary Relations in a Set.

2.4.3 Equivalence Relations and Partitions.

2.4.4 Order Relations.

2.5 Functions, Mappings, and Operations.

2.5.1 Fundamental Concepts.

2.5.2 The Graphical Representations of a Function.

2.5.3 The Range of a Function, and Various Categories of Function.

2.5.4 Composition of Functions.

2.5.5 The Inverse Function.

2.5.6 The One-to-One Onto Function and Set Isomorphism.

2.5.7 Equivalence Relations and Functions.

2.5.8 Functions of Many Variables, *n*-ary Operations.

2.5.9 A Special Type of Function: The Analytic Function.

**3 Algebraic Structures for Shape Description.**

3.1 What is an Algebraic Structure?

3.1.1 Algebraic Systems with Internal Composition Laws.

3.1.2 Algebraic Systems with External Composition Laws.

3.2 Properties of Algebraic Systems.

3.2.1 Associativity.

3.2.2 Commutativity.

3.2.3 Distributivity.

3.2.4 The Existence of the Identity/Unit Element.

3.2.5 The Existence of an Inverse Element.

3.3 Morphisms of Algebraic Systems.

3.4 Semigroups and Monoids: Two Simple Algebraic Systems.

3.5 Groups.

3.5.1 Fundamentals.

3.5.2 The Advantages of Identifying a System as a Group.

3.5.3 Transformation Groups.

3.6 Symmetry Groups.

3.6.1 The Action of a Group on a Set.

3.6.2 Translations and the Euclidean Group.

3.6.3 The Matrix Group.

3.7 Proper Rotations of Regular Solids.

3.7.1 The Symmetry Groups of the Regular Solids.

3.7.2 Finite Rotation Groups in Three Dimensions.

3.8 Rings.

3.8.1 Definitions and Examples.

3.8.2 Some Classes of Rings.

3.8.3 The Ring of Quaternions and Rotation of Objects.

**4 Morphological Models for Shape Description and Minkowski Operators.**

4.1 The Objective of Shape Description Modeling.

4.2 The Basic Idea of Model Description.

4.2.1 The Model.

4.2.2 The Shape Operator.

4.3 The Mathematical Nature of the Shape Operators.

4.3.1 The Minkowski Addition Operator.

4.3.2 The Minkowski Decomposition Operator.

4.4 A Few Reasons for Choosing Minkowski Operators as Shape Operators.

4.4.1 A Natural Description Tool.

4.4.2 The Large Domain of the Model.

4.4.3 Conciseness in Shape Representation.

4.4.4 The Geometric Nature of the Shape Operators.

4.5 Geometric Modeling by Minkowski Operations.

4.5.1 Better Shape Representation.

4.5.2 A Procedural Model.

4.5.3 The Internal Structure of a Model.

4.5.4 Concise Representation.

4.6 Image Analysis by Minkowski Operations.

4.6.1 Mathematical Morphology.

4.6.2 Morphological Operators.

4.6.3 Morphology of Multivalued Figures.

4.6.4 Morphological Expansion.

4.6.5 The Morphological Skeleton and its Properties.

4.6.6 Morphological Decomposition of Figures.

4.7 The Wealth and Potential of the Minkowski Operators.

4.7.1 Minkowski Operations on Discrete Shapes.

4.7.2 Minkowski Operations on Dynamically Varying Shapes.

4.7.3 Inverse Shapes.

**5 Arithmetics of Geometric Shape.**

5.1 The Motivation for a Shape Arithmetic.

5.1.1 Does Negative Shape Exist?

5.1.2 What Form Must Negative Shapes Take?

5.2 Morphology and the Theory of Numbers.

5.2.1 Morphology for High-Level Vision.

5.2.2 The Resemblance between Morphology and the Theory of Numbers.

5.3 Boundary Representation by Support Functions for Morphological Operations.

5.3.1 The Support Function Representation.

5.3.2 The Support Function is a Signed Distance.

5.3.3 From Support Function Representation to Boundary Representation and Vice Versa.

5.3.4 Necessary and Sufficient Conditions for a Function to be a Support Function.

5.4 Geometric Operations by Means of Support Functions.

5.4.1 MAX and MIN Operations (Convex Hull and Intersection).

5.4.2 Morphological Operations in Boundary Representation.

5.5 Morphological Operations on Convex Polygons.

5.5.1 Computation by Means of Support Function Vectors.

5.5.2 Computation by Means of Edges: The Emergence of the Boundary Addition Operation.

5.5.3 Computation by Means of Slope Diagrams: The Unification of Minkowski Addition and Decomposition.

5.5.4 The Computation of Boundary Addition.

5.6 In the Domain of Convex Polyhedra.

5.6.1 Computation by Means of Faces.

5.6.2 The Slope Diagram Representation of a Convex Polyhedron.

5.6.3 Computation by Means of Slope Diagrams.

**6 Morphological Operations on Nonconvex Objects.**

6.1 Problems with Nonconvex Objects.

6.1.1 A Localized Definition of *F*(*A, u*).

6.1.2 The Anomalous Behavior of the Outer Normals at the Nonconvex Faces.

6.1.3 The Need to Maintain Explicit Topological Information about the Operands.

6.2 Slope Diagrams for Nonconvex Polygons.

6.2.1 The Boundary Addition of Nonconvex Polygons by Means of Slope Diagrams.

6.2.2 Boundary Operations on Nonconvex Polygons – More Complex Cases.

6.2.3 Nonconvex Polyhedra and the Slope Diagrammatic Approach.

6.3 A Unified Algorithm for Minkowski Operations.

6.3.1 The Unified Algorithm.

6.3.2 A Complexity Analysis of the Unified Algorithm.

6.3.3 Simplification of the Unified Algorithm Depending on the Type of Input.

**7 The Morphological Decomposability and Indecomposability of Binary Shapes.**

7.1 The Morphological Indecomposability Problem.

7.1.1 The Problem and its Motivation.

7.1.2 Earlier Works.

7.2 A Special Class of Binary Shapes: The Weakly Taxicab Convex (WTC) Polygons.

7.2.1 Transforming Binary Images into Polygons.

7.2.2 The Weakly Taxicab Convex Class of Polygons.

7.2.3 A Few Properties of WTC Polygons Related to Minkowski Operations.

7.3 Computing Minkowski Operations on WTC Polygons.

7.3.1 Representation of WTC Polygons.

7.3.2 The Minkowski Addition of Two WTC Polygons.

7.3.3 The Minkowski Decomposition of Two WTC Polygons.

7.4 A Few Results on Indecomposability in the WTC Domain.

7.4.1 The Number of Indecomposable Shapes.

7.4.2 Identifying Indecomposable Polygons within the WTC Domain.

7.4.3 Simple Indecomposability Tests.

7.5 A Brief Summing Up.

7.5.1 Why Does the Uniqueness of Shape Decomposition Fail?

7.5.2 How Many Indecomposable Shapes are There?

7.5.3 How Can We Define New Equivalence Classes of Polygons?

7.5.4 Can We Devise Laws of Exponents, and Eventually Binomial Formulas for Shapes?

**References.**

**Index.**