Data Structures for Efficient Dynamic Processing in 3-D

Jean-Francois Lalonde, Nicolas Vandapel, and Martial Hebert
The International Journal of Robotics Research, Vol. 26, No. 8, August, 2007, pp. 777-796.


Download
  • Adobe portable document format (pdf) (3MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to 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.

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

Notes
Sponsor: Army Research Laboratory
Grant ID: DAAD19-01-209912
Associated Center(s) / Consortia: Vision and Autonomous Systems Center and Field Robotics Center
Associated Project(s): CTA Robotics
Number of pages: 19

Text Reference
Jean-Francois Lalonde, Nicolas Vandapel, and Martial Hebert, "Data Structures for Efficient Dynamic Processing in 3-D," The International Journal of Robotics Research, Vol. 26, No. 8, August, 2007, pp. 777-796.

BibTeX Reference
@article{Lalonde_2007_5806,
   author = "Jean-Francois Lalonde and Nicolas Vandapel and Martial Hebert",
   title = "Data Structures for Efficient Dynamic Processing in 3-D",
   journal = "The International Journal of Robotics Research",
   pages = "777-796",
   publisher = "Sage",
   month = "August",
   year = "2007",
   volume = "26",
   number = "8",
}