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.1 for MRPT 0.9.4 SVN: at Mon Jan 10 23:33:19 UTC 2011 |