Computational Morphology (eBook)

A Computational Geometric Approach to the Analysis of Form

G.T. Toussaint (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
273 Seiten
Elsevier Science (Verlag)
978-1-4832-9672-2 (ISBN)

Infos

Computational Geometry is a new discipline of computer science that deals with the design and analysis of algorithms for solving geometric problems. There are many areas of study in different disciplines which, while being of a geometric nature, have as their main component the extraction of a description of the shape or form of the input data. This notion is more imprecise and subjective than pure geometry. Such fields include cluster analysis in statistics, computer vision and pattern recognition, and the measurement of form and form-change in such areas as stereology and developmental biology.This volume is concerned with a new approach to the study of shape and form in these areas. Computational morphology is thus concerned with the treatment of morphology from the computational geometry point of view. This point of view is more formal, elegant, procedure-oriented, and clear than many previous approaches to the problem and often yields algorithms that are easier to program and have lower complexity.

Inhalt

Front Cover 1
Computational Morphology: A Computational Geometric Approach to the Analysis of Form 4
Copyright Page 5
Table of Contents 14
Preface 8
Chapter 1. Computational Complexity of Restricted Polygon Decompositions 16
1. Introduction 16
2. Restricted Convex and Spiral Decompositions 17
3. Computing Restricted Star-Shaped Decompositions 20
CHAPTER 2. COMPUTING MONOTONE SIMPLE CIRCUITS IN THE PLANE 28
1. INTRODUCTION 28
2. PYRAMIDAL TOURS AND MONOTONE CIRCUITS 29
3. DISCUSSION 37
REFERENCES 38
Chapter 3. Circular Separability of Planar Point Sets 40
1. Introduction 40
2. Geometric properties of S(S1,S2) 41
3. Algorithm CIRCULAR and its worst-case analysis 46
4. Smallest and largest separating circles 52
5. Conclusions 53
REFERENCES 54
CHAPTER 4. SYMMETRY FINDING ALGORITHMS 56
1. Introduction 56
2. Algorithms in Two Dimensions 58
3. Three Dimensions 61
4. Optimality 63
5. Final Remarks: "Near" Symmetry 63
References 65
CHAPTER 5. COMPUTING THE RELATIVE NEIGHBOUR DECOMPOSITION OF A SIMPLE POLYGON 68
1. INTRODUCTION 68
2. THE RND PROBLEM 69
3. PROOF OF PLANARITY 72
4. ALGORITHMS 78
5. CONCLUDING REMARKS 84
REFERENCES 84
Chapter 6. Polygonal Approximations of a Curve — Formulations and Algorithms 86
1. Introduction 86
2. Approximation problems for a piecewise linear function 87
3. The approximation problems for a general piecewise linear curve 92
4. Concluding Remarks 99
Acknowledgment 100
References 101
CHAPTER 7. ON POLYGONAL CHAIN APPROXIMATION 102
1. INTRODUCTION 102
2. THE ALGORITHM 103
REFERENCES 110
CHAPTER 8. UNIQUENESS OF ORTHOGONAL CONNECT-THE-DOTS 112
1. INTRODUCTION 112
2. TWO DIMENSIONS 113
3. THREE DIMENSIONS 115
4. DISCUSSION 118
REFERENCES 119
CHAPTER 9. ON THE SHAPE OF A SET OF POINTS 120
1. Introduction 120
2. Motivation for Studying Form 122
3. Properties of a Point Set 123
4. Methods of Point Pattern Analysis 124
5. Notions of Shape 130
6. Decompositions That Characterize Form 131
7. Discussion 148
REFERENCES 149
CHAPTER 10. ORTHO-CONVEXITY AND ITS GENERALIZATIONS 152
1. Introduction 152
2. Characterizations of ortho-convexity 154
3. A second definition of orthogonal convexity 159
4. Ortho-convex hulls 161
5. Restricted-Orientation Convexity 163
6. Generalized convexity 165
7. Future directions 166
8. References 167
Chapter 11. Guard Placement in Rectilinear Polygons 168
1. INTRODUCTION 169
2. OVERVIEW OF ALGORITHM 173
3. QUADRILATERIZING PYRAMIDS 174
4. QUADRILATERIZING MONOTONE POLYGONS 178
5. QUADRILATERIZING RECTILINEAR POLYGONS 183
OPEN PROBLEMS 189
ACKNOWLEDGEMENTS 189
REFERENCES 189
CHAPTER 12. REALIZABILITY OF POLYHEDRONS FROM LINE DRAWINGS 192
1. INTRODUCTION 192
2. REALIZABILITY PROBLEMS 192
3. PERSPECTIVE, OBLIQUE, OR ORTHOGRAPHIC 198
4. LABELING SCHEME 201
5. GRADIENT SPACE AND RECIPROCAL FIGURES 203
6. LINEAR-ALGEBRAIC APPROACH 207
7. FLEXIBLE JUDGMENT OF THE REALIZABILITY 210
8. REALIZABILITY OF RECTANGULAR OBJECTS 212
9. CONCLUDING REMARKS 216
ACKNOWLEDGMENTS 217
REFERENCES 217
CHAPTER 13. VORONOI AND RELATED NEIGHBORS ON DIGITIZED TWO-DIMENSIONAL SPACE WITH APPLICATIONS TO TEXTURE ANALYSIS 222
1. Introduction 222
2. Definition of Modified Digital Voronoi Diagram 223
3. Algorithm to Obtain the MDVD 226
4. Neighboring Relations 227
5. Properties of Neighborhood Relations 232
6. Applications - Texture Analysis Using Adjacency Graphs 233
7. Conclusion 241
References 242
CHAPTER 14. A GRAPH-THEORETICAL PRIMAL SKETCH 244
I. INTRODUCTION 244
II. THE SPHERE-OF-INFLUENCE GRAPH 245
ACKNOWLEDGEMENT 247
REFERENCES 247
AUTHOR INDEX 276

Produkt-Details

• Erscheint lt. Verlag: 28.6.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Geometrie / Topologie
• Themenwelt: Naturwissenschaften
• ISBN-10: 1-4832-9672-5 / 1483296725
• ISBN-13: 978-1-4832-9672-2 / 9781483296722