Multiple View Reconstruction Class 25 Multiple View Geometry Comp 290-089 Marc Pollefeys Content Background: Projective geometry (2D, 3D), Parameter estimation, Algorithm evaluation. Single View: Camera model, Calibration, Single View Geometry.

Two Views: Epipolar Geometry, 3D reconstruction, Computing F, Computing structure, Plane and homographies. Three Views: Trifocal Tensor, Computing T. More Views: N-Linearities, Self-Calibration, Multi View Reconstruction, Bundle adjustment, Cheirality, Duality, Dynamic SfM Multi-view computation practical structure and motion recovery from images

Obtain reliable matches using matching or tracking and 2/3-view relations Compute initial structure and motion sequential structure and motion recovery hierarchical structure and motion recovery Refine structure and motion bundle adjustment Auto-calibrate Refine metric structure and motion

Sequential SaM recovery Select two initial views Extract features Compute two-view geometry and matches Initialize projective pose for two-views Initialize new structure For every additional view i Extract features Compute two view geometry i-1/i and matches Compute pose using robust algorithm Refine existing structure

Initialize new structure Refine proj. SaM estimation Self-calibrate Refine metr.SaM estimation X F x Hierarchical structure and

motion recovery Compute 2-view Compute 3-view Stitch 3-view reconstructions Merge and refine reconstruction F T H PM Refining structure and motion

Minimize reprojection error m n min D mki , PkMi Pk ,M i 2

k 1 i 1 Maximum Likelyhood Estimation (if error zero-mean Gaussian noise) Huge problem but can be solved efficiently (Bundle adjustment)

Sparse bundle adjustment LM iteration: m -1 T J J J e T n Jacobian of

D m ki , Pk M i 2 has sparse block k 1 i 1 structure

P1 P2 P3 M U1 im.pts. view 1

U2 J W N JT J U3 WT 12xm

3xn (in general much larger) V Needed for non-linear minimization Sparse bundle adjustment Eliminate dependence of camera/motion parameters on structure parameters

Note in general 3n >> 11m 1 I WV N 0 I Allows much more efficient computations e.g. 100 views,10000 points, solve 1000x1000, not 30000x30000

Often still band diagonal use sparse linear algebra algorithms U-WV-1WT WT V 11xm

3xn Degenerate configurations (H&Z Ch.21) Camera resectioning Two views More views Camera resectioning Cameras as points

2D case Chasles theorem Ambiguity for 3D cameras Twisted cubic (or less) meeting lin. subspace(s) (degree+dimension<3) Ambiguous two-view reconstructions Ruled quadric containing both scene points and camera centers alternative reconstructions exist for which the reconstruction of points located

off the quadric are not projectively equivalent hyperboloid 1s cone pair of planes single plane + 2 points single line + 2 points Multiple view reconstructions Single plane is still a problem Hartley and others looked at 3

and more view critical configurations, but those are rather exotic and are not a problem in practice. Carlsson-Weinshall duality (H&Z Ch.19) Exchange role of points and cameras Dualize algorithm for n views and m+4 points to algorithm for

m views and n+4 points e.g. (2im,7+pts)(3+im,6pts) Reduced camera duality Reduced camera: Carlsson-Weinshall duality Reduced camera reconstruction

N M M N Obtain reduced cameras Pick 4 reference points to form projective basis in P 2 e1 , e2 , e3 , e4

E1 , E2 , E3 , E4 Dual algorithm outline: input transpose transform Solve dual problem Dualize

Transform to Reverse transform reduced cameras extend Applications 6 points in 3 views minimal, useful for 3-view RANSAC reduced F-matrix (eiTFei=0,i=14)

in N views useful for reconstruction from tracks 7 points in 4 or more views reduced trifocal tensor 6 points in N views (Hartley and Dano CVPR00) use Sampson error in stead of algebraic (important because of projective warping!)

Oriented projective geometry (~H&Z Ch.20) two geometric entities are equivalent if they are equal up to a strictly positive scale factor projective geometry oriented projective geometry (from PhD Stephane Laveau)

Oriented projective geometry front back Oriented line oriented line pxq goes from p to q over shortest distance Oriented plane

Front LT X 0 Camera focal plane In front of camera P1 P P2 P3 or

P3 X 0 w0 x x y PX w oriented plane through camera center and 3D point

M C Oriented epipolar plane 1 point correspondence allows orientation Eliminates zone and But not ( not known) Multi camera orientation constraint

Hartleys Cheirality Nisters QUARC Application to view synthesis Laveau96 which point is in front? Epipole orientation Next class:

Dynamic structure from motion