Image Component Library (ICL)
|
00001 /******************************************************************** 00002 ** Image Component Library (ICL) ** 00003 ** ** 00004 ** Copyright (C) 2006-2013 CITEC, University of Bielefeld ** 00005 ** Neuroinformatics Group ** 00006 ** Website: www.iclcv.org and ** 00007 ** http://opensource.cit-ec.de/projects/icl ** 00008 ** ** 00009 ** File : ICLMath/src/ICLMath/RansacFitter.h ** 00010 ** Module : ICLMath ** 00011 ** Authors: Christof Elbrechter ** 00012 ** ** 00013 ** ** 00014 ** GNU LESSER GENERAL PUBLIC LICENSE ** 00015 ** This file may be used under the terms of the GNU Lesser General ** 00016 ** Public License version 3.0 as published by the ** 00017 ** ** 00018 ** Free Software Foundation and appearing in the file LICENSE.GPL ** 00019 ** included in the packaging of this file. Please review the ** 00020 ** following information to ensure the license requirements will ** 00021 ** be met: http://www.gnu.org/licenses/lgpl-3.0.txt ** 00022 ** ** 00023 ** The development of this software was supported by the ** 00024 ** Excellence Cluster EXC 277 Cognitive Interaction Technology. ** 00025 ** The Excellence Cluster EXC 277 is a grant of the Deutsche ** 00026 ** Forschungsgemeinschaft (DFG) in the context of the German ** 00027 ** Excellence Initiative. ** 00028 ** ** 00029 ********************************************************************/ 00030 00031 #pragma once 00032 00033 #include <ICLMath/DynVector.h> 00034 #include <ICLMath/FixedVector.h> 00035 #include <ICLUtils/Function.h> 00036 #include <ICLUtils/Uncopyable.h> 00037 #include <ICLUtils/Random.h> 00038 00039 namespace icl{ 00040 namespace math{ 00041 00042 00044 00060 template<class DataPoint=std::vector<float>, 00061 class Model=std::vector<float> > 00062 class RansacFitter{ 00063 public: 00065 typedef std::vector<DataPoint> DataSet; 00066 00068 typedef utils::Function<Model,const DataSet&> ModelFitting; 00069 00071 typedef utils::Function<icl64f,const Model&,const DataPoint&> PointError; 00072 00073 private: 00075 int m_minPointsForModel; 00076 00078 int m_iterations; 00079 00081 icl64f m_maxModelDistance; 00082 00084 int m_minClosePointsForGoodModel; 00085 00087 ModelFitting m_fitting; 00088 00090 PointError m_err; 00091 00093 icl64f m_minErrorExit; 00094 00095 public: 00097 struct Result{ 00099 icl64f error; 00100 00102 Model model; 00103 00105 00106 DataSet consensusSet; 00107 00109 int iterationCount; 00110 00112 bool found() const { return consensusSet.size(); } 00113 }; 00114 00115 private: 00117 Result m_result; 00118 00120 static inline bool find_in(const std::vector<int> &v, int i, int n){ 00121 return std::find(v.data(), v.data()+n, i) != v.data()+n; 00122 } 00123 00125 void find_random_consensus_set(DataSet &currConsensusSet, 00126 const DataSet &allPoints, 00127 std::vector<int> &usedIndices){ 00128 const int n = currConsensusSet.size(); 00129 utils::URandI r(allPoints.size()-1); 00130 00131 for(int i=0;i<n;++i){ 00132 do { usedIndices[i] = r; } while ( find_in(usedIndices, usedIndices[i], i-1) ); 00133 currConsensusSet[i] = allPoints[ usedIndices[i] ]; 00134 } 00135 } 00136 00137 public: 00139 RansacFitter(){} 00140 00142 00144 RansacFitter(int minPointsForModel, 00145 int iterations, 00146 ModelFitting fitting, 00147 PointError err, 00148 icl64f maxModelDistance, 00149 int minClosePointsForGoodModel, 00150 icl64f minErrorExit=0): 00151 m_minPointsForModel(minPointsForModel), 00152 m_iterations(iterations), 00153 m_maxModelDistance(maxModelDistance), 00154 m_minClosePointsForGoodModel(minClosePointsForGoodModel), 00155 m_fitting(fitting),m_err(err), 00156 m_minErrorExit(minErrorExit){ 00157 } 00158 00160 const Result &fit(const DataSet &allPoints){ 00161 m_result.model = Model(); 00162 m_result.consensusSet.clear(); 00163 m_result.error = utils::Range64f::limits().maxVal; 00164 m_result.iterationCount = 0; 00165 std::vector<DataPoint> consensusSet(m_minPointsForModel); 00166 std::vector<int> usedIndices(m_minPointsForModel); 00167 00168 int i = 0; 00169 for(i=0;i<m_iterations;++i){ 00170 consensusSet.resize(m_minPointsForModel); 00171 find_random_consensus_set(consensusSet, allPoints, usedIndices); 00172 00173 Model model = m_fitting(consensusSet); 00174 for(int j=0;j<(int)allPoints.size();++j){ 00175 if(find_in(usedIndices, j, usedIndices.size())) continue; 00176 if(m_err(model, allPoints[j]) < m_maxModelDistance){ 00177 consensusSet.push_back(allPoints[j]); 00178 } 00179 } 00180 00181 if((int)consensusSet.size() >= m_minClosePointsForGoodModel){ 00182 model = m_fitting(consensusSet); 00183 double error = 0; 00184 for(unsigned int j=0;j<consensusSet.size();++j){ 00185 error += m_err(model, consensusSet[j]); 00186 } 00187 error /= consensusSet.size(); 00188 00189 if(error < m_result.error){ 00190 m_result.error = error; 00191 m_result.model = model; 00192 m_result.consensusSet = consensusSet; 00193 if(m_result.error < m_minErrorExit){ 00194 m_result.iterationCount = i; 00195 return m_result; 00196 } 00197 } 00198 } 00199 } 00200 m_result.iterationCount = i; 00201 return m_result; 00202 } 00203 }; 00204 } // namespace math 00205 } 00206