Efficient Data Structures for On-Line Processing of 3-D Point Clouds



Example of a raw 3-D point cloud from a typical sensor.  This dataset is made of 259,528 points. With current mobility sensors,  this volume  of datamust be stored and processed in real-time. The dynamic and sparse nature of data motivated the development of new data structures.
Mobility sensors (such as 3-D scanning ladars) can measure hundreds of thousands of 3-D points per second, with range resolution on the order of one centimeter.  As the input data rate increases, it is critical to design data structures that can efficiently store large amounts of data and quickly perform basic operations such as insertion, memory access, and range search. In addition, it is desirable to use a data structure which can adapt to the distribution of the data and to the type of computaiton applied to the data. Traditional algorithms and data structures designed for batch processing are inadequate in that particular setting because they cannot handle dynamic data efficiently.

Assuming a computation model in which 1) the output is computed a t each point by using data in its neighborhood and 2) intermediate computation results at one point can be reused at a neighboring point, the data structure developed in this project addresses these challenges in two ways:

The optimal scanning pattern depends on the underlying distribution of the point cloud.

The data structure is used for real-time operation on an unmanned ground vehicle for mobility in unstructured environments.  It was evaluated on a classification task using algorithms developed in a related project. The task is to segment the point cloud into three classes (load bearing surface, vegetation, and linear structures).  This was tested in a variety of environments to assess the performance of the approach under different distribution of the data:
Two typical environments (meadow and light forest) Point cloud classification (red = load bearing surface; green = vegetation; blue = linear structures)

The proposed data structure is shown to more effectient than the alternatives. In particular, it retains the same level of performance across the different types of data distribution. Also, owing to the dynamically optimized re-use of computation,  the computation time remains roughly constant as the radius of the computation neighborhood increases:


Jean-Francois LalondeNicolas Vandapel, Martial Hebert, Data Structures for Efficient Dynamic Processing in 3-D International Journal of Robotics Research.   Vol. 26, No. 8, August, 2007, pp. 777-796. 

Jean-Francois Lalonde,  Data Structure for Efficient Dynamic Processing in 3-D.  

Master's thesis, CMU-RI-TR-06-22, Robotics Institute, Carnegie Mellon University, May, 2006.

Jean-Francois LalondeNicolas Vandapel, Martial Hebert, Data Structure for Efficient Processing in 3-D  In Proceedings Robotics: Science and Systems 1 Conf., (RSS) , 2005.


This research is supported by:

Copyright notice