The LidarK library provides an open-source framework for processing multidimensional point data such as 3D LIDAR scans. It allows building a spatial index for performing fast search queries of different kinds. Although it is intended to be used for LIDAR scans, it can be helpful for a wide range of problems that require spatial data processing.Download LidarK 2.0, or browse for the previous versions and data samples.
The core of the library is a spatial index framework. While having an unstructured set of points in a 3D space (point cloud), it is very hard to perform operations like k nearest neighbors search, or finding all points within a box or some other shape. To eliminate the problem complexity some index structure can be created for a point cloud. The well-known approach to the space partitioning problem is building octree or kd-tree. They are probably good for ray-tracers, but usually show poor results on real-world data, such as outdoor scene scans, which consist of surfaces instead of uniformly distributed points.
The problem was addressed by Tamy Boubekeur et al. . They used VS-Tree (Volume-Surface Tree) to approximate surface-like clouds. VS-Tree is a combination of an octree and quadtrees that approximate surface elements in the octree leaves. However, VS-Tree performs poorly when the surface of a scanned object is not enough smooth. In this case the structure degenerates to an octree. VS-Tree was primarily intended for the visualization sake while we belive that our data structure is more flexible.
We called the data structure we designed Seg-Tree. Seg-Tree is a modification of the R-Tree data structure by Antonin Guttman , which is just an hierarchy of enclosed bounding boxes. A leave of the tree contains a set of tuples. Every node of the tree contains a set of children nodes, which can have the cardinality in the pre-defined range. Seg-Tree is more usable than R-Tree for dynamic indexing real-world data, such as LIDAR scans. It produces tighter leaves, and it is especially good for 'stripped' clouds where classic R-Tree is likely to produce leaves of weird shape.
The distinguishing features of Seg-Tree include:
The leaves of the tree are highlighted. Each color corresponds to one leaf, which contains "a patch" of the object surface.
The advantages of our approach are:
The main disadvantage of Seg-Tree is slow performance of building index. Theoretically, it equals O(n*log(n)) where log(n) grows slowly, because the tree is usually very ramificated in practice. It is relatively slow on small clouds.
The k nearest neighbors (kNN) retrieval is implemented according to the original PruneDescent algorithm, which is an implementation of the branch-and-bound scheme and works extremely fast with the data structure. It also descends from the root to leaves seeding faraway nodes out on every step. The key idea of this kind of kNN retrieval schemes is described by Sankaranarayanan et al. .
The code provides a set of classes which allows building Seg-Tree, get nodes, get children of the node, get k nearest neighbors of a point etc. Also we implemented a MATLAB wrapper for the library and some unit tests that show how to work with C++ and MATLAB library versions. The library was developed on Microsoft Windows XP + Microsoft Visual Studio 2005 but it was also tested on Ubuntu 9.10 Karmic Koala + gcc-4.4.4. The MATLAB interface was tested on MATLAB R2007b.
The framework provides the following features:
There are some examples explaining how to use this API.
Please, mail all comments, suggestions, problems and contributions to Alexander Velizhev (email@example.com) and Roman Shapovalov (firstname.lastname@example.org). We appreciate your assistance!
GML LidarK Library v. 2.0 September 10, 2010 Download
GML LidarK Library v. 1.2 December 5, 2008 Download
GML LidarK Library v. 1.1 September 9,2008 Download
GML LidarK Library v. 1.0 July 1, 2008 Download
Sample data files (in the compressed library format):
The Stanford 3D Scanning Repository
International Society for Photogrammetry and Remote Sensing,
Working Group V/3 Terrestrial Laser Scanning