CS 787: Assignment 4, Stereo Vision:
Block Matching and Dynamic Programming
Due: 12:00noon, Fri. Mar. 30, 2007.
In this assignment you will implement and test some simple stereo algorithms discussed
in class.
In each case you will take two images Il and Ir (a left and a right image) and compute
the horizontal disparity (ie., shift) of pixels along each scanline. This is the so-called baseline
stereo case, where the images are taken with a forward-facing camera, and the translation
between cameras is along the horizontal axis.
Your system will output a disparity image, where each pixel encodes the shift between
the left and right images. In general one needs to know the interoccular distance, T, and
the nodal distance, f, to reconstruct depth, Z, from disparity (ie., d = fT
Z
). Here we will
just focus on the computation of the disparity d.
You will be given two pairs of images. The first pair is a synthetic scene with images
synth1.tif and synth2.tif. The second pair is a real scene with images pm1.tif and
pm2.tif.
1 Block Matching
Write a Matlab program to compute the disparity (horizontal shift) of each scanline. In
particular, your program should find the displacement d that minimizes the mean-squared
error between an image patch at (y, x) in the left image (Il) and a corresponding patch at
(y, x + d) in the right image (Ir):
∑
−W≤j≤W
∑
−W≤i≤W
(Il(y + j, x + i) − Ir(y + j, x + i + d))2
W is the half window width. For this assignment we will use W = 3, which gives a 7-by-7
window. The disparity, d, is restricted to be in range −D ≤ d ≤ D. For this assignment we
will use D = 8.
Note: The summation above can be efficiently implemented in Matlab using matrix
functions. Suppose matrices A and B are patches from the left and right images, respectively.
We can compute the mean squared error as sum(sum((A-B).^2)).
1
1.1 Plain block matching
Perform the above block matching for both image pairs. To display the disparity, plot a
greyscale image of the same size as the input images Il and Ir. Each pixel of the output
image denotes a disparity. Print out the disparity images to show the block matching results
both the synthetic and real image pairs.
Note: You can use the Matlab function imshow(D,[-8,8]) to display a disparity matrix
D as a greyscale image. Dark areas depict negative disparities, while bright areas depict
positive disparities. Zero disparities will show up as gray areas in the image.
1.2 Censoring: removing areas of low texture
As with motion estimation, areas of low texture are hard to match reliably between images.
In stereo, since we are attempting to determine the horizontal motion between frames we
want to remove areas where the horizontal texture is low.
The average horizontal variation of an image patch centered at (y, x) is given by:
σ2
h =
1
4W2
∑
−W≤j≤W
∑
−W≤i≤W
(I(y + j, x + i) −
¯
I(y + j, x))2
where y denotes a particular scanline of the image and
¯
I(y, x) =
1
2W
∑
−W≤i≤W
I(y, x + i)
denotes the mean value of the jth scanline of the patch centered at (y, x).
Use the above formula to censor image positions in the left image, Il, which have low
horizontal variation. Perform exactly the same matching as the previous section, except that
when the horizontal variation in Il is low, output a value of -8 to the disparity image instead
of computing the disparity. Black areas of the resulting disparity maps will indicate places
where there is no disparity information.
You may experiment with σ, but a good starting value is σ = 2.
1.3 Consistency checking
Often a part of the scene may be visible in only one of the images. This will result in random
or spurious matches, since a correct match does not exist.
2
Let dl(x) be the disparity estimate for a particular scanline (row) in the left image. (This
was obtained above by matching every patch along the left scanline with a patch in the
corresponding row of Ir.) Similarly let dr(x) be the disparity estimate for matching the right
image to the left image.
For a given pixel at xl in the left scanline the predicted position in right scanline is
xr = xl + dl(xl) (ie., the position in the left scanline plus the disparity). Projecting this
position back to the left scanline, we have xl = xr + dr(xr). A match between the left and
right scanlines is consistent iff xl = xl.
Use the above consistency check to remove places where the match is inconsistent. At
the places where the match is inconsistent, set the disparity value to -8.
Note: Implementing the consistency check requires that you do the block matching in
both directions (to compute dl(x) and dr(x))!
Output the result for both the synthetic and real image pairs. You may use the block
matcher from the plain block matching or the censored block matcher (your choice). However,
please specify which one you used.
2 Dynamic programming
Another way to match scanlines is by dynamic programming.
Consider two scanlines Il(i) and Ir(j), 1 ≤ i, j ≤ N, where N is the number of pixels in
each line (the process will be repeated for each row of the image). Pixels in each scanline
may be matched, or skipped (considered to be occluded in either the left or right image).
Let dij be the cost associated with matching pixel Il(i) with pixel Ir(j). Here we consider
a squared error measure between pixels given by:
dij =
(Il(i) − Ir(j))2
σ2
where σ is some measure of pixel noise. The cost of skipping a pixel (in either scanline) is
given by a constant c0. For the experiments here we will use σ = 2 and c0 = 1 (although
you may experiment if you wish).
Given these costs, we can compute the optimal (minimal cost) alignment of two scalines
recursively as follows:
1. D(1,1) = d11,
3
2. D(i, j) = min(D(i − 1,j − 1) + dij,D(i − 1,j) + c0,D(i, j − 1) + c0),
The intermediate values are stored in an N-by-N matrix, D. The total cost of matching two
scanlines is D(N,N). Note that this assumes the lines are matched at both ends (and hence
have zero disparity there). This is a reasonable approximation provided the images are large
relative to the disparity shift.
Given D we find the optimal alignment by backtracking. In particular, starting at (i, j) =
(N,N), we choose the minimum value of D from {(i−1,j −1),(i−1,j),(i, j −1)}. Selecting
(i − 1,j) corresponds to skipping a pixel in Il (a unit increase in disparity), while selecting
(i, j − 1) corresponds to skipping a pixel in Ir (a unit decrease in disparity). Selecting
(i − 1,j − 1) matches pixels (i, j), and therefore leaves disparity unchanged. Beginning with
zero disparity, we can work backwards from (N,N), tallying the disparity until we reach
(1,1).
2.1 Individual scanline matching
Implement the above method of scanline matching for both the synthetic and real image
pairs.
A good way to interpret your solution is to plot the alignment found for single scan line(s).
To display the alignment plot a graph of Il (horizontal) vs Ir (vertical). Begin at D(N,N)
and work backwards to find the best path. If a pixel in Il is skipped, draw a horizontal line.
If a pixel in Ir is skipped, draw a vertical line. Otherwise, the pixels are matched, and you
draw a diagonal line. The plot should end at (0,0).
Show the scanline matching for line 50 in both the synthetic and real pairs.
Optional: You can also show the values of Il(x) and Ir(x) that are matched by the
dynamic programming algorithm. Starting at D(N,N), the path will either skip a pixel in
Il, skip a pixel in Ir, or match pixels in Il and Ir. You will only plot pixel values when the
pixels are matched. Otherwise the graph will be empty. The graph should be the same size
as the scanline, just with missing values where no match was performed.
2.2 Disparity computation
Compute the disparity maps for both image pairs using the method described above. Output
the disparity as a greyscale image.
4
Note: With dynamic programming (at least this simple implementation of the algo-
rithm), the range of disparities is not limited. Before plotting, it is best to check the min-
imum and maximum value. (min(min(D)) and max(max(D)) will give the minimum and
maximum values of a matrix in Matlab.) If necessary, use these as parameters to the imshow
command to scale your images appropriately.
5
