Stereo matching• “Stereo matching” is the correspondence problem– For a point in Image #1, where is the corresponding point inImage #2?C1C2??C1C2Epipolar lines• Image rectification makes the correspondence problemeasier– And reduces computation timeStereo matching• “Stereo matching” is the correspondence problem– For a point in Image #1, where is the corresponding point in|Image #2???C1Rectified C2Epipolar lines• Image rectification makes the correspondence problemeasier– And reduces computation timeStereo matchingLeft RightuuRectified imagesMatching along epipolar lineMatching valueThe best match estimates the “disparity”• In this case, horizontal disparity only (since images were rectified)uiArea matching• Correlation– Correlate left image patch along the epipolar line in the right image– Best match = highest value Normalized correlation would be better!• Sum of Squared Differences (SSD)– Better than correlation, faster than normalized correlation= v)(u,aroundarea2)),(),((),( jiIjiIvuSSDrightleft– Best match = lowest valueStereo matching algorithms• There are many!– Edge based– Coarse-to-fine– Adaptive windows– Dynamic programming– Markov random fields,graph cuts– Multi-baseline– Etc.• Pitfalls– Specularities– Occlusions (missing data)– Sensor noise– Calibration error– Matching ambiguity(constant or low-constrastregions)– Etc.Basic Stereo Configuration: rectified imagesxrxlZXbfXb+2Xb2xfXbZl=+2xfXbZr=2xxfbZZbfx xlrlr==()ZZ2bDisparityStereo disparity• “Stereo disparity” is the difference in position betweencorrespondence points in two images– Disparity is inversely proportional to scene depth(u0, v0)(u0, v0)Disparity: (du0, dv0) = (u0 - u0, v0 - v0) = (0, 0)Disparity is a vector!Stereo disparity(u1, v1)(u1, v1)Disparity: (du1, dv1) = (u1 - u1, v1 - v1)Stereo disparityDisparity: (du2, dv2) = (u2 - u2, v2 - v2)(u2, v2)(u2, v2)Stereo disparity(u, v)Disparities: (dui, dvi) = (ui - ui, vi - vi)(u, v)Depth = f (disparity, geometry)Output of stereo matching• Dense stereo– Disparity at each point• Sparse stereo– Disparity at each feature pointDepth = f (disparity, geometry)Random dot stereograms• Correspondence is not always required in order to seedepth• Existence proof: random-dot stereogramsRDS exampleHow is this possible with completely random correspondence?Left Right Depth imageMarr -Poggiocooperative stereoalgorithmSingle image stereograms: should try this!Red/Green stereo displayFrom Mars PathfinderMultiple camera stereo• Using multiple camera in stereo has advantages anddisadvantages• Some disadvantages– Computationally more expensive– More correspondence matching issues– More hardware ($)• Some advantages– Extra view(s) reduces ambiguity in matching– Wider range of view, fewer “holes”– Better noise properties– Increased depth precisionThree Camera Stereo• A powerful way of eliminate spurious matches– Hypothesize matches between A & B– Matches between A & C on green epipolar line– Matches between B & C on red epipolar line– There better be something at the intersection (no search needed!)ABCThe Stanford Multi-Camera Array128 CMOS cameras, 2” baselineCMU multi-camera stereo51 video cameras mounted on a 5-meter diameter geodesic domeStereo: Summary• Multiview geometry– Epipolar geometry• Correspondence problem• Essential Matrix and Fundamental Matrix• Random dot