Search code examples
opencvflann

FLANN in opencv runs too slow

I have a set of point cloub(number of point cloub≈2million). I would like to find the nearest k neighbor for each point within the point cloub. I did something like this 

flann::Index flann_index(data_m, flann::KDTreeIndexParams(),cvflann::FLANN_DIST_EUCLIDEAN);// create the object of flann
    for (int i = 0; i < numberOfPointsInPointCloub; i++){
    flann_index.knnSearch(data_m.row(i), indices, dists,num_of_knn); //each row is a new set of point in 3D
    ..//save the results "dist" and "indices" in somewhere else
}

But this runs very slow. Within the for loop, it runs 1000 times for 20 seconds which is very slow. Am I use it wrongly? Or are there any method so that I can speed it up?

Update: The query point that I need to search is exactly the point used to construct the tree, I need to find the nearest k neighbor for each of the point within the tree thus I take the point from each row of the data and perform a knnSearch.

Solution

  • I was having similar issues recently. Here are some ideas:

    First, make sure you are in release mode. Unoptimized code can seriously affect performance. My most recent test showed an improvement of 70x after a switch from debug to release code.

    Second, you are using the default value for flann::KDTreeIndexParams(), which is 4 trees. For speed you can reduce this to 1. This may reduce accuracy, but could help in performance.

    Third, at least in recent versions of OpenCV there is a fifth parameter for the knnSearch function, namely SearchParams(). Its constructor's first parameter, which "specifies the number of times the tree(s) in the index should be recursively traversed", can be modified to balance performance with accuracy. See the OpenCV documentation for details.

    Fourth, it seems you are searching for the neighbors of one query point at a time. Try running with several query points at a time. The return parameters "indices" and "dists" will be matrices where each row r represents the neighbors of the point at index r (and the first element of each row represents the query point itself).

    Finally, if this is still not fast enough, perhaps check out the KdTree implementation in VCG ibrary. So far I've seen release mode performance gains of > 2x over OpenCV's FLANN. You can also try parallelizing, though I would only go down this road once you've eked out as much performance as possible from your non-parallel version.