This paper concerns the creation of efficient surface representations from laser point clouds created by a push broom laser system. We produce a continuous, implicit, non-parametric and non-stationary representation with an update time that is constant. This allows us to form predictions of the underlying workspace surfaces at arbitrary locations and densities. The algorithm places no restriction on the complexity of the surfaces and automatically prunes redundant data via an information theoretic criterion. This criterion makes the use of Gaussian Process Regression a natural choice. We adopt a formulation which handles the typical non-functional relation between XY location and elevation allowing us to map arbitrary environments. Results are presented that use real and synthetic data to analyse the trade-off between compression rate and reconstruction error. We attain decimation factors in excess of two orders of magnitude without significant degradation in fidelity.
Ansley C. and Kohn R. ( 1985) Estimation, filtering, and smoothing in state space models with incompletely specified initial conditions. The Annals of Statistics13: 1286-1316.
2.
Bares J., Hebert M., Kanade T., Krotkov E., Mitchell T., Simmons R., et al. (1989) Ambler: An autonomous rover for planetary exploration. IEEE Computer22: 18-26.
3.
Csató L. and Opper M. ( 2002) Sparse on-line Gaussian processes. Neural Computation14: 641-668.
4.
Deisenroth M., Rasmussen C. and Peters J.(2009) Gaussian process dynamic programming. Neurocomputing72: 1508-1524.
5.
Dongara J., Moler C., Bunch J. and Stewart G. ( 1979) LINPACK users’ Guide. Philadelphia , PA: SIAM.
6.
Früh C. and Zakhor A. ( 2003) Constructing 3D city models by merging aerial and ground views. IEEE Computer Graphics Applications23: 52-61.
7.
Hadsell R., Bagnell J., Huber D and Hebert M (2010) Non-stationary space-carving kernels for accurate rough terrain estimation. The International Journal for Robotics Research29: 981-996.
8.
Hähnel D., Burgard W. and Thrun S. ( 2003) Learning compact 3D models of indoor and outdoor environment with a mobile robot. Robotics and Autonomous Systems44: 15-27.
9.
Hoppe H., DeRose T., Duchamp T., McDonald J. and Stuetzle W. ( 1993) Mesh optimization. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques . New York: ACM Press , pp. 19-26.
10.
Krause A., Singh A. and Guestrin C. ( 2008) Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. The Journal of Machine Learning Research9: 235-284.
11.
Lang T., Plagemann C. and Burgard W. ( 2007) Adaptive non-stationary kernel regression for terrain modeling. In Robotics: Science and Systems (RSS).
12.
MacKay D. ( 2003) Information Theory, Inference, and Learning Algorithms . Cambridge: Cambridge University Press.
13.
Martin MC and Moravec H. ( 1996) Robot Evidence Grids. Technical Report CMU-RI-TR-96-06 , Robotics Institute, Carnegie Mellon University.
14.
Matheron G. ( 1973) The intrinsic random functions and their applications . Advances in Applied Probability5: 439-468.
15.
Newman P., Sibley G., Smith M., Cummins M., Harrison A., Mei C., et al. (2009) Navigating, recognising and describing urban spaces with vision and laser. The International Journal of Robotics Research28: 1406-1433.
16.
Nguyen-Tuong D. and Peters J. ( 2010) Using model knowledge for learning inverse dynamics . In IEEE International Conference on Robotics and Automation .
17.
O’Hagan A. ( 1987) Monte Carlo is fundamentally unsound. The Statistician36: 247-249.
18.
O’Hagan A. ( 1991) Bayes-Hermite quadrature. Journal of Statistical Planning and Inference29: 245-260.
19.
O’Hagan A. and Kingman J. ( 1978) Curve fitting and optimal design for prediction . Journal of the Royal Statistical Society. Series B (Methodological)40: 1-42.
20.
Osborne M. ( 2010) Bayesian Gaussian Processes for Sequential Prediction, Optimisation and Quadrature. PhD thesis, University of Oxford.
21.
Osborne M., Roberts S., Rogers A., Ramchurn S. and Jennings N. ( 2008) Towards real-time information processing of sensor network data using computationally efficient multi-output Gaussian processes . In Proceedings of the 7th International Conference on Information Processing in Sensor Networks. Washington, DC: IEEE Computer Society, pp. 109-120.
22.
Pfaff P. and Burgard W. ( 2005) An efficient extension of elevation maps for outdoor terrain mapping. In International Conference on Field and Service Robotics (FSR).
23.
Plagemann C., Kersting K., Pfaff P. and Burgard W. ( 2007) Gaussian beam processes: a nonparametric Bayesian measurement model for range finders. In Robotics: Science and Systems (RSS).
24.
Plagemann C., Mischke S., Prentice S., Kersting K., Roy N. and Burgard W. ( 2008) Learning predictive terrain models for legged robot locomotion . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
25.
Quiñonero-Candela J. and Rasmussen C. ( 2005) A unifying view of sparse approximate Gaussian process regression. Journal of Machine Learning Research6: 1939-1959.
26.
Rasmussen C. and Ghahramani Z. ( 2003) Bayesian Monte Carlo. In Advances in Neural Information Processing Systems, pp. 505-512.
27.
Rasmussen CE and Williams CKI ( 2006) Gaussian Processes for Machine Learning. Cambridge, MA: The MIT Press.
28.
Rusinkiewicz S. and Levoy M. ( 2001) Efficient variants of the ICP algorithm. In Proceedings of 3DIM, pp. 145-152.
29.
Scholkopf B. and Smola A. ( 2002) Learning with Kernels. Cambridge, MA : The MIT Press. http://www.learning-with-kernels.org/ .
30.
Seeger M. ( 2008) Low Rank Updates for the Cholesky Decomposition. Technical Report, University of California at Berkeley .
31.
Seeger M., Williams C. and Lawrence N. ( 2003) Fast forward selection to speed up sparse Gaussian process regression. In Workshop on AI and Statistics , volume 9.
32.
Smith M., Baldwin I., Churchill W., Paul R and Newman P (2009) The new college vision and laser data set. The International Journal of Robotics Research28: 595-599.
33.
Smith M., Posner I. and Newman P. ( 2010a). Efficient nonparametric surface representations using active sampling for push broom laser data. In Proceedings of Robotics: Science and Systems, Zaragoza, Spain.
34.
Smith M., Posner I. and Newman P. ( 2010b) Generating implicit surfaces from lidar data. In Towards Autonomous Robotic Systems, Plymouth, UK.
35.
Stein ML ( 1999) Interpolating Spatial Data. Berlin : Springer-Verlag.
36.
Triebel R., Burgard W. and Dellaert F. ( 2005) Using hierarchical EM to extract planes from 3D range scans. In International Conference on Robotics and Automation (ICRA).
37.
Triebel R., Pfaff P. and Burgard W. ( 2006) Multi-level surface maps for outdoor terrain mapping and loop closing. In International Conference on Intelligent Robots and Systems (IROS).
38.
Vasudevan S., Ramos F., Nettleton E., Durrant-Whyte H. and Blair A. ( 2009) Gaussian process modeling of large scale terrain . In International Conference on Robotics and Automation (ICRA).
