Stereo and Segmentation Solution

Description

For the third homework assignment, we are asking you to implement a few functions in a stereo pipeline examprovided by mathworks.com

Provided files:

In your Matlab Command Window, type

>> edit DepthEstimationFromStereoVideoExample

What You Have to Do:

Task 1 (15 points): Calculate disparity using the SSD algorithm

Implement the SSD matching algorithm for a range of window sizes, and create a disparity image D(x, y) such that Left(x, y) = Right(x + D(x, y), y) when matching from left to right.

Write a function to replace the disparity built- in function on line 54. Your function needs to accept as an input value the size of the window search. Call your function three times for the following window sizes: 1, 5 and 11.

Create a 2×2 subplot and display the disparity map results from these three function calls, plus the one obtained using Matlab’s built-in disparity function.

Notes:

1. Remember to reduce the search only over epipolar lines.

2. You should also restrict the search using the maximum disparity range. You can use the value 63. This is the maximum disparity value as calculated by using the built-in Matlab disparity.m function (see line 56 in the original script). Feel free to try a lower value and notice if your disparity maps improve.

3. When using a window size bigger than 1, it is common practice to use a Gaussian weighting of the window, so that the center has greater influence than the periphery. Convolve your window matrices with a Gaussian filter prior to computing the sum of squared differences.

4. For this task, you do not need to impose any constraint on the matching algorithm. But, if your matching algorithm finds more than one “best match”, you will want to come up with a rule for selecting just one match and stick to it. Don’t forget to let us know in your comments, what rule did you use.

Task 2 (15 points): Calculate disparity using the NCC algorithm

Implement the normalized cross correlation (NCC) matching algorithm for a range of window sizes, and create a disparity image D(x, y) such that Left(x, y) = Right(x + D(x, y), y) when matching from left to right. Similarly, remember to reduce the search only over epipolar lines and to restrict the search using the disparity range [0,63] (see line 56 in the original script).

Information on how to compute NCC for image-processing applications here: https://en.wikipedia.org/wiki/Cross-correlation#Normalized_cross- correlation The inner product of vectors approach mentioned on Wikipedia, also here, slide 66:

http://www.gris.tudarmstadt.de/teaching/courses/ws0910/cv2_ws0910/slides/l3-stereo-v1_0.pdf

Write a function to replace the disparity built- in function on line 54. Your function needs to accept as an input value the size of the window search. Call your function three times for the following window sizes: 3, 5 and 7.

Create a 2 x 2 subplot and display the disparity map results from these three function calls, plus the one obtained using Matlab’s built-in disparity function.

Note (same as for Task1):

1. For this task, you do not need to impose any constraint on the matching algorithm. But, if your matching algorithm finds more than one “best match”, you will want to come up with a rule for selecting just one match and stick to it. Don’t forget to let us know in your comments, what rule did you use.

Task 3 (20 points): Uniqueness constraint. So far, you have found matches based on an epipolar constraint (matches lie on the same scanline) and on the similarity constraint ( because each unique pair of visual features originate from the same physical surface or object, they naturally look very similar and should have similar intensity values). Modify your implementation of the disparity function to incorporate the uniqueness constraint: one visual feature in one retinal image can have at most one corresponding counterpart in the other image. This is explained by the fact that one physical point/surface always ‘causes’ at most one feature in each retinal image, and one physical point/surface cannot project at two retinal locations at the same time. Your algorithm should enforce a rule that, for each left-/right- eye feature, there will be only one corresponding feature in the right-/left- eye image.

Note:

1. There is no correct answer here. Think hard and come up with your own solution to this constraint and don’t be upset if another peer comes up with a different way.

Task 4 (20 points): Generate outliers map – Refine the disparity by performing a left-right consistency check.

The disparity map d LR(x) is acquired considering as reference image the left image of the stereo pair. If the right image is considered as reference, then the disparity map d RL(x) is acquired. The disparity maps dLR(x) and dRL(x) can be useful in detecting problematic areas, especially outliers in occluded regions and depth discontinuities. One strategy for detecting outliers is the Left–Right consistency check introduced by (1). In this strategy, the outliers are disparity values that are not consistent between the two maps and therefore, they do not satisfy the relation:

| dLR(x) −dRL(x−dLR(x)) | ≤ TLR, where TLR is a user-defined threshold.

Write a function that accepts as inputs two disparity maps (LR and RL) and a value for TLR and returns a binary image where the outliers have the value 1 and the inliers have the value 0.

Call this function twice, passing as inputs the LR and RL disparity maps from SSD and NCC matching with window size of 3. Use a TLR value of 1. With this value, pixels with difference equal to 1 in the Left–Right consistency check are not considered outliers. Plot the two resulting binary images side by side.

Task 5 (10 points): Compute depth from disparity

Now that we have a disparity image, computing depth at every pixel in the left image should be very straightforward. Use equation 11.1 from the Szeliski textbook.

Write a function to replace the reconstructScene built- in function on line 64. Your function should have the same input arguments as the built -in version and it should return a matrix of depth values for each pixel location from the left image.

Task 6 (20 points): Synthetic stereo sequences

As you’re developing stereo matching algorithms, it might prove useful to test them on synthetic stereo sequences, and to compare with a ground truth disparity map.

Use the provided pair of synthetic images and your disparity implementation functions from Tasks 1-3 to generate your disparity map(s). Compare your result to the corresponding ground truth (provided):

1. Compare disparity maps visually by plotting side by side

2. Calculate a map of errors and display it

3. Calculate a histogram of disparity differences and display it – the bin size is up to you.

Dynamic Programming

Task 7 (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 (i.e. the image is grayscale).

Part A (20 points): Disparity matching along each epipolar lines

Your DP algorithm will replace the disparity.m built-in Matlab function, just like the ones for Task 1 and 2. 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 63 (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))²

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

Given D we 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, again

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

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:

1. 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 values obtained at the first pass

2. Think of ways to compute any parts of the match cost using vectorized code rather than loops

3. 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.

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. Save all the figures/plots your program generates as image files. Zip all the .m and image files together and submit the resulting .zip file through Moodle as homework 3 by Sunday, March 11th, by 11:55pm.

1. M. Humenberger, T. Engelke, W. Kubinger, A census-based stereo vision algorithm using modified semi-global matching and plane-fitting to improve matching quality, CVPR ECV Workshop, 2010.