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