slow radius searches with ANN and FLANN

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

slow radius searches with ANN and FLANN

garratt
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 kdtree-like 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/mit-ros-pkg/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 sudo-kdtree (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/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: slow radius searches with ANN and FLANN

Marius Muja-2
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 k-nn search for large dimensional data. I'm
going to release a new version soon that is faster for k-nn 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 (k-nn 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 kd-tree 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 kdtree-like 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/mit-ros-pkg/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 sudo-kdtree (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/pcl-users
>
_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: slow radius searches with ANN and FLANN

Radu B. Rusu
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 k-nn search for large dimensional data. I'm
> going to release a new version soon that is faster for k-nn 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 (k-nn 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 kd-tree 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 kdtree-like 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/mit-ros-pkg/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 sudo-kdtree (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/pcl-users
>>
> _______________________________________________
> [hidden email] / http://pcl.ros.org
> https://code.ros.org/mailman/listinfo/pcl-users
_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users