K-近傍探索の高速な近似計算 ====================================== .. highlight:: cpp このセクションでは，FLANN ライブラリに対する OpenCVのインタフェースについて説明します．FLANN（Fast Library for Approximate Nearest Neighbors）は，K-近傍探索の高速な近似計算アルゴリズムのコレクションで，巨大なデータセットと高次元特徴量に対して最適化されています．FLANN についてさらに詳しく知りたい場合は， muja_flann_2009 を参照してください． .. index:: cv::flann::Index_ .. _cv::flann::Index_: cv::flann::Index_ ----------------- `id=0.514950352292 Comments from the Wiki `__ .. ctype:: cv::flann::Index_ FLANN 最近傍インデックスクラス．このクラスは，要素の型でテンプレート化されており，この要素に対するインデックスが構築されます． .. code-block:: c namespace cv { namespace flann { template class Index_ { public: Index_(const Mat& features, const IndexParams& params); ~Index_(); void knnSearch(const vector& query, vector& indices, vector& dists, int knn, const SearchParams& params); void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const SearchParams& params); int radiusSearch(const vector& query, vector& indices, vector& dists, float radius, const SearchParams& params); int radiusSearch(const Mat& query, Mat& indices, Mat& dists, float radius, const SearchParams& params); void save(std::string filename); int veclen() const; int size() const; const IndexParams* getIndexParameters(); }; typedef Index_ Index; } } // namespace cv::flann .. .. index:: cv::flann::Index_::Index_ cv::cv::flann::Index_::Index_ -------------------------------- `id=0.317694162406 Comments from the Wiki `__ .. cfunction:: Index_::Index_(const Mat\& features, const IndexParams\& params) 与えられたデータセットの最近傍探索インデックスを作成します． :param features: インデックス作成対象となる特徴（点）が格納された行列．この行列のサイズは num _ features x feature _ dimensionality となります． また行列の要素のデータ型は，インデックスの型と一致していなければいけません． :param params: インデックスパラメータを含む構造体．作成されるインデックスの種類は，このパラメータの種類に依存します． 選択できるパラメータの種類を以下に示します： * **LinearIndexParams** この型のオブジェクトが渡されると，インデックスに対して，線形のブルートフォース探索が行われます． .. code-block:: c struct LinearIndexParams : public IndexParams { }; .. * **KDTreeIndexParams** この型のオブジェクトが渡されると，ランダム kd-tree の集合でインデックスが表現され，これは並列に探索されます． .. code-block:: c struct KDTreeIndexParams : public IndexParams { KDTreeIndexParams( int trees = 4 ); }; .. * **trees** 並列な kd-tree の個数．[1..16] の範囲が適切な値です． * **KMeansIndexParams** この型のオブジェクトが渡されると，階層型 k-means tree でインデックスが表現されます． .. code-block:: c struct KMeansIndexParams : public IndexParams { KMeansIndexParams( int branching = 32, int iterations = 11, flann_centers_init_t centers_init = CENTERS_RANDOM, float cb_index = 0.2 ); }; .. * **branching** 階層型 k-means tree で利用される branching ファクタ． * **iterations** k-means tree を作成する際の，k-means クラスタリングステージでの反復数の上限．ここで -1 は，k-means クラスタリングが収束するまで続けられることを意味します． * **centers_init** k-means クラスタリングの初期中心を選択するアルゴリズム．CENTERS _ RANDOM（ランダムに初期クラスタ中心を選択）， CENTERS _ GONZALES（Gonzalesのアルゴリズムを用いて初期クラスタ中心を選択）， CENTERS _ KMEANSPP（ arthur_kmeanspp_2007 で提案されたアルゴリズムを用いて初期クラスタ中心を選択）のいずれかです． * **cb_index** このパラメータ（クラスタ境界インデックス）は，階層的 k-means tree の探索方法に影響を与えます． ``cb_index`` が 0の場合，最も近い中心のクラスタが，次に探索される k-means 領域になります．0 より大きい値の場合も，領域サイズが考慮されます． * **CompositeIndexParams** この型のパラメータオブジェクトを利用すると，ランダム kd-tree と 階層的 k-means tree の組み合わせでインデックスが表現されます． .. code-block:: c 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 ); }; .. * **AutotunedIndexParams** この型のオブジェクトが渡されると，与えられたデータ集合に対して最適なインデックスの種類（ランダム kd-tree，階層的 k-means tree，線形）とパラメータが選択され，最も効率的になるように自動で調整されたインデックスが作成されます． .. code-block:: c struct AutotunedIndexParams : public IndexParams { AutotunedIndexParams( float target_precision = 0.9, float build_weight = 0.01, float memory_weight = 0, float sample_fraction = 0.1 ); }; .. * **target_precision** どれだけ厳密な最近傍を返すかを意味する，最近傍探索の近似の割合を指定する 0から1の間の値．このパラメータが大きくなると，より正確な結果が得られますが，探索時間が長くなります．最適な値は，アプリケーションに依存します． * **build_weight** 最近傍探索時間に対するインデックスの構築時間の重要度を指定します．その後のインデックス探索時間が高速になるならば，インデックスの構築時間が長くても良いというアプリケーションが存在する一方で，インデックスの探索時間が多少長くなっても，できるだけ高速にインデックスを構築する必要があるアプリケーションもあります． * **memory_weight** これは，（インデックスの構築時間と探索時間）とインデックスの占有メモリとの，トレードオフを指定するのに利用されます．1より小さい値は消費時間を重要視し，1より大きい値はメモリ使用量を重要視します． * **sample_fraction** パラメータの自動設定アルゴリズムにおけるデータ集合の比率を示す，0から1の間の値．全データ集合を用いてアルゴリズムを実行すると，最も正確な結果が得られますが，巨大なデータ集合に対しては長い計算時間がかかります．このような場合，データをある比率分だけ使うことでアルゴリズムを高速化し，なおかつ，最適なパラメータの良い近似となる結果を得ることができます． * **SavedIndexParams** この型のオブジェクトは，ディスクにあらかじめ保存されたデータを読み出すために利用されます． .. code-block:: c struct SavedIndexParams : public IndexParams { SavedIndexParams( std::string filename ); }; .. * **filename** インデックスが保存されたファイル名 .. index:: cv::flann::Index_::knnSearch cv::cv::flann::Index_::knnSearch ----------------------------------- `id=0.675734657305 Comments from the Wiki `__ .. cfunction:: void Index_::knnSearch(const vector\& query, vector\& indices, vector\& dists, int knn, const SearchParams\& params) .. cfunction:: void Index_::knnSearch(const Mat\& queries, Mat\& indices, Mat\& dists, int knn, const SearchParams\& params) インデックスを用いてクエリ点に対するk-近傍探索を行います． :param query: クエリ点． :param indices: k-近傍探索で求められたインデックスが格納されるベクトル．少なくとも knn サイズでなければいけません． :param dists: k-近傍探索で求められた距離が格納されるベクトル．最低でも knn サイズでなければいけません :param knn: この個数分の最近傍を求めます． :param params: 探索パラメータ． .. code-block:: c struct SearchParams { SearchParams(int checks = 32); }; .. * **checks** インデックスの tree が再帰的に横断されるべき回数．このパラメータが大きくなると，より正確な探索が行われますが，探索時間も長くなります．インデックス作成時に自動設定が利用されると，指定精度を達成するために必要な checks 数も計算されます．その場合，このパラメータは無視されます． .. index:: cv::flann::Index_::radiusSearch cv::cv::flann::Index_::radiusSearch -------------------------------------- `id=0.703288595249 Comments from the Wiki `__ .. cfunction:: int Index_::radiusSearch(const vector\& query, vector\& indices, vector\& dists, float radius, const SearchParams\& params) .. cfunction:: int Index_::radiusSearch(const Mat\& query, Mat\& indices, Mat\& dists, float radius, const SearchParams\& params) 与えられたクエリ点に対するradius 最近傍探索を行います． :param query: クエリ点． :param indices: 探索範囲内に存在する近傍点のインデックスが格納されるベクトル．クエリ点までの距離で降順に並びます．探索範囲内の近傍数がこのベクトルサイズよりも大きい場合，はみ出したものは無視されます． :param dists: 探索範囲内に存在する近傍点までの距離が格納されるベクトル． :param radius: 探索範囲． :param params: 探索パラメータ． .. index:: cv::flann::Index_::save cv::cv::flann::Index_::save ------------------------------ `id=0.28452898006 Comments from the Wiki `__ .. cfunction:: void Index_::save(std::string filename) インデックスをファイルに保存します． :param filename: ファイル名．ここにインデックスが保存されます． .. index:: cv::flann::Index_::getIndexParameters cv::cv::flann::Index_::getIndexParameters -------------------------------------------- `id=0.717091112599 Comments from the Wiki `__ .. cfunction:: const IndexParams* Index_::getIndexParameters() インデックスパラメータを返します．これは，自動調整されたインデックスの場合に，このメソッドを用いて計算されたパラメータを取り出す際に役立ちます．