flann, ann radiusSearch max responses parameter

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

flann, ann radiusSearch max responses parameter

garratt
Hi Marius, et. al.:

when I run radiusSearch on a flann tree, it only returns 200 points,
when I should be getting more.

I tracked the problem into kdtree_flann.hpp, where
KdTreeFLANN<PointT>::radiusSearch
uses the value set in flann_param_.checks rather than max_nn.

flann_param_.checks has been set to 200 in initParameters()
to 200.

I can change the code to set the flann_param_.checks value, (I'll copy
the flann_param struct to maintain an illusion of thread safety, and I'm
thinking the default value should be the size of the point cloud,
instead of INT_MAX)


specifically to Marius:
flann_param_.checks has this description:
/* how many leafs (features) to check in one search */

the flann manual says it is: denoting the number of times the
tree(s) in the index should be recursively traversed

setting the checks parameter limits the number of returns to be <= the
checks value (in my testing), but are there guarantees that it will find
that many points (if they exist) ?  



On another note, in kdtree_ann.hpp the number of nearest neighbors is
set by:
int neighbors_in_radius = ann_kd_tree_->annkFRSearch (&tmp[0], radius,
0, NULL, NULL, epsilon_);
neighbors_in_radius  = std::min(neighbors_in_radius, max_nn);

do I interpret this correctly to mean that ann performs 2 radius
searches (the first one to just find out how big to make the
indices,dist vectors)?


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: flann, ann radiusSearch max responses parameter

garratt-2
oh, and as might be expected, kdTreeANN does not have the problem of
returning too few points.

my test code for this can be found at:
https://svn.csail.mit.edu/mit-ros-pkg/branches/sandbox/furniture_ops/src/test_radiusSearch.cpp

cheers,
Garratt

On Wed, 2010-10-13 at 14:11 -0400, garratt wrote:

> Hi Marius, et. al.:
>
> when I run radiusSearch on a flann tree, it only returns 200 points,
> when I should be getting more.
>
> I tracked the problem into kdtree_flann.hpp, where
> KdTreeFLANN<PointT>::radiusSearch
> uses the value set in flann_param_.checks rather than max_nn.
>
> flann_param_.checks has been set to 200 in initParameters()
> to 200.
>
> I can change the code to set the flann_param_.checks value, (I'll copy
> the flann_param struct to maintain an illusion of thread safety, and I'm
> thinking the default value should be the size of the point cloud,
> instead of INT_MAX)
>
>
> specifically to Marius:
> flann_param_.checks has this description:
> /* how many leafs (features) to check in one search */
>
> the flann manual says it is: denoting the number of times the
> tree(s) in the index should be recursively traversed
>
> setting the checks parameter limits the number of returns to be <= the
> checks value (in my testing), but are there guarantees that it will find
> that many points (if they exist) ?  
>
>
>
> On another note, in kdtree_ann.hpp the number of nearest neighbors is
> set by:
> int neighbors_in_radius = ann_kd_tree_->annkFRSearch (&tmp[0], radius,
> 0, NULL, NULL, epsilon_);
> neighbors_in_radius  = std::min(neighbors_in_radius, max_nn);
>
> do I interpret this correctly to mean that ann performs 2 radius
> searches (the first one to just find out how big to make the
> indices,dist vectors)?
>
>
> 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: flann, ann radiusSearch max responses parameter

Marius Muja-2
In reply to this post by garratt


On Wed, Oct 13, 2010 at 11:11 AM, garratt <[hidden email]> wrote:
Hi Marius, et. al.:

when I run radiusSearch on a flann tree, it only returns 200 points,
when I should be getting more.

I tracked the problem into kdtree_flann.hpp, where
KdTreeFLANN<PointT>::radiusSearch
uses the value set in flann_param_.checks rather than max_nn.

flann_param_.checks has been set to 200 in initParameters()
to 200.

I can change the code to set the flann_param_.checks value, (I'll copy
the flann_param struct to maintain an illusion of thread safety, and I'm
thinking the default value should be the size of the point cloud,
instead of INT_MAX)


specifically to Marius:
flann_param_.checks has this description:
/* how many leafs (features) to check in one search */

the flann manual says it is: denoting the number of times the
tree(s) in the index should be recursively traversed

setting the checks parameter limits the number of returns to be <= the
checks value (in my testing), but are there guarantees that it will find
that many points (if they exist) ?

The search is an approximate search and the level of approximation is controlled by the checks parameter. Using a larger value will explore more of the tree(s) and return all the neighbors found in the explored region(s). The number of returns is <= the checks value since it only looks at as many leafs (points) as the checks value. It is possible for a neighbor to be outside the explored region of the tree in which case it will not be returned, however in practice this does not happen often. So the answer is no, there are no guarantees that it will  find that many points if they exists.

 



On another note, in kdtree_ann.hpp the number of nearest neighbors is
set by:
int neighbors_in_radius = ann_kd_tree_->annkFRSearch (&tmp[0], radius,
0, NULL, NULL, epsilon_);
neighbors_in_radius  = std::min(neighbors_in_radius, max_nn);

do I interpret this correctly to mean that ann performs 2 radius
searches (the first one to just find out how big to make the
indices,dist vectors)?


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: flann, ann radiusSearch max responses parameter

Radu B. Rusu
Administrator

On 10/13/2010 12:21 PM, Marius Muja wrote:

>
>
> On Wed, Oct 13, 2010 at 11:11 AM, garratt <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hi Marius, et. al.:
>
>     when I run radiusSearch on a flann tree, it only returns 200 points,
>     when I should be getting more.
>
>     I tracked the problem into kdtree_flann.hpp, where
>     KdTreeFLANN<PointT>::radiusSearch
>     uses the value set in flann_param_.checks rather than max_nn.
>
>     flann_param_.checks has been set to 200 in initParameters()
>     to 200.
>
>     I can change the code to set the flann_param_.checks value, (I'll copy
>     the flann_param struct to maintain an illusion of thread safety, and I'm
>     thinking the default value should be the size of the point cloud,
>     instead of INT_MAX)
>
>
>     specifically to Marius:
>     flann_param_.checks has this description:
>     /* how many leafs (features) to check in one search */
>
>     the flann manual says it is: denoting the number of times the
>     tree(s) in the index should be recursively traversed
>
>     setting the checks parameter limits the number of returns to be <= the
>     checks value (in my testing), but are there guarantees that it will find
>     that many points (if they exist) ?
>
>
> The search is an approximate search and the level of approximation is
> controlled by the checks parameter. Using a larger value will explore
> more of the tree(s) and return all the neighbors found in the explored
> region(s). The number of returns is <= the checks value since it only
> looks at as many leafs (points) as the checks value. It is possible for
> a neighbor to be outside the explored region of the tree in which case
> it will not be returned, however in practice this does not happen often.
> So the answer is no, there are no guarantees that it will  find that
> many points if they exists.

Hmm, so how do we fix this? It seems that just modifying KdTreeFLANN<PointT>::radiusSearch won't do? It would be nice if
FLANN has the same behavior as ANN.

In fact, I would be happy to throw ANN if we could make FLANN work as fast as ANN for 3D (x,y,z) search. Marius, we
talked about it a few months ago, but I don't remember exactly what the conclusion was. Is this a good time to
re-iterate that? Maintaining both FLANN and ANN is a pain, as it's hard to recommend one or the other to the user. :)



>     On another note, in kdtree_ann.hpp the number of nearest neighbors is
>     set by:
>     int neighbors_in_radius = ann_kd_tree_->annkFRSearch (&tmp[0], radius,
>     0, NULL, NULL, epsilon_);
>     neighbors_in_radius  = std::min(neighbors_in_radius, max_nn);
>
>     do I interpret this correctly to mean that ann performs 2 radius
>     searches (the first one to just find out how big to make the
>     indices,dist vectors)?

No, that is fine. The ANN manual says:

"In order to produce a true fixed-radius search, first set k = 0 and run the procedure in order to obtain the number k of
points that lie within the radius bound. Then, allocate index and distance arrays of size k each, and repeat the
fixed-radius search by setting k = k and passing in these two arrays."

The other explanations are here:

"Fixed-radius k-Nearest Neighbor Search: This member function is a modification of the above procedure [they refer to the
regular k-nearest neighbor search], which searches for up to k nearest neighbors, but confines the search to a fixed
radius bound. It is given a query point q, a (squared) radius bound sqRad, a nonnegative integer k. Optionally, it is
given an array of point indices, nn idx, an array of distances, dists. If provided, both arrays are assumed to contain
at least k elements. This procedure performs two different types of search.

First, if k is positive and the two arrays nn idx and dists are provided, then among the points whose squared distance
from q is at most sqRad, it finds the k closest of these to q. If the number of points within the squared radius bound is
some value k < k, then only the first k entries of these arrays have meaningful entries. The other entries of nn idx
contain the special value ANN NULL IDX and the other entries of dists contain the special value ANN DIST INF (which are
defined in ANN.h).

This is called a fixed-radius search, because it ignores all the points that lie outside of the radius bound. It is not
however, a true fixed-radius search, because it computes only the closest k points that lie within the radius bound.
Thus, if the value of k is less than the total number of points k in the radius bound, the farthest k − k points within
the radius will not be reported.
"

Cheers,
Radu.

_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: flann, ann radiusSearch max responses parameter

Marius Muja-2


On Wed, Oct 13, 2010 at 12:47 PM, Radu Bogdan Rusu <[hidden email]> wrote:

On 10/13/2010 12:21 PM, Marius Muja wrote:


On Wed, Oct 13, 2010 at 11:11 AM, garratt <[hidden email]
<mailto:[hidden email]>> wrote:

   Hi Marius, et. al.:

   when I run radiusSearch on a flann tree, it only returns 200 points,
   when I should be getting more.

   I tracked the problem into kdtree_flann.hpp, where
   KdTreeFLANN<PointT>::radiusSearch
   uses the value set in flann_param_.checks rather than max_nn.

   flann_param_.checks has been set to 200 in initParameters()
   to 200.

   I can change the code to set the flann_param_.checks value, (I'll copy
   the flann_param struct to maintain an illusion of thread safety, and I'm
   thinking the default value should be the size of the point cloud,
   instead of INT_MAX)


   specifically to Marius:
   flann_param_.checks has this description:
   /* how many leafs (features) to check in one search */

   the flann manual says it is: denoting the number of times the
   tree(s) in the index should be recursively traversed

   setting the checks parameter limits the number of returns to be <= the
   checks value (in my testing), but are there guarantees that it will find
   that many points (if they exist) ?


The search is an approximate search and the level of approximation is
controlled by the checks parameter. Using a larger value will explore
more of the tree(s) and return all the neighbors found in the explored
region(s). The number of returns is <= the checks value since it only
looks at as many leafs (points) as the checks value. It is possible for
a neighbor to be outside the explored region of the tree in which case
it will not be returned, however in practice this does not happen often.
So the answer is no, there are no guarantees that it will  find that
many points if they exists.

Hmm, so how do we fix this? It seems that just modifying KdTreeFLANN<PointT>::radiusSearch won't do? It would be nice if FLANN has the same behavior as ANN.

In fact, I would be happy to throw ANN if we could make FLANN work as fast as ANN for 3D (x,y,z) search. Marius, we talked about it a few months ago, but I don't remember exactly what the conclusion was. Is this a good time to re-iterate that? Maintaining both FLANN and ANN is a pain, as it's hard to recommend one or the other to the user. :)


Yes, I'd definitely like to look at improving performance for low dimensionality search. When I started implementing FLANN my use case was very fast matching of high dimensional features (SIFT features for example) and the implementation was done with that in mind. I'll do some profiling for the 3D case and see where the bottleneck is and probably implement a specialized index that is used when dimensionality if low.
 



   On another note, in kdtree_ann.hpp the number of nearest neighbors is
   set by:
   int neighbors_in_radius = ann_kd_tree_->annkFRSearch (&tmp[0], radius,
   0, NULL, NULL, epsilon_);
   neighbors_in_radius  = std::min(neighbors_in_radius, max_nn);

   do I interpret this correctly to mean that ann performs 2 radius
   searches (the first one to just find out how big to make the
   indices,dist vectors)?

No, that is fine. The ANN manual says:

"In order to produce a true fixed-radius search, first set k = 0 and run the procedure in order to obtain the number k of points that lie within the radius bound. Then, allocate index and distance arrays of size k each, and repeat the fixed-radius search by setting k = k and passing in these two arrays."

The other explanations are here:

"Fixed-radius k-Nearest Neighbor Search: This member function is a modification of the above procedure [they refer to the regular k-nearest neighbor search], which searches for up to k nearest neighbors, but confines the search to a fixed radius bound. It is given a query point q, a (squared) radius bound sqRad, a nonnegative integer k. Optionally, it is given an array of point indices, nn idx, an array of distances, dists. If provided, both arrays are assumed to contain at least k elements. This procedure performs two different types of search.

First, if k is positive and the two arrays nn idx and dists are provided, then among the points whose squared distance from q is at most sqRad, it finds the k closest of these to q. If the number of points within the squared radius bound is some value k < k, then only the first k entries of these arrays have meaningful entries. The other entries of nn idx contain the special value ANN NULL IDX and the other entries of dists contain the special value ANN DIST INF (which are defined in ANN.h).

This is called a fixed-radius search, because it ignores all the points that lie outside of the radius bound. It is not however, a true fixed-radius search, because it computes only the closest k points that lie within the radius bound. Thus, if the value of k is less than the total number of points k in the radius bound, the farthest k − k points within the radius will not be reported.
"

Cheers,
Radu.



_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: flann, ann radiusSearch max responses parameter

garratt
In reply to this post by Radu B. Rusu
On Wed, 2010-10-13 at 12:47 -0700, Radu Bogdan Rusu wrote:

> Hmm, so how do we fix this? It seems that just modifying
> KdTreeFLANN<PointT>::radiusSearch won't do? It would be nice if
> FLANN has the same behavior as ANN.
>
> In fact, I would be happy to throw ANN if we could make FLANN work as
> fast as ANN for 3D (x,y,z) search. Marius, we
> talked about it a few months ago, but I don't remember exactly what
> the conclusion was. Is this a good time to
> re-iterate that? Maintaining both FLANN and ANN is a pain, as it's
> hard to recommend one or the other to the user. :)

Wait, isn't the point of FLANN that it is faster than ANN, but less
accurate (it is in my tests)?  If ANN is faster than FLANN, why do we
use FLANN at all?

I think that it would be OK if the behavior for ANN and FLANN are
different - specifically, I would imagine that FLANN would have a
parameter you would pass it to dictate where it should operate in the
fast/accurate scale.

cheers
Garratt




_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: flann, ann radiusSearch max responses parameter

Radu B. Rusu
Administrator

On 10/13/2010 01:52 PM, garratt wrote:

> On Wed, 2010-10-13 at 12:47 -0700, Radu Bogdan Rusu wrote:
>> Hmm, so how do we fix this? It seems that just modifying
>> KdTreeFLANN<PointT>::radiusSearch won't do? It would be nice if
>> FLANN has the same behavior as ANN.
>>
>> In fact, I would be happy to throw ANN if we could make FLANN work as
>> fast as ANN for 3D (x,y,z) search. Marius, we
>> talked about it a few months ago, but I don't remember exactly what
>> the conclusion was. Is this a good time to
>> re-iterate that? Maintaining both FLANN and ANN is a pain, as it's
>> hard to recommend one or the other to the user. :)
>
> Wait, isn't the point of FLANN that it is faster than ANN, but less
> accurate (it is in my tests)?  If ANN is faster than FLANN, why do we
> use FLANN at all?

Well, as Marius replied, unfortunately it's not so simple. FLANN was optimized for fast queries in high-dimensional
trees. ANN works very well for low dimensions (e.g., 3D), and tends to be slower for higher dimensions.


Cheers,
Radu.
_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: flann, ann radiusSearch max responses parameter

garratt
In reply to this post by garratt
> I can change the code to set the flann_param_.checks value, (I'll copy
> the flann_param struct to maintain an illusion of thread safety, and I'm
> thinking the default value should be the size of the point cloud,
> instead of INT_MAX)
>
done.  Now the default value passed in is -1, which causes the max_nn to
be set to the point cloud size, or the size of _indices, if it is not
NULL.

Garratt

_______________________________________________
[hidden email] / http://pcl.ros.org
https://code.ros.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: flann, ann radiusSearch max responses parameter

Radu B. Rusu
Administrator
I forgot to ask. Garratt, can you and/or Marius please add this change to the Changelist? Thanks.

Cheers,
Radu.


On 10/13/2010 02:08 PM, garratt wrote:

>> I can change the code to set the flann_param_.checks value, (I'll copy
>> the flann_param struct to maintain an illusion of thread safety, and I'm
>> thinking the default value should be the size of the point cloud,
>> instead of INT_MAX)
>>
> done.  Now the default value passed in is -1, which causes the max_nn to
> be set to the point cloud size, or the size of _indices, if it is not
> NULL.
>
> 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