Digital geometry in image processing

Title:

Series:

Iit kharagpur research monograph series

Publication Information:

Boca Raton, FL : Taylor & Francis, 2013

Physical Description:

xxvii, 274 pages : ill. ; 24 cm.

ISBN:

9781466505674

Subject Term:

Image processing -- Digital techniques -- Mathematics.

Geometry -- Data processing.

Added Author:

Mukhopadhyay, Jayanta

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010327948	TA1637 D35 2013	Open Access Book	Book	Searching... Unknown
Searching... PSZ KL	33000000000170	TA1637 D35 2013	Open Access Book	Book	Searching... Unknown
Searching... PSZ KL	33000000000096	TA1637 D35 2013	Open Access Book	Book	Searching... Unknown

Exploring theories and applications developed during the last 30 years, Digital Geometry in Image Processing presents a mathematical treatment of the properties of digital metric spaces and their relevance in analyzing shapes in two and three dimensions. Unlike similar books, this one connects the two areas of image processing and digital geometry, highlighting important results of digital geometry that are currently used in image analysis and processing.

The book discusses different digital geometries in multi-dimensional integral coordinate spaces. It also describes interesting properties of the geometries, including metric and topological properties, shapes of circles and spheres, proximity to Euclidean norms, and number theoretic representations of geometric objects such as straight lines and circles. The authors--all active researchers in image processing and digital geometry--demonstrate how these concepts and properties are useful in various techniques for image processing and analysis. In particular, the book covers applications in object representation and shape analysis.

With many figures (some in color) and end-of-chapter exercises, this book provides an in-depth, unified account of digital metrics, the characterization of digital curves and straight lines, and their uses in shape analysis. It gives you insight on the latest two- and three-dimensional image processing applications.

Author Notes

Jayanta Mukhopadhyay is a professor in the Department of Computer Science and Engineering at the Indian Institute of Technology (IIT) Kharagpur, where he is currently head of the Department of Computer Science and Engineering and the School of Information and Technology. Dr. Mukhopadhyay was a Humboldt Research Fellow at the Technical University of Munich and has held visiting positions at the University of California-Santa Barbara, University of Southern California, and the National University of Singapore. He is a senior member of the IEEE and a fellow of the Indian National Academy of Engineering (INAE). His research interests include image processing, pattern recognition, computer graphics, multimedia systems, and medical informatics. He has published more than 170 journal articles and conference proceedings in these areas. He received his B.Tech., M.Tech., and Ph.D. in electronics and electrical communication engineering from IIT Kharagpur.

Partha Pratim Das is a professor in the Department of Computer Science and Engineering at IIT Kharagpur. He is also a visiting professor in the Institute of Radio Physics and Electronics at Calcutta University. Dr. Das is a member of the Association for Computing Machinery (ACM) and the VLSI Society of India and a reviewer for ACM Computing Surveys and Pattern Recognition Letters . He has published over 40 technical papers in digital geometry, image processing, parallel computing, and knowledge-based systems and has co-authored a book Digital Geometry in Image Processing . His research interests include object tracking and interpretation in videos, medical information processing, and debugging automation for multi-threaded programs. He obtained his B.Tech., M.Tech., and Ph.D. in electronics and electrical communication from IIT Kharagpur.

Samiran Chattopadhyay is a professor in the Department of Information Technology at Jadavpur Univers

Series Preface	p. xi
Preface	p. xiii
List of Figures	p. xvii
List of Tables	p. xxv
1 Digital Topology: Fundamentals	p. 1
1.1 Tessellation of a Continuous Space	p. 2
1.2 Digital Grid	p. 3
1.2.1 Jordan's Theorem on Closed Curves	p. 4
1.3 Grid Topology	p. 5
1.3.1 Component Labeling	p. 6
1.3.2 Containment	p. 7
1.3.3 Boundary and Interior	p. 9
1.3.3.1 Contour Tracing	p. 10
1.3.3.2 Chain Code	p. 10
1.3.3.3 Neighborhood Plane Set (NPS)	p. 11
1.4 Topology Preserving Operations	p. 14
1.4.1 Skeletonization	p. 14
1.4.1.1 Extended SPTA (ESPTA) for 3-D Images	p. 16
1.4.2 Adjacency Tree	p. 21
1.5 The Euler Characteristics	p. 22
1.6 Summary	p. 25
2 Distance Functions in Digital Geometry	p. 27
2.1 Mathematical Definitions and Notation	p. 29
2.1.1 Properties of Integer Functions	p. 30
2.2 Neighborhoods, Paths, and Distances	p. 30
2.2.1 Neighborhoods	p. 31
2.2.1.1 Characterizations of Neighborhood Sets	p. 31
2.2.2 Digital Paths	p. 34
2.2.2.1 Shortest Path Algorithm	p. 36
2.2.3 Distances and Metrics	p. 37
2.2.3.1 Distance as a Norm	p. 38
2.2.4 Metricity Preserving Transforms	p. 39
2.2.4.1 Generalized Metricity Preserving Transforms (GMPT)	p. 42
2.3 Neighborhood Distances	p. 44
2.3.1 m-Neighbor Distance	p. 44
2.3.1.1 Length of Shortest Path	p. 45
2.3.1.2 m-Neighbor Distance in Real Space	p. 46
2.3.2 t-Cost Distance	p. 47
2.3.2.1 Necessary and Sufficient Condition for Metricity	p. 48
2.3.2.2 Length of Shortest Path	p. 49
2.3.2.3 Real-Valued Cost	p. 49
2.3.2.4 t-Cost Distance in Real Space	p. 50
2.3.3 Weighted Cost Distance	p. 50
2.3.4 Knight's Distance	p. 51
2.4 Path-Dependent Neighborhoods and Distances	p. 52
2.4.1 Hyperoctagonal Distance	p. 52
2.4.1.1 Necessary and Sufficient Condition for Metricity	p. 55
2.4.2 Octagonal Distances in 2-D	p. 56
2.4.2.1 Best Simple Octagonal Distance	p. 58
2.4.3 Weighted t-Cost Distance	p. 59
2.5 Hyperspheres of Digital Distances	p. 59
2.5.1 Notions of Hyperspheres	p. 60
2.5.2 Euclidean Hyperspheres	p. 62
2.5.3 Hyperspheres of m-Neighbor Distance	p. 62
2.5.3.1 Vertices of Hyperspheres	p. 65
2.5.3.2 Errors in Surface and Volume Estimations	p. 65
2.5.3.3 Hyperspheres of Real m-Neighbor Distance	p. 66
2.5.4 Hyperspheres of t-Cost Distance	p. 68
2.5.5 Hyperspheres of Hyperoctagonal Distances	p. 69
2.5.5.1 Vertices of Hyperspheres and Approximations	p. 70
2.5.5.2 Special Cases of Hyperspheres in 2-D and 3-D	p. 72
2.5.6 Hyperspheres of Weighted t-Cost Distance	p. 75
2.5.6.1 Proximity to Euclidean Hyperspheres	p. 78
2.6 Error Estimation and Approximation of Euclidean Distance	p. 80
2.6.1 Notions of Error	p. 81
2.6.2 Error of m-Neighbor Distance	p. 81
2.6.3 Error of Real m-Neighbor Distance	p. 82
2.6.4 Error of t-Cost Distance	p. 83
2.6.4.1 Error of t-Cost Distance for Real Costs	p. 84
2.7 Summary	p. 85
3 Digitization of Straight Lines and Planes	p. 89
3.11 2-D Discrete Straight Line Segments	p. 90
3.1.1 Computation of subport Line of DSLS	p. 93
3.1.2 Number Theoretic Characterization and Domain of DSLS	p. 95
3.2 Iterative Refinement: An Algebraic Characterization	p. 98
3.2.1 Gradient and Intercept Estimation	p. 98
3.2.2 Reconstruction of a DSLS	p. 100
3.2.3 Computation of Precise Domain of a DSLS	p. 102
3.2.4 Speed and Convergence of Iterative Refinement	p. 106
3.2.5 Length Estimators	p. 107
3.2.5.1 (n)-characterization [76, 79]	p. 109
3.2.5.2 (n e , n o )-characterization [76, 79]	p. 109
3.2.5.3 (n, q, p, s)-characterization [76, 79]	p. 109
3.3 Three-Dimensional Digital Straight Line Segments	p. 109
3.3.1 Geometric Preliminaries, Digitization, and Characterization	p. 110
3.3.1.1 Digitization of a 3-D Line Segment	p. 112
3.3.1.2 Characterization of a 3-D DSLS	p. 113
3.3.2 Characterization of Cham Codes of 3-D DSLS	p. 113
3.3.2.1 n-characterization	p. 114
3.3.2.2 (n, n o1 , n o2 )-characterization	p. 114
3.3.2.3 (n, n o1 , n c1 , n o2 , n c2 )-characterization	p. 114
3.3.2.4 (n, q 1 , p 1 , S 1 , q 2 , p 2 , S 2 )-characterization	p. 114
3.3.3 Length Estimators for Different Characterizations	p. 114
3.3.3.1 (n)-characterization [39]	p. 115
3.3.3.2 (n, n o1 , n o2 )-characterization [39]	p. 116
3.3.3.3 (n. n o1 , n c1 , n o2 , n c2 )-characterization [39]	p. 116
3.3.3.4 (n, q 1 , p 1 , S 1 , q 2 , p 2 , S 2 )-characterization	p. 116
3.4 Digital Plane Segments	p. 117
3.4.1 Digitization and Netcode Representation	p. 117
3.4.2 Geometric Characterization	p. 119
3.4.3 Characterization by Convex Hull Separability	p. 120
3.4.4 Area Estimators	p. 122
3.4.4.1 n 2 -characterization	p. 123
3.4.4.2 (n 1 , n 2 , n 3 ) -characterization	p. 123
3.4.4.3 Non-linear Estimators	p. 124
3.5 Summary	p. 124
4 Digital Straightness and Polygonal Approximation	p. 127
4.1 Digital Straightness	p. 129
4.1.1 Slopes and Continued Fractions	p. 130
4.1.1.1 Analyzing a Continued Fraction	p. 133
4.1.2 Periodicity	p. 135
4.2 Approximate Straightness	p. 136
4.2.1 Extraction of ADSS	p. 138
4.2.2 Algorithm Detect-ADSS	p. 140
4.2.3 Error Points	p. 143
4.3 Polygonal Approximation	p. 143
4.3.1 Approximation Criterion	p. 144
4.3.1.1 Cumulative Error	p. 144
4.3.1.2 Maximum Error	p. 145
4.3.2 Algorithm for Polygonal Approximation	p. 146
4.3.3 Quality of Approximation	p. 146
4.4 Approximation on Gray-Scale Images	p. 148
4.4.1 Commencing a Straight Edge	p. 149
4.4.2 Exponential Averaging	p. 149
4.4.3 Checking the Straightness	p. 150
4.4.4 Finishing the Edge Sequence	p. 151
4.5 Examples	p. 151
4.6 Summary	p. 154
5 Parametric Curve Estimation and Reconstruction	p. 159
5.1 Digital Conies in Canonical Form	p. 160
5.2 Circles and Parabolas in Canonical Form	p. 163
5.3 Estimation of Major and Minor Axes of an Ellipse in Canonical Form	p. 166
5.3.1 Reconstruction of Ellipse	p. 166
5.3.2 The Reconstruction Algorithm	p. 170
5.3.3 The Domain Theorem	p. 171
5.4 Reconstruction of Hyperbola in Canonical Form	p. 172
5.5 A Restricted Class of Digitized Planar Curves	p. 175
5.5.1 Characterizing Properties of the Class	p. 176
5.5.2 One-Parameter Class	p. 181
5.5.3 Two-Parameter Class	p. 183
5.6 Summary	p. 186
6 Medial Axis Transform	p. 189
6.1 Distance Transform	p. 190
6.1.1 Distance Transform through Iterative Scan	p. 190
6.1.2 Chamfering Algorithm	p. 191
6.1.2.1 Designing Masks	p. 192
6.1.3 Forward and Reverse Scans	p. 192
6.1.4 Euclidean Distance Transform	p. 193
6.2 Medial Axis Transform (MAT)	p. 196
6.2.1 MAT from the Distance Transform	p. 197
6.2.2 Reduced Centers of Maximal Disks (RCMD)	p. 198
6.3 Skeletonization Using MAT	p. 200
6.4 Geometric Transformation	p. 203
6.4.1 Approximate Transformation by Euclidean Disks	p. 204
6.5 Computation of Normals at Boundary Points of 2-D Objects	p. 205
6.5.1 Algorithm for Normal Computation	p. 206
6.5.2 Use of Octagonal Distances	p. 206
6.5.3 Quality of Computation	p. 208
6.6 Computation of Cross-Sections of 3-D Objects	p. 212
6.6.1 Computation with MAT	p. 215
6.6.2 The Algorithm	p. 216
6.6.3 Using Euclidean Approximation	p. 218
6.7 Shading of 3-D Objects	p. 219
6.8 Summary	p. 220
7 Modeling of a Voxelated Surface	p. 225
7.1 Voxelation and Approximation of 3-D Surface	p. 228
7.1.1 3-D Isothetic Covers	p. 230
7.1.2 Test Results	p. 232
7.2 Voxelation of Surface of Revolution	p. 233
7.2.1 Various Techniques	p. 234
7.2.2 Digital Curves and Surfaces	p. 236
7.2.3 Algorithm to Wheel-Throw a Single Piece	p. 238
7.2.4 Number-Theoretic Approach	p. 241
7.2.4.1 Algorithm DCS (Digital Circle Using Squares)	p. 244
7.2.4.2 Run Length Properties of Digital Circles	p. 244
7.2.5 Creating Realistic Potteries	p. 248
7.2.6 Some Examples	p. 251
7.3 Summary	p. 252
References	p. 255
Index	p. 271

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents