1 /***********************************************************************
2 * Software License Agreement (BSD License)
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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 *************************************************************************/
35 #include "constants.h"
39 /* win32 dll export/import directives */
41 #define LIBSPEC __declspec(dllexport)
43 #define LIBSPEC __declspec(dllimport)
46 /* unix needs nothing */
54 struct FLANNParameters {
55 flann_algorithm_t algorithm; // the algorithm to use (see constants.h)
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
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
75 typedef void* FLANN_INDEX; // deprecated
76 typedef void* flann_index_t;
83 Sets the log level used for all flann functions (unless
84 specified in FLANNParameters for each call
87 level = verbosity level (defined in constants.h)
89 LIBSPEC void flann_log_verbosity(int level);
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.
97 LIBSPEC void flann_set_distance_type(flann_distance_t distance_type, int order);
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.
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
112 Returns: the newly created index or a number <0 for error
114 LIBSPEC FLANN_INDEX flann_build_index(float* dataset,
118 struct FLANNParameters* flann_params);
125 * Saves the index to a file. Only the index is saved into the file, the dataset corresponding to the index is not saved.
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.
131 LIBSPEC int flann_save_index(FLANN_INDEX index_id,
136 * Loads an index from a file.
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
144 LIBSPEC FLANN_INDEX flann_load_index(char* filename,
152 Builds an index and uses it to find nearest neighbors.
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
166 Returns: zero or -1 for error
168 LIBSPEC int flann_find_nearest_neighbors(float* dataset,
176 struct FLANNParameters* flann_params);
181 Searches for nearest neighbors using the index provided
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
193 Returns: zero or a number <0 for error
195 LIBSPEC int flann_find_nearest_neighbors_index(FLANN_INDEX index_id,
202 struct FLANNParameters* flann_params);
207 * Performs an radius search using an already constructed index.
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.
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.
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);
231 Deletes an index and releases the memory used by it.
234 index_id = the index (constructed previously using flann_build_index).
235 flann_params = generic flann parameters
237 Returns: zero or a number <0 for error
239 LIBSPEC int flann_free_index(FLANN_INDEX index_id,
240 struct FLANNParameters* flann_params);
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
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
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.
261 LIBSPEC int flann_compute_cluster_centers(float* dataset,
266 struct FLANNParameters* flann_params);