git.maemo.org Git - opencv/blob - 3rdparty/flann/flann.hpp

   1 /***********************************************************************
   2  * Software License Agreement (BSD License)
   3  *
   4  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
   5  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
   6  *
   7  * THE BSD LICENSE
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *************************************************************************/
  30
  31 #ifndef FLANN_HPP_
  32 #define FLANN_HPP_
  33
  34 #include <vector>
  35 #include <string>
  36
  37 #include "constants.h"
  38 #include "common.h"
  39 #include "matrix.h"
  40
  41 #include "flann.h"
  42
  43 namespace flann
  44 {
  45
  46 class NNIndex;
  47
  48 class IndexFactory
  49 {
  50 public:
  51     virtual ~IndexFactory() {}
  52         virtual NNIndex* createIndex(const Matrix<float>& dataset) const = 0;
  53 };
  54
  55 struct IndexParams : public IndexFactory {
  56 protected:
  57         IndexParams() {};
  58
  59 public:
  60
  61         static IndexParams* createFromParameters(const FLANNParameters& p);
  62
  63         void fromParameters(const FLANNParameters&) {};
  64         void toParameters(FLANNParameters&) { };
  65 };
  66
  67 struct LinearIndexParams : public IndexParams {
  68         LinearIndexParams() {};
  69
  70         NNIndex* createIndex(const Matrix<float>& dataset) const;
  71 };
  72
  73
  74
  75 struct KDTreeIndexParams : public IndexParams {
  76         KDTreeIndexParams(int trees_ = 4) : trees(trees_) {};
  77
  78         int trees;                 // number of randomized trees to use (for kdtree)
  79
  80         NNIndex* createIndex(const Matrix<float>& dataset) const;
  81
  82         void fromParameters(const FLANNParameters& p)
  83         {
  84                 trees = p.trees;
  85         }
  86
  87         void toParameters(FLANNParameters& p)
  88         {
  89                 p.algorithm = KDTREE;
  90                 p.trees = trees;
  91         };
  92
  93 };
  94
  95 struct KMeansIndexParams : public IndexParams {
  96         KMeansIndexParams(int branching_ = 32, int iterations_ = 11,
  97                         flann_centers_init_t centers_init_ = CENTERS_RANDOM, float cb_index_ = 0.2 ) :
  98                 branching(branching_),
  99                 iterations(iterations_),
 100                 centers_init(centers_init_),
 101                 cb_index(cb_index_) {};
 102
 103         int branching;             // branching factor (for kmeans tree)
 104         int iterations;            // max iterations to perform in one kmeans clustering (kmeans tree)
 105         flann_centers_init_t centers_init;          // algorithm used for picking the initial cluster centers for kmeans tree
 106     float cb_index;            // cluster boundary index. Used when searching the kmeans tree
 107
 108
 109     NNIndex* createIndex(const Matrix<float>& dataset) const;
 110
 111         void fromParameters(const FLANNParameters& p)
 112         {
 113                 branching = p.branching;
 114                 iterations = p.iterations;
 115                 centers_init = p.centers_init;
 116                 cb_index = p.cb_index;
 117         }
 118
 119         void toParameters(FLANNParameters& p)
 120         {
 121                 p.algorithm = KMEANS;
 122                 p.branching = branching;
 123                 p.iterations = iterations;
 124                 p.centers_init = centers_init;
 125                 p.cb_index = cb_index;
 126         };
 127
 128 };
 129
 130
 131 struct CompositeIndexParams : public IndexParams {
 132         CompositeIndexParams(int trees_ = 4, int branching_ = 32, int iterations_ = 11,
 133                         flann_centers_init_t centers_init_ = CENTERS_RANDOM, float cb_index_ = 0.2 ) :
 134                 trees(trees_),
 135                 branching(branching_),
 136                 iterations(iterations_),
 137                 centers_init(centers_init_),
 138                 cb_index(cb_index_) {};
 139
 140         int trees;                 // number of randomized trees to use (for kdtree)
 141         int branching;             // branching factor (for kmeans tree)
 142         int iterations;            // max iterations to perform in one kmeans clustering (kmeans tree)
 143         flann_centers_init_t centers_init;          // algorithm used for picking the initial cluster centers for kmeans tree
 144     float cb_index;            // cluster boundary index. Used when searching the kmeans tree
 145
 146     NNIndex* createIndex(const Matrix<float>& dataset) const;
 147
 148         void fromParameters(const FLANNParameters& p)
 149         {
 150                 trees = p.trees;
 151                 branching = p.branching;
 152                 iterations = p.iterations;
 153                 centers_init = p.centers_init;
 154                 cb_index = p.cb_index;
 155         }
 156
 157         void toParameters(FLANNParameters& p)
 158         {
 159                 p.algorithm = COMPOSITE;
 160                 p.trees = trees;
 161                 p.branching = branching;
 162                 p.iterations = iterations;
 163                 p.centers_init = centers_init;
 164                 p.cb_index = cb_index;
 165         };
 166 };
 167
 168
 169 struct AutotunedIndexParams : public IndexParams {
 170         AutotunedIndexParams( float target_precision_ = 0.9, float build_weight_ = 0.01,
 171                         float memory_weight_ = 0, float sample_fraction_ = 0.1) :
 172                 target_precision(target_precision_),
 173                 build_weight(build_weight_),
 174                 memory_weight(memory_weight_),
 175                 sample_fraction(sample_fraction_) {};
 176
 177         float target_precision;    // precision desired (used for autotuning, -1 otherwise)
 178         float build_weight;        // build tree time weighting factor
 179         float memory_weight;       // index memory weighting factor
 180     float sample_fraction;     // what fraction of the dataset to use for autotuning
 181
 182     NNIndex* createIndex(const Matrix<float>& dataset) const;
 183
 184         void fromParameters(const FLANNParameters& p)
 185         {
 186                 target_precision = p.target_precision;
 187                 build_weight = p.build_weight;
 188                 memory_weight = p.memory_weight;
 189                 sample_fraction = p.sample_fraction;
 190         }
 191
 192         void toParameters(FLANNParameters& p)
 193         {
 194                 p.algorithm = AUTOTUNED;
 195                 p.target_precision = target_precision;
 196                 p.build_weight = build_weight;
 197                 p.memory_weight = memory_weight;
 198                 p.sample_fraction = sample_fraction;
 199         };
 200 };
 201
 202
 203 struct SavedIndexParams : public IndexParams {
 204         SavedIndexParams() {
 205                 throw FLANNException("I don't know which index to load");
 206         }
 207         SavedIndexParams(std::string filename_) : filename(filename_) {}
 208
 209         std::string filename;           // filename of the stored index
 210
 211         NNIndex* createIndex(const Matrix<float>& dataset) const;
 212 };
 213
 214
 215 struct SearchParams {
 216         SearchParams(int checks_ = 32) :
 217                 checks(checks_) {};
 218
 219         int checks;
 220 };
 221
 222
 223 class Index {
 224         NNIndex* nnIndex;
 225
 226 public:
 227         Index(const Matrix<float>& features, const IndexParams& params);
 228
 229         ~Index();
 230
 231         void knnSearch(const Matrix<float>& queries, Matrix<int>& indices, Matrix<float>& dists, int knn, const SearchParams& params);
 232
 233         int radiusSearch(const Matrix<float>& query, Matrix<int> indices, Matrix<float> dists, float radius, const SearchParams& params);
 234
 235         void save(std::string filename);
 236
 237         int veclen() const;
 238
 239         int size() const;
 240 };
 241
 242
 243 int hierarchicalClustering(const Matrix<float>& features, Matrix<float>& centers, const KMeansIndexParams& params);
 244
 245
 246 }
 247 #endif /* FLANN_HPP_ */