CS223B L9 StructureFromMotion

100 %
0 %
Information about CS223B L9 StructureFromMotion
News-Reports

Published on October 3, 2007

Author: craig

Source: authorstream.com

Stanford CS223B Computer Vision, Winter 2007 Lecture 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

Add a comment

Related presentations

Related pages

Monte Carlo Hidden Markov Models - Sebastian Thrun – Home

Stanford CS223B Computer Vision, Winter 2007 Lecture 8 Structure From Motion Professors Sebastian Thrun and Jana Košecká CAs: Vaibhav Vaish and David Stavens
Read more