CS223B L9 StructureFromMotion

Information about CS223B L9 StructureFromMotion

Published on October 3, 2007

Author: craig

Source: authorstream.com

Content

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

Related presentations


Other presentations created by craig

hae livingwagepp
13. 04. 2008
0 views

hae livingwagepp

Hamburg 2 zensiert
07. 04. 2008
0 views

Hamburg 2 zensiert

Unit II Ch 26 Sect 1
27. 03. 2008
0 views

Unit II Ch 26 Sect 1

Kaohsiung Speech
26. 03. 2008
0 views

Kaohsiung Speech

projectsummary
21. 03. 2008
0 views

projectsummary

Presentation Ljubljana 20041214
18. 03. 2008
0 views

Presentation Ljubljana 20041214

docNews308
14. 03. 2008
0 views

docNews308

PBC KamalMeattle 11Oct2005
12. 03. 2008
0 views

PBC KamalMeattle 11Oct2005

Toronto 09 28 07
10. 03. 2008
0 views

Toronto 09 28 07

kramer
27. 09. 2007
0 views

kramer

oct98 g
11. 10. 2007
0 views

oct98 g

03 05board
03. 10. 2007
0 views

03 05board

Hindu Sangam 2006 D
05. 12. 2007
0 views

Hindu Sangam 2006 D

Collection Systems
07. 11. 2007
0 views

Collection Systems

Canada and World War II
13. 11. 2007
0 views

Canada and World War II

Dr Nikolaos Dimakis nano panam
21. 11. 2007
0 views

Dr Nikolaos Dimakis nano panam

Richels
28. 11. 2007
0 views

Richels

KS3PDW
04. 10. 2007
0 views

KS3PDW

Be Careful
26. 09. 2007
0 views

Be Careful

2004 eslestirme projesi
21. 11. 2007
0 views

2004 eslestirme projesi

Waterwkshp1207 Matney
31. 12. 2007
0 views

Waterwkshp1207 Matney

chippowerpoint
26. 02. 2008
0 views

chippowerpoint

MILITARY JUSTICE 1stSgt BRIEF
28. 02. 2008
0 views

MILITARY JUSTICE 1stSgt BRIEF

SocialNetwork
29. 12. 2007
0 views

SocialNetwork

Alistair Miles SKOSxmluk2005
04. 12. 2007
0 views

Alistair Miles SKOSxmluk2005

CHINA 2
28. 11. 2007
0 views

CHINA 2

SAFIE RMS Tasks Tools Needs
20. 11. 2007
0 views

SAFIE RMS Tasks Tools Needs

12 Saket Forest Res Assessment
23. 11. 2007
0 views

12 Saket Forest Res Assessment

Lacrimal
16. 11. 2007
0 views

Lacrimal

gonzalez
23. 11. 2007
0 views

gonzalez

0051582
16. 11. 2007
0 views

0051582