/*M///////////////////////////////////////////////////////////////////////////////////////
//
// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
// By downloading, copying, installing or using the software you agree to this license.
// If you do not agree to this license, do not download, install,
// copy or use the software.
//
// This file originates from the openFABMAP project:
// [http://code.google.com/p/openfabmap/]
//
// For published work which uses all or part of OpenFABMAP, please cite:
// [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6224843]
//
// Original Algorithm by Mark Cummins and Paul Newman:
// [http://ijr.sagepub.com/content/27/6/647.short]
// [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5613942]
// [http://ijr.sagepub.com/content/30/9/1100.abstract]
//
// License Agreement
//
// Copyright (C) 2012 Arren Glover [aj.glover@qut.edu.au] and
// Will Maddern [w.maddern@qut.edu.au], all rights reserved.
//
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
// * Redistribution's of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
//
// * Redistribution's in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// * The name of the copyright holders may not be used to endorse or promote products
// derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/
#ifndef __OPENCV_OPENFABMAP_H_
#define __OPENCV_OPENFABMAP_H_
#include "opencv2/core/core.hpp"
#include "opencv2/features2d/features2d.hpp"
#include <vector>
#include <list>
#include <map>
#include <set>
#include <valarray>
namespace cv {
namespace of2 {
using std::list;
using std::map;
using std::multiset;
/*
Return data format of a FABMAP compare call
*/
struct CV_EXPORTS IMatch {
IMatch() :
queryIdx(-1), imgIdx(-1), likelihood(-DBL_MAX), match(-DBL_MAX) {
}
IMatch(int _queryIdx, int _imgIdx, double _likelihood, double _match) :
queryIdx(_queryIdx), imgIdx(_imgIdx), likelihood(_likelihood), match(
_match) {
}
int queryIdx; //query index
int imgIdx; //test index
double likelihood; //raw loglikelihood
double match; //normalised probability
bool operator<(const IMatch& m) const {
return match < m.match;
}
};
/*
Base FabMap class. Each FabMap method inherits from this class.
*/
class CV_EXPORTS FabMap {
public:
//FabMap options
enum {
MEAN_FIELD = 1,
SAMPLED = 2,
NAIVE_BAYES = 4,
CHOW_LIU = 8,
MOTION_MODEL = 16
};
FabMap(const Mat& clTree, double PzGe, double PzGNe, int flags,
int numSamples = 0);
virtual ~FabMap();
//methods to add training data for sampling method
virtual void addTraining(const Mat& queryImgDescriptor);
virtual void addTraining(const vector<Mat>& queryImgDescriptors);
//methods to add to the test data
virtual void add(const Mat& queryImgDescriptor);
virtual void add(const vector<Mat>& queryImgDescriptors);
//accessors
const vector<Mat>& getTrainingImgDescriptors() const;
const vector<Mat>& getTestImgDescriptors() const;
//Main FabMap image comparison
void compare(const Mat& queryImgDescriptor,
vector<IMatch>& matches, bool addQuery = false,
const Mat& mask = Mat());
void compare(const Mat& queryImgDescriptor,
const Mat& testImgDescriptors, vector<IMatch>& matches,
const Mat& mask = Mat());
void compare(const Mat& queryImgDescriptor,
const vector<Mat>& testImgDescriptors,
vector<IMatch>& matches, const Mat& mask = Mat());
void compare(const vector<Mat>& queryImgDescriptors, vector<
IMatch>& matches, bool addQuery = false, const Mat& mask =
Mat());
void compare(const vector<Mat>& queryImgDescriptors,
const vector<Mat>& testImgDescriptors,
vector<IMatch>& matches, const Mat& mask = Mat());
protected:
void compareImgDescriptor(const Mat& queryImgDescriptor,
int queryIndex, const vector<Mat>& testImgDescriptors,
vector<IMatch>& matches);
void addImgDescriptor(const Mat& queryImgDescriptor);
//the getLikelihoods method is overwritten for each different FabMap
//method.
virtual void getLikelihoods(const Mat& queryImgDescriptor,
const vector<Mat>& testImgDescriptors,
vector<IMatch>& matches);
virtual double getNewPlaceLikelihood(const Mat& queryImgDescriptor);
//turn likelihoods into probabilities (also add in motion model if used)
void normaliseDistribution(vector<IMatch>& matches);
//Chow-Liu Tree
int pq(int q);
double Pzq(int q, bool zq);
double PzqGzpq(int q, bool zq, bool zpq);
//FAB-MAP Core
double PzqGeq(bool zq, bool eq);
double PeqGL(int q, bool Lzq, bool eq);
double PzqGL(int q, bool zq, bool zpq, bool Lzq);
double PzqGzpqL(int q, bool zq, bool zpq, bool Lzq);
double (FabMap::*PzGL)(int q, bool zq, bool zpq, bool Lzq);
//data
Mat clTree;
vector<Mat> trainingImgDescriptors;
vector<Mat> testImgDescriptors;
vector<IMatch> priorMatches;
//parameters
double PzGe;
double PzGNe;
double Pnew;
double mBias;
double sFactor;
int flags;
int numSamples;
};
/*
The original FAB-MAP algorithm, developed based on:
http://ijr.sagepub.com/content/27/6/647.short
*/
class CV_EXPORTS FabMap1: public FabMap {
public:
FabMap1(const Mat& clTree, double PzGe, double PzGNe, int flags,
int numSamples = 0);
virtual ~FabMap1();
protected:
//FabMap1 implementation of likelihood comparison
void getLikelihoods(const Mat& queryImgDescriptor, const vector<
Mat>& testImgDescriptors, vector<IMatch>& matches);
};
/*
A computationally faster version of the original FAB-MAP algorithm. A look-
up-table is used to precompute many of the reoccuring calculations
*/
class CV_EXPORTS FabMapLUT: public FabMap {
public:
FabMapLUT(const Mat& clTree, double PzGe, double PzGNe,
int flags, int numSamples = 0, int precision = 6);
virtual ~FabMapLUT();
protected:
//FabMap look-up-table implementation of the likelihood comparison
void getLikelihoods(const Mat& queryImgDescriptor, const vector<
Mat>& testImgDescriptors, vector<IMatch>& matches);
//precomputed data
int (*table)[8];
//data precision
int precision;
};
/*
The Accelerated FAB-MAP algorithm, developed based on:
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5613942
*/
class CV_EXPORTS FabMapFBO: public FabMap {
public:
FabMapFBO(const Mat& clTree, double PzGe, double PzGNe, int flags,
int numSamples = 0, double rejectionThreshold = 1e-8, double PsGd =
1e-8, int bisectionStart = 512, int bisectionIts = 9);
virtual ~FabMapFBO();
protected:
//FabMap Fast Bail-out implementation of the likelihood comparison
void getLikelihoods(const Mat& queryImgDescriptor, const vector<
Mat>& testImgDescriptors, vector<IMatch>& matches);
//stucture used to determine word comparison order
struct WordStats {
WordStats() :
q(0), info(0), V(0), M(0) {
}
WordStats(int _q, double _info) :
q(_q), info(_info), V(0), M(0) {
}
int q;
double info;
mutable double V;
mutable double M;
bool operator<(const WordStats& w) const {
return info < w.info;
}
};
//private fast bail-out necessary functions
void setWordStatistics(const Mat& queryImgDescriptor, multiset<WordStats>& wordData);
double limitbisection(double v, double m);
double bennettInequality(double v, double m, double delta);
static bool compInfo(const WordStats& first, const WordStats& second);
//parameters
double PsGd;
double rejectionThreshold;
int bisectionStart;
int bisectionIts;
};
/*
The FAB-MAP2.0 algorithm, developed based on:
http://ijr.sagepub.com/content/30/9/1100.abstract
*/
class CV_EXPORTS FabMap2: public FabMap {
public:
FabMap2(const Mat& clTree, double PzGe, double PzGNe, int flags);
virtual ~FabMap2();
//FabMap2 builds the inverted index and requires an additional training/test
//add function
void addTraining(const Mat& queryImgDescriptors) {
FabMap::addTraining(queryImgDescriptors);
}
void addTraining(const vector<Mat>& queryImgDescriptors);
void add(const Mat& queryImgDescriptors) {
FabMap::add(queryImgDescriptors);
}
void add(const vector<Mat>& queryImgDescriptors);
protected:
//FabMap2 implementation of the likelihood comparison
void getLikelihoods(const Mat& queryImgDescriptor, const vector<
Mat>& testImgDescriptors, vector<IMatch>& matches);
double getNewPlaceLikelihood(const Mat& queryImgDescriptor);
//the likelihood function using the inverted index
void getIndexLikelihoods(const Mat& queryImgDescriptor, vector<
double>& defaults, map<int, vector<int> >& invertedMap,
vector<IMatch>& matches);
void addToIndex(const Mat& queryImgDescriptor,
vector<double>& defaults,
map<int, vector<int> >& invertedMap);
//data
vector<double> d1, d2, d3, d4;
vector<vector<int> > children;
// TODO: inverted map a vector?
vector<double> trainingDefaults;
map<int, vector<int> > trainingInvertedMap;
vector<double> testDefaults;
map<int, vector<int> > testInvertedMap;
};
/*
A Chow-Liu tree is required by FAB-MAP. The Chow-Liu tree provides an
estimate of the full distribution of visual words using a minimum spanning
tree. The tree is generated through training data.
*/
class CV_EXPORTS ChowLiuTree {
public:
ChowLiuTree();
virtual ~ChowLiuTree();
//add data to the chow-liu tree before calling make
void add(const Mat& imgDescriptor);
void add(const vector<Mat>& imgDescriptors);
const vector<Mat>& getImgDescriptors() const;
Mat make(double infoThreshold = 0.0);
private:
vector<Mat> imgDescriptors;
Mat mergedImgDescriptors;
typedef struct info {
float score;
short word1;
short word2;
} info;
//probabilities extracted from mergedImgDescriptors
double P(int a, bool za);
double JP(int a, bool za, int b, bool zb); //a & b
double CP(int a, bool za, int b, bool zb); // a | b
//calculating mutual information of all edges
void createBaseEdges(list<info>& edges, double infoThreshold);
double calcMutInfo(int word1, int word2);
static bool sortInfoScores(const info& first, const info& second);
//selecting minimum spanning egdges with maximum information
bool reduceEdgesToMinSpan(list<info>& edges);
//building the tree sctructure
Mat buildTree(int root_word, list<info> &edges);
void recAddToTree(Mat &cltree, int q, int pq,
list<info> &remaining_edges);
vector<int> extractChildren(list<info> &remaining_edges, int q);
};
/*
A custom vocabulary training method based on:
http://www.springerlink.com/content/d1h6j8x552532003/
*/
class CV_EXPORTS BOWMSCTrainer: public BOWTrainer {
public:
BOWMSCTrainer(double clusterSize = 0.4);
virtual ~BOWMSCTrainer();
// Returns trained vocabulary (i.e. cluster centers).
virtual Mat cluster() const;
virtual Mat cluster(const Mat& descriptors) const;
protected:
double clusterSize;
};
}
}
#endif /* OPENFABMAP_H_ */
Submit an article or tip