计算机视觉structurefrommotionII专题知识专家讲座.pptx

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,计算机视觉structurefrommotionII专题知识专家讲座,第1页,Issues in SFM,Track lifetime,Nonlinear lens distortion,Degeneracy and critical surfaces,Prior knowledge and scene constraints,Multiple motions,计算机视觉structurefrommotionII专题知识专家讲座,第2页,Track lifetime,every 50th frame of a 800-frame sequence,计算机视觉structurefrommotionII专题知识专家讲座,第3页,Track lifetime,lifetime of 3192 tracks from the previous sequence,计算机视觉structurefrommotionII专题知识专家讲座,第4页,Track lifetime,track length histogram,计算机视觉structurefrommotionII专题知识专家讲座,第5页,Nonlinear lens distortion,计算机视觉structurefrommotionII专题知识专家讲座,第6页,Nonlinear lens distortion,effect of lens distortion,计算机视觉structurefrommotionII专题知识专家讲座,第7页,Prior knowledge and scene constraints,add a constraint that several lines are parallel,计算机视觉structurefrommotionII专题知识专家讲座,第8页,Prior knowledge and scene constraints,add a constraint that it is a turntable sequence,计算机视觉structurefrommotionII专题知识专家讲座,第9页,Factorization,Tomasi&Kanade,IJCV 92,计算机视觉structurefrommotionII专题知识专家讲座,第10页,Problem statement,计算机视觉structurefrommotionII专题知识专家讲座,第11页,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,计算机视觉structurefrommotionII专题知识专家讲座,第12页,Structure from motion,Estimate M,j,and p,i,to minimize,Assume isotropic Gaussian noise,it is reduced to,计算机视觉structurefrommotionII专题知识专家讲座,第13页,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:,计算机视觉structurefrommotionII专题知识专家讲座,第14页,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,计算机视觉structurefrommotionII专题知识专家讲座,第15页,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,计算机视觉structurefrommotionII专题知识专家讲座,第16页,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,),计算机视觉structurefrommotionII专题知识专家讲座,第17页,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,计算机视觉structurefrommotionII专题知识专家讲座,第18页,Results,计算机视觉structurefrommotionII专题知识专家讲座,第19页,Results,计算机视觉structurefrommotionII专题知识专家讲座,第20页,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第21页,Perspective and Perspective Factorization,Object-centered projection,the object-centered projection model,计算机视觉structurefrommotionII专题知识专家讲座,第22页,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.,计算机视觉structurefrommotionII专题知识专家讲座,第23页,Bundle Adjustment,计算机视觉structurefrommotionII专题知识专家讲座,第24页,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/,Structure from Motion,25,计算机视觉structurefrommotionII专题知识专家讲座,第25页,Bundle Adjustment,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第26页,Bundle Adjustment,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第27页,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第28页,2/3/,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.,计算机视觉structurefrommotionII专题知识专家讲座,第29页,2/3/,Structure from Motion,30,Sparse Cholesky(skyline),First used in finite element analysis,Applied to SfM by Szeliski&Kang 1994 structure|motion fill-in,计算机视觉structurefrommotionII专题知识专家讲座,第30页,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第31页,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第32页,2/3/,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,计算机视觉structurefrommotionII专题知识专家讲座,第33页,