Some books on linear algebraLast lectureTodayStructure from Motion by FactorizationProblem statementSFM under orthographic projectionSlide 7factorization (Tomasi & Kanade)FactorizationMetric constraintsResultsExtensions to factorization methodsPerspective Bundle adjustmentBundle AdjustmentLots of parameters: sparsityStructure from motion: limitationsTrack lifetimeSlide 18Slide 19Nonlinear lens distortionSlide 21Prior knowledge and scene constraintsSlide 23Applications of Structure from MotionJurassic parkPhotoSynthSlide 27Choosing the stereo baselineThe Effect of Baseline on Depth EstimationSlide 30Slide 31Multibaseline StereoMSR Image based Reality ProjectThe visibility problemVolumetric stereoDiscrete formulation: Voxel ColoringComplexity and computabilityIssuesSlide 39Reconstruction from Silhouettes (C = 2)Volume intersectionVoxel algorithm for volume intersectionProperties of Volume IntersectionSlide 44Voxel Coloring ApproachDepth Ordering: visit occluders first!Panoramic Depth OrderingSlide 48Panoramic LayeringSlide 50Compatible Camera ConfigurationsCalibrated Image AcquisitionVoxel Coloring Results (Video)Limitations of Depth OrderingSlide 55Space Carving AlgorithmWhich shape do you get?Slide 58Multi-Pass Plane SweepSlide 60Slide 61Slide 62Slide 63Slide 64Space Carving Results: African VioletSpace Carving Results: HandProperties of Space CarvingAlternatives to space carvingSlide 69Level sets vs. space carvingReferencesSlide 72Some books on linear algebraLinear Algebra, Serge Lang, 2004Finite Dimensional Vector Spaces, Paul R. Halmos, 1947Matrix Computation, Gene H. Golub, Charles F. Van Loan, 1996Linear Algebra and its Applications, Gilbert Strang, 1988Last lecture•2-Frame Structure from Motion•Multi-Frame Structure from MotionCC’T=C’-CRpp’0' Epp0' FxxToday•Continue on Multi-Frame Structure from Motion: •Multi-View StereoUnknownUnknowncameracameraviewpointsviewpointsStructure from Motion by FactorizationProblem statementSFM under orthographic projection2D image pointorthographicprojectionmatrix3D scenepointCameracenter)( tpΠq 12321313010001ΠFor example, fedcbaΠIn general, subject to 1001TΠΠ)( tpΠq nnSFM under orthographic projection2D image pointorthographicprojectionmatrix3D scenepointΠpq 12321313Cameracenter•Choose scene origin to be the centroid of the 3D points•Choose image origin to be the centroid of the 2D points0np0nqfactorization (Tomasi & Kanade)  n332n2 n21n21pppqqq projection of n features in one image: n332mn2m2121212222111211nmmnmmnnpppΠΠΠqqqqqqqqqprojection of n features in m imagesW measurement M motionS shapeKey Observation: ra nk(W) <= 3n33m2n2m'' SMW•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))(('' ASMASMW1n33m2n2m  SMWknownsolve forMetric constraints•Enforcing “Metric” Constraints•Compute A such that rows of M have these propertiesAAΜM''''m21m21Trick (not in original Tomasi/Kanade paper, but in followup work)•Constraints are linear in AAT : TiiTiiiiwhere AAGGAA TTT''''1001•Solve for G first by writing equations for every i in M•Then G = AAT by SVDResultsExtensions to factorization methods•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 Bundle adjustmentRichard Szeliski CSE 576 (Spring 2005): Computer Vision14Bundle Adjustment•What makes this non-linear minimization hard?•many more parameters: potentially slow•poorer conditioning (high correlation)•potentially lots of outliers• How to initialize?• 2 or 3 views at a time, add more iteratively [Hartley 00]Richard Szeliski CSE 576 (Spring 2005): Computer Vision15Lots of parameters: sparsity•Only a few entries in Jacobian are non-zeroRichard Szeliski CSE 576 (Spring 2005): Computer Vision16Structure from motion: limitations•Very difficult to reliably estimate metricstructure and motion unless:•large (x or y) rotation or•large field of view and depth variation•Camera calibration important for Euclidean reconstructions•Need good feature tracker•Lens distortionTrack lifetimeevery 50th frame of a 800-frame sequenceTrack lifetimelifetime of 3192 tracks from the previous sequenceTrack lifetimetrack length histogramNonlinear lens distortionNonlinear lens distortioneffect of lens distortionPrior knowledge and scene constraintsadd a constraint that several lines are parallelPrior knowledge and scene constraintsadd a constraint that it is a turntable sequenceApplications of Structure from MotionJurassic parkPhotoSynthhttp://labs.live.com/photosynth/Multiview Stereowidth of a pixelChoosing the stereo baselineWhat’s the optimal baseline?•Too small: large depth error•Too large: difficult search problemLarge BaselineLarge BaselineSmall BaselineSmall Baselineall of thesepoints projectto the same pair of pixelsThe Effect of Baseline on Depth Estimation1/zwidth of a pixelwidth of a pixel1/zpixel matching scoreMultibaseline StereoBasic Approach•Choose a reference view•Use your favorite stereo algorithm BUT>replace two-view SSD with SSD over all baselinesLimitations•Must choose a reference view (bad)•Visibility!MSR Image based Reality Projecthttp://research.microsoft.com/~larryz/videoviewinterpolation.htm…|The visibility problemInverse Visibilityknown imagesUnknown SceneUnknown SceneWhich points are visible in which images?Known SceneKnown SceneForward Visibilityknown sceneVolumetric stereoScene VolumeScene VolumeVVInput ImagesInput Images(Calibrated)(Calibrated)Goal: Goal: Determine occupancy, “color” of points in VDetermine occupancy, “color” of points in VDiscrete formulation: Voxel ColoringDiscretized Discretized Scene VolumeScene VolumeInput ImagesInput