導入
元論文：
FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
高次元空間である点に対する最近傍点を探索する問題はよく直面するが計算量コストがかかる。全探索より高速なアルゴリズムは知られていない。しかし近似アルゴリズムとしてはhierarchical k-means treeとrandomized k-d tree が高速であることがわかった。線形探索より1000倍高速である一方で95%の精度（一番遠い点を0%、近い点を100%とした時の選択された点の値）を保っていることがわかった。
k-d tree
まずk-d treeについてまとめる。k-d treeは事前に領域を細かく区切って二分木のような構成をつくっておき、最近傍点を探索するときはクエリ点に近い領域のみを調べることで時間を短縮する。segment treeの多次元版のようなイメージである。領域分割は分散が大きい軸に垂直な超平面で分割すると効率が良い。各領域に代表点を1つ用意しておき、領域を探索するときにクエリ点と代表点の距離の最小値をどんどん更新していく。
参考： github.com
Randomized k-d tree
k-d treeと基本的な考え方は同じである。k-d treeでは領域分割は分散が最も大きくなる軸に垂直な超平面で分割していたが、ここを少し変える。分散が大きい軸上位D軸をリストアップし、その中からランダムに軸を選んで領域を分割する。分割が完了した後最近傍点を探索する時は、query pointに対して各領域までの距離をpriority queueに入れておき、小さい順に取り出して最小値を更新していく（最小値よりも離れている領域は探索しない）ことで求める。このとき全ての領域を探索せず、小さい順に探索して行った途中で止めることで高速化を図る。
Hierarchical k-means tree algorithm
1つの領域をk-meansクラスタリング手法によってk領域に分割するという操作を再帰的に行い、領域内の点数が閾値以下になるまで繰り返す手法。Randomized k-d treeと同様、priority queueを使って小さい順にいくつかの領域を探索して最近傍点を求める。
OpenCVのライブラリ
OpenCVのFast Approximate Nearest Neighbor Searchにそれらを計算してくれるライブラリがある。
- knnSearch: （おそらく）priorirty queueに入っている小さい順の点をkこ見るまで探索を続ける方法
- radiusSearch:（おそらく）priority queueに入っている小さい順に距離rを超えるまでの全ての点を探索する方法
サンプルコード (OpenCV forumを参考にした)
#include <iostream>
#include <vector>
#include <opencv2/opencv.hpp>
#include <opencv2/flann.hpp>
#include <TRandom.h>
cv::Mat_<float> features(0,2);
void generate_points(const int repeatnum) {
gRandom->SetSeed(0);
// Sample data
for (int i=0; i<repeatnum; i++) {
double x = gRandom->Uniform(0, 100);
double y = gRandom->Uniform(0, 100);
cv::Mat row = (cv::Mat_<float>(1, 2) << x, y);
features.push_back(row);
}
return;
}
int main() {
// generate random points on plane
const int repeatnum = 100;
generate_points(repeatnum);
// set flan
cv::flann::Index flann_index(features, cv::flann::KDTreeIndexParams(1));
// define query point
double qx = 50.0, qy = 50.0;
unsigned int max_neighbours = 10;
cv::Mat query = (cv::Mat_<float>(1, 2) << qx, qy);
cv::Mat indices, dists;
double radius= 1000.0;
flann_index.radiusSearch(query, indices, dists, radius, max_neighbours, cv::flann::SearchParams(32));
int nearest_index = indices.at<int>(0, 0);
float nearest_distance = dists.at<float>(0, 0);
std::cout << "nearest index = " << nearest_index << ": dist=" << nearest_distance << std::endl;
return 0;
}
g++ -g `pkg-config --libs --cflags opencv4` `root-config --cflags --libs` test.cpp
