modules/contrib/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_ */