Morphological grayscale reconstruction in image analysis: applications and efficient algorithms

TLDR

Gray‑scale reconstruction, defined in two formal ways, is widely applied to image filtering and segmentation, yet existing parallel and sequential methods are reviewed as inefficient. The authors introduce an algorithm based on regional maxima and breadth‑first scanning with a pixel queue to improve reconstruction efficiency. The algorithm employs regional maxima and breadth‑first image scanning via a pixel queue. The hybrid algorithm, combining the new breadth‑first approach with the sequential technique, is an order of magnitude faster than previous methods, demonstrating that existing approaches are inefficient on conventional computers.

Abstract

Two different formal definitions of gray-scale reconstruction are presented. The use of gray-scale reconstruction in various image processing applications discussed to illustrate the usefulness of this transformation for image filtering and segmentation tasks. The standard parallel and sequential approaches to reconstruction are reviewed. It is shown that their common drawback is their inefficiency on conventional computers. To improve this situation, an algorithm that is based on the notion of regional maxima and makes use of breadth-first image scannings implemented using a queue of pixels is introduced. Its combination with the sequential technique results in a hybrid gray-scale reconstruction algorithm which is an order of magnitude faster than any previously known algorithm.