I've been working on making various PCL methods faster recently, and
while debugging why certain methods (such as segmentation) were so slow, I came across the following behavior: while small radius searches (.01 m) were fast for ANN, and FLANN (~.3ms) larger radii take a significantly longer time (.1m taking 4ms per search for ANN) these searches were with clouds of ~80,000 pts. For comparison, I wrote a functions that simply searches every point in the whole cloud, and checks to see if it is within the radius. This function takes between .35 and .5 ms per search, no matter that the search radius, making it 10X faster for .1m radius searches, and 30X faster at radii of .8m and up! building on this, I made a depth 6 kdtreelike structure, which performs searches from 4X to 10X faster than the naive search (and between 10 and 100 times faster than ANN) The package is in: https://svn.csail.mit.edu/mitrospkg/branches/sandbox/nnn I wrote two functions: simpletest, which takes a pcd file and a tolerance, and is a simple example of how to call the library, and naivetester, which runs a multithreaded test over a range of tolerances, and compares the results of ANN and the other methods to make sure that they are indeed giving the same result. You can see a plot the performance of ANN,FLANN, the naive implementation, and a depth 3 and 6 sudokdtree (labeled sc and sc2) at: http://people.csail.mit.edu/garratt/naiveresults.png The question embedded in all of this is: why is the naive solution so much faster than the ANN and FLANN solution? I can understand that ANN and FLANN are optimized to do NN search, not necessarily radius search, but still... On the other hand, if it turns out I am not calling ANN and FLANN correctly, that would also be good to know. Thanks Garratt _______________________________________________ [hidden email] / http://pcl.ros.org https://code.ros.org/mailman/listinfo/pclusers 
Hi Garratt,
If the search radius gets large, the search algorithm will end up exploring much of the tree so it will end up looking at the majority of the points, which is what naive search does, but there's some overhead from the tree. So for a very large radius the fastest method will be naive search. You are correct that FLANN is not optimized for radius search it was originally optimized to do knn search for large dimensional data. I'm going to release a new version soon that is faster for knn search for 3D data (such as point clouds). I'll do some benchmarking for radius search and see how the new version performs on that (I didn't really look at radius search yet). Generally it's difficult to have a single implementation that works best for all types of search (knn and radius, low and high dimension) and it's possible to write a implementation that works better for one particular case (such as 3D radius search). I'll look at your sc2 implementation and if it's much faster than the generic kdtree I can include it in FLANN as a new type of index (with the proper credit of course). Marius On Mon, Nov 22, 2010 at 11:49 AM, garratt <[hidden email]> wrote: > I've been working on making various PCL methods faster recently, and > while debugging why certain methods (such as segmentation) were so slow, > I came across the following behavior: > > while small radius searches (.01 m) were fast for ANN, and FLANN (~.3ms) > larger radii take a significantly longer time (.1m taking 4ms per search > for ANN) these searches were with clouds of ~80,000 pts. > > For comparison, I wrote a functions that simply searches every point in > the whole cloud, and checks to see if it is within the radius. This > function takes between .35 and .5 ms per search, no matter that the > search radius, making it 10X faster for .1m radius searches, and 30X > faster at radii of .8m and up! > > building on this, I made a depth 6 kdtreelike structure, which performs > searches from 4X to 10X faster than the naive search (and between 10 and > 100 times faster than ANN) > > The package is in: > https://svn.csail.mit.edu/mitrospkg/branches/sandbox/nnn > I wrote two functions: > simpletest, which takes a pcd file and a tolerance, and is a simple > example of how to call the library, and naivetester, which runs a > multithreaded test over a range of tolerances, and compares the results > of ANN and the other methods to make sure that they are indeed giving > the same result. > > You can see a plot the performance of ANN,FLANN, the naive > implementation, and a depth 3 and 6 sudokdtree (labeled sc and sc2) at: > http://people.csail.mit.edu/garratt/naiveresults.png > > The question embedded in all of this is: why is the naive solution so > much faster than the ANN and FLANN solution? I can understand that ANN > and FLANN are optimized to do NN search, not necessarily radius search, > but still... > > On the other hand, if it turns out I am not calling ANN and FLANN > correctly, that would also be good to know. > > > Thanks > Garratt > > > > > _______________________________________________ > [hidden email] / http://pcl.ros.org > https://code.ros.org/mailman/listinfo/pclusers > [hidden email] / http://pcl.ros.org https://code.ros.org/mailman/listinfo/pclusers 
Administrator

Marius is probably still moving from his old apartment to the new one, so I'll steal his thunder by announcing that: he
is _awesome_! :) Marius just committed the new version of FLANN (1.6) in the trunk of point_cloud_perception, and initial tests (committed in trunk in test/test_kdtree.cpp) on nearestKSearch show: ANN nearestKSearch took 12673.1ms. FLANN nearestKSearch took 8223.04ms. for a 640x480 XYZ dataset, with k=20. Awesome!!! One step closer to getting rid of ANN. The radiusSearch is slower but that's partly because the FLANN wrapper right now does two resizes. Marius, is there a way to find the number of neighbors in the sphere first before resizing? See kdtree_ann.hpp's: 193 int neighbors_in_radius = ann_kd_tree_>annkFRSearch (&tmp[0], radius, 0, NULL, NULL, epsilon_); followed by: // Allocate enough space to hold all neighbors neighbors_in_radius = std::min (neighbors_in_radius, max_nn); k_indices.resize (neighbors_in_radius); k_squared_distances.resize (neighbors_in_radius); versus (in kdtree_flann.hpp): 171 // Find out how many neighbors does the sphere with radius `radius` contains 172 k_indices.resize (max_nn); 173 k_distances.resize (max_nn); 174 175 flann::Matrix<int> k_indices_mat (&k_indices[0], 1, max_nn); 176 flann::Matrix<float> k_distances_mat (&k_distances[0], 1, max_nn); 177 int neighbors_found = flann_index_>radiusSearch (flann::Matrix<float>(&tmp[0], 1, dim_), 178 k_indices_mat, k_distances_mat, radius, flann::SearchParams (1, epsilon_)); followed by: 191 k_indices.resize (neighbors_found); 192 k_distances.resize (neighbors_found); I think we should wait on 0.6 before we integrate Garratt's algorithms/ideas. All these things will make the kdtree support blazing fast in PCL 1.0. Great job guys! Cheers, Radu. On 11/22/2010 01:29 PM, Marius Muja wrote: > Hi Garratt, > > If the search radius gets large, the search algorithm will end up > exploring much of the tree so it will end up looking at the majority > of the points, which is what naive search does, but there's some > overhead from the tree. So for a very large radius the fastest method > will be naive search. > > You are correct that FLANN is not optimized for radius search it was > originally optimized to do knn search for large dimensional data. I'm > going to release a new version soon that is faster for knn search for > 3D data (such as point clouds). I'll do some benchmarking for radius > search and see how the new version performs on that (I didn't really > look at radius search yet). Generally it's difficult to have a single > implementation that works best for all types of search (knn and > radius, low and high dimension) and it's possible to write a > implementation that works better for one particular case (such as 3D > radius search). I'll look at your sc2 implementation and if it's much > faster than the generic kdtree I can include it in FLANN as a new > type of index (with the proper credit of course). > > > Marius > > > > > > On Mon, Nov 22, 2010 at 11:49 AM, garratt<[hidden email]> wrote: >> I've been working on making various PCL methods faster recently, and >> while debugging why certain methods (such as segmentation) were so slow, >> I came across the following behavior: >> >> while small radius searches (.01 m) were fast for ANN, and FLANN (~.3ms) >> larger radii take a significantly longer time (.1m taking 4ms per search >> for ANN) these searches were with clouds of ~80,000 pts. >> >> For comparison, I wrote a functions that simply searches every point in >> the whole cloud, and checks to see if it is within the radius. This >> function takes between .35 and .5 ms per search, no matter that the >> search radius, making it 10X faster for .1m radius searches, and 30X >> faster at radii of .8m and up! >> >> building on this, I made a depth 6 kdtreelike structure, which performs >> searches from 4X to 10X faster than the naive search (and between 10 and >> 100 times faster than ANN) >> >> The package is in: >> https://svn.csail.mit.edu/mitrospkg/branches/sandbox/nnn >> I wrote two functions: >> simpletest, which takes a pcd file and a tolerance, and is a simple >> example of how to call the library, and naivetester, which runs a >> multithreaded test over a range of tolerances, and compares the results >> of ANN and the other methods to make sure that they are indeed giving >> the same result. >> >> You can see a plot the performance of ANN,FLANN, the naive >> implementation, and a depth 3 and 6 sudokdtree (labeled sc and sc2) at: >> http://people.csail.mit.edu/garratt/naiveresults.png >> >> The question embedded in all of this is: why is the naive solution so >> much faster than the ANN and FLANN solution? I can understand that ANN >> and FLANN are optimized to do NN search, not necessarily radius search, >> but still... >> >> On the other hand, if it turns out I am not calling ANN and FLANN >> correctly, that would also be good to know. >> >> >> Thanks >> Garratt >> >> >> >> >> _______________________________________________ >> [hidden email] / http://pcl.ros.org >> https://code.ros.org/mailman/listinfo/pclusers >> > _______________________________________________ > [hidden email] / http://pcl.ros.org > https://code.ros.org/mailman/listinfo/pclusers [hidden email] / http://pcl.ros.org https://code.ros.org/mailman/listinfo/pclusers 
Free forum by Nabble  Edit this page 