Stereo Vision

The Correspondence Problem

 Methods of Stereo Matching
Correlation-based
Attempt to establish a correspondence by matching image
intensities usually over a window of pixels in each image
− Disparity is found for all image points
− Dense disparity maps
 Feature-based
Attempt to establish a correspondence by matching a sparse
sets of image features – usually edges
− Disparity map is sparse
− Number of points is related to the number of image
features identified

2
Correlation Matching
• Fundamental algorithm

− For each pixel in one image (the reference image)

Find best match (best correlation) in the other
image

3
Correlation-Based Methods
• Cost function
− Simplest
f ( I1(j,k), I2(j-d,k) ) = | I1 (j,k) - I2 (j-d,k) |
absolute difference
− Generally a window of pixels around j,k will be considered

f ( I1(j,k), I2(j-d,k) ) = S
-w≤p≤+w
| I1 (j+p,k+q) - I2 (j+p-d,k+q) |
-w≤q≤+w
Sum of Absolute Differences (SAD)

− SAD takes random pixel noise into account well

4
Window-based Correlation Algorithms
• Compare a window of pixels in one image with a
window of pixels in the other
− Noise averages itself out over the window

d=D d=0

Reference Image Move an identical window

along the epipolar line
In the other image looking
for the best match

5
Correlation-Based Methods
• Basic Algorithm
− Assume rectified images in canonical configuration
− Epipolar lines aligned with scan lines
or
− Conjugate pairs lie in corresponding scan lines

for each row, k

for j = D to w
cmin = 
for d = 0 to D // check each possible disparity
c(d) = f ( I1(j,k), I2(j-d,k) )
if c(d) < cmin then
dbest = d
cmin = c(d)
disp( j,k ) = dbest // Save best d value

6
 Correlation-Based Methods
• normalized cross-correlation, c(d)  [0,1])

where I l and I r are the average pixel values in the left and right windows.

• An alternative similarity measure is the sum of squared differences (SSD):

7
Correlation-Based Methods

− How to choose the size of the window, W?

− too small a window

− may not capture enough image structure and
− may be too noise sensitive
many false matches
− too large a window
− makes matching less sensitive to noise (desired) but also
− decreases precision
(blurs disparity map)

8
Feature-Based Methods
• Main idea
− Look for a feature in an image that matches a feature in the other.
− Typical features used are:
− edge points
− line segments
− corners (junctions)

9
Feature-Based Methods
• A set of features is used for matching
− a line feature descriptor, for example, could contain:

− length, l
− orientation, 
− coordinates of the midpoint, m
− average intensity along the line, i

• Similarity measures are based on matching feature descriptors:

where w0, ..., w3 are weights

(determining the weights that yield the best matches is a nontrivial task).

10
Feature-Based Methods

11
Correlation vs. feature-based approaches
• Correlation methods
− Easier to implement
− Provide a dense disparity map (useful for reconstructing surfaces)
− Need textured images to work well (many false matches otherwise)
− Don’t work well when viewpoints are very different, due to change in
illumination direction

• Feature-based methods
− Suitable when good features can be extracted from the scene
− Faster than correlation-based methods
− Provide sparse disparity maps
− Suitable for applications like visual navigation
− Relatively insensitive to illumination changes

12
Assumptions and constraints
• Epipolar constraint
− Corresponding points lie on corresponding epipolar lines

− In the canonical configuration (|| optical axes, image planes)

− Epipolar lines are scan lines

• Uniqueness constraint
− Each pixel in the reference image corresponds to at most one
pixel in the other image

13
Assumptions and constraints
• Continuity constraint
− Surfaces are generally continuous
− Disparity differences between neighbouring pixels less than a
threshhold
− If xL1 matches xR1 and
neighbouring pixel, xL2 matches xR2
 || xL1 – xR1| - | xL2 – xR2|| < th

14
Constraints
• Ordering constraint
− Points on an epipolar line in
one image appear on the
corresponding epipolar line
in the other image in the
same order

Note the ordering of image

points (lower case) in the left
and right images

15
Assumptions
• Intensity
− Intensities of matching points are the same
− Gain and offset of both cameras identical
− No noise
Usually relaxed to
− …… differ by a very small amount

• Fronto-planar
− Surface segments
− Subtend the same angle or
− Occupy the same number of pixels
in both images

16
 matching in case of occlusion

Left Occluded Pixels

Left scanline

Right scanline

Right occluded Pixels

Three cases:
− Sequential – cost of match
− Left occluded – cost of no match
− Right occluded – cost of no match

17
18
“Shortest paths” for scan-line stereo
Left image I
Right image I

S left
Right
occlusion
q Coccl

occlusi
Left

on
t

Coccl Ccorr
S right
s p

Can be implemented with dynamic programming

Ohta & Kanade ’85, Cox et al. ‘96 Slide credit: Y. Boykov
Standard 3-move Dynamic Programming for Stereo

Left Occluded Pixels

Start Left scanline

Dynamic programming yields

the optimal path through
Right occluded Pixels

grid. This is the best set of

matches that satisfy the
Right scanline

ordering constraint

End
20
Stereo Matching with Dynamic Programming

Pseudo-code for calculating the optimal match

M(i,j) : predecessors
21
Stereo Matching with Dynamic Programming

Pseudo-code for
reconstructing the optimal
path

Occlusions –
Skip until next
match is found

22
Dynamic Programming - Result

Local errors may be propagated along a scan-line:

no inter scan-line consistency is enforced

23