An Introduction to 3D Computer Vision Techniques and Algorithms

Boguslaw Cyganek, AGH – University of Science and Technology, Department of Computer Science, Signal Processing Laboratory, Krakow, Poland Boguslaw Cyganek has been teaching at the AGH – University of Science and Technology since 1993 and is now a Lecturer and Researcher in the Department of Electronics and Computer Science. His research interests include the development of image processing systems, robot vision and neural networks. During this time, he has gained several years of practical experience working as a Software Development Manager and a Software Engineer both in the USA and Poland. He has also written Three Dimensional Image Processing (Academic Publisher House, 2002) and 18 academic papers on image processing and algorithms. Paul Siebert, Department of Computing Science, University of Glasgow, 3D-MATIC Research Laboratory, Scotland Dr Jan Paul Siebert is currently Director of the 3D-MATIC Research Laboratory in the Department of Computing Science at Glasgow University. His research interests are in computer vision, image processing, and 3D imaging by stereo photogrammetry and its applications in 3D whole human body imaging. He is Scottish Chair of the BMVC and prior to his current position he was Chief Executive of the of the Turing Institute, Glasgow, which developed the ‘C3D’ imaging technology. He has written over 50 journal, technical and conference papers on 3D image processing, modelling virtual images and photogrammetry.

Preface xv

Acknowledgements xvii

Notation and Abbreviations xix

Part I 1

1 Introduction 3

1.1 Stereo-pair Images and Depth Perception 4

1.2 3D Vision Systems 4

1.3 3D Vision Applications 5

1.4 Contents Overview: The 3D Vision Task in Stages 6

2 Brief History of Research on Vision 9

2.1 Abstract 9

2.2 Retrospective of Vision Research 9

2.3 Closure 14

2.3.1 Further Reading 14

Part II 15

3 2D and 3D Vision Formation 17

3.1 Abstract 17

3.2 Human Visual System 18

3.3 Geometry and Acquisition of a Single Image 23

3.3.1 Projective Transformation 24

3.3.2 Simple Camera System: the Pin-hole Model 24

3.3.3 Projective Transformation of the Pin-hole Camera 28

3.3.4 Special Camera Setups 29

3.3.5 Parameters of Real Camera Systems 30

3.4 Stereoscopic Acquisition Systems 31

3.4.1 Epipolar Geometry 31

3.4.2 Canonical Stereoscopic System 36

3.4.3 Disparity in the General Case 38

3.4.4 Bifocal, Trifocal and Multifocal Tensors 39

3.4.5 Finding the Essential and Fundamental Matrices 41

3.4.6 Dealing with Outliers 49

3.4.7 Catadioptric Stereo Systems 54

3.4.8 Image Rectification 55

3.4.9 Depth Resolution in Stereo Setups 59

3.4.10 Stereo Images and Reference Data 61

3.5 Stereo Matching Constraints 66

3.6 Calibration of Cameras 70

3.6.1 Standard Calibration Methods 71

3.6.2 Photometric Calibration 73

3.6.3 Self-calibration 73

3.6.4 Calibration of the Stereo Setup 74

3.7 Practical Examples 75

3.7.1 Image Representation and Basic Structures 75

3.8 Appendix: Derivation of the Pin-hole Camera Transformation 91

3.9 Closure 93

3.9.1 Further Reading 93

3.9.2 Problems and Exercises 94

4 Low-level Image Processing for Image Matching 95

4.1 Abstract 95

4.2 Basic Concepts 95

4.2.1 Convolution and Filtering 95

4.2.2 Filter Separability 97

4.3 Discrete Averaging 99

4.3.1 Gaussian Filter 100

4.3.2 Binomial Filter 101

4.4 Discrete Differentiation 105

4.4.1 Optimized Differentiating Filters 105

4.4.2 Savitzky–Golay Filters 108

4.5 Edge Detection 115

4.5.1 Edges from Signal Gradient 117

4.5.2 Edges from the Savitzky–Golay Filter 119

4.5.3 Laplacian of Gaussian 120

4.5.4 Difference of Gaussians 126

4.5.5 Morphological Edge Detector 127

4.6 Structural Tensor 127

4.6.1 Locally Oriented Neighbourhoods in Images 128

4.6.2 Tensor Representation of Local Neighbourhoods 133

4.6.3 Multichannel Image Processing with Structural Tensor 143

4.7 Corner Detection 144

4.7.1 The Most Common Corner Detectors 144

4.7.2 Corner Detection with the Structural Tensor 149

4.8 Practical Examples 151

4.8.1 C++ Implementations 151

4.8.2 Implementation of the Morphological Operators 157

4.8.3 Examples in Matlab: Computation of the SVD 161

4.9 Closure 162

4.9.1 Further Reading 163

4.9.2 Problems and Exercises 163

5 Scale-space Vision 165

5.1 Abstract 165

5.2 Basic Concepts 165

5.2.1 Context 165

5.2.2 Image Scale 166

5.2.3 Image Matching Over Scale 166

5.3 Constructing a Scale-space 168

5.3.1 Gaussian Scale-space 168

5.3.2 Differential Scale-space 170

5.4 Multi-resolution Pyramids 172

5.4.1 Introducing Multi-resolution Pyramids 172

5.4.2 How to Build Pyramids 175

5.4.3 Constructing Regular Gaussian Pyramids 175

5.4.4 Laplacian of Gaussian Pyramids 177

5.4.5 Expanding Pyramid Levels 178

5.4.6 Semi-pyramids 179

5.5 Practical Examples 181

5.5.1 C++ Examples 181

5.5.2 Matlab Examples 186

5.6 Closure 191

5.6.1 Chapter Summary 191

5.6.2 Further Reading 191

5.6.3 Problems and Exercises 192

6 Image Matching Algorithms 193

6.1 Abstract 193

6.2 Basic Concepts 193

6.3 Match Measures 194

6.3.1 Distances of Image Regions 194

6.3.2 Matching Distances for Bit Strings 198

6.3.3 Matching Distances for Multichannel Images 199

6.3.4 Measures Based on Theory of Information 202

6.3.5 Histogram Matching 205

6.3.6 Efficient Computations of Distances 206

6.3.7 Nonparametric Image Transformations 209

6.3.8 Log-polar Transformation for Image Matching 218

6.4 Computational Aspects of Matching 222

6.4.1 Occlusions 222

6.4.2 Disparity Estimation with Subpixel Accuracy 224

6.4.3 Evaluation Methods for Stereo Algorithms 226

6.5 Diversity of Stereo Matching Methods 229

6.5.1 Structure of Stereo Matching Algorithms 233

6.6 Area-based Matching 238

6.6.1 Basic Search Approach 239

6.6.2 Interpreting Match Cost 241

6.6.3 Point-oriented Implementation 245

6.6.4 Disparity-oriented Implementation 250

6.6.5 Complexity of Area-based Matching 256

6.6.6 Disparity Map Cross-checking 257

6.6.7 Area-based Matching in Practice 259

6.7 Area-based Elastic Matching 273

6.7.1 Elastic Matching at a Single Scale 273

6.7.2 Elastic Matching Concept 278

6.7.3 Scale-based Search 280

6.7.4 Coarse-to-fine Matching Over Scale 283

6.7.5 Scale Subdivision 284

6.7.6 Confidence Over Scale 285

6.7.7 Final Multi-resolution Matcher 286

6.8 Feature-based Image Matching 288

6.8.1 Zero-crossing Matching 289

6.8.2 Corner-based Matching 292

6.8.3 Edge-based Matching: The Shirai Method 295

6.9 Gradient-based Matching 296

6.10 Method of Dynamic Programming 298

6.10.1 Dynamic Programming Formulation of the Stereo Problem 301

6.11 Graph Cut Approach 306

6.11.1 Graph Cut Algorithm 306

6.11.2 Stereo as a Voxel Labelling Problem 311

6.11.3 Stereo as a Pixel Labelling Problem 312

6.12 Optical Flow 314

6.13 Practical Examples 318

6.13.1 Stereo Matching Hierarchy in C++ 318

6.13.2 Log-polar Transformation 319

6.14 Closure 321

6.14.1 Further Reading 321

6.14.2 Problems and Exercises 322

7 Space Reconstruction and Multiview Integration 323

7.1 Abstract 323

7.2 General 3D Reconstruction 323

7.2.1 Triangulation 324

7.2.2 Reconstruction up to a Scale 325

7.2.3 Reconstruction up to a Projective Transformation 327

7.3 Multiview Integration 329

7.3.1 Implicit Surfaces and Marching Cubes 330

7.3.2 Direct Mesh Integration 338

7.4 Closure 342

7.4.1 Further Reading 342

8 Case Examples 343

8.1 Abstract 343

8.2 3D System for Vision-Impaired Persons 343

8.3 Face and Body Modelling 345

8.3.1 Development of Face and Body Capture Systems 345

8.3.2 Imaging Resolution, 3D Resolution and Implications for Applications 346

8.3.3 3D Capture and Analysis Pipeline for Constructing Virtual Humans 350

8.4 Clinical and Veterinary Applications 352

8.4.1 Development of 3D Clinical Photography 352

8.4.2 Clinical Requirements for 3D Imaging 353

8.4.3 Clinical Assessment Based on 3D Surface Anatomy 353

8.4.4 Extraction of Basic 3D Anatomic Measurements 354

8.4.5 Vector Field Surface Analysis by Means of Dense Correspondences 357

8.4.6 Eigenspace Methods 359

8.4.7 Clinical and Veterinary Examples 362

8.4.8 Multimodal 3D Imaging 367

8.5 Movie Restoration 370

8.6 Closure 374

8.6.1 Further Reading 374

Part III 375

9 Basics of the Projective Geometry 377

9.1 Abstract 377

9.2 Homogeneous Coordinates 377

9.3 Point, Line and the Rule of Duality 379

9.4 Point and Line at Infinity 380

9.5 Basics on Conics 382

9.5.1 Conics in ℘2 382

9.5.2 Conics in ℘2 384

9.6 Group of Projective Transformations 385

9.6.1 Projective Base 385

9.6.2 Hyperplanes 386

9.6.3 Projective Homographies 386

9.7 Projective Invariants 387

9.8 Closure 388

9.8.1 Further Reading 389

10 Basics of Tensor Calculus for Image Processing 391

10.1 Abstract 391

10.2 Basic Concepts 391

10.2.1 Linear Operators 392

10.2.2 Change of Coordinate Systems: Jacobians 393

10.3 Change of a Base 394

10.4 Laws of Tensor Transformations 396

10.5 The Metric Tensor 397

10.5.1 Covariant and Contravariant Components in a Curvilinear Coordinate System 397

10.5.2 The First Fundamental Form 399

10.6 Simple Tensor Algebra 399

10.6.1 Tensor Summation 399

10.6.2 Tensor Product 400

10.6.3 Contraction and Tensor Inner Product 400

10.6.4 Reduction to Principal Axes 400

10.6.5 Tensor Invariants 401

10.7 Closure 401

10.7.1 Further Reading 401

11 Distortions and Noise in Images 403

11.1 Abstract 403

11.2 Types and Models of Noise 403

11.3 Generating Noisy Test Images 405

11.4 Generating Random Numbers with Normal Distributions 407

11.5 Closure 408

11.5.1 Further Reading 408

12 Image Warping Procedures 409

12.1 Abstract 409

12.2 Architecture of the Warping System 409

12.3 Coordinate Transformation Module 410

12.3.1 Projective and Affine Transformations of a Plane 410

12.3.2 Polynomial Transformations 411

12.3.3 Generic Coordinates Mapping 412

12.4 Interpolation of Pixel Values 412

12.4.1 Bilinear Interpolation 412

12.4.2 Interpolation of Nonscalar-Valued Pixels 414

12.5 The Warp Engine 414

12.6 Software Model of the Warping Schemes 415

12.6.1 Coordinate Transformation Hierarchy 415

12.6.2 Interpolation Hierarchy 416

12.6.3 Image Warp Hierarchy 416

12.7 Warp Examples 419

12.8 Finding the Linear Transformation from Point Correspondences 420

12.8.1 Linear Algebra on Images 424

12.9 Closure 427

12.9.1 Further Reading 428

13 Programming Techniques for Image Processing and Computer Vision 429

13.1 Abstract 429

13.2 Useful Techniques and Methodology 430

13.2.1 Design and Implementation 430

13.2.2 Template Classes 436

13.2.3 Asserting Code Correctness 438

13.2.4 Debugging Issues 440

13.3 Design Patterns 441

13.3.1 Template Function Objects 441

13.3.2 Handle-body or Bridge 442

13.3.3 Composite 445

13.3.4 Strategy 447

13.3.5 Class Policies and Traits 448

13.3.6 Singleton 450

13.3.7 Proxy 450

13.3.8 Factory Method 451

13.3.9 Prototype 452

13.4 Object Lifetime and Memory Management 453

13.5 Image Processing Platforms 455

13.5.1 Image Processing Libraries 455

13.5.2 Writing Software for Different Platforms 455

13.6 Closure 456

13.6.1 Further Reading 456

14 Image Processing Library 457

References 459

Index 475