Efficient Map Representations for Multi-Dimensional Normal Distributions Transforms

Cornelia Schulz, Richard Hanten

Efficient map repesentations are crucial for many mobile robotic applications. There are already different map representations available which differ in applicability and accuracy. This includes occupancy grid map structures, feature maps, and Normal Distributions Transform (NDT) maps.

While there is a lot of research on maps for 2D space and this task can be considered extensively elaborated, there are only few approaches for accurate and real-time mapping in 3D space, which is of interest for many robotic tasks, such as exploration, localization and path planning, especially for unmanned aerial vehicles (UAVs), mobile manipulators and also outdoor robots.

Our research focus lies on combining NDT with occupancy grid maps. NDT maps also discretize the environmental space into a grid, but the sensor readings inside each grid cell are represented as normal distributions, hence the name. Originally, this was proposed for 2D space, whereby the authors use four overlapping grid cells to overcome the discretization error resulting from space segmentation. While other NDT implementations, especially for the 3D case, omit overlapping grids because of runtime efficiency, our implementation still uses these four and eight overlapping grids for 2D and 3D space, respectively:

If using only one grid, the maps become inconsistent and suffer from discontinuities in between the distributions. Using four overlapping grids reduces this effect drastically:

Although our implementations use overlapping grids, the approach outperforms its direct competitor regarding accuracy and memory consumption, while being comparably fast. Regarding accuracy, it also outperforms OctoMap, the current state-of-the-art in 3D mapping.

The following images show exemplary maps we built to evaluate our implementation against e.g. OctoMap. Details on the mapping approach, implementation and evaluation can be found in our paper [1].

We already successfully used our ONDT maps with a newly developed sensor model for 2D Monte Carlo Localization with laser data on 2D maps and stereo camera data on 3D maps. More information thereabout can be found on the related research page.

Getting the Software

Our mapping software and its dependencies can be found on our GitHub page.
More information can be found on the cslibs_ndt GitHub page.


[1] Cornelia Schulz, Richard Hanten, and Andreas Zell. "Efficient Map Representations for Multi-Dimensional Normal Distributions Transforms". In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2679--2686, Madrid, Spain, October 2018. [ details ]