Multiple View GeometryOur GoalThe Plenoptic FunctionStereo ReconstructionWhy do we have two eyes?1. Two is better than one2. Depth from Convergence3. Depth from binocular disparitySlide 9StereoSlide 11Stereo correspondenceStereo image rectificationSlide 14Stereo RectificationYour basic stereo algorithmWindow sizeStereo resultsResults with window searchBetter methods exist...Depth from disparityStereo reconstruction pipelineStereo matchingActive stereo with structured lightSlide 25Laser scanningSlide 27Real-time stereoVolumetric StereoDiscrete Formulation: Voxel ColoringComplexity and ComputabilityIssuesSlide 33Reconstruction from SilhouettesVolume IntersectionVoxel Algorithm for Volume IntersectionProperties of Volume IntersectionSlide 38Voxel Coloring ApproachThe Global Visibility ProblemDepth Ordering: visit occluders first!Calibrated Image AcquisitionVoxel Coloring Results (Video)Limitations of Depth OrderingSlide 45Space Carving AlgorithmConvergenceStructure from MotionSlide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Façade (Debevec et al) inputsFaçade (Debevec et al)Multiple View Geometry15-463: Computational PhotographyAlexei Efros, CMU, Fall 2007© Martin Quinn …with a lot of slides stolen from Steve Seitz and Jianbo ShiOur GoalThe Plenoptic FunctionP(,t,VX,VY,VZ)How can we compress this into something manageable?Stereo ReconstructionThe Stereo Problem•Shape from two (or more) images•Biological motivationknownknowncameracameraviewpointsviewpointsWhy do we have two eyes?Cyclope vs. Odysseus1. Two is better than one2. Depth from ConvergenceHuman performance: up to 6-8 feet3. Depth from binocular disparitySign and magnitude of disparityP: converging pointC: object nearer projects to the outside of the P, disparity = +F: object farther projects to the inside of the P, disparity = -Stereoscene pointscene pointoptical centeroptical centerimage planeimage planeStereoBasic Principle: Triangulation•Gives reconstruction as intersection of two rays•Requires –calibration–point correspondenceStereo correspondenceDetermine Pixel Correspondence•Pairs of points that correspond to same scene pointEpipolar Constraint•Reduces correspondence problem to 1D search along conjugate epipolar linesepipolar planeepipolar lineepipolar lineepipolar lineepipolar lineStereo image rectificationStereo image rectificationImage Reprojection•reproject image planes onto common plane parallel to line between optical centers•a homography (3x3 transform)applied to both input images•pixel motion is horizontal after this transformation•C. Loop and Z. Zhang. Computing Rectifying Homographies for Stereo Vision. IEEE Conf. Computer Vision and Pattern Recognition, 1999.Stereo RectificationYour basic stereo algorithmFor each epipolar lineFor each pixel in the left image•compare with every pixel on same epipolar line in right image•pick pixel with minimum match costImprovement: match windows•This should look familar...•Can use Lukas-Kanade or discrete search (latter more common)Window size•Smaller window+ – •Larger window+ – W = 3 W = 20Effect of window sizeStereo resultsGround truthScene•Data from University of Tsukuba•Similar results on other images without ground truthResults with window searchWindow-based matching(best window size)Ground truthBetter methods exist...State of the art methodBoykov et al., Fast Approximate Energy Minimization via Graph Cuts, International Conference on Computer Vision, September 1999.Ground truthDepth from disparityfx x’baselinezC C’Xf input image (1 of 2) [Szeliski & Kang ‘95] depth map 3D rendering•Camera calibration errors•Poor image resolution•Occlusions•Violations of brightness constancy (specular reflections)•Large motions•Low-contrast image regionsStereo reconstruction pipelineSteps•Calibrate cameras•Rectify images•Compute disparity•Estimate depthWhat will cause errors?Stereo matchingNeed texture for matchingJulesz-style Random Dot StereogramActive stereo with structured lightProject “structured” light patterns onto the object•simplifies the correspondence problemcamera 2camera 1projectorcamera 1projectorLi Zhang’s one-shot stereoActive stereo with structured lightLaser scanningOptical triangulation•Project a single stripe of laser light•Scan it across the surface of the object•This is a very precise version of structured light scanningDigital Michelangelo Projecthttp://graphics.stanford.edu/projects/mich/Portable 3D laser scanner (this one by Minolta)Real-time stereoUsed for robot navigation (and other tasks)•Several software-based real-time stereo techniques have been developed (most based on simple discrete search)Nomad robot searches for meteorites in Antarticahttp://www.frc.ri.cmu.edu/projects/meteorobot/index.htmlVolumetric StereoScene VolumeScene VolumeVVInput ImagesInput Images(Calibrated)(Calibrated)Goal: Goal: Determine transparency, radiance of points in VDetermine transparency, radiance of points in VDiscrete Formulation: Voxel ColoringDiscretized Discretized Scene VolumeScene VolumeInput ImagesInput Images(Calibrated)(Calibrated)Goal: Assign RGBA values to voxels in Vphoto-consistent with imagesComplexity and ComputabilityDiscretized Discretized Scene VolumeScene VolumeN voxelsN voxelsC colorsC colors33All Scenes (CN3)Photo-ConsistentScenesTrueSceneIssuesTheoretical Questions•Identify class of all photo-consistent scenesPractical Questions•How do we compute photo-consistent models?1. C=2 (silhouettes)•Volume intersection [Martin 81, Szeliski 93]2. C unconstrained, viewpoint constraints•Voxel coloring algorithm [Seitz & Dyer 97]3. General Case•Space carving [Kutulakos & Seitz 98]Voxel Coloring SolutionsReconstruction from SilhouettesBinary ImagesBinary ImagesApproach: •Backproject each silhouette•Intersect backprojected volumesVolume IntersectionReconstruction Contains the True Scene•But is generally not the same •In the limit get visual hull >Complement of all lines that don’t intersect SVoxel Algorithm for Volume IntersectionColor voxel black if on silhouette in every image•O(MN3), for M images, N3 voxels•Don’t have to search 2N3 possible scenes!Properties of Volume IntersectionPros•Easy to implement, fast•Accelerated via octrees [Szeliski 1993]Cons•No concavities•Reconstruction is not photo-consistent•Requires identification of silhouettes1. C=2 (silhouettes)•Volume intersection
View Full Document
Unlocking...