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 RightuuRectified imagesMatching along epipolar lineMatching valueThe best match estimates the “disparity”• In this case, horizontal disparity only (since images were rectified)uiArea 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+2Xb2xfXbZl=+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)(u0, v0)Disparity: (du0, dv0) = (u0 - u0, v0 - v0) = (0, 0)Disparity is a vector!Stereo disparity(u1, v1)(u1, v1)Disparity: (du1, dv1) = (u1 - u1, v1 - v1)Stereo disparityDisparity: (du2, dv2) = (u2 - u2, v2 - v2)(u2, v2)(u2, v2)Stereo disparity(u, v)Disparities: (dui, dvi) = (ui - ui, vi - vi)(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
View Full Document