Class WatershedVincentSoille1991

Direct Known Subclasses:
WatershedVincentSoille1991.Connect4, WatershedVincentSoille1991.Connect8

public abstract class WatershedVincentSoille1991
extends Object

Fast watershed based upon Vincient and Soille's 1991 paper [1]. Watershed segments an image using the idea of immersion simulation. For example, the image is treated as a topological map and if you let a droplet of water flow down from each pixel the location the droplets cluster in defines a region. Two different methods are provided for processing the image, a new region is created at each local minima or the user provides an initial seed for each region for it to grow from. The output will be a segmented image with watersheds being assign a value of 0 and each region a value > 0. Watersheds are assigned to pixels which are exactly the same distance from multiple regions, thus it is ambiguous which one it is a member of.

If the image is processed with process(GrayU8) then a new region is created at each local minima and assigned a unique ID > 0. The total number of regions found is returned by getTotalRegions(). This technique will lead to over segmentation on many images.

Initial seeds are provided with a call to process(GrayU8, GrayS32). No new regions will be created. By providing an initial set of seeds over segmentation can be avoided, but prior knowledge of the image is typically needed to create the seeds.


  • For faster processing, the internal labeled image has a 1 pixel border around it. If you call getOutput() this border is removed automatically by creating a sub-image.
  • Connectivity is handled by child sub-classes. An index of neighbors could have been used, but the additional additional array access/loop slows things down a little bit.
  • Watersheds are included. To remove them using RemoveWatersheds
  • Pixel values are assumed to range from 0 to 255, inclusive.

[1] Vincent, Luc, and Pierre Soille. "Watersheds in digital spaces: an efficient algorithm based on immersion simulations." IEEE transactions on pattern analysis and machine intelligence 13.6 (1991): 583-598.

  • Field Details

  • Constructor Details

    • WatershedVincentSoille1991

      protected WatershedVincentSoille1991()
  • Method Details

    • process

      public void process​(GrayU8 input)
      Perform watershed segmentation on the provided input image. New basins are created at each local minima.
      input - Input gray-scale image.
    • process

      public void process​(GrayU8 input, GrayS32 seeds)

      Segments the image using initial seeds for each region. This is often done to avoid over segmentation but requires additional preprocessing and/or knowledge on the image structure. Initial seeds are specified in the input image 'seeds'. A seed is any pixel with a value > 0. New new regions will be created beyond those seeds. The final segmented image is provided by getOutput().

      NOTE: If seeds are used then getTotalRegions() will not return a correct solution.

      input - (Input) Input image
      seeds - (Output) Segmented image containing seeds. Note that all seeds should have a value > 0 and have a value ≤ numRegions.
    • assignNewToNeighbors

      protected abstract void assignNewToNeighbors​(int index)
      See if a neighbor has a label ( > 0 ) or has been assigned WSHED ( == 0 ). If so set distance of pixel index to 1 and add it to fifo.
      index - Pixel whose neighbors are being examined
    • checkNeighborsAssign

      protected abstract void checkNeighborsAssign​(int index)
      Check the neighbors to see if it should become a member or a watershed
      index - Index of the target pixel
    • handleNeighborAssign

      protected void handleNeighborAssign​(int indexTarget, int indexNeighbor)
    • checkNeighborsMasks

      protected abstract void checkNeighborsMasks​(int index)
      Checks neighbors of pixel 'index' to see if their region is MASK, if so they are assigned the currentLabel and added to fifo.
      index - Pixel whose neighbors are being examined.
    • checkMask

      protected void checkMask​(int index)
    • sortPixels

      protected void sortPixels​(GrayU8 input)
      Very fast histogram based sorting. Index of each pixel is placed inside a list for its intensity level.
    • getOutput

      public GrayS32 getOutput()
      Segmented output image with watersheds. This is a sub-image of getOutputBorder() to remove the outside border of -1 valued pixels.
    • getOutputBorder

      public GrayS32 getOutputBorder()
      The entire segmented image used internally. This contains a 1-pixel border around the entire image filled with pixels of value -1.
    • removeWatersheds

      public void removeWatersheds()
      Removes watershed pixels from the output image by merging them into an arbitrary neighbor.
    • getTotalRegions

      public int getTotalRegions()
      Returns the total number of regions labeled. If watersheds have not been removed then this will including the watershed.


      number of regions.