Ransac.cpp
Go to the documentation of this file.
00001 /*
00002  * This file is part of ALVAR, A Library for Virtual and Augmented Reality.
00003  *
00004  * Copyright 2007-2012 VTT Technical Research Centre of Finland
00005  *
00006  * Contact: VTT Augmented Reality Team <alvar.info@vtt.fi>
00007  *          <http://www.vtt.fi/multimedia/alvar.html>
00008  *
00009  * ALVAR is free software; you can redistribute it and/or modify it under the
00010  * terms of the GNU Lesser General Public License as published by the Free
00011  * Software Foundation; either version 2.1 of the License, or (at your option)
00012  * any later version.
00013  *
00014  * This library is distributed in the hope that it will be useful, but WITHOUT
00015  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00016  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
00017  * for more details.
00018  *
00019  * You should have received a copy of the GNU Lesser General Public License
00020  * along with ALVAR; if not, see
00021  * <http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html>.
00022  */
00023 
00024 #include "Ransac.h"
00025 #include <memory.h>
00026 #include <math.h>
00027 
00028 #ifdef TRACE
00029     #include <stdio.h>
00030 #endif
00031 
00032 namespace alvar {
00033 
00034 RansacImpl::RansacImpl(int min_params, int max_params, 
00035                        int sizeof_param, int sizeof_model) {
00036   this->min_params = min_params;
00037   this->max_params = max_params;
00038   this->sizeof_param = sizeof_param;
00039   this->sizeof_model = sizeof_model;
00040   indices = NULL;
00041 
00042   samples = new void*[max_params];
00043   if (!samples) {
00044 #ifdef TRACE
00045     printf("Cound not allocate memory for %d sample pointers.",
00046                   max_params);
00047 #endif
00048   }
00049 
00050   hypothesis = new char[sizeof_model];
00051   if (!hypothesis) {
00052 #ifdef TRACE
00053     printf("Cound not allocate %d bytes of memory for model parameters.",
00054                   sizeof_model);
00055 #endif
00056   }
00057 }
00058 
00059 RansacImpl::~RansacImpl() {
00060   if (samples) delete[] samples;
00061   if (hypothesis) delete[] (char *)hypothesis;
00062   if (indices) delete[] indices;
00063 }
00064 
00065 int RansacImpl::_estimate(void* params, int param_c,
00066                           int support_limit, int max_rounds,
00067                           void* model) {
00068             if (param_c < min_params) return 0;
00069 
00070             int max_support = 0;
00071 
00072             // Randomly search for the best model.
00073             for (int i = 0; 
00074                  i < max_rounds && max_support < support_limit; 
00075                  i++) {
00076                 // 1. pick a random sample of min_params.
00077                 int sample_c;
00078                 for (sample_c = 0; sample_c < min_params; sample_c++) {
00079                     int r = rand() % (param_c-sample_c);
00080                     void* s = (char*)params + r*sizeof_param;
00081                     for (int j = 0; j < sample_c; j++) 
00082                         if (s >= samples[j]) s = (char*)s + sizeof_param;
00083                     samples[sample_c] = s;
00084                 }
00085 
00086                 // 2. create a model from the sampled parameters.
00087                 _doEstimate(samples, sample_c, hypothesis);
00088 
00089                 // 3. count the support for the model.
00090                 int hypo_support = 0;
00091                 for (int j = 0; j < param_c; j++) {
00092                     if (_doSupports((char*)params + j*sizeof_param, hypothesis)) {
00093                         hypo_support++;
00094                     }
00095                 }
00096 #ifdef TRACE
00097                 printf("Hypothesis got %d support\n", hypo_support);
00098 #endif
00099                 if (hypo_support > max_support) {
00100                     max_support = hypo_support;
00101                     memcpy(model, hypothesis, sizeof_model);
00102                 }
00103             }
00104 
00105             return max_support;
00106 }
00107 
00108 int RansacImpl::_refine(void* params, int param_c,
00109                         int support_limit, int max_rounds,
00110                         void* model, char *inlier_mask) {
00111   if (param_c < min_params) return 0;
00112 
00113   int max_support = 0;
00114 
00115   // Iteratively make the model estimation better.
00116   for (int i = 0; 
00117        i < max_rounds && max_support < support_limit; 
00118        i++) {
00119     int sample_c = 0;
00120     // 1. Find all parameters that support the current model.
00121     for (int j = 0; j < param_c && sample_c < max_params; j++) {
00122       if (_doSupports((char*)params + j*sizeof_param, model)) {
00123               samples[sample_c++] = (char*)params + j*sizeof_param;
00124         if (inlier_mask) inlier_mask[j] = 1;
00125       } else {
00126         if (inlier_mask) inlier_mask[j] = 0;
00127       }
00128     }
00129 #ifdef TRACE
00130     printf("Found %d supporting parameters\n", sample_c);
00131 #endif
00132     if (sample_c > max_support) {
00133       // 2. create a model from all supporting parameters.
00134       _doEstimate(samples, sample_c, model);
00135       max_support = sample_c;
00136       
00137     } else {
00138       // until there are no new supporting parameters.
00139       break;
00140     }
00141   }
00142   
00143   return max_support;
00144 }
00145 
00148 RansacImpl::RansacImpl(int min_params, int max_params, int sizeof_model) {
00149   this->min_params = min_params;
00150   this->max_params = max_params;
00151   this->sizeof_param = -1;
00152   this->sizeof_model = sizeof_model;
00153   samples = NULL;
00154   indices = new int[max_params];
00155   hypothesis = new char[sizeof_model];
00156   if (!hypothesis) {
00157 #ifdef TRACE
00158     printf("Cound not allocate %d bytes of memory for model parameters.",
00159                   sizeof_model);
00160 #endif
00161   }
00162 }
00163 
00164 int RansacImpl::_estimate(int param_c,
00165                                       int support_limit, int max_rounds,
00166                           void* model) {
00167   if (param_c < min_params) return 0;
00168 
00169   int max_support = 0;
00170 
00171   // Randomly search for the best model.
00172   for (int i = 0; 
00173        i < max_rounds && max_support < support_limit; 
00174        i++) {
00175       // 1. pick a random sample of min_params.
00176       int sample_c;
00177       for (sample_c = 0; sample_c < min_params; sample_c++) {
00178           int r = rand() % (param_c-sample_c);
00179           for (int j = 0; j < sample_c; j++) 
00180               if (r >= indices[j]) r++;
00181           indices[sample_c] = r;
00182       }
00183 
00184       // 2. create a model from the sampled parameters.
00185       _doEstimate(indices, sample_c, hypothesis);
00186 
00187       // 3. count the support for the model.
00188       int hypo_support = 0;
00189       for (int j = 0; j < param_c; j++) {
00190           if (_doSupports(j, hypothesis)) {
00191               hypo_support++;
00192           }
00193       }
00194 #ifdef TRACE
00195       printf("Hypothesis got %d support\n", hypo_support);
00196 #endif
00197       if (hypo_support > max_support) {
00198           max_support = hypo_support;
00199           memcpy(model, hypothesis, sizeof_model);
00200       }
00201   }
00202 
00203   return max_support;
00204 }
00205 
00206 int RansacImpl::_refine(int param_c,
00207                               int support_limit, int max_rounds,
00208                         void* model, char *inlier_mask) {
00209   if (param_c < min_params) return 0;
00210 
00211   int max_support = 0;
00212 
00213   // Iteratively make the model estimation better.
00214   for (int i = 0; 
00215        i < max_rounds && max_support < support_limit; 
00216        i++) {
00217     int sample_c = 0;
00218     // 1. Find all parameters that support the current model.
00219     for (int j = 0; j < param_c && sample_c < max_params; j++) {
00220       if (_doSupports(j, model)) {
00221               indices[sample_c++] = j;
00222         if (inlier_mask) inlier_mask[j] = 1;
00223       } else {
00224         if (inlier_mask) inlier_mask[j] = 0;
00225       }
00226     }
00227 #ifdef TRACE
00228     printf("Found %d supporting parameters\n", sample_c);
00229 #endif
00230     if (sample_c < min_params) break; // indicates too few points.
00231     if (sample_c > max_support) {
00232       // 2. create a model from all supporting parameters.
00233       _doEstimate(indices, sample_c, model);
00234       max_support = sample_c;
00235       
00236     } else {
00237       // until there are no new supporting parameters.
00238       break;
00239     }
00240   }
00241   
00242   return max_support;
00243 }
00244 
00247 int RansacImpl::estimateRequiredRounds(float success_propability,
00248                                        float inlier_percentage) {
00249   return (int) 
00250     (log(1-success_propability) / log(1-pow(inlier_percentage,3)));
00251 }
00252 
00253 } // namespace alvar


ar_track_alvar
Author(s): Scott Niekum
autogenerated on Sat Dec 28 2013 16:46:15