Languages
GML LidarK Library
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.
Spatial index
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. [2006]. 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.
Library Overview
Seg-Tree
We called the data structure we designed Seg-Tree. Seg-Tree is a modification of the R-Tree data structure by Antonin Guttman [1984], 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:
- we use the well-known k-means clustering algorithm for node splitting, as it was introduced in cR-Tree [Brakatsoulas et al., 2002]
- the original k-pseudocentroids algorithm is used for inserting tuples into the tree. It picks a leaf to insert the tuple by traversing the nodes from the tree root to the leaf itself. On every step it retains a small amount of nodes of the current tree level in which the best fitted leaf could be found. Finally, it selects the best leaf from the short list.
The leaves of the tree are highlighted. Each color corresponds to one leaf, which contains "a patch" of the object surface.
Comparison to the related data structures
The advantages of our approach are:
- Seg-Tree does not "rip" surface elements like octree. Seg-Tree attempts to include a single continuous surface element to each leaf
- Seg-Tree produces more efficient space partition than octree
- Seg-Tree can effectively handle 'stripped clouds' while R-Tree cannot
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.
kNN retrieval
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. [2007].
Implementation details
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.
Library API
The framework provides the following features:
- create tuple that contains point and to create his/her own tuple implementation that contains any meta-data as well
- create Seg-Tree by a tuple collection or a single seminal tuple. Empty tree is not allowed
- add tuples to the created tree
- check if a tree node is a leaf and then get either children tuples or children nodes
- get information about node bounds
- find k nearest neighbours of a point
- find all tuples in the given radius
- find all the tuples/leafnodes intersecting the given figure
- save the created tree to disk and load it from disk
There are some examples explaining how to use this API.
License agreement
The library is free of charge for academic use. The detailed license terms could be found within the archive.Project team
Principal researchers:
Developers/researchers:
- Roman Shapovalov
- Dmitry Potapov
- Elena Tretyak
Please, mail all comments, suggestions, problems and contributions to Alexander Velizhev (avelizhev@graphics.cs.msu.su) and Roman Shapovalov (shapovalov@graphics.cs.msu.su). We appreciate your assistance!
Downloads
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):
