Preface -- Structure of this Book -- Contents -- 1. Introduction -- 1.1 Pictures -- 1.1.1 Pixels, voxels, and their values -- 1.1.2 Picture resolution and picture size -- 1.1.3 Scan orders -- 1.1.4 Adjacency and connectedness -- 1.2 Digital Geometry and Related Disciplines -- 1.2.1 Coordinates and metric spaces -- 1.2.2 Euclidean, similarity, and affine geometry -- 1.2.3 Projective geometry -- 1.2.4 Vector and geometric algebra -- 1.2.5 Graph theory -- 1.2.6 Topology -- 1.2.7 Approximation and estimation -- 1.2.8 Combinatorial geometry -- 1.2.9 Computational geometry -- 1.2.10 Fuzzy geometry -- 1.2.11 Integral geometry, isoperimetry, stereology, and tomography -- 1.2.12 Mathematic morphology -- 1.3 Exercises -- 1.4 Commented Bibliography -- 2. Grids and Digitization -- 2.1 The Grid Point and Grid Cell Models -- 2.1.1 Grid points and grid cells -- 2.1.2 Variable grid resolution -- 2.1.3 Adjacencies in 2D grids -- 2.1.4 Adjacencies in 3D grids -- 2.1.5 Grid cell incidence -- 2.2 Connected Components -- 2.2.1 Connectedness and components -- 2.2.2 Counting connected sets -- 2.2.3 Component labeling -- 2.3 Digitization Models -- 2.3.1 Gauss digitization -- 2.3.2 Jordan digitization -- 2.3.3 Grid-intersection digitization -- 2.3.4 Types of digital sets -- 2.3.5 Domain digitizations -- 2.4 Property Estimation -- 2.4.1 Content estimation -- 2.4.2 Convergent 2D area estimates -- 2.4.3 Multigrid convergence -- 2.5 Exercises -- 2.6 Commented Bibliography -- 3. Metrics -- 3.1 Basics About Metrics -- 3.1.1 The Euclidean metric -- 3.1.2 Norms and Minkowski metrics -- 3.1.3 Scalar products and angles -- 3.1.4 Integer-Valued metrics -- 3.1.5 Restricting and combining metrics -- 3.1.6 Boundedness -- 3.1.7 The topology induced by a metric -- 3.1.8 Distances between sets -- 3.2 Grid Point Metrics -- 3.2.1 Basic grid point metrics.

3.2.2 Neighborhoods and degrees of closeness -- 3.2.3 Approximations to the Euclidean metric -- 3.2.4 Paths, geodesics, and intrinsic distances -- 3.2.5 Distances between sets -- 3.3 Grid Cell Metrics -- 3.3.1 Basic grid cell metrics -- 3.3.2 Seminorms -- 3.3.3 Scalar products and angles -- 3.4 Metrics on Pictures -- 3.4.1 Value-weighted distance -- 3.4.2 Distance transforms -- 3.4.3 The Euclidean distance transform -- 3.4.4 Medial axes -- 3.5 Exercises -- 3.6 Commented Bibliography -- 4. Adjacency Graphs -- 4.1 Graphs, Adjacency Structures, and Adjacency Graphs -- 4.1.1 Graphs and adjacency structures -- 4.1.2 Connectedness with respect to a subgraph -- 4.1.3 Adjacency graphs -- 4.1.4 Types of nodes -- region adjacencies -- 4.2 Some Basics of Graph Theory -- 4.2.1 Nodes, paths, and distances -- 4.2.2 Special types of nodes, edges, and graphs -- 4.3 Oriented Adjacency Graphs -- 4.3.1 Local circular orders -- 4.3.2 The Euler characteristic and planarity -- 4.3.3 Atomic and border cycles -- 4.3.4 The separation theorem -- 4.3.5 Holes -- 4.3.6 Boundaries -- 4.3.7 Some combinatorial results -- 4.4 Combinatorial Maps -- 4.4.1 2D maps -- 4.4.2 3D maps -- 4.5 Exercises -- 4.6 Commented Bibliography -- 5. Incidence Pseudographs -- 5.1 Incidence Structures -- 5.1.1 Adjacency and completeness -- incidence pseudographs -- 5.1.2 Incidence grids -- 5.1.3 Components and regions -- borders -- 5.1.4 Closed and open regions -- 5.2 Boundaries, Frontiers, and the Euler Characteristic -- 5.2.1 Boundaries, chains, and frontiers -- 5.2.2 The matching theorem -- 5.2.3 The Euler characteristic -- 5.3 The Regular Case -- 5.3.1 Regular infinite incidence pseudographs -- 5.3.2 The region matching theorem -- 5.3.3 Euler characteristics -- 5.4 Pictures on Incidence Grids -- 5.4.1 Ordered labeling -- 5.4.2 The ordered adjacency procedure -- 5.4.3 Frontiers in 2D incidence grids.

5.4.4 Frontiers in 3D incidence grids -- 5.5 Exercises -- 5.6 Commented Bibliography -- 6. Topology -- 6.1 Topologic Spaces -- 6.1.1 General definitions -- 6.1.2 Poset topologies -- 6.1.3 Topologies on incidence pseudographs -- 6.2 Digital Topologies -- 6.2.1 General definition -- 6.2.2 The grid point topology -- 6.2.3 The grid cell topology -- 6.2.4 The number of digital topologies -- 6.2.5 Topologic adjacency and dimension -- 6.3 Topologic Concepts -- 6.3.1 Homeomorphy -- 6.3.2 Isotopy -- 6.3.3 Homotopy -- 6.4 Combinatorial Topology -- 6.4.1 Geometric complexes and the Euler characteristic -- 6.4.2 Euclidean complexes -- 6.4.3 Simplicial complexes -- triangulations -- 6.4.4 Abstract complexes -- 6.4.5 The Poincaré formula -- 6.4.6 Homology groups -- 6.5 Exercises -- 6.6 Commented Bibliography -- 7. Curves and Surfaces: Topology -- 7.1 Curves in the Euclidean Topology -- Jordan curves -- Urysohn-Menger curves -- Simple curves and arcs -- Elementary curves and the Euler characteristic -- Separation theorems -- 7.2 Curves in Incidence Grids -- Frontier grids -- curves of marginal nodes -- Curves of principal nodes -- 7.3 Curves in Adjacency Grids -- Euler characteristics of curves -- Simple 2D curves -- Good pairs for 2D binary pictures -- s-Adjacencies in 2D multivalued pictures -- 7.4 Surfaces in the Euclidean Topology -- Manifolds -- Surfaces -- Orientable surfaces -- The connectivity and genus of a surface -- Separation theorems -- 7.5 Surfaces and Separations in 3D Grids -- Surfaces in the grid point model -- Surfaces in the grid cell topology -- Separations in adjacency grids -- 7.6 Exercises -- 7.7 Commented Bibliography -- 8. Curves and Surfaces: Geometry -- 8.1 Planar Curves and Arcs -- 8.2 Space Curves and Arcs -- 8.3 Surfaces and Solids -- 8.4 Surface Tracing and Approximation -- 8.5 Exercises -- 8.6 Commented Bibliography.

9. 2D Straightness -- 9.1 Basics -- 9.2 Supporting Lines -- 9.3 Self-Similarity -- 9.3.1 The chord property -- 9.3.2 Syntactic characterization -- 9.3.3 Continued fractions -- 9.4 Periodicity -- 9.5 Number-Theoretic Properties -- 9.5.1 Counting segments and partitions -- 9.5.2 Spirographs -- 9.6 Algorithms -- 9.6.1 Design paradigms -- 9.6.2 A linear online DSS recognition algorithm -- 9.6.3 Review of other algorithms -- 9.6.4 A linear online 4-DSS algorithm -- 9.7 Exercises -- 9.8 Commented Bibliography -- 10. 2D Arc Length -- Curvature and Corners -- 10.1 The Length of a Digital Curve -- 10.1.1 Curve digitizations -- 10.1.2 Local and global estimation -- 10.1.3 DSS-based estimation -- 10.1.4 MLP-based estimation -- 10.1.5 Tangent-based estimation -- 10.2 Definitions of 2D Arc Length Estimators -- 10.2.1 Local estimators -- 10.2.2 DSS estimators -- 10.2.3 MLP estimators -- 10.2.4 MLPs of simple 1-curves -- 10.2.5 The approximating sausage approach -- 10.2.6 Tangent-based estimators -- 10.3 Evaluation of 2D Arc Length Estimators -- 10.3.1 Online and offline algorithms and time complexity -- 10.3.2 Multigrid convergence theorems -- 10.3.3 Proof of Theorem 10.1 -- 10.3.4 Experimental evaluation -- 10.4 The Curvature of a Planar Digital Curve -- 10.4.1 Corner detectors -- 10.4.2 Curvature estimators -- 10.4.3 Experimental evaluation -- 10.5 Exercises -- 10.6 Commented Bibliography -- 11. 3D Straightness and Planarity -- 11.1 3D Straightness -- 11.1.1 Grid-plane intersection digitization -- 11.1.2 Arithmetic geometry -- 11.1.3 A linear online 3D DSS segmentation algorithm -- 11.1.4 MLPs of simple 2-curves -- 11.1.5 The rubber band algorithm -- 11.2 Digital Planes in 3D Adjacency Grids -- 11.2.1 3D grid-line intersection digitization -- 11.2.2 Self-similarity -- 11.2.3 Supporting and separating planes -- 11.2.4 Arithmetic planes -- 11.2.5 Periodicity.

11.2.6 Connectivity of arithmetic planes -- 11.3 Digital Planes in the 3D Incidence Grid -- 11.4 DPS Recognition and Generation -- 11.4.1 An incremental DPS algorithm -- 11.4.2 DPS generation algorithms -- 11.5 Exercises -- 11.6 Commented Bibliography -- 12. 3D Arc Length, Surface Area, and Curvature -- 12.1 3D Arcs -- 12.1.1 Arc length estimation -- 12.1.2 Estimation of curvature and torsion -- 12.2 Surface Area Estimation -- 12.2.1 Local methods -- 12.2.2 RCH methods -- 12.2.3 NOR methods -- 12.2.4 DPS methods -- 12.3 Surface Curvature Estimation -- 12.4 Exercises -- 12.5 Commented Bibliography -- 13. Hulls and Diagrams -- 13.1 Hulls -- 13.1.1 Convex hull computation in the Euclidean plane -- 13.1.2 Convex hull computation in the (2D) grid -- 13.1.3 Near-hull computation in the Euclidean plane -- 13.2 2D Digital Convexity -- 13.2.1 Digital convex hulls -- 13.2.2 Row and column convexity -- 13.2.3 Fuzzy digital convexity -- 13.3 Diagrams -- 13.3.1 Diagram computation in the Euclidean plane -- 13.3.2 Diagram computation in the digital plane -- 13.3.3 Diagrams in pictures -- 13.4 Exercises -- 13.5 Commented Bibliography -- 14. Transformations -- 14.1 Geometries -- 14.2 Axiomatic Digital Geometry -- 14.3 Transformation Groups and Symmetries -- 14.4 Neighborhood-Preserving Transformations -- 14.5 Applying Transformations to Pictures -- 14.6 Magnification and Demagnification -- 14.7 Digital Tomography -- 14.8 Exercises -- 14.9 Commented Bibliography -- 15. Morphologic Operations -- 15.1 Dilation -- 15.2 Erosion -- 15.3 Combining Dilations and Erosions -- 15.3.1 Hit-and-miss transforms and templates -- 15.3.2 Opening and closing -- 15.4 Simplification -- 15.5 Segmentation -- 15.5.1 Thresholding -- 15.5.2 Local features -- 15.5.3 Texture -- 15.6 Decomposition -- 15.6.1 Clusters -- 15.6.2 Elongated object parts -- 15.6.3 Distance transforms and medial axes.

15.7 Exercises.