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

   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_H
  32 #define FLANN_H
  33
  34
  35 #include "constants.h"
  36
  37
  38 #ifdef WIN32
  39 /* win32 dll export/import directives */
  40 #ifdef flann_EXPORTS
  41 #define LIBSPEC __declspec(dllexport)
  42 #else
  43 #define LIBSPEC __declspec(dllimport)
  44 #endif
  45 #else
  46 /* unix needs nothing */
  47 #define LIBSPEC
  48 #endif
  49
  50
  51
  52
  53
  54 struct FLANNParameters {
  55         flann_algorithm_t algorithm; // the algorithm to use (see constants.h)
  56
  57         int checks;                // how many leafs (features) to check in one search
  58     float cb_index;            // cluster boundary index. Used when searching the kmeans tree
  59         int trees;                 // number of randomized trees to use (for kdtree)
  60         int branching;             // branching factor (for kmeans tree)
  61         int iterations;            // max iterations to perform in one kmeans cluetering (kmeans tree)
  62         flann_centers_init_t centers_init;          // algorithm used for picking the initial cluetr centers for kmeans tree
  63         float target_precision;    // precision desired (used for autotuning, -1 otherwise)
  64         float build_weight;        // build tree time weighting factor
  65         float memory_weight;       // index memory weigthing factor
  66     float sample_fraction;     // what fraction of the dataset to use for autotuning
  67
  68     flann_log_level_t log_level;             // determines the verbosity of each flann function
  69         char* log_destination;     // file where the output should go, NULL for the console
  70         long random_seed;          // random seed to use
  71 };
  72
  73
  74
  75 typedef void* FLANN_INDEX; // deprecated
  76 typedef void* flann_index_t;
  77
  78 #ifdef __cplusplus
  79 extern "C" {
  80 #endif
  81
  82 /**
  83 Sets the log level used for all flann functions (unless
  84 specified in FLANNParameters for each call
  85
  86 Params:
  87     level = verbosity level (defined in constants.h)
  88 */
  89 LIBSPEC void flann_log_verbosity(int level);
  90
  91
  92 /**
  93  * Sets the distance type to use throughout FLANN.
  94  * If distance type specified is MINKOWSKI, the second argument
  95  * specifies which order the minkowski distance should have.
  96  */
  97 LIBSPEC void flann_set_distance_type(flann_distance_t distance_type, int order);
  98
  99
 100 /**
 101 Builds and returns an index. It uses autotuning if the target_precision field of index_params
 102 is between 0 and 1, or the parameters specified if it's -1.
 103
 104 Params:
 105     dataset = pointer to a data set stored in row major order
 106     rows = number of rows (features) in the dataset
 107     cols = number of columns in the dataset (feature dimensionality)
 108     speedup = speedup over linear search, estimated if using autotuning, output parameter
 109     index_params = index related parameters
 110     flann_params = generic flann parameters
 111
 112 Returns: the newly created index or a number <0 for error
 113 */
 114 LIBSPEC FLANN_INDEX flann_build_index(float* dataset,
 115                                                                           int rows,
 116                                                                           int cols,
 117                                                                           float* speedup,
 118                                                                           struct FLANNParameters* flann_params);
 119
 120
 121
 122
 123
 124 /**
 125  * Saves the index to a file. Only the index is saved into the file, the dataset corresponding to the index is not saved.
 126  *
 127  * @param index_id The index that should be saved
 128  * @param filename The filename the index should be saved to
 129  * @return Returns 0 on success, negative value on error.
 130  */
 131 LIBSPEC int flann_save_index(FLANN_INDEX index_id,
 132                                                          char* filename);
 133
 134
 135 /**
 136  * Loads an index from a file.
 137  *
 138  * @param filename File to load the index from.
 139  * @param dataset The dataset corresponding to the index.
 140  * @param rows Dataset tors
 141  * @param cols Dataset columns
 142  * @return
 143  */
 144 LIBSPEC FLANN_INDEX flann_load_index(char* filename,
 145                                                                          float* dataset,
 146                                                                          int rows,
 147                                                                          int cols);
 148
 149
 150
 151 /**
 152 Builds an index and uses it to find nearest neighbors.
 153
 154 Params:
 155     dataset = pointer to a data set stored in row major order
 156     rows = number of rows (features) in the dataset
 157     cols = number of columns in the dataset (feature dimensionality)
 158     testset = pointer to a query set stored in row major order
 159     trows = number of rows (features) in the query dataset (same dimensionality as features in the dataset)
 160     indices = pointer to matrix for the indices of the nearest neighbors of the testset features in the dataset
 161             (must have trows number of rows and nn number of columns)
 162     nn = how many nearest neighbors to return
 163     index_params = index related parameters
 164     flann_params = generic flann parameters
 165
 166 Returns: zero or -1 for error
 167 */
 168 LIBSPEC int flann_find_nearest_neighbors(float* dataset,
 169                                                                                  int rows,
 170                                                                                  int cols,
 171                                                                                  float* testset,
 172                                                                                  int trows,
 173                                                                                  int* indices,
 174                                                                                  float* dists,
 175                                                                                  int nn,
 176                                                                                  struct FLANNParameters* flann_params);
 177
 178
 179
 180 /**
 181 Searches for nearest neighbors using the index provided
 182
 183 Params:
 184     index_id = the index (constructed previously using flann_build_index).
 185     testset = pointer to a query set stored in row major order
 186     trows = number of rows (features) in the query dataset (same dimensionality as features in the dataset)
 187     indices = pointer to matrix for the indices of the nearest neighbors of the testset features in the dataset
 188             (must have trows number of rows and nn number of columns)
 189     nn = how many nearest neighbors to return
 190     checks = number of checks to perform before the search is stopped
 191     flann_params = generic flann parameters
 192
 193 Returns: zero or a number <0 for error
 194 */
 195 LIBSPEC int flann_find_nearest_neighbors_index(FLANN_INDEX index_id,
 196                                                                                            float* testset,
 197                                                                                            int trows,
 198                                                                                            int* indices,
 199                                                                                            float* dists,
 200                                                                                            int nn,
 201                                                                                            int checks,
 202                                                                                            struct FLANNParameters* flann_params);
 203
 204
 205
 206 /**
 207  * Performs an radius search using an already constructed index.
 208  *
 209  * In case of radius search, instead of always returning a predetermined
 210  * number of nearest neighbours (for example the 10 nearest neighbours), the
 211  * search will return all the neighbours found within a search radius
 212  * of the query point.
 213  *
 214  * The check parameter in the function below sets the level of approximation
 215  * for the search by only visiting "checks" number of features in the index
 216  * (the same way as for the KNN search). A lower value for checks will give
 217  * a higher search speedup at the cost of potentially not returning all the
 218  * neighbours in the specified radius.
 219  */
 220 LIBSPEC int flann_radius_search(FLANN_INDEX index_ptr, /* the index */
 221                                                                                 float* query,   /* query point */
 222                                                                                 int* indices, /* array for storing the indices found (will be modified) */
 223                                                                                 float* dists, /* similar, but for storing distances */
 224                                                                                 int max_nn,  /* size of arrays indices and dists */
 225                                                                                 float radius, /* search radius (squared radius for euclidian metric) */
 226                                                                                 int checks,  /* number of features to check, sets the level of approximation */
 227                                                                                 FLANNParameters* flann_params);
 228
 229
 230 /**
 231 Deletes an index and releases the memory used by it.
 232
 233 Params:
 234     index_id = the index (constructed previously using flann_build_index).
 235     flann_params = generic flann parameters
 236
 237 Returns: zero or a number <0 for error
 238 */
 239 LIBSPEC int flann_free_index(FLANN_INDEX index_id,
 240                                      struct FLANNParameters* flann_params);
 241
 242 /**
 243 Clusters the features in the dataset using a hierarchical kmeans clustering approach.
 244 This is significantly faster than using a flat kmeans clustering for a large number
 245 of clusters.
 246
 247 Params:
 248     dataset = pointer to a data set stored in row major order
 249     rows = number of rows (features) in the dataset
 250     cols = number of columns in the dataset (feature dimensionality)
 251     clusters = number of cluster to compute
 252     result = memory buffer where the output cluster centers are storred
 253     index_params = used to specify the kmeans tree parameters (branching factor, max number of iterations to use)
 254     flann_params = generic flann parameters
 255
 256 Returns: number of clusters computed or a number <0 for error. This number can be different than the number of clusters requested, due to the
 257     way hierarchical clusters are computed. The number of clusters returned will be the highest number of the form
 258     (branch_size-1)*K+1 smaller than the number of clusters requested.
 259 */
 260
 261 LIBSPEC int flann_compute_cluster_centers(float* dataset,
 262                                                                                   int rows,
 263                                                                                   int cols,
 264                                                                                   int clusters,
 265                                                                                   float* result,
 266                                                                                   struct FLANNParameters* flann_params);
 267
 268
 269 #ifdef __cplusplus
 270 };
 271
 272
 273 #include "flann.hpp"
 274
 275 #endif
 276
 277
 278 #endif /*FLANN_H*/