ComputerVision Lab 5- Epipolar Geometry Solved

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:

1
[x, y, a, b, c, desc ] = ./ extract features -haraff -i ...

img.png -sift
2
[matches, scores] = vl ubcmatch (desc1 , desc2)
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 xi and yi denote x and y coordinates of the ith point pi, respectively.

Equation 1 can also be written as

f11

 
x1y10

...

xnyn0
x1

...

xn
y1x01

...

ynx0n
y1y10

...

ynyn0
y1

...

yn
x01

...

x0n
y10

...

yn0
 ,
(2)
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 = UfDfVfT

•    Set the smallest singular value in the diagonal matrix Df to zero in order to obtain the corrected matrix Df

•    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√        pi so that their mean is 0 and the average distance to the mean is  2.

Let ,

and   , where xi and yi denote x and y

coordinates of a point pi, respectively.

Then ˆpi = Tpi. Check and show that the set of points ˆpi 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 ˆpi ↔ pˆi0 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 DFˆ to zero in order to obtain the corrected matrix 

•    Recompute  

3.3       Denormalization:

Finally, let F = TTFTˆ .

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ˆi0}, then, calculate a fundamental matrix Fˆ0, 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 ˆpi ↔ pˆi0 agrees with a fundamental matrix F, we typically use the Sampson distance as follows:

                                       ,                         (3)

where (Fp)2j is the square of the jth entry of the vector Fp. If di 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
[1]  Richard I. Hartley. ”In Defence of the Eight-Point Algorithm”. IEEE Transactions on Pattern Analysis and Machine Intelligence, June 1997.

[2]  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.