Find Closest Neighbors - OpenCV

Question

I do have a set of openCV Point2f type image points (coordinates). I want to find the 4 nearest neighbors of each point in that set. Is there any specific build-in function in openCV to do this or should I measure the distance between each point and decide the four closest?

Answer 1

Following code will help to find the nearest neighbors of a selected point out of a set of points.

vector<Point2f> pointsForSearch; //Insert all 2D points to this vector
flann::KDTreeIndexParams indexParams;
flann::Index kdtree(Mat(pointsForSearch).reshape(1), indexParams);
vector<float> query;
query.push_back(pnt.x); //Insert the 2D point we need to find neighbours to the query
query.push_back(pnt.y); //Insert the 2D point we need to find neighbours to the query
vector<int> indices;
vector<float> dists;
kdtree.radiusSearch(query, indices, dists, range, numOfPoints);

indices gives the indexes of selected neighbors and dists gives the distances for selected neighbors.

Answer 2

This tutorial could be helpful.

It offers an example of training (as far as I know either using the KNearest constructor or train() method; check the documentation) and recognizing items (by utilizing, as @sietschie mentioned find_nearest() method).

find_nearest() takes an int k value representing the needed amount of neighbors upon which classification is based, the k neighbors' labels could be optionally returned through the parameter neighborResponses, as taken from find_nearest() documentation linked earlier:

neighborResponses – Optional output values for corresponding neighbors.

where, again as part of the documentation, neighbors are:

neighbors – Optional output pointers to the neighbor vectors themselves.

I'm not experienced with those parameters, however provided I understood correctly, neighbors offer the actual neighbors' values, while neighborResponses offers their labels.

Answer 3

Here is small example how to find 3 closest points to (370,464):

#include "opencv2/flann/miniflann.hpp"

vector<Point2f> cloud2d;
flann::KDTreeIndexParams indexParams;
flann::Index kdtree(Mat(cloud2d).reshape(1), indexParams);
vector<float> query;
query.push_back(370); 
query.push_back(464); 
vector<int> indices;
vector<float> dists;
kdtree.knnSearch(query, indices, dists, 3);
// cloud2d[indices[0]] -- is your first point now
// cloud2d[indices[1]] and cloud2d[indices[2]] -- is your 2nd and 3rd point

Please note that function behaves crazy if some of points have NAN coordinates, this may be the case if you divide by 0.0 somewhere before.

Answer 4

You could use the k Nearest Neighbour classifier CvKNearest. After you trained the classifier with all your points you can get the k nearest neighbours with calling the function CvKNearest::find_nearest.