How can I compute the dense disparity map from to stereo images ?

Question

How can I compute the dense disparity map from to stereo images ?

My idea so far was to go over all the pixels from the first image, and scan the second image for matches. To compare the similarity of two pixels i computed the squared difference of pixels in a small window around them. The algorithm works relatively well on synthetic images, but fail on pictures that contain reflections, or have larger differences in light intensity. What approach should i use to get better results?

Masters of image processing, please share you knowledge.

Answer 1

I found this write up on a method for calculating a dense disparity map, and if you follow the links you can get the PDF describing their method in detail. Unfortunately my image processing experience doesn't include stereoscopy so I can't comment on the quality of the algorithm presented.

http://serdis.dis.ulpgc.es/~lalvarez/research/demos/StereoFlow/

I'll check my texts for any further material on this subject.

Edit: I looked through the books I have and "Computer Vision" by Linda G. Shapiro and George C. Stockman has a ~10 page explanation of the math behind stereoscopy when camera and image orientation is known, and points to a section on correlation to find common features between stereo images but nothing on disparity mapping.

Answer 2

A popular and effective way to compute disparities involves graph cuts. Essentially, a graph is created from two images and then cut in such a way as to minimize the energy that results from depth discontinuities in the image. Ramin Zabih at Cornell has many papers on the topic:

http://www.cs.cornell.edu/~rdz/graphcuts.html

I suggest "Fast Approximate Energy Minimization via Graph Cuts" as an overview.

Answer 3

The Otto-Chau stereo matching algorithm is very effective and combines adaptive least squares patch matching with sub-pixel precision together with region growing over the matched images:

Otto, G. P., Chau, T. K. W., 1989. ‘Region-growing’ algorithm for matching of terrain images. Image Vision Computing, 7(2), pp. 83-94.

It's an area based approach so does rely to an extent on reasonable amounts of texture in the images. if you have very sparse image data a feature based approach might work better, perhaps augmented by the adaptive LS matching for accuracy. Correlation approaches are easy to implement and can be fast but because they don't take into account affine warping between images they are often not as robust or as accurate as ALS techniques that use a Newton-Raphson scheme to minimise over a number of warping and radiometric parameters to get a really good fit from image to image.