Fast morphological attribute operations using Tarjan's union-find algorithm
M.H.F. Wilkinson and J.B.T.M. Roerdink. Fast morphological attribute operations using Tarjan's union-find algorithm. In: Mathematical Morphology and its Applications to Image and Signal Processing, J. Goutsias, L. Vincent and D. S. Bloomberg (eds.), Kluwer, 2000, pp. 311-320.
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.
Download in pdf format
© Kluwer Acad. Publ. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the publisher.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.