git.maemo.org Git - opencv/blob - 3rdparty/include/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 public:
  59
  60         static IndexParams* createFromParameters(const FLANNParameters& p);
  61
  62         void fromParameters(const FLANNParameters&) {};
  63         void toParameters(FLANNParameters&) { };
  64 };
  65
  66 struct LinearIndexParams : public IndexParams {
  67         LinearIndexParams() {};
  68
  69         NNIndex* createIndex(const Matrix<float>& dataset) const;
  70 };
  71
  72
  73
  74 struct KDTreeIndexParams : public IndexParams {
  75         KDTreeIndexParams(int trees_ = 4) : trees(trees_) {};
  76
  77         int trees;                 // number of randomized trees to use (for kdtree)
  78
  79         NNIndex* createIndex(const Matrix<float>& dataset) const;
  80
  81         void fromParameters(const FLANNParameters& p)
  82         {
  83                 trees = p.trees;
  84         }
  85
  86         void toParameters(FLANNParameters& p)
  87         {
  88                 p.algorithm = KDTREE;
  89                 p.trees = trees;
  90         };
  91
  92 };
  93
  94 struct KMeansIndexParams : public IndexParams {
  95         KMeansIndexParams(int branching_ = 32, int iterations_ = 11,
  96                         flann_centers_init_t centers_init_ = CENTERS_RANDOM, float cb_index_ = 0.2 ) :
  97                 branching(branching_),
  98                 iterations(iterations_),
  99                 centers_init(centers_init_),
 100                 cb_index(cb_index_) {};
 101
 102         int branching;             // branching factor (for kmeans tree)
 103         int iterations;            // max iterations to perform in one kmeans clustering (kmeans tree)
 104         flann_centers_init_t centers_init;          // algorithm used for picking the initial cluster centers for kmeans tree
 105     float cb_index;            // cluster boundary index. Used when searching the kmeans tree
 106
 107
 108     NNIndex* createIndex(const Matrix<float>& dataset) const;
 109
 110         void fromParameters(const FLANNParameters& p)
 111         {
 112                 branching = p.branching;
 113                 iterations = p.iterations;
 114                 centers_init = p.centers_init;
 115                 cb_index = p.cb_index;
 116         }
 117
 118         void toParameters(FLANNParameters& p)
 119         {
 120                 p.algorithm = KMEANS;
 121                 p.branching = branching;
 122                 p.iterations = iterations;
 123                 p.centers_init = centers_init;
 124                 p.cb_index = cb_index;
 125         };
 126
 127 };
 128
 129
 130 struct CompositeIndexParams : public IndexParams {
 131         CompositeIndexParams(int trees_ = 4, int branching_ = 32, int iterations_ = 11,
 132                         flann_centers_init_t centers_init_ = CENTERS_RANDOM, float cb_index_ = 0.2 ) :
 133                 trees(trees_),
 134                 branching(branching_),
 135                 iterations(iterations_),
 136                 centers_init(centers_init_),
 137                 cb_index(cb_index_) {};
 138
 139         int trees;                 // number of randomized trees to use (for kdtree)
 140         int branching;             // branching factor (for kmeans tree)
 141         int iterations;            // max iterations to perform in one kmeans clustering (kmeans tree)
 142         flann_centers_init_t centers_init;          // algorithm used for picking the initial cluster centers for kmeans tree
 143     float cb_index;            // cluster boundary index. Used when searching the kmeans tree
 144
 145     NNIndex* createIndex(const Matrix<float>& dataset) const;
 146
 147         void fromParameters(const FLANNParameters& p)
 148         {
 149                 trees = p.trees;
 150                 branching = p.branching;
 151                 iterations = p.iterations;
 152                 centers_init = p.centers_init;
 153                 cb_index = p.cb_index;
 154         }
 155
 156         void toParameters(FLANNParameters& p)
 157         {
 158                 p.algorithm = COMPOSITE;
 159                 p.trees = trees;
 160                 p.branching = branching;
 161                 p.iterations = iterations;
 162                 p.centers_init = centers_init;
 163                 p.cb_index = cb_index;
 164         };
 165 };
 166
 167
 168 struct AutotunedIndexParams : public IndexParams {
 169         AutotunedIndexParams( float target_precision_ = 0.9, float build_weight_ = 0.01,
 170                         float memory_weight_ = 0, float sample_fraction_ = 0.1) :
 171                 target_precision(target_precision_),
 172                 build_weight(build_weight_),
 173                 memory_weight(memory_weight_),
 174                 sample_fraction(sample_fraction_) {};
 175
 176         float target_precision;    // precision desired (used for autotuning, -1 otherwise)
 177         float build_weight;        // build tree time weighting factor
 178         float memory_weight;       // index memory weighting factor
 179     float sample_fraction;     // what fraction of the dataset to use for autotuning
 180
 181     NNIndex* createIndex(const Matrix<float>& dataset) const;
 182
 183         void fromParameters(const FLANNParameters& p)
 184         {
 185                 target_precision = p.target_precision;
 186                 build_weight = p.build_weight;
 187                 memory_weight = p.memory_weight;
 188                 sample_fraction = p.sample_fraction;
 189         }
 190
 191         void toParameters(FLANNParameters& p)
 192         {
 193                 p.algorithm = AUTOTUNED;
 194                 p.target_precision = target_precision;
 195                 p.build_weight = build_weight;
 196                 p.memory_weight = memory_weight;
 197                 p.sample_fraction = sample_fraction;
 198         };
 199 };
 200
 201
 202 struct SavedIndexParams : public IndexParams {
 203         SavedIndexParams() {
 204                 throw FLANNException("I don't know which index to load");
 205         }
 206         SavedIndexParams(std::string filename_) : filename(filename_) {}
 207
 208         std::string filename;           // filename of the stored index
 209
 210         NNIndex* createIndex(const Matrix<float>& dataset) const;
 211 };
 212
 213
 214 struct SearchParams {
 215         SearchParams(int checks_ = 32) :
 216                 checks(checks_) {};
 217
 218         int checks;
 219 };
 220
 221
 222 class Index {
 223         NNIndex* nnIndex;
 224
 225 public:
 226         Index(const Matrix<float>& features, const IndexParams& params);
 227
 228         ~Index();
 229
 230         void knnSearch(const Matrix<float>& queries, Matrix<int>& indices, Matrix<float>& dists, int knn, const SearchParams& params);
 231
 232         int radiusSearch(const Matrix<float>& query, Matrix<int> indices, Matrix<float> dists, float radius, const SearchParams& params);
 233
 234         void save(std::string filename);
 235
 236         int veclen() const;
 237
 238         int size() const;
 239 };
 240
 241
 242 int hierarchicalClustering(const Matrix<float>& features, Matrix<float>& centers, const KMeansIndexParams& params);
 243
 244
 245 }
 246 #endif /* FLANN_HPP_ */