文件名称：Klette R., Rosenfeld A. Digital Geometry.. Geometric Methods for Digital Image Analysis (Morgan Kaufmann, 2004)
文件大小：6.3MB
文件格式：PDF
更新时间：2012-04-23 19:01:25
Digital Geometry;Adjacency Graphs;Incidence Pseudographs;Topology;Hulls
Dr. Rosenfeld was widely regarded as the leading researcher in the world in the field of computer image analysis. Over a period of nearly 40 years he made many fundamental and pioneering contributions to nearly every area of that field. He wrote the first textbook in the field (1969); was founding editor of its first journal (1972); and was co-chairman of its first international conference (1987). He published over 30 books and over 600 book chapters and journal articles, and directed nearly 60 Ph.D. dissertations. In 1985 he served as chairman of a panel appointed by the National Research Council to brief the President's Science Advisor on the subject of computer vision; he has also served (1985-8) as a member of the Vision Committee of the National Research Council. In honor of his 65th birthday, a book entitled �Advances in Image Understanding --- A Festschrift for Azriel Rosenfeld�, edited by Kevin Bowyer and Narendra Ahuja, was published in 1996. In honor of his 70th birthday and retirement, a book entitled �Foundation of Image Understanding�, edited by Larry S. Davis, was published in 2001. Dr. Rosenfeld also made important contributions to mathematics, and founded the subfield of fuzzy digital geometry. http://www.cfar.umd.edu/~ar/ Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Pictures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Digital Geometry and Related Disciplines . . . . . . . . . . . . . . . 11 1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.4 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 33 2 Grids and Digitization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.1 The Grid Point and Grid Cell Models . . . . . . . . . . . . . . . . . 35 2.2 Connected Components . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.3 Digitization Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Property Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 73 3 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.1 Basics About Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.2 Grid Point Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.3 Grid Cell Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.4 Metrics on Pictures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 115 4 Adjacency Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.1 Graphs, Adjacency Structures, and Adjacency Graphs . . . . . . . . 117 4.2 Some Basics of Graph Theory . . . . . . . . . . . . . . . . . . . . . . 125 4.3 Oriented Adjacency Graphs . . . . . . . . . . . . . . . . . . . . . . . 135 4.4 Combinatorial Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 156 5 Incidence Pseudographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 5.1 Incidence Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 5.2 Boundaries, Frontiers, and the Euler Characteristic . . . . . . . . . . 168 5.3 The Regular Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.4 Pictures on Incidence Grids . . . . . . . . . . . . . . . . . . . . . . . 181 5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 5.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 190 6 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 6.1 Topologic Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 6.2 Digital Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 6.3 Topologic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 6.4 Combinatorial Topology . . . . . . . . . . . . . . . . . . . . . . . . . 216 6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 6.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 229 7 Curves and Surfaces: Topology . . . . . . . . . . . . . . . . . . . . . . . . 231 7.1 Curves in the Euclidean Topology . . . . . . . . . . . . . . . . . . . 231 7.2 Curves in Incidence Grids . . . . . . . . . . . . . . . . . . . . . . . . 237 7.3 Curves in Adjacency Grids . . . . . . . . . . . . . . . . . . . . . . . 241 7.4 Surfaces in the Euclidean Topology . . . . . . . . . . . . . . . . . . . 251 7.5 Surfaces and Separations in 3D Grids . . . . . . . . . . . . . . . . . 258 7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 7.7 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 266 8 Curves and Surfaces: Geometry . . . . . . . . . . . . . . . . . . . . . . . 269 8.1 Planar Curves and Arcs . . . . . . . . . . . . . . . . . . . . . . . . . 269 8.2 Space Curves and Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . 281 8.3 Surfaces and Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 8.4 Surface Tracing and Approximation . . . . . . . . . . . . . . . . . . 300 8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 8.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 305 9 2D Straightness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 9.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 9.2 Supporting Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 9.3 Self-Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 9.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 9.5 Number-Theoretic Properties . . . . . . . . . . . . . . . . . . . . . . 325 9.6 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 9.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 9.8 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . 337 10 2D Arc Length: Curvature and Corners . . . . . . . . . . . . . . . . . . . . 341 10.1 The Length of a Digital Curve . . . . . . . . . . . . . . . . . . . . . . 341 10.2 Definitions of 2D Arc Length Estimators . . . . . . . . . . . . . . . . 346 10.3 Evaluation of 2D Arc Length Estimators . . . . . . . . . . . . . . . . 353 10.4 The Curvature of a Planar Digital Curve . . . . . . . . . . . . . . . . 362 10.4.1 Corner detectors . . . . . . . . . . . . . . . . . . . . . . . . . 362 10.4.2 Curvature estimators . . . . . . . . . . . . . . . . . . . . . . . 364 10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 10.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 373 11 3D Straightness and Planarity . . . . . . . . . . . . . . . . . . . . . . . . . 375 11.1 3D Straightness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 11.2 Digital Planes in 3D Adjacency Grids . . . . . . . . . . . . . . . . . . 390 11.3 Digital Planes in the 3D Incidence Grid . . . . . . . . . . . . . . . . . 399 11.4 DPS Recognition and Generation . . . . . . . . . . . . . . . . . . . . 402 11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 11.6 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 407 12 3D Arc Length, Surface Area, and Curvature . . . . . . . . . . . . . . . . 409 12.1 3D Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 12.2 Surface Area Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 414 12.3 Surface Curvature Estimation . . . . . . . . . . . . . . . . . . . . . . 422 12.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 12.5 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 426 13 Hulls and Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 13.1 Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 13.2 2D Digital Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 13.3 Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439 13.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 13.5 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 453 14 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 14.1 Geometries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 14.2 Axiomatic Digital Geometry . . . . . . . . . . . . . . . . . . . . . . . 456 14.3 Transformation Groups and Symmetries . . . . . . . . . . . . . . . . . 459 14.4 Neighborhood-Preserving Transformations . . . . . . . . . . . . . . . 462 14.5 Applying Transformations to Pictures . . . . . . . . . . . . . . . . . . 464 14.6 Magnification and Demagnification . . . . . . . . . . . . . . . . . . . . 470 14.7 Digital Tomography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 14.9 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 479 15 Morphologic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 15.1 Dilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 15.2 Erosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 15.3 Combining Dilations and Erosions . . . . . . . . . . . . . . . . . . . . 485 15.4 Simplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 15.5 Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490 15.6 Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 15.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496 15.8 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 496 16 Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499 16.1 Topology-Preserving Deformations and Simple Pixels . . . . . . . . . 499 16.2 Shrinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506 16.3 Thinning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 16.4 Deformations of Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 513 16.5 Interchangeable Pairs of Pixels . . . . . . . . . . . . . . . . . . . . . . 520 16.6 Deformations of 3D Pictures . . . . . . . . . . . . . . . . . . . . . . . 530 16.7 Deformations of Multivalued Pictures . . . . . . . . . . . . . . . . . . 532 16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534 16.9 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 535 17Picture Properties and Spatial Relations . . . . . . . . . . . . . . . . . . . 537 17.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 17.2 Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 17.3 Experimental Evaluation of Moment Estimates . . . . . . . . . . . . . 546 17.4 Operations on Pictures and Invariant Properties . . . . . . . . . . . . 554 17.5 Spatial Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555 17.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558 17.7 Commented Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 559 List of Algorithms 561 List of Symbols 565 List of Axioms 569 Bibliography 571 Index 645