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.hpp"
  56 #include "opencv2/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 /*
  69     Return data format of a FABMAP compare call
  70 */
  71 struct CV_EXPORTS IMatch {
  72
  73     IMatch() :
  74         queryIdx(-1), imgIdx(-1), likelihood(-DBL_MAX), match(-DBL_MAX) {
  75     }
  76     IMatch(int _queryIdx, int _imgIdx, double _likelihood, double _match) :
  77         queryIdx(_queryIdx), imgIdx(_imgIdx), likelihood(_likelihood), match(
  78                 _match) {
  79     }
  80
  81     int queryIdx;    //query index
  82     int imgIdx;      //test index
  83
  84     double likelihood;  //raw loglikelihood
  85     double match;      //normalised probability
  86
  87     bool operator<(const IMatch& m) const {
  88         return match < m.match;
  89     }
  90
  91 };
  92
  93 /*
  94     Base FabMap class. Each FabMap method inherits from this class.
  95 */
  96 class CV_EXPORTS FabMap {
  97 public:
  98
  99     //FabMap options
 100     enum {
 101         MEAN_FIELD = 1,
 102         SAMPLED = 2,
 103         NAIVE_BAYES = 4,
 104         CHOW_LIU = 8,
 105         MOTION_MODEL = 16
 106     };
 107
 108     FabMap(const Mat& clTree, double PzGe, double PzGNe, int flags,
 109             int numSamples = 0);
 110     virtual ~FabMap();
 111
 112     //methods to add training data for sampling method
 113     virtual void addTraining(const Mat& queryImgDescriptor);
 114     virtual void addTraining(const std::vector<Mat>& queryImgDescriptors);
 115
 116     //methods to add to the test data
 117     virtual void add(const Mat& queryImgDescriptor);
 118     virtual void add(const std::vector<Mat>& queryImgDescriptors);
 119
 120     //accessors
 121     const std::vector<Mat>& getTrainingImgDescriptors() const;
 122     const std::vector<Mat>& getTestImgDescriptors() const;
 123
 124     //Main FabMap image comparison
 125     void compare(const Mat& queryImgDescriptor,
 126             std::vector<IMatch>& matches, bool addQuery = false,
 127             const Mat& mask = Mat());
 128     void compare(const Mat& queryImgDescriptor,
 129             const Mat& testImgDescriptors, std::vector<IMatch>& matches,
 130             const Mat& mask = Mat());
 131     void compare(const Mat& queryImgDescriptor,
 132             const std::vector<Mat>& testImgDescriptors,
 133             std::vector<IMatch>& matches, const Mat& mask = Mat());
 134     void compare(const std::vector<Mat>& queryImgDescriptors, std::vector<
 135             IMatch>& matches, bool addQuery = false, const Mat& mask =
 136             Mat());
 137     void compare(const std::vector<Mat>& queryImgDescriptors,
 138             const std::vector<Mat>& testImgDescriptors,
 139             std::vector<IMatch>& matches, const Mat& mask = Mat());
 140
 141 protected:
 142
 143     void compareImgDescriptor(const Mat& queryImgDescriptor,
 144             int queryIndex, const std::vector<Mat>& testImgDescriptors,
 145             std::vector<IMatch>& matches);
 146
 147     void addImgDescriptor(const Mat& queryImgDescriptor);
 148
 149     //the getLikelihoods method is overwritten for each different FabMap
 150     //method.
 151     virtual void getLikelihoods(const Mat& queryImgDescriptor,
 152             const std::vector<Mat>& testImgDescriptors,
 153             std::vector<IMatch>& matches);
 154     virtual double getNewPlaceLikelihood(const Mat& queryImgDescriptor);
 155
 156     //turn likelihoods into probabilities (also add in motion model if used)
 157     void normaliseDistribution(std::vector<IMatch>& matches);
 158
 159     //Chow-Liu Tree
 160     int pq(int q);
 161     double Pzq(int q, bool zq);
 162     double PzqGzpq(int q, bool zq, bool zpq);
 163
 164     //FAB-MAP Core
 165     double PzqGeq(bool zq, bool eq);
 166     double PeqGL(int q, bool Lzq, bool eq);
 167     double PzqGL(int q, bool zq, bool zpq, bool Lzq);
 168     double PzqGzpqL(int q, bool zq, bool zpq, bool Lzq);
 169     double (FabMap::*PzGL)(int q, bool zq, bool zpq, bool Lzq);
 170
 171     //data
 172     Mat clTree;
 173     std::vector<Mat> trainingImgDescriptors;
 174     std::vector<Mat> testImgDescriptors;
 175     std::vector<IMatch> priorMatches;
 176
 177     //parameters
 178     double PzGe;
 179     double PzGNe;
 180     double Pnew;
 181
 182     double mBias;
 183     double sFactor;
 184
 185     int flags;
 186     int numSamples;
 187
 188 };
 189
 190 /*
 191     The original FAB-MAP algorithm, developed based on:
 192     http://ijr.sagepub.com/content/27/6/647.short
 193 */
 194 class CV_EXPORTS FabMap1: public FabMap {
 195 public:
 196     FabMap1(const Mat& clTree, double PzGe, double PzGNe, int flags,
 197             int numSamples = 0);
 198     virtual ~FabMap1();
 199 protected:
 200
 201     //FabMap1 implementation of likelihood comparison
 202     void getLikelihoods(const Mat& queryImgDescriptor, const std::vector<
 203             Mat>& testImgDescriptors, std::vector<IMatch>& matches);
 204 };
 205
 206 /*
 207     A computationally faster version of the original FAB-MAP algorithm. A look-
 208     up-table is used to precompute many of the reoccuring calculations
 209 */
 210 class CV_EXPORTS FabMapLUT: public FabMap {
 211 public:
 212     FabMapLUT(const Mat& clTree, double PzGe, double PzGNe,
 213             int flags, int numSamples = 0, int precision = 6);
 214     virtual ~FabMapLUT();
 215 protected:
 216
 217     //FabMap look-up-table implementation of the likelihood comparison
 218     void getLikelihoods(const Mat& queryImgDescriptor, const std::vector<
 219             Mat>& testImgDescriptors, std::vector<IMatch>& matches);
 220
 221     //precomputed data
 222     int (*table)[8];
 223
 224     //data precision
 225     int precision;
 226 };
 227
 228 /*
 229     The Accelerated FAB-MAP algorithm, developed based on:
 230     http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5613942
 231 */
 232 class CV_EXPORTS FabMapFBO: public FabMap {
 233 public:
 234     FabMapFBO(const Mat& clTree, double PzGe, double PzGNe, int flags,
 235             int numSamples = 0, double rejectionThreshold = 1e-8, double PsGd =
 236                     1e-8, int bisectionStart = 512, int bisectionIts = 9);
 237     virtual ~FabMapFBO();
 238
 239 protected:
 240
 241     //FabMap Fast Bail-out implementation of the likelihood comparison
 242     void getLikelihoods(const Mat& queryImgDescriptor, const std::vector<
 243             Mat>& testImgDescriptors, std::vector<IMatch>& matches);
 244
 245     //stucture used to determine word comparison order
 246     struct WordStats {
 247         WordStats() :
 248             q(0), info(0), V(0), M(0) {
 249         }
 250
 251         WordStats(int _q, double _info) :
 252             q(_q), info(_info), V(0), M(0) {
 253         }
 254
 255         int q;
 256         double info;
 257         mutable double V;
 258         mutable double M;
 259
 260         bool operator<(const WordStats& w) const {
 261             return info < w.info;
 262         }
 263
 264     };
 265
 266     //private fast bail-out necessary functions
 267     void setWordStatistics(const Mat& queryImgDescriptor, std::multiset<WordStats>& wordData);
 268     double limitbisection(double v, double m);
 269     double bennettInequality(double v, double m, double delta);
 270     static bool compInfo(const WordStats& first, const WordStats& second);
 271
 272     //parameters
 273     double PsGd;
 274     double rejectionThreshold;
 275     int bisectionStart;
 276     int bisectionIts;
 277 };
 278
 279 /*
 280     The FAB-MAP2.0 algorithm, developed based on:
 281     http://ijr.sagepub.com/content/30/9/1100.abstract
 282 */
 283 class CV_EXPORTS FabMap2: public FabMap {
 284 public:
 285
 286     FabMap2(const Mat& clTree, double PzGe, double PzGNe, int flags);
 287     virtual ~FabMap2();
 288
 289     //FabMap2 builds the inverted index and requires an additional training/test
 290     //add function
 291     void addTraining(const Mat& queryImgDescriptors) {
 292         FabMap::addTraining(queryImgDescriptors);
 293     }
 294     void addTraining(const std::vector<Mat>& queryImgDescriptors);
 295
 296     void add(const Mat& queryImgDescriptors) {
 297         FabMap::add(queryImgDescriptors);
 298     }
 299     void add(const std::vector<Mat>& queryImgDescriptors);
 300
 301 protected:
 302
 303     //FabMap2 implementation of the likelihood comparison
 304     void getLikelihoods(const Mat& queryImgDescriptor, const std::vector<
 305             Mat>& testImgDescriptors, std::vector<IMatch>& matches);
 306     double getNewPlaceLikelihood(const Mat& queryImgDescriptor);
 307
 308     //the likelihood function using the inverted index
 309     void getIndexLikelihoods(const Mat& queryImgDescriptor, std::vector<
 310                              double>& defaults, std::map<int, std::vector<int> >& invertedMap,
 311             std::vector<IMatch>& matches);
 312     void addToIndex(const Mat& queryImgDescriptor,
 313             std::vector<double>& defaults,
 314             std::map<int, std::vector<int> >& invertedMap);
 315
 316     //data
 317     std::vector<double> d1, d2, d3, d4;
 318     std::vector<std::vector<int> > children;
 319
 320     // TODO: inverted map a vector?
 321
 322     std::vector<double> trainingDefaults;
 323     std::map<int, std::vector<int> > trainingInvertedMap;
 324
 325     std::vector<double> testDefaults;
 326     std::map<int, std::vector<int> > testInvertedMap;
 327
 328 };
 329 /*
 330     A Chow-Liu tree is required by FAB-MAP. The Chow-Liu tree provides an
 331     estimate of the full distribution of visual words using a minimum spanning
 332     tree. The tree is generated through training data.
 333 */
 334 class CV_EXPORTS ChowLiuTree {
 335 public:
 336     ChowLiuTree();
 337     virtual ~ChowLiuTree();
 338
 339     //add data to the chow-liu tree before calling make
 340     void add(const Mat& imgDescriptor);
 341     void add(const std::vector<Mat>& imgDescriptors);
 342
 343     const std::vector<Mat>& getImgDescriptors() const;
 344
 345     Mat make(double infoThreshold = 0.0);
 346
 347 private:
 348     std::vector<Mat> imgDescriptors;
 349     Mat mergedImgDescriptors;
 350
 351     typedef struct info {
 352         float score;
 353         short word1;
 354         short word2;
 355     } info;
 356
 357     //probabilities extracted from mergedImgDescriptors
 358     double P(int a, bool za);
 359     double JP(int a, bool za, int b, bool zb); //a & b
 360     double CP(int a, bool za, int b, bool zb); // a | b
 361
 362     //calculating mutual information of all edges
 363     void createBaseEdges(std::list<info>& edges, double infoThreshold);
 364     double calcMutInfo(int word1, int word2);
 365     static bool sortInfoScores(const info& first, const info& second);
 366
 367     //selecting minimum spanning egdges with maximum information
 368     bool reduceEdgesToMinSpan(std::list<info>& edges);
 369
 370     //building the tree sctructure
 371     Mat buildTree(int root_word, std::list<info> &edges);
 372     void recAddToTree(Mat &cltree, int q, int pq,
 373         std::list<info> &remaining_edges);
 374     std::vector<int> extractChildren(std::list<info> &remaining_edges, int q);
 375
 376 };
 377
 378 /*
 379     A custom vocabulary training method based on:
 380     http://www.springerlink.com/content/d1h6j8x552532003/
 381 */
 382 class CV_EXPORTS BOWMSCTrainer: public BOWTrainer {
 383 public:
 384     BOWMSCTrainer(double clusterSize = 0.4);
 385     virtual ~BOWMSCTrainer();
 386
 387     // Returns trained vocabulary (i.e. cluster centers).
 388     virtual Mat cluster() const;
 389     virtual Mat cluster(const Mat& descriptors) const;
 390
 391 protected:
 392
 393     double clusterSize;
 394
 395 };
 396
 397 }
 398
 399 }
 400
 401 #endif /* OPENFABMAP_H_ */