Grassfire transform

In image processing, 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 or medial axis. Harry Blum introduced the concept in 1967.[1]

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.[2] 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.[2]

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.[1]

Example algorithm

The algorithm below is a simple two pass method for computing the Manhattan distance 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) {
        set pixel to 1 + minimum value of the north and west neighbours
      } else {
        set pixel to zero
      }
    }
  }

  for each row right to left
    for each column bottom to top
      if (pixel is in region) {
        set pixel to min(value of the pixel,1 + minimum value of the south and east neighbours)
      } else {
        set pixel to zero
      }
    }
  }

Below is the result of this transform. It is important to note that the most intense lines make up the skeleton.

Source image
Result image

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.[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.[3]

It can also be used to compute the distance between regions by setting the background to be as a region.

gollark: Democratic ones theoretically allow more input from everyone, which should lead to decisions which consider their interests more and take into account information people know, but also run into whatever issues existing democracies have plus probably exciting new ones due to presumably having a direct democracy voting on a lot of things.
gollark: Hierarchical ones (theoretically) allow clear direction and management from the top but also lack input from lower levels and are vulnerable to the top people being wrong/bad.
gollark: Before trying to think of ideas for organization structure it might be good to clarify what exactly the organizational structure should do/allow/optimize.
gollark: https://www.youtube.com/watch?v=xA27x7GRMZQ
gollark: You can buy and sell tokens which will become $1 if event X happens and $0 otherwise.

See also

References
  1. Blum, Harry. A Transformation for extracting new descriptors of shape, 1967,"http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf",6/8/2012
  2. Leymarie, F; Levine, M.D (1992). "Simulating the grassfire transform using an active contour model". IEEE Transactions on Pattern Analysis and Machine Intelligence. 14: 56–75. doi:10.1109/34.107013.
  3. Felzenszwalb, Pedro F; Huttenlocher, Daniel P (2012). "Distance Transforms of Sampled Functions". Theory of Computing. 8: 415–28. CiteSeerX 10.1.1.88.1647. doi:10.4086/toc.2012.v008a019.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.