CORNELL CS 664 - Structure and Motion

Unformatted text preview:

CS 664Structure and MotionDaniel Huttenlocher2Determining 3D Structure Consider set of 3D points Xjseen by set of cameras with projection matrices Pi Given only image coordinates xijof each point in each image, determine 3D coordinates Xjand camera matrices Pi Known correspondence between points and known form of projection matrix…3Structure From Motion Recover 3D coordinates and (relative) camera locations Issues– Point correspondences and visibility of points– Projection model– Calibrated vs. un-calibrated cameras– Non-rigid motions, multiple motions– Numerical stability of methods4Projection Model Parallel (orthographic) Point X=(U,V,W) in space projects to x=(u,v) in image plane– Contrast with (fX/W,fY/W) in pinhole model– Light rays all parallel rather than through principal point• Similar when points at same depth, narrow FOV5Recovering 3D Structure With enough corresponding points and views can in principle determine 3D info– Redundant data• Each view changes only viewing parameters and not point locations− 3n unknowns for n points and d(k-1) unknowns for k views and d dof in transformation from one view to next− 2nk observed values• Overconstrained when 2nk ≥ 3n+d(k-1)− Optimization methods, for linear formulations generally least squares error minimization6Minimum Number of Measurements In principle can use small number of points and views– For instance, 5 points in two images for R,t• 5 dof + 3n point locations ≤ 4n point measurements when n ≥ 5 In 1980’s many variants investigated– Different projection models– Correspondences of lines, points– Some nice geometric problems, but studied in absence of noise sensitivity/stability analysis7Sensitive to Measurement Noise Solutions based on a small number of points are not stable– Errors of the magnitude found in most images yield substantial differences in recovered 3D values Method that works in practice called factorization [Tomasi-Kanade 92]– Works on sequence of several frames– With correspondences of points– Consider case of factorization for orthographic projection, no outliers, can be extended8Input: Sequence of Tracked Points Point coordinatesw’ij=(u’ij,v’ij)– Where i denotes frame (camera) indexand j denotes point index – Points tracked over frames• E.g., use corner trackers discussed previously…12 3K framesn pointsin eachframe9Centroid Normalized Coordinates From observed coordinates w’ij=(u’ij,v’ij)wfp=(u’ij-uij, v’ij-vij)– Whereuij= (1/n) ∑ju’ijandvij= (1/n) ∑jv’ij…Centroidsin frame10Normalization Goal of separating out effects of camera translation from those of rotation Subtract out centroid to remove translation effects– Assume all points belong to object and present at all frames– Centroid preserved under projection Left to recover 3D coordinates (shape) of n points from k camera orientations11Measurement Matrix 2n by k – 2 rows per frame, one col per point In absence of senor noise this matrix is highly rank deficient– Under orthographic projection rank 3 or lessW =⎥⎥⎥⎤⎢⎢⎢⎡u11⎦⎣u1n…uk1ukn………v11v1n…vk1vkn………⎢⎢⎢⎥⎥⎥12Structure of W World point sj’=(xj’,yj’,zj’) projects to image points u’ij= miT(sj’–ti)v’ij= niT(sj’–ti)– Where mi, niare unitvectors defining orientation of image plane in world– And tiis vector from world origin to image plane originminiti13Structure of W (Cont’d) Can rewrite in centroid normalized coordinates– Since centroid preserved under projection– Projection of centroid is centroid of projectionuij= miTsjvij= niTsj– Wheresj=sj’- sands = (1/n) ∑js’j14W Factors Into Simple Product W=MS where– M is 2kx3 matrix of camera locations– S is 3xn matrix of points in world– Product is 2kx3 matrix W• Clearly rank at most 3 ⎥⎥⎥⎤⎢⎢⎢⎡m1T⎦⎣mkT…n1TnkT…⎢⎢⎢⎥⎥⎥⎤⎡s1⎦⎣sn…M =S =15Factoring W Don’t know M,S only measurements W Given noise or errors in measurements seek least squares approximation– Note assuming no outliers (bad data)argminM,S⎟⎜W-MS⎟⎜2 Several methods for solving linear least squares problems– Here highly rank deficient, use SVD16Singular Value Decomposition Seek M,S from the SVD of W=UΣV– Where U and V are orthogonal and Σ is diagonal matrix Know from structure of problem that rank is at most 3– Consider only 3 largest singular values, let Σ’denote matrix with other singular values set to zero Then estimate M*=U Σ’½S*= Σ’½V17Factorization Not Unique Any linear transformation of M,S possibleW=MS=M(LL-1)S=(ML)(L-1S) Often referred to as “affine shape”– Preserves parallelism/coplanarity Still haven’t used a constraint on the form of M– Describes camera planeorientation at each framemi,niall unit vectorsmini= 0⎥⎥⎥⎤⎢⎢⎢⎡m1T⎦⎣mkT…n1TnkT…⎢⎢⎢⎥⎥⎥18Factorization Results19Extensions Paraperspective[Poelman & Kanade, PAMI 97] Sequential Factorization[Morita & Kanade, PAMI 97] Factorization under perspective[Christy & Horaud, PAMI 96][Sturm & Triggs, ECCV 96] Factorization with Uncertainty[Anandan & Irani, IJCV 2002]20Bundle Adjustment More generally don’t necessarily have linear least squares form of problem Technique from photogrammetry literature dating back many years Needs good initialization Estimate projection matrices and 3D points which minimize image distance d between re-projected and measured points ),(min'',,''ijjijiXPxXPdji∑21Bundle Adjustment Involves adjusting bundle of rays between each camera center and set of 3D points– Or equivalently, each 3D point and set of camera centers Maximum likelihood estimate under Gaussian noise model Xj’s depend on Pi’sand vice versa– Solved iteratively22Iterative Minimization Local search from initial solution– Convergence depends on solution quality In full projective case each camera has 11 dof and each point 3 dof– Often use 12 parameter homogeneous P matrix, so 3n+12k Using Levenberg-Marquardt algorithm– Matrices of dimension (3n+12k) x (3n+12k) can be slow to factor/invert Various approaches23Addressing Computational Issues  Solve smaller problems and merge… Interleave by alternately minimizing error by moving cameras for fixed point locations and vice versa– Limits matrices to 12x12


View Full Document
Download Structure and Motion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Structure and Motion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Structure and Motion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?