Efficient Polyline Surface Mapping with Strong Error Bounds

We propose a novel surface mapping algorithm processing sensor data from, e.g., stereo or structure from motion video, triangulating ultrasonic, lidar, or tactile sensors. The algorithm does not rely on a grid and instead constructs a set of polylines as an extremely efficient representation of surrounding surfaces. We use ridges of a continuous occupancy to extract surfaces from location measurements which are subject to noise. Our algorithm for iterative map updates is efficient, stable, unconditionally convergent, gives strong guarantees about the map accuracy, and is invariant under permutation of the input data. It does not suffer from association errors, and operations such as shape updates, splitting, and merging of surfaces arise naturally and are not handled separately. The algorithm corrects wrongly mapped surfaces with future more accurate measurements, and the polyline approximation of the ridge can be tuned to arbitrary accuracy. Runtime measurements demonstrate the feasibility of the approach for embedded applications.