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#include "opencv2/core.hpp"
47#include "opencv2/flann/miniflann.hpp"
48#include "opencv2/flann/flann_base.hpp"
49
50/**
51@defgroup flann Clustering and Search in Multi-Dimensional Spaces
52
53This section documents OpenCV's interface to the FLANN library. FLANN (Fast Library for Approximate
54Nearest Neighbors) is a library that contains a collection of algorithms optimized for fast nearest
55neighbor search in large datasets and for high dimensional features. More information about FLANN
56can be found in @cite Muja2009 .
57*/
58
59namespace cvflann
60{
61 CV_EXPORTS flann_distance_t flann_distance_type();
62 CV_DEPRECATED CV_EXPORTS void set_distance_type(flann_distance_t distance_type, int order);
63}
64
65
66namespace cv
67{
68namespace flann
69{
70
71
72//! @addtogroup flann
73//! @{
74
75template <typename T> struct CvType {};
76template <> struct CvType<unsigned char> { static int type() { return CV_8U; } };
77template <> struct CvType<char> { static int type() { return CV_8S; } };
78template <> struct CvType<unsigned short> { static int type() { return CV_16U; } };
79template <> struct CvType<short> { static int type() { return CV_16S; } };
80template <> struct CvType<int> { static int type() { return CV_32S; } };
81template <> struct CvType<float> { static int type() { return CV_32F; } };
82template <> struct CvType<double> { static int type() { return CV_64F; } };
83
84
85// bring the flann parameters into this namespace
86using ::cvflann::get_param;
87using ::cvflann::print_params;
88
89// bring the flann distances into this namespace
90using ::cvflann::L2_Simple;
91using ::cvflann::L2;
92using ::cvflann::L1;
93using ::cvflann::MinkowskiDistance;
94using ::cvflann::MaxDistance;
95using ::cvflann::HammingLUT;
96using ::cvflann::Hamming;
97using ::cvflann::Hamming2;
98using ::cvflann::DNAmmingLUT;
99using ::cvflann::DNAmming2;
100using ::cvflann::HistIntersectionDistance;
101using ::cvflann::HellingerDistance;
102using ::cvflann::ChiSquareDistance;
103using ::cvflann::KL_Divergence;
104
105
106/** @brief The FLANN nearest neighbor index class. This class is templated with the type of elements for which
107the index is built.
108
109`Distance` functor specifies the metric to be used to calculate the distance between two points.
110There are several `Distance` functors that are readily available:
111
112cv::cvflann::L2_Simple - Squared Euclidean distance functor.
113This is the simpler, unrolled version. This is preferable for very low dimensionality data (eg 3D points)
114
115cv::flann::L2 - Squared Euclidean distance functor, optimized version.
116
117cv::flann::L1 - Manhattan distance functor, optimized version.
118
119cv::flann::MinkowskiDistance - The Minkowski distance functor.
120This is highly optimised with loop unrolling.
121The computation of squared root at the end is omitted for efficiency.
122
123cv::flann::MaxDistance - The max distance functor. It computes the
124maximum distance between two vectors. This distance is not a valid kdtree distance, it's not
125dimensionwise additive.
126
127cv::flann::HammingLUT - %Hamming distance functor. It counts the bit
128differences between two strings using a lookup table implementation.
129
130cv::flann::Hamming - %Hamming distance functor. Population count is
131performed using library calls, if available. Lookup table implementation is used as a fallback.
132
133cv::flann::Hamming2 - %Hamming distance functor. Population count is
134implemented in 12 arithmetic operations (one of which is multiplication).
135
136cv::flann::DNAmmingLUT - %Adaptation of the Hamming distance functor to DNA comparison.
137As the four bases A, C, G, T of the DNA (or A, G, C, U for RNA) can be coded on 2 bits,
138it counts the bits pairs differences between two sequences using a lookup table implementation.
139
140cv::flann::DNAmming2 - %Adaptation of the Hamming distance functor to DNA comparison.
141Bases differences count are vectorised thanks to arithmetic operations using standard
142registers (AVX2 and AVX-512 should come in a near future).
143
144cv::flann::HistIntersectionDistance - The histogram
145intersection distance functor.
146
147cv::flann::HellingerDistance - The Hellinger distance functor.
148
149cv::flann::ChiSquareDistance - The chi-square distance functor.
150
151cv::flann::KL_Divergence - The Kullback-Leibler divergence functor.
152
153Although the provided implementations cover a vast range of cases, it is also possible to use
154a custom implementation. The distance functor is a class whose `operator()` computes the distance
155between two features. If the distance is also a kd-tree compatible distance, it should also provide an
156`accum_dist()` method that computes the distance between individual feature dimensions.
157
158In addition to `operator()` and `accum_dist()`, a distance functor should also define the
159`ElementType` and the `ResultType` as the types of the elements it operates on and the type of the
160result it computes. If a distance functor can be used as a kd-tree distance (meaning that the full
161distance between a pair of features can be accumulated from the partial distances between the
162individual dimensions) a typedef `is_kdtree_distance` should be present inside the distance functor.
163If the distance is not a kd-tree distance, but it's a distance in a vector space (the individual
164dimensions of the elements it operates on can be accessed independently) a typedef
165`is_vector_space_distance` should be defined inside the functor. If neither typedef is defined, the
166distance is assumed to be a metric distance and will only be used with indexes operating on
167generic metric distances.
168 */
169template <typename Distance>
170class GenericIndex
171{
172public:
173 typedef typename Distance::ElementType ElementType;
174 typedef typename Distance::ResultType DistanceType;
175
176 /** @brief Constructs a nearest neighbor search index for a given dataset.
177
178 @param features Matrix of containing the features(points) to index. The size of the matrix is
179 num_features x feature_dimensionality and the data type of the elements in the matrix must
180 coincide with the type of the index.
181 @param params Structure containing the index parameters. The type of index that will be
182 constructed depends on the type of this parameter. See the description.
183 @param distance
184
185 The method constructs a fast search structure from a set of features using the specified algorithm
186 with specified parameters, as defined by params. params is a reference to one of the following class
187 IndexParams descendants:
188
189 - **LinearIndexParams** When passing an object of this type, the index will perform a linear,
190 brute-force search. :
191 @code
192 struct LinearIndexParams : public IndexParams
193 {
194 };
195 @endcode
196 - **KDTreeIndexParams** When passing an object of this type the index constructed will consist of
197 a set of randomized kd-trees which will be searched in parallel. :
198 @code
199 struct KDTreeIndexParams : public IndexParams
200 {
201 KDTreeIndexParams( int trees = 4 );
202 };
203 @endcode
204 - **HierarchicalClusteringIndexParams** When passing an object of this type the index constructed
205 will be a hierarchical tree of clusters, dividing each set of points into n clusters whose centers
206 are picked among the points without further refinement of their position.
207 This algorithm fits both floating, integer and binary vectors. :
208 @code
209 struct HierarchicalClusteringIndexParams : public IndexParams
210 {
211 HierarchicalClusteringIndexParams(
212 int branching = 32,
213 flann_centers_init_t centers_init = CENTERS_RANDOM,
214 int trees = 4,
215 int leaf_size = 100);
216
217 };
218 @endcode
219 - **KMeansIndexParams** When passing an object of this type the index constructed will be a
220 hierarchical k-means tree (one tree by default), dividing each set of points into n clusters
221 whose barycenters are refined iteratively.
222 Note that this algorithm has been extended to the support of binary vectors as an alternative
223 to LSH when knn search speed is the criterium. It will also outperform LSH when processing
224 directly (i.e. without the use of MCA/PCA) datasets whose points share mostly the same values
225 for most of the dimensions. It is recommended to set more than one tree with binary data. :
226 @code
227 struct KMeansIndexParams : public IndexParams
228 {
229 KMeansIndexParams(
230 int branching = 32,
231 int iterations = 11,
232 flann_centers_init_t centers_init = CENTERS_RANDOM,
233 float cb_index = 0.2,
234 int trees = 1);
235 };
236 @endcode
237 - **CompositeIndexParams** When using a parameters object of this type the index created
238 combines the randomized kd-trees and the hierarchical k-means tree. :
239 @code
240 struct CompositeIndexParams : public IndexParams
241 {
242 CompositeIndexParams(
243 int trees = 4,
244 int branching = 32,
245 int iterations = 11,
246 flann_centers_init_t centers_init = CENTERS_RANDOM,
247 float cb_index = 0.2 );
248 };
249 @endcode
250 - **LshIndexParams** When using a parameters object of this type the index created uses
251 multi-probe LSH (by Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search
252 by Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li., Proceedings of the 33rd
253 International Conference on Very Large Data Bases (VLDB). Vienna, Austria. September 2007).
254 This algorithm is designed for binary vectors. :
255 @code
256 struct LshIndexParams : public IndexParams
257 {
258 LshIndexParams(
259 int table_number,
260 int key_size,
261 int multi_probe_level );
262 };
263 @endcode
264 - **AutotunedIndexParams** When passing an object of this type the index created is
265 automatically tuned to offer the best performance, by choosing the optimal index type
266 (randomized kd-trees, hierarchical kmeans, linear) and parameters for the dataset provided. :
267 @code
268 struct AutotunedIndexParams : public IndexParams
269 {
270 AutotunedIndexParams(
271 float target_precision = 0.9,
272 float build_weight = 0.01,
273 float memory_weight = 0,
274 float sample_fraction = 0.1 );
275 };
276 @endcode
277 - **SavedIndexParams** This object type is used for loading a previously saved index from the
278 disk. :
279 @code
280 struct SavedIndexParams : public IndexParams
281 {
282 SavedIndexParams( String filename );
283 };
284 @endcode
285 */
286 GenericIndex(const Mat& features, const ::cvflann::IndexParams& params, Distance distance = Distance());
287
288 ~GenericIndex();
289
290 /** @brief Performs a K-nearest neighbor search for a given query point using the index.
291
292 @param query The query point
293 @param indices Vector that will contain the indices of the K-nearest neighbors found. It must have
294 at least knn size.
295 @param dists Vector that will contain the distances to the K-nearest neighbors found. It must have
296 at least knn size.
297 @param knn Number of nearest neighbors to search for.
298 @param params SearchParams
299 */
300 void knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices,
301 std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& params);
302 void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& params);
303
304 /** @brief Performs a radius nearest neighbor search for a given query point using the index.
305
306 @param query The query point.
307 @param indices Vector that will contain the indices of the nearest neighbors found.
308 @param dists Vector that will contain the distances to the nearest neighbors found. It has the same
309 number of elements as indices.
310 @param radius The search radius.
311 @param params SearchParams
312
313 This function returns the number of nearest neighbors found.
314 */
315 int radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices,
316 std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& params);
317 int radiusSearch(const Mat& query, Mat& indices, Mat& dists,
318 DistanceType radius, const ::cvflann::SearchParams& params);
319
320 void save(String filename) { nnIndex->save(filename); }
321
322 int veclen() const { return nnIndex->veclen(); }
323
324 int size() const { return (int)nnIndex->size(); }
325
326 ::cvflann::IndexParams getParameters() { return nnIndex->getParameters(); }
327
328 CV_DEPRECATED const ::cvflann::IndexParams* getIndexParameters() { return nnIndex->getIndexParameters(); }
329
330private:
331 ::cvflann::Index<Distance>* nnIndex;
332 Mat _dataset;
333};
334
335//! @cond IGNORED
336
337#define FLANN_DISTANCE_CHECK \
338 if ( ::cvflann::flann_distance_type() != cvflann::FLANN_DIST_L2) { \
339 printf("[WARNING] You are using cv::flann::Index (or cv::flann::GenericIndex) and have also changed "\
340 "the distance using cvflann::set_distance_type. This is no longer working as expected "\
341 "(cv::flann::Index always uses L2). You should create the index templated on the distance, "\
342 "for example for L1 distance use: GenericIndex< L1<float> > \n"); \
343 }
344
345
346template <typename Distance>
347GenericIndex<Distance>::GenericIndex(const Mat& dataset, const ::cvflann::IndexParams& params, Distance distance)
348: _dataset(dataset)
349{
350 CV_Assert(dataset.type() == CvType<ElementType>::type());
351 CV_Assert(dataset.isContinuous());
352 ::cvflann::Matrix<ElementType> m_dataset((ElementType*)_dataset.ptr<ElementType>(0), _dataset.rows, _dataset.cols);
353
354 nnIndex = new ::cvflann::Index<Distance>(m_dataset, params, distance);
355
356 FLANN_DISTANCE_CHECK
357
358 nnIndex->buildIndex();
359}
360
361template <typename Distance>
362GenericIndex<Distance>::~GenericIndex()
363{
364 delete nnIndex;
365}
366
367template <typename Distance>
368void GenericIndex<Distance>::knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& searchParams)
369{
370 ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
371 ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
372 ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
373
374 FLANN_DISTANCE_CHECK
375
376 nnIndex->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
377}
378
379
380template <typename Distance>
381void GenericIndex<Distance>::knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& searchParams)
382{
383 CV_Assert(queries.type() == CvType<ElementType>::type());
384 CV_Assert(queries.isContinuous());
385 ::cvflann::Matrix<ElementType> m_queries((ElementType*)queries.ptr<ElementType>(0), queries.rows, queries.cols);
386
387 CV_Assert(indices.type() == CV_32S);
388 CV_Assert(indices.isContinuous());
389 ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(y: 0), indices.rows, indices.cols);
390
391 CV_Assert(dists.type() == CvType<DistanceType>::type());
392 CV_Assert(dists.isContinuous());
393 ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
394
395 FLANN_DISTANCE_CHECK
396
397 nnIndex->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
398}
399
400template <typename Distance>
401int GenericIndex<Distance>::radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
402{
403 ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
404 ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
405 ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
406
407 FLANN_DISTANCE_CHECK
408
409 return nnIndex->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
410}
411
412template <typename Distance>
413int GenericIndex<Distance>::radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
414{
415 CV_Assert(query.type() == CvType<ElementType>::type());
416 CV_Assert(query.isContinuous());
417 ::cvflann::Matrix<ElementType> m_query((ElementType*)query.ptr<ElementType>(0), query.rows, query.cols);
418
419 CV_Assert(indices.type() == CV_32S);
420 CV_Assert(indices.isContinuous());
421 ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(y: 0), indices.rows, indices.cols);
422
423 CV_Assert(dists.type() == CvType<DistanceType>::type());
424 CV_Assert(dists.isContinuous());
425 ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
426
427 FLANN_DISTANCE_CHECK
428
429 return nnIndex->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
430}
431
432/**
433 * @deprecated Use GenericIndex class instead
434 */
435template <typename T>
436class Index_
437{
438public:
439 typedef typename L2<T>::ElementType ElementType;
440 typedef typename L2<T>::ResultType DistanceType;
441
442 CV_DEPRECATED Index_(const Mat& dataset, const ::cvflann::IndexParams& params)
443 {
444 printf(format: "[WARNING] The cv::flann::Index_<T> class is deperecated, use cv::flann::GenericIndex<Distance> instead\n");
445
446 CV_Assert(dataset.type() == CvType<ElementType>::type());
447 CV_Assert(dataset.isContinuous());
448 ::cvflann::Matrix<ElementType> m_dataset((ElementType*)dataset.ptr<ElementType>(0), dataset.rows, dataset.cols);
449
450 if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L2 ) {
451 nnIndex_L1 = NULL;
452 nnIndex_L2 = new ::cvflann::Index< L2<ElementType> >(m_dataset, params);
453 }
454 else if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L1 ) {
455 nnIndex_L1 = new ::cvflann::Index< L1<ElementType> >(m_dataset, params);
456 nnIndex_L2 = NULL;
457 }
458 else {
459 printf(format: "[ERROR] cv::flann::Index_<T> only provides backwards compatibility for the L1 and L2 distances. "
460 "For other distance types you must use cv::flann::GenericIndex<Distance>\n");
461 CV_Assert(0);
462 }
463 if (nnIndex_L1) nnIndex_L1->buildIndex();
464 if (nnIndex_L2) nnIndex_L2->buildIndex();
465 }
466 CV_DEPRECATED ~Index_()
467 {
468 if (nnIndex_L1) delete nnIndex_L1;
469 if (nnIndex_L2) delete nnIndex_L2;
470 }
471
472 CV_DEPRECATED void knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& searchParams)
473 {
474 ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
475 ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
476 ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
477
478 if (nnIndex_L1) nnIndex_L1->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
479 if (nnIndex_L2) nnIndex_L2->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
480 }
481 CV_DEPRECATED void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& searchParams)
482 {
483 CV_Assert(queries.type() == CvType<ElementType>::type());
484 CV_Assert(queries.isContinuous());
485 ::cvflann::Matrix<ElementType> m_queries((ElementType*)queries.ptr<ElementType>(0), queries.rows, queries.cols);
486
487 CV_Assert(indices.type() == CV_32S);
488 CV_Assert(indices.isContinuous());
489 ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(y: 0), indices.rows, indices.cols);
490
491 CV_Assert(dists.type() == CvType<DistanceType>::type());
492 CV_Assert(dists.isContinuous());
493 ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
494
495 if (nnIndex_L1) nnIndex_L1->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
496 if (nnIndex_L2) nnIndex_L2->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
497 }
498
499 CV_DEPRECATED int radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
500 {
501 ::cvflann::Matrix<ElementType> m_query((ElementType*)&query[0], 1, query.size());
502 ::cvflann::Matrix<int> m_indices(&indices[0], 1, indices.size());
503 ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
504
505 if (nnIndex_L1) return nnIndex_L1->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
506 if (nnIndex_L2) return nnIndex_L2->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
507 }
508
509 CV_DEPRECATED int radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
510 {
511 CV_Assert(query.type() == CvType<ElementType>::type());
512 CV_Assert(query.isContinuous());
513 ::cvflann::Matrix<ElementType> m_query((ElementType*)query.ptr<ElementType>(0), query.rows, query.cols);
514
515 CV_Assert(indices.type() == CV_32S);
516 CV_Assert(indices.isContinuous());
517 ::cvflann::Matrix<int> m_indices((int*)indices.ptr<int>(y: 0), indices.rows, indices.cols);
518
519 CV_Assert(dists.type() == CvType<DistanceType>::type());
520 CV_Assert(dists.isContinuous());
521 ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
522
523 if (nnIndex_L1) return nnIndex_L1->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
524 if (nnIndex_L2) return nnIndex_L2->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
525 }
526
527 CV_DEPRECATED void save(String filename)
528 {
529 if (nnIndex_L1) nnIndex_L1->save(filename);
530 if (nnIndex_L2) nnIndex_L2->save(filename);
531 }
532
533 CV_DEPRECATED int veclen() const
534 {
535 if (nnIndex_L1) return nnIndex_L1->veclen();
536 if (nnIndex_L2) return nnIndex_L2->veclen();
537 }
538
539 CV_DEPRECATED int size() const
540 {
541 if (nnIndex_L1) return nnIndex_L1->size();
542 if (nnIndex_L2) return nnIndex_L2->size();
543 }
544
545 CV_DEPRECATED ::cvflann::IndexParams getParameters()
546 {
547 if (nnIndex_L1) return nnIndex_L1->getParameters();
548 if (nnIndex_L2) return nnIndex_L2->getParameters();
549
550 }
551
552 CV_DEPRECATED const ::cvflann::IndexParams* getIndexParameters()
553 {
554 if (nnIndex_L1) return nnIndex_L1->getIndexParameters();
555 if (nnIndex_L2) return nnIndex_L2->getIndexParameters();
556 }
557
558private:
559 // providing backwards compatibility for L2 and L1 distances (most common)
560 ::cvflann::Index< L2<ElementType> >* nnIndex_L2;
561 ::cvflann::Index< L1<ElementType> >* nnIndex_L1;
562};
563
564//! @endcond
565
566/** @brief Clusters features using hierarchical k-means algorithm.
567
568@param features The points to be clustered. The matrix must have elements of type
569Distance::ElementType.
570@param centers The centers of the clusters obtained. The matrix must have type
571Distance::CentersType. The number of rows in this matrix represents the number of clusters desired,
572however, because of the way the cut in the hierarchical tree is chosen, the number of clusters
573computed will be the highest number of the form (branching-1)\*k+1 that's lower than the number of
574clusters desired, where branching is the tree's branching factor (see description of the
575KMeansIndexParams).
576@param params Parameters used in the construction of the hierarchical k-means tree.
577@param d Distance to be used for clustering.
578
579The method clusters the given feature vectors by constructing a hierarchical k-means tree and
580choosing a cut in the tree that minimizes the cluster's variance. It returns the number of clusters
581found.
582 */
583template <typename Distance>
584int hierarchicalClustering(const Mat& features, Mat& centers, const ::cvflann::KMeansIndexParams& params,
585 Distance d = Distance())
586{
587 typedef typename Distance::ElementType ElementType;
588 typedef typename Distance::CentersType CentersType;
589
590 CV_Assert(features.type() == CvType<ElementType>::type());
591 CV_Assert(features.isContinuous());
592 ::cvflann::Matrix<ElementType> m_features((ElementType*)features.ptr<ElementType>(0), features.rows, features.cols);
593
594 CV_Assert(centers.type() == CvType<CentersType>::type());
595 CV_Assert(centers.isContinuous());
596 ::cvflann::Matrix<CentersType> m_centers((CentersType*)centers.ptr<CentersType>(0), centers.rows, centers.cols);
597
598 return ::cvflann::hierarchicalClustering<Distance>(m_features, m_centers, params, d);
599}
600
601//! @cond IGNORED
602
603template <typename ELEM_TYPE, typename DIST_TYPE>
604CV_DEPRECATED int hierarchicalClustering(const Mat& features, Mat& centers, const ::cvflann::KMeansIndexParams& params)
605{
606 printf(format: "[WARNING] cv::flann::hierarchicalClustering<ELEM_TYPE,DIST_TYPE> is deprecated, use "
607 "cv::flann::hierarchicalClustering<Distance> instead\n");
608
609 if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L2 ) {
610 return hierarchicalClustering< L2<ELEM_TYPE> >(features, centers, params);
611 }
612 else if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L1 ) {
613 return hierarchicalClustering< L1<ELEM_TYPE> >(features, centers, params);
614 }
615 else {
616 printf(format: "[ERROR] cv::flann::hierarchicalClustering<ELEM_TYPE,DIST_TYPE> only provides backwards "
617 "compatibility for the L1 and L2 distances. "
618 "For other distance types you must use cv::flann::hierarchicalClustering<Distance>\n");
619 CV_Assert(0);
620 }
621}
622
623//! @endcond
624
625//! @} flann
626
627} } // namespace cv::flann
628
629#endif
630

source code of opencv/modules/flann/include/opencv2/flann.hpp