クラスタリングと多次元空間探索 ============================================= .. highlight:: cpp .. index:: kmeans cv::kmeans ---------- .. cfunction:: double kmeans( const Mat\& samples, int clusterCount, Mat\& labels, TermCriteria termcrit, int attempts, int flags, Mat* centers ) クラスタ中心を求め，入力サンプルを各クラスタにグループ分けします． :param samples: 入力サンプルの浮動小数点型行列．1行が1つのサンプルを表します :param clusterCount: サンプル集合を分割するクラスタ数 :param labels: 整数型の入出力配列．各要素が属するクラスタのインデックスを格納します :param termcrit: 反復数の最大値 および/または 精度（連続する試行間でクラスタ中心が移動する距離）を指定します :param attempts: このアルゴリズムが，異なる初期ラベルを与えられて実行される回数．このアルゴリズムは，最もコンパクトな分割を行うラベル（最後のパラメータを参照してください）を返します :param flags: 以下の値をとることができます： * **KMEANS_RANDOM_CENTERS** 各試行で，ランダムな初期中心が選択されます * **KMEANS_PP_CENTERS** Arthur および Vassilvitskiiによる kmeans++ の中心初期化手法が利用されます * **KMEANS_USE_INITIAL_LABELS** 最初の試行で（だけ）は，ランダムに生成されるラベルの代わりに，ユーザが与えたラベルを初期推定値として利用します．2回目以降の試行では，ランダムまたは半ランダム（手法を指定するために ``KMEANS_*_CENTERS`` フラグの1つを利用します）に選択された中心が用いられます :param centers: クラスタ中心の出力行列．1つの行が1つのクラスタ中心を表します 関数 ``kmeans`` は， ``clusterCount`` 個のクラスタの中心を求め，入力サンプルを各クラスタに分類する k-means アルゴリズムの実装です．出力として， ``samples`` 行列の :math:`i^{th}` 行目のサンプルが属するクラスタの（0基準の）インデックスが， :math:`\texttt{labels}_i` に格納されます． この関数は，次のように計算されるコンパクト尺度を返します． .. math:: \sum _i \| \texttt{samples} _i - \texttt{centers} _{ \texttt{labels} _i} \| ^2 全試行の終了後，最もよい（小さい）値が選択され，それに対応するラベルとコンパクト尺度が戻り値として返されます． また，基本的に次のようにして，ユーザはこの関数の基本機能だけを利用することができます．まず，試行回数を1にセットし，フラグ（ ``flags`` = ``KMEANS_USE_INITIAL_LABELS`` ）をセットして，独自アルゴリズムによりラベルを毎回初期化します そして，最良の（最もコンパクトな）クラスタリングを選択します． .. index:: partition cv::partition ------------- .. cfunction:: template int .. cfunction:: partition( const vector<_Tp>\& vec, vector\& labels, _EqPredicate predicate=_EqPredicate()) 要素の集合を同値クラス（同値類）に分割します． :param vec: ベクトルで表現された要素の集合 :param labels: 出力されるラベルのベクトル． ``vec`` と同じ要素数．各ラベル ``labels[i]`` は， ``vec[i]`` が属する0基準のクラスタインデックスです :param predicate: 同値述語（つまり，2つの引数をとり真偽値を返す関数へのポインタ，あるいは， ``bool operator()(const _Tp& a, const _Tp& b)`` メソッドを持つクラスのインスタンスへのポインタ）．この述語は，要素が確実に同じクラスならば真値を返し，同じクラスの可能性がある（同じクラスではない可能性がある）場合は偽値を返します 汎用関数 ``partition`` は， :math:`N` 個の要素の集合を1つまたは複数の同値類に分割する :math:`O(N^2)` のアルゴリズムの実装です．これについては http://en.wikipedia.org/wiki/Disjoint-set_data_structure で説明されています．また，この関数は，同値類の個数を返します． K-近傍探索の高速な近似計算 -------------------------------------- このセクションでは，OpenCV の FLANN ライブラリインタフェースについて説明します．FLANN（Fast Library for Approximate Nearest Neighbors）は，K-近傍探索の高速な近似計算アルゴリズムの集合体で，巨大なデータセットと高次元特徴量に対して最適化されています．FLANN についてさらに詳しく知りたい場合は， muja_flann_2009 を参照してください． .. index:: cvflann::Index .. _cvflann::Index: cvflann::Index -------------- .. ctype:: cvflann::Index FLANN 最近傍インデックスクラス :: namespace cvflann { class Index { public: Index(const Mat& features, const IndexParams& params); 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; }; } .. .. index:: cvflann::Index::Index cv::cvflann::Index::Index ------------------------- .. cfunction:: Index::Index(const Mat\& features, const IndexParams\& params) 与えられたデータセットの最近傍探索インデックスを作成します． :param features: インデックス作成対象となる特徴（点）が格納された， ``CV_32F`` 型の行列．この行列のサイズは matrix is num _ features x feature _ dimensionality となります :param 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** インデックスが保存されたファイル名 .. index:: cvflann::Index::knnSearch cv::cvflann::Index::knnSearch ----------------------------- .. cfunction:: void Index::knnSearch(const vector\& query, vector\& indices, vector\& dists, int knn, const SearchParams\& params) インデックスを用いてクエリ点に対するk-近傍探索を行います． :param query: クエリ点 :param indices: k-近傍探索で求められたインデックスが格納されるベクトル．最低でも knn サイズでなければいけません :param dists: k-近傍探索で求められた距離が格納されるベクトル．最低でも knn サイズでなければいけません :param knn: この個数分の最近傍を求めます :param params: 探索パラメータ :: struct SearchParams { SearchParams(int checks = 32); }; .. * **checks** インデックスの tree が再帰的に横断されるべき回数．このパラメータが大きくなると，より正確な探索が行われますが，探索時間も長くなります．インデックス作成時に自動設定が利用されると，指定精度を達成するために必要な checks 数も計算されます．その場合，このパラメータは無視されます .. index:: cvflann::Index::knnSearch cv::cvflann::Index::knnSearch ----------------------------- .. cfunction:: void Index::knnSearch(const Mat\& queries, Mat\& indices, Mat\& dists, int knn, const SearchParams\& params) 複数のクエリ点に対するk-近傍探索を行います． :param queries: クエリ点．1行が1つの点を表します :param indices: 求められた最近傍のインデックス :param dists: 求められた最近傍までの距離 :param knn: この個数分の最近傍を求めます :param params: 探索パラメータ .. index:: cvflann::Index::radiusSearch cv::cvflann::Index::radiusSearch -------------------------------- .. cfunction:: int Index::radiusSearch(const vector\& query, vector\& indices, vector\& dists, float radius, const SearchParams\& params) 与えられたクエリ点に対するradius 最近傍探索を行います． :param query: クエリ点 :param indices: 探索範囲内に存在する近傍点のインデックスが格納されるベクトル．クエリ点までの距離で降順に並びます．探索範囲内の近傍数がこのベクトルサイズよりも大きい場合，はみ出したものは無視されます :param dists: 探索範囲内に存在する近傍点までの距離が格納されるベクトル :param radius: 探索範囲 :param params: 探索パラメータ .. index:: cvflann::Index::radiusSearch cv::cvflann::Index::radiusSearch -------------------------------- .. cfunction:: int Index::radiusSearch(const Mat\& query, Mat\& indices, Mat\& dists, float radius, const SearchParams\& params) 複数のクエリ点に対するradius 最近傍探索を行います． :param queries: クエリ点．1行が1つの点を表します :param indices: 求められた最近傍のインデックス :param dists: 求められた最近傍までの距離 :param radius: 探索範囲 :param params: 探索パラメータ .. index:: cvflann::Index::save cv::cvflann::Index::save ------------------------ .. cfunction:: void Index::save(std::string filename) インデックスをファイルに保存します． :param filename: インデックスを保存するファイル名 .. index:: cvflann::hierarchicalClustering cv::cvflann::hierarchicalClustering ----------------------------------- .. cfunction:: int hierarchicalClustering(const Mat\& features, Mat\& centers, const KMeansIndexParams\& params) 階層的 k-means tree を構築し，クラスタの分散を最小にするカットを選択することで，与え得られた点群を分類します． :param features: クラスタリングされる点 :param centers: 得られるクラスタの中心．この行列の行数は要求クラスタ数を表します．しかし，階層的 k-means tree のカットを選択する方法により，求められるクラスタ数は，要求クラスタ数より小さい値 :math:`(branching-1)*k+1` の最大値になります．ここで :math:`branching` は tree の branching ファクタ（KMeansIndexParams の説明を参照してください） :param params: 階層的 k-means tree を構築する際に利用されるパラメータ このメソッドは，求められたクラスタ数を返します．