RansacFitter.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.hipparchus.fitting.ransac;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Optional;
import java.util.Random;
import java.util.stream.Collectors;
import org.hipparchus.exception.LocalizedCoreFormats;
import org.hipparchus.exception.MathIllegalArgumentException;
/**
* Class implementing Random sample consensus (RANSAC) algorithm.
* <p>
* RANSAC is a robust method for estimating the parameters of a
* mathematical model from a set of observed data.
* It works iteratively selecting random subsets of the input data,
* fitting a model to these subsets, and then determining how many
* data points from the entire set are consistent with the estimated
* model parameters.
* The model can yields the largest number of inliers (i.e., point
* that fit well) is considered the best estimate.
* </p>
* <p>
* This implementation is designed to be generic and can be used with
* different types of models, such as {@link PolynomialModelFitter
* polynomial models}.
* </p>
* @param <M> mathematical model representing the parameters to estimate
* @since 4.1
*/
public class RansacFitter<M> {
/** Mathematical model fitter. */
private final IModelFitter<M> fitter;
/** The minimum number of data points to estimate the model parameters. */
private final int sampleSize;
/** The maximum number of iterations allowed to fit the model. */
private final int maxIterations;
/** Threshold to assert that a data point fits the model. */
private final double threshold;
/** The minimum number of close data points required to assert that the model fits the input data. */
private final int minInliers;
/** Random generator. */
private final Random random;
/**
* Constructor.
* @param fitter mathematical model fitter
* @param sampleSize minimum number of data points to estimate the model parameters
* @param maxIterations maximum number of iterations allowed to fit the model
* @param threshold threshold to assert that a data point fits the model
* @param minInliers minimum number of close data points required to assert that the model fits the input data
* @param seed seed for the random generator
*/
public RansacFitter(final IModelFitter<M> fitter, final int sampleSize,
final int maxIterations, final double threshold,
final int minInliers, final int seed) {
this.fitter = fitter;
this.sampleSize = sampleSize;
this.maxIterations = maxIterations;
this.threshold = threshold;
this.minInliers = minInliers;
this.random = new Random(seed);
checkInputs();
}
/**
* Fits the set of observed data to determine the model parameters.
* @param points set of observed data
* @return a java class containing the best estimate of the model parameters
*/
public RansacFitterOutputs<M> fit(final List<Fittable> points) {
// Initialize the best model data
final List<Fittable> data = new ArrayList<>(points);
Optional<M> bestModel = Optional.empty();
List<Fittable> bestInliers = new ArrayList<>();
// Iterative loop to determine the best model
for (int iteration = 0; iteration < maxIterations; iteration++) {
// Random permute the set of observed data and determine the inliers
Collections.shuffle(data, random);
final List<Fittable> inliers = determineCurrentInliersFromRandomlyPermutedPoints(data);
// Verifies if the current inliers are fit better the model than the previous ones
if (isCurrentInliersSetBetterThanPreviousOne(inliers, bestInliers)) {
bestModel = Optional.of(fitter.fitModel(inliers));
bestInliers = inliers;
}
}
// Returns the best model data
return new RansacFitterOutputs<>(bestModel, bestInliers, fitter);
}
/**
* Determines the current inliers (i.e., points that fit well the model) from the input randomly permuted data.
* @param permutedPoints randomly permuted data
* @return the list of inliers
*/
private List<Fittable> determineCurrentInliersFromRandomlyPermutedPoints(final List<Fittable> permutedPoints) {
final M model = fitter.fitModel(permutedPoints.subList(0, sampleSize));
return permutedPoints.stream().filter(point -> fitter.computeModelError(model, point) < threshold).collect(Collectors.toList());
}
/**
* Verifies is the current inliers are better than the previous ones.
* @param current current inliers
* @param previous previous inliers
* @return true is the current inlier are better than the previous ones
*/
private boolean isCurrentInliersSetBetterThanPreviousOne(final List<Fittable> current, final List<Fittable> previous) {
return current.size() > previous.size() && current.size() >= minInliers;
}
/**
* Checks that the fitter inputs are correct.
*/
private void checkInputs() {
if (maxIterations < 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL, maxIterations, 0);
}
if (sampleSize < 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL, sampleSize, 0);
}
if (threshold < 0.) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL, threshold, 0);
}
if (minInliers < 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL, minInliers, 0);
}
}
}