This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Lalonde, J.-F. Articles by Hebert, M. Search for Related Content Social Bookmarking                         What's this?

Data Structures for Efficient Dynamic Processing in 3-D

Carnegie Mellon University The Robotics Institute - Newell Simon Hall 5000 Forbes Avenue Pittsburgh, 15213, PA, USA, {jlalonde, vandapel, hebert}@ri.cmu.edu

Nicolas Vandapel

Carnegie Mellon University The Robotics Institute - Newell Simon Hall 5000 Forbes Avenue Pittsburgh, 15213, PA, USA, {jlalonde, vandapel, hebert}@ri.cmu.edu

Martial Hebert

Carnegie Mellon University The Robotics Institute - Newell Simon Hall 5000 Forbes Avenue Pittsburgh, 15213, PA, USA, {jlalonde, vandapel, hebert}@ri.cmu.edu

This paper considers 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. A new, efficient data structure and corresponding algorithms are proposed 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, data obtained from a laser radar mounted on a ground mobile robot operating in complex, outdoor environments is used. It is shown that this approach considerably improves the speed of an established 3-D perception processing algorithm.

Key Words: field robots • range sensing • mapping • data structure • terrain classification

The International Journal of Robotics Research, Vol. 26, No. 8, 777-796 (2007)
DOI: 10.1177/0278364907079265


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?