Epipolar Geometry

Students should work on this lab exercise in groups of two people. In this assignment you will write a function that takes two images as input and computes fundamental matrix by Normalized Eight-point Algorithm with RANSAC 1.3. You will work with supplied teddy bear (obj02 001.jpg, obj02

002.jpg).

1 Fundamental Matrix Estimation

Please consult the lecture slides for the definition of the fundamental matrix and Epipolar geometry and the following papers [1, 2]. The overall scheme can be summarized as follows:

1. Detect interest points in each image.
2. Describe the local appearance of the regions around interest points.
3. Get a set of supposed matches between region descriptors in each image and select 20 correspondences from them. Remember that matched points are needed to be well distributed on the images for an accurate estimation of the fundamental matrix.
4. Estimate the fundamental matrix for the given two images.

The first two steps can be performed using Harris/Hessian Affine implementation which can be downloaded from http://www.robots.ox.ac.uk/ _~vgg/research/affine/detectors.html. Third step can be performed using vl feat functions:

Note: Eliminate detected interest points on background. In the next stage, for given n < 8 known corresponding points pairs in stereo images, we can formulate a homogenous linear equation as follows:

, (1)

where x_i and y_i denote x and y coordinates of the i^th point p_i, respectively.

Equation 1 can also be written as

f₁₁

f21

| {z }f13

A

f23 f33

where F denotes the fundamental matrix.

2 Eight-point Algorithm

• Construct the n 9 matrix A
• Find the SVD of A : A = UDV ^T
• The entries of F are the components of the column of V corresponding to the smallest singular value.

Estimated fundamental matrix F is almost always non-singular (read pages 215 221 from Forsyth & Ponce book for further details). The singularity of fundamental matrix is enforced by adjusting the entries of estimated F:

• Find the SVD of F : F = U_fD_fV_f^T
• Set the smallest singular value in the diagonal matrix D_f to zero in order to obtain the corrected matrix D_f
• Recompute

3 Normalized Eight-point Algorithm

It turns out that a careful normalization of the input data (the point correspondences) leads to an enormous improvement in the conditioning of the problem, and hence in the stability of the result. The added complexity necessary for this transformation is insignificant.

3.1 Normalization:

We want to apply a similarity transformation to the set of points p_i so that their mean is 0 and the average distance to the mean is 2.

Let,

and , where x_i and y_i denote x and y

coordinates of a point p_i, respectively.

Then p_i = Tp_i. Check and show that the set of points p_i satisfies our criteria.

Similarly, define a transformation T using the set {p_i}, and let .

3.2 Find a fundamental matrix:

• Construct a matrix A from the matches p_i ↔ p_i⁰ and get F from the last column of V in the SVD of A
• Find the SVD of
• Set the smallest singular value in the diagonal matrix D_F to zero in order to obtain the corrected matrix
• Recompute

3.3 Denormalization:

Finally, let F = T^TFT .

4 Normalized Eight-point Algorithm with RANSAC

Fundamental matrix estimation step given in Section 3.2 can also be performed via a RANSAC-based approach. First pick 8 point correspondences randomly from the set {p_i ↔ p_i⁰}, then, calculate a fundamental matrix F⁰, and count the number of inliers (the other correspondences that agree with this fundamental matrix). Repeat this process many times, pick the largest set of inliers obtained, and apply fundamental matrix estimation step given in Section 3.2 to the set of all inliers.

In order to determine whether a match p_i ↔ p_i⁰ agrees with a fundamental matrix F, we typically use the Sampson distance as follows:

, (3)

where (Fp)²_j is the square of the j^th entry of the vector Fp. If d_i is smaller than some threshold, the match is said to be an inlier.

5 Outputs

The example of the images that you can plot for these assignment are provided in Fig. 1.

Figure 1: Feature matching and Epipolar lines for the teddy bear image example

Moreover, since the rest of the project needs many point matches on 20 images, you can start to find more point correspondences on different image pairs of the teddy-bear.

References

• Richard I. Hartley. In Defence of the Eight-Point Algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, June 1997.
• Fred Rothganger, Svetlana Lazebnik, Cordelia Schmid, Jean Ponce.3D Object Modeling and Recognition Using Local Affine-Invariant Image Descriptors and Multi-View Spatial Constraints. International Journal of Computer Vision, March 2006.