Skip to main content
Conference paper - Peer-reviewed, 2015

Fast Evaluation of the Robust Stochastic Watershed

Selig, Bettina; Malmberg, Filip; Luengo, Cris


The stochastic watershed is a segmentation algorithm that estimates the importance of each boundary by repeatedly segmenting the image using a watershed with randomly placed seeds. Recently, this algorithm was further developed in two directions: (1) The exact evaluation algorithm efficiently produces the result of the stochastic watershed with an infinite number of repetitions. This algorithm computes the probability for each boundary to be found by a watershed with random seeds, making the result deterministic and much faster. (2) The robust stochastic watershed improves the usefulness of the segmentation result by avoiding false edges in large regions of uniform intensity. This algorithm simply adds noise to the input image for each repetition of the watershed with random seeds. In this paper, we combine these two algorithms into a method that produces a segmentation result comparable to the robust stochastic watershed, with a considerably reduced computation time. We propose to run the exact evaluation algorithm three times, with uniform noise added to the input image, to produce three different estimates of probabilities for the edges. We combine these three estimates with the geometric mean. In a relatively simple segmentation problem, F-measures averaged over the results on 46 images were identical to those of the robust stochastic watershed, but the computation times were an order of magnitude shorter.


Stochastic watershed; Watershed cuts; Monte Carlo simulations

Published in

Lecture Notes in Computer Science
2015, volume: 9082, pages: 705-716
ISBN: 978-3-319-18719-8


12th International Symposium on Mathematical Morphology (ISMM)

Authors' information

Selig, Bettina
Swedish University of Agricultural Sciences, Centre for Image Analysis
Malmberg, Filip
Swedish University of Agricultural Sciences, Centre for Image Analysis
Luengo, Cris
Swedish University of Agricultural Sciences, Centre for Image Analysis

UKÄ Subject classification

Computer Science

Publication Identifiers


URI (permanent link to this page)