今日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が必要(6個目の引数は省略可).