4/15/2021
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
STEREO MATCHING
‘-
2
1
4/15/2021
Correspondence problem
‘-
Multiple match hypotheses satisfy epipolar constraint, but which is correct?
Figure from Gee & Cipolla 1999
Correspondence problem
• Beyond the hard constraint of epipolar geometry, there are “soft” constraints to help identify corresponding points
• Similarity
• Uniqueness ‘- • Ordering
• Disparity gradient
• To find matches in the image pair, we will assume • Most scene points visible from both views
• Image regions for the matches are similar in appearance
2
4/15/2021
Dense correspondence search
‘-
• compare with every pixel / window on same epipolar line in right image
• pick position with minimum match cost (e.g., SSD, normalized correlation)
For each epipolar line
For each pixel / window in the left image
Adapted from Li Zhang
Correspondence search with similarity constraint
Left
Right
scanline
Matching cost
‘-
• Slide a window along the right scanline and compare contents of that window with the reference window in the left image
• Matching cost: SSD or normalized correlation
disparity
3
4/15/2021
Left
Right
scanline
‘-
SSD
Left
Right
scanline
‘-
Norm. corr
4
4/15/2021
‘-
Intensity profiles
Source: Andrew Zisserman
‘-
Neighborhoods of corresponding points are similar in intensity patterns.
Source: Andrew Zisserman
5
4/15/2021
Correlation-based window matching
‘-
‘-
6
4/15/2021
‘-
Correlation-based window matching
‘-
7
4/15/2021
Correlation-based window matching
‘-
???
Textureless regions are non‐distinct; high ambiguity for matches.
Effect of window size
‘-
Source: Andrew Zisserman
8
4/15/2021
Effect of window size
Want window large enough to have sufficient intensity variation, yet small enough to contain only pixels with about the same disparity.
Figures from Li Zhang
‘-
W = 3
W = 20
Correspondence problem
• Beyond the hard constraint of epipolar geometry, there are “soft” constraints to help identify corresponding points
• Similarity
• Disparity gradient – depth doesn’t change too quickly.
‘-
• Uniqueness • Ordering
9
4/15/2021
Uniqueness constraint
• Up to one match in right image for every point in left
image
‘-
Figure from Gee & Cipolla 1999
Problem: Occlusion
• Uniqueness says “up to match” per pixel
• When is there no match?
‘-
Occluded pixels
10
4/15/2021
Disparity gradient constraint
• Assume piecewise continuous surface, so want disparity
estimates to be locally smooth
‘-
Figure from Gee & Cipolla 1999
Ordering constraint
• Points on same surface (opaque object) will be in same
order in both views
‘-
Figure from Gee & Cipolla 1999
11
4/15/2021
Ordering constraint
• Won’t always hold, e.g. consider transparent object, or an occluding surface
‘-
Figures from Forsyth & Ponce
Left image Right image
‘-
12
4/15/2021
Results with window search
‘-
Window-based matching (best window size)
Ground truth
Better solutions
• Beyond individual correspondences to estimate
disparities:
• Optimize correspondence assignments jointly
• Scanline at a time (DP) • Full 2D grid (graph cuts)
‘-
13
4/15/2021
Stereo as energy minimization
‘-
• What defines a good stereo correspondence? 1. Matchquality
‐ Want each pixel to find a good match in the other image 2. Smoothness
‐ If two pixels are adjacent, they should (usually) move about the same amount
Stereo matching as energy minimization
I1
D
‘-
I2
W2(i+D(i ))
W1(i )
D(i )
E Edata (I1, I2 , D) Esmooth (D) •Energy functions of this form can be minimized
Y. Boykov, O. Veksler, and R. Zabih, Fast Approximate Energy Minimization using graph cuts
Esmooth D(i)D(j) neighbors i, j
E
data
W(i)W (iD(i))2 12
i
via Graph Cuts, PAMI 2001
Source: Steve Seitz
14
4/15/2021
Better results…
Graph cut method
Boykov et al., Fast Approximate Energy Minimization via Graph Cuts,
International Conference on Computer Vision, September 1999.
‘-
Ground truth
For the latest and greatest: http://www.middlebury.edu/stereo/
Challenges
•Low-contrast ; textureless image regions
• Occlusions
•Violations of brightness constancy (e.g.,
specular reflections)
•Really large baselines (foreshortening and
appearance change)
Exercise
‘-
•Camera calibration errors Pause Video and be able to explain these challenges
15
4/15/2021
Active stereo with structured light
‘-
•Project “structured” light patterns onto the objec camera
• Simplifies the correspondence problem • Allows us to use only one camera
L. Zhang, B. Curless, and S. M. Seitz. Rapid Shape Acquisition Using Color Structured Light and Multi-pass Dynamic Programming. 3DPVT 2002
projector
Kinect: Structured infrared light
‘-
Kinect in infrared
16
4/15/2021
iPhone X
• IR Emitter
• 30,000 points
• 2D IR snapshot
‘-
Next Lecture
• Motion and Optical Flow
‘-
17