3D reconstruction class 11Multiple View Geometry course schedule (subject to change)Slide Number 4Slide Number 5Slide Number 6Slide Number 7Slide Number 8Slide Number 9Slide Number 10Slide Number 11Slide Number 12Slide Number 13True Euclidean ReconstructionSlide Number 15Slide Number 16Slide Number 17Slide Number 18Slide Number 19Slide Number 20Slide Number 21Slide Number 22Slide Number 23Slide Number 24Slide Number 25Slide Number 26Slide Number 27Slide Number 28Slide Number 29Slide Number 30Slide Number 31Slide Number 32Slide Number 33Next class: Computing F3D reconstruction class 11Multiple View GeometryComp 290-089Marc PollefeysMultiple View Geometry course schedule (subject to change)Jan. 7, 9 Intro & motivation Projective 2D GeometryJan. 14, 16 (no class) Projective 2D GeometryJan. 21, 23 Projective 3D Geometry (no class)Jan. 28, 30 Parameter Estimation Parameter EstimationFeb. 4, 6 Algorithm Evaluation Camera ModelsFeb. 11, 13 Camera Calibration Single View GeometryFeb. 18, 20 Epipolar Geometry 3D reconstructionFeb. 25, 27 Fund. Matrix Comp. Structure Comp.Mar. 4, 6 Planes & Homographies Trifocal TensorMar. 18, 20 Three View Reconstruction Multiple View GeometryMar. 25, 27 MultipleView Reconstruction Bundle adjustmentApr. 1, 3 Auto-Calibration PapersApr. 8, 10 Dynamic SfM PapersApr. 15, 17 Cheirality PapersApr. 22, 24 Duality Project DemosTwo-view geometryEpipolar geometry3D reconstructionF-matrix comp.Structure comp.(i) Correspondence geometry: Given an image point x in the first image, how does this constrain the position of the corresponding point x’ in the second image?(ii) Camera geometry (motion): Given a set of corresponding image points {xi ↔x’i }, i=1,…,n, what are the cameras P and P’ for the two views?(iii) Scene geometry (structure): Given corresponding image points xi ↔x’i and cameras P, P’, what is the position of (their pre-image) X in space?Three questions:C1C2l2Pl1e1e20m m1T2=FFundamental matrix (3x3 rank 2 matrix)1. Computable from corresponding points2. Simplifies matching3. Allows to detect wrong matches4. Related to calibrationUnderlying structure in set of matches for rigid scenesl2C1m1L1m2L2MC2m1m2C1C2l2Pl1e1e2m1L1m2L2Ml2lT1Epipolar geometryCanonical representation: ]λe'|ve'F][[e'P' 0]|[IPT+==×3D reconstruction of cameras and structuregiven xi ↔x‘i , compute P,P‘ and Xireconstruction problem:iiPXx=iiXP'x=′for all iwithout additional informastion possible up to projective ambiguityoutline of reconstruction(i) Compute F from correspondences(ii) Compute camera matrices from F(iii) Compute 3D point for each pair of corresponding pointscomputation of Fuse x‘i Fxi =0 equations, linear in coeff. F8 points (linear), 7 points (non-linear), 8+ (least-squares)(more on this next class)computation of camera matricesuse ]λe'|ve'F][[e'P' 0]|[IPT+==×triangulationcompute intersection of two backprojected raysReconstruction ambiguity: similarity()()iiiXHPHPXxS-1S==Replace with Cameras P and P’ byPHs -1 and P’Hs -1 ÎDoes not change the imagePoint or the calibration Matrix of P and P’iXHSiXFor calibrated cameras, reconstruction is possible up to similarity &This is the only ambiguity of reconstruction (Longuet & Higgins 81)Reconstruction ambiguity: projective()()iiiXHPHPXx P-1 P==For uncaliberated cameras, ambiguity of reconstruction is expressed by an Arbitrary projective transformation.Terminologyxi ↔x‘iOriginal scene XiProjective, affine, similarity reconstruction = reconstruction that is identical to original up to projective, affine, similarity transformationLiterature: Metric and Euclidean reconstruction = similarity reconstructionThe projective reconstruction theoremIf a set of point correspondences in two views determine the fundamental matrix uniquely, then the scene and cameras may be reconstructed from these correspondences alone, and any two such reconstructions from these correspondences are projectively equivalent{}()i111X,'P,P{}()i222X,'P,Piixx′↔-112HPP =-112HPP′=′12HXX =()0FxFx :except=′=iikey result: allows reconstruction from pair of uncalibrated imagesPoints lying On line joining Two camera centersProjective reconstruction answers questions like:At what point does a line intersect a plane?What is the mapping between two views induced by planes?True Euclidean ReconstructionStratified reconstruction(i) Projective reconstruction(ii) Affine reconstruction(iii) Metric reconstructionProjective to affineremember 2-D caseProjective to affine{}()iX,P'P,()( )TT1,0,0,0,,,π aDCBA=∞()TT1,0,0,0πH-=∞⎥⎦⎤⎢⎣⎡=∞π0|I H(if D≠0)Now apply H to all points and to two cameras.Plane at infinity has been correctly place. This reconstruction differs from true Reconstruction up to projective transformation that fixes the plane at infinity. But projective with fixed π∞ is affine transformationAffine reconstruction can be sufficient depending on application, e.g. mid-point, centroid can be computedParallellism: lines constructed parallel to other lines and to planesQuestion: how to identify plane at infinityÎ need extra informationThe essence of affine reconstruction is to locate the plane at infinity; suppose We have somehow identified the plane at infinity. Projective reconstruction of the sceneTranslational motion to find plane at infinitypoints at infinity are fixed for a pure translation⇒ reconstruction of xi ↔ xi is on π∞⇒ Get three points on plane at infinity to reconstruct it. ××==]e'[]e[F0]|[IP=]e'|[IP=Scene constraints to find plane at infinityParallel linesparallel lines intersect at infinityreconstruction of corresponding vanishing point yields point on plane at infinity3 sets of parallel lines allow to uniquely determine π∞remark: in presence of noise determining the intersection of parallel lines is a delicate problemremark: obtaining vanishing point in one image can be sufficientScene constraintsScene constraintsDistance ratios on a line to find plane at infinityknown distance ratio along a line allow to determine point at infinity (same as 2D case)Given two intervales on a line with a known length ratio, the point at infinity on the line can be found Îfrom an image of a line on which a world distance ratiois known, for example that three points are equally spaced, the vanishing point may be determined.The infinity homography∞∞m]|[MP = ]m'|[M'P'=-1MM'H =∞()T0,X~X =∞X~Mx =∞X~M'x' =∞m]Ma|[MA10aAm]|[MP +=⎥⎦⎤⎢⎣⎡=-1-1MAAM'H