A disjoint set algorithm for the watershed transform
A. Meijster and J.B.T.M. Roerdink. A disjoint set algorithm for the watershed transform. In: Proc. EUSIPCO'98, IX European Signal Processing Conference, September 8 - 11, 1998, Rhodes, Greece, pp. 1665-1668.
Note: Received best young author paper award for EUSIPCO-98.
In this paper the implementation of a watershed transform based on Tarjan's Union-Find algorithm is described. The algorithm computes the watershed as defined by Meyer in \cite{Meyer:94b}. The algorithm consists of two stages. In the first stage the image to be segmented is transformed into a lower complete image, using a FIFO-queue algorithm. In the second stage, the watershed of the lower complete image is computed. In this stage no FIFO-queues are used. This feature makes parallel implementation of the watershed transform much easier.
Download in gzipped postscript format