1Binocular Stereo• Take 2 images from different knownviewpoints ⇒ 1stcalibrate• Identify corresponding points between 2 images• Derive the 2 lines on which world point lies• Intersect 2 linesPublic Library, Stereoscopic Looking Room, Chicago, by Phillips, 192323Stereo• Basic Principle: Triangulation– Gives reconstruction as intersection of two rays– Requires • calibration• point correspondence4Depth from Disparityfu u’baselinezCC’Xfinput image (1 of 2)[Szeliski & Kang ‘95]depth map 3D rendering5Multi-View Geometry• Different views of a scene are not unrelated• Several relationships exist between two, three and more cameras• Question: Given an image point in one image, does this restrict the position of the corresponding image point in another image?6Epipolar Geometry: Formalism• Depth can be reconstructed based on corresponding points (disparity)• Finding corresponding points is hard & computationally expensive• Epipolar geometry helps to significantly reduce search from 2-D to 1-D lineEpipolar Geometry: DemoJava Applethttp://www-sop.inria.fr/robotvis/personnel/sbougnou/Meta3DViewer/EpipolarGeo.htmlSylvain Bougnoux, INRIA Sophia Antipolis7• Scene point P projects to image point pl= (xl, yl, fl) in left image and point pr= (xr, yr, fr) in right image• Epipolar plane contains P, Ol, Or, pland pr–called co-planarity constraint• Given point plin left image, its corresponding point in right image is on line defined by intersection of epipolar plane defined by pl, Ol, Orand image Ir– called epipolar line of pl• In other words, pland Oldefine a ray where Pmay lie; projection of this ray into Iris the epipolar lineMarc Pollefeys, University of Leuven, Belgium, Siggraph2001 Course8Epipolar Line Geometry• Epipolar Constraint: The correct match for a point plis constrained to a 1D search along the epipolar line in Ir• All epipolar planes defined by all points in Ilcontain the line OlOr⇒ All epipolar lines in Irintersect at a point, er, called the epipole• Left and right epipoles, el and er, defined by the intersection of line OlOrwith the left and right images Iland Ir, respectively910Epipolar GeometryMarc Pollefeys, University of Leuven, Belgium, Siggraph2001 CourseEpipolar Geometry: Rectification• [Trucco 157-160]• Motivation: Simplify search for corresponding points along scan lines (avoids interpolation and simplify sampling)• Technique: Image planes parallel -> pairs of conjugate epipolar lines become collinear and parallel to image axis.11Stereo Image Rectification• Image 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, Computer Vision and Pattern Recognition Conf., 1999RectificationMarc Pollefeys, University of Leuven, Belgium, Siggraph2001 Course12Rectification ExamplebeforeafterRectification ProcedureGiven: Intrinsic and extrinsic parameters for 2 cameras1. Rotate left camera so that the epipole goes to infinity along the horizontal axis⇒ left image parallel to baseline2. Rotate right camera using same transformation3. Rotate right camera by R, the transformation of the right camera frame with respect to the left camera4. Adjust scale in both camerasImplement as backward transformations, and resample using bilinear interpolation13• Conjugate Epipolar Line: A pair of epipolar lines in Iland Irdefined by P, Oland Or• Conjugate (i.e., corresponding) Pair: A pair of matching image points from Iland Irthat are projections of a single scene point Definitions1415161718192021Basic 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 windows22stereoleft image right imagedisparitiesStereo Correspondencedisparity = x1-x2 is inversely proportional to depth3D scene structure recovery(x1,y)(x2,y)23Stereo Matching• Features vs. pixels?– Do we extract features prior to matching?Julesz-style Random Dot Stereogram24Difficulties in Stereo Correspondence2) Low texture:??Perfect case:never happens!left image right image1) Image noise:25Local Approach• Look at one image patch at at time • Solve many small problems independently• Faster, less accurateGlobal Approach• Look at the whole image • Solve one large problem• Slower, more accurateHow Difficult is Correspondence?• local works for high texture• enough texture in a patch to disambiguatehigh texture• global works up to medium texture• propagates estimates from textured to untextured regionsmedium texturelow texture• salient regions work up to low texture• propagation fails; some regions are inherently ambiguous, match only unambiguous regions d i f f i c u l t y26Local Approach [Levine’73]left imageright imagep1C12C23C3+++2222=Common Cpd= i which gives bestiC(SSD)Fixed Window Size Problemstrue disparitiesfixed small window fixed large windowleft imageneed different window shapes27Window Size– Smaller window+–– Larger window+–W = 3 W = 20Better results with adaptive window• T. Kanade and M. Okutomi, A Stereo Matching Algorithm with an Adaptive Window: Theory and Experiment, Proc. Int. Conf. Robotics and Automation, 1991• D. Scharstein and R. Szeliski. Stereo matching with nonlinear diffusion, Int. J. Computer Vision, 28(2):155-174, 1998• Effect of window sizeSample Compact Windows [Veksler 2001]28Comparison to Fixed WindowVeksler’s compact windows:16% errorstrue disparitiesfixed small window: 33% errors fixed large window: 30% errors1.670.531.692.791.001.791.52Venus0.331.613.36Veksler’s var. windows0.260.618.08Multiw. Cut 2.390.421.86Graph cuts1.790.361.27GC+occl.0.840.981.15Belief prop0.311.301.94Graph cuts0.370.341.58LayeredMapSawtoothTsukubaAlgorithmResults (% Errors) all global29Constraints2) most nearby pixels should have similar disparitydisparity continuous in most placesexcept a few places: disparity discontinuity1) corresponding pixels should be close in colorpqAdditional geometric constraints for correspondence• Ordering of points: Continuous surface: same order in both images.• Is that always true?A B C A B CA B CA B C30Forbidden Zone of MForbidden Zonem1m2MNn1n2Practical applications: – Object bulges out: