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

## People

## 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. |

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.