| 1. |
- Malmberg, Filip, et al.
(författare)
-
An efficient algorithm for exact evaluation of stochastic watersheds
- 2014
-
Ingår i: Pattern Recognition Letters. - : Elsevier BV. - 0167-8655 .- 1872-7344. ; 47, s. 80-84
-
Tidskriftsartikel (refereegranskat)abstract
- The stochastic watershed is a method for unsupervised image segmentation proposed by Angulo and Jeulin (2007). The method first computes a probability density function (PDF), assigning to each piece of contour in the image the probability to appear as a segmentation boundary in seeded watershed segmentation with randomly selected seeds. Contours that appear with high probability are assumed to be more important. This PDF is then post-processed to obtain a final segmentation. The main computational hurdle with the stochastic watershed method is the calculation of the PDF. In the original publication by Angulo and Jeulin, the PDF was estimated by Monte Carlo simulation, i.e., repeatedly selecting random markers and performing seeded watershed segmentation. Meyer and Stawiaski (2010) showed that the PDF can be calculated exactly, without performing any Monte Carlo simulations, but do not provide any implementation details. In a naive implementation, the computational cost of their method is too high to make it useful in practice. Here, we extend the work of Meyer and Stawiaski by presenting an efficient (quasi-linear) algorithm for exact computation of the PDF. We demonstrate that in practice, the proposed method is faster than any previously reported method by more than two orders of magnitude. The algorithm is formulated for general undirected graphs, and thus trivially generalizes to images with any number of dimensions.
|
|
| 2. |
- Malmberg, Filip, et al.
(författare)
-
Exact evaluation of stochastic watersheds : From trees to general graphs
- 2014
-
Ingår i: Discrete Geometry for Computer Imagery. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783319099545 ; 8668, s. 309-319
-
Konferensbidrag (refereegranskat)abstract
- The stochastic watershed is a method for identifying salient contours in an image, with applications to image segmentation. The method computes a probability density function (PDF), assigning to each piece of contour in the image the probability to appear as a segmentation boundary in seeded watershed segmentation with randomly selected seedpoints. Contours that appear with high probability are assumed to be more important. This paper concerns an efficient method for computing the stochastic watershed PDF exactly, without performing any actual seeded watershed computations. A method for exact evaluation of stochastic watersheds was proposed by Meyer and Stawiaski (2010). Their method does not operate directly on the image, but on a compact tree representation where each edge in the tree corresponds to a watershed partition of the image elements. The output of the exact evaluation algorithm is thus a PDF defined over the edges of the tree. While the compact tree representation is useful in its own right, it is in many cases desirable to convert the results from this abstract representation back to the image, e. g, for further processing. Here, we present an efficient linear time algorithm for performing this conversion.
|
|
| 3. |
- Malmberg, Filip, 1980-, et al.
(författare)
-
Exact Evaluation of Targeted Stochastic Watershed Cuts
- 2017
-
Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 216:2, s. 449-460
-
Tidskriftsartikel (refereegranskat)abstract
- Seeded segmentation with minimum spanning forests, also known as segmentation by watershed cuts, is a powerful method for supervised image segmentation. Given that correct segmentation labels are provided for a small set of image elements, called seeds, the watershed cut method completes the labeling for all image elements so that the boundaries between different labels are optimally aligned with salient edges in the image. Here, a randomized version of watershed segmentation, the targeted stochastic watershed, is proposed for performing multi-label targeted image segmentation with stochastic seed input. The input to the algorithm is a set of probability density functions (PDFs), one for each segmentation label, defined over the pixels of the image. For each pixel, we calculate the probability that the pixel is assigned a given segmentation label in seeded watershed segmentation with seeds drawn from the input PDFs. We propose an efficient algorithm (quasi-linear with respect to the number of image elements) for calculating the desired probabilities exactly.
|
|
| 4. |
- Selig, Bettina, et al.
(författare)
-
Fast evaluation of the robust stochastic watershed
- 2015
-
Ingår i: Mathematical Morphology and Its Applications to Signal and Image Processing. - Cham : Springer. - 9783319187198 ; 9082, s. 705-716
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
