Binary digital image processing: a discrete approach

Stéphane Marchand-Maillet, Yazid M. Sharaiha9780080527826, 9780124705050, 0124705057

This book is aimed at faculty, postgraduate students and industry specialists. It is both a text reference and a textbook that reviews and analyses the research output in this field of binary image processing. It is aimed at both advanced researchers as well as educating the novice to this area. The theoretical part of this book includes the basic principles required for binary digital image analysis. The practical part which will take an algorithmic approach addresses problems which find applications beyond binary digital line image processing. The book first outlines the theoretical framework underpinning the study of digital image processing with particular reference to those needed for line image processing. The theoretical tools in the first part of the book set the stage for the second and third parts, where low-level binary image processing is addressed and then intermediate level processing of binary line images is studied. The book concludes with some practical applications of this work by reviewing some industrial and software applications (engineering drawing storage and primitive extraction, fingerprint compression). The book: * outlines the theoretical framework underpinning the study of digital image processing with particular reference to binary line image processing * addresses low-level binary image processing, reviewing a number of essential characteristics of binary digital images and providing solution procedures and algorithms * includes detailed reviews of topics in binary digital image processing with up-to-date research references in relation to each of the problems under study * includes some practical applications of this work by reviewing some common applications * covers a range of topics, organised by theoretical field rather than being driven by problem definitions

---

Table of contents :
Cover……Page 1
Title page……Page 3
Date-line……Page 4
CONTENTS……Page 5
LIST OF FIGURES……Page 7
1.2 Resulting pixels from sampling……Page 28
1.3 Nq(p): 6-neighbourhood of the point p on the triangular lattice……Page 30
1.5 Neighbourhoods on the square grid……Page 31
1.7 A 3-digital closed curve……Page 34
1.10 A 8-digital closed curve……Page 35
1.11 Borders of a binary digital image……Page 37
1.12 A 6-discrete disc of radius 4, centred at p……Page 40
1.13 Distribution of discrete points on regular lattices……Page 41
1.14 4-Disc of radius 3: A4(3)……Page 42
1.15 8-Disc centred at p and of radius 3: Ag(p, 3)……Page 43
1.16 Knight-discs……Page 45
1.18 Hexagonal discs on the square lattice……Page 46
1.19 Oct-disc of radius 4, Aoct(4)……Page 47
1.20 Chamfer discs……Page 49
1.21 Neighbourhoods corresponding to Farey sequences……Page 51
1.23 The graph of Eaj, in the first octant……Page 54
1.24 Calculation of da^,c in the first octant……Page 55
1.25 The graph of Ea^,c in the first octant……Page 56
1.26 Geometrical inconsistencies in the discrete distance calculations……Page 58
1.28 Geometrical explanation of the non-invariance of da$……Page 59
2.1 Grid-intersect quantisation……Page 63
2.2 Freeman’s codes in the 8-neighbourhood……Page 64
2.3 An example of the use of Freeman’s codes……Page 65
2.4 A general sketch for the chord properties……Page 67
2.6 Example for the violation of the chord property……Page 68
2.7 Example for the validity of the compact chord property……Page 69
2.8 Example for the violation of the compact chord property……Page 70
2.9 Upper and lower bounds……Page 71
2.10 Square-box quantisation of a continuous segment……Page 74
2.13 Comparison of visibility polygons defined by the chord properties……Page 76
2.14 Move codes in the 16-neighbourhood……Page 77
2.15 Ti transforms……Page 78
2.16 Example of Ti-mapping……Page 79
2.17 Example of verifications of the 16-compact chord property……Page 81
2.18 Examples of continuous convex and non-convex sets……Page 83
2.20 An equivalent characterisation of discrete convexity……Page 85
2.21 Relation between L- and T-convexity……Page 86
2.22 Relation between definitions of discrete convexity……Page 87
2.23 A special case of intersection for two discrete convex sets……Page 88
2.24 Relation between L- and T-convex hulls……Page 90
2.25 Discrete convex hull of a discrete non-convex set……Page 91
2.26 Square-box quantisation of continuous sets……Page 92
2.27 Relation between continuous and T-convexity……Page 93
2.4 Discrete curvature……Page 94
2.29 Discrete curvature calculation……Page 95
2.31 Curvature of a digital straight segment……Page 96
2.32 Discrete circle defined via the grid-intersect quantisation……Page 98
2.34 Curvature of a discrete disc……Page 99
2.35 GIQ-domain of a digital straight segment……Page 101
2.36 Intersection of two digital straight segments……Page 102
3.1 Graph……Page 105
3.2 Examples of a graph, non-simple path and forest……Page 109
3.3 Binary digital image, grid-graph and path……Page 124
3.4 Shortest path base graph SPBG8(u,w)……Page 126
3.5 Shortest path spanning tree……Page 128
4.1 A simple digitisation scheme……Page 133
4.2 Digitisation using different sampling step values……Page 134
4.3 Inconsistencies of the digitisation scheme……Page 135
4.4 Digitisation based on digitisation boxes……Page 137
4.5 Semi-open tile quantisation of a continuous straight segment……Page 138
4.6 Special cases in the SBQ……Page 139
4.7 Reduction of aliasing with the use of digitisation boxes……Page 140
4.9 Inconsistencies of the digitisation scheme……Page 141
4.10 Grid-intersect quantisation of a continuous curve C……Page 142
4.11 Digitisation scheme for a continuous segment……Page 143
4.12 Grid-intersect quantisation of a continuous straight segment……Page 144
4.13 Aliasing created by the grid-intersect quantisation……Page 145
4.14 Continuous objects associated with a digitisation set……Page 146
4.15 Comparison of the grid-intersect and square-box quantisation schemes……Page 147
4.16 Object-boundary quantisation……Page 148
4.17 Aliasing created by the object-boundary quantisation……Page 150
4.18 OBQ-domain of a digital straight segment……Page 151
4.19 Example of a binary digital image……Page 153
4.20 Forward star structure of a grid graph……Page 154
4.21 Dynamic forward star structure of a grid graph……Page 156
4.22 Test image for the white block skipping coding scheme……Page 158
4.23 Test image for the quadtree encoding scheme……Page 160
4.24 Test image for the boundary encoding scheme……Page 162
4.25 Neighbouring pixel template for JBIG encoding……Page 163
5.1 Centre of maximal disc……Page 167
5.2 Masks for chamfer distance transformations……Page 170
5.3 Masks for chamfer distance transformations (implementation)……Page 171
5.5 Backward pass……Page 172
5.1 Sequential discrete distance mapping algorithm……Page 173
5.7 Sketch for the graph-theoretic distance mapping……Page 176
5.8 Distance mapping on triangular lattices……Page 178
5.9 Euclidean distance mask in the 8-neighbourhood space……Page 182
5.11 Downward pass for the sequential EDT algorithm……Page 183
5.12 A case where the Euclidean distance cannot be propagated……Page 184
5.13 Propagation of the Euclidean distance using contour processing……Page 185
5.4 Related results……Page 192
5.15 The constrained distance mapping problem……Page 193
5.16 Simple pixel set for the calculation of Voronoi diagrams……Page 194
5.18 Grey level representation of a distance map……Page 195
5.20 Compatibility between discrete and Euclidean distances……Page 196
6.1 Masks for component labelling……Page 201
6.2 Sequential connected component labelling……Page 202
6.3 Sequential labelling algorithm……Page 203
6.4 Parallel connected component labelling……Page 204
6.5 Graph-theoretic connected component labelling……Page 205
6.6 Median filtering……Page 208
6.8 Chain-code-based smoothing……Page 209
6.9 Contour smoothing using a distance transformation……Page 211
6.10 Morphological operators……Page 212
6.3 Shape factors……Page 214
6.12 Interpretation of connectivity numbers……Page 216
6.13 Area of a polygon……Page 218
6.14 Centre, eccentricity, radius and diameter of a component……Page 219
6.15 Centroid and optimal orientation of a generic component……Page 220
6.16 Correcting the skewness of digitised text……Page 221
6.18 x- and y-histograms……Page 222
6.19 x- and y-histograms (continued)……Page 223
6.20 Curvature evolution along a contour……Page 224
7.1 Image skeleton……Page 226
7.2 Blum’s model of a ribbon-like image……Page 229
7.3 Wavefront propagation model……Page 230
7.2 Thinning algorithms……Page 231
7.5 Discrete Voronoi diagram deduced from the distance map……Page 233
7.6 Morphological skeleton……Page 235
7.7 Hit or miss operator (256 )……Page 236
7.3 Binary line images……Page 237
7.10 Examples of images and their skeletons……Page 238
7.11 Instances of binary line images……Page 239
7.13 Steps of graph-theoretic thinning……Page 242
7.14 Graph-theoretic thinning of a network image……Page 243
8.1 Circuit image……Page 249
8.3 Width lines of image “Circuit……Page 250
8.5 Vector form of image “Circuit……Page 251
8.2 Road map image……Page 252
8.3 Fingerprint image……Page 253
8.4 Text image……Page 254
8.12 Centres of maximal discs and skeleton for a part of image “Text……Page 255
8.5 Drawing image……Page 256
8.16 Image “Squirrel”: centres of maximal discs and partially reconstructed image……Page 257
8.17 Image “Squirrel”: skeleton and skeleton subtracted from the original……Page 258
LIST OF ALGORITHMS……Page 13
3.1 The generic shortest path algorithm……Page 111
3.2 D’Esopo-Pape’s shortest path algorithm……Page 113
3.3 Dijkstra’s shortest path algorithm……Page 115
3.4 Dial’s shortest path algorithm……Page 117
3.5 Backtracking procedure in the shortest path spanning tree……Page 118
3.6 Kruskal’s minimum weighted spanning tree algorithm……Page 120
3.7 Prim’s minimum weighted spanning tree algorithm……Page 121
5.2 Parallel discrete distance mapping algorithm……Page 174
5.3 Graph-theoretic algorithm for the characterisation of discrete discs……Page 175
5.4 Graph-theoretic algorithm for the discrete distance mapping……Page 177
5.5 Euclidean distance mapping based on contour processing……Page 186
5.6 Euclidean discs on the 8-grid graph……Page 189
5.7 Graph-theoretic Euclidean distance mapping……Page 190
Foreword……Page 15
Acknowledgements……Page 17
Notation……Page 19
Preface……Page 23
1.1 Continuous to discrete images……Page 27
1.2 Neighbourhoods……Page 29
1.3 Discrete sets……Page 32
1.4 Discrete distances……Page 38
1.5 Compatibility with continuous distances……Page 52
2.1 Introduction……Page 61
2.2 Discrete straightness……Page 62
2.3 Discrete convexity……Page 82
2.5 Parallelism and orthogonality……Page 100
3.1 Definitions……Page 103
3.2 Optimisation……Page 110
3.3 Analogies with digital image processing……Page 122
4.1 Digitisation……Page 131
4.2 Storage of binary digital images……Page 152
5.1 Definitions and properties……Page 165
5.2 Discrete distance transformations……Page 168
5.3 Euclidean distance transformations……Page 179
6.1 Connected component labelling……Page 199
6.2 Noise reduction……Page 206
7.1 Skeleton models……Page 225
References……Page 259
Index……Page 273