The full stereo computer vision problem consists of taking two images of a scene (a left-eye image and a right-eye image, actually taken with a camera or two cameras), and computing a depth map from them, using the slight differences between the images.

We will focus on a small but key part of this problem: the problem of taking a pair of scanlines (one from each image) and determining the correspondence between pixels. For ex, if the scene includes a human face, there should be a pixel at the lower-left corner of the person's nose in each of the images, and assuming that the images are aligned properly, the two pixels should occur in corresponding scanlines (at the same height in the images). The two pixels will probably be in slightly different horizontal positions due to the difference in the left and right views. The pixels can be expected to have approximately the same brightness value. We want our method to put these two pixels into correspondence (along with many other corresponding pairs).

Our procedure should accept as input two lists of numbers. The first will represent the pixel values along the left scanline, and the second will be for the right scanline. It should compute a minimum-cost correspondence, which for each pixel of the scanlines gives it either a displacement (to its corresponding pixel in the other scanline) or marks it as "occluded" which means it has no corresponding pixel in the other scanline.

Here is an ex:

Left scanline L: [7, 6, 0, 12, 12, 4]
Right scanline R: [7, 0, 12, 13, 11, 4, 3]
With Dynamic Programming, we build an m by n array to hold the M values of the subproblems. Each subproblem is of the form S(i,j) = minimum cost of a correspondence between the first i pixels of L and the first j pixels of R.
We assume that the cost of a correspondence is based on the following: if pixel pi is matched with pixel pj, the cost for this pair is (pi-pj)2. If pixel pi is considered "occluded" (not matched), the cost is Coccl, a constant that is set before the algorithm runs. Let us use Coccl = 10 for our ex.

(a) Draw the M array for the sample problem (with the two scanline sequences given above), filling in the correct values at least on the main diagonal and three diagonals on each side of it. (5 points)

(b) Draw a backtrace in M that shows an optimal set of corresponding pixels. (5 points).

(c) Determine the sequence of disparity values that goes with the left scanline sequence. (5 points). [Late clarifications: Since the scanlines here have different lengths, assume that we define the cyclopean to follow the main diagonal of the matrix from the (0,0) entry to the (6,6) entry, not the (6,7) or (7,6) entry. To determine the disparity at row i of the table, find the leftmost table cell in row i through which your chosen optimal path passes, and then subtract from i the value of j there. (Disparity values can be either negative or positive or zero.) You should give a sequence of 6 disparity values, starting with that for row 0 and ending with that for row 6.]