Bug#652103: ITP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees
Hi Martin,
On Wed, Dec 14, 2011 at 9:40 PM, martin f krafft <madduck@debian.org> wrote:
>> nanoflann is a C++ header-only library for building KD-Trees,
>> mostly optimized for 2D or 3D point clouds.
>
> I won't ask what "clouds" are,
I want to answer that anyway... In the scope of mobile robotics and
computer vision, "point clouds" is a widely used term for "sets of 2D
or 3D points". In fact, one of the most used libraries for related
stuff is named "Point Cloud Library" (PCL) [1], and is maintained by
Willow Garage, a leader company in robotics R&D [2].
All this info is relevant, because one of my initial motivations for
creating nanoflann and for packaging now, was to work in PCL to
replace its usage of flann with this new nanoflann (which, for now, is
~2 times faster for typical operations in mobile robotics).
> but please tell us about how the
> 2D/3D optimisation happens.
Well, in comparison to the original flann, this new lib exploits
templatized code and inlining as much as possible (as I see
libkdtree++ also does). By templatizing the dimensionality of data
points, the generated code typically contains SSE* instructions
instead of loops.
Another important advantage of nanoflann, which I think can't be found
in other libs (note: haven't explored in deep libkdtree++ yet...) is
the usage of data source adaptor classes to avoid allocating memory
for copying of the original data sets: only indices are kept at each
kd-tree node.
>> This implementation is roughly one order of magnitude faster than
>> some other popular KD-tree libraries.
>
> What are other popular KD-tree libraries? And does this apply to
> 2D/3D only?
I personally carried out detailed comparisons vs. flann, with results
shown in [3]. I also compared this new lib to ANN [4] and was about
~50% faster, but didn't make any detailed records or graphs so that
figure is just based on what I recall.
Not personally, I received recently a report of a user which also said
nanoflann was "about one order of magnitude faster than kdtree++" (I
guess that's libkdtree++). I know he works with datasets in the order
of 2^32 data points but I don't know their dimensionality. Perhaps
most of the gain comes from the source data adaptor class, but I'm
just guessing here.
> How does nanoflann compare to libkdtree++? Why would you want to use
> one over the other?
Well, I'm pretty sure it depends on the application, but as said
above, at least for some applications it seems that this new lib makes
sense.
> Note: I am the author of libkdtree++, and I think choice is good.
> However, I simply don't believe some of the claims made in the long
> description, and I question the usefulness of 2D/3D optimisation wrt
> KD-Trees: if you are dealing with only two or three dimensions,
> KD-Trees are usually not what you want. Then again, that was just my
> experience, my KD-Trees usually had dimensions in the low thousands…
Sure, kd-trees are useful for high dimensionality, I've also used them
for that sometimes.
But believe me: there're algorithms in mobile robotics where you have
to look for the nearest points in a set of 2D/3D points (i.e. from
the Microsoft's Kinect sensor) and, in our community, every
implementation which is worth must rely on KD-trees (or similar ideas)
to achieve a reasonable performance.
To get a feeling of what is all this stuff used for, you can see for
example this video [5] (just a quick random search on YouTube, I have
no connection with them!)
Best,
JL
[1] http://pointclouds.org
[2] http://www.willowgarage.com/
[3] http://code.google.com/p/nanoflann/
[4] http://www.cs.umd.edu/~mount/ANN/
[5] http://www.youtube.com/watch?v=pCxbfvEpcXs
--
___________________________________________________________
Dr. Jose-Luis Blanco-Claraco
Dpt. Ing. Civil, Mat. y Fabric - Phone: +34 951 952435
E.T.S.I. Industriales - Despacho 2.037
Universidad de Malaga - Campus Universitario de Teatinos
29071 Malaga, Spain
https://sites.google.com/site/jlblancosite/
___________________________________________________________
Reply to: