OpenCVのradiusSearch

by

今日OpenCVのradiusSearchを使っていてハマったのでメモ．
radiusSearchとは，「ある点（検索クエリ）から半径(radius)いくら以内にある点を探す」という処理．例えば，画像上にいくつかの特徴点があるときにある特徴点から距離r以内にある点を探す，とか，特徴空間中のある点から距離r以内にある点を探す，といったことに使う．実装上は，前者なら画像上の座標を，後者なら特徴空間中の座標＝特徴量を各行の値として入れた行列（列数＝点の数，行数＝座標や特徴量の次元数）に対してIndexというものを作り，そのIndexを使ってradiusSearchを行う．
普通，何も考えずに上記の処理を行おうとすると，ある点と他の全ての点との距離を計算してソートし，上位のものを返せば良いが，それは計算量が大きい．特に何度もそういった処理を繰り返す場合．
これに対して，予め索引を作っておき，高速に検索できるようにするのがIndex．例えば，(Randomized) kd-treeや，Locality-Sensitive Hashing (LSH)などの手法がある．
以下ではRandomized kd-treeの使い方を簡単に説明する．ここで検索対象のデータは，cv::Mat型の変数dataに，前述のとおり，点数(行)×次元数(列)の行列として格納されているとする．この例では，各点から距離r内にある点のうち最大maxRadius個をすべて求める例である．

// 予めIndexを作成しておく．この例ではRandomized KDTreeをTree数4で
cv::flann::Index idx(data, cv::flann::KDTreeIndexParams(4), cvflann::FLANN_DIST_EUCLIDEAN);
int maxRadius=10; // 最大10個の点を求める
for(int i=0; i<data.rows; i++){
    cv::Mat_<int> indices; // dataの何行目か
    cv::Mat_<float> dists; // それぞれどれだけの距離だったか
    idx.radiusSearch(query, indices, dists, r, maxResults);
    for(int j=0;j<indices.row; j++){
        std::cout << indices(j,0) << "[" << dists.row(j) << "]" << " " << std::endl;
    }
}

こちらの公式ドキュメントでは引数が5個だったが，本当は5個目の引数にmaxResultsが必要（６個目の引数は省略可）．

コメントする