CSE 417 Homework 4, Winter 2011

1. (15 points). In Kleinberg and Tardos, Chapter 6, Exercise 4. (pp.315-316) on finding optimal plans for a consulting business.
    
   
2. (20 points). The Longest Common Subsequence (LCS) of two strings: S_a = s_a1 s_a2 ... s_am and S_b = s_b1 s_b2 ... s_bn is a string S_c = LCS(S_a, S_b) = s_c1 s_c2 ... s_cq such that S_c is a subsequence of S_a, and S_c is a subsequence of S_b, and for any other common subsequence S_c' of S_a and S_b, length(S_c) >= length(S_c').

   It is possible to compute the length of an LCS using Dynamic Programming.

   (a) give a recurrence equation for computing M(Prefix(S_a, i), Prefix(S_b, j)) which is defined as the length of a longest common subsequence of Prefix(S_a, i) and Prefix(S_b, j). Here Prefix(S, k) is defined as the string consisting of the first k characters of S.

   (b) Draw the 2D array of values for M(Prefix(S_a, i), Prefix(S_b, j)) for the following pair of strings.

   Sa = W H I S P E R S
   Sb = W I S H E S
   

   (c) Draw a backtrace on the array that shows how to recover LCS(S_a, S_b) from the M array. Circle the entries of the array M that correspond to one particular LCS.
    
   
3. (15 points). In this exercise, you'll apply dynamic programming to the problem of stereo computer vision.

   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 example, 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 example:

   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 p_i is matched with pixel p_j, the cost for this pair is (p_i-p_j)². If pixel p_i is considered "occluded" (not matched), the cost is C_occl, a constant that is set before the algorithm runs. Let us use C_occl = 10 for our example.

   (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).
    
   

4. (20 points). Implement the LCS method described in Problem 2 above. (10). Your program should print out the M array to the screen after it has been computed. (5) Then it should compute and output the LCS itself. (5)
    
   
5. (30 points). Implement a stereo correspondence algorithm that uses Dynamic Programming to find the correspondences between the pixels in a given Left scanline and a given Right scanline. Your program should compute an M array and print it out to the screen after it has been computed (15). Then it should output an array of displacement values, with one value for each element in the left scanline (15).

   
    
   

6. (Optional, and for 10 points of extra credit, and due separately on Monday, February 14 at 11:45 PM) Extend your solution to Problem 5 so that it reads in a pair of images in PNG format and computes a 2D depth map from them. The images will be in color, and you should use the sum of squared differences between pixel red, green, and blue components as the matching cost. You may assume that the images have been rectified, so that scan lines correspond to epipolar lines. Sample data is available here: teddy-left.png; teddy-right.png. As a rough check on your disparity map, here is a thumbnail image that shows a miniature version of what you should come up with: teddy-depth-thumb.png.

   Turn in your code and its output (which should be a monochrome .PNG image of the same dimensions as the input images). Please adjust the range of disparity values in the output image so that the depths are readily visible without further processing. You can use the linked thumbnail image as a rough guide to how light and dark your image should be. There will be a separate Drop-box assignment area for this problem.