Shearing and Hartley's rectification

Question

I'm using Richard Hartley's rectification algorithm to rectify a pair of images before performing stereo disparity computation. The problem is I'm observing shearing in one of the rectified images and it's causing problems on disparity computation.

Consider these two input images (the points pairs were produced using SURF):

Hartley's algorithm produced these two rectified images:

The epipolar lines look fine. The following images shows some epipolar lines and a few point pairs:

The rectified SURF keypoints look fine too, consider the following small sample for inspection, d is disparity and erro is the difference between the y coordinate (zero for a perfect mapping):

(306.28, 139.00) <-> (284.15, 138.48): d = -22.13, erro = -0.52
(259.84, 150.72) <-> (234.34, 150.51): d = -25.50, erro = -0.21
(423.93, 151.01) <-> (425.24, 150.71): d = 1.30, erro = -0.30
(220.98, 151.05) <-> (190.53, 151.05): d = -30.45, erro = -0.00
(354.21, 157.88) <-> (346.19, 157.91): d = -8.02, erro = 0.04
(304.17, 161.58) <-> (289.66, 161.80): d = -14.51, erro = 0.22
(229.47, 162.44) <-> (203.86, 162.27): d = -25.61, erro = -0.17
(406.54, 262.40) <-> (442.38, 262.91): d = 35.84, erro = 0.50
(361.67, 290.02) <-> (399.54, 289.98): d = 37.87, erro = -0.04
(356.44, 293.49) <-> (394.51, 292.96): d = 38.07, erro = -0.53
(340.01, 339.44) <-> (318.47, 339.75): d = -21.54, erro = 0.31
(245.47, 360.89) <-> (204.93, 360.18): d = -40.55, erro = -0.71
...

Now, the problem. The following image shows the two rectified images overlaped:

The ZOTAC word printed in the box is a good example. The word is in the same plane and, ideally, should present similar disparity. But the observed shearing will produce small disparities for "Z pixels" compared to disparities for "C pixels".

I'm computed the rectification using two different implementations of the algorithm: the OpenCV implementation, stereoRectifyUncalibrated, and an implementation coded by myself, from scratch, using Python and NumPy (following section 11.12 in Hartley and Zisserman's book). Both implementations got the same results. What is the matter with Hartley's algorithm? Can stereo algorithms handle this problem? Or have I made some mistake?

[This question was asked at OpenCV Q&A. Because, apparently, it is not an OpenCV issue but an algorithm issue, it is being asked here as an general computer vision question.]

Answer 1

Loop & Zhang present a solution in this paper. They use a shearing transform to reduce the distortion introduced by the projective transform that mapped the epipoles to infinity (ie, that made the epipolar lines parallel). Consider the shearing transform

     | k1 k2 0 |
S =  | 0   1 0 |.
     | 0   0 1 |

Let w and h be image width and height respectively. Consider the four midpoints of the image edges:

a = ((w-1)/2, 0, 1),
b = (w-1, (h-1)/2, 1),
c = ((w-1)/2, h-1, 1) and
d = (0, (h-1)/2, 1).

According to Loop & Zhang:

(...) we attempt to preserve perpendicularity and aspect ratio of the lines bd and ca

Let H be the rectification homography and let a' = Ha be a point in the affine plane by dividing through so that a'2 = 1 (note a'2 is the third component, ie, a' = (a'[0], a'1, a'2)). Let

x = b' - d',
y = c' - a'

According to Loop & Zhang:

As the difference of affine points, x and y are vectors in the euclidean image plane. Perpendicularity is preserved when (Sx)^T(Sy) = 0, and aspect ratio is preserved if [(Sx)^T(Sx)]/[(Sy)^T(Sy)] = w²/h².

The real solution presents a closed-form:

k1 = (h²x[1]² + w²y[1]²)/(hw(x[1]y[0] - x[0]y[1])) and
k2 = (h²x[0]x[1] + w²y[0]y[1])/(hw(x[0]y[1] - x[1]y[0]))

up to sign (the positive is preferred).

This is the result after applying shearing S on the left image:

Now the left and right images overlaped:

Finally, OpenCV stereo method StereoBM can compute a reasonable result for disparity: