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

FLANN最近傍インデックスクラス。このクラスは、インデックスを構築する対象の要素の型でテンプレート化されている。続き...

#include <opencv2/flann.hpp>

Collaboration diagram for cv::flann::GenericIndex< Distance >:

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

公開メンバ関数
	GenericIndex (const Mat &features, const ::cvflann::IndexParams &params, Distance distance=Distance())
	与えられたデータセットに対する最近傍探索インデックスを構築する。
	~GenericIndex ()
const ::cvflann::IndexParams *	getIndexParameters ()
::cvflann::IndexParams	getParameters ()
void	knnSearch (const Mat &queries, Mat &indices, Mat &dists, int knn, const ::cvflann::SearchParams &params)
void	knnSearch (const std::vector< ElementType > &query, std::vector< int > &indices, std::vector< DistanceType > &dists, int knn, const ::cvflann::SearchParams &params)
	インデックスを用いて、与えられたクエリ点に対するK近傍探索を実行する。
int	radiusSearch (const Mat &query, Mat &indices, Mat &dists, DistanceType radius, 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)
	インデックスを用いて、与えられたクエリ点に対する半径最近傍探索を実行する。
void	save (String filename)
int	size () const
int	veclen () const

詳細説明

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

FLANN最近傍探索インデックスクラス。このクラスは、インデックスを構築する対象の要素の型でテンプレート化されている。

Distance ファンクタは、2点間の距離を計算するために用いる距離尺度を指定する。すぐに利用できる Distance ファンクタがいくつか用意されている:

cv::cvflann::L2_Simple - ユークリッド距離の2乗のファンクタ。これはよりシンプルでループ展開された版である。ごく低次元のデータ(例: 3D点)に適している

cv::flann::L2 - ユークリッド距離の2乗のファンクタ。最適化版。

cv::flann::L1 - マンハッタン距離のファンクタ。最適化版。

cv::flann::MinkowskiDistance - ミンコフスキー距離のファンクタ。ループ展開によって高度に最適化されている。効率のため、最後の平方根計算は省略されている。

cv::flann::MaxDistance - 最大距離のファンクタ。2つのベクトル間の最大距離を計算する。この距離はkd-tree距離として有効ではなく、次元ごとに加法的ではない。

cv::flann::HammingLUT - ハミング距離のファンクタ。ルックアップテーブル実装を用いて、2つの文字列間のビットの相違数を数える。

cv::flann::Hamming - ハミング距離のファンクタ。利用可能であればライブラリ呼び出しによりポピュレーションカウントを実行する。フォールバックとしてルックアップテーブル実装が使われる。

cv::flann::Hamming2 - ハミング距離のファンクタ。ポピュレーションカウントは12個の算術演算(うち1つは乗算)で実装されている。

cv::flann::DNAmmingLUT - Hamming 距離ファンクタをDNA比較に適応させたもの。DNAの4つの塩基A, C, G, T(RNAの場合はA, G, C, U)は2ビットで符号化できるため、ルックアップテーブル実装を用いて2つの配列間のビット対の相違数を数える。

cv::flann::DNAmming2 - Hamming 距離ファンクタをDNA比較に適応させたもの。塩基の相違数の計算は、標準レジスタを用いた算術演算によりベクトル化されている(AVX2およびAVX-512は近い将来対応予定)。

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

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

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

cv::flann::KL_Divergence - カルバック・ライブラーダイバージェンスのファンクタ。

提供されている実装は幅広いケースをカバーしているが、カスタム実装を使うことも可能である。距離ファンクタは、operator() が2つの特徴間の距離を計算するクラスである。その距離がkd-tree互換距離でもある場合は、個々の特徴次元間の距離を計算する accum_dist() メソッドも提供すべきである。

operator() と accum_dist() に加えて、距離ファンクタは、扱う要素の型としての ElementType と、計算結果の型としての ResultType も定義すべきである。距離ファンクタがkd-tree距離として使用できる(つまり、特徴対間の全体距離を個々の次元間の部分距離から累積できる)場合は、is_kdtree_distance のtypedefを距離ファンクタ内に存在させるべきである。距離がkd-tree距離ではないが、ベクトル空間上の距離である(扱う要素の個々の次元に独立してアクセスできる)場合は、is_vector_space_distance のtypedefをファンクタ内に定義すべきである。どちらのtypedefも定義されていない場合、その距離は計量距離(metric distance)とみなされ、汎用的な計量距離で動作するインデックスでのみ使用される。

型定義メンバ詳解

DistanceType

template<typename Distance >

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

ElementType

template<typename Distance >

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

構築子と解体子の詳解

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派生クラスのいずれかへの参照である:

• LinearIndexParams この型のオブジェクトを渡すと、インデックスは線形の総当たり探索を実行する。:

  struct LinearIndexParams : public IndexParams
  {
  };

• KDTreeIndexParams この型のオブジェクトを渡すと、構築されるインデックスは並列に探索される複数のランダム化されたkd-treeの集合で構成される。:

  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-treeと階層的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(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(
   int table_number,
   int key_size,
   int multi_probe_level );
  };

• AutotunedIndexParams この型のオブジェクトを渡すと、作成されるインデックスは、提供されたデータセットに対して最適なインデックス型(ランダム化kd-tree、階層的kmeans、線形)とパラメータを選択することで、最良の性能を提供するよう自動的に調整される。:

  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 );
  };

~GenericIndex()

template<typename Distance >

cv::flann::GenericIndex< Distance >::~GenericIndex

(

)

メンバ関数詳解

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 Mat &	queries,
		Mat &	indices,
		Mat &	dists,
		int	knn,
		const ::cvflann::SearchParams &	params )

knnSearch() [2/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 )

インデックスを用いて、指定したクエリ点に対するK最近傍探索を実行する。

引数

query	クエリ点
indices	見つかったK近傍のインデックスを格納するベクトル。少なくとも knn のサイズを持たなければならない。
dists	見つかったK近傍までの距離を格納するベクトル。少なくとも knn のサイズを持たなければならない。
knn	探索する最近傍の個数。
params	SearchParams

radiusSearch() [1/2]

template<typename Distance >

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

radiusSearch() [2/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 )

インデックスを用いて、指定したクエリ点に対する半径最近傍探索を実行する。

引数

query	クエリ点。
indices	見つかった最近傍のインデックスを格納するベクトル。
dists	見つかった最近傍までの距離を格納するベクトル。indices と同じ数の要素を持つ。
radius	探索半径。
params	SearchParams

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

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

---

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

• opencv2/flann.hpp