Main MRPT website > C++ reference
MRPT logo

model_search.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 
00029 #ifndef math_modelsearch_h
00030 #define math_modelsearch_h
00031 
00032 #include <mrpt/utils/utils_defs.h>
00033 
00034 namespace mrpt {
00035         namespace math {
00036 
00037         /** Model search implementations: RANSAC and genetic algorithm
00038           *
00039           *  The type  \a TModelFit is a user-supplied struct/class that implements this interface:
00040           *  - Types:
00041           *    - \a Real : The numeric type to use (typ: double, float)
00042           *    - \a Model : The type of the model to be fitted (for example: A matrix, a TLine2D, a TPlane3D, ...)
00043           *  - Methods:
00044           *    - size_t getSampleCount() const : return the number of samples. This should not change during a model search.
00045           *    - bool fitModel( const vector_size_t& useIndices, Model& model ) const : This function fits a model to the data selected by the indices. The return value indicates the success, hence false means a degenerate case, where no model was found.
00046           *    - Real testSample( size_t index, const Model& model ) const : return some value that indicates how well a sample fits to the model. This way the thresholding is moved to the searching procedure and the model just tells how good a sample is.
00047           *
00048           *  There are two methods provided in this class to fit a model:
00049           *    - \a ransacSingleModel (RANSAC): Just like mrpt::math::RANSAC_Template
00050           *
00051           *    - \a geneticSingleModel (Genetic): Provides a mixture of a genetic and the ransac algorithm.
00052           *         Instead of selecting a set of data in each iteration, it takes more (ex. 10) and order these model
00053           *         using some fitness function: the average error of the inliers scaled by the number of outliers (This
00054           *         fitness might require some fine tuning). Than the (ex 10) new kernel for the next iteration is created as follows:
00055           *             - Take the best kernels (as for the original ransac)
00056           *             - Select two kernels ( with a higher probability for the better models) and let the new kernel be a subset of the two original kernels ( additionally to leave the local minimums an additional random seed might appear - mutation)
00057           *             - Generate some new random samples.
00058           *
00059           *  For an example of usage, see "samples/model_search_test/"
00060           *  \sa mrpt::math::RANSAC_Template, another RANSAC implementation where models can be matrices only.
00061           *
00062           *  \author Zoltar Gaal
00063           */
00064         class BASE_IMPEXP ModelSearch {
00065         private:
00066                 //! Select random (unique) indices from the 0..p_size sequence
00067                 void pickRandomIndex( size_t p_size, size_t p_pick, vector_size_t& p_ind );
00068 
00069                 /** Select random (unique) indices from the set.
00070                   *  The set is destroyed during pick */
00071                 void pickRandomIndex( std::set<size_t> p_set, size_t p_pick, vector_size_t& p_ind );
00072 
00073         public:
00074                 template<typename TModelFit>
00075                 bool    ransacSingleModel( const TModelFit& p_state,
00076                                                                    size_t p_kernelSize,
00077                                                                    const typename TModelFit::Real& p_fitnessThreshold,
00078                                                                    typename TModelFit::Model& p_bestModel,
00079                                                                    vector_size_t& p_inliers );
00080 
00081         private:
00082                 template<typename TModelFit>
00083                 struct TSpecies {
00084                         typename TModelFit::Model       model;
00085                         vector_size_t                           sample;
00086                         vector_size_t                           inliers;
00087                         typename TModelFit::Real        fitness;
00088 
00089                         static bool compare( const TSpecies* p_a, const TSpecies* p_b )
00090                         {
00091                                 return p_a->fitness < p_b->fitness;
00092                         }
00093                 };
00094 
00095         public:
00096                 template<typename TModelFit>
00097                 bool    geneticSingleModel( const TModelFit& p_state,
00098                                                                         size_t p_kernelSize,
00099                                                                         const typename TModelFit::Real& p_fitnessThreshold,
00100                                                                         size_t p_populationSize,
00101                                                                         size_t p_maxIteration,
00102                                                                         typename TModelFit::Model& p_bestModel,
00103                                                                         vector_size_t& p_inliers );
00104         }; // end of class
00105 
00106         } // namespace math
00107 } // namespace mrpt
00108 
00109 // Template implementations:
00110 #include "model_search_impl.h"
00111 
00112 #endif // math_modelsearch_h



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011