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);
        }
    }
}