Toussaint Computational Morphology

A Computational Geometric Approach to the Analysis of Form
1. Auflage 2014
ISBN: 978-1-4832-9672-2
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band Volume 6, 273 Seiten, Web PDF

Reihe: Machine Intelligence and Pattern Recognition

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.

Autoren/Hrsg.

Toussaint, G. T.

Inhaltsverzeichnis

1;Front Cover;1
2;Computational Morphology: A Computational Geometric Approach to the Analysis of Form;4
3;Copyright Page;5
4;Table of Contents;14
5;Preface;8
6;Chapter 1. Computational Complexity of Restricted Polygon Decompositions;16
6.1;1. Introduction;16
6.2;2. Restricted Convex and Spiral Decompositions;17
6.3;3. Computing Restricted Star-Shaped Decompositions;20
7;CHAPTER 2. COMPUTING MONOTONE SIMPLE CIRCUITS IN THE PLANE;28
7.1;1. INTRODUCTION;28
7.2;2. PYRAMIDAL TOURS AND MONOTONE CIRCUITS;29
7.3;3. DISCUSSION;37
7.4;REFERENCES;38
8;Chapter 3. Circular Separability of Planar Point Sets;40
8.1;1. Introduction;40
8.2;2. Geometric properties of S(S1,S2);41
8.3;3. Algorithm CIRCULAR and its worst-case analysis;46
8.4;4. Smallest and largest separating circles;52
8.5;5. Conclusions;53
8.6;REFERENCES;54
9;CHAPTER 4. SYMMETRY FINDING ALGORITHMS;56
9.1;1. Introduction;56
9.2;2. Algorithms in Two Dimensions;58
9.3;3. Three Dimensions;61
9.4;4. Optimality;63
9.5;5. Final Remarks: "Near" Symmetry;63
9.6;References;65
10;CHAPTER 5. COMPUTING THE RELATIVE NEIGHBOUR DECOMPOSITION OF A SIMPLE POLYGON;68
10.1;1. INTRODUCTION;68
10.2;2. THE RND PROBLEM;69
10.3;3. PROOF OF PLANARITY;72
10.4;4. ALGORITHMS;78
10.5;5. CONCLUDING REMARKS;84
10.6;REFERENCES;84
11;Chapter 6. Polygonal Approximations of a Curve — Formulations and Algorithms;86
11.1;1. Introduction;86
11.2;2. Approximation problems for a piecewise linear function;87
11.3;3. The approximation problems for a general piecewise linear curve;92
11.4;4. Concluding Remarks;99
11.5;Acknowledgment;100
11.6;References;101
12;CHAPTER 7. ON POLYGONAL CHAIN APPROXIMATION;102
12.1;1. INTRODUCTION;102
12.2;2. THE ALGORITHM;103
12.3;REFERENCES;110
13;CHAPTER 8. UNIQUENESS OF ORTHOGONAL CONNECT-THE-DOTS;112
13.1;1. INTRODUCTION;112
13.2;2. TWO DIMENSIONS;113
13.3;3. THREE DIMENSIONS;115
13.4;4. DISCUSSION;118
13.5;REFERENCES;119
14;CHAPTER 9. ON THE SHAPE OF A SET OF POINTS;120
14.1;1. Introduction;120
14.2;2. Motivation for Studying Form;122
14.3;3. Properties of a Point Set;123
14.4;4. Methods of Point Pattern Analysis;124
14.5;5. Notions of Shape;130
14.6;6. Decompositions That Characterize Form;131
14.7;7. Discussion;148
14.8;REFERENCES;149
15;CHAPTER 10. ORTHO-CONVEXITY AND ITS GENERALIZATIONS;152
15.1;1. Introduction;152
15.2;2. Characterizations of ortho-convexity;154
15.3;3. A second definition of orthogonal convexity;159
15.4;4. Ortho-convex hulls;161
15.5;5. Restricted-Orientation Convexity;163
15.6;6. Generalized convexity;165
15.7;7. Future directions;166
15.8;8. References;167
16;Chapter 11. Guard Placement in Rectilinear Polygons;168
16.1;1. INTRODUCTION;169
16.2;2. OVERVIEW OF ALGORITHM;173
16.3;3. QUADRILATERIZING PYRAMIDS;174
16.4;4. QUADRILATERIZING MONOTONE POLYGONS;178
16.5;5. QUADRILATERIZING RECTILINEAR POLYGONS;183
16.6;OPEN PROBLEMS;189
16.7;ACKNOWLEDGEMENTS;189
16.8;REFERENCES;189
17;CHAPTER 12. REALIZABILITY OF POLYHEDRONS FROM LINE DRAWINGS;192
17.1;1. INTRODUCTION;192
17.2;2. REALIZABILITY PROBLEMS;192
17.3;3. PERSPECTIVE, OBLIQUE, OR ORTHOGRAPHIC;198
17.4;4. LABELING SCHEME;201
17.5;5. GRADIENT SPACE AND RECIPROCAL FIGURES;203
17.6;6. LINEAR-ALGEBRAIC APPROACH;207
17.7;7. FLEXIBLE JUDGMENT OF THE REALIZABILITY;210
17.8;8. REALIZABILITY OF RECTANGULAR OBJECTS;212
17.9;9. CONCLUDING REMARKS;216
17.10;ACKNOWLEDGMENTS;217
17.11;REFERENCES;217
18;CHAPTER 13. VORONOI AND RELATED NEIGHBORS ON DIGITIZED TWO-DIMENSIONAL SPACE WITH APPLICATIONS TO TEXTURE ANALYSIS;222
18.1;1. Introduction;222
18.2;2. Definition of Modified Digital Voronoi Diagram;223
18.3;3. Algorithm to Obtain the MDVD;226
18.4;4. Neighboring Relations;227
18.5;5. Properties of Neighborhood Relations;232
18.6;6. Applications - Texture Analysis Using Adjacency Graphs;233
18.7;7. Conclusion;241
18.8;References;242
19;CHAPTER 14. A GRAPH-THEORETICAL PRIMAL SKETCH;244
19.1;I. INTRODUCTION;244
19.2;II. THE SPHERE-OF-INFLUENCE GRAPH;245
19.3;ACKNOWLEDGEMENT;247
19.4;REFERENCES;247
20;AUTHOR INDEX;276