IEEE Transaction on Robotics (T-RO) 2019

Super Rays and Culling Region for Real-Time Updates on Grid-based Occupancy Maps

Super Rays and Culling Region for Real-Time Updates on Grid-based Occupancy Maps

by Youngsun Kwon, Donghyuk Kim, Inkyu An, and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)




Abstract

In this paper, we present two novel approaches, Super Rays and Culling Region, for efficiently updating gridbased occupancy maps with point clouds. Rays, which traverse from the sensor origin to the sensor data, update the occupancy probabilities of a map representing an environment. Based on the ray model, we define a super ray as a representative ray to multiple rays having the same traversal patterns during the map updates. Our super rays utilize the geometric information of rays and reduce the number of points used for updating the map. For constructing super rays efficiently, we propose mapping lines for handling 2D and 3D cases from an observation that edges or grid points branch out the traversal patterns on the map. Furthermore, we introduce a culling region using the occupancy states of the updated map for reducing redundant computations occurred in updates. The super rays perform the update process in a single traversal, and the culling region reduces the number of unnecessary traversals for updating the map. As a result, our combined method improves the update performance without compromising any representation accuracy of a grid-based map.
We test the update performance of the proposed method using public indoor and outdoor datasets. Our combined approach shows up to 11.8 times and 2.8 times performance improvement over the state-of-the-art update methods of grid-based maps in the indoor and outdoor scenes, respectively. Also, we compare the update speed and the representation accuracy of our method using KITTI dataset over the state-of-the-art learning based occupancy maps. In a navigation scenario that raw point clouds are acquired in 10 Hz, our method shows the best performance on the update speed and thus the highest representation accuracy within a given time.



This figure represents an overview of our super ray when we have the new measurements as shown in (a). (b) and (c) represent occupancy probabilities of cells after updating the 2D grid map with different methods. The green and red cells have free and occupied states, respectively. The bold numbers with * notation in cells indicate that those cells are classified into fully occupied or fully free state. In (b), the state-of-the-art method updates the same set of cells for three different rays. The blue ray in (c) is a super ray computed out of those three rays in (b). The super ray updates the map with a single traversal on the cells.

This figure shows an overview of our culling region, given the new measurements as shown in (a). In (b), the prior method causes redundant computation on traversals on the cells having fully-free states. The blue box in (c) is a culling region that prevents the three rays to traverse the fully-free cells for updates. In this figure, we use the same setting with the above figure.

These figures visualize the points that each map classifies the test points to be occupied in our navigation scenario. We do not visualize the free points in this figure to avoid cluttered visualization, but consider them to compute the representation accuracy. The color represents the relative height of points, and the number in parenthesis is the representation accuracy and the update speed of a map. Our method shows the fastest update performance resulting in the highest representation accuracy.

Contents

Paper: PDF (4.3MB)
Source Code: GitHub page


Related links

Super Ray-based Updates for Occupancy Maps

Bibtex: 
@article{kwon2019super,
	title={Super rays and culling region for real-time updates on grid-based occupancy maps},
	author={Kwon, Youngsun and Kim, Donghyuk and An, Inkyu and Yoon, Sung-eui},
	journal={IEEE Transactions on Robotics},
	volume={35},
	number={2},
	pages={482--497},
	year={2019},
	publisher={IEEE}
}