COMP 776 Spring 2009

Assignment 4: Stereo Matching

Due date: March 31, 5PM

The goal of the assignment is to implement a simple window-based stereo matching algorithm for rectified stereo pairs. You will be using the following stereo pair:

  • first image, second image

    Follow the basic outline given in this lecture: pick a window around each pixel in the first (reference) image, and then search the corresponding scanline in the second image for a matching window. The output should be a disparity map with respect to the first view (use this ground truth map for qualitative reference). You should experiment with the following settings and parameters:

    • Search window size: show disparity maps for several window sizes and discuss which window size works the best (or what are the tradeoffs between using different window sizes). How does the running time depend on window size?

    • Disparity range: what is the range of the scanline in the second image that should be traversed in order to find a match for a given location in the first image? Examine the stereo pair to determine what is the maximum disparity value that makes sense, where to start the search on the scanline, and which direction to search in. Report which settings you ended up using.

    • Matching function: try sum of squared differences (SSD) and normalized correlation. Discuss in your report whether there is any difference between using these two functions, both in terms of quality of the results and in terms of running time.
    In addition to showing your results and discussing implementation parameters, discuss the shortcomings of your algorithm. Where do the estimated disparity maps look good, and where do they look bad? What would be required to produce better results? Also discuss the running time of your approach and what might be needed to make stereo run faster.


    You should also implement at least one of the following extensions. Of course, feel free to do more than one for bonus points.
    • Convert your disparity map to a depth map and attempt to visualize the depth map in 3D. Just pretend that all projection rays are parallel, and try to "guess" the depth scaling constant. Experiment with displaying a 3D point cloud, or computing a Delaunay triangulation of that point cloud.

    • Find additional rectified stereo pairs on the Web and show the results of your algorithm on these pairs.

    • Find non-rectified stereo pairs and rectification code on the Web and apply your algorithm to this data.

    • Implement multiple-baseline stereo as described in this lecture (see paper by Okutomi and Kanade). Use this data.

    • Try to incorporate non-local constraints (smoothness, uniqueness, ordering) into your algorithm. You can come up with simple heuristic ways of incorporating these constraints, or try to implement some of the more advanced methods discussed in the course (dynamic programming, graph cuts). For this part, it is also fine to find code on the web.

    • Got another idea not listed above? Just send me email and I'll let you know whether it's OK for the assignment.

    Turning in the Assignment

    As usual, please email me or post on the Web (1) your MATLAB code and (2) a PDF report file that includes all your results and discussion by 5PM, Tuesday, March 31.