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. [詳解]

#include <flann.hpp>

公開型
typedef Distance::ElementType	ElementType
typedef Distance::ResultType	DistanceType

公開メンバ関数
	GenericIndex (const Mat &features, const ::cvflann::IndexParams &params, Distance distance=Distance())
	与えられたデータセットに対する最近傍探索インデックスを構築します。[【詳解】（英語］
void	knnSearch (const std::vector< ElementType > &query, std::vector< int > &indices, std::vector< DistanceType > &dists, int knn, const ::cvflann::SearchParams &params)
	インデックスを使って、与えられたクエリポイントに対するK-nearest neighbor検索を実行します。[【詳解】（英語］
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)
	インデックスを使用して、指定されたクエリポイントの半径方向の最近傍探索を実行します。[【詳解】（英語］
int	radiusSearch (const Mat &query, Mat &indices, Mat &dists, DistanceType radius, const ::cvflann::SearchParams &params)
void	save (String filename)
int	veclen () const
int	size () const
::cvflann::IndexParams	getParameters ()
CV_DEPRECATEDconst ::cvflann::IndexParams *	getIndexParameters ()

詳解

テンプレート<typame Distance>．
クラス cv::flann::GenericIndex< Distance > 。

FLANNの最近傍インデックスクラスです．このクラスは，インデックスが作成される要素の種類でテンプレート化されています．

Distancefunctor は，2点間の距離を計算するために利用するメトリックを指定します．ファンクタにはいくつかの種類があります。Distanceファンクタは，すぐに利用できるものがいくつかあります．

cv::cvflann::L2_Simple - 2乗ユークリッド距離ファンクタ．これは，より単純な，展開されたバージョンです．これは，非常に次元の低いデータ（例えば，3次元の点）に適しています．

cv::flann::L2 - ユークリッド二乗距離ファンクタ，最適化されたバージョン．

cv::flann::L1 - マンハッタン距離ファンクタ，最適化されています．

cv::flann::MinkowskiDistance - ミンコフスキー距離ファンクタ．これは，ループアンローリングによって高度に最適化されています．効率化のために，最後の自乗根の計算は省略されています．

cv::flann::MaxDistance - 最大距離ファンクタ．これは，2つのベクトル間の最大距離を求めます．この距離は，有効な kdtree の距離ではなく，次元加法ではありません．

cv::flann::HammingLUT - ハミング距離ファンクタ．ルックアップテーブルの実装を利用して，2つの文字列のビット差を数えます．

cv::flann::Haming - ハミング距離ファンクタ．人口カウントは，利用可能であればライブラリコールを利用して行われます．ルックアップテーブルの実装がフォールバックとして利用されます．

cv::flann::Haming2 - ハミング距離ファンクタ．人口カウントは，12の算術演算（そのうちの1つは乗算）で実装されます．

cv::flann::DNAmmingLUT - 距離ファンクタの DNA 比較への適応。Hamming距離ファンクタを DNA の比較に適応させます．DNAの4つの塩基 A, C, G, T（または，RNAのA, G, C, U）は，2ビットでコード化できるので，ルックアップテーブルの実装を用いて，2つの配列のビットペアの違いを数えます．

cv::flann::DNAmming2 - 距離ファンクタを DNA 比較に適応させたもの．Hamming距離ファンクタを DNA比較に適応させたものです．標準的なレジスタ（AVX2 や AVX-512 が近い将来に登場する予定です）を利用した算術演算により，塩基の違いのカウントをベクトル化します．

cv::flann::HistIntersectionDistance - ヒストグラムの交点距離ファンクタ．

cv::flann::HellingerDistance - ヘリンガー距離ファンクタ．

cv::flann::ChiSquareDistance - カイ二乗距離ファンクタ．

cv::flann::KL_Divergence - Kullback-Leibler ダイバージェンスファンクタ．

提供されている実装は，非常に多くのケースをカバーしていますが，独自の実装を利用することも可能です．距離ファンクタは，2つの特徴間の距離を計算するクラスである．operator()は2つの特徴間の距離を計算します．その距離が kd-tree 互換の距離でもある場合は、個々の特徴間の距離を計算するaccum_dist()メソッドを提供する必要があります。

に加えてoperator()およびaccum_dist()に加えて、距離ファンクタは以下のものを定義する必要があります。ElementTypeとResultTypeを、操作する要素の型と計算する結果の型として定義すべきである。距離ファンクタが kd-tree 距離として使用される場合（つまり，特徴のペア間の完全な距離が，個々の次元間の部分的な距離から累積される場合），typedefis_kdtree_distanceが距離ファンクタの内部に存在しなければなりません。距離が kd-tree 距離ではなく，ベクトル空間での距離である場合（操作する要素の個々の次元は独立してアクセスできる），型定義のis_vector_space_distanceがファンクタの内部で定義されなければならない．どちらのtypedefも定義されていない場合，その距離はメトリック距離であるとみなされ，一般的なメトリック距離を操作するインデックスでのみ使用されます．

構築子と解体子

GenericIndex()

template<typename Distance >

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

与えられたデータセットに対する最近傍探索インデックスを構築します。

引数

features	インデックスを作成する特徴（点）を含む行列です。行列のサイズは num_features x feature_dimensionality であり、行列の要素のデータ型はインデックスの型と一致していなければなりません。
params	インデックスのパラメータを含む構造体。構築されるインデックスの種類は，このパラメータの型に依存します。説明を参照してください。
distance

このメソッドは、paramsで定義されているように、指定されたパラメータを持つ指定されたアルゴリズムを使用して、特徴のセットから高速検索構造を構築します。 paramsは、以下のクラスIndexParamsの子孫の1つへの参照です。

• LinearIndexParamsこのタイプのオブジェクトを渡すと、インデックスは線形のブルートフォース・サーチを行います。

  
  struct
  LinearIndexParams :
  public
  IndexParams
  {
  };

• KDTreeIndexParamsこのタイプのオブジェクトを渡すと、構築されたインデックスは、ランダム化されたKDツリーのセットで構成され、それらは並行して検索されます。

  
  struct
  KDTreeIndexParams :
  public
  IndexParams
  {
  
  KDTreeIndexParams(
  int
  trees = 4 );
  };

• HierarchicalClusteringIndexParamsこのタイプのオブジェクトを渡すと、構築されるインデックスは、クラスタの階層的な木になります。これは、各点の集合をn個のクラスタに分割し、その中心を点の中から選び、その位置をさらに細かくすることはありません。このアルゴリズムは，浮動小数点，整数，バイナリのいずれのベクトルにも対応します．

  
  struct
  HierarchicalClusteringIndexParams :
  public
  IndexParams
  {
  
  HierarchicalClusteringIndexParams(
  
  int
  branching = 32,
  
  flann_centers_init_t centers_init = CENTERS_RANDOM,
  
  int
  trees = 4,
  
  int
  leaf_size = 100);
  
  
  };

• KMeansIndexParamsこのタイプのオブジェクトを渡すと、構築されるインデックスは、階層化されたk-meansツリー（デフォルトでは1つのツリー）となり、各点のセットをn個のクラスタに分割し、その中心は反復的に改良されます。なお、このアルゴリズムは、knnの検索速度を重視する場合にLSHに代わるものとして、二値ベクトルをサポートするように拡張されています。また、ほとんどの次元でポイントが同じ値を持つデータセットを直接（MCA/PCAを使用せずに）処理する場合にも、LSHを上回る性能を発揮します。バイナリデータの場合は，複数の木を設定することをお勧めします．

  
  struct
  KMeansIndexParams :
  public
  IndexParams
  {
  
  KMeansIndexParams(
  
  int
  branching = 32,
  
  int
  iterations = 11,
  
  flann_centers_init_t centers_init = CENTERS_RANDOM,
  
  float
  cb_index = 0.2,
  
  int
  trees = 1);
  };

• CompositeIndexParamsこのタイプのパラメータ・オブジェクトを使用すると、作成されるインデックスは、ランダム化された kd ツリーと階層的な k-means ツリーを組み合わせたものになります。

  
  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このタイプのパラメータオブジェクトを使用すると、作成されるインデックスはマルチプローブ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). ウィーン、オーストリア。September 2007）を参照してください。このアルゴリズムは，バイナリ・ベクトルを対象としています．

  
  struct
  LshIndexParams :
  public
  IndexParams
  {
  
  LshIndexParams(
  
  int
  table_number,
  
  int
  key_size,
  
  int
  multi_probe_level );
  };

• AutotunedIndexParamsこのタイプのオブジェクトを渡すと、作成されたインデックスは、提供されたデータセットに最適なインデックス・タイプ（ランダム化されたkd-tree、階層化されたkmeans、linear）とパラメータを選択することによって、最高のパフォーマンスを提供するように自動的に調整されます。 :

  
  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このオブジェクトタイプは、以前に保存されたインデックスをディスクから読み込むために使用されます。

  
  struct
  SavedIndexParams :
  public
  IndexParams
  {
  
  SavedIndexParams( String filename );
  };

関数詳解

knnSearch()

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
	)

インデックスを使って、与えられたクエリポイントに対するK-nearest neighbor検索を実行します。

引数

query	クエリポイント
indices	見つかったK-nearest neighborのインデックスを格納するベクター。少なくともknnサイズである必要があります。
dists	見つかったK-nearest neighborsの距離を含むベクター。少なくともknnサイズである必要があります。
knn	検索する最近傍の数。
params	SearchParams

radiusSearch()

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
	)

インデックスを使用して、指定されたクエリポイントの半径方向の最近傍探索を実行します。

引数

query	クエリポイント。
indices	見つかった最近傍のインデックスを含むベクター。
dists	見つかった最近傍探索の距離を含むベクター。インデックスと同じ数の要素を持ちます。
radius	探索半径です。
params	SearchParams

この関数は，見つかった最近傍傍の数を返します。

---

このクラス詳解は次のファイルから抽出されました:

• flann.hpp