Basic Image AlgorithmS Library 2.8.0

RANSACPreKnowledge.hh

00001 /* 
00002 This file is part of the BIAS library (Basic ImageAlgorithmS).
00003 
00004 Copyright (C) 2003-2009    (see file CONTACT for details)
00005   Multimediale Systeme der Informationsverarbeitung
00006   Institut fuer Informatik
00007   Christian-Albrechts-Universitaet Kiel
00008 
00009 
00010 BIAS is free software; you can redistribute it and/or modify
00011 it under the terms of the GNU Lesser General Public License as published by
00012 the Free Software Foundation; either version 2.1 of the License, or
00013 (at your option) any later version.
00014 
00015 BIAS is distributed in the hope that it will be useful,
00016 but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 GNU Lesser General Public License for more details.
00019 
00020 You should have received a copy of the GNU Lesser General Public License
00021 along with BIAS; if not, write to the Free Software
00022 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00023 */
00024 
00025 
00026 #ifndef __RANSACPREKNOWLEDGE_hh__
00027 #define __RANSACPREKNOWLEDGE_hh__
00028 
00029 #include "RANSAC.hh"
00030 
00031 namespace BIAS {
00032 
00033   /** @class RANSACPreKnowledge
00034       @ingroup g_mathalgo
00035       @brief Extension of RANSAC algorithm: user-supplied guesses are evaluated
00036              and refined using RANSAC criterions before actually starting the
00037              RANSAC algorithm
00038              
00039       @author koeser 11/2003 */
00040 
00041   template <class SolutionType>
00042   class /*BIASMathAlgo_EXPORT*/ RANSACPreKnowledge : public RANSAC<SolutionType>
00043   {
00044   public:
00045     using RANSAC<SolutionType>::_uiSampleSize;
00046     using RANSAC<SolutionType>::_uiMaxSolutionsPerSample;
00047     using RANSAC<SolutionType>::_uiDataSize;
00048     using RANSAC<SolutionType>::_bRefineSolution;
00049     using RANSAC<SolutionType>::_iBestSampleAcceptCount;
00050     using RANSAC<SolutionType>::_dBestSampleEvaluateScore;
00051     using RANSAC<SolutionType>::_iBestInlierAcceptCount;
00052     using RANSAC<SolutionType>::_dBestInlierEvaluateScore;
00053     using RANSAC<SolutionType>::_uiMaxSamples;
00054     using RANSAC<SolutionType>::_uiExplicitSampleNo;
00055     using RANSAC<SolutionType>::_dProbabilityOfGoodSolution;
00056     using RANSAC<SolutionType>::_dSoSmallSolutionChange;
00057     using RANSAC<SolutionType>::_got_solution_flag;
00058     using RANSAC<SolutionType>::_greedy;
00059 
00060     RANSACPreKnowledge() : RANSAC<SolutionType>() 
00061     { Debug::NewDebugLevel("D_RANSAC_PRE_KNOWLEDGE"); };
00062     
00063     /** Construct a RANSAC object that takes samples of size sample_size,
00064         returning at most max_solutions_per_sample solutions each time.
00065         If the refine_solution flag is true, a routine has been supplied to
00066         refine the initial fits before evaluation. */
00067     RANSACPreKnowledge(unsigned int sample_size,
00068                        unsigned int max_solutions_per_sample = 1,
00069                        bool refine_solution = false): 
00070       RANSAC<SolutionType>(sample_size, max_solutions_per_sample, 
00071                            refine_solution)
00072     { Debug::NewDebugLevel("D_RANSAC_PRE_KNOWLEDGE"); };
00073 
00074     /** @brief default destructor does nothing */
00075     virtual ~RANSACPreKnowledge() { };
00076 
00077     /** @brief add some guessed solutions which are tested by RANSAC later */
00078     virtual inline void AddGoodGuesses(const std::vector<SolutionType> &Guesses) {
00079       UserGuesses_.reserve(UserGuesses_.size() + Guesses.size());
00080       for (typename std::vector<SolutionType>::const_iterator 
00081              it = Guesses.begin(); it!=Guesses.end(); it++)
00082         UserGuesses_.push_back(*it);
00083     }
00084 
00085     /** @brief clear all guesses */
00086     virtual inline void ClearGuesses() {
00087       UserGuesses_.clear();
00088     }
00089 
00090     /** @brief checks UserGuesses and calls RANSAC::SolveMaster
00091         @author koeser */
00092     virtual inline int SolveMaster(double inlying_data_fraction,
00093                                    SolutionType &solution,
00094                                    std::vector<bool> &inliers);
00095 
00096   protected:
00097     /// vector of guesses to be checked, which were manually supplied by user
00098     std::vector<SolutionType> UserGuesses_;
00099 
00100   };
00101 
00102   template <class SolutionType> inline int
00103   RANSACPreKnowledge<SolutionType>::SolveMaster(double inlying_data_fraction,
00104                                                 SolutionType &solution,
00105                                                 std::vector<bool> &inliers) {
00106     BCDOUT(D_RANSAC_PRE_KNOWLEDGE, 
00107            "RANSACPreKnowledge::SolveMaster() -----------------------------"
00108            "-----------------\n");
00109     BCDOUT(D_RANSAC_SAMPLE_QUALITY, "|||||||||||||||||||||\n\n");
00110     // in order to do a real RANSAC run without high thresholds of 
00111     // pre-guesses, we clean up everything
00112     _iBestSampleAcceptCount   = -1;
00113     _dBestSampleEvaluateScore = -1;
00114     _iBestInlierAcceptCount   = -1;
00115     _dBestInlierEvaluateScore = -1;
00116     _got_solution_flag = false;
00117 
00118    // offsets of samples for current solution
00119     std::vector<unsigned int> which_samples;
00120 
00121     // vector indicating which ssamples are inliers
00122     std::vector<bool> inlier_set(_uiDataSize, false);
00123 
00124     // number of inliers for current solution
00125     int sample_accept_count; 
00126     
00127     // score for sample set(resp. current solution), is set by EvaluateSolution
00128     double sample_evaluate_score; 
00129 
00130     // found a solution that good that we can finish, set by EvaluateSolution
00131     bool ok_to_terminate_flag;
00132 
00133     // current solution is accepted by EvaluateSolution
00134     bool good_flag;
00135 
00136     // number of inliers for current solution after refinement
00137     int inlier_accept_count;
00138 
00139     // score for current solution after refinement
00140     double inlier_evaluate_score;
00141 
00142     // indicates that the current is the best solution so far
00143     bool best_so_far_flag;
00144 
00145     // if ok_to_terminate is set true, fast termination is enabled if
00146     // termination_check_active_flag is true.
00147     bool termination_check_active_flag = false;
00148 
00149     BCDOUT(D_RANSAC_PRE_KNOWLEDGE,"checking "<<UserGuesses_.size()<<
00150               " user guesses\n");
00151     // run over all user guesses and evaluate using RANSAC criterions:
00152     for (typename std::vector<SolutionType>::iterator 
00153            it = UserGuesses_.begin(); it!=UserGuesses_.end(); it++) {
00154       
00155 
00156       ok_to_terminate_flag = false;
00157       sample_evaluate_score = DBL_MAX;
00158       good_flag = this->EvaluateSolution(*it, _got_solution_flag, 
00159                                    inlier_set, sample_accept_count, 
00160                                    sample_evaluate_score, 
00161                                    ok_to_terminate_flag); 
00162 
00163       BCDOUT(D_RANSAC_PRE_KNOWLEDGE,"PreGuess. "
00164                <<" solution: "<<(*it)
00165                <<" inliers: " <<sample_accept_count<<"/"<<_uiDataSize
00166                <<" score: "<< sample_evaluate_score<<std::endl);        
00167 
00168       inlier_accept_count=-1;
00169       inlier_evaluate_score = 1e20;
00170       if (good_flag && _bRefineSolution) { 
00171         // backup linear solution in case refining doesnt improve results
00172         SolutionType samplesolution = *it;
00173         bool ok_to_terminate_with_linear = ok_to_terminate_flag;
00174 
00175         which_samples.clear();
00176         for (unsigned int i=0; i<_uiDataSize; i++)
00177           if (inlier_set[i]) which_samples.push_back(i);
00178         if (this->RefineSolution(which_samples, *it, 
00179                            inlier_set)){
00180           if (_got_solution_flag)
00181             inlier_accept_count = _iBestInlierAcceptCount;
00182           good_flag = 
00183             this->EvaluateSolution (*it, _got_solution_flag,
00184                               inlier_set, inlier_accept_count,
00185                               inlier_evaluate_score, ok_to_terminate_flag);
00186           if (good_flag) {
00187             BCDOUT(D_RANSAC_PRE_KNOWLEDGE, 
00188                    "RANSACPreKnowledge: minimal/refined "
00189                      <<sample_accept_count<<"/"
00190                      <<inlier_accept_count<<" "<<sample_evaluate_score<<"/"
00191                      <<inlier_evaluate_score<<std::endl);
00192           }
00193         } else { 
00194           // RefineSolution did not succeed, we do not use the solution
00195           good_flag = false;
00196           BCDOUT(D_RANSAC_PRE_KNOWLEDGE,
00197                  "RANSACPreKnowledge: (note) refine_solution returned false"
00198                  <<std::endl);
00199         }
00200 
00201         // refining didnt improve results, use linear solution:
00202         if (!good_flag ||  (inlier_accept_count < sample_accept_count)) {
00203           BCDOUT(D_RANSAC_SOLVE_MASTER, "RANSAC: (note) Linear solution"
00204                  <<" overrides refined !!! \n");
00205           good_flag = true;
00206           inlier_accept_count = sample_accept_count;
00207           inlier_evaluate_score =  sample_evaluate_score;
00208           *it = samplesolution;
00209           ok_to_terminate_flag = ok_to_terminate_with_linear;
00210         }
00211       } else { // if (good_flag && _bRefineSolution) { 
00212         BCDOUT(D_RANSAC_PRE_KNOWLEDGE,
00213                  "RANSACPreKnowledge: (note) either good_flag=false or "
00214                  <<"_bRefineSolution=false"<<std::endl);
00215       }
00216     
00217       // the criteria for deciding the best solution is the following -
00218       // (a) if the accept_count is higher than the previous best, take it,
00219       // (b) if the accept_count is equal to the previous best, and 
00220       //     the evaluate score is smaller than the previous best, take it.
00221       if (good_flag) {
00222         BCDOUT(D_RANSAC_SAMPLE_QUALITY, "."<<std::flush);
00223         best_so_far_flag = false;
00224       
00225         if (!_got_solution_flag) {
00226           _got_solution_flag = true;
00227           best_so_far_flag = true;
00228         } else {
00229           if (!_bRefineSolution) {
00230             if (sample_accept_count > _iBestSampleAcceptCount ||
00231                 (sample_accept_count == _iBestSampleAcceptCount &&
00232                  sample_evaluate_score < _dBestSampleEvaluateScore))
00233               best_so_far_flag = true;
00234           } else {
00235             if (inlier_accept_count > _iBestInlierAcceptCount ||
00236                 (inlier_accept_count == _iBestInlierAcceptCount &&
00237                  inlier_evaluate_score < _dBestInlierEvaluateScore))
00238               best_so_far_flag = true;
00239           }
00240         }
00241 
00242         // save all the scores associated with this result.
00243         // future evaluations will be tested against these accept scores.
00244         if (best_so_far_flag) {
00245           _iBestSampleAcceptCount = sample_accept_count;
00246           _dBestSampleEvaluateScore = 
00247             (sample_evaluate_score<inlier_evaluate_score) ?
00248             sample_evaluate_score : inlier_evaluate_score;
00249           _iBestInlierAcceptCount = inlier_accept_count;
00250           _dBestInlierEvaluateScore = inlier_evaluate_score;
00251               
00252           // save inliers and solution
00253           inliers = inlier_set;
00254           solution = *it;
00255         
00256           if (_bRefineSolution){
00257             BCDOUT(D_RANSAC_PRE_KNOWLEDGE,"RANSACPreKnowledge: PreGuess "
00258                      <<" is best so far.  " << "Inliers/score "
00259                      <<_iBestInlierAcceptCount << "/" 
00260                      <<_dBestInlierEvaluateScore<<": "<<solution<<std::endl);
00261           } else {
00262             BCDOUT(D_RANSAC_PRE_KNOWLEDGE, "RANSACPreKnowledge: PreGuess "
00263                      <<" is best so far.  " << "Inliers/score "
00264                      << _iBestSampleAcceptCount << "/"
00265                      <<_dBestSampleEvaluateScore<<": "<<solution<<std::endl);
00266           }
00267               
00268           if (ok_to_terminate_flag){
00269             termination_check_active_flag = true;
00270             BCDOUT(D_RANSAC_PRE_KNOWLEDGE, 
00271                    "RANSACPreKnowledge: termination_check_active_flag = true");
00272             break; // do not evaluate the remaining solutions
00273           }
00274         } // if (best_so_far_flag) {
00275       } else { // if (good_flag) {
00276         BCDOUT(D_RANSAC_SAMPLE_QUALITY, "*"<<std::flush);
00277       }
00278     } // Guesses
00279     
00280     // check whether our guesses yielded a good solution ...
00281     if  (termination_check_active_flag) {
00282       BCDOUT(D_RANSAC_SAMPLE_QUALITY, "P" << std::endl);
00283       BCDOUT(D_RANSAC_PRE_KNOWLEDGE,
00284                "VERY GOOD preguess! Skipping RANSAC." << std::endl);
00285       return 0;
00286     }
00287 
00288     BCDOUT(D_RANSAC_PRE_KNOWLEDGE, 
00289              "RANSACPreKnowledge: No good preguess. Calling RANSAC without "
00290            "preknowledge.");
00291     // ok, we have no really good solution, call RANSAC algorithm:
00292     return  RANSAC<SolutionType>::SolveMaster(inlying_data_fraction, 
00293                                               solution, inliers);
00294   }
00295 
00296 } // end namespace
00297 
00298 #endif // header defined
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends