Fast Distance Transforms in Graphs and in Gmaps

Abstract

Distance Transform (DT) as a fundamental operation in pattern recognition computes how far inside a shape a point is located. In this paper, at first, a novel method is proposed to compute the DT in a graph. By using the edge classification and a total order, the spanning forest of the foreground is created where distances are propagated through it. Second, in contrast to common linear DT methods, by exploiting the hierarchical structure of the irregular pyramid, the geodesic DT (GDT) is calculated with parallel logarithmic complexity. Third, we introduce the DT in the nD generalized map (n-Gmap) leading to a more precise and smoother DT. Forth, in the n-Gmap we define n different distances and the relation between these distances. Finally, we sketch how the newly introduced concepts can be used to simulate gas propagation in 2D sections of plant leaves.