next up previous
Next: Mismatches Up: No Title Previous: Example 2 -

Computing F: II Least Squares Solutions

Given n corresponding points (n is typically hundreds) --- inevitably the points will be `` noisy'' and there will be mis-matches (outliers).

Linear solution --- ``The 8-point Algorithm''

This equation will not be satisfied exactly (for n > 8). A solution is obtained by:

This is a standard linear algebra problem, the solution is the eigenvector with minimum eigenvalue of .

This computation is generally poorly conditioned, and it is very important to pre-condition the matrix: i.e. (affine) transform the image points:

where and are matrices, such that

and < > indicates averages. A fundamental matrix is then computed from the transformed points and obtained by

Pre-conditioning can make a difference of an order of magnitude to the average distance of a point from its epipolar lines (e.g. reduce an average of 3.5 to 0.3 pixels) and hundreds of pixels in the position of the epipoles.

Non-linear solution

Minimise (average) squared perpendicular distance of points from their epipolar lines:


Use Levenberg-Marquardt or Powell for non-linear optimisation.

Summary Point

Bob Fisher
Wed Apr 16 00:58:54 BST 1997