Elsevier S & T

Digital Geometry: Geometric Methods for Digital Picture Analysis

Klette, Reinhard; Rosenfeld, Azriel

In stock

No reviews

35.500 KD inc. VAT

License

perpetual

Table of contents

Cover
Prefacev
Structure of this Bookxi
Contentsxv
1. Introduction1
1.1 Pictures1
1.1.1 Pixels, voxels, and their values2
1.1.2 Picture resolution and picture size4
1.1.3 Scan orders6
1.1.4 Adjacency and connectedness9
1.2 Digital Geometry and Related Disciplines11
1.2.1 Coordinates and metric spaces11
1.2.2 Euclidean, similarity, and affine geometry13
1.2.3 Projective geometry15
1.2.4 Vector and geometric algebra17
1.2.5 Graph theory19
1.2.6 Topology20
1.2.7 Approximation and estimation21
1.2.8 Combinatorial geometry23
1.2.9 Computational geometry24
1.2.10 Fuzzy geometry27
1.2.11 Integral geometry, isoperimetry, stereology, and tomography28
1.2.12 Mathematic morphology29
1.3 Exercises30
1.4 Commented Bibliography33
2. Grids and Digitization35
2.1 The Grid Point and Grid Cell Models35
2.1.1 Grid points and grid cells35
2.1.2 Variable grid resolution38
2.1.3 Adjacencies in 2D grids38
2.1.4 Adjacencies in 3D grids41
2.1.5 Grid cell incidence44
2.2 Connected Components46
2.2.1 Connectedness and components46
2.2.2 Counting connected sets50
2.2.3 Component labeling51
2.3 Digitization Models55
2.3.1 Gauss digitization56
2.3.2 Jordan digitization58
2.3.3 Grid-intersection digitization60
2.3.4 Types of digital sets64
2.3.5 Domain digitizations65
2.4 Property Estimation66
2.4.1 Content estimation67
2.4.2 Convergent 2D area estimates68
2.4.3 Multigrid convergence70
2.5 Exercises70
2.6 Commented Bibliography73
3. Metrics77
3.1 Basics About Metrics77
3.1.1 The Euclidean metric77
3.1.2 Norms and Minkowski metrics78
3.1.3 Scalar products and angles79
3.1.4 Integer-Valued metrics81
3.1.5 Restricting and combining metrics83
3.1.6 Boundedness83
3.1.7 The topology induced by a metric85
3.1.8 Distances between sets86
3.2 Grid Point Metrics89
3.2.1 Basic grid point metrics89
3.2.2 Neighborhoods and degrees of closeness91
3.2.3 Approximations to the Euclidean metric92
3.2.4 Paths, geodesics, and intrinsic distances95
3.2.5 Distances between sets98
3.3 Grid Cell Metrics100
3.3.1 Basic grid cell metrics100
3.3.2 Seminorms101
3.3.3 Scalar products and angles103
3.4 Metrics on Pictures105
3.4.1 Value-weighted distance105
3.4.2 Distance transforms106
3.4.3 The Euclidean distance transform108
3.4.4 Medial axes111
3.5 Exercises112
3.6 Commented Bibliography115
4. Adjacency Graphs117
4.1 Graphs, Adjacency Structures, and Adjacency Graphs117
4.1.1 Graphs and adjacency structures117
4.1.2 Connectedness with respect to a subgraph119
4.1.3 Adjacency graphs121
4.1.4 Types of nodes; region adjacencies122
4.2 Some Basics of Graph Theory125
4.2.1 Nodes, paths, and distances126
4.2.2 Special types of nodes, edges, and graphs130
4.3 Oriented Adjacency Graphs135
4.3.1 Local circular orders136
4.3.2 The Euler characteristic and planarity137
4.3.3 Atomic and border cycles140
4.3.4 The separation theorem141
4.3.5 Holes143
4.3.6 Boundaries144
4.3.7 Some combinatorial results146
4.4 Combinatorial Maps150
4.4.1 2D maps150
4.4.2 3D maps152
4.5 Exercises153
4.6 Commented Bibliography156
5. Incidence Pseudographs159
5.1 Incidence Structures159
5.1.1 Adjacency and completeness; incidence pseudographs160
5.1.2 Incidence grids163
5.1.3 Components and regions; borders164
5.1.4 Closed and open regions166
5.2 Boundaries, Frontiers, and the Euler Characteristic168
5.2.1 Boundaries, chains, and frontiers168
5.2.2 The matching theorem172
5.2.3 The Euler characteristic173
5.3 The Regular Case175
5.3.1 Regular infinite incidence pseudographs175
5.3.2 The region matching theorem176
5.3.3 Euler characteristics178
5.4 Pictures on Incidence Grids181
5.4.1 Ordered labeling181
5.4.2 The ordered adjacency procedure183
5.4.3 Frontiers in 2D incidence grids185
5.4.4 Frontiers in 3D incidence grids186
5.5 Exercises189
5.6 Commented Bibliography190
6. Topology193
6.1 Topologic Spaces193
6.1.1 General definitions193
6.1.2 Poset topologies195
6.1.3 Topologies on incidence pseudographs196
6.2 Digital Topologies197
6.2.1 General definition197
6.2.2 The grid point topology198
6.2.3 The grid cell topology200
6.2.4 The number of digital topologies204
6.2.5 Topologic adjacency and dimension206
6.3 Topologic Concepts209
6.3.1 Homeomorphy209
6.3.2 Isotopy212
6.3.3 Homotopy214
6.4 Combinatorial Topology216
6.4.1 Geometric complexes and the Euler characteristic216
6.4.2 Euclidean complexes219
6.4.3 Simplicial complexes; triangulations221
6.4.4 Abstract complexes222
6.4.5 The Poincaré formula223
6.4.6 Homology groups225
6.5 Exercises226
6.6 Commented Bibliography229
7. Curves and Surfaces: Topology231
7.1 Curves in the Euclidean Topology231
Jordan curves231
Urysohn-Menger curves232
Simple curves and arcs234
Elementary curves and the Euler characteristic234
Separation theorems236
7.2 Curves in Incidence Grids237
Frontier grids; curves of marginal nodes237
Curves of principal nodes238
7.3 Curves in Adjacency Grids241
Euler characteristics of curves241
Simple 2D curves243
Good pairs for 2D binary pictures246
s-Adjacencies in 2D multivalued pictures248
7.4 Surfaces in the Euclidean Topology251
Manifolds251
Surfaces252
Orientable surfaces254
The connectivity and genus of a surface256
Separation theorems258
7.5 Surfaces and Separations in 3D Grids258
Surfaces in the grid point model258
Surfaces in the grid cell topology259
Separations in adjacency grids262
7.6 Exercises264
7.7 Commented Bibliography266
8. Curves and Surfaces: Geometry269
8.1 Planar Curves and Arcs269
8.2 Space Curves and Arcs281
8.3 Surfaces and Solids282
8.4 Surface Tracing and Approximation300
8.5 Exercises304
8.6 Commented Bibliography305
9. 2D Straightness309
9.1 Basics309
9.2 Supporting Lines312
9.3 Self-Similarity316
9.3.1 The chord property316
9.3.2 Syntactic characterization318
9.3.3 Continued fractions320
9.4 Periodicity321
9.5 Number-Theoretic Properties325
9.5.1 Counting segments and partitions325
9.5.2 Spirographs326
9.6 Algorithms328
9.6.1 Design paradigms328
9.6.2 A linear online DSS recognition algorithm329
9.6.3 Review of other algorithms331
9.6.4 A linear online 4-DSS algorithm334
9.7 Exercises336
9.8 Commented Bibliography337
10. 2D Arc Length; Curvature and Corners341
10.1 The Length of a Digital Curve341
10.1.1 Curve digitizations341
10.1.2 Local and global estimation343
10.1.3 DSS-based estimation343
10.1.4 MLP-based estimation344
10.1.5 Tangent-based estimation346
10.2 Definitions of 2D Arc Length Estimators346
10.2.1 Local estimators346
10.2.2 DSS estimators347
10.2.3 MLP estimators348
10.2.4 MLPs of simple 1-curves348
10.2.5 The approximating sausage approach351
10.2.6 Tangent-based estimators352
10.3 Evaluation of 2D Arc Length Estimators353
10.3.1 Online and offline algorithms and time complexity353
10.3.2 Multigrid convergence theorems354
10.3.3 Proof of Theorem 10.1356
10.3.4 Experimental evaluation358
10.4 The Curvature of a Planar Digital Curve362
10.4.1 Corner detectors362
10.4.2 Curvature estimators364
10.4.3 Experimental evaluation366
10.5 Exercises372
10.6 Commented Bibliography373
11. 3D Straightness and Planarity375
11.1 3D Straightness375
11.1.1 Grid-plane intersection digitization375
11.1.2 Arithmetic geometry376
11.1.3 A linear online 3D DSS segmentation algorithm377
11.1.4 MLPs of simple 2-curves380
11.1.5 The rubber band algorithm385
11.2 Digital Planes in 3D Adjacency Grids390
11.2.1 3D grid-line intersection digitization390
11.2.2 Self-similarity393
11.2.3 Supporting and separating planes393
11.2.4 Arithmetic planes394
11.2.5 Periodicity396
11.2.6 Connectivity of arithmetic planes397
11.3 Digital Planes in the 3D Incidence Grid399
11.4 DPS Recognition and Generation402
11.4.1 An incremental DPS algorithm402
11.4.2 DPS generation algorithms405
11.5 Exercises405
11.6 Commented Bibliography407
12. 3D Arc Length, Surface Area, and Curvature409
12.1 3D Arcs409
12.1.1 Arc length estimation409
12.1.2 Estimation of curvature and torsion413
12.2 Surface Area Estimation414
12.2.1 Local methods414
12.2.2 RCH methods416
12.2.3 NOR methods418
12.2.4 DPS methods421
12.3 Surface Curvature Estimation422
12.4 Exercises424
12.5 Commented Bibliography426
13. Hulls and Diagrams427
13.1 Hulls427
13.1.1 Convex hull computation in the Euclidean plane429
13.1.2 Convex hull computation in the (2D) grid431
13.1.3 Near-hull computation in the Euclidean plane434
13.2 2D Digital Convexity436
13.2.1 Digital convex hulls436
13.2.2 Row and column convexity438
13.2.3 Fuzzy digital convexity439
13.3 Diagrams439
13.3.1 Diagram computation in the Euclidean plane440
13.3.2 Diagram computation in the digital plane443
13.3.3 Diagrams in pictures445
13.4 Exercises450
13.5 Commented Bibliography453
14. Transformations455
14.1 Geometries455
14.2 Axiomatic Digital Geometry456
14.3 Transformation Groups and Symmetries459
14.4 Neighborhood-Preserving Transformations462
14.5 Applying Transformations to Pictures464
14.6 Magnification and Demagnification470
14.7 Digital Tomography475
14.8 Exercises477
14.9 Commented Bibliography479
15. Morphologic Operations481
15.1 Dilation481
15.2 Erosion483
15.3 Combining Dilations and Erosions485
15.3.1 Hit-and-miss transforms and templates485
15.3.2 Opening and closing486
15.4 Simplification486
15.5 Segmentation490
15.5.1 Thresholding490
15.5.2 Local features491
15.5.3 Texture491
15.6 Decomposition492
15.6.1 Clusters492
15.6.2 Elongated object parts493
15.6.3 Distance transforms and medial axes495
15.7 Exercises496
15.8 Commented Bibliography496
16. Deformations499
16.1 Topology-Preserving Deformations and Simple Pixels499
16.2 Shrinking506
16.3 Thinning509
16.4 Deformations of Curves513
16.5 Interchangeable Pairs of Pixels520
16.6 Deformations of 3D Pictures530
16.7 Deformations of Multivalued Pictures532
16.8 Exercises534
16.9 Commented Bibliography535
17. Picture Properties and Spatial Relations537
17.1 Properties537
17.1.1 Predicates537
17.1.2 Local properties538
17.1.3 Linear properties540
17.2 Moments541
17.2.1 Moments of pictures541
17.2.2 Moments of sets543
17.2.3 Estimation of moments of sets544
17.3 Experimental Evaluation of Moment Estimates546
17.3.1 Square546
17.3.2 Disk548
17.3.3 Isometric quartic frontier segments549
17.3.4 Parameterized quartic frontier segments551
17.4 Operations on Pictures and Invariant Properties554
17.5 Spatial Relations555
17.5.1 Relations of relative position555
17.5.2 Topologic relations556
17.6 Exercises558
17.7 Commented Bibliography559
List of Algorithms561
List of Symbols565
List of Axioms and Properties569
Bibliography571
Index645

Book details

Vendor Elsevier S & T
SKU 9781558608610
ISBN-13 9780080477268
Author Klette, Reinhard; Rosenfeld, Azriel
Category Computers
Subject Computer Graphics

Do you have questions about this book?

Ask an expert!

Digital geometry is about deriving geometric information from digital pictures. The field emerged from its mathematical roots some forty-years ago through work in computer-based imaging, and it is used today in many fields, such as digital image processing and analysis (with applications in medical imaging, pattern recognition, and robotics) and of course computer graphics. Digital Geometry is the first book to detail the concepts, algorithms, and practices of the discipline. This comphrehensive text and reference provides an introduction to the mathematical foundations of digital geometry, some of which date back to ancient times, and also discusses the key processes involved, such as geometric algorithms as well as operations on pictures.

*A comprehensive text and reference written by pioneers in digital geometry, image processing and analysis, and computer vision
*Provides a collection of state-of-the-art algorithms for a wide variety of geometrical picture analysis tasks, including extracting data from digital images and making geometric measurements on the data
*Includes exercises, examples, and references to related or more advanced work

Instant delivery by email
Your access email arrives within minutes of checkout, with a sign-in link for each book — no shipping, no waiting.

Read on any device
Books open in VitalSource Bookshelf on your phone, tablet, or computer, online or offline. Your library is always available at aafaq.vitalsource.com — just log in with the email you used at checkout.

Lost the email?
Resend it to yourself in seconds from My eBook orders, or email cs@aafaqeducation.com and we'll help.