Fast Morphological Attribute Operations Using Tarjan’s Union-Find Algorithm
Michael H. F. Wilkinson, Jos B. T. M. Roerdink · Kluwer Academic Publishers eBooks · 2005
Morphological attribute openings and closings and related operators are generalizations of the area opening and closing, and allow filtering of images based on a wide variety of shape or size based criteria. A fast union-find algorithm for the computation of these operators is presented in this paper. The new algorithm has a worst case time complexity of O ( N log N ) where N is the image size, as opposed to O ( N 2 log N ) for the existing algorithm. Memory requirements are O ( N ) for both algorithms.