The Manhattan method: a fast Cartesian elevation map reconstruction from range data

A Cartesian elevation map (CEM) is an internal representation of a robot´s environment. The reconstruction method must solve a nonlinear sampling problem without losing too much information. A fast CEM reconstruction algorithm that also recovers the position and the size of obstacles is presented. The algorithm is able to classify each pixel in the CEM as unexplored, occluded (the algorithm computes the maximum possible elevation), traversable, and obstacle. A presentation of a global slope detection algorithm is given. The method is successfully tested on a scene that contains traversable slopes, nontraversable slopes and obstacles