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
#![no_std] /// 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<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: &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<Data> { /// `Model` is the model which is estimated from the underlying data type Model: Model<Data>; /// 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<I>(&self, data: I) -> Self::ModelIter where I: Iterator<Item = Data> + Clone; } /// 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, Data> where E: Estimator<Data>, { /// 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<I>(&mut self, estimator: &E, data: I) -> Option<E::Model> where I: Iterator<Item = Data> + Clone; /// 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<I>(&mut self, estimator: &E, data: I) -> Option<(E::Model, Self::Inliers)> where I: Iterator<Item = Data> + Clone; } /// 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, Data> where E: Estimator<Data>, { /// 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<I>(&mut self, estimator: &E, data: I) -> Self::Models where I: Iterator<Item = Data> + Clone; }