Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

RANSAC Algorithm

Can anybody please show me how to use RANSAC algorithm to select common feature points in two images which have a certain portion of overlap? The problem came out from feature based image stitching.
alt textalt text

like image 809
view Avatar asked Jan 11 '11 07:01

view


People also ask

What does RANSAC algorithm do?

Random sample consensus, or RANSAC, is an iterative method for estimating a mathematical model from a data set that contains outliers. The RANSAC algorithm works by identifying the outliers in a data set and estimating the desired model using data that does not contain outliers.

What does RANSAC stand for?

Abbreviation of random sample consensus., an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers.

How does RANSAC help curve fitting?

The RANSAC algorithm creates a fit from a small sample of points but tries to maximize the number of inlier points. Lowering the maximum distance helps to improve the polynomial fit by putting a tighter tolerance on inlier points.


1 Answers

I implemented a image stitcher a couple of years back. The article on RANSAC on Wikipedia describes the general algortihm well.

When using RANSAC for feature based image matching, what you want is to find the transform that best transforms the first image to the second image. This would be the model described in the wikipedia article.

If you have already got your features for both images and have found which features in the first image best matches which features in the second image, RANSAC would be used something like this.

The input to the algorithm is:
n - the number of random points to pick every iteration in order to create the transform. I chose n = 3 in my implementation.
k - the number of iterations to run
t - the threshold for the square distance for a point to be considered as a match
d - the number of points that need to be matched for the transform to be valid
image1_points and image2_points - two arrays of the same size with points. Assumes that image1_points[x] is best mapped to image2_points[x] accodring to the computed features.

best_model = null
best_error = Inf
for i = 0:k
  rand_indices = n random integers from 0:num_points
  base_points = image1_points[rand_indices]
  input_points = image2_points[rand_indices] 
  maybe_model = find best transform from input_points -> base_points

  consensus_set = 0
  total_error = 0
  for i = 0:num_points
    error = square distance of the difference between image2_points[i] transformed by maybe_model and image1_points[i]
    if error < t
      consensus_set += 1
      total_error += error

  if consensus_set > d && total_error < best_error
    best_model = maybe_model
    best_error = total_error

The end result is the transform that best tranforms the points in image2 to image1, which is exacly what you want when stitching.

like image 140
erik Avatar answered Dec 10 '22 04:12

erik