Fast Implementation of Volumetric Occupancy Grids

Mapping vehicle surroundings using an occupancy grid is commonly a performance bottleneck in many automotive applications. In particular, three dimensional map generation becomes extremely complex because of the additional degree of freedom that significantly increases the amount of occupancy grid cells to be examined. In this work, we present a novel way to speed up generation of volumetric occupancy grids, by approximating heavy calculations and utilizing efficient data structures. Our proposed method produces a 15-fold speedup in a high-resolution mode and demonstrates real-time performance, without discernible impact on the accuracy. A description of the algorithm and the data structures is provided. The algorithm is tested on a multi-sensor system in a challenging environment. Moreover, our design is portable and could suit many platforms, including embedded automotive hardware.