CS223B L9 StructureFromMotion

Stanford CS223B Computer Vision, Winter 2007Lecture 8 Structure From Motion : Stanford CS223B Computer Vision, Winter 2007 Lecture 8 Structure From Motion Professors Sebastian Thrun and Jana Košecká CAs: Vaibhav Vaish and David Stavens Slide credit: Gary Bradski, Stanford SAIL


Summary SFM : Summary SFM Problem Determine feature locations (=structure) Determine camera extrinsic (=motion) Two Principal Solutions Bundle adjustment (nonlinear least squares, local minima) SVD (through orthographic approximation, affine geometry) Correspondence (RANSAC) Expectation Maximization


Structure From Motion : Structure From Motion Recover: structure (feature locations), motion (camera extrinsics)


SFM = Holy Grail of 3D Reconstruction : SFM = Holy Grail of 3D Reconstruction Take movie of object Reconstruct 3D model Would be commercially highly viable live.com


Structure From Motion (1) : Structure From Motion (1) [Tomasi & Kanade 92]


Structure From Motion (2) : Structure From Motion (2) [Tomasi & Kanade 92]


Structure From Motion (3) : Structure From Motion (3) [Tomasi & Kanade 92]


Structure From Motion (4a): Images : Structure From Motion (4a): Images Marc Pollefeys


Structure From Motion (4b) : Structure From Motion (4b) Marc Pollefeys


Structure From Motion (5) : Structure From Motion (5) http://www.cs.unc.edu/Research/urbanscape


Structure From Motion : Structure From Motion Problem 1: Given n points pij =(xij, yij) in m images Reconstruct structure: 3-D locations Pj =(xj, yj, zj) Reconstruct camera positions (extrinsics) Mi=(Aj, bj) Problem 2: Establish correspondence: c(pij)


Structure From Motion : Structure From Motion Recover: structure (feature locations), motion (camera extrinsics)


Recovery Problems : Recovery Problems


SFM: General Formulation : SFM: General Formulation


SFM: Bundle Adjustment : SFM: Bundle Adjustment


Bundle Adjustment : Bundle Adjustment SFM = Nonlinear Least Squares problem Minimize through Gradient Descent Conjugate Gradient Gauss-Newton Levenberg Marquardt common method Prone to local minima


Count # Constraints vs #Unknowns : Count # Constraints vs #Unknowns m camera poses n points 2mn point constraints 6m+3n unknowns Suggests: need 2mn  6m + 3n But: Can we really recover all parameters???


How Many Parameters Can’t We Recover? : How Many Parameters Can’t We Recover? Place Your Bet! We can recover all but… m = #camera poses n = # feature points


Count # Constraints vs #Unknowns : Count # Constraints vs #Unknowns m camera poses n points 2mn point constraints 6m+3n unknowns Suggests: need 2mn  6m + 3n But: Can we really recover all parameters??? Can’t recover origin, orientation (6 params) Can’t recover scale (1 param) Thus, we need 2mn  6m + 3n - 7


Are we done? : Are we done? No, bundle adjustment has many local minima.


The “Trick Of The Day” : The “Trick Of The Day” Replace Perspective by Orthographic Geometry Replace Euclidean Geometry by Affine Geometry Solve SFM linearly via PCA (“closed” form, globally optimal) Post-Process to make solution Euclidean Post-Process to make solution perspective By Tomasi and Kanade, 1992


Orthographic Camera Model : Orthographic Camera Model Orthographic = Limit of Pinhole Model:


Orthographic Projection : Orthographic Projection Limit of Pinhole Model: Orthographic Projection


The Orthographic SFM Problem : The Orthographic SFM Problem subject to


The Affine SFM Problem : The Affine SFM Problem subject to


Count # Constraints vs #Unknowns : Count # Constraints vs #Unknowns m camera poses n points 2mn point constraints 8m+3n unknowns Suggests: need 2mn  8m + 3n But: Can we really recover all parameters???


How Many Parameters Can’t We Recover? : How Many Parameters Can’t We Recover? Place Your Bet! We can recover all but…


The Answer is (at least): 12 : The Answer is (at least): 12


Points for Solving Affine SFM Problem : Points for Solving Affine SFM Problem m camera poses n points Need to have: 2mn  8m + 3n-12


Affine SFM : Affine SFM


The Rank Theorem : The Rank Theorem n elements 2m elements


Singular Value Decomposition : Singular Value Decomposition


Affine Solution to Orthographic SFM : Affine Solution to Orthographic SFM Gives also the optimal affine reconstruction under noise


Back To Orthographic Projection : Back To Orthographic Projection Find C for which constraints are met Search in 9-dim space (instead of 8m + 3n-12)


Back To Projective Geometry : Back To Projective Geometry Orthographic (in the limit) Projective


Back To Projective Geometry : Back To Projective Geometry Optimize Using orthographic solution as starting point


The “Trick Of The Day” : The “Trick Of The Day” Replace Perspective by Orthographic Geometry Replace Euclidean Geometry by Affine Geometry Solve SFM linearly via PCA (“closed” form, globally optimal) Post-Process to make solution Euclidean Post-Process to make solution perspective By Tomasi and Kanade, 1992


Structure From Motion : Structure From Motion Problem 1: Given n points pij =(xij, yij) in m images Reconstruct structure: 3-D locations Pj =(xj, yj, zj) Reconstruct camera positions (extrinsics) Mi=(Aj, bj) Problem 2: Establish correspondence: c(pij)


The Correspondence Problem : The Correspondence Problem View 1 View 3 View 2


Correspondence: Solution 1 : Correspondence: Solution 1 Track features (e.g., optical flow) …but fails when images taken from widely different poses


Correspondence: Solution 2 : Correspondence: Solution 2 Start with random solution A, b, P Compute soft correspondence: p(c|A,b,P) Plug soft correspondence into SFM Reiterate See Dellaert/Seitz/Thorpe/Thrun, Machine Learning Journal, 2003


Example : Example


Results: Cube : Results: Cube


Animation : Animation


Tomasi’s Benchmark Problem : Tomasi’s Benchmark Problem


Reconstruction with EM : Reconstruction with EM


3-D Structure : 3-D Structure


Correspondence: Alternative Approach : Correspondence: Alternative Approach Ransac [Fisher/Bolles] = Random sampling and consensus Will be discussed Wednesday


Summary SFM : Summary SFM Problem Determine feature locations (=structure) Determine camera extrinsic (=motion) Two Principal Solutions Bundle adjustment (nonlinear least squares, local minima) SVD (through orthographic approximation, affine geometry) Correspondence (RANSAC) Expectation Maximization