Computer vision encompasses the construction of integrated vision systems and the application of vision to problems of real-world importance. The process of creating 3D models is still rather difficult, requiring mechanical measurement of the camera positions or manual alignment of partial 3D views of a scene. However using algorithms, it is possible to take a collection of stereo-pair images of a scene and then automatically produce a photo-realistic, geometrically accurate digital 3D model. This book provides a comprehensive introduction to the methods, theories and algorithms of 3D computer vision. Almost every theoretical issue is underpinned with practical implementation or a working algorithm using pseudo-code and complete code written in C++ and MatLab®. There is the additional clarification of an accompanying website with downloadable software, case studies and exercises. Organised in three parts, Cyganek and Siebert give a brief history of vision research, and subsequently:   present basic low-level image processing operations for image matching, including a separate chapter on image matching algorithms; explain scale-space vision, as well as space reconstruction and multiview integration; demonstrate a variety of practical applications for 3D surface imaging and analysis; provide concise appendices on topics such as the basics of projective geometry and tensor calculus for image processing, distortion and noise in images plus image warping procedures. An Introduction to 3D Computer Vision Algorithms and Techniques is a valuable reference for practitioners and programmers working in 3D computer vision, image processing and analysis as well as computer visualisation. It would also be of interest to advanced students and researchers in the fields of engineering, computer science, clinical photography, robotics, graphics and mathematics.

Table of Contents:
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