Starting from:
$29.99
Dynamic Programming_Homework 4 Solution
Dynamic Programming
Task 1 (20 points): Implement the Longest Common Subsequence (LCS) Given two sequences, X ={x1; ... ; xm} and Y ={y1; ... ; yn}. Find a subsequence common to both whose length is longest. A subsequence doesn‘t have to be consecutive, but it has to be in order. The LCS problem has 2 versions: • The Simple version, requesting only to find out the length of the longest common subsequence. • The Complete version, requesting to find out the sequence itself. For this assignment, you need to implement the Complete version using the Dynamic Programming approach. X = {x1, … xm} Y = {y1, …,yn} Xi = the prefix subsequence {x1, … xi} Yi = the prefix subsequence {y1, … yi} Z ={z1, … zk} is the LCS of X and Y . LCS(i,j) = LCS of Xi and Yj We can recursively define the LCS as: Use the recursive definition to set up your memorization table and compute the size of the longest subsequence and the characters that are part of it. LCS(i,j)= 0 if i=0 or j=0, LCS(i−1 ,j−1)+1 if i,j0 and xi =yj, max(LCS(i−1 ,j),LCS(i,j−1)) if i,j0 and xi ≠yj. # $ % % & % % H O R S E B A C K S N O W F L A K E LCS = OAK
Task 2 (40 points): Calculate stereo disparity using the DP (as outlined below) Here, you will implement a stereo algorithm that uses dynamic programming. This algorithm enforces the ordering constraint, the uniqueness constraint, and matches individual pixels based on a cost function. Every pixel in one image can either match one pixel in another image, or be marked as occluded. Note: this algorithm assumes the image intensities in the left and right image fall in the range 0 to 1. Part A (20 points): Disparity matching along each epipolar lines Just like in Assignment 3, you will use the files provided with the script DepthEstimationFromStereoVideoExample. Your DP algorithm will replace the disparity.m built-‐in Matlab function. For each image pair, you seek to output a disparity map for the left image indicating the disparity to the right image. The cost function is defined such that the penalty for matching two pixels is the square of the difference in their intensity. The penalty for a pixel being occluded is a fixed value, occ. The images (frames in the video) are already rectified, so that the epipolar lines are horizontal scan lines of the input images. Thus, you just need to run the DP stereo algorithm on each corresponding line/row in the two images. You will need to call your function once for each epipolar line. Your function should have the form: D = stereoDP(e1, e2, maxDisp, occ) The recommended value for occ is 0.01. For maxDisp, you can start with the value 64 (this is the maximum disparity value as resulting from using the built-‐in Matlab disparity.m function). Feel free to try a lower value and notice if your disparity maps improves. Algorithm: 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 if they are 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 The cost of skipping a pixel (in either scanline) is given by a constant occ.
We can compute the optimal (minimal cost) alignment of two scanlines recursively as follows: 1. D(0,j) = j * occ 2. D(i,0) = i * occ 3. D(1, 1) = d11, 4. D(i, j) = = min(D(i−1,j−1) + dij , D(i−1,j) + occ, D(i,j−1) + occ) Note: just like in the LCS complete problem, you will need to save which “direction” was used for the calculation of each D(i, j)value: North, West, or Northwest. Part B (10 points): Backtracking The goal is to find the optimal alignment (and thus the disparity) by backtracking. Starting at (i, j) = (N, N), trace your path of minimum cost all the way to (1,1). You will need to use the “directions” saved in part A. 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. Part C (10 points): Displaying the disparity map For display purposes, the disparity values should be normalized and mapped to the range [0,1] and, to distinguish valid disparities from occlusions, you should colorize the image so that occluded pixels are shown in color while the rest of the disparity map is shown in grayscale. Here is pseudo-‐code for scaling the values appropriately and showing occlusions in a different color: function [d_color] = display_dmap(d) % 1. Map disparity into the range [0,1] % max_d = the maximum calculated value of disparity; % min_d = the minimum calculated value of disparity; % scale the disparity values by subtracting the minimum % value min_d and dividing by the difference beween max_d % and min_d % 2. Colorize occluded pixels to be red % dColor = color image where each RGB layer is equal to the % scaled disparity matrix (values between 0 and 1) % find the positions/indices where each of the 3 values of % dColor is equal to NaN, and store them in a variable % replace the values of these positions with: % dColor(at position in R layer) = 1;
% dColor(at position in G layer) = 0; % dColor(at position in B layer) = 0; % 3. Display dColor image using imshow Part C (extra credit 20 points): Different Cost Metrics Up to this point, we have used the squared difference in pixel value as our matching cost. In this section we will extend our definition of matching cost to include neighborhoods of pixels. We will evaluate two different cost metrics: 1. (10 points) Sum of Squared Differences (SSD) and 2. (10 points) Normalized Cross Correlation (NCC). W e wish to compute the SSD/NCC match cost between pixel (x1, y) in image 1 and pixel (x2, y) in image 2. We first extract a window W1 centered at pixel (x1, y) from image 1. We then extract a window W2 centered at pixel (x2, y) from image 2. The size of the two windows should be the same. Use the same definition of window matching with SSD and NCC as in Assignment 3. For this assignment (extra credit), evaluate your algorithm using the SSD and NCC match costs with window sizes of 3x3 and 5x5 (four disparity maps total, 5 points each). You can start with the same occlusion penalty (occ) as for 1-‐pixel SSD, and then try to change this value and see how it affects your disparity maps. Since evaluating these cost functions can be computationally intensive, you may find it helpful to optimize your implementation to get acceptable run-‐times. The following list of suggestions may be of help: • Adjust the values for the minimum and maximum disparity for each epipolar line and only evaluate the match cost for pixels in this disparity range. You can use the values obtained at the first pass and then reduce the search range accordingly. • Think of ways to compute any part of the match cost using vectorized code rather than loops. • Take advantage of Matlab’s profiling tool (available under Desktop → Profiler in the menu). This will isolate the slowest parts of your code. Implementing the first suggestion is probably sufficient to make your algorithm run in a reasonable amount of time. Task 3 (20 points): Calculate stereo disparity using the DP (cones images) Task 4 (20 points): Calculate stereo disparity using the DP (teddy images) The left and right images for the cones and the teddy sets, as well as the left and right disparity maps (ground truth) can be found here: http://vision.middlebury.edu/stereo/data/scenes2003/
Task 1 (20 points): Implement the Longest Common Subsequence (LCS) Given two sequences, X ={x1; ... ; xm} and Y ={y1; ... ; yn}. Find a subsequence common to both whose length is longest. A subsequence doesn‘t have to be consecutive, but it has to be in order. The LCS problem has 2 versions: • The Simple version, requesting only to find out the length of the longest common subsequence. • The Complete version, requesting to find out the sequence itself. For this assignment, you need to implement the Complete version using the Dynamic Programming approach. X = {x1, … xm} Y = {y1, …,yn} Xi = the prefix subsequence {x1, … xi} Yi = the prefix subsequence {y1, … yi} Z ={z1, … zk} is the LCS of X and Y . LCS(i,j) = LCS of Xi and Yj We can recursively define the LCS as: Use the recursive definition to set up your memorization table and compute the size of the longest subsequence and the characters that are part of it. LCS(i,j)= 0 if i=0 or j=0, LCS(i−1 ,j−1)+1 if i,j0 and xi =yj, max(LCS(i−1 ,j),LCS(i,j−1)) if i,j0 and xi ≠yj. # $ % % & % % H O R S E B A C K S N O W F L A K E LCS = OAK
Task 2 (40 points): Calculate stereo disparity using the DP (as outlined below) Here, you will implement a stereo algorithm that uses dynamic programming. This algorithm enforces the ordering constraint, the uniqueness constraint, and matches individual pixels based on a cost function. Every pixel in one image can either match one pixel in another image, or be marked as occluded. Note: this algorithm assumes the image intensities in the left and right image fall in the range 0 to 1. Part A (20 points): Disparity matching along each epipolar lines Just like in Assignment 3, you will use the files provided with the script DepthEstimationFromStereoVideoExample. Your DP algorithm will replace the disparity.m built-‐in Matlab function. For each image pair, you seek to output a disparity map for the left image indicating the disparity to the right image. The cost function is defined such that the penalty for matching two pixels is the square of the difference in their intensity. The penalty for a pixel being occluded is a fixed value, occ. The images (frames in the video) are already rectified, so that the epipolar lines are horizontal scan lines of the input images. Thus, you just need to run the DP stereo algorithm on each corresponding line/row in the two images. You will need to call your function once for each epipolar line. Your function should have the form: D = stereoDP(e1, e2, maxDisp, occ) The recommended value for occ is 0.01. For maxDisp, you can start with the value 64 (this is the maximum disparity value as resulting from using the built-‐in Matlab disparity.m function). Feel free to try a lower value and notice if your disparity maps improves. Algorithm: 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 if they are 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 The cost of skipping a pixel (in either scanline) is given by a constant occ.
We can compute the optimal (minimal cost) alignment of two scanlines recursively as follows: 1. D(0,j) = j * occ 2. D(i,0) = i * occ 3. D(1, 1) = d11, 4. D(i, j) = = min(D(i−1,j−1) + dij , D(i−1,j) + occ, D(i,j−1) + occ) Note: just like in the LCS complete problem, you will need to save which “direction” was used for the calculation of each D(i, j)value: North, West, or Northwest. Part B (10 points): Backtracking The goal is to find the optimal alignment (and thus the disparity) by backtracking. Starting at (i, j) = (N, N), trace your path of minimum cost all the way to (1,1). You will need to use the “directions” saved in part A. 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. Part C (10 points): Displaying the disparity map For display purposes, the disparity values should be normalized and mapped to the range [0,1] and, to distinguish valid disparities from occlusions, you should colorize the image so that occluded pixels are shown in color while the rest of the disparity map is shown in grayscale. Here is pseudo-‐code for scaling the values appropriately and showing occlusions in a different color: function [d_color] = display_dmap(d) % 1. Map disparity into the range [0,1] % max_d = the maximum calculated value of disparity; % min_d = the minimum calculated value of disparity; % scale the disparity values by subtracting the minimum % value min_d and dividing by the difference beween max_d % and min_d % 2. Colorize occluded pixels to be red % dColor = color image where each RGB layer is equal to the % scaled disparity matrix (values between 0 and 1) % find the positions/indices where each of the 3 values of % dColor is equal to NaN, and store them in a variable % replace the values of these positions with: % dColor(at position in R layer) = 1;
% dColor(at position in G layer) = 0; % dColor(at position in B layer) = 0; % 3. Display dColor image using imshow Part C (extra credit 20 points): Different Cost Metrics Up to this point, we have used the squared difference in pixel value as our matching cost. In this section we will extend our definition of matching cost to include neighborhoods of pixels. We will evaluate two different cost metrics: 1. (10 points) Sum of Squared Differences (SSD) and 2. (10 points) Normalized Cross Correlation (NCC). W e wish to compute the SSD/NCC match cost between pixel (x1, y) in image 1 and pixel (x2, y) in image 2. We first extract a window W1 centered at pixel (x1, y) from image 1. We then extract a window W2 centered at pixel (x2, y) from image 2. The size of the two windows should be the same. Use the same definition of window matching with SSD and NCC as in Assignment 3. For this assignment (extra credit), evaluate your algorithm using the SSD and NCC match costs with window sizes of 3x3 and 5x5 (four disparity maps total, 5 points each). You can start with the same occlusion penalty (occ) as for 1-‐pixel SSD, and then try to change this value and see how it affects your disparity maps. Since evaluating these cost functions can be computationally intensive, you may find it helpful to optimize your implementation to get acceptable run-‐times. The following list of suggestions may be of help: • Adjust the values for the minimum and maximum disparity for each epipolar line and only evaluate the match cost for pixels in this disparity range. You can use the values obtained at the first pass and then reduce the search range accordingly. • Think of ways to compute any part of the match cost using vectorized code rather than loops. • Take advantage of Matlab’s profiling tool (available under Desktop → Profiler in the menu). This will isolate the slowest parts of your code. Implementing the first suggestion is probably sufficient to make your algorithm run in a reasonable amount of time. Task 3 (20 points): Calculate stereo disparity using the DP (cones images) Task 4 (20 points): Calculate stereo disparity using the DP (teddy images) The left and right images for the cones and the teddy sets, as well as the left and right disparity maps (ground truth) can be found here: http://vision.middlebury.edu/stereo/data/scenes2003/
1 file (4.0MB)
