page_title: Grassfire transform
section_title: Example algorithm
hierarchical_section_title: Grassfire transform / Example algorithm
caption_attribution_description: English: This is the resulting image from a distance transform.
context_page_description: 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.
context_section_description: 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.
caption: Result image
exif: {}