1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
9 // This file originates from the openFABMAP project:
10 // [http://code.google.com/p/openfabmap/]
12 // For published work which uses all or part of OpenFABMAP, please cite:
13 // [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6224843]
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]
22 // Copyright (C) 2012 Arren Glover [aj.glover@qut.edu.au] and
23 // Will Maddern [w.maddern@qut.edu.au], all rights reserved.
26 // Redistribution and use in source and binary forms, with or without modification,
27 // are permitted provided that the following conditions are met:
29 // * Redistribution's of source code must retain the above copyright notice,
30 // this list of conditions and the following disclaimer.
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.
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.
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.
52 #ifndef __OPENCV_OPENFABMAP_H_
53 #define __OPENCV_OPENFABMAP_H_
55 #include "opencv2/core.hpp"
56 #include "opencv2/features2d.hpp"
69 Return data format of a FABMAP compare call
71 struct CV_EXPORTS IMatch {
74 queryIdx(-1), imgIdx(-1), likelihood(-DBL_MAX), match(-DBL_MAX) {
76 IMatch(int _queryIdx, int _imgIdx, double _likelihood, double _match) :
77 queryIdx(_queryIdx), imgIdx(_imgIdx), likelihood(_likelihood), match(
81 int queryIdx; //query index
82 int imgIdx; //test index
84 double likelihood; //raw loglikelihood
85 double match; //normalised probability
87 bool operator<(const IMatch& m) const {
88 return match < m.match;
94 Base FabMap class. Each FabMap method inherits from this class.
96 class CV_EXPORTS FabMap {
108 FabMap(const Mat& clTree, double PzGe, double PzGNe, int flags,
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);
116 //methods to add to the test data
117 virtual void add(const Mat& queryImgDescriptor);
118 virtual void add(const std::vector<Mat>& queryImgDescriptors);
121 const std::vector<Mat>& getTrainingImgDescriptors() const;
122 const std::vector<Mat>& getTestImgDescriptors() const;
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 =
137 void compare(const std::vector<Mat>& queryImgDescriptors,
138 const std::vector<Mat>& testImgDescriptors,
139 std::vector<IMatch>& matches, const Mat& mask = Mat());
143 void compareImgDescriptor(const Mat& queryImgDescriptor,
144 int queryIndex, const std::vector<Mat>& testImgDescriptors,
145 std::vector<IMatch>& matches);
147 void addImgDescriptor(const Mat& queryImgDescriptor);
149 //the getLikelihoods method is overwritten for each different FabMap
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);
156 //turn likelihoods into probabilities (also add in motion model if used)
157 void normaliseDistribution(std::vector<IMatch>& matches);
161 double Pzq(int q, bool zq);
162 double PzqGzpq(int q, bool zq, bool zpq);
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);
173 std::vector<Mat> trainingImgDescriptors;
174 std::vector<Mat> testImgDescriptors;
175 std::vector<IMatch> priorMatches;
191 The original FAB-MAP algorithm, developed based on:
192 http://ijr.sagepub.com/content/27/6/647.short
194 class CV_EXPORTS FabMap1: public FabMap {
196 FabMap1(const Mat& clTree, double PzGe, double PzGNe, int flags,
201 //FabMap1 implementation of likelihood comparison
202 void getLikelihoods(const Mat& queryImgDescriptor, const std::vector<
203 Mat>& testImgDescriptors, std::vector<IMatch>& matches);
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
210 class CV_EXPORTS FabMapLUT: public FabMap {
212 FabMapLUT(const Mat& clTree, double PzGe, double PzGNe,
213 int flags, int numSamples = 0, int precision = 6);
214 virtual ~FabMapLUT();
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);
229 The Accelerated FAB-MAP algorithm, developed based on:
230 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5613942
232 class CV_EXPORTS FabMapFBO: public FabMap {
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();
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);
245 //stucture used to determine word comparison order
248 q(0), info(0), V(0), M(0) {
251 WordStats(int _q, double _info) :
252 q(_q), info(_info), V(0), M(0) {
260 bool operator<(const WordStats& w) const {
261 return info < w.info;
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);
274 double rejectionThreshold;
280 The FAB-MAP2.0 algorithm, developed based on:
281 http://ijr.sagepub.com/content/30/9/1100.abstract
283 class CV_EXPORTS FabMap2: public FabMap {
286 FabMap2(const Mat& clTree, double PzGe, double PzGNe, int flags);
289 //FabMap2 builds the inverted index and requires an additional training/test
291 void addTraining(const Mat& queryImgDescriptors) {
292 FabMap::addTraining(queryImgDescriptors);
294 void addTraining(const std::vector<Mat>& queryImgDescriptors);
296 void add(const Mat& queryImgDescriptors) {
297 FabMap::add(queryImgDescriptors);
299 void add(const std::vector<Mat>& queryImgDescriptors);
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);
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);
317 std::vector<double> d1, d2, d3, d4;
318 std::vector<std::vector<int> > children;
320 // TODO: inverted map a vector?
322 std::vector<double> trainingDefaults;
323 std::map<int, std::vector<int> > trainingInvertedMap;
325 std::vector<double> testDefaults;
326 std::map<int, std::vector<int> > testInvertedMap;
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.
334 class CV_EXPORTS ChowLiuTree {
337 virtual ~ChowLiuTree();
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);
343 const std::vector<Mat>& getImgDescriptors() const;
345 Mat make(double infoThreshold = 0.0);
348 std::vector<Mat> imgDescriptors;
349 Mat mergedImgDescriptors;
351 typedef struct info {
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
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);
367 //selecting minimum spanning egdges with maximum information
368 bool reduceEdgesToMinSpan(std::list<info>& edges);
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);
379 A custom vocabulary training method based on:
380 http://www.springerlink.com/content/d1h6j8x552532003/
382 class CV_EXPORTS BOWMSCTrainer: public BOWTrainer {
384 BOWMSCTrainer(double clusterSize = 0.4);
385 virtual ~BOWMSCTrainer();
387 // Returns trained vocabulary (i.e. cluster centers).
388 virtual Mat cluster() const;
389 virtual Mat cluster(const Mat& descriptors) const;
401 #endif /* OPENFABMAP_H_ */