Overview

RANSAC holds the assumption that some so called inliers are presented in the data, whose distribution/pattern can be explained by model parameters. In contrast, outlier consist of noise, and can be rejected in the selection process. This method does not gauarantee good result, but increased probability of getting one with more iteration. In practice, a metric would use to determine whether a point is a inlier or not, and a model would be updated if number of inliers is greater than the yet best estimated model.

Application in Homography

The 3x3 homography matrix can be estimated by 4 pair of matched points, since we operate in homogeneous coordinate and we simply drop z i.e. there’s only 8 elements to estimate. The 8 equations can be reformed as a standard Ah = 0 format, with A having shape 8x8 and h 8x1. The answer to h can be estimated by the smallest eigenvector of SVD, which is equivalent to least square fitting (Ideally the corresponding eigenvalue should be zero and send h into Null space of A). The RANSAC will select 4 matches and determine whether a match is inliner based on pixel-to-pixel distance, which is computed by dist(p1 - (HT * p2)/p2.z). Note that since we enforce z = 1 (abitrarily), HT * p2 needs to be divided by p2.z to fall on the image plane where p1 = [x1,y1,1] lies.

Remarks

1. This method would not hold if there’s a constant bias presented i.e. no inlier, or when there’s non-negligible noise impose on all data.
2. This method also require strong prior of the model. Estimating a plane may be a non-trival task – perhaps except for estimating the ground plane – e.g. given a rectangular box, the smaller faces are much harder to estimate as their estimation could be easily interfered by the points of the larger faces. This example illustrates that RANSAC may not be suitable when there’s multiple close candidates available.

Extension Question

How to update model during the iteration?