OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / flann / flann.hpp
1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 //  By downloading, copying, installing or using the software you agree to this license.
6 //  If you do not agree to this license, do not download, install,
7 //  copy or use the software.
8 //
9 //
10 //                           License Agreement
11 //                For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
14 // Copyright (C) 2009, Willow Garage Inc., all rights reserved.
15 // Third party copyrights are property of their respective owners.
16 //
17 // Redistribution and use in source and binary forms, with or without modification,
18 // are permitted provided that the following conditions are met:
19 //
20 //   * Redistribution's of source code must retain the above copyright notice,
21 //     this list of conditions and the following disclaimer.
22 //
23 //   * Redistribution's in binary form must reproduce the above copyright notice,
24 //     this list of conditions and the following disclaimer in the documentation
25 //     and/or other materials provided with the distribution.
26 //
27 //   * The name of the copyright holders may not be used to endorse or promote products
28 //     derived from this software without specific prior written permission.
29 //
30 // This software is provided by the copyright holders and contributors "as is" and
31 // any express or implied warranties, including, but not limited to, the implied
32 // warranties of merchantability and fitness for a particular purpose are disclaimed.
33 // In no event shall the Intel Corporation or contributors be liable for any direct,
34 // indirect, incidental, special, exemplary, or consequential damages
35 // (including, but not limited to, procurement of substitute goods or services;
36 // loss of use, data, or profits; or business interruption) however caused
37 // and on any theory of liability, whether in contract, strict liability,
38 // or tort (including negligence or otherwise) arising in any way out of
39 // the use of this software, even if advised of the possibility of such damage.
40 //
41 //M*/
42
43 #ifndef _OPENCV_FLANN_HPP_
44 #define _OPENCV_FLANN_HPP_
45
46 #ifdef __cplusplus
47
48 #include "opencv2/core/types_c.h"
49 #include "opencv2/core/core.hpp"
50 #include "opencv2/flann/flann_base.hpp"
51 #include "opencv2/flann/miniflann.hpp"
52
53 namespace cvflann
54 {
55     CV_EXPORTS flann_distance_t flann_distance_type();
56     FLANN_DEPRECATED CV_EXPORTS void set_distance_type(flann_distance_t distance_type, int order);
57 }
58
59
60 namespace cv
61 {
62 namespace flann
63 {
64
65 template <typename T> struct CvType {};
66 template <> struct CvType<unsigned char> { static int type() { return CV_8U; } };
67 template <> struct CvType<char> { static int type() { return CV_8S; } };
68 template <> struct CvType<unsigned short> { static int type() { return CV_16U; } };
69 template <> struct CvType<short> { static int type() { return CV_16S; } };
70 template <> struct CvType<int> { static int type() { return CV_32S; } };
71 template <> struct CvType<float> { static int type() { return CV_32F; } };
72 template <> struct CvType<double> { static int type() { return CV_64F; } };
73
74
75 // bring the flann parameters into this namespace
76 using ::cvflann::get_param;
77 using ::cvflann::print_params;
78
79 // bring the flann distances into this namespace
80 using ::cvflann::L2_Simple;
81 using ::cvflann::L2;
82 using ::cvflann::L1;
83 using ::cvflann::MinkowskiDistance;
84 using ::cvflann::MaxDistance;
85 using ::cvflann::HammingLUT;
86 using ::cvflann::Hamming;
87 using ::cvflann::Hamming2;
88 using ::cvflann::HistIntersectionDistance;
89 using ::cvflann::HellingerDistance;
90 using ::cvflann::ChiSquareDistance;
91 using ::cvflann::KL_Divergence;
92
93
94
95 template <typename Distance>
96 class GenericIndex
97 {
98 public:
99         typedef typename Distance::ElementType ElementType;
100         typedef typename Distance::ResultType DistanceType;
101
102         GenericIndex(const Mat& features, const ::cvflann::IndexParams& params, Distance distance = Distance());
103
104         ~GenericIndex();
105
106         void knnSearch(const vector<ElementType>& query, vector<int>& indices,
107                        vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& params);
108         void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& params);
109
110         int radiusSearch(const vector<ElementType>& query, vector<int>& indices,
111                          vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& params);
112         int radiusSearch(const Mat& query, Mat& indices, Mat& dists,
113                          DistanceType radius, const ::cvflann::SearchParams& params);
114
115         void save(std::string filename) { nnIndex->save(filename); }
116
117         int veclen() const { return nnIndex->veclen(); }
118
119         int size() const { return nnIndex->size(); }
120
121         ::cvflann::IndexParams getParameters() { return nnIndex->getParameters(); }
122
123         FLANN_DEPRECATED const ::cvflann::IndexParams* getIndexParameters() { return nnIndex->getIndexParameters(); }
124
125 private:
126         ::cvflann::Index<Distance>* nnIndex;
127 };
128
129
130 #define FLANN_DISTANCE_CHECK \
131     if ( ::cvflann::flann_distance_type() != cvflann::FLANN_DIST_L2) { \
132         printf("[WARNING] You are using cv::flann::Index (or cv::flann::GenericIndex) and have also changed "\
133         "the distance using cvflann::set_distance_type. This is no longer working as expected "\
134         "(cv::flann::Index always uses L2). You should create the index templated on the distance, "\
135         "for example for L1 distance use: GenericIndex< L1<float> > \n"); \
136     }
137
138
139 template <typename Distance>
140 GenericIndex<Distance>::GenericIndex(const Mat& dataset, const ::cvflann::IndexParams& params, Distance distance)
141 {
142     CV_Assert(dataset.type() == CvType<ElementType>::type());
143     CV_Assert(dataset.isContinuous());
144     ::cvflann::Matrix<ElementType> m_dataset((ElementType*)dataset.ptr<ElementType>(0), dataset.rows, dataset.cols);
145
146     nnIndex = new ::cvflann::Index<Distance>(m_dataset, params, distance);
147
148     FLANN_DISTANCE_CHECK
149
150     nnIndex->buildIndex();
151 }
152
153 template <typename Distance>
154 GenericIndex<Distance>::~GenericIndex()
155 {
156     delete nnIndex;
157 }
158
159 template <typename Distance>
160 void GenericIndex<Distance>::knnSearch(const vector<ElementType>& query, vector<int>& indices, vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& searchParams)
161 {
162     ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
163     ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
164     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
165
166     FLANN_DISTANCE_CHECK
167
168     nnIndex->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
169 }
170
171
172 template <typename Distance>
173 void GenericIndex<Distance>::knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& searchParams)
174 {
175     CV_Assert(queries.type() == CvType<ElementType>::type());
176     CV_Assert(queries.isContinuous());
177     ::cvflann::Matrix<ElementType> m_queries((ElementType*)queries.ptr<ElementType>(0), queries.rows, queries.cols);
178
179     CV_Assert(indices.type() == CV_32S);
180     CV_Assert(indices.isContinuous());
181     ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
182
183     CV_Assert(dists.type() == CvType<DistanceType>::type());
184     CV_Assert(dists.isContinuous());
185     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
186
187     FLANN_DISTANCE_CHECK
188
189     nnIndex->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
190 }
191
192 template <typename Distance>
193 int GenericIndex<Distance>::radiusSearch(const vector<ElementType>& query, vector<int>& indices, vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
194 {
195     ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
196     ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
197     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
198
199     FLANN_DISTANCE_CHECK
200
201     return nnIndex->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
202 }
203
204 template <typename Distance>
205 int GenericIndex<Distance>::radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
206 {
207     CV_Assert(query.type() == CvType<ElementType>::type());
208     CV_Assert(query.isContinuous());
209     ::cvflann::Matrix<ElementType> m_query((ElementType*)query.ptr<ElementType>(0), query.rows, query.cols);
210
211     CV_Assert(indices.type() == CV_32S);
212     CV_Assert(indices.isContinuous());
213     ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
214
215     CV_Assert(dists.type() == CvType<DistanceType>::type());
216     CV_Assert(dists.isContinuous());
217     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
218
219     FLANN_DISTANCE_CHECK
220
221     return nnIndex->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
222 }
223
224 /**
225  * @deprecated Use GenericIndex class instead
226  */
227 template <typename T>
228 class
229 #ifndef _MSC_VER
230  FLANN_DEPRECATED
231 #endif
232  Index_ {
233 public:
234         typedef typename L2<T>::ElementType ElementType;
235         typedef typename L2<T>::ResultType DistanceType;
236
237     Index_(const Mat& features, const ::cvflann::IndexParams& params);
238
239     ~Index_();
240
241     void knnSearch(const vector<ElementType>& query, vector<int>& indices, vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& params);
242     void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& params);
243
244     int radiusSearch(const vector<ElementType>& query, vector<int>& indices, vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& params);
245     int radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& params);
246
247     void save(std::string filename)
248         {
249             if (nnIndex_L1) nnIndex_L1->save(filename);
250             if (nnIndex_L2) nnIndex_L2->save(filename);
251         }
252
253     int veclen() const
254     {
255             if (nnIndex_L1) return nnIndex_L1->veclen();
256             if (nnIndex_L2) return nnIndex_L2->veclen();
257         }
258
259     int size() const
260     {
261             if (nnIndex_L1) return nnIndex_L1->size();
262             if (nnIndex_L2) return nnIndex_L2->size();
263         }
264
265         ::cvflann::IndexParams getParameters()
266         {
267             if (nnIndex_L1) return nnIndex_L1->getParameters();
268             if (nnIndex_L2) return nnIndex_L2->getParameters();
269
270         }
271
272         FLANN_DEPRECATED const ::cvflann::IndexParams* getIndexParameters()
273         {
274             if (nnIndex_L1) return nnIndex_L1->getIndexParameters();
275             if (nnIndex_L2) return nnIndex_L2->getIndexParameters();
276         }
277
278 private:
279         // providing backwards compatibility for L2 and L1 distances (most common)
280         ::cvflann::Index< L2<ElementType> >* nnIndex_L2;
281         ::cvflann::Index< L1<ElementType> >* nnIndex_L1;
282 };
283
284 #ifdef _MSC_VER
285 template <typename T>
286 class FLANN_DEPRECATED Index_;
287 #endif
288
289 template <typename T>
290 Index_<T>::Index_(const Mat& dataset, const ::cvflann::IndexParams& params)
291 {
292     printf("[WARNING] The cv::flann::Index_<T> class is deperecated, use cv::flann::GenericIndex<Distance> instead\n");
293
294     CV_Assert(dataset.type() == CvType<ElementType>::type());
295     CV_Assert(dataset.isContinuous());
296     ::cvflann::Matrix<ElementType> m_dataset((ElementType*)dataset.ptr<ElementType>(0), dataset.rows, dataset.cols);
297
298     if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L2 ) {
299         nnIndex_L1 = NULL;
300         nnIndex_L2 = new ::cvflann::Index< L2<ElementType> >(m_dataset, params);
301     }
302     else if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L1 ) {
303         nnIndex_L1 = new ::cvflann::Index< L1<ElementType> >(m_dataset, params);
304         nnIndex_L2 = NULL;
305     }
306     else {
307         printf("[ERROR] cv::flann::Index_<T> only provides backwards compatibility for the L1 and L2 distances. "
308         "For other distance types you must use cv::flann::GenericIndex<Distance>\n");
309         CV_Assert(0);
310     }
311     if (nnIndex_L1) nnIndex_L1->buildIndex();
312     if (nnIndex_L2) nnIndex_L2->buildIndex();
313 }
314
315 template <typename T>
316 Index_<T>::~Index_()
317 {
318     if (nnIndex_L1) delete nnIndex_L1;
319     if (nnIndex_L2) delete nnIndex_L2;
320 }
321
322 template <typename T>
323 void Index_<T>::knnSearch(const vector<ElementType>& query, vector<int>& indices, vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& searchParams)
324 {
325     ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
326     ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
327     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
328
329     if (nnIndex_L1) nnIndex_L1->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
330     if (nnIndex_L2) nnIndex_L2->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
331 }
332
333
334 template <typename T>
335 void Index_<T>::knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& searchParams)
336 {
337     CV_Assert(queries.type() == CvType<ElementType>::type());
338     CV_Assert(queries.isContinuous());
339     ::cvflann::Matrix<ElementType> m_queries((ElementType*)queries.ptr<ElementType>(0), queries.rows, queries.cols);
340
341     CV_Assert(indices.type() == CV_32S);
342     CV_Assert(indices.isContinuous());
343     ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
344
345     CV_Assert(dists.type() == CvType<DistanceType>::type());
346     CV_Assert(dists.isContinuous());
347     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
348
349     if (nnIndex_L1) nnIndex_L1->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
350     if (nnIndex_L2) nnIndex_L2->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
351 }
352
353 template <typename T>
354 int Index_<T>::radiusSearch(const vector<ElementType>& query, vector<int>& indices, vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
355 {
356     ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
357     ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
358     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
359
360     if (nnIndex_L1) return nnIndex_L1->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
361     if (nnIndex_L2) return nnIndex_L2->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
362 }
363
364 template <typename T>
365 int Index_<T>::radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
366 {
367     CV_Assert(query.type() == CvType<ElementType>::type());
368     CV_Assert(query.isContinuous());
369     ::cvflann::Matrix<ElementType> m_query((ElementType*)query.ptr<ElementType>(0), query.rows, query.cols);
370
371     CV_Assert(indices.type() == CV_32S);
372     CV_Assert(indices.isContinuous());
373     ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
374
375     CV_Assert(dists.type() == CvType<DistanceType>::type());
376     CV_Assert(dists.isContinuous());
377     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
378
379     if (nnIndex_L1) return nnIndex_L1->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
380     if (nnIndex_L2) return nnIndex_L2->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
381 }
382
383
384 template <typename Distance>
385 int hierarchicalClustering(const Mat& features, Mat& centers, const ::cvflann::KMeansIndexParams& params,
386                            Distance d = Distance())
387 {
388     typedef typename Distance::ElementType ElementType;
389     typedef typename Distance::ResultType DistanceType;
390
391     CV_Assert(features.type() == CvType<ElementType>::type());
392     CV_Assert(features.isContinuous());
393     ::cvflann::Matrix<ElementType> m_features((ElementType*)features.ptr<ElementType>(0), features.rows, features.cols);
394
395     CV_Assert(centers.type() == CvType<DistanceType>::type());
396     CV_Assert(centers.isContinuous());
397     ::cvflann::Matrix<DistanceType> m_centers((DistanceType*)centers.ptr<DistanceType>(0), centers.rows, centers.cols);
398
399     return ::cvflann::hierarchicalClustering<Distance>(m_features, m_centers, params, d);
400 }
401
402
403 template <typename ELEM_TYPE, typename DIST_TYPE>
404 FLANN_DEPRECATED int hierarchicalClustering(const Mat& features, Mat& centers, const ::cvflann::KMeansIndexParams& params)
405 {
406     printf("[WARNING] cv::flann::hierarchicalClustering<ELEM_TYPE,DIST_TYPE> is deprecated, use "
407         "cv::flann::hierarchicalClustering<Distance> instead\n");
408
409     if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L2 ) {
410         return hierarchicalClustering< L2<ELEM_TYPE> >(features, centers, params);
411     }
412     else if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L1 ) {
413         return hierarchicalClustering< L1<ELEM_TYPE> >(features, centers, params);
414     }
415     else {
416         printf("[ERROR] cv::flann::hierarchicalClustering<ELEM_TYPE,DIST_TYPE> only provides backwards "
417         "compatibility for the L1 and L2 distances. "
418         "For other distance types you must use cv::flann::hierarchicalClustering<Distance>\n");
419         CV_Assert(0);
420     }
421 }
422
423 } } // namespace cv::flann
424
425 #endif // __cplusplus
426
427 #endif