1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

#![no_std]

pub type EstimatorData<E> = <<E as Estimator>::Model as Model>::Data;

/// A model is a best-fit of at least some of the underlying data. You can compute residuals in respect to the model.
pub trait Model {
    type Data;

    /// Note that the residual error is returned as a 32-bit float. This might be harder to preserve precision with
    /// than a 64-bit float, but it will be faster to perform RANSAC if care is taken to avoid
    /// [round-off error](https://en.wikipedia.org/wiki/Round-off_error)
    /// using [Kahan's algorithm](https://en.wikipedia.org/wiki/Kahan_summation_algorithm) or using
    /// [Pairwise summation](https://en.wikipedia.org/wiki/Pairwise_summation). If the number of datapoints is
    /// small, then there should be little issue with the accumulation of
    /// [round-off error](https://en.wikipedia.org/wiki/Round-off_error) and 32-bit floats should work
    /// without any concern.
    ///
    /// Here are some helpers to allow you to perform less lossy summation:
    ///
    /// - [Kahan Summation](https://crates.io/crates/kahan)
    /// - [Pairwise Summation](https://docs.rs/itertools/0.8.0/itertools/trait.Itertools.html#method.tree_fold1)
    ///     - `let sum = estimator.residuals(data).tree_fold1(|a, b| a + b).unwrap_or(0.0)`
    ///
    /// If all you wish to do is filter data points out if they are above a certian threshold of error
    /// then the 32-bit float's precision will be no issue for you. Most fast RANSAC algorithms
    /// utilize this approach and score models based only on their inlier count.
    fn residual(&self, data: &Self::Data) -> f32;
}

/// An `Estimator` is able to create a model that best fits a set of data.
/// It is also able to determine the residual error each data point contributes in relation to the model.
pub trait Estimator {
    /// `Model` is the model which is estimated from the underlying data
    type Model: Model;
    /// Iterator over the models produced from the data.
    type ModelIter: IntoIterator<Item = Self::Model>;

    /// The minimum number of samples that the estimator can estimate a model from.
    const MIN_SAMPLES: usize;

    /// Takes in an iterator over the data and produces a model that best fits the data.
    ///
    /// This must be passed at least `Self::MIN_SAMPLES` data points, otherwise `estimate` should panic
    /// to indicate a developer error.
    ///
    /// `None` should be returned only if a model is impossible to estimate based on the data.
    /// For instance, if a particle has greater than infinite mass, a point is detected behind a camera,
    /// an equation has an imaginary answer, or non-causal events happen, then a model may not be produced.
    fn estimate<'a, I>(&self, data: I) -> Self::ModelIter
    where
        I: Iterator<Item = &'a EstimatorData<Self>> + Clone,
        EstimatorData<Self>: 'a;
}

/// A consensus algorithm extracts a consensus from an underlying model of data.
/// This consensus includes a model of the data and which datapoints fit the model.
///
/// Note that all the consensus methods take a `&mut self`. This allows the consensus to store
/// state such as an RNG or pre-allocted memory. This means multiple threads will be forced
/// to create their own `Consensus` instance, which is most efficient.
pub trait Consensus<E>
where
    E: Estimator,
{
    /// Iterator over the indices of the inliers in the clonable iterator.
    type Inliers: IntoIterator<Item = usize>;

    /// Takes a slice over the data and an estimator instance.
    /// It returns `None` if no valid model could be found for the data and
    /// `Some` if a model was found.
    fn model(&mut self, estimator: &E, data: &[EstimatorData<E>]) -> Option<E::Model>;

    /// Takes a slice over the data and an estimator instance.
    /// It returns `None` if no valid model could be found for the data and
    /// `Some` if a model was found. It includes the inliers consistent with the model.
    fn model_inliers(
        &mut self,
        estimator: &E,
        data: &[EstimatorData<E>],
    ) -> Option<(E::Model, Self::Inliers)>;
}

/// See [`Consensus`]. A multi-consensus can handle situations where different subsets of the data are consistent
/// with different models. This kind of consensus also considers whether a point is part of another orthoganal
/// model that is known before assuming it is a true outlier. In this situation there are inliers of different
/// models and then true outliers that are actual erroneous data that should be filtered out.
pub trait MultiConsensus<E>
where
    E: Estimator,
{
    /// Iterator over the indices of the inliers in the clonable iterator.
    type Inliers: IntoIterator<Item = usize>;
    type Models: IntoIterator<Item = (E::Model, Self::Inliers)>;

    /// Takes a slice over the data and an estimator instance.
    /// It returns an iterator over all of the models and all of the inliers
    /// that are consistent with that model. Every point that is not an
    /// inlier of a given model is considered an outlier of that model.
    fn models(&mut self, estimator: &E, data: &[EstimatorData<E>]) -> Self::Models;
}