计算机视觉15 7.2 structure from motion II

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2/3/2005,Structure from Motion,*,Multi-frame Structure from Motion,Issues in SFM,Track lifetime,Nonlinear lens distortion,Degeneracy and critical surfaces,Prior knowledge and scene constraints,Multiple motions,Track lifetime,every 50th frame of a 800-frame sequence,Track lifetime,lifetime of 3192 tracks from the previous sequence,Track lifetime,track length histogram,Nonlinear lens distortion,Nonlinear lens distortion,effect of lens distortion,Prior knowledge and scene constraints,add a constraint that several lines are parallel,Prior knowledge and scene constraints,add a constraint that it is a turntable sequence,Factorization,Tomasi & Kanade, IJCV 92,Problem statement,Notations,n,3D points are seen in,m,views,q,=(u,v,1): 2D image point,p,=(x,y,z,1): 3D scene point,: projection matrix,: projection function,q,ij,is the projection of the,i,-th point on image,j,ij,projective depth of,q,ij,Structure from motion,Estimate M,j,and p,i,to minimize,Assume isotropic Gaussian noise, it is reduced to,SFM under orthographic projection,2D image,point,orthographic,projection,matrix,3D scene,point,image,offset,Trick,Choose scene origin to be centroid of 3D points,Choose image origins to be centroid of 2D points,Allows us to drop the camera translation:,factorization (Tomasi & Kanade),projection of,n,features in one image:,projection of,n,features in,m,images,W,measurement,M,motion,S,shape,Key Observation:,rank,(,W,) = 3,Factorization Technique,W,is at most rank 3 (assuming no noise),We can use,singular value decomposition,to factor,W,:,Factorization,S,differs from,S,by a linear transformation,A,:,Solve for,A,by enforcing,metric,constraints on,M,known,solve for,Metric constraints,Orthographic Camera,Rows of,P,are orthonormal:,Enforcing “Metric” Constraints,Compute,A,such that rows of,M,have these properties,Trick,(not in original Tomasi/Kanade paper, but in followup work),Constraints are linear in,AA,T,:,Solve for,G,first by writing equations for every,P,i,in,M,Then,G,=,AA,T,by SVD (since,U,=,V,),Factorization with noisy data,SVD gives this solution,Provides optimal rank 3 approximation,W,of,W,Approach,Estimate,W, then use noise-free factorization of,W,as before,Result minimizes the SSD between positions of image features and projection of the reconstruction,Results,Results,2/3/2005,Structure from Motion,21,Extensions,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,Perspective and Perspective Factorization,Object-centered projection,the object-centered projection model,Perspective and Perspective Factorization,the object-centered projection model,In practice, after an initial reconstruction, the values of,j,can be estimated independently for each frame by comparing reconstructed and sensed point positions.,Once the,j,have been estimated, the feature locations can then be corrected before applying another round of factorization.,Bundle Adjustment,Bundle Adjustment,The term ”bundle” refers to the bundles of rays connecting camera centers to 3D points.,The term ”adjustment” refers to the iterative minimization of re-projection error. Alternative terms for this in the vision community include optimal motion estimation and non-linear least squares.,2/3/2005,Structure from Motion,25,Bundle Adjustment,2/3/2005,Structure from Motion,26,The formula for the radial distortion function is,The feature location measurements x,ij,now depend not only on the point (track index),i, but also on the camera pose index,j,Bundle Adjustment,2/3/2005,Structure from Motion,27,The leftmost box performs a robust comparison of the predicted and measured 2D locations after re-projection.,is the noise covariance,2/3/2005,Structure from Motion,28,Bundle Adjustment,What makes this non-linear minimization hard?,many more parameters: potentially slow,poorer conditioning (high correlation),potentially lots of outliers,gauge (coordinate) freedom,2/3/2005,Structure from Motion,29,Lots of parameters: sparsity,Only a few entries in Jacobian are non-zero,(a) Bipartite graph for a toy structure from motion problem and (b) its associated Jacobian J and (c) Hessian A.,2/3/2005,Structure from Motion,30,Sparse Cholesky (skyline),First used in finite element analysis,Applied to SfM by Szeliski & Kang 1994 structure | motion fill-in,2/3/2005,Structure from Motion,31,Conditioning and gauge freedom,Poor conditioning:,use 2,nd,order method,use Cholesky decomposition,Gauge freedom,fix certain parameters (orientation),or,zero out last few rows in Cholesky decomposition,2/3/2005,Structure from Motion,32,Robust error models,Outlier rejection,use robust penalty appliedto each set of jointmeasurements,for extremely bad data, use random sampling RANSAC, Fischler & Bolles, CACM81,2/3/2005,Structure from Motion,33,RAN,dom,SA,mple,C,onsensus,Related to least median squares Stewart99,Repeatedly select a small (minimal) subset of correspondences,Estimate a solution (structure & motion),Count the number of “inliers”,|,e,|,(for LMS, estimate,med(|,e,|),Pick the,best,subset of inliers,Find a complete least-squares solution,2/3/2005,Structure from Motion,34,Correspondences,Can refine feature matching,after,a structure and motion estimate has been produced,decide which ones obey the,epipolar geometry,decide which ones are,geometrically consistent,(optional) iterate between correspondences and SfM estimates using MCMC,Dellaert,et al.,Machine Learning 2003,