| OpenCV 3.4.8 Open Source Computer Vision

Public Types | Public Member Functions | List of all members
cv::flann::GenericIndex< Distance > Class Template Reference
Clustering and Search in Multi-Dimensional Spaces

The FLANN nearest neighbor index class. This class is templated with the type of elements for which the index is built. More...

`#include <opencv2/flann.hpp>`

## Public Types
typedef Distance::ResultType | DistanceType
typedef Distance::ElementType | ElementType

## Public Member Functions
| GenericIndex (const Mat &features, const ::cvflann::IndexParams &params, Distance distance=Distance())
| Constructs a nearest neighbor search index for a given dataset. More...
| ~GenericIndex ()
const ::cvflann::IndexParams * | getIndexParameters ()
::cvflann::IndexParams | getParameters ()
void | knnSearch (const std::vector< ElementType > &query, std::vector< int > &indices, std::vector< DistanceType > &dists, int knn, const ::cvflann::SearchParams &params)
| Performs a K-nearest neighbor search for a given query point using the index. More...
void | knnSearch (const Mat &queries, Mat &indices, Mat &dists, int knn, const ::cvflann::SearchParams &params)
int | radiusSearch (const std::vector< ElementType > &query, std::vector< int > &indices, std::vector< DistanceType > &dists, DistanceType radius, const ::cvflann::SearchParams &params)
| Performs a radius nearest neighbor search for a given query point using the index. More...
int | radiusSearch (const Mat &query, Mat &indices, Mat &dists, DistanceType radius, const ::cvflann::SearchParams &params)
void | save (String filename)
int | size () const
int | veclen () const

## Detailed Description

### template<typename Distance>
class cv::flann::GenericIndex< Distance >

The FLANN nearest neighbor index class. This class is templated with the type of elements for which the index is built.

`Distance` functor specifies the metric to be used to calculate the distance between two points. There are several `Distance` functors that are readily available:

cv::cvflann::L2_Simple - Squared Euclidean distance functor. This is the simpler, unrolled version. This is preferable for very low dimensionality data (eg 3D points)

cv::flann::L2 - Squared Euclidean distance functor, optimized version.

cv::flann::L1 - Manhattan distance functor, optimized version.

cv::flann::MinkowskiDistance - The Minkowsky distance functor. This is highly optimised with loop unrolling. The computation of squared root at the end is omitted for efficiency.

cv::flann::MaxDistance - The max distance functor. It computes the maximum distance between two vectors. This distance is not a valid kdtree distance, it's not dimensionwise additive.

cv::flann::HammingLUT - Hamming distance functor. It counts the bit differences between two strings using a lookup table implementation.

cv::flann::Hamming - Hamming distance functor. Population count is performed using library calls, if available. Lookup table implementation is used as a fallback.

cv::flann::Hamming2 - Hamming distance functor. Population count is implemented in 12 arithmetic operations (one of which is multiplication).

cv::flann::HistIntersectionDistance - The histogram intersection distance functor.

cv::flann::HellingerDistance - The Hellinger distance functor.

cv::flann::ChiSquareDistance - The chi-square distance functor.

cv::flann::KL_Divergence - The Kullback-Leibler divergence functor.

Although the provided implementations cover a vast range of cases, it is also possible to use a custom implementation. The distance functor is a class whose `operator()` computes the distance between two features. If the distance is also a kd-tree compatible distance, it should also provide an `accum_dist()` method that computes the distance between individual feature dimensions.

In addition to `operator()` and `accum_dist()`, a distance functor should also define the `ElementType` and the `ResultType` as the types of the elements it operates on and the type of the result it computes. If a distance functor can be used as a kd-tree distance (meaning that the full distance between a pair of features can be accumulated from the partial distances between the individual dimensions) a typedef `is_kdtree_distance` should be present inside the distance functor. If the distance is not a kd-tree distance, but it's a distance in a vector space (the individual dimensions of the elements it operates on can be accessed independently) a typedef `is_vector_space_distance` should be defined inside the functor. If neither typedef is defined, the distance is assumed to be a metric distance and will only be used with indexes operating on generic metric distances.

## Member Typedef Documentation

## § DistanceType

template<typename Distance >

typedef Distance::ResultType cv::flann::GenericIndex< Distance >::DistanceType

## § ElementType

template<typename Distance >

typedef Distance::ElementType cv::flann::GenericIndex< Distance >::ElementType

## Constructor & Destructor Documentation

## § GenericIndex()

template<typename Distance >

cv::flann::GenericIndex< Distance >::GenericIndex | ( | const Mat & | features,
|  | const ::cvflann::IndexParams & | params,
|  | Distance | distance = `Distance()`
| ) |  |

Constructs a nearest neighbor search index for a given dataset.

Parameters

  features | Matrix of containing the features(points) to index. The size of the matrix is num_features x feature_dimensionality and the data type of the elements in the matrix must coincide with the type of the index.
  params | Structure containing the index parameters. The type of index that will be constructed depends on the type of this parameter. See the description.
  distance | The method constructs a fast search structure from a set of features using the specified algorithm with specified parameters, as defined by params. params is a reference to one of the following class IndexParams descendants:

- LinearIndexParams When passing an object of this type, the index will perform a linear, brute-force search. :
  struct LinearIndexParams : public IndexParams
  {
  };
- KDTreeIndexParams When passing an object of this type the index constructed will consist of a set of randomized kd-trees which will be searched in parallel. :
  struct KDTreeIndexParams : public IndexParams
  {
  KDTreeIndexParams( int trees = 4 );
  };
- KMeansIndexParams When passing an object of this type the index constructed will be a hierarchical k-means tree. :
  struct KMeansIndexParams : public IndexParams
  {
  KMeansIndexParams(
  int branching = 32,
  int iterations = 11,
  flann_centers_init_t centers_init = CENTERS_RANDOM,
  float cb_index = 0.2 );
  };
- CompositeIndexParams When using a parameters object of this type the index created combines the randomized kd-trees and the hierarchical k-means tree. :
  struct CompositeIndexParams : public IndexParams
  {
  CompositeIndexParams(
  int trees = 4,
  int branching = 32,
  int iterations = 11,
  flann_centers_init_t centers_init = CENTERS_RANDOM,
  float cb_index = 0.2 );
  };
- LshIndexParams When using a parameters object of this type the index created uses multi-probe LSH (by Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search by Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li., Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). Vienna, Austria. September 2007) :
  struct LshIndexParams : public IndexParams
  {
  LshIndexParams(
  unsigned int table_number,
  unsigned int key_size,
  unsigned int multi_probe_level );
  };
- AutotunedIndexParams When passing an object of this type the index created is automatically tuned to offer the best performance, by choosing the optimal index type (randomized kd-trees, hierarchical kmeans, linear) and parameters for the dataset provided. :
  struct AutotunedIndexParams : public IndexParams
  {
  AutotunedIndexParams(
  float target_precision = 0.9,
  float build_weight = 0.01,
  float memory_weight = 0,
  float sample_fraction = 0.1 );
  };
- SavedIndexParams This object type is used for loading a previously saved index from the disk. :
  struct SavedIndexParams : public IndexParams
  {
  SavedIndexParams( String filename );
  };

## § ~GenericIndex()

template<typename Distance >

cv::flann::GenericIndex< Distance >::~GenericIndex | ( |  | ) |

## Member Function Documentation

## § getIndexParameters()

template<typename Distance >

const ::cvflann::IndexParams* cv::flann::GenericIndex< Distance >::getIndexParameters | ( |  | ) |
| inline

## § getParameters()

template<typename Distance >

::cvflann::IndexParams cv::flann::GenericIndex< Distance >::getParameters | ( |  | ) |
| inline

## § knnSearch() [1/2]

template<typename Distance >

void cv::flann::GenericIndex< Distance >::knnSearch | ( | const std::vector< ElementType > & | query,
|  | std::vector< int > & | indices,
|  | std::vector< DistanceType > & | dists,
|  | int | knn,
|  | const ::cvflann::SearchParams & | params
| ) |  |

Performs a K-nearest neighbor search for a given query point using the index.

Parameters

  query | The query point
  indices | Vector that will contain the indices of the K-nearest neighbors found. It must have at least knn size.
  dists | Vector that will contain the distances to the K-nearest neighbors found. It must have at least knn size.
  knn | Number of nearest neighbors to search for.
  params | SearchParams

## § knnSearch() [2/2]

template<typename Distance >

void cv::flann::GenericIndex< Distance >::knnSearch | ( | const Mat & | queries,
|  | Mat & | indices,
|  | Mat & | dists,
|  | int | knn,
|  | const ::cvflann::SearchParams & | params
| ) |  |

## § radiusSearch() [1/2]

template<typename Distance >

int cv::flann::GenericIndex< Distance >::radiusSearch | ( | const std::vector< ElementType > & | query,
|  | std::vector< int > & | indices,
|  | std::vector< DistanceType > & | dists,
|  | DistanceType | radius,
|  | const ::cvflann::SearchParams & | params
| ) |  |

Performs a radius nearest neighbor search for a given query point using the index.

Parameters

  query | The query point.
  indices | Vector that will contain the indices of the nearest neighbors found.
  dists | Vector that will contain the distances to the nearest neighbors found. It has the same number of elements as indices.
  radius | The search radius.
  params | SearchParams

This function returns the number of nearest neighbors found.

## § radiusSearch() [2/2]

template<typename Distance >

int cv::flann::GenericIndex< Distance >::radiusSearch | ( | const Mat & | query,
|  | Mat & | indices,
|  | Mat & | dists,
|  | DistanceType | radius,
|  | const ::cvflann::SearchParams & | params
| ) |  |

## § save()

template<typename Distance >

void cv::flann::GenericIndex< Distance >::save | ( | String | filename | ) |
| inline

## § size()

template<typename Distance >

int cv::flann::GenericIndex< Distance >::size | ( |  | ) | const
| inline

## § veclen()

template<typename Distance >

int cv::flann::GenericIndex< Distance >::veclen | ( |  | ) | const
| inline

The documentation for this class was generated from the following file:

- opencv2/flann.hpp