Hi Martin, On Wed, Dec 14, 2011 at 9:40 PM, martin f krafft <madd...@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/ ___________________________________________________________ -- To UNSUBSCRIBE, email to debian-wnpp-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/CAAZP6fnpeLrRcLjf=rbwwfhpumpzhpvxhvt+n0hsbx6w42d...@mail.gmail.com
