Description
Book SynopsisFrom 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.
Table of Contents1 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 퐻∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
