Package org.ddogleg.fitting.modelset.lmeds

Class LeastMedianOfSquares<Model,Point>

java.lang.Object
org.ddogleg.fitting.modelset.lmeds.LeastMedianOfSquares<Model,Point>
All Implemented Interfaces:
InlierFraction, ModelMatcher<Model,Point>, ModelMatcherPost<Model,Point>
Direct Known Subclasses:
LeastMedianOfSquares_MT
public class LeastMedianOfSquares<Model,Point> extends Object implements ModelMatcherPost<Model,Point>, InlierFraction

Another technique similar to RANSAC known as Least Median of Squares (LMedS). For each iteration a small number N points are selected. A model is fit to these points and then the error is computed for the whole set. The model which minimizes the median is selected as the final model. No pruning or formal selection of inlier set is done.

  • Field Details

    • trialRNG

      protected final FastArray<Random> trialRNG

    • totalCycles

      protected final int totalCycles
      number of times it performs its fit cycle

    • sampleSize

      protected int sampleSize

    • maxMedianError

      protected final double maxMedianError

    • ModelManager

      protected final ModelManager<Model> ModelManager

    • matchToInput

      protected int[] matchToInput

    • bestMedian

      protected volatile double bestMedian

    • errorFraction

      protected double errorFraction

    • inlierSet

      protected List<Point> inlierSet

    • inlierFrac

      protected final double inlierFrac

    • helper

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

    • initializeModels

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

  • Constructor Details

    • LeastMedianOfSquares

      public LeastMedianOfSquares(long randSeed, int totalCycles, double maxMedianError, double inlierFraction, ModelManager<Model> modelManager, Class<Point> pointType)
      Configures the algorithm.
      Parameters:
      randSeed - Random seed used internally.
      totalCycles - Number of random draws it will make when estimating model parameters.
      maxMedianError - If the best median error is larger than this it is considered a failure.
      inlierFraction - Data which is this fraction or lower is considered an inlier and used to recompute model parameters at the end. Set to 0 to turn off. Domain: 0 to 1.

    • LeastMedianOfSquares

      public LeastMedianOfSquares(long randSeed, int totalCycles, ModelManager<Model> modelManager, Class<Point> pointType)
      Configures the algorithm.
      Parameters:
      randSeed - Random seed used internally.
      totalCycles - Number of random draws it will make when estimating model parameters.

  • Method Details

    • 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

    • setSampleSize

      public void setSampleSize(int sampleSize)
      Number of points it samples to compute a model from. Typically this is the minimum number of points needed.
      Parameters:
      sampleSize - Number of points sampled when computing the model.

    • 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.

    • computeInlierSet

      protected void computeInlierSet(List<Point> dataSet, int n, LeastMedianOfSquares<Model,Point>.TrialHelper helper)

    • checkTrialGenerators

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

    • getErrorFraction

      public double getErrorFraction()
      Description copied from interface: InlierFraction
      Gets the inlier set's fractional value
      Specified by:
      getErrorFraction in interface InlierFraction

    • setErrorFraction

      public void setErrorFraction(double errorFraction)
      Description copied from interface: InlierFraction
      Specifies the inlier set as a fraction
      Specified by:
      setErrorFraction in interface InlierFraction
      Parameters:
      errorFraction - inlier threshold. Must be from 0 to 1, inclusive.

    • getModelParameters

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

    • getMatchSet

      public List<Point> getMatchSet()
      If configured to computer the inlier set it returns the computed inliers. Otherwise it returns the data set orginally passed in.
      Specified by:
      getMatchSet in interface ModelMatcher<Model,Point>
      Returns:
      Set of points that are inliers to the returned model parameters..

    • 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.

    • getFitQuality

      public double getFitQuality()
      Value of the best median error.
      Specified by:
      getFitQuality in interface ModelMatcher<Model,Point>
      Returns:
      Quality of fit to matched set of points

    • 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>

    • 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>