Point matching algorithm from two different images

Question

I am looking for a method or an algorithm which would allow me to recognize and pair sets of points from two different images, for the purpose of stereo vision.

The attached picture presents what I have at the moment: 2 cameras are aligned on the Y axis and slightly offset on the X axis, looking at a set of points. I am able to track and get the 2D positions of each of these points on the two camera images (IMG0 and IMG1).

As such, I have two lists of 2D coordinates:

L0 = { a0, a1, a2, a3, a4, a5, a6 }
L1 = { b0, b1, b2, b3, b4, b5, b6 }

Now, in order to carry out triangulation to get the 3D position of each point, I need to know which point on image IMG1 corresponds to a which point on IMG0. Both camera see the exact same set of point, with the same overall shape, but obviously, due to slight distortion and to the camera being offset on the horizontal, the 2D coordinates do not match from an image to the other.

Ideally, the point matching algorithm I am looking for would result in a list such as:

List = {a0-b0, a1-b1, a2-b2,...}

The order of the list doesn't matter as long as I am sure each point is paired with the right one from the second image.

I have been looking at several papers presenting stereo mapping algorithms, but I didn't find anything relevant to my problem as most algorithm are based on heavy image feature recognition, which is not suitable in my case where I want to quickly process everything in real-time. The closest solution I seemed to find is the point matching algorithm presented here, but once again this seems too heavy for my issue.

Any help would be greatly appreciated.

Answer 1

First of all you should make sure you understand the basic concepts of epipolar geometry, especially the concept of an epipolar line.

In a nutshell: Say you have a 3D point P that projects to a 2D point q in the image of a camera A. Now you have a second camera, call it B, and you want to find the image of P in B. Epipolar geometry tells you that the possible locations of the image of P in B given q are limited to a line, called the epipolar line. It also tells you that (and how) you can compute this line from q and the calibration of your cameras, using what is called the Fundamental matrix.

For your problem this has the following implications:

Let q be a point from list L0.

• If there is a single point in your list L1 which is on the epipolar line of q in the second image, then this is the correct correspondence for q.
• If there are several points on the epipolar line, then your problem cannot be solved with the given information. In this case you need to make heuristic assumptions about the distribution of your points in 3D, since you get one possible 3D point for each pairing of q with a point on the epipolar line.

If your cameras are only offset along the X axis, and if they are identically oriented (i.e. the image planes are parallel), they it is your lucky day: In this special camera configuration, the epipolar lines are horizontal, i.e. for a point (x,y) the epipolar line is the line of all points with arbitrary X coordinate and Y coordinate y.

Note that in practice you also face the problem that points are unlikely to be exactly on epipolar lines due to measurement errors and numerical issues.