OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / contrib / openfabmap.hpp
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"
56 #include "opencv2/features2d/features2d.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
176     Mat clTree;
177     vector<Mat> trainingImgDescriptors;
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;
190     int numSamples;
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
229     int 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 {
251         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;
278     double rejectionThreshold;
279     int bisectionStart;
280     int bisectionIts;
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_ */