RANSACEvaluatorInterface.hh

/* This file is part of the BIAS library (Basic ImageAlgorithmS).

   Copyright (C) 2003, 2004    (see file CONTACTS for details)
   Multimediale Systeme der Informationsverarbeitung
   Institut fuer Informatik
   Christian-Albrechts-Universitaet Kiel
   
   BIAS is free software; you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as published by
   the Free Software Foundation; either version 2.1 of the License, or
   (at your option) any later version.
   
   BIAS is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.
   
   You should have received a copy of the GNU Lesser General Public License
   along with BIAS; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
#ifndef __RANSACEvaluatorInterface_hh__
#define __RANSACEvaluatorInterface_hh__

#include <Base/Math/Random.hh>

#include <vector>
#include <algorithm>

namespace BIAS {

  /** @class RANSACEvaluatorInterface
      @brief Interface for computation of solutions and evaluation of 
      measurements. This interface is used by the PreemptiveRANSAC and the 
      COSAC classes and decouples the problem (for example Homography 
      estimation) from the algorithm (for example PreemptiveRANSAC or 
      Complete Sampling Consesus / COSAC).

      A standard implementation for sample generation is also given.

      @relates PreemptiveRANSAC, COSAC

      @author woelk 01/2010 (c) www.vision-n.de */
  template <class SolutionType>
  class RANSACEvaluatorInterface
  {
  public:
    /** Returns the number of available measurements */
    virtual unsigned GetNumMeasurements() const = 0;

    /** Returns the minimum required samples for computation of a solution */
    virtual unsigned GetMinNumSamplesForSolutionComputation() const = 0;

    /** Checks whether a certain sample (i.e. data) is an inlier and computes
        the associated score. Good solutions result in a small score, bad 
        solutions result in big scores. Scores may also be negative. It is 
        often a good idea do define the score as the logarithm of some 
        normalized distance measure. */
    virtual bool IsInlier(const SolutionType& solution, 
                          const unsigned data_index,
                          double& score) = 0;
    
    /** @brief Compute solution(s) for the given set of samples
        @return the number of solutions found.

        The which_samples array will be of length sample_size, selecting the
        indices to be fit to from the subclass's data array. */
    virtual int GetSampleSolutions(const std::vector<unsigned> &which_samples,
                                   std::vector<SolutionType> &solutions)= 0;

    /** @brief Refine a solution based on the inliers vector */
    virtual bool RefineSolution(const std::vector<bool>& inliers,
                                SolutionType& solution) = 0; 

    /** @brief randomly generates the indizes of the samples used for 
        computation of the solution. This function can be overloaded, for 
        example when it is of advantage when the samples span a big 
        area (for example in the image) */
    virtual bool GenerateSamples(const unsigned sample_index, 
                                 const unsigned sample_size,
                                 const unsigned data_size, 
                                 std::vector<unsigned>& which_samples);

  protected:
    /// purely random generation of sample indizes
    bool GenerateSamplesRandom_(const unsigned sample_index, 
                                const unsigned sample_size,
                                const unsigned data_size, 
                                std::vector<unsigned>& which_samples);

  }; // class

  //////////////////////////////////////////////////////////////////////////
  // implementation
  /////////////////////////////////////////////////////////////////////////

  template <class SolutionType>
  bool RANSACEvaluatorInterface<SolutionType>::
  GenerateSamples(const unsigned sample_index, 
                  const unsigned sample_size,
                  const unsigned data_size, 
                  std::vector<unsigned>& which_samples)
  { 
    return GenerateSamplesRandom_(sample_index, sample_size, data_size, 
                                  which_samples); 
  }


  template <class SolutionType>
  bool RANSACEvaluatorInterface<SolutionType>::
  GenerateSamplesRandom_(const unsigned sample_index, 
                         const unsigned sample_size,
                         const unsigned data_size, 
                         std::vector<unsigned>& which_samples)
  {
    BIASASSERT(sample_size<=data_size);
    BIASASSERT(data_size>0);
    
    // initialzing random with 0 and 1 does not seem to work well
    //Random ran(sample_index+rand());
    Random ran(sample_index);
    unsigned count=0;
    unsigned index;
    which_samples.clear();
    which_samples.reserve(sample_size);
    const unsigned max_tries = 10000;
    do {
      index = ran.GetUniformDistributedInt(0u, data_size-1);
      if (std::find(which_samples.begin(), which_samples.end(), index)==
          which_samples.end()){
        which_samples.push_back(index);
        count++;
        //std::cout << index << "  ";
      }
    } while (count<sample_size && count<max_tries);
    //std::cout << std::endl;
    if (count>=max_tries){ 
      BIASERR("error generating samples (max_tries reached)");
      return false; 
    }
    
    return true;
  }
} // namespace

#endif // __RANSACEvaluatorInterface_hh__