Grassfire transform

In image processing, the grassfire transform is the computation of the distance from a pixel to the border of a region.

In the grassfire transform, the skeleton forms at the points in the region where the "fires" meet.

[1] The algorithm below is a simple two pass method for computing the Manhattan distance from the border of a region.

The grassfire transform can be abstracted to suit a variety of computing problems.

[3] This includes applications in energy minimization problems such as those handled by the Viterbi algorithm, max-product belief propagation, resource allocation, and in optimal control methods.