An Effective Rigidity Constraint for Improving RANSAC in Homography Estimation - Advanced Concepts for Intelligent Vision Systems - page 205

Algorithm 1. RANSAC algorithm for homography estimation
number_of_iterations := 0;
inliers := {};
H := {};

repeat
random_sample := four randomly-selected correspondences;

if (is_not_degenerated(random_sample))
begin
current_H := homography_processed_from(random_sample);
current_inliers := putative correspondences matching H;
if (number_of(current_inliers) > number_of(inliers))
begin
inliers := current_inliers;
H := current_H;
end
end
number_of_iterations := number_of_iterations + 1;
until (number_of_iterations > max_number_of_iterations)

return (inliers,H);

2.2 RANSAC in Homography Estimation

The Random Sample Consensus algorithm, or RANSAC, is an iterative method
of estimating the parameters of a mathematical model from sample data con-
taining both inliers and outliers, with the ability to simultaneously sort out the
inliers from the outliers according to the estimated model [1]. This algorithm,
described in Algorithm 1, is commonly used for homography estimation in im-
age registration tasks. For this purpose, it starts with a putative set of point
correspondences from two different images. Samples of four point correspon-
dences are then iteratively evaluated by first processing a homography using
the four correspondences and then by checking the consistency of all the pu-
tative correspondences with respect to this homography. The consistency of a
correspondence with a given homography can be evaluated using different error
measurement methods [3] such as, for example, the symmetric transfer function:

d p, H − 1 · p 2

2 .

p ,H = + d ( · p ) (7)

The process ends after a number of iterations which is interactively re-evaluated
with respect to the largest current number of inliers [3]. The literature recom-
mends that degenerated samples containing three collinear points should not
be evaluated, as it leads to under-determined systems of equations [2,3]. An-
other current advice is to prefer samples with a good spatial distribution over
the images. If the first advice definitely makes sense, the second one is more
dicult to follow in the case of images with very little overlapping where the
inliers are concentrated in regions much smaller than the size of images. Even