Package org.ddogleg.fitting.modelset.ransac

Class Ransac<Model,Point>

java.lang.Object
org.ddogleg.fitting.modelset.ransac.Ransac<Model,Point>
All Implemented Interfaces:
InlierThreshold, ModelMatcher<Model,Point>, ModelMatcherPost<Model,Point>
Direct Known Subclasses:
Ransac_MT
public class Ransac<Model,Point> extends Object implements ModelMatcherPost<Model,Point>, InlierThreshold

RANSAC is an abbreviation for "RANdom SAmple Consensus" and is an iterative algorithm. The model with the largest set of inliers is found by randomly sampling the set of points and fitting a model. The algorithm terminates when the maximum number of iterations has been reached. An inlier is defined as a point which has an error less than a user specified threshold to the estimated model being considered. The algorithm was first published by Fischler and Bolles in 1981."

Sample Points: By default the minimum number of points are sampled. The user to override this default and set it to any number.

  • Field Details

    • sampleSize

      protected int sampleSize

    • thresholdFit

      protected double thresholdFit

    • masterModelManager

      protected ModelManager<Model> masterModelManager

    • randSeed

      protected long randSeed

    • trialRNG

      protected final FastArray<Random> trialRNG

    • maxIterations

      protected int maxIterations

    • helper

      @Nullable protected Ransac<Model,Point>.@Nullable TrialHelper helper

    • initializeModels

      @Nullable protected @Nullable Ransac.InitializeModels<Model,Point> initializeModels
      Optional function for initializing generator and distance functions

  • Constructor Details

    • Ransac

      public Ransac(long randSeed, int maxIterations, double thresholdFit, ModelManager<Model> modelManager, Class<Point> pointType)
      Creates a new instance of the ransac algorithm. The number of points sampled will default to the minimum number. To override this default invoke setSampleSize(int).
      Parameters:
      randSeed - The random seed used by the random number generator.
      maxIterations - The maximum number of iterations the RANSAC algorithm will perform.
      thresholdFit - How close of a fit a points needs to be to the model to be considered a fit.

  • Method Details

    • process

      public boolean process(List<Point> dataSet)
      Description copied from interface: ModelMatcher
      Finds a set of points from the provided list that are a good fit for the internal model and computes the fit parameters for the model.
      Specified by:
      process in interface ModelMatcher<Model,Point>
      Parameters:
      dataSet - Set of points (with noise) that are to be fit.
      Returns:
      true if it successfully found a solution or false if not.

    • setModel

      public void setModel(Factory<ModelGenerator<Model,Point>> factoryGenerator, Factory<DistanceFromModel<Model,Point>> factoryDistance)
      Description copied from interface: ModelMatcherPost
      Specifies the internal model. Factories are provided since each thread might need its own unique instance of the generator and distance function if they are not thread safe.
      Specified by:
      setModel in interface ModelMatcherPost<Model,Point>
      Parameters:
      factoryGenerator - ModelGenerator
      factoryDistance - DistanceFromModel

    • checkTrialGenerators

      protected void checkTrialGenerators()
      If the maximum number of iterations has changed then re-generate the RNG for each trial

    • randomDraw

      public static <T> void randomDraw(List<T> dataSet, int numSample, List<T> initialSample, Random rand)
      Performs a random draw in the dataSet. When an element is selected it is moved to the end of the list so that it can't be selected again.
      Parameters:
      dataSet - List that points are to be selected from. Modified.

    • randomDraw

      public static void randomDraw(DogArray_I32 indexes, int size, int numSample, Random rand)
      Randomly selects a set of points in indexes. The selects points are put at the end of the array

    • addSelect

      public static <T> void addSelect(DogArray_I32 indexes, int numSample, List<T> dataSet, List<T> initialSample)
      Adds the selected elements to the initialSample list and undoes the shuffling. There is probably a slightly more elegant way to do this...

    • getMatchSet

      public List<Point> getMatchSet()
      Description copied from interface: ModelMatcher
      A set of points which match the provided parameters.
      Specified by:
      getMatchSet in interface ModelMatcher<Model,Point>
      Returns:
      List of points in the match set.

    • getInputIndex

      public int getInputIndex(int matchIndex)
      Description copied from interface: ModelMatcher
      For an item in the match set, return the index of the item in the original input set.
      Specified by:
      getInputIndex in interface ModelMatcher<Model,Point>
      Parameters:
      matchIndex - Index of an element in the match set.
      Returns:
      Index of the same element in the original input list.

    • getModelParameters

      public Model getModelParameters()
      Description copied from interface: ModelMatcher
      Model for the match set
      Specified by:
      getModelParameters in interface ModelMatcher<Model,Point>
      Returns:
      model.

    • getFitQuality

      public double getFitQuality()
      Description copied from interface: ModelMatcher
      Returns the metric used to evaluate the quality of fit. Meaning is implementation specific. Larger or smaller values could be preferred depending on implementation..
      Specified by:
      getFitQuality in interface ModelMatcher<Model,Point>
      Returns:
      Quality of fit to matched set of points

    • getMaxIterations

      public int getMaxIterations()

    • setMaxIterations

      public void setMaxIterations(int maxIterations)

    • getMinimumSize

      public int getMinimumSize()
      Description copied from interface: ModelMatcher
      This is the minimum number of observations which can be input and produce a valid model.
      Specified by:
      getMinimumSize in interface ModelMatcher<Model,Point>
      Returns:
      Minimum number of sample points

    • reset

      public void reset()
      Description copied from interface: ModelMatcher
      Resets the model matcher to its original state. This means that given identical inputs it would produce the same outputs
      Specified by:
      reset in interface ModelMatcher<Model,Point>

    • setSampleSize

      public void setSampleSize(int sampleSize)
      Override the number of points that are sampled and used to generate models. If this value is not set it defaults to the minimum number.
      Parameters:
      sampleSize - Number of sample points.

    • getThresholdFit

      public double getThresholdFit()
      Description copied from interface: InlierThreshold
      Returns the inlier threshold
      Specified by:
      getThresholdFit in interface InlierThreshold

    • setThresholdFit

      public void setThresholdFit(double thresholdFit)
      Description copied from interface: InlierThreshold
      Specifies the "fit" criteria for inlier set as being equal to or less than this
      Specified by:
      setThresholdFit in interface InlierThreshold
      Parameters:
      thresholdFit - inlier threshold

    • getPointType

      public Class<Point> getPointType()
      Description copied from interface: ModelMatcher
      Returns a class for the input point object
      Specified by:
      getPointType in interface ModelMatcher<Model,Point>

    • getModelType

      public Class<Model> getModelType()
      Description copied from interface: ModelMatcher
      Returns a class for the input point object
      Specified by:
      getModelType in interface ModelMatcher<Model,Point>