Morphological grayscale reconstruction in image analysis: Applications and efficient algorithms

Morphological reconstruction is part of a set of image operators often referred to as geodesic. In the binary case, reconstruction simply extracts the connected components of binary image I (the mask) which are "marked" by a (binary) image J contained in I. This transformation can be extended to the grayscale case, where it turns out to be extremely useful for several image analysis tasks. This paper first provides two different formal definitions of grayscale reconstruction. It then illustrates the use of grayscale reconstruction in various image processing applications and aims at demonstrating the usefulness of this transformation for image filtering and segmentation tasks. Lastly, the paper focuses on implementation issues: The standard parallel and sequential approaches to reconstruction are briefly recalled; their common drawback is their inefficiency on conventional computers. To improve this situation, a new algorithm is introduced, which is based on the notion of regional maxima and makes use of breadthfirst image scannings implemented via a queue of pixels. Its combination with the sequential technique results in a hybrid grayscale reconstruction algorithm which is an order of magnitude faster than any previously known algorithm.