Computing the fundamental/essential matrix

      #include <gandalf/vision/fundamental.h>
      #include <gandalf/vision/essential.h>

The fundamental matrix [#!Luong:Faugeras:IJCV96!#] encodes all the geometrical constraints available given two images of a rigid scene. Given two images with point locations ${\bf x}_1=(x_1\;y_1\;z_h)^{\top}$ and ${\bf x}_2=(x_2\;y_2\;z_h)^{\top}$ in homogeneous coordinates, the relationship between image points projected from the same scene point is

$${\bf x}_2^{\top}F {\bf x}_1 = 0$$

$F$ is the $3\times 3$ fundamental matrix. To compute $F$ you can use multiple point matches to solve the above homogeneous linear equations. The standard technique is to use pre-conditioning followed by symmetric matrix eigendecomposition to solve for the nine elements of $F$ up to an undetermined scale factor.

      Gan_SymMatEigenStruct SymEigen;
      Gan_Vector3 *av3Point1, *av3Point2; /* arrays of image points */
      Gan_Matrix33 m33F;

      /* allocate arrays of image coordinates, one array for each image */
      av3Point1 = gan_malloc_array ( Gan_Vector3, 100 );
      av3Point2 = gan_malloc_array ( Gan_Vector3, 100 );

      /* ... fill arrays av3Point1 and av3Point2 with point correspondence
             data for 100 points ... */

      /* create structure for computing eigenvalues and eigenvectors,
         initialising accumulated matrix S (here 9x9) to zero */
      gan_symeigen_form ( &SymEigen, 9 );

      /* solve for fundamental matrix */
      gan_fundamental_matrix_fit ( av3Point1, av3Point2, 100, &SymEigen, &m33F );

      /* free stuff */
      gan_symeigen_free ( &SymEigen );
      gan_free_va ( av3Point2, av3Point1, NULL );

The essential matrix $E$ is the equivalent of the fundamental matrix in the case of known camera calibration parameters. In this case the rotation between the cameras can be computed, and also the translation vector between them up to an unknown scale factor. The mathematical model is that the images are related by the equation

$${{\bf x}_2'}^{\top}E {\bf x}_1' = 0$$

involving the essential matrix $E$, where ${\bf x}_1'$, ${\bf x}_2'$ are ideal image coordinates for images 1 & 2, transformed from the original image coordinates ${\bf x}_1$, ${\bf x}_2$ so that ${\bf x}_1'$ and ${\bf x}_2'$ are the projected coordinates for an ideal camera, which is to say a linear camera with focal distances $f_x=f_y=1$, image centre $x_0=y_0=0$, and homogeneous $z$-coordinate $z_h=1$. The camera calibration matrix for an ideal camera is $K=I_{3\times 3}$. This means that the 3D camera coordinate frame can be identified with the ideal image frame (up to scale as usual). The essential matrix can be written as

$$E = R[{\bf T}]_\times$$

where $R$ is the rotation matrix, ${\bf T}$ is the translation vector between the camera positions and $[{\bf T}]_\times$ is the ``cross product matrix'' of ${\bf T}$, defined as

$${\bf T}= \left(\!\!\begin{array}{c} T_X \ T_Y \ T_Z \end{ar... ... \ T_Z & 0 & -T_X \\ -T_Y & T_X & 0 \end{array}\!\!\right).$$

It is termed the cross product matrix because given any 3-vectors ${\bf x}$ and ${\bf y}$, $[{\bf x}]_\times {\bf y}= {\bf x}\times {\bf y}$. For more details of the essential matrix see [#!Faugeras:93!#].

The main difference in Gandalf between computing the fundamental and essential matrices is in the computation of the ideal image coordinates. These can be computed by back-projecting the original image coordinates out into 3D camera (ideal image) coordinates, using the Gandalf back-projection function described in Section 5.1. Here is a code fragment to compute the essential matrix, represented by the rotation $R$ and translation ${\bf T}$.

      Gan_SymMatEigenStruct SymEigen;
      Gan_Vector3 *av3Point1, *av3Point2; /* arrays of image points */
      Gan_Camera Camera;
      Gan_Euclid3D Pose;

      /* allocate arrays of image coordinates, one array for each image */
      av3Point1 = gan_malloc_array ( Gan_Vector3, 100 );
      av3Point2 = gan_malloc_array ( Gan_Vector3, 100 );

      /* ... fill arrays av3Point1 and av3Point2 with point correspondence
             data for 100 points ... */

      /* build a camera with two radial distortion parameters */
      gan_camera_build_radial_distortion_2 ( &Camera,
                                             100.0, 700.0, 500.0, 150.0, 100.0,
                                             0.001, 1.0e-7 );
      
      /* create structure for computing eigenvalues and eigenvectors,
         initialising accumulated matrix S (here 9x9) to zero */
      gan_symeigen_form ( &SymEigen, 9 );

      /* compute essential matrix */
      gan_essential_matrix_fit ( av3Point1, av3Point2, 100, &Camera, &Camera,
                                 &SymEigen, &Pose );

      /* free stuff */
      gan_symeigen_free ( &SymEigen );
      gan_free_va ( av3Point2, av3Point1, NULL );

The Gandalf 3D Euclidean transformation structure Gan_Euclid3D is used to store the result rotation and translation.

Error detection: Both fundamental and essential matrix routines return a boolean value, which is GAN_FALSE on error, invoking the Gandalf error handler.