How to obtain stereo correspondences and what exactly is a disparity map?

Question

I am currently reading into the topic of stereo vision, using the book of Hartley&Zimmerman alongside some papers, as I am trying to develop an algorithm capable of creating elevation maps from two images.

I am trying to come up with the basic steps for such an algorithm. This is what I think I have to do:

If I have two images I somehow have to find the fundamental matrix, F, in order to find the actual elevation values at all points from triangulation later on. If the cameras are calibrated this is straightforward if not it is slightly more complex (plenty of methods for this can be found in H&Z).

It is necessary to know F in order to obtain the epipolar lines. These are lines that are used in order to find image point x in the first image back in the second image.

Now comes the part were it gets a bit confusing for me: Now I would start taking a image point x_i in the first picture and try to find the corresponding point x_i’ in the second picture, using some matching algorithm. Using triangulation it is now possible to compute the real world point X and from that it’s elevation. This process will be repeated for every pixel in the right image.

In the perfect world (no noise etc) triangulation will be done based on

x1=P1X 
x2=P2X

In the real world it is necessary to find a best fit instead.

Doing this for all pixels will lead to the complete elevation map as desired, some pixels will however be impossible to match and therefore can't be triangulated.

What confuses me most is that I have the feeling that Hartley&Zimmerman skip the entire discussion on how to obtain your point correspondences (matching?) and that the papers I read in addition to the book talk a lot about disparity maps which aren’t mentioned in H&Z at all. However I think I understood correctly that the disparity is simply the difference x1_i- x2_i?

Is this approach correct, and if not where did I make mistakes?

Answer 1

How to obtain your point correspondences

There are many ways to do it, which can basically be classified into two categories: feature-based and dense matching.

Feature-based methods include using corner detectors, SIFT/SURF/ORB descriptors and other similar feature detectors that provide point to point correspondences. A few of those methods that are implemented in OpenCV are compared here.

Dense-matching methods usually involve some kind of comparison between sliding windows in both images. The most used approach is SSD or variants. A few of these variants are listed here.

What are disparity maps

Your intuition is right: disparity, in a rectified image, is defined as the difference between the x coordinate of a point in two images. It had a neat relationship from projective geometry: disparity = 1/depth. This stackoverflow answer has a few pointers about it. Disparity maps are basically images where each pixel value is the disparity of that point, so it gives you a sense of depth - the further away from the camera, the darker.

EDIT: Yes, in general terms your approach is correct AFAIK. Your description lacks detail, but as you mentioned you can find out how to do each of these pieces in H&Z.