Opencv uses genericindex for KNN search

I didn't know OpenCV Of flann modular , do K-nearest-neighbour Search has been using Github A very simple implementation on ：kd-tree. This KD tree The implementation is simple , Only one header file , Easy to join your own project , And it's very convenient to use . But it's said cv::flann Realized KNN Faster , And more powerful , So I took a look at how to use .

In view of the current lack of relevant information on the Internet , And basically all you can find is about what has been abandoned cv::flann::Index,OpenCV Official documents also lack relevant instructions , I'm here to record what I know cv::flann::GenericIndex Usage of （ In fact, there are still many things I don't understand , Welcome to comment area ）.

Sample code

// generate points
constexpr size_t num = 100;
constexpr int width = 640, height = 480;
vector<Point2f> pts;
Mat image(height, width, CV_8UC3, cv::Scalar::all(255));
{
    
    mt19937 gen(0);
    uniform_real_distribution<float> dis_x(0.f, float(width));
    uniform_real_distribution<float> dis_y(0.f, float(height));
    pts.reserve(num);
    for (size_t i = 0; i < num; ++i) {
    
        pts.emplace_back(dis_x(gen), dis_y(gen));
        circle(image, pts.back(), 2, cv::Scalar::all(0), cv::FILLED);
    }
}
cout << "num of points: " << pts.size() << '\n';
Point2f query(width / 2.f, height / 2.f);
cout << "query: " << query.x << " " << query.y << '\n';
circle(image, query, 2, {
     0, 0, 255 }, cv::FILLED);

// build kd-tree
auto kdtree = flann::GenericIndex(Mat(pts).reshape(1), cvflann::KDTreeIndexParams {
     2 }, flann::L2<float> {
    });

// knn search
constexpr int K = 4;
vector<int> indices(K);
vector<float> dists(K);
kdtree.knnSearch({
     query.x, query.y }, indices, dists, K, cvflann::SearchParams {
    });
cout << " nearest " << K << ": " << Mat(indices).t() << endl;
{
    
    Mat result = image.clone();
    for (int i : indices) {
    
        line(result, query, pts[i], {
     0, 255, 0 });
        circle(result, pts[i], 2, {
     255, 0, 0 }, cv::FILLED);
    }
    imwrite("knn_result.png", result);
}

// radius search
constexpr float radius = 50.f;
constexpr size_t max_num = 10;
indices.resize(max_num, -1);
dists.resize(max_num);
kdtree.radiusSearch({
     query.x, query.y }, indices, dists, radius * radius, cvflann::SearchParams {
    });
cout << "in radius " << radius << ": " << Mat(indices).t() << endl;
{
    
    Mat result = image.clone();
    for (int i : indices) {
    
        if (i < 0)
            break;
        line(result, query, pts[i], {
     0, 255, 0 });
        circle(result, pts[i], 2, {
     255, 0, 0 }, cv::FILLED);
    }
    circle(result, query, radius, {
     0, 0, 255 });
    imwrite("radius_result.png", result);
}

This example is in size 640×480 Randomly generated on the image 100 A little bit , And then use it KD tree Find the nearest... To the center of the image 4 A little bit （KNN search）, And the distance from the center of the image is less than 50 Pixel point （radius search）：

flann::GenericIndex Support violent search (LinearIndexParams)、KD tree (KDTreeIndexParams)、 Hierarchical clustering (HierarchicalClusteringIndexParams) Equal search strategy , Support at the same time L1、L2、Hamming Equidistance calculation method , It's really powerful , See OpenCV Docs.

It should be noted that , In the use of L2 In the case of distance , radiusSearch Medium radius The parameter is actually the square of the radius （ So the code says radius*radius）, See issue#12683.