Ask Your Question
1

How to use cv::flann (radiusSearch) to find all neighbouring points within radius r in 2D using Euclidean distance

asked 2016-10-27 14:41:07 -0500

socratic gravatar image

I have a std::vector of a couple million points (cv::Point2d) and I'd like to find, for every point, all other points within a 2 pixel radius.

Since my project already requires OpenCV, I thought it would be useful to use the cv::flann module. However, I haven't made much progress with my attempts so far. In particular, I'm not sure how to present my data to the index constructor. Here is my best attempt:

#include <iostream>
#include <vector>
#include <opencv2/opencv.hpp>
#include <opencv2/flann.hpp>


int main(int argc, char* argv[]) {

  // Sample data
  std::vector<cv::Point2d> points;
  points.emplace_back(438.6,268.8);
  points.emplace_back(439.1,268.6);
  points.emplace_back(438.2,268.1);
  points.emplace_back(498.3,285.9);
  points.emplace_back(312.9,245.9);
  points.emplace_back(313.4,245.7);
  points.emplace_back(313.1,245.5);
  points.emplace_back(312.5,245.4);
  points.emplace_back(297.6,388.1);
  points.emplace_back(291.7,309.8);
  points.emplace_back(194.1,369.8);
  points.emplace_back(439.9,314.9);
  points.emplace_back(312.8,246.0);

  // Create an empty Mat for the features that includes dimensional
  // space for an x and y coordinate
  cv::Mat_<double> features(0,2);

  for(auto && point : points) {

    //Fill matrix
    cv::Mat row = (cv::Mat_<double>(1, 2) << point.x, point.y);
    features.push_back(row);
  }
  std::cout << features << std::endl;

  cv::flann::Index flann_index(features, cv::flann::KDTreeIndexParams(1));


  unsigned int max_neighbours = 10;
  cv::Mat query = (cv::Mat_<double>(1, 2) << 313.0, 245.6);
  //Ensure indices and dists have enough space for at least max_neighbours
  cv::Mat_<double> indices(max_neighbours, 2) ;
  cv::Mat_<double> dists(max_neighbours, 2);
  double radius= 2.0;

  flann_index.radiusSearch(query, indices, dists, radius, max_neighbours,
      cv::flann::SearchParams(32));
}

The code compiles, but I receive a runtime error:

OpenCV Error: Unsupported format or combination of formats (type=6
) in buildIndex_, file /opt/opencv/modules/flann/src/miniflann.cpp, line 315
terminate called after throwing an instance of 'cv::Exception'
  what():  /opt/opencv/modules/flann/src/miniflann.cpp:315: error: (-210) type=6
 in function buildIndex_

Aborted (core dumped)

Can anyone please help me figure out how to use radiusSearch? And how can I configure the radiusSearch to find all neighbours, instead of just max_neighbours? Thanks in advance.

edit retag flag offensive close merge delete

Comments

I modify radiusSearch to knnSearch and It works:

std::vector<int> indices; std::vector<float> dists; std::vector<float> query; // Insert the 2D point we need to find neighbours to the query query.push_back(f.x); query.push_back(f.y); kdtree.knnSearch(query, indices, dists, numOfPoints);

xavier12358 gravatar imagexavier12358 ( 2019-02-04 02:37:50 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
3

answered 2016-10-27 22:21:44 -0500

berak gravatar image

please use float Mat's here (it seems it can't handle anything else), also do not pre-allocate your indices & dists for the radiusSearch():

  cv::Mat_<float> features(0,2);

  for(auto && point : points) {

    //Fill matrix
    cv::Mat row = (cv::Mat_<float>(1, 2) << point.x, point.y);
    features.push_back(row);
  }
  std::cout << features << std::endl;

  cv::flann::Index flann_index(features, cv::flann::KDTreeIndexParams(1));


  unsigned int max_neighbours = 10;
  cv::Mat query = (cv::Mat_<float>(1, 2) << 313.0, 245.6);
  cv::Mat indices, dists; //neither assume type nor size here !
  double radius= 2.0;

  flann_index.radiusSearch(query, indices, dists, radius, max_neighbours,
      cv::flann::SearchParams(32));

  cerr << indices.type() << endl << indices << endl;
  cerr << dists.type() << endl << dists << endl;

4
[6, 4, 5, 12, 7, 0, 0, 0, 0, 0]
5
[0.020002441, 0.099993892, 0.1699933, 0.2, 0.29000488, 0, 0, 0, 0, 0]
edit flag offensive delete link more

Comments

2

Thank you so much for your response. Is there any way to avoid specifying the number of neighbours to find? The trailing zeros take up memory, and it won't be clear if the indices indicate the first element or no-more-elements.

socratic gravatar imagesocratic ( 2016-10-28 09:23:21 -0500 )edit
2

that's some kind of procrustes problem right ? (either too long, or too short)

though your requirement makes a lot of sense to me, - no idea, how to solve it, unfortunately ;(

berak gravatar imageberak ( 2016-10-28 10:30:53 -0500 )edit

OK. Thanks again for your help.

socratic gravatar imagesocratic ( 2016-10-28 11:09:10 -0500 )edit
Login/Signup to Answer

Question Tools

1 follower

Stats

Asked: 2016-10-27 14:41:07 -0500

Seen: 2,103 times

Last updated: Oct 27 '16