## Description

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, j > 0 and xi = yj

,

max(LCS(i −1, j), LCS(i, j −1)) if i, j > 0 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).

We 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 3×3 and 5×5 (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/

Submitting the assignment:

Make sure each script or function file is well commented and it includes a block

comment with your name, course number, assignment number and instructor name.

Zip all the .m files together and submit the resulting .zip file through Moodle as

Assignment 4 by Wednesday, November 2nd, by 11:55pm.