Initial structure

Once the two projection matrices have been fully determined the matches can be reconstructed through triangulation. For each point a corresponding line of sight can be placed in space. In the absence of noise these lines should intersect in the 3D points. In practice, however, these lines will not perfectly intersect and a trade off should be made. In a metric frame one would take the point in the middle. In projective space, however, this concept is not defined.

In the uncalibrated case the only meaningful minimizations can be carried out in the image and not in space. Therefore, the distance between the reprojected 3D point and the image points should be minimized:

$$D({\tt m}_1,{\bf P}_1 {\tt M})^2 + D({\tt m}_2,{\bf P}_2 {\tt M})^2$$ (E2)

It was noted by Hartley and Sturm [67] that the only important choice is to select in which epipolar plane the point is reconstructed. Once this choice is made it is trivial to select the optimal point from the plane.

A bundle of epipolar planes has only one parameter. In this case the dimension of the problem is reduced from 3-dimensions to 1-dimension. Minimizing the following equation is thus equivalent to minimize equation 5.2.

$$D({\tt m}_1,{\tt l}_1(\alpha))^2+D({\tt m}_2,{\tt l}_2(\alpha))^2$$ (E3)

with ${\tt l}_1(\alpha)$ and ${\tt l}_2(\alpha)$ the epipolar lines obtained in function of the parameter $\alpha$ describing the bundle of epipolar planes. It turns out [67] that this equation is a polynomial of degree 6 in $\alpha$. The global minimum of equation 5.3 can thus easily be computed.

In both images the point on the epipolar line ${\tt l}_1(\alpha)$ and ${\tt l}_2(\alpha)$ closest to the points ${\tt m}_1$ resp. ${\tt m}_2$ is selected. Since these points are in epipolar correspondence their lines of sight meet in a 3D point.

This procedure is followed for every match that was obtained between the two first images. This yields an initial 3D structure. In the next section we will see how this allows us to place all the other views in the frame defined by the two first views.