Package com.irurueta.numerical.robust

Class PROSACRobustEstimator<T>

java.lang.Object
com.irurueta.numerical.robust.RobustEstimator<T>
com.irurueta.numerical.robust.PROSACRobustEstimator<T>
Type Parameters:
T - type of object to be estimated.
public class PROSACRobustEstimator<T> extends RobustEstimator<T>
This class implements PROSAC (PROgressive random SAmple Consensus) algorithm to robustly estimate a data model. This algorithm is an improvement over RANSAC that can be used whenever a certain measure of quality is known for each sample of data. The measure of quality does not need to be precise, only needs to give a certain idea whether a given sample is likely to be better than another one (by having a higher quality score). Whenever RANSAC is being used but quality of measures is known, PROSAC should be used instead, since this algorithm offers a result with a comparable precision to that obtained with RANSAC but having a much smaller computational cost. The large improvement in computational cost is achieved thanks to the fact that by taking into account the quality measures, sub-samples can be prioritized so that more likely to be inliers are picked first.

This implementation is based on: http://devernay.free.fr/vision/src/prosac.c

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    PROSACRobustEstimator.PROSACInliersData
    Contains data related to estimated inliers.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private PROSACRobustEstimator.PROSACInliersData
    bestInliersData
    Data related to inliers found for best result.
    private T
    bestResult
    Best solution that has been found so far during an estimation.
    private double
    beta
    beta is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface.
    static final double
    CHI_SQUARED
    Chi squared.
    private boolean
    computeAndKeepInliers
    Indicates whether inliers must be computed and kept.
    private boolean
    computeAndKeepResiduals
    Indicates whether residuals must be computed and kept.
    private double
    confidence
    Amount of confidence expressed as a value between 0 and 1.0 (which is equivalent to 100%).
    static final double
    DEFAULT_BETA
    Defines the default value for beta, which is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface.
    static final boolean
    DEFAULT_COMPUTE_AND_KEEP_INLIERS
    Indicates that by default inliers will only be computed but not kept.
    static final boolean
    DEFAULT_COMPUTE_AND_KEEP_RESIDUALS
    Indicates that by default residuals will only be computed but not kept.
    static final double
    DEFAULT_CONFIDENCE
    Constant defining default confidence of the estimated result, which is 99%.
    static final double
    DEFAULT_ETA0
    Defines the default value for the maximum probability that a solution with more than inliersNStar in U_nStar exist and was not found after k samples.
    static final int
    DEFAULT_MAX_ITERATIONS
    Default maximum allowed number of iterations.
    static final double
    DEFAULT_MAX_OUTLIERS_PROPORTION
    Default maximum allowed outliers proportion in the input data.
    private double
    eta0
    eta0 is the maximum probability that a solution with more than inliersNStar inliers in U_nStar exists and was not found after k samples (typically set to 5%).
    static final double
    MAX_BETA
    Maximum allowed value for beta.
    static final double
    MAX_CONFIDENCE
    Maximum allowed confidence value.
    static final double
    MAX_ETA0
    Maximum allowed value for eta0.
    static final double
    MAX_MAX_OUTLIERS_PROPORTION
    Maximum allowed value for maximum allowed outliers proportion in the input data
    private int
    maxIterations
    Maximum allowed number of iterations.
    private double
    maxOutliersProportion
    In this implementation, PROSAC won't stop before having reached the corresponding inliers rate on the complete data set.
    static final double
    MIN_BETA
    Minimum allowed value for beta.
    static final double
    MIN_CONFIDENCE
    Minimum allowed confidence value.
    static final double
    MIN_ETA0
    Minimum allowed value for eta0.
    static final int
    MIN_ITERATIONS
    Minimum allowed number of iterations.
    static final double
    MIN_MAX_OUTLIERS_PROPORTION
    Minimum allowed value for maximum allowed outliers proportion in the input data.
    static final double
    MIN_THRESHOLD
    Minimum allowed threshold to determine inliers.
    private int
    nIters
    Number of iterations to be done to obtain required confidence.
    private SubsetSelector
    subsetSelector
    Instance in charge of picking random subsets of samples.

    Fields inherited from class com.irurueta.numerical.robust.RobustEstimator

    DEFAULT_PROGRESS_DELTA, listener, locked, MAX_PROGRESS_DELTA, MIN_PROGRESS_DELTA, progressDelta

  • Constructor Summary

    Constructors
    Constructor
    Description
    PROSACRobustEstimator()
    Constructor.
    PROSACRobustEstimator(PROSACRobustEstimatorListener<T> listener)
    Constructor with listener.

  • Method Summary

    Modifier and Type
    Method
    Description
    private static <T> int
    computeInliers(T iterResult, double threshold, BitSet inliers, int totalSamples, PROSACRobustEstimatorListener<T> listener, double[] residuals)
    Computes inliers data for current iteration.
    private static int
    computeIterations(double probInlier, int subsetSize, double confidence)
    Computes number of required iterations to achieve required confidence with current probability of inlier and sample subset size.
    private static int[]
    computeSortedQualityIndices(double[] qualityScores)
    Obtains indices of samples corresponding to samples ordered in descending quality scores.
    T
    estimate()
    Robustly estimates an instance of T.
    PROSACRobustEstimator.PROSACInliersData
    getBestInliersData()
    Gets data related to inliers found for best result.
    T
    getBestResult()
    Returns best solution that has been found so far during an estimation.
    double
    getBeta()
    Returns beta, which is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface.
    double
    getConfidence()
    Returns amount of confidence expressed as a value between 0 and 1.0 (which is equivalent to 100%).
    double
    getEta0()
    Return eta0, which is the maximum probability that a solution with more than inliersNStar inliers in U_nStar exists and was not found after k samples (typically set to 5%).
    InliersData
    getInliersData()
    Returns data about inliers once estimation has been done.
    int
    getMaxIterations()
    Maximum allowed number of iterations.
    double
    getMaxOutliersProportion()
    Returns maximum allowed outliers proportion in the input data.
    RobustEstimatorMethod
    getMethod()
    Returns method being used for robust estimation.
    int
    getNIters()
    Returns number of iterations to be done to obtain required confidence.
    private static int
    imin(int subsetSize, int sampleSize, double beta)
    Non randomness states that i-m (where i is the cardinal of the set of inliers for a wrong model) follows the binomial distribution B(n,beta).
    boolean
    isComputeAndKeepInliersEnabled()
    Indicates whether inliers must be computed and kept.
    boolean
    isComputeAndKeepResidualsEnabled()
    Indicates whether residuals must be computed and kept.
    boolean
    isReady()
    Indicates if estimator is ready to start the estimation process.
    private static void
    reverse(int[] array)
    Reverses provided array.
    void
    setBeta(double beta)
    Sets beta, which is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface.
    void
    setComputeAndKeepInliersEnabled(boolean computeAndKeepInliers)
    Specifies whether inliers must be computed and kept.
    void
    setComputeAndKeepResidualsEnabled(boolean computeAndKeepResiduals)
    Specifies whether residuals must be computed and kept.
    void
    setConfidence(double confidence)
    Sets amount of confidence expressed as a value between 0 and 1.0 (which is equivalent to 100%).
    void
    setEta0(double eta0)
    Sets eta0, which is the maximum probability that a solution with more than inliersNStar inliers in U_nStar exists and was not found after k samples (typically set to 5%).
    void
    setMaxIterations(int maxIterations)
    Sets maximum allowed number of iterations.
    void
    setMaxOutliersProportion(double maxOutliersProportion)
    Sets maximum allowed outliers proportion in the input data.
    private static void
    transformIndices(int[] subsetIndices, int[] sortedIndices, int[] transformedSubsetIndices)
    Transforms indices picked by the subset selector into the indices where samples are actually localed by taking into account their original position before sorting quality scores.

    Methods inherited from class com.irurueta.numerical.robust.RobustEstimator

    getListener, getProgressDelta, isListenerAvailable, isLocked, setListener, setProgressDelta

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • DEFAULT_CONFIDENCE

      public static final double DEFAULT_CONFIDENCE
      Constant defining default confidence of the estimated result, which is 99%. This means that with a probability of 99% estimation will be accurate because chosen sub-samples will be inliers.
      See Also:

    • DEFAULT_MAX_ITERATIONS

      public static final int DEFAULT_MAX_ITERATIONS
      Default maximum allowed number of iterations.
      See Also:

    • MIN_CONFIDENCE

      public static final double MIN_CONFIDENCE
      Minimum allowed confidence value.
      See Also:

    • MAX_CONFIDENCE

      public static final double MAX_CONFIDENCE
      Maximum allowed confidence value.
      See Also:

    • MIN_ITERATIONS

      public static final int MIN_ITERATIONS
      Minimum allowed number of iterations.
      See Also:

    • MIN_THRESHOLD

      public static final double MIN_THRESHOLD
      Minimum allowed threshold to determine inliers.
      See Also:

    • DEFAULT_MAX_OUTLIERS_PROPORTION

      public static final double DEFAULT_MAX_OUTLIERS_PROPORTION
      Default maximum allowed outliers proportion in the input data. This is used do determine the number of required iterations.
      See Also:

    • MIN_MAX_OUTLIERS_PROPORTION

      public static final double MIN_MAX_OUTLIERS_PROPORTION
      Minimum allowed value for maximum allowed outliers proportion in the input data.
      See Also:

    • MAX_MAX_OUTLIERS_PROPORTION

      public static final double MAX_MAX_OUTLIERS_PROPORTION
      Maximum allowed value for maximum allowed outliers proportion in the input data
      See Also:

    • DEFAULT_ETA0

      public static final double DEFAULT_ETA0
      Defines the default value for the maximum probability that a solution with more than inliersNStar in U_nStar exist and was not found after k samples.
      See Also:

    • MIN_ETA0

      public static final double MIN_ETA0
      Minimum allowed value for eta0.
      See Also:

    • MAX_ETA0

      public static final double MAX_ETA0
      Maximum allowed value for eta0.
      See Also:

    • DEFAULT_BETA

      public static final double DEFAULT_BETA
      Defines the default value for beta, which is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface. The inlier surface is a disc with radius 1.96s for homography/displacement computation, or a band with width 1.96*s*2 for epipolar geometry (s is the detection noise), and the total surface is the surface of the image.
      See Also:

    • MIN_BETA

      public static final double MIN_BETA
      Minimum allowed value for beta.
      See Also:

    • MAX_BETA

      public static final double MAX_BETA
      Maximum allowed value for beta.
      See Also:

    • CHI_SQUARED

      public static final double CHI_SQUARED
      Chi squared.
      See Also:

    • DEFAULT_COMPUTE_AND_KEEP_INLIERS

      public static final boolean DEFAULT_COMPUTE_AND_KEEP_INLIERS
      Indicates that by default inliers will only be computed but not kept.
      See Also:

    • DEFAULT_COMPUTE_AND_KEEP_RESIDUALS

      public static final boolean DEFAULT_COMPUTE_AND_KEEP_RESIDUALS
      Indicates that by default residuals will only be computed but not kept.
      See Also:

    • confidence

      private double confidence
      Amount of confidence expressed as a value between 0 and 1.0 (which is equivalent to 100%). The amount of confidence indicates the probability that the estimated result is correct. Usually this value will be close to 1.0, but not exactly 1.0.

    • maxIterations

      private int maxIterations
      Maximum allowed number of iterations. When the maximum number of iterations is exceeded, result will not be available, however an approximate result will be available for retrieval.

    • maxOutliersProportion

      private double maxOutliersProportion
      In this implementation, PROSAC won't stop before having reached the corresponding inliers rate on the complete data set. Maximum allowed outliers proportion in the input data: used to compute nIters (can be as high as 0.95).

    • eta0

      private double eta0
      eta0 is the maximum probability that a solution with more than inliersNStar inliers in U_nStar exists and was not found after k samples (typically set to 5%).

    • beta

      private double beta
      beta is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface. The inlier surface is a disc with radius 1.96s for homography/displacement computation, or a band with width 1.96s*2 for epipolar geometry (s is the detection noise), and the total surface is the surface of the image YOU MUST ADJUST THIS VALUE, DEPENDING ON YOUR PROBLEM!

    • subsetSelector

      private SubsetSelector subsetSelector
      Instance in charge of picking random subsets of samples.

    • nIters

      private int nIters
      Number of iterations to be done to obtain required confidence.

    • bestResult

      private T bestResult
      Best solution that has been found so far during an estimation.

    • bestInliersData

      private PROSACRobustEstimator.PROSACInliersData bestInliersData
      Data related to inliers found for best result.

    • computeAndKeepInliers

      private boolean computeAndKeepInliers
      Indicates whether inliers must be computed and kept.

    • computeAndKeepResiduals

      private boolean computeAndKeepResiduals
      Indicates whether residuals must be computed and kept.

  • Constructor Details

    • PROSACRobustEstimator

      public PROSACRobustEstimator()
      Constructor.

    • PROSACRobustEstimator

      public PROSACRobustEstimator(PROSACRobustEstimatorListener<T> listener)
      Constructor with listener.
      Parameters:
      listener - listener to be notified of events such as when estimation starts, ends or its progress significantly changes, as well as in charge of picking samples and doing per-iteration estimations.

  • Method Details

    • getConfidence

      public double getConfidence()
      Returns amount of confidence expressed as a value between 0 and 1.0 (which is equivalent to 100%). The amount of confidence indicates the probability that the estimated result is correct. Usually this value will be close to 1.0, but not exactly 1.0.
      Returns:
      amount of confidence as a value between 0.0 and 1.0.

    • setConfidence

      public void setConfidence(double confidence) throws LockedException
      Sets amount of confidence expressed as a value between 0 and 1.0 (which is equivalent to 100%). The amount of confidence indicates the probability that the estimated result is correct. Usually this value will be close to 1.0, but not exactly 1.0.
      Parameters:
      confidence - confidence to be set as a value between 0.0 and 1.0.
      Throws:
      IllegalArgumentException - if provided value is not between 0.0 and 1.0.
      LockedException - if this estimator is locked because an estimation is being computed.

    • getMaxIterations

      public int getMaxIterations()
      Maximum allowed number of iterations. When the maximum number of iterations is exceeded, result will not be available, however an approximate result will be available for retrieval.
      Returns:
      maximum allowed number of iterations.

    • setMaxIterations

      public void setMaxIterations(int maxIterations) throws LockedException
      Sets maximum allowed number of iterations. When the maximum number of iterations is exceeded, result will not be available, however an approximate result will be available for retrieval.
      Parameters:
      maxIterations - maximum allowed number of iterations to be set.
      Throws:
      IllegalArgumentException - if provided value is less than 1.
      LockedException - if this estimator is locked because an estimation is being computed.

    • getMaxOutliersProportion

      public double getMaxOutliersProportion()
      Returns maximum allowed outliers proportion in the input data. This is used to compute number of iterations to be done (nIters). It typically can be as high as 0.95. Higher values, up to 1 are possible but not recommended. In this implementation, PROSAC won't stop before having reached the corresponding inliers rate on the complete data set.
      Returns:
      maximum allowed outliers proportion in the input data.

    • setMaxOutliersProportion

      public void setMaxOutliersProportion(double maxOutliersProportion) throws LockedException
      Sets maximum allowed outliers proportion in the input data. This is used to compute number of iterations to be done (nIters). It typically can be as high as 0.95. Higher values, up to 1 are possible but not recommended. In this implementation, PROSAC won't stop before having reached the corresponding inliers rate on the complete data set.
      Parameters:
      maxOutliersProportion - maximum allowed outliers proportion in the input data.
      Throws:
      IllegalArgumentException - if provided value is less than 0.0 or greater than 1.0.
      LockedException - if this estimator is locked because an estimation is being computed.

    • getEta0

      public double getEta0()
      Return eta0, which is the maximum probability that a solution with more than inliersNStar inliers in U_nStar exists and was not found after k samples (typically set to 5%).
      Returns:
      eta0 value.

    • setEta0

      public void setEta0(double eta0) throws LockedException
      Sets eta0, which is the maximum probability that a solution with more than inliersNStar inliers in U_nStar exists and was not found after k samples (typically set to 5%).
      Parameters:
      eta0 - eta0 value to be set.
      Throws:
      IllegalArgumentException - if provided value is less than 0.0 or greater than 1.0.
      LockedException - if this estimator is locked because an estimation is being computed.

    • getBeta

      public double getBeta()
      Returns beta, which is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface. The inlier surface is a disc with radius 1.96s for homography/displacement computation, or a band with width 1.96s*2 for epipolar geometry (s is the detection noise), and the total surface is the surface of the image YOU MUST ADJUST THIS VALUE, DEPENDING ON YOUR PROBLEM!
      Returns:
      beta value.

    • setBeta

      public void setBeta(double beta) throws LockedException
      Sets beta, which is the probability that a match is declared inlier by mistake, i.e. the ratio of the "inlier" surface by the total surface. The inlier surface is a disc with radius 1.96s for homography/displacement computation, or a band with width 1.96s*2 for epipolar geometry (s is the detection noise), and the total surface is the surface of the image YOU MUST ADJUST THIS VALUE, DEPENDING ON YOUR PROBLEM!
      Parameters:
      beta - beta value to be set.
      Throws:
      IllegalArgumentException - if provided value is less than 0.0 or greater than 1.0.
      LockedException - if this estimator is locked because an estimation is being computed.

    • getNIters

      public int getNIters()
      Returns number of iterations to be done to obtain required confidence. This does not need to be equal to the actual number of iterations the algorithm finally required to obtain a solution.
      Returns:
      number of iterations to be done to obtain required confidence.

    • getBestResult

      public T getBestResult()
      Returns best solution that has been found so far during an estimation.
      Returns:
      best solution that has been found so far during an estimation.

    • getBestInliersData

      public PROSACRobustEstimator.PROSACInliersData getBestInliersData()
      Gets data related to inliers found for best result.
      Returns:
      data related to inliers found for best result.

    • isComputeAndKeepInliersEnabled

      public boolean isComputeAndKeepInliersEnabled()
      Indicates whether inliers must be computed and kept.
      Returns:
      true if inliers must be computed and kept, false if inliers only need to be computed but not kept.

    • setComputeAndKeepInliersEnabled

      public void setComputeAndKeepInliersEnabled(boolean computeAndKeepInliers) throws LockedException
      Specifies whether inliers must be computed and kept.
      Parameters:
      computeAndKeepInliers - true if inliers must be computed and kept, false if inliers only need to be computed but not kept.
      Throws:
      LockedException - if estimator is locked.

    • isComputeAndKeepResidualsEnabled

      public boolean isComputeAndKeepResidualsEnabled()
      Indicates whether residuals must be computed and kept.
      Returns:
      true if residuals must be computed and kept, false if residuals only need to be computed but not kept.

    • setComputeAndKeepResidualsEnabled

      public void setComputeAndKeepResidualsEnabled(boolean computeAndKeepResiduals) throws LockedException
      Specifies whether residuals must be computed and kept.
      Parameters:
      computeAndKeepResiduals - true if residuals must be computed and kept, false if residuals only need to be computed but not kept.
      Throws:
      LockedException - if estimator is locked.

    • isReady

      public boolean isReady()
      Indicates if estimator is ready to start the estimation process.
      Overrides:
      isReady in class RobustEstimator<T>
      Returns:
      true if ready, false otherwise.

    • estimate

      public T estimate() throws LockedException, NotReadyException, RobustEstimatorException
      Robustly estimates an instance of T.
      Specified by:
      estimate in class RobustEstimator<T>
      Returns:
      estimated object.
      Throws:
      LockedException - if robust estimator is locked.
      NotReadyException - if provided input data is not enough to start the estimation.
      RobustEstimatorException - if estimation fails for any reason (i.e. numerical instability, no solution available, etc).

    • getInliersData

      public InliersData getInliersData()
      Returns data about inliers once estimation has been done.
      Specified by:
      getInliersData in class RobustEstimator<T>
      Returns:
      data about inliers or null if estimation has not been done.

    • getMethod

      public RobustEstimatorMethod getMethod()
      Returns method being used for robust estimation.
      Specified by:
      getMethod in class RobustEstimator<T>
      Returns:
      method being used for robust estimation.

    • transformIndices

      private static void transformIndices(int[] subsetIndices, int[] sortedIndices, int[] transformedSubsetIndices)
      Transforms indices picked by the subset selector into the indices where samples are actually localed by taking into account their original position before sorting quality scores.
      Parameters:
      subsetIndices - indices picked by the subset selector. These are positions after sorting. Must have the subset length.
      sortedIndices - indices relating sorted positions to their original positions. Each position i-th in the array refers to the original position before sorting. Must have the number of samples length.
      transformedSubsetIndices - array where result is stored. Must have the subset length.

    • computeInliers

      private static <T> int computeInliers(T iterResult, double threshold, BitSet inliers, int totalSamples, PROSACRobustEstimatorListener<T> listener, double[] residuals)
      Computes inliers data for current iteration.
      Type Parameters:
      T - type of result to be estimated.
      Parameters:
      iterResult - result to be tested on current iteration.
      threshold - threshold to determine whether samples are inliers or not.
      inliers - bitset indicating which samples are inliers. This is indicated in their original position before sorting.
      totalSamples - total number of samples.
      listener - listener to obtain residuals for samples.
      residuals - array where residuals must be stored (if provided).
      Returns:
      inliers data.

    • computeSortedQualityIndices

      private static int[] computeSortedQualityIndices(double[] qualityScores) throws com.irurueta.sorting.SortingException
      Obtains indices of samples corresponding to samples ordered in descending quality scores.
      Parameters:
      qualityScores - quality scores associated to each sample to be used to obtain indices to sort samples in descending order of quality values.
      Returns:
      indices to sort samples in descending order of quality values.
      Throws:
      com.irurueta.sorting.SortingException - if sorting fails.

    • reverse

      private static void reverse(int[] array)
      Reverses provided array.
      Parameters:
      array - array to be reversed.

    • computeIterations

      private static int computeIterations(double probInlier, int subsetSize, double confidence)
      Computes number of required iterations to achieve required confidence with current probability of inlier and sample subset size.
      Parameters:
      probInlier - probability of inlier.
      subsetSize - sample subset size.
      confidence - required confidence of result.
      Returns:
      number of required iterations.

    • imin

      private static int imin(int subsetSize, int sampleSize, double beta)
      Non randomness states that i-m (where i is the cardinal of the set of inliers for a wrong model) follows the binomial distribution B(n,beta). For n big enough, B(n,beta) approximates to normal distribution N(mu, sigma^2) by the central limit theorem, with mu = n*beta and sigma = sqrt(n*beta*(1 - beta)). Psi, the probability that In_star out of n_star data points are by chance inliers to an arbitrary incorrect model, is set to 0.05 (5%, as in the original paper), and you must change the Chi2 value if you chose a different value for psi.
      Parameters:
      subsetSize - sample subset size.
      sampleSize - total number of samples.
      beta - beta value.
      Returns:
      i-m.