Computation of the Fundamental Matrix


The fundamental matrix F relates points in two images. If x is a point in one image and x' a point in another image, then  x'Fx = 0. To compute F completely automatically we begin by using a corner detector to find interest points in an image.
 
Feature points extracted by a corner detector.

Putative matches of the feature points in both images are computed by using a correlation measure for points in one image with a features in the other image. Only features within a small window are considered to limit computation time. Mutually best matches are retained.

RANSAC is used to robustly determine F from these putative matches. A minimal sample is selected from the putative matches from which a tentative F is calculated. The process is iterated until a sufficient number of samples have been taken. The F which fits the matches the becomes the input for the next step.
 
Putative matches. Cyan lines indicate outliers rejected by RANSAC.

Once an initial F has been computed, more matches can be found by searching along epipolar lines. A non-linear minimization is used to fit an F to a large number of points.
 
 
Additional matches found by searching along epipolar lines and iteratively improving the F matrix.

The following parameters were used for these images:

Putative match neighborhood: 15 pixels
Putative match search window: 100 pixels
Putative match correlation threshold: 0.8
Putative matches: 270
RANSAC iterations: 19
Inliers found: 224
Residual error after RANSAC: 1.057
Guided matching neighborhood: 25 pixels
Matches found after iterative improvement: 297
Residual error after iterative improvement: 0.497
Iterations: 4
 
 

Here are the result for some more images.
 
Putative matches

 
Final matches and epipolar lines

Putative match neighborhood: 15 pixels
Putative match search window: 100 pixels
Putative match correlation threshold: 0.8
Putative matches: 239
RANSAC iterations: 25
Inliers found: 163
Residual error after RANSAC: 0.764
Guided matching neighborhood: 25 pixels
Matches found after iterative improvement: 270
Residual error after iterative improvement: 0.541
Iterations: 5
 
 
 
 
Putative matches
Final matches and epipolar lines.

Putative match neighborhood: 15 pixels
Putative match search window: 100 pixels
Putative match correlation threshold: 0.8
Putative matches: 210
RANSAC iterations: 24
Inliers found: 169
Residual error after RANSAC: 1.077
Guided matching neighborhood: 25 pixels
Matches found after iterative improvement: 180
Residual error after iterative improvement: 0.454
Iterations: 4
 
 

Experiments

The size of the matching neigborhood has a significant impact on the quality of the putative matches. If the window is made very large, say on the order of 50 pixels, almost all of the putative matches will be inliers. In general, I used a larger neighborhood with guided matching because the search area was more restricted.

I tried to use images with a larger baseline. This required enlarging the putative match search window quite a bit. The size of the window greatly affects the time it takes to compute the matches. RANSAC seemed to produce acceptable results but the guided matching actually yielded fewer matches. The non-linear minimization seemed to drift which led to fewer matches which, in turn, led to further drift. I had a problem with drift when enlarging the valid distance from the epipolar line for the guided matching.

I was unable to use a much smaller window for putative matches because the baseline is rather large in the images I captured. All of the images used here are adjacent in a sequence of images. I should have taken them closer together.

I tried both the 7-point and the 8-point algorithm for calculating F in RANSAC. I found that 8 point algorithm seemed to produce better results on average. The 8-point algorithm required about the same number of iterations as the 7-point algorithm because I adaptively determined the number of samples to take. Since the 8-point algorithm produced good results RANSAC quickly converged with a small number of samples.

 

Source code

The main script is computeF.m. Look at the top of computeF to see what variables to set before running the script (they are set to defaults). There are several scripts to generate the images in this write-up. These need to be run after computeF.m because they assume the existence of several variable. Viewer.m is one of these scripts. Clicking in the first window shows the epipolar lines corresponding to the clicked point. Right click to exit the viewer.

Source code (10 K)
Sample Images (812K)