Stereo images rectification and disparity: which algorithms

algorithmsimage processing

I'm trying to figure out what are currently the two most efficent algorithms that permit, starting from a L/R pair of stereo images created using a traditional camera (so affected by some epipolar lines misalignment), to produce a pair of adjusted images plus their depth information by looking at their disparity.

Actually I've found lots of papers about these two methods, like:

"Computing Rectifying Homographies for Stereo Vision" (Zhang – seems one of the best for rectification only)
"Three-step image rectiﬁcation" (Monasse)
"Rectification and Disparity" (slideshow by Navab)
"A fast area-based stereo matching algorithm" (Di Stefano – seems a bit inaccurate)
"Computing Visual Correspondence with Occlusions via Graph Cuts" (Kolmogorov – this one produces a very good disparity map, with also occlusion informations, but is it efficient?)
"Dense Disparity Map Estimation Respecting Image Discontinuities" (Alvarez – toooo long for a first review)

Anyone could please give me some advices for orienting into this wide topic?

What kind of algorithm/method should I treat first, considering that I'll work on a very simple input: a pair of left and right images and nothing else, no more information (some papers are based on additional, pre-taken, calibration infos)?

Speaking about working implementations, the only interesting results I've seen so far belongs to this piece of software, but only for automatic rectification, not disparity: http://stereo.jpn.org/eng/stphmkr/index.html

I tried the "auto-adjustment" feature and seems really effective. Too bad there is no source code…

Best Answer

Although I don't have any specific expertise in this field, I can make some recommendations with regard to your research.

A Google Scholar search can be a bit daunting at first, but you can begin to filter the results by noting the number of citations a document has. (Citation count often correlates to how authoritative a given article is. Of course, this is only one metric and isn't foolproof: older documents tend to have more citations than newer ones simply because they've had more time to collect them. But it is a good starting point.) For example, Di Stefano's paper has been cited by over 200 authors, so that might put into question your suggestion that his approach as "inaccurate" (unless that is the consensus of the other citations). On the other hand, the following paper has been cited over 4000 times in the last 10 years and so would probably be a good place to start:

A taxonomy and evaluation of dense two-frame stereo correspondence algorithms (Scharstein, '02)

Look for papers that offer reviews or aggregated summaries of other approaches, such as

Review of stereo vision algorithms: from software to hardware (Lazaros, '08)

I would also recommend looking at some of the standard textbooks in the field, such as:

An Introduction to 3D Computer Vision Techniques and Algorithms (Cyganek, '09)
Multiple View Geometry in Computer Vision (Hartley, '04; may be more dated)

Related Solutions

Which mathematical properties apply to XOR Swap algorithm (and similar bitwise operator algorithms)

This can be done with any invertable binary operation like XOR or addition. So you could just as well write:

 a ← a + b
 b ← a - b
 a ← a - b

Or more generally, suppose that for some binary (associative, commutative) operator # there is an identity i such that

x # i = i # x = x

and that for every value x there is a value x' such that

x # x' = i

Then you can swap two values using that operator:

a ← a # b
b ← a # b'
a ← a # b'

For addition, x' = -x, but for XOR we have x XOR x = 0 so that x' = x, so that:

a ← a XOR b
b ← a XOR b'
a ← a XOR b'

reduces to

a ← a XOR b
b ← a XOR b
a ← a XOR b

Image Processing – How to Implement K-Means Algorithm on RGB Images

You can readily apply the k-means algorithm to the RGB image data set. An image data set is in no way special, except that each data vector is three dimensional (R, G and B) and the values are bounded integers in the [0, 255] range.

The standard k-means algorithm just needs to compute the distance between two as well as the mean of several data points.

For more information on the k-means algorithm, see for example here.

Naive RGB color distance: If you have two elements i and j with RGB values (ri, gi, bi) and (rj, gj, bj), respectively, then the distance d between image points i and j equals:

d = sqrt((ri-rj)^2+(gi-gj)^2+(bi-bj)^2)

And the mean of several colors points would then be the mean of the RGB values separately.

For an implementation of this in OpenCV see example for color quantization on the OpenCV tutorial.

More realistic color distance: The RGB color space is not a good model for color distance unfortunately (see excellent comment by John Forkosh). However, the CIE-L*ab colorspace and some associated color distance model seem to be suited better.

Step 1: Conversion of RGB to CIE-L*ab (RGB is device dependent, so it may need to be transformed before to some absolute colorspace RGB values).

Very probably the platform you are using already has an RGB to CIE-L*ab conversion (Matlab, Java, Python or C++ using OpenCV). Otherwise you would have to write your own (Help).

Step 2: Calculate the distance in the k-means algorithm.

Delta E* from there seems simple to calculate:

(l1,a1,b1) are the Lab values of data point 1 and (l2,a2,b2) are the Lab values of data point 2

d = sqrt((l1 - l2)^2 + (a1 - a2)^2 + (b1 - b2)^2)

The mean of several colors in the CIE-Lab space would again be the mean of each Lab component separately.

But you also may want to try others distances and see what works best.

Summary: The k-means algorithm doesn't need to be modified except for the distance and the mean calculation. For a better suited distance, the conversion to another color space (CIE-L*ab) and the computation of a distance in that color space are recommended.

Best Answer

Related Solutions

Which mathematical properties apply to XOR Swap algorithm (and similar bitwise operator algorithms)

Image Processing – How to Implement K-Means Algorithm on RGB Images

Related Topic