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.

Inliers are selected using Rousseeuw reweighting by default, this uses the median value to derive a normal distribution. Alternatively, N-best error fraction can be used to define the inlier set.

  • 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
      how many points it samples to generate a model from

    • 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 final List<Point> inlierSet

    • inlierFraction

      protected double inlierFraction
      Fraction of samples which will be considered an inlier. <= 0 disables it

    • inlierRouseeuwSigma

      protected double inlierRouseeuwSigma
      Computes an inlier threshold by assuming the distribution is normal. Sigma defines the number of stdev the error can be for it to be an inlier. If inlier fraction is specified it will take precedence.

    • inlierThreshold

      protected double inlierThreshold
      Largest error an inlier can have. With inlierRouseeuwSigma it's the computed threshold. With inlierFraction or too few points to estimate sigma, it's the error of the worst inlier and points with an identical error might have been excluded. NaN until process() has been called.

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

    • 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

    • setInlierFraction

      public void setInlierFraction(double inlierFraction)
      Fraction of samples which will be considered an inlier. <= 0 disables it

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

    • computeInliers

      protected void computeInliers(List<Point> dataSet, int N, LeastMedianOfSquares<Model,Point>.TrialHelper helper)
      Computes the inlier set for the best model using inlierFraction or inlierRouseeuwSigma

    • computeInliersFromFraction

      protected void computeInliersFromFraction(List<Point> dataSet, int n, LeastMedianOfSquares<Model,Point>.TrialHelper helper)
      Selects the inlierFraction of points with the smallest error. Assumes errors have been computed.

    • selectSmallestErrors

      protected void selectSmallestErrors(List<Point> dataSet, int n, int numPts, LeastMedianOfSquares<Model,Point>.TrialHelper helper)
      Adds the numPts points with the smallest errors to the inlier set and sets the threshold to the largest error

    • computeInliersFromSigma

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

      Computes inlier using Rousseeuw's reweighting. Assumes errors have been computed.

      Rousseeuw and Leroy, "Robust Regression and Outlier Detection", 1987

    • selectThresholdIndex

      protected static int selectThresholdIndex(int N, double fraction)
      Index of the element at the specified fraction. Clamped so it's always a valid index

    • 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()
      Returns the inlier set. If inlierFraction > 0 then it's that fraction of points with the smallest error, otherwise it's found using Rousseeuw's reweighting and inlierRouseeuwSigma.
      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>