3-D Image Processing Algorithms

Foreword V

Preface XIII

Conventions and Notation XV

1 Introduction 1

2 Preliminaries 11

2.1 General Notation 11

2.1.1 Points and Sets in Euclidean Spaces 11

2.1.2 Curvatures 14

2.1.3 Measures and Measurable Spaces 17

2.2 Characteristics of Sets 18

2.2.1 The Euler Number and the Integral of Gaussian Curvature 18

2.2.2 The Mean Width and the Integral of the Mean Curvature 20

2.2.3 Intrinsic Volumes of Convex Bodies 22

2.2.4 Additive Extensions on the Convex Ring 24

2.2.5 The Principal Kinematic Formulae of Integral Geometry 25

2.3 Random Sets 26

2.3.1 Definition of Random Sets 27

2.3.2 Characteristics of Random Closed Sets 28

2.3.3 Random Point Fields 30

2.3.4 Random Tessellations 33

2.4 Fourier Analysis 34

2.4.1 Measurable Functions 34

2.4.2 Fourier Transform 36

2.4.3 Bochner’s Theorem 40

3 Lattices, Adjacency of Lattice Points, and Images 43

3.1 Introduction 43

3.2 Point Lattices, Digitizations and Pixel Configurations 43

3.2.1 Homogeneous Lattices 44

3.2.2 Digitization 45

3.2.3 Pixel Configurations 46

3.3 Adjacency and Euler Number 47

3.3.1 Adjacency Systems 48

3.3.2 Discretization of Sets with Respect to Adjacency 51

3.3.3 Euler Number 52

3.3.4 Complementarity 59

3.3.5 Multi-grid Convergence 60

3.4 The Euler Number of Microstructure Constituents 61

3.4.1 Counting Nodes in Open Foams 61

3.4.2 Connectivity of the Fibres in Non-woven Materials 63

3.5 Image Data 64

3.5.1 The Inverse Lattice 65

3.5.2 The Nyquist–Shannon Sampling Theorem 66

3.6 Rendering 69

3.6.1 Volume Rendering 69

3.6.1.1 Physical Background 69

3.6.1.2 Transfer function 70

3.6.1.3 Ray Casting 71

3.6.1.4 3D Texture Mapping 72

3.6.2 Surface Rendering 72

3.6.2.1 Properties of the Reconstructed Surface 72

3.6.2.2 Marching Cube Type Algorithms 73

3.6.2.3 The Wrapper Algorithm 75

3.6.2.4 Merging and Simplification of Surface Meshes 77

4 Image Processing 79

4.1 Fourier Transform of an Image 79

4.1.1 The Discrete Fourier Transform of a Discrete One-Dimensional Signal 79

4.1.2 Fast Fourier Transform 80

4.1.3 Extensions to Higher Dimensions 81

4.2 Filtering 82

4.2.1 Morphological Transforms of Sets 82

4.2.1.1 Minkowski Addition and Dilation 83

4.2.1.2 Minkowski Subtraction and Erosion 85

4.2.1.3 Mean Co-ordination Number of Sinter Particles 86

4.2.1.4 Morphological Opening and Closure 87

4.2.1.5 Top-Hat Transforms 89

4.2.1.6 Algebraic Opening and Closure 89

4.2.1.7 Aspects of Algorithmic Implementation 90

4.2.1.8 Handling of Edge Effects 92

4.2.1.9 Adaptable Morphology 93

4.2.2 Linear Filters 94

4.2.2.1 Linear Smoothing Filters 94

4.2.2.2 Linear Derivative Filters 98

4.2.3 Morphological Filters 102

4.2.4 Rank Value Filters 103

4.2.5 Diffusion Filters 105

4.2.6 Geodesic Morphological Transforms 107

4.2.6.1 Reconstruction by Erosion 108

4.2.6.2 Reconstruction by Dilation 109

4.2.6.3 Self-Dual Reconstruction 110

4.2.6.4 H-Minima 111

4.2.7 Distance Transforms 111

4.2.7.1 Discrete or Chamfer Distance Transforms 113

4.2.7.2 Euclidean Distance Transforms 114

4.2.8 Skeletonization 116

4.3 Segmentation 120

4.3.1 Binarization 121

4.3.1.1 Global Thresholding 121

4.3.1.2 Local Thresholding 123

4.3.1.3 Hysteresis 125

4.3.1.4 Region Growing 127

4.3.2 Connectedness, Connected Components and Labelling 128

4.3.2.1 Connectedness 128

4.3.2.2 Jordan Theorems 132

4.3.2.3 A Simple Labelling Algorithm 135

4.3.2.4 Advanced Labelling Techniques 141

4.3.3 Watershed Transform 143

4.3.4 Further Segmentation Methods 148

5 Measurement of Intrinsic Volumes and Related Quantities 149

5.1 Introduction 149

5.2 Intrinsic Volumes 150

5.2.1 Section Lattices and Translation Lattices 151

5.2.2 Measurement of Intrinsic Volumes 152

5.2.3 Discretization of the Translative Integral 153

5.2.4 Discretization of the Integral over all Subspaces 156

5.2.4.1 Simple Quadrature 156

5.2.4.2 Fourier Expansion 159

5.2.5 Shape Factors 162

5.2.6 Edge Correction 164

5.3 Intrinsic Volume Densities 166

5.3.1 Estimation of Intrinsic Volume Densities for Macroscopically Homogeneous Random Sets 167

5.3.2 Characterization of Anisotropy 169

5.3.3 Mean Chord Length 170

5.3.4 Structure Model Index 171

5.3.5 Estimation of the Intrinsic Volume Densities for Macroscopically Homogeneous and Isotropic Random Sets 172

5.3.6 Intrinsic Volume Densities of the Solid Matter of Two Natural Porous Structures 176

5.4 Directional Analysis 179

5.4.1 Inverse Cosine Transform 180

5.4.2 Use of Pixel Configurations Carrying Directional Information 182

5.4.3 Gradient and Hessian Matrix 184

5.4.4 Maximum Filter Response 185

5.4.5 Directional Analysis for Fibres in Ultra-High-Performance Concrete 187

5.5 Distances Between Random Sets and Distance Distributions 187

5.5.1 Spherical Contact Distribution Function and Related Quantities 189

5.5.2 Stochastic Dependence of Constituents of Metallic Foams 192

6 Spectral Analysis 195

6.1 Introduction 195

6.2 Second-Order Characteristics of a Random Volume Measure 196

6.2.1 Covariance Function and Bartlett Spectrum 197

6.2.2 Power Spectrum 201

6.2.3 Measurement of the Covariance and the Power Spectrum 202

6.2.4 Macroscopic Homogeneity and Isotropy 203

6.2.5 Mean Face Width of an Open Foam 205

6.2.6 Random Packing of Balls 206

6.2.7 Particle Rearrangement During Sintering Processes 207

6.3 Correlations Between Random Structures 208

6.3.1 The Cross-Covariance Function 209

6.3.2 Measurement of the Cross Covariance Function 211

6.3.3 Spatial Cross-Correlation Between Constituents of Metallic Foams 211

6.4 Second-Order Characteristics of Random Surfaces 212

6.4.1 The Random Surface Measure 213

6.4.2 The Bartlett Spectrum 215

6.4.3 Power Spectrum 218

6.4.4 Measurement of the Power Spectrum with Respect to the Surface Measure 220

6.5 Second-Order Characteristics of Random Point Fields 222

6.5.1 Point Fields and Associated Random Functions 223

6.5.2 A Wiener–Khintchine Theorem for Point Fields 224

6.5.3 Estimation of the Pair Correlation Function 226

6.5.4 The Power Spectra of the Centres of Balls in Dense Packings 230

7 Model-based Image Analysis 233

7.1 Introduction,Motivation 233

7.2 Point Field Models 234

7.2.1 The Poisson Point Field 234

7.2.2 Matern Hard-Core Point Fields 235

7.2.3 Finite Point Fields Defined by a Probability Density 235

7.2.3.1 Simulation of Finite Point Fields: Metropolis–Hastings 237

7.2.3.2 Simulation of Finite Point Fields: Spatial Birth-and-Death Processes 238

7.3 Macroscopically Homogeneous Systems of Non-overlapping Particles 239

7.4 Macroscopically Homogeneous Systems of Overlapping Particles 243

7.4.1 Intrinsic Volumes of Boolean Models in Rn 245

7.4.2 Intrinsic Volumes of Boolean Models in R3 248

7.4.3 Structure Model Index for Boolean Models in R3 250

7.5 Macroscopically Homogeneous Fibre Systems 251

7.5.1 Boolean Cylinder Model 251

7.5.2 PET Stacked Fibre Non-woven Materials 252

7.5.3 Carbon Paper 255

7.6 Tessellations 256

7.6.1 Geometric Properties of Tessellations of R3 256

7.6.1.1 Mean Number of `-Faces Adjacent to a k-Face 257

7.6.1.2 The Density of k-Faces 258

7.6.1.3 Mecke’s Characteristics 258

7.6.1.4 Cell-Based Characteristics 259

7.6.2 Voronoi Tessellations 260

7.6.2.1 Poisson Voronoi Tessellation 260

7.6.2.2 Hard-Core Voronoi Tessellation 261

7.6.3 Laguerre Tessellations 261

7.6.3.1 Poisson–Laguerre Tessellations 264

7.6.3.2 Laguerre Tessellations Generated by Random Packings of Balls 264

7.6.4 The Weaire–Phelan Foam 265

7.6.4.1 Random Perturbations of the Weaire–Phelan Foam 266

7.6.5 Mean Values of Geometric Characteristics of Open Foams 267

7.6.6 Modelling a Closed Polymer Foam 270

7.6.7 Modelling an Open Ceramic Foam 276

7.6.7.1 Modelling the Polyurethane Core 277

7.6.7.2 Modelling the Coating 278

8 Simulation of Material Properties 281

8.1 Introduction 281

8.2 Effective Conductivity of Polycrystals by Stochastic Homogenization 282

8.3 Computation of Effective Elastic Moduli of Porous Media by FEM Simulation 288

8.3.1 Fundamentals of Linear Elasticity 288

8.3.2 Finite Element Method 291

8.3.2.1 Discretization 291

8.3.2.2 Numerical Solution of the Linear Elastic Problem 292

8.3.3 Effective Stiffness Tensor Random Sets 294

8.3.4 Effective Elastic Moduli of a Porous AluminaMaterial 296

References 301

Index 319