Saturday, June 25, 2011

Stereo Matching - Depth Maps from Stereo Pairs

3D lenticulars made from just the left and right images suffer from a very narrow viewing angle, which makes getting the 3D effect difficult. Intermediate frames makes the viewing a much more pleasant experience. They also make the GIF animations (wiggles) more fluid and therefore more effective. Understandably, there's a lot of interest in generating depth maps from stereo pairs in the 3D community.

If you have a look at the academic papers that deal with depth maps or stereo matching (just using google), you will soon be overwhelmed by the amount of stuff that's being written over the years. The question is: how do you know which method works best?

There's a paper published in 2002 titled "A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms" by Daniel Scharstein and Richard Szeliski that does a thorough review of stereo matching methods. "Taxonomy" means that they have identified "building blocks" that are common in most algorithms. Doing that always makes things easier since it shows that a lot of algorithms are actually quite similar in the way they are designed. "Dense" means that the matching is done at the pixel level. "Dense Two-Frame Stereo Correspondence" is basically another way of saying "depth map". The authors are kind enough to provide the source code that was used to do the testing (which you can use on your own stereo pairs). If you are interested in trying this out yourself, go to vision.middlebury.com, download the source code, the scripts and the images. You need to compile the code to be able to use the program, called StereoMatcher, which runs on a script that you can customize. On a windows pc, you're probably gonna need Microsoft Visual Studio (the Express version is free). On a linux box, it's a bit easier since the gnu C++ compiler is already there as part of the install. Once you have created the executable and read the scripts that are used to run the provided test cases, it's not that hard to figure out how you can run your own stuff. The only thing is that you're gonna have to save or convert your stereo images in the ppm format (see gimp or photoshop for that). You also have to be well aware that the stereo pairs you can feed to those stereo matching algorithms need to be rectified, that is, for any point in the scene, the two projected points (on the left and right images) must be on the same line, or scan line (see Stereo Matching Rectified Geometry).

I took the liberty to run StereoMatch on the (overused) test image called "Tsukuba":


Left image.



Right image.



True disparities.


Here are the depth maps for each available algorithm:


SSD (Sum of Squared Differences).



SO (Scanline Optimization).



SAD (Sum of Absolute Differences).



SA (Simulated Annealing).



GC (Graph Cut).



DP (Dynamic Programming).


GC (Graph Cut) appears to be the best performing algorithm for this particular benchmark stereo pair which, to be honest, has about nothing to do with the "real world" (piecewise planar objects perpendicular to the optical axes are not too commonly found in nature). If this subject fascinates you, check Stereo Matching - Local Methods, Stereo Matching - Global Methods, and Stereo Matching - Variational Methods for more info on various stereo matching methodologies.

I, Ugo Capeto, have implemented some software to generate depth maps from stereo pairs. It's available at the 3D Software page right here on this blog and it's free to download.

10 comments:

  1. This is very interesting. I'm currently working on optimizing and increasing the sharpness of each object in said pictures. As of right now I believe this code is the best depth generator available.

    ReplyDelete
  2. you mean graph cuts? the only problem with graph cuts is that the type of energy it can handle is limited. Then again, and that's true for all stereo matching methods that rely on the minimization of an energy functional, you have to be careful with the energy formulation because if it's not convex, the problem is ill-posed and you may end with local minima unless you use simulated annealing.

    ReplyDelete
  3. please , where to find sample of the scriptFile.txt
    and where to put it in code , to test the Application
    please reply, I need it fast ,thanks in advance

    ReplyDelete
    Replies
    1. the code is available at http://vision.middlebury.edu/stereo/code/

      Delete
    2. ok, I already install code and compile , but it need me to write script file to read from it the input as I guess but no example how to write the script file and where to locate it in the source code directory, please say to me how to use the program after compile as it run and say no command given in the command line

      Delete
    3. can't say i remember the details but if i was able to figure it out, it means that it wasn't too hard.

      Delete
    4. Hi @emyton did you solve the problem and run the GC (Graph Cut) ?

      Delete
    5. hi did you solve the problem and run GC (Graph Cut) ?

      Delete
    6. if yes I need it fast ,thanks in advance :)

      Delete
    7. I have implemented a Graph Cut depth map generator under the name dmag3. It is available freely via the "Software" page on this very blog. I personally don't recommended using GC for depth map creation though.

      Delete