In
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...
, the grassfire transform is the computation of the distance from a pixel to the border of a region. It can be described as "setting fire" to the borders of an image region to yield descriptors such as the region's
skeleton
A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...
or
medial axis
The medial axis of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced in 1967 by Harry Blum as a tool for biological shape reco ...
.
Harry Blum introduced the concept in 1967.
Motivation
A region's skeleton can be a useful descriptor, because it describes things such as the symmetry of the region as well as subparts, depressions and protrusions.
It also provides a way of relating the interior of a region to the shape of the boundary. In the grassfire transform, the skeleton forms at the points in the region where the "fires" meet. In the literature this is described as the locus of meeting waveforms.
Another advantage of using the outcome of the grassfire transform as a descriptor is that it is invertible. Assuming information about when the medial axis or skeleton is created by meeting waveforms is kept, then the skeleton can be restored by radiating outward.
Example algorithm
The algorithm below is a simple two pass method for computing the
Manhattan distance
A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...
from the border of a region. Of course there are several other algorithms for performing the grassfire transform.
for each row in image left to right
for each column in image top to bottom
if (pixel is in region) else
}
}
for each row right to left
for each column bottom to top
if (pixel is in region) else
}
}
Below is the result of this transform. It is important to note that the most intense lines make up the skeleton.
Applications
The grassfire transform can be abstracted to suit a variety of computing problems. It has been shown that it can be extended beyond the context of images to arbitrary functions.
This includes applications in energy minimization problems such as those handled by the
Viterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especiall ...
, max-product belief propagation, resource allocation, and in optimal control methods.
It can also be used to compute the distance between regions by setting the background to be as a region.
See also
*
Topological skeleton
In shape analysis, skeleton (or topological skeleton) of a shape is a thin version of that shape that is equidistant to its boundaries. The skeleton usually emphasizes geometrical and topological properties of the shape, such as its connectivity, ...
*
Distance transform
References
{{Reflist
Image processing
Computer graphics algorithms