Data Structures for Efficient Dynamic Processing in 3-D


Dynamic 3-D data is being accumulated by a ladar sensor mounted on an outdoor mobile robot. We introduce a novel data structure which enables efficient processing of such data.

People

Abstract

We consider the problem of the dynamic processing of large amounts of sparse three-dimensional data. It is assumed that computations are performed in a neighborhood defined around each point in order to retrieve local properties. This general kind of processing can be applied to a wide variety of problems. We propose a new, efficient data structure and corresponding algorithms that significantly improve the speed of the range search operation and that are suitable for on-line operation where data is accumulated dynamically. The method relies on taking advantage of overlapping neighborhoods and the reuse of previously computed data as the algorithm scans each data point. To demonstrate the dynamic capabilities of the data structure, we use data obtained from a laser radar mounted on a ground mobile robot operating in complex, outdoor environments. We show that this approach considerably improves the speed of an established 3-D perception processing algorithm.

International Journal of Robotics Research

Jean-François Lalonde, Nicolas Vandapel, and Martial Hebert. Data Structures for Efficient Dynamic Processing in 3-D. International Journal of Robotics Research, 26(8), 777--796, 2007. [PDF], [BibTeX]

M.S. Thesis, 2006

This work was the focus of my M.S. thesis.

Citation

Jean-François Lalonde. Data Structures for Efficient Dynamic Processing in 3-D. Technical Report CMU-RI-TR-06-22, Robotics Institute, Carnegie Mellon University, May 2006. [PDF], [BibTeX]

Talk

Download the slides from the talk presented at my M.S. talk in the following formats:

[MS Powerpoint, 13.6MB], original version.
[PDF, 8MB], export from Powerpoint.

Robotics: Science and Systems, 2005

Parts of this work previously appeared at Robotics: Science and Systems in 2005.

Citation

Jean-François Lalonde, Nicolas Vandapel, and Martial Hebert. Data Structure for Efficient Processing in 3-D. Robotics: Science and Systems I, 2005. [PDF], [BibTeX]

Talk

Download the slides from the talk presented at RSS'05 in the following formats:

[MS Powerpoint, 3.1MB], original version.
[PDF, 1.9MB], export from Powerpoint.

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. These works may not be reposted without the explicit permission of the copyright holder, except when identified by Creative Commons License 2.0, in which case the license applies to both the original and modified versions of the images.