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

People

• Jean-Francois Lalonde
• Nicolas Vandapel
• Martial Hebert

Description

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:

• Data density: The data structure adapts to the varying density of the 3-D point cloud by using a different representation depending on the local data density., from sparse hashing to dense voxels.
• Data distribution:  The order in which the point cloud is scanned depends on the data distribution in order to maximize the re-use of  computation between points.

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:

References

Jean-Francois Lalonde, Nicolas 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 Lalonde, Nicolas Vandapel, Martial Hebert, Data Structure for Efficient Processing in 3-D.   In Proceedings Robotics: Science and Systems 1 Conf., (RSS) , 2005.

Funding

This research is supported by:

• ARL, Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-
  01-209912.

Copyright notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.