CS223B L9 StructureFromMotion

Download
Share  Add to  Flag Embed
Uploaded from authorPOINTLite
Views:
 
Category: News & Reports..
     
 
License:   All Rights Reserved

Presentation Description

No description available.

Comments

Presentation Transcript

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