ebook img

3D Reconstruction from Multiple Images PDF

188 Pages·2008·5.958 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview 3D Reconstruction from Multiple Images

3D reconstruction from multiple images Theo Moons, Maarten Vergauwen, and Luc Van Gool July 2008 2 Contents 1 Introduction to 3D Acquisition 7 1.1 A Taxonomy of Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 (Passive) Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Structure-from-Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Active Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Other Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.1 Time-of-Flight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.2 Shape-from-Shading and Photometric Stereo . . . . . . . . . . . . . . . . . 14 1.4.3 Shape-from-Texture and Shape-from-Contour . . . . . . . . . . . . . . . . . 15 1.4.4 Shape-from-Defocus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4.5 Shape-from-Silhouettes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4.6 Hybrid Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Image Formation and Camera Models 23 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 The Linear Camera Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.1 The Pinhole Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 ACamera-CenteredReferenceFrameandtheAssociatedProjectionEquations 24 2.2.3 AMatrixExpressionfortheProjectionEquationsAssociatedwithaCamera- Centered Reference Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.4 The General Linear Camera Model . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.5 Non-Linear Distortions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Camera Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.1 Internal Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.2 External Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3 Principles of Passive 3D Reconstruction 37 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 The 3D Reconstruction Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 The Epipolar Relation Between Two Images of a Static Scene . . . . . . . . . . . . 39 3.4 3D Reconstruction Equations Up-Close . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4.1 Euclidean 3D Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4.2 Metric 3D Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4.3 Affine 3D Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4.4 Projective 3D Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4.5 Taking Stock - Stratification . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4.6 From Projective to Metric Using More Than Two Images . . . . . . . . . . 50 3.5 Some Important Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.5.1 Camera Translation and Stereo Rigs . . . . . . . . . . . . . . . . . . . . . . 55 3 4 CONTENTS 3.5.2 Pure Rotation around the Camera Center . . . . . . . . . . . . . . . . . . . 58 4 Epipolar Geometry in Practice 61 4.1 Finding seed correspondences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1.1 Interest points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1.2 Other seed features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Epipolar geometry - implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2.1 Pairs of epipolar lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2.2 Computation of the Fundamental Matrix . . . . . . . . . . . . . . . . . . . 66 4.2.3 RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5 Relations between Multiple Views 73 5.1 The Trifocal Relations Between Three Images of a Static Scene . . . . . . . . . . . 73 5.1.1 The Fundamental Trifocal Relation between Three Images . . . . . . . . . . 74 5.1.2 The Trifocal Relation between Corresponding Lines . . . . . . . . . . . . . 78 5.1.3 The Trifocal Relations between Corresponding Image Points. . . . . . . . . 80 5.1.4 The Trifocal Constraints as Incidence Relations . . . . . . . . . . . . . . . . 81 5.1.5 The Trifocal Constraints as a Transfer Principle . . . . . . . . . . . . . . . 82 6 Structure and Motion 85 6.1 Computing Projection Matrices and a Projective Reconstruction . . . . . . . . . . 85 6.1.1 Initialization Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.1.2 Projective Pose Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.1.3 Updating Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.1.4 Global Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.2 The Projective Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.3 Scene Constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.4 Self-Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.4.1 Conics and Quadrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.4.2 The Absolute Conic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.4.3 Practical Constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4.4 Coupled Self-Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7 Model Selection 103 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.2 Problems with Planar Scenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.3 Detecting Planar Scenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.3.1 Occam’s Razor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.3.2 GRIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.4 More GRICs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.5 Long Video Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 7.5.1 Video Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7.5.2 Long Sequences and Subsequences . . . . . . . . . . . . . . . . . . . . . . . 112 7.5.3 Intermediate Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.5.4 Blurry Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 8 Essential Matrices 121 8.1 Essential Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.1.1 Normalized Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.1.2 The Essential Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.1.3 Properties of the Essential Matrix . . . . . . . . . . . . . . . . . . . . . . . 122 8.1.4 Cameras from the Essential Matrix . . . . . . . . . . . . . . . . . . . . . . . 123 8.2 Computation of the Essential Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 124 8.2.1 8 and 7 Point Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 CONTENTS 5 8.2.2 6 Point Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 8.2.3 5 Point Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 8.2.4 Planar Degeneracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 9 Bundle Adjustment 129 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 9.2 Levenberg-Marquardt Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 9.3 Sparse Bundle Adjustment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 10 Dense Matching 137 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.2 Rectification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.2.1 Planar Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.2.2 Polar Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 10.3 Stereo Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 10.3.1 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 10.3.2 Matching Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 10.3.3 Cost Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 10.3.4 Hierarchical Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 10.3.5 Post Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 10.4 Linking Stereo Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 10.5 Fast Matching on the GPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 10.5.1 Why GPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 10.5.2 Basic Setup and Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . 151 10.5.3 Hierarchical Plane-Sweep Algorithm . . . . . . . . . . . . . . . . . . . . . . 151 10.5.4 The Connectivity Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . 152 10.5.5 Retrieval Of Fine Structures . . . . . . . . . . . . . . . . . . . . . . . . . . 153 10.5.6 Smoothness Penalty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 10.6 Bayesian Multi-View Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 11 3D Webservice 159 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 11.1.1 3D Technologies in the Cultural Heritage Field . . . . . . . . . . . . . . . . 159 11.1.2 Low-cost Pipeline for 3D Reconstruction . . . . . . . . . . . . . . . . . . . . 159 11.1.3 Chapter Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 11.2 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 11.2.1 Upload Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 11.2.2 Modelviewer Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 11.3 Automatic Reconstruction Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 11.3.1 Pipeline Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 11.3.2 Opportunistic Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 11.3.3 Hierarchical Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 11.3.4 Parallel Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 11.4 Global Image Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 11.5 Self-calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 11.5.1 Classical SaM techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 11.5.2 Triplet Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 11.5.3 Coupled Self-calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 11.5.4 Statistical Coupled Self-calibration . . . . . . . . . . . . . . . . . . . . . . . 171 11.6 Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 11.6.1 Upscaling the Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 11.6.2 Robust Euclidean Bundle Adjustment . . . . . . . . . . . . . . . . . . . . . 174 11.7 Dense Matching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 11.7.1 Linked Pairwise Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 6 CONTENTS 11.7.2 Multi-View Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 11.8 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 Chapter 1 Introduction to 3D Acquisition This chapter discusses different methods for capturing or ‘acquiring’ the 3-dimensional shape of surfaces and, in some cases, also the distance of the object to the 3D device. Such distance is often referred to as ‘range’. The chapter aims at positioning the methods discussed in this text within this more global context. This will make clear that alternative methods may actually be better suited for some applications that need 3D. This said, the discussion will also show that the approach described here is one of the more attractive and powerful ones. The reader will be able to experiment with the described techniques through the ARC3D Webservice. Aswewillexplainattheendofthetutorial,thisisafreeservice(fornon-commercial use) which lets users upload images to a central server, and then applies the described techniques to extract depth maps for each uploaded image. As a by-product, also the spatial arrangement of the camera positions is supplied. This webservice can be visited at www.arc3d.be. 1.1 A Taxonomy of Methods A 3-D acquisition taxonomy is given in Figure 1.1. A first distinction is between active and passive methods. With active techniques the light sources are specially controlled, as part of the strategy to arrive at the 3D information. Active lighting incorporates some form of temporal or spatial modulation of the illumination. With pas- sive techniques, on the other hand, light is not controlled or only with respect to image quality. Typically they work with whatever ambient light that is available. From a computational viewpoint, active methods tend to be less demanding, as the special illu- mination is used to simplify some of the steps in the 3D capturing process. Their applicability is restricted to environments where the special illumination techniques can be applied. Aseconddistinctionisbetweenthenumberofvantagepointsfromwherethesceneisobserved and/or illuminated. With single-vantage methods the system works from a single vantage point. In case there are multiple viewing or illumination components, these are positioned close to each other,andideallytheywouldcoincide. Thelattercansometimesberealisedvirtually,throughop- tical means like semi-transparent mirrors. With multi-vantage systems, several viewpoints and/or controlled illumination source positions are involved. For multi-vantage systems to work well, the different components often have to be positioned far emough from each other. One says that the ‘baseline’ between the components has to be wide enough. Single-vantage methods have as advantages that they can be made compact and that they suffer less from occlusion problems with parts of the scene not visible from all vantage points. The methods mentioned in the taxonomy will now be discussed in a bit more detail. In the remaining chapters, we then continue with the more detailed discussion of passive, multi-vantage Structure-from-Motion (SfM) techniques, the actual subject of this tutorial. As this overview of 3D acquisition methods is not intendedto be in-depth nor exhaustive, we don’t include references in this part. 7 8 CHAPTER 1. INTRODUCTION TO 3D ACQUISITION Figure 1.1: Taxonomy of methods for the extraction of information on 3D shape. 1.2 Triangulation Several multi-vantage approaches use the principle of triangulation for the extraction of depth information. This also is the key concept exploited by the structure-from-motion (SfM) methods described here. 1.2.1 (Passive) Stereo Supposewehavetwoimages,takenatthesametimeandfromdifferentviewpoints. Suchsettingis referred to as stereo. The situation is illustrated in Figure 1.2. The principle behind stereo-based 3D reconstruction is simple: given the two projections of the same point in the world onto the twoimages,its3Dpositionisfoundastheintersectionofthetwoprojectionrays. Repeatingsuch process for several points yields the 3D shape and configuration of the objects in the scene. Note thatthisconstruction–referredtoastriangulation–requirescompleteknowledgeofthecameras: their (relative) positions and orientations, but also their settings like the focal length. These camera parameters will be discussed in chapter 2. The process to determine these parameters is called (camera) calibration. Moreover, in order to perform this triangulation process, one needs ways of solving the corre- spondence problem, i.e. finding the point in the second image that corresponds to a specific point in the first image, or vice versa. Correspondence search actually is the hardest part of stereo, and one would typically have to solve it for many points. Often the correspondence problem is solved in two stages. First, correspondences are sought for those points for which this is easiest. Then, correspondences are sought for the remaining points. This will be explained in more detail in subsequent chapters. 1.2.2 Structure-from-Motion Passive stereo uses two cameras, usually synchronised. If the scene is static, the two images could also be taken by placing the same camera at the two positions, and taking the images in sequence. Clearly, once such strategy is considered, one may just as well take more than two images, while moving the camera. If images are taken over short time intervals, it will be easier to find correspondences, e.g. by tracking feature points over time. Moreover, having more camera views will yield object models that are more complete. Last but not least, if multiple views are 1.2. TRIANGULATION 9 Figure 1.2: The principle behind stereo-based 3D reconstruction is very simple: given two images of a point, the point’s position in space is found as the intersection of the two projection rays. 10 CHAPTER 1. INTRODUCTION TO 3D ACQUISITION O P P’ I L Figure 1.3: The triangulation principle used already with stereo, can also be used in an active configuration. The laser L projects a ray of light onto the object O. The intersection point P with the object is viewed by a camera and forms the spot P(cid:48) on its image plane I. This information suffices for the computation of the three-dimensional coordinates of P, assuming that the laser- camera configuration is known. available, the camera(s) need no longer be calibrated beforehand, and a self-calibration procedure maybeemployedinstead. Self-calibrationmeansthattheinternalandexternalcameraparameters (see next chapter) are extracted from the images directly. These properties render SfM a very attractive 3D acquisition strategy. A more detailed discussion is given in the following chapters. 1.3 Active Triangulation Finding corresponding points can be facilitated by replacing one of the cameras in a stereo setup byaprojectiondevice. Hence,wecombineoneilluminationsourcewithonecamera. Forinstance, one can project a spot onto the object surface with a laser. The spot will be easily detectable in the image taken by the camera. If we know the position and orientation of both the laser ray and the camera projection ray, then the 3D surface point is found as their intersection. The principle is illustrated in Figure 1.3. The problem is that knowledge about the 3D coordinates of one point is hardly sufficient in most applications. Hence, in the case of the laser, it should be directed at different points on the surfaceandeachtimeanimagehastobetaken. Inthisway,the3Dcoordinatesofthesepointsare extracted, one point at a time. Such a ‘scanning’ process requires precise mechanical apparatus (e.g. bysteeringrotatingmirrorsthatreflectthelaserlightintocontrolleddirections). Ifthelaser

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.