Fusiello Computer Vision: Three-dimensional Reconstruction Techniques

1. Auflage 2024
ISBN: 978-3-031-34507-4
Verlag: Springer International Publishing
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 338 Seiten, eBook

From facial recognition to self-driving cars, the applications of computer vision are vast and ever-expanding.  Geometry plays a fundamental role in this discipline, providing the necessary mathematical framework to understand the underlying principles of how we perceive and interpret visual information in the world around us.

 This text explores the theories and computational techniques used to determine the geometric properties of solid objects through images. It covers the basic concepts and provides the necessary mathematical background for more advanced studies.  The book is divided into clear and concise chapters covering a wide range of topics including image formation, camera models, feature detection and 3D reconstruction. Each chapter includes detailed explanations of the theory as well as practical examples to help the reader understand and apply the concepts presented.

 The book has been written with the intention of being used as a primary resource for students on university courses in computer vision, particularly final year undergraduate or postgraduate computer science or engineering courses.  It is also useful for self-study and for those who, outside the academic field, find themselves applying computer vision to solve practical problems. The aim of the book is to strike a balance between the complexity of the theory and its practical applicability in terms of implementation.  Rather than providing a comprehensive overview of the current state of the art, it offers a selection of specific methods with enough detail to enable the reader to implement them.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Fusiello, Andrea

Inhaltsverzeichnis

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 The Prodigy of vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Low-level Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 Overview of the Boook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Fundamentals of Imaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Digital Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 Thin Lenses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4.1 Telecentric Optics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 Radiometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 The Pinhole Camera Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2 Pinhole camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.3 Simplified Pinhole Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 General Pinhole Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.4.1 Intrinsic Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.4.1.1 Field of View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4.2 Extrinsic Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.5 Dissection of the Perspective Projection Matrix . . . . . . . . . . . . . . . . . 26

3.5.1 Collinearity Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.6 Radial Distortion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Camera Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2 The Direct Linear Transform Method . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3 Factorization of the Perspective Projection Matrix . . . . . . . . . . . . . . . 37

4.4 Calibrating Radial Distortion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.5 The Sturm-Maybank-Zhang Calibration Algorithm . . . . . . . . . . . . . . 39

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5 Absolute and Exterior Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.2 Absolute Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.2.1 Orthogonal Procrustes Analysis . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3 Exterior orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.3.1 Fiore’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.3.2 Procrustean Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.3.3 Direct Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6 Two-view Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2 Epipolar Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.3 Fundamental Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.4 Computing the Fundamental Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.4.1 The 7-points Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.4.2 Preconditioning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.5 Planar Homography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6.5.1 Computing the Homography . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.6 Planar Parallax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

7 Relative Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.2 The Essential Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.2.1 Geometric Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

7.2.2 Computing the Essential Matrix . . . . . . . . . . . . . . . . . . . . . . . 74

7.3 Relative Orientation from the Essential Matrix . . . . . . . . . . . . . . . . . . 75

7.3.1 Closed Form Factorization of the Essential Matrix . . . . . . . . 77

7.4 Relative Orientation from the Calibrated Homography . . . . . . . . . . . . 79

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Contents xv

8 Reconstruction from Two Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.2 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.3 Ambiguity of Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

8.4 Euclidean Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

8.5 Projective Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

8.6 Euclidean Upgrade from Known Intrinsic Parameters . . . . . . . . . . . . 89

8.7 Stratification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

9 Nonlinear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

9.2 Algebraic vs Geometric distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

9.3 Nonlinear Regression of the PPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

9.3.1 Residual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

9.3.2 Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

9.3.3 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

9.3.4 General Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

9.4 Nonlinear Regression of Exterior Orientation . . . . . . . . . . . . . . . . . . . 100

9.5 Nonlinear Regression of a Point in Space . . . . . . . . . . . . . . . . . . . . . . . 100

9.5.1 Residual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

9.5.2 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

9.5.3 Radial Distortion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

9.6 Regression in the Joint Image Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

9.7 Nonlinear Regression of the Homography . . . . . . . . . . . . . . . . . . . . . . 104

9.7.1 Residual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

9.7.2 Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

9.7.3 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

9.8 Nonlinear Regression of the Fundamental Matrix . . . . . . . . . . . . . . . . 107

9.8.1 Residual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

9.8.2 Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.8.3 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

9.9 Nonlinear Regression of Relative Orientation . . . . . . . . . . . . . . . . . . . 112

9.9.1 Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.9.2 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.10 Robust Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

10 Stereopsis: geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

10.2 Triangulation in the Normal Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

10.3 Epipolar Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

10.3.1 Calibrated Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

10.3.2 Uncalibrated Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

11 Features points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

11.2 Filtering Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

11.2.1 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

11.2.1.1 Non-linear Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

11.2.2 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

11.3 LoG Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

11.4 Harris-Stephens Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

11.4.1 Matching and tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

11.4.2 Kanade-Lucas-Tomasi Algorithm . . . . . . . . . . . . . . . . . . . . . . 146

11.4.3 Predictive Tracking. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

11.5 Scale Invariant Feature Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

11.5.1 Space-Scale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

11.5.2 SIFT Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

11.5.3 SIFT descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

11.5.4 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

12 Stereopsis: matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

12.2 Constraints and Ambiguities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

12.3 Local Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

12.3.1 Matching Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

12.3.2 Census Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

12.4 Adaptive Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

12.4.1 Multiresolution Stereo Matching . . . . . . . . . . . . . . . . . . . . . . . 166

12.4.2 Adaptive Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

12.5 Global Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

12.6 Post-processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

12.6.1 Reliability Indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

12.6.2 Occlusions Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

13 Range sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

13.2 Structured Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

13.2.1 Active Stereopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

13.2.2 Active Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

13.2.3 Ray-Plane Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

13.2.4 Scanning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

13.2.5 Coded Light Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

13.3 Time-of-Flight Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

13.4 Photometric Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

13.4.1 From Normals to Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . 188

13.5 Practical Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

14 Multiview Euclidean Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

14.1.1 Epipolar Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

14.1.2 The Case of Three Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

14.1.3 Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

14.2 Points-based Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

14.2.1 Adjustment of Independent Models . . . . . . . . . . . . . . . . . . . . . 199

14.2.2 Incremental Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

14.2.3 Hierarchical Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

14.3 Frames-based Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

14.3.1 Synchronization of Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . 203

14.3.2 Synchronization of Translations . . . . . . . . . . . . . . . . . . . . . . . . 205

14.3.3 Localization from Bearings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

14.4 Bundle Adjustment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

14.4.1 Jacobian of Bundle Adjustment . . . . . . . . . . . . . . . . . . . . . . . . 210

14.4.2 Reduced System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

15 3D Registration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

15.1.1 Generalised Procrustean Analysis . . . . . . . . . . . . . . . . . . . . . . . 218

15.2 Correspondence-less Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

15.2.1 Registration of Two Point-clouds . . . . . . . . . . . . . . . . . . . . . . . 220

15.2.2 Iterative Closest Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

15.2.3 Registration of Many Point-clouds . . . . . . . . . . . . . . . . . . . . . . 223

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

16 Multiview Projective Reconstruction and Autocalibration. . . . . . . . . . . 227

16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

16.1.1 Sturm-Triggs Factorization Method . . . . . . . . . . . . . . . . . . . . . 227

16.2 Autocalibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

16.2.1 Absolute Quadric Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . 231

16.2.1.1 Solution Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

Linear Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

Constant Intrinsic Parameters . . . . . . . . . . . . . . . . . . 233

16.2.2 Mendonça-Cipolla Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

16.3 Autocalibration via ?8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

16.4 Tomasi-Kanade’s Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

16.4.1 Affine Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

16.4.2 The Factorization Method for Affine Camera . . . . . . . . . . . . . 239

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

17 Multi-View Stereo Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

17.2 Volumetric Stereo in Object-space . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

17.2.1 Shape from Silhouette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

17.2.2 Szeliski’s Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

17.2.3 Voxel Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

17.2.4 Space Carving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

17.3 Volumetric Stereo in Image-space . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

Alignment of Epipolar Lines . . . . . . . . . . . . . . . . . . . 253

Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

Surface Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

17.4 Marching Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

18 Image-based Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

18.2 Parametric Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

18.2.1 Mosaics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

18.2.1.1 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

Synchronization of Homographies . . . . . . . . . . . . . . 261

18.2.1.2 Blending . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

18.2.2 Image Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

18.2.3 Perspective Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

18.3 Non-parametric Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

18.3.1 Transfer with Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

18.3.2 Transfer with Disparity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

18.3.3 Epipolar Transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

18.3.4 Transfer with Parallax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

18.3.5 Ortho-projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

18.4 Geometric Image Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

Bilinear Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 274

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276

A Notions of linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

A.2 Scalar Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

A.3 Matrix Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

A.4 Inverse Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

A.5 Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

A.6 Orthogonal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

A.7 Linear and Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

A.8 Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

A.9 QR Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

A.10 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

A.11 Singular Values Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

A.12 Pseudoinverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

A.13 Cross Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

A.14 Kronecker’s Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

A.15 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

A.16 Matrices Associated with Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

B Matrix Differential Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

B.1 Derivatives of Vector and Matrix Functions . . . . . . . . . . . . . . . . . . . . . 299

B.2 Derivative of Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

Axis/Angle Representation.. . . . . . . . . . . . . . . . . . . . 303

Euler Representation. . . . . . . . . . . . . . . . . . . . . . . . . . 303

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

C Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

C.2 Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

C.2.1 Linear Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

C.2.2 Nonlinear Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

C.2.2.1 Gauss-Newton Method . . . . . . . . . . . . . . . . . . . . . . . 307

C.2.3 The Levenberg-Marquardt Method . . . . . . . . . . . . . . . . . . . . . . 308

C.3 Robust Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

C.3.1 Outliers and Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

C.3.2 M-estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

C.3.3 Least Median of Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

C.3.4 RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

C.4 Propagation of Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

Propagation of Covariance in Least Squares. . . . . . 317

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

D Notions of Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

D.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

D.2 Perspective Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

D.3 Homogeneous Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

D.4 Equation of the Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

D.5 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

E Matlab Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

Über Autor(innen)

Andrea Fusiello has been teaching computer vision since 2000, first at the University of Verona and then at the University of Udine, where he is currently Professor of Computer Science. He has published more than 180 papers on these topics, and in 2011 he co-founded a start-up company that applies computer vision in the field.