OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / flann / flann_base.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 OPENCV_FLANN_BASE_HPP_
32 #define OPENCV_FLANN_BASE_HPP_
33
34 #include <vector>
35 #include <string>
36 #include <cassert>
37 #include <cstdio>
38
39 #include "general.h"
40 #include "matrix.h"
41 #include "params.h"
42 #include "saving.h"
43
44 #include "all_indices.h"
45
46 namespace cvflann
47 {
48
49 /**
50  * Sets the log level used for all flann functions
51  * @param level Verbosity level
52  */
53 inline void log_verbosity(int level)
54 {
55     if (level >= 0) {
56         Logger::setLevel(level);
57     }
58 }
59
60 /**
61  * (Deprecated) Index parameters for creating a saved index.
62  */
63 struct SavedIndexParams : public IndexParams
64 {
65     SavedIndexParams(std::string filename)
66     {
67         (* this)["algorithm"] = FLANN_INDEX_SAVED;
68         (*this)["filename"] = filename;
69     }
70 };
71
72
73 template<typename Distance>
74 NNIndex<Distance>* load_saved_index(const Matrix<typename Distance::ElementType>& dataset, const std::string& filename, Distance distance)
75 {
76     typedef typename Distance::ElementType ElementType;
77
78     FILE* fin = fopen(filename.c_str(), "rb");
79     if (fin == NULL) {
80         return NULL;
81     }
82     IndexHeader header = load_header(fin);
83     if (header.data_type != Datatype<ElementType>::type()) {
84         throw FLANNException("Datatype of saved index is different than of the one to be created.");
85     }
86     if ((size_t(header.rows) != dataset.rows)||(size_t(header.cols) != dataset.cols)) {
87         throw FLANNException("The index saved belongs to a different dataset");
88     }
89
90     IndexParams params;
91     params["algorithm"] = header.index_type;
92     NNIndex<Distance>* nnIndex = create_index_by_type<Distance>(dataset, params, distance);
93     nnIndex->loadIndex(fin);
94     fclose(fin);
95
96     return nnIndex;
97 }
98
99
100 template<typename Distance>
101 class Index : public NNIndex<Distance>
102 {
103 public:
104     typedef typename Distance::ElementType ElementType;
105     typedef typename Distance::ResultType DistanceType;
106
107     Index(const Matrix<ElementType>& features, const IndexParams& params, Distance distance = Distance() )
108         : index_params_(params)
109     {
110         flann_algorithm_t index_type = get_param<flann_algorithm_t>(params,"algorithm");
111         loaded_ = false;
112
113         if (index_type == FLANN_INDEX_SAVED) {
114             nnIndex_ = load_saved_index<Distance>(features, get_param<std::string>(params,"filename"), distance);
115             loaded_ = true;
116         }
117         else {
118             nnIndex_ = create_index_by_type<Distance>(features, params, distance);
119         }
120     }
121
122     ~Index()
123     {
124         delete nnIndex_;
125     }
126
127     /**
128      * Builds the index.
129      */
130     void buildIndex()
131     {
132         if (!loaded_) {
133             nnIndex_->buildIndex();
134         }
135     }
136
137     void save(std::string filename)
138     {
139         FILE* fout = fopen(filename.c_str(), "wb");
140         if (fout == NULL) {
141             throw FLANNException("Cannot open file");
142         }
143         save_header(fout, *nnIndex_);
144         saveIndex(fout);
145         fclose(fout);
146     }
147
148     /**
149      * \brief Saves the index to a stream
150      * \param stream The stream to save the index to
151      */
152     virtual void saveIndex(FILE* stream)
153     {
154         nnIndex_->saveIndex(stream);
155     }
156
157     /**
158      * \brief Loads the index from a stream
159      * \param stream The stream from which the index is loaded
160      */
161     virtual void loadIndex(FILE* stream)
162     {
163         nnIndex_->loadIndex(stream);
164     }
165
166     /**
167      * \returns number of features in this index.
168      */
169     size_t veclen() const
170     {
171         return nnIndex_->veclen();
172     }
173
174     /**
175      * \returns The dimensionality of the features in this index.
176      */
177     size_t size() const
178     {
179         return nnIndex_->size();
180     }
181
182     /**
183      * \returns The index type (kdtree, kmeans,...)
184      */
185     flann_algorithm_t getType() const
186     {
187         return nnIndex_->getType();
188     }
189
190     /**
191      * \returns The amount of memory (in bytes) used by the index.
192      */
193     virtual int usedMemory() const
194     {
195         return nnIndex_->usedMemory();
196     }
197
198
199     /**
200      * \returns The index parameters
201      */
202     IndexParams getParameters() const
203     {
204         return nnIndex_->getParameters();
205     }
206
207     /**
208      * \brief Perform k-nearest neighbor search
209      * \param[in] queries The query points for which to find the nearest neighbors
210      * \param[out] indices The indices of the nearest neighbors found
211      * \param[out] dists Distances to the nearest neighbors found
212      * \param[in] knn Number of nearest neighbors to return
213      * \param[in] params Search parameters
214      */
215     void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params)
216     {
217         nnIndex_->knnSearch(queries, indices, dists, knn, params);
218     }
219
220     /**
221      * \brief Perform radius search
222      * \param[in] query The query point
223      * \param[out] indices The indinces of the neighbors found within the given radius
224      * \param[out] dists The distances to the nearest neighbors found
225      * \param[in] radius The radius used for search
226      * \param[in] params Search parameters
227      * \returns Number of neighbors found
228      */
229     int radiusSearch(const Matrix<ElementType>& query, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params)
230     {
231         return nnIndex_->radiusSearch(query, indices, dists, radius, params);
232     }
233
234     /**
235      * \brief Method that searches for nearest-neighbours
236      */
237     void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams)
238     {
239         nnIndex_->findNeighbors(result, vec, searchParams);
240     }
241
242     /**
243      * \brief Returns actual index
244      */
245     FLANN_DEPRECATED NNIndex<Distance>* getIndex()
246     {
247         return nnIndex_;
248     }
249
250     /**
251      * \brief Returns index parameters.
252      * \deprecated use getParameters() instead.
253      */
254     FLANN_DEPRECATED  const IndexParams* getIndexParameters()
255     {
256         return &index_params_;
257     }
258
259 private:
260     /** Pointer to actual index class */
261     NNIndex<Distance>* nnIndex_;
262     /** Indices if the index was loaded from a file */
263     bool loaded_;
264     /** Parameters passed to the index */
265     IndexParams index_params_;
266 };
267
268 /**
269  * Performs a hierarchical clustering of the points passed as argument and then takes a cut in the
270  * the clustering tree to return a flat clustering.
271  * @param[in] points Points to be clustered
272  * @param centers The computed cluster centres. Matrix should be preallocated and centers.rows is the
273  *  number of clusters requested.
274  * @param params Clustering parameters (The same as for cvflann::KMeansIndex)
275  * @param d Distance to be used for clustering (eg: cvflann::L2)
276  * @return number of clusters computed (can be different than clusters.rows and is the highest number
277  * of the form (branching-1)*K+1 smaller than clusters.rows).
278  */
279 template <typename Distance>
280 int hierarchicalClustering(const Matrix<typename Distance::ElementType>& points, Matrix<typename Distance::ResultType>& centers,
281                            const KMeansIndexParams& params, Distance d = Distance())
282 {
283     KMeansIndex<Distance> kmeans(points, params, d);
284     kmeans.buildIndex();
285
286     int clusterNum = kmeans.getClusterCenters(centers);
287     return clusterNum;
288 }
289
290 }
291 #endif /* OPENCV_FLANN_BASE_HPP_ */