3D Reconstruction: Solving Equations for 3D Points from Uncalibrated Images

Question

This is a pretty straightforward question (I hope). The following is from 3D reconstruction from Multiple Images, Moons et al (Fig 2-13, p. 348):

Projective 3D reconstruction from two uncalibrated images

Given: A set of point correspondences m1 in I1 and m2 in I2 between two uncalibrated images I1 and I2 of a static scene.

Aim: A projective 3D reconstruction ^M of the scene.

Algorithm:

1. Compute an estimate ^F for the fundamental matrix
2. Compute the epipole e2 from ^F
3. Compute the 3x3-matrix
   ^A = −(1/||e2||2) [e2]x ^F
4. For each pair of corresponding image points m1 and m2, solve the following system of linear equations for ^M :
   ^p1 m1 = ^M and ^p2 m2 = ^A ^M + e2
   ( ^p1 and ^p2 are non-zero scalars )

[I apologize for the formatting. I don't know how to put hats over characters.]

I'm pretty much OK up until step 4. But it's been 30+ years since my last linear algebra class, and even then I'm not sure I knew how to solve something like this. Any help or references would be greatly appreciated.

By the way, this is sort of a follow-on to another post of mine:

Detecting/correcting Photo Warping via Point Correspondences

This is just another way to try to solve the problem.

Answer 1

Given a pair of matching image points m₁ and m₂, the two corresponding rays from the optical centers are unlikely to intersect perfectly due to noise in the measurements. Consequently a solution to the provided system should instead be found in the (linear) least square sense i.e. find x = argmin_x | C x - d |^2 with (for instance):

      /           0 \ /    \
      |  I  -m1   0 | |  M |
C x = |           0 | |    |
      |       0     | | p1 |
      |  A    0 -m2 | \ p2 /
      \       0     /

and

    /  0  \
    |  0  |
d = |  0  |
    |     |
    | -e2 |
    \     /

The problem has 5 unknowns for 6 equations.

A possible alternative formulation exploits the fact that m₁ and m₂ are collinear with M so m1 x M = 0 and m2 x (A M + e2) = 0 yielding the linear least squares problem x = argmin_x | C x - d |^2 with:

    / [m1]x   \ /   \
C = |         | | M |
    \ [m2]x A / \   /

and

    /     0    \
d = |          |
    \ -m2 x e2 /

where [v]x is the 3 x 3 matrix of the cross product with v. The problem has 3 unknowns for 6 equations which can be reduced to 4 only by keeping non-linearly dependent ones.