K-近傍探索の高速な近似計算

このセクションでは，FLANN ライブラリに対する OpenCVのインタフェースについて説明します．FLANN（Fast Library for Approximate Nearest Neighbors）は，K-近傍探索の高速な近似計算アルゴリズムのコレクションで，巨大なデータセットと高次元特徴量に対して最適化されています．FLANN についてさらに詳しく知りたい場合は， muja_flann_2009 を参照してください．

cv::flann::Index_

Comments from the Wiki

cv::flann::Index_

FLANN 最近傍インデックスクラス．このクラスは，要素の型でテンプレート化されており，この要素に対するインデックスが構築されます．

namespace cv
{
namespace flann
{
    template <typename T>
    class Index_
    {
    public:
            Index_(const Mat& features, const IndexParams& params);

            ~Index_();

            void knnSearch(const vector<T>& query,
                           vector<int>& indices,
                           vector<float>& dists,
                           int knn,
                           const SearchParams& params);
            void knnSearch(const Mat& queries,
                           Mat& indices,
                           Mat& dists,
                           int knn,
                           const SearchParams& params);

            int radiusSearch(const vector<T>& query,
                             vector<int>& indices,
                             vector<float>& 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_<float> Index;

} } // namespace cv::flann

cv::cv::flann::Index_<T>::Index_

Comments from the Wiki

Index_<T>::Index_(const Mat& features, const IndexParams& params)

与えられたデータセットの最近傍探索インデックスを作成します．

パラメタ:

• features – インデックス作成対象となる特徴（点）が格納された行列．この行列のサイズは matrix is num _ features x feature _ dimensionality となります． また行列の要素のデータ型は，インデックスの種類と一致していなければいけません．
• params – インデックスパラメータを含む構造体．作成されるインデックスの種類は，このパラメータの種類に依存します．

選択できるパラメータの種類を以下に示します：

• LinearIndexParams この型のオブジェクトが渡されると，インデックスに対して，線形のブルートフォース探索が行われます．

struct LinearIndexParams : public IndexParams
{
};

• KDTreeIndexParams この型のオブジェクトが渡されると，ランダム kd-tree の集合でインデックスが表現され，これは並列に探索されます．

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

• trees 並列な kd-tree の個数．[1..16] の範囲が適切な値です．

• KMeansIndexParams この型のオブジェクトが渡されると，階層型 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 );
};

• 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 の組み合わせでインデックスが表現されます．

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，線形）とパラメータが選択され，最も効率的になるように自動で調整されたインデックスが作成されます．

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 この型のオブジェクトは，ディスクにあらかじめ保存されたデータを読み出すために利用されます．

struct SavedIndexParams : public IndexParams
{
    SavedIndexParams( std::string filename );
};

• filename インデックスが保存されたファイル名

cv::cv::flann::Index_<T>::knnSearch

Comments from the Wiki

void Index_<T>::knnSearch(const vector<T>& query, vector<int>& indices, vector<float>& dists, int knn, const SearchParams& params)

void Index_<T>::knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const SearchParams& params)

インデックスを用いてクエリ点に対するk-近傍探索を行います．

パラメタ:

• query – クエリ点．
• indices – k-近傍探索で求められたインデックスが格納されるベクトル．少なくとも knn サイズでなければいけません．
• dists – k-近傍探索で求められた距離が格納されるベクトル．最低でも knn サイズでなければいけません
• knn – この個数分の最近傍を求めます．
• params – 探索パラメータ．

struct SearchParams {
        SearchParams(int checks = 32);
};

• checks インデックスの tree が再帰的に横断されるべき回数．このパラメータが大きくなると，より正確な探索が行われますが，探索時間も長くなります．インデックス作成時に自動設定が利用されると，指定精度を達成するために必要な checks 数も計算されます．その場合，このパラメータは無視されます．

cv::cv::flann::Index_<T>::radiusSearch

Comments from the Wiki

int Index_<T>::radiusSearch(const vector<T>& query, vector<int>& indices, vector<float>& dists, float radius, const SearchParams& params)

int Index_<T>::radiusSearch(const Mat& query, Mat& indices, Mat& dists, float radius, const SearchParams& params)

与えられたクエリ点に対するradius 最近傍探索を行います．

パラメタ:

• query – クエリ点．
• indices – 探索範囲内に存在する近傍点のインデックスが格納されるベクトル．クエリ点までの距離で降順に並びます．探索範囲内の近傍数がこのベクトルサイズよりも大きい場合，はみ出したものは無視されます．
• dists – 探索範囲内に存在する近傍点までの距離が格納されるベクトル．
• radius – 探索範囲．
• params – 探索パラメータ．

cv::cv::flann::Index_<T>::save

Comments from the Wiki

void Index_<T>::save(std::string filename)

インデックスをファイルに保存します．

パラメタ:

• filename – ファイル名．ここにインデックスが保存されます．

cv::cv::flann::Index_<T>::getIndexParameters

Comments from the Wiki

const IndexParams* Index_<T>::getIndexParameters()

インデックスパラメータを返します．これは，自動調整されたインデックスの場合に，このメソッドを用いて計算されたパラメータを取り出す際に役立ちます．