Assignment 3: Stereo

Due date : 2/23 (Tuesday)

Late Due date : 2/27 (Friday)

Before you start:

Download the assignment's files here.

Assignment:

For this assignment you'll be implementing a stereo algorithm for computing disparities between already rectified image pairs. This requires the implementation of several image match scores, methods for smoothing or removing the noise from the match scores, a segmentation algorithm, and a method for finding the best disparity for each pixel. Feel free to reuse any code from previous assignments.

In the project, you should only have to update one file "Project3.cpp. " The buttons in the UI will call the corresponding functions in "Project3.cpp. " For the stereo datasets with ground truth disparities, the percentage of wrong pixels will be displayed above the image. Please select different tabs to see different images. Slices of the match costs may be viewed by left clicking on the image (they are displayed below the image. )

What to turn in:

To receive credit for the project, you need to turn in the completed file "Project3.cpp", any additional files needed for compiling, the requested images for each task, and a text file reporting the error values with the corresponding parameters (SSD offset, Sigma S, Sigma I, Sigma Spatial, Sigma Color, Grid size) changed for each task.

Tasks:

Overview of the tasks is given here and details of the data structures used in the program are here.

Step 1: (6 points: 2 points each) Implement SSD (Sum of Squared Differences), SAD (Sum of Absolute Differences) and NCC (Normalized Cross Correlation) match cost functions. For each routine, compute the score over a window with the supplied offset. Window size is computes as =(2*offset) +1. For example, if offset = 2, then Window size is 5x5. Store the computed match cost in "matchCost". Each entry in matchCost is the distance in color space between (c, r) in image 1 and (c - d, r) in image 2. Store these values at "matchCost[(d - minDisparity)*w*h + r*w + c]". Note: The NCC score is high for good matches and low for bad matches, so store one minus the NCC score instead of the NCC score in 1-D array matchCost.

(4 points) Implement FindBestDisparity which finds the disparity with minimum cost for each pixel and stores it in the input array "disparities".

Required: Open "cones.txt". Press SSD with offset = 2, and Find Best Disparity. Save the "Disparity" image as "1a.png". Press SAD with offset = 2 , and Find Best Disparity. Save the "Disparity" image as "1b.png". Open "conesGainOffset.txt". Press SSD, and Find Best Disparity. Save the "Disparity" image as "1c.png". Press NCC with Offset = 2, and Find Best Disparity. Save the "Disparity" image as "1d.png". (The gain offset images are brighter.)

Step 2: (2 points) Smooth and denoise the match cost values. For this step, implement GaussianBlurMatchScore to blur the match costs in the 1-D array "matchCost" i.e., Gaussian blur the match cost for each disparity. You have to implement SeparableGaussianBlurImage as a helper function (similar to Assignment 1) . BilateralBlurMatchScore is already implemented to use a bilateral filter to blur the match costs at each disparity. The weights or kernel used in the bilateral filter are computed from the color image. Using the computed kernels, match costs are blurred at each disparity.

Required: Open "cones.txt". Press SSD, press Gaussian, and Find Best Disparity. Repeat this process and change the value of SSD offset, Gaussian Sigma S until the error is below 21.0. Save the corresponding "Disparity" image as "2a.png". Press SSD, press Bilateral, and Find Best Disparity. Repeat this process and change the value of SSD offset, Bilateral Sigma S and Sigma I until the error is below 21.0. Save the corresponding "Disparity" image as "2b.png".

Step 3: Implement k-means clustering to cluster in color and position space. The function Segment has already been implemented, along with GridSegmentation that initializes the segmentation. Please examine Segment to see how the k-means clustering algorithm works by iteratively updating the segment means and assigning pixels to segments. You'll need to implement three helper functions:

1. (2 points) ComputeSegmentMeans - Compute the mean position and color for each segment.

2. (2 points) AssignPixelsToSegments - Assign each pixel to its closest segment. The distance between a pixel and segment is measured in a 5 dimensional space, position (2) and color (3). Use the Mahalanobis distance (see Wikipedia or Rick's book) when computing the closest segments with standard deviations of spatialSigma and colorSigma for position and color respectively.

3. (4 points) SegmentAverageMatchCost - Given the computed segmentation, average the match costs within each segment producing a new "disparities" image. That is, each pixel in the segment should have the same match cost for each disparity. The output is a new 1-D matchCost array.

Required: Open "cones.txt". Press SSD, press Segment, and Find Best Disparity. Repeat this process and change the value of SSD offset, Sigma Spatial, Sigma Color, Grid Size until the error is below 25.0. Save the corresponding "Disparity" image as "3a.png" and the "Segments" image as "3b.png".

Bell and Whistles (extra credit)

(Whistle = 1 point, Bell = 2 points)

Compute one of the 20 best disparities in the class on "cones.txt" as measured by the error score. Please briefly describe your approach, record your error score, and save the disparity and error image. Use any approach you please (in the literature or something you thought up), and implement using the "Magic Stereo" button.

Compute one of the 10 best disparities in the class on "cones.txt" as measured by the error score. Please briefly describe your approach, record your error score, and save the disparity and error image. Use any approach you please (in the literature or something you thought up), and implement using the "Magic Stereo" button.

Compute one of the 5 best disparities in the class on "cones.txt" as measured by the error score. Please briefly describe your approach, record your error score, and save the disparity and error image. Use any approach you please (in the literature or something you thought up), and implement using the "Magic Stereo" button.

Improve the "Render" function to use both image 1 and image 2 when rendering. That is, use image 2 to fill in the holes in the rendering of image 1. To do this you'll need to compute disparities for image 2 as well as image 1.