1、ComputerVisionProjective structure from motionMarc PollefeysCOMP 256Some slides and illustrations from J.Ponce,ComputerVision2Last class:Affine camera The affine projection equations are 1 jjjyixiijijZYXPPyxhow to find the origin?or for that matter a 3D reference point?affine projection preserves ce
2、nter of gravityiijijijxxx iijijijyyy 21tt jjjyixiijijZYXPPyxComputerVision3Orthographic factorization The orthographic projection equations are where njmijiij,.,1,.,1,Xx P All equations can be collected for all i and j wherenmmnmmnnX,.,X,X,xxxxxxxxx2121212222111211XPPPPxXPx X xjjjjyixiiijijijZYX,PP,
3、yxPNote that P and X are resp.2mx3 and 3xn matrices and therefore the rank of x is at most 321tt jjjyixiijijZYXPPyxComputerVision4Orthographic factorization Factorize m through singular value decomposition An affine reconstruction is obtained as followsTVUxT,VXUPnmmnmmnnX,.,X,X xxxxxxxxxmin212121222
4、2111211PPPClosest rank-3 approximation yields MLE!ComputerVision5Jan 16/18-IntroductionJan 23/25CamerasRadiometryJan 30/Feb1Sources&ShadowsColorFeb 6/8Linear filters&edgesTextureFeb 13/15Multi-View GeometryStereoFeb 20/22Optical flowProject proposalsFeb27/Mar1Affine SfMProjective SfMMar 6/8Camera Ca
5、librationSilhouettes and PhotoconsistencyMar 13/15SpringbreakSpringbreakMar 20/22SegmentationFittingMar 27/29Prob.SegmentationProject UpdateApr 3/5TrackingTrackingApr 10/12Object RecognitionObject RecognitionApr 17/19Range dataRange dataApr 24/26Final projectFinal project Tentative class scheduleCom
6、puterVision6PROJECTIVE STRUCTURE FROM MOTION Reading:Chapter 13.The Projective Structure from Motion Problem Elements of Projective Geometry Projective Structure and Motion from Two Images Projective Motion from Fundamental Matrices Projective Structure and Motion from Multiple ImagesComputerVision7
7、The Projective Structure-from-Motion ProblemGiven m perspective images of n fixed points P we can writeProblem:estimate the m 3x4 matrices M andthe n positions P from the mn correspondences p .ijij2mn equations in 11m+3n unknownsOverconstrained problem,that can be solvedusing(non-linear)least square
8、s!jComputerVision8The Projective Ambiguity of Projective SFMIf M and P are solutions,ijSo are M and P whereijand Q is an arbitrary non-singular 4x4 matrix.When the intrinsic and extrinsic parameters are unknownQ is a projective transformation.ComputerVision9Projective Spaces:(Semi-Formal)DefinitionC
9、omputerVision10A Model of P(R )3ComputerVision11Projective Subspaces and Projective CoordinatesComputerVision12Projective Subspaces and Projective CoordinatesProjectivecoordinatesPComputerVision13Projective SubspacesGiven a choice of coordinate frameLine:Plane:ComputerVision14Affine and Projective S
10、pacesComputerVision15Affine and Projective CoordinatesComputerVision16Cross-RatiosCollinear pointsPencil of coplanar linesPencil of planesA,B;C,D=sin(+)sin(+)sin(+)sinComputerVision17Cross-Ratios and Projective CoordinatesAlong a line equipped with the basisIn a plane equipped with the basisIn 3-spa
11、ce equipped with the basis*ComputerVision18Projective TransformationsBijective linear map:Projective transformation:(=homography)Projective transformations map projective subspaces ontoprojective subspaces and preserve projective coordinates.Projective transformations map lines onto lines andpreserv
12、e cross-ratios.ComputerVision19Perspective Projections induce projective transformationsbetween planes.ComputerVision20Geometric SceneReconstructionIdea:use(A,O”,O,B,C)as a projective basis.ComputerVision21Reprinted from“Relative Stereo and Motion Reconstruction,”by J.Ponce,T.A.Cass and D.H.Marimont
13、,Tech.ReportUIUC-BI-AI-RCV-93-07,Beckman Institute,Univ.of Illinois(1993).ComputerVision22Motion estimation from fundamental matricesQFacts:b can be found using LLS.Once M and M are known,P can be computed with LLS.ComputerVision23Projective Structure from Motion and FactorizationFactorization?Algor
14、ithm(Sturm and Triggs,2019)Guess the depths;Factorize D;Iterate.Does it converge?(Mahamud and Hebert,2000)ComputerVision24Bundle adjustment-refining structure and motion Minimize reprojection error Maximum Likelyhood Estimation(if error zero-mean Gaussian noise)Huge problem but can be solved efficie
15、ntly(exploit sparseness)minjjiijDji112X,PXP,xminComputerVision25 Developed in photogrammetry in 50sBundle adjustmentComputerVision26Non-linear least squares Linear approximation of residual allows quadratic approximation of sum-of-squaresJ0e0T1-T0TTJJJ0J2J2Jee JJ00eeTJ)diag(JJJNTTN(extra term=descen
16、t term)Minimization corresponds to finding zeros of derivativeLevenberg-Marquardt:extra term to deal with singular N(decrease/increase l if success/failure to descent)ComputerVision27Bundle adjustmentU1U2U3WTWVP1P2P3M Jacobian of has sparse block structure cameras independent of other cameras,points
17、 independent of other pointsJJJNT12xm3xn(in general much larger)im.pts.view 1minjjiijD112MP,mNeeded for non-linear minimizationComputerVision28Bundle adjustmentEliminate dependence of camera/motion parameters on structure parametersNote in general 3n 11mWTVU-WV-1WTNI0WVI111xm3xnAllows much more effi
18、cient computations e.g.100 views,10000 points,solve 1000 x1000,not 30000 x30000Often still band diagonaluse sparse linear algebra algorithms ComputerVision29Sequential SfM Initialize motion from two images Initialize structure For each additional view Determine pose of camera Refine and extend struc
19、ture Refine structure and motionComputerVision30Initial projective camera motion Choose P and Pcompatible with FReconstruction up to projective ambiguity eeae0333TFPIP(reference plane;arbitrary)Initialize motionInitialize structureFor each additional viewDetermine pose of cameraRefine and extend str
20、uctureRefine structure and motioneaee?TFPSame for more views?different projective basisComputerVision31Initializing projective structure Reconstruct matches in projective frame by minimizing the reprojection error222211XP,xXP,xDDNon-iterative optimal solutionInitialize motionInitialize structureFor
21、each additional viewDetermine pose of cameraRefine and extend structureRefine structure and motionComputerVision32Projective pose estimation Infere 2D-3D matches from 2D-2D matches Compute pose from (RANSAC,6pts)XxP0XX0X0XpyxTTTTFXxInliers:inx,X x XDDiiiPInitialize motionInitialize structureFor each
22、 additional viewDetermine pose of cameraRefine and extend structureRefine structure and motionComputerVision33 Refining structure Extending structure2-view triangulation 0XPPPP1313yxXP13(Iterative linear)Initialize motionInitialize structureFor each additional viewDetermine pose of cameraRefine and
23、extend structureRefine structure and motionRefining and extending structureComputerVision34Refining structure and motion use bundle adjustment211X,X,xminargmkniikkiDikPPAlso model radial distortion to avoid bias!ComputerVision35Hierarchical structure and motion recovery Compute 2-view Compute 3-view
24、 Stitch 3-view reconstructions Merge and refine reconstructionFTHPMComputerVision36Metric structure and motion Note that a fundamental problem of the uncalibrated approach is that it fails if a purely planar scene is observed(in one or more views)(solution possible based on model selection)use self-
25、calibration(see next class)ComputerVision37Dealing with dominant planesComputerVision38PPPgricHHgricComputerVision39Farmhouse 3D models(note:reconstruction much larger than camera field-of-view)ComputerVision40Application:video augmentationComputerVision41Next class:Camera calibration(and self-calibration)Reading:Chapter 2 and 3
