A Parallel Watershed Algorithm
Andreas Bieniek, Hans Burkhardt, Henrik Marschner, Michael Nölle, Gerald Schreiber · 1996
The watershed transformation is a popular image segmentation algorithm for grey scale images. Sequential watershed algorithms perform a highly data dependent flooding process over the global image. Because of global data dependencies over the sub-domains parallel algorithms which distribute the image over the available processors and simulate the flooding process have a limited speedup. The achievable speedup is highly data dependent. In this paper we show that it is possible to achieve a data independent speedup for images without plateaus. This can be done by inserting temporary labels where the solution depends on neighboring results. We show that the local solutions can be merged to a global solution in a data-independent way.