openfabmap.hpp
Go to the documentation of this file.
1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
8 //
9 // This file originates from the openFABMAP project:
10 // [http://code.google.com/p/openfabmap/]
11 //
12 // For published work which uses all or part of OpenFABMAP, please cite:
13 // [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6224843]
14 //
15 // Original Algorithm by Mark Cummins and Paul Newman:
16 // [http://ijr.sagepub.com/content/27/6/647.short]
17 // [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5613942]
18 // [http://ijr.sagepub.com/content/30/9/1100.abstract]
19 //
20 // License Agreement
21 //
22 // Copyright (C) 2012 Arren Glover [aj.glover@qut.edu.au] and
23 // Will Maddern [w.maddern@qut.edu.au], all rights reserved.
24 //
25 //
26 // Redistribution and use in source and binary forms, with or without modification,
27 // are permitted provided that the following conditions are met:
28 //
29 // * Redistribution's of source code must retain the above copyright notice,
30 // this list of conditions and the following disclaimer.
31 //
32 // * Redistribution's in binary form must reproduce the above copyright notice,
33 // this list of conditions and the following disclaimer in the documentation
34 // and/or other materials provided with the distribution.
35 //
36 // * The name of the copyright holders may not be used to endorse or promote products
37 // derived from this software without specific prior written permission.
38 //
39 // This software is provided by the copyright holders and contributors "as is" and
40 // any express or implied warranties, including, but not limited to, the implied
41 // warranties of merchantability and fitness for a particular purpose are disclaimed.
42 // In no event shall the Intel Corporation or contributors be liable for any direct,
43 // indirect, incidental, special, exemplary, or consequential damages
44 // (including, but not limited to, procurement of substitute goods or services;
45 // loss of use, data, or profits; or business interruption) however caused
46 // and on any theory of liability, whether in contract, strict liability,
47 // or tort (including negligence or otherwise) arising in any way out of
48 // the use of this software, even if advised of the possibility of such damage.
49 //
50 //M*/
51 
52 #ifndef __OPENCV_OPENFABMAP_H_
53 #define __OPENCV_OPENFABMAP_H_
54 
55 #include "opencv2/core/core.hpp"
57 
58 #include <vector>
59 #include <list>
60 #include <map>
61 #include <set>
62 #include <valarray>
63 
64 namespace cv {
65 
66 namespace of2 {
67 
68 using std::list;
69 using std::map;
70 using std::multiset;
71 
72 /*
73  Return data format of a FABMAP compare call
74 */
75 struct CV_EXPORTS IMatch {
76 
77  IMatch() :
78  queryIdx(-1), imgIdx(-1), likelihood(-DBL_MAX), match(-DBL_MAX) {
79  }
80  IMatch(int _queryIdx, int _imgIdx, double _likelihood, double _match) :
81  queryIdx(_queryIdx), imgIdx(_imgIdx), likelihood(_likelihood), match(
82  _match) {
83  }
84 
85  int queryIdx; //query index
86  int imgIdx; //test index
87 
88  double likelihood; //raw loglikelihood
89  double match; //normalised probability
90 
91  bool operator<(const IMatch& m) const {
92  return match < m.match;
93  }
94 
95 };
96 
97 /*
98  Base FabMap class. Each FabMap method inherits from this class.
99 */
100 class CV_EXPORTS FabMap {
101 public:
102 
103  //FabMap options
104  enum {
105  MEAN_FIELD = 1,
106  SAMPLED = 2,
107  NAIVE_BAYES = 4,
108  CHOW_LIU = 8,
109  MOTION_MODEL = 16
110  };
111 
112  FabMap(const Mat& clTree, double PzGe, double PzGNe, int flags,
113  int numSamples = 0);
114  virtual ~FabMap();
115 
116  //methods to add training data for sampling method
117  virtual void addTraining(const Mat& queryImgDescriptor);
118  virtual void addTraining(const vector<Mat>& queryImgDescriptors);
119 
120  //methods to add to the test data
121  virtual void add(const Mat& queryImgDescriptor);
122  virtual void add(const vector<Mat>& queryImgDescriptors);
123 
124  //accessors
125  const vector<Mat>& getTrainingImgDescriptors() const;
126  const vector<Mat>& getTestImgDescriptors() const;
127 
128  //Main FabMap image comparison
129  void compare(const Mat& queryImgDescriptor,
130  vector<IMatch>& matches, bool addQuery = false,
131  const Mat& mask = Mat());
132  void compare(const Mat& queryImgDescriptor,
133  const Mat& testImgDescriptors, vector<IMatch>& matches,
134  const Mat& mask = Mat());
135  void compare(const Mat& queryImgDescriptor,
136  const vector<Mat>& testImgDescriptors,
137  vector<IMatch>& matches, const Mat& mask = Mat());
138  void compare(const vector<Mat>& queryImgDescriptors, vector<
139  IMatch>& matches, bool addQuery = false, const Mat& mask =
140  Mat());
141  void compare(const vector<Mat>& queryImgDescriptors,
142  const vector<Mat>& testImgDescriptors,
143  vector<IMatch>& matches, const Mat& mask = Mat());
144 
145 protected:
146 
147  void compareImgDescriptor(const Mat& queryImgDescriptor,
148  int queryIndex, const vector<Mat>& testImgDescriptors,
149  vector<IMatch>& matches);
150 
151  void addImgDescriptor(const Mat& queryImgDescriptor);
152 
153  //the getLikelihoods method is overwritten for each different FabMap
154  //method.
155  virtual void getLikelihoods(const Mat& queryImgDescriptor,
156  const vector<Mat>& testImgDescriptors,
157  vector<IMatch>& matches);
158  virtual double getNewPlaceLikelihood(const Mat& queryImgDescriptor);
159 
160  //turn likelihoods into probabilities (also add in motion model if used)
161  void normaliseDistribution(vector<IMatch>& matches);
162 
163  //Chow-Liu Tree
164  int pq(int q);
165  double Pzq(int q, bool zq);
166  double PzqGzpq(int q, bool zq, bool zpq);
167 
168  //FAB-MAP Core
169  double PzqGeq(bool zq, bool eq);
170  double PeqGL(int q, bool Lzq, bool eq);
171  double PzqGL(int q, bool zq, bool zpq, bool Lzq);
172  double PzqGzpqL(int q, bool zq, bool zpq, bool Lzq);
173  double (FabMap::*PzGL)(int q, bool zq, bool zpq, bool Lzq);
174 
175  //data
178  vector<Mat> testImgDescriptors;
179  vector<IMatch> priorMatches;
180 
181  //parameters
182  double PzGe;
183  double PzGNe;
184  double Pnew;
185 
186  double mBias;
187  double sFactor;
188 
189  int flags;
191 
192 };
193 
194 /*
195  The original FAB-MAP algorithm, developed based on:
196  http://ijr.sagepub.com/content/27/6/647.short
197 */
198 class CV_EXPORTS FabMap1: public FabMap {
199 public:
200  FabMap1(const Mat& clTree, double PzGe, double PzGNe, int flags,
201  int numSamples = 0);
202  virtual ~FabMap1();
203 protected:
204 
205  //FabMap1 implementation of likelihood comparison
206  void getLikelihoods(const Mat& queryImgDescriptor, const vector<
207  Mat>& testImgDescriptors, vector<IMatch>& matches);
208 };
209 
210 /*
211  A computationally faster version of the original FAB-MAP algorithm. A look-
212  up-table is used to precompute many of the reoccuring calculations
213 */
214 class CV_EXPORTS FabMapLUT: public FabMap {
215 public:
216  FabMapLUT(const Mat& clTree, double PzGe, double PzGNe,
217  int flags, int numSamples = 0, int precision = 6);
218  virtual ~FabMapLUT();
219 protected:
220 
221  //FabMap look-up-table implementation of the likelihood comparison
222  void getLikelihoods(const Mat& queryImgDescriptor, const vector<
223  Mat>& testImgDescriptors, vector<IMatch>& matches);
224 
225  //precomputed data
226  int (*table)[8];
227 
228  //data precision
230 };
231 
232 /*
233  The Accelerated FAB-MAP algorithm, developed based on:
234  http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5613942
235 */
236 class CV_EXPORTS FabMapFBO: public FabMap {
237 public:
238  FabMapFBO(const Mat& clTree, double PzGe, double PzGNe, int flags,
239  int numSamples = 0, double rejectionThreshold = 1e-8, double PsGd =
240  1e-8, int bisectionStart = 512, int bisectionIts = 9);
241  virtual ~FabMapFBO();
242 
243 protected:
244 
245  //FabMap Fast Bail-out implementation of the likelihood comparison
246  void getLikelihoods(const Mat& queryImgDescriptor, const vector<
247  Mat>& testImgDescriptors, vector<IMatch>& matches);
248 
249  //stucture used to determine word comparison order
250  struct WordStats {
252  q(0), info(0), V(0), M(0) {
253  }
254 
255  WordStats(int _q, double _info) :
256  q(_q), info(_info), V(0), M(0) {
257  }
258 
259  int q;
260  double info;
261  mutable double V;
262  mutable double M;
263 
264  bool operator<(const WordStats& w) const {
265  return info < w.info;
266  }
267 
268  };
269 
270  //private fast bail-out necessary functions
271  void setWordStatistics(const Mat& queryImgDescriptor, multiset<WordStats>& wordData);
272  double limitbisection(double v, double m);
273  double bennettInequality(double v, double m, double delta);
274  static bool compInfo(const WordStats& first, const WordStats& second);
275 
276  //parameters
277  double PsGd;
281 };
282 
283 /*
284  The FAB-MAP2.0 algorithm, developed based on:
285  http://ijr.sagepub.com/content/30/9/1100.abstract
286 */
287 class CV_EXPORTS FabMap2: public FabMap {
288 public:
289 
290  FabMap2(const Mat& clTree, double PzGe, double PzGNe, int flags);
291  virtual ~FabMap2();
292 
293  //FabMap2 builds the inverted index and requires an additional training/test
294  //add function
295  void addTraining(const Mat& queryImgDescriptors) {
296  FabMap::addTraining(queryImgDescriptors);
297  }
298  void addTraining(const vector<Mat>& queryImgDescriptors);
299 
300  void add(const Mat& queryImgDescriptors) {
301  FabMap::add(queryImgDescriptors);
302  }
303  void add(const vector<Mat>& queryImgDescriptors);
304 
305 protected:
306 
307  //FabMap2 implementation of the likelihood comparison
308  void getLikelihoods(const Mat& queryImgDescriptor, const vector<
309  Mat>& testImgDescriptors, vector<IMatch>& matches);
310  double getNewPlaceLikelihood(const Mat& queryImgDescriptor);
311 
312  //the likelihood function using the inverted index
313  void getIndexLikelihoods(const Mat& queryImgDescriptor, vector<
314  double>& defaults, map<int, vector<int> >& invertedMap,
315  vector<IMatch>& matches);
316  void addToIndex(const Mat& queryImgDescriptor,
317  vector<double>& defaults,
318  map<int, vector<int> >& invertedMap);
319 
320  //data
321  vector<double> d1, d2, d3, d4;
322  vector<vector<int> > children;
323 
324  // TODO: inverted map a vector?
325 
326  vector<double> trainingDefaults;
327  map<int, vector<int> > trainingInvertedMap;
328 
329  vector<double> testDefaults;
330  map<int, vector<int> > testInvertedMap;
331 
332 };
333 /*
334  A Chow-Liu tree is required by FAB-MAP. The Chow-Liu tree provides an
335  estimate of the full distribution of visual words using a minimum spanning
336  tree. The tree is generated through training data.
337 */
338 class CV_EXPORTS ChowLiuTree {
339 public:
340  ChowLiuTree();
341  virtual ~ChowLiuTree();
342 
343  //add data to the chow-liu tree before calling make
344  void add(const Mat& imgDescriptor);
345  void add(const vector<Mat>& imgDescriptors);
346 
347  const vector<Mat>& getImgDescriptors() const;
348 
349  Mat make(double infoThreshold = 0.0);
350 
351 private:
352  vector<Mat> imgDescriptors;
353  Mat mergedImgDescriptors;
354 
355  typedef struct info {
356  float score;
357  short word1;
358  short word2;
359  } info;
360 
361  //probabilities extracted from mergedImgDescriptors
362  double P(int a, bool za);
363  double JP(int a, bool za, int b, bool zb); //a & b
364  double CP(int a, bool za, int b, bool zb); // a | b
365 
366  //calculating mutual information of all edges
367  void createBaseEdges(list<info>& edges, double infoThreshold);
368  double calcMutInfo(int word1, int word2);
369  static bool sortInfoScores(const info& first, const info& second);
370 
371  //selecting minimum spanning egdges with maximum information
372  bool reduceEdgesToMinSpan(list<info>& edges);
373 
374  //building the tree sctructure
375  Mat buildTree(int root_word, list<info> &edges);
376  void recAddToTree(Mat &cltree, int q, int pq,
377  list<info> &remaining_edges);
378  vector<int> extractChildren(list<info> &remaining_edges, int q);
379 
380 };
381 
382 /*
383  A custom vocabulary training method based on:
384  http://www.springerlink.com/content/d1h6j8x552532003/
385 */
386 class CV_EXPORTS BOWMSCTrainer: public BOWTrainer {
387 public:
388  BOWMSCTrainer(double clusterSize = 0.4);
389  virtual ~BOWMSCTrainer();
390 
391  // Returns trained vocabulary (i.e. cluster centers).
392  virtual Mat cluster() const;
393  virtual Mat cluster(const Mat& descriptors) const;
394 
395 protected:
396 
397  double clusterSize;
398 
399 };
400 
401 }
402 
403 }
404 
405 #endif /* OPENFABMAP_H_ */
CvArr CvPoint2D32f double M
Definition: imgproc_c.h:186
WordStats()
Definition: openfabmap.hpp:251
CvArr * edges
Definition: imgproc_c.h:555
vector< Mat > trainingImgDescriptors
Definition: openfabmap.hpp:177
double PzGNe
Definition: openfabmap.hpp:183
map< int, vector< int > > testInvertedMap
Definition: openfabmap.hpp:330
Definition: openfabmap.hpp:198
vector< vector< int > > children
Definition: openfabmap.hpp:322
int queryIdx
Definition: openfabmap.hpp:85
Definition: openfabmap.hpp:236
int int int flags
Definition: highgui_c.h:186
void add(const Mat &queryImgDescriptors)
Definition: openfabmap.hpp:300
WordStats(int _q, double _info)
Definition: openfabmap.hpp:255
vector< IMatch > priorMatches
Definition: openfabmap.hpp:179
Definition: features2d.hpp:1531
Definition: openfabmap.hpp:338
double sFactor
Definition: openfabmap.hpp:187
int flags
Definition: openfabmap.hpp:189
Definition: openfabmap.hpp:250
GLenum GLsizei GLenum GLenum const GLvoid * table
double PsGd
Definition: openfabmap.hpp:277
int q
Definition: openfabmap.hpp:259
virtual void add(const Mat &queryImgDescriptor)
Mat clTree
Definition: openfabmap.hpp:176
int bisectionIts
Definition: openfabmap.hpp:280
vector< double > trainingDefaults
Definition: openfabmap.hpp:326
GLint * first
Definition: legacy.hpp:1133
GLdouble GLdouble GLdouble GLdouble q
bool operator<(const IMatch &m) const
Definition: openfabmap.hpp:91
CvSize int int int CvPoint int delta
Definition: core_c.h:1427
virtual void addTraining(const Mat &queryImgDescriptor)
double likelihood
Definition: openfabmap.hpp:88
int bisectionStart
Definition: openfabmap.hpp:279
IMatch()
Definition: openfabmap.hpp:77
const GLdouble * v
The Core Functionality.
GLboolean GLboolean GLboolean b
Definition: legacy.hpp:633
The n-dimensional matrix class.
Definition: core.hpp:1688
double V
Definition: openfabmap.hpp:261
const CvArr const CvArr * V
Definition: core_c.h:733
const CvArr CvSeq CvSeq ** descriptors
Definition: compat.hpp:647
vector< double > testDefaults
Definition: openfabmap.hpp:329
vector< Mat > testImgDescriptors
Definition: openfabmap.hpp:178
double clusterSize
Definition: openfabmap.hpp:397
void addTraining(const Mat &queryImgDescriptors)
Definition: openfabmap.hpp:295
double rejectionThreshold
Definition: openfabmap.hpp:278
double Pnew
Definition: openfabmap.hpp:184
Definition: openfabmap.hpp:100
GLboolean GLboolean GLboolean GLboolean a
Definition: legacy.hpp:633
map< int, vector< int > > trainingInvertedMap
Definition: openfabmap.hpp:327
Definition: openfabmap.hpp:386
double M
Definition: openfabmap.hpp:262
int precision
Definition: openfabmap.hpp:229
double mBias
Definition: openfabmap.hpp:186
int int int * second
Definition: legacy.hpp:1115
Definition: openfabmap.hpp:75
::max::max int
Definition: functional.hpp:324
GLubyte GLubyte GLubyte GLubyte w
CV_EXPORTS_W void add(InputArray src1, InputArray src2, OutputArray dst, InputArray mask=noArray(), int dtype=-1)
adds one matrix to another (dst = src1 + src2)
vector< double > d4
Definition: openfabmap.hpp:321
Definition: openfabmap.hpp:214
const GLfloat * m
double info
Definition: openfabmap.hpp:260
IMatch(int _queryIdx, int _imgIdx, double _likelihood, double _match)
Definition: openfabmap.hpp:80
Definition: openfabmap.hpp:287
GLenum GLint GLuint mask
Definition: tracking.hpp:132
CV_EXPORTS_W void compare(InputArray src1, InputArray src2, OutputArray dst, int cmpop)
compares elements of two arrays (dst = src1 src2)
CvFileNode * map
Definition: core_c.h:1584
int numSamples
Definition: openfabmap.hpp:190
double match
Definition: openfabmap.hpp:89
int imgIdx
Definition: openfabmap.hpp:86
bool operator<(const WordStats &w) const
Definition: openfabmap.hpp:264
short float uchar uchar uchar uchar uchar ushort int uchar ushort int float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float int int int float int int int float int CV_CUDEV_IMPLEMENT_VEC_BINARY_OP char CV_CUDEV_IMPLEMENT_VEC_BINARY_OP ushort CV_CUDEV_IMPLEMENT_VEC_BINARY_OP short CV_CUDEV_IMPLEMENT_VEC_BINARY_OP int CV_CUDEV_IMPLEMENT_VEC_BINARY_OP uint CV_CUDEV_IMPLEMENT_VEC_BINARY_OP float CV_CUDEV_IMPLEMENT_VEC_BINARY_OP double int int uint double
Definition: vec_math.hpp:432
double PzGe
Definition: openfabmap.hpp:182