Breadth-first search and its application to image processing problems

This paper explores the use of breadth-first graph traversal for the processing of digital images. It presents efficient algorithms for eroding, dilating, skeletonizing, and distance-transforming regions. These algorithms work by traversing regions in a breadth-first manner using a queue for storage of unprocessed pixels. They use memory efficiently--pixels are removed from the queue as soon as their processing has been completed--and they process only pixels in the region (and their neighbors), rather than requiring a complete scan of the image. The image is still represented as a pixel matrix in memory; the graph is just a convenient framework for thinking about the algorithms.