The Grassfire Transform
The grassfire transform counts how far each pixel is from a region of interest.
Although the algorithm requires two passes over the image, it can save computation by allowing a region to be grown or shrunk by any number of pixels in three passes. To grow a region by n pixels with other methods requires n passes. The grassfire transform is also useful because it identifies the borders of a
region allowing one to "skeltonize" it.
The algorithm works as follows:
- Select a value for the border. It should either be zero or a very large integer.
- Identify the region of interest.
- Begin at one corner of and iterate through the image. If the pixel is in the region of interest, set the value of the pixel to zero. Otherwise, look at the adjacent (either four or eight connected) pixels that have already been visited, and assign the minimum of these values plus one to the current pixel.
- Do a second pass over the image, beginning at the opposite corner. If the pixel is in the region of interest, continue. Otherwise, look at the adjacent pixels that have already been visited on the second pass and calculate the minimum. If this minimum is less than the current value of the pixel, assign one plus this value to the pixel.
For professor Maxwell's explanation, go to http://www.palantir.swarthmore.edu/~maxwell/classes/e27/homework.htm. My code is in grassfire.c
The effect of the grassfire transform is illustrated on the following image. Unfortunately, some of the images may not show up well.
When the border is set to zero and the background is the region of interest, the grassfire transform becomes:
When the border is set to inf and the background is the region of interest, the grassfire transform becomes:
When the border is set to zero and the stopsign is the region of interest, the grassfire transform becomes:
When the border is set to inf and the stopsign is the region of interest, the grassfire transform becomes:
When the region is skeletonized, it becomes:
