Zakariyya Mughal




version 0.04



            L_WSHED         *wshedCreate()
            void             wshedDestroy()
            l_int32          wshedApply()

            static l_int32   identifyWatershedBasin()
            static l_int32   mergeLookup()
            static l_int32   wshedGetHeight()
            static void      pushNewPixel()
            static void      popNewPixel()
            static void      pushWSPixel()
            static void      popWSPixel()
            static void      debugPrintLUT()
            static void      debugWshedMerge()

            l_int32          wshedBasins()
            PIX             *wshedRenderFill()
            PIX             *wshedRenderColors()

  The watershed function identifies the "catch basins" of the input
  8 bpp image, with respect to the specified seeds or "markers".
  The use is in segmentation, but the selection of the markers is
  critical to getting meaningful results.

  How are the markers selected?  You can't simply use the local
  minima, because a typical image has sufficient noise so that
  a useful catch basin can easily have multiple local minima.  However
  they are selected, the question for the watershed function is
  how to handle local minima that are not markers.  The reason
  this is important is because of the algorithm used to find the
  watersheds, which is roughly like this:

    (1) Identify the markers and the local minima, and enter them
        into a priority queue based on the pixel value.  Each marker
        is shrunk to a single pixel, if necessary, before the
        operation starts.
    (2) Feed the priority queue with neighbors of pixels that are
        popped off the queue.  Each of these queue pixels is labelled
        with the index value of its parent.
    (3) Each pixel is also labelled, in a 32-bit image, with the marker
        or local minimum index, from which it was originally derived.
    (4) There are actually 3 classes of labels: seeds, minima, and
        fillers.  The fillers are labels of regions that have already
        been identified as watersheds and are continuing to fill, for
        the purpose of finding higher watersheds.
    (5) When a pixel is popped that has already been labelled in the
        32-bit image and that label differs from the label of its
        parent (stored in the queue pixel), a boundary has been crossed.
        There are several cases:
         (a) Both parents are derived from markers but at least one
             is not deep enough to become a watershed.  Absorb the
             shallower basin into the deeper one, fixing the LUT to
             redirect the shallower index to the deeper one.
         (b) Both parents are derived from markers and both are deep
             enough.  Identify and save the watershed for each marker.
         (c) One parent was derived from a marker and the other from
             a minima: absorb the minima basin into the marker basin.
         (d) One parent was derived from a marker and the other is
             a filler: identify and save the watershed for the marker.
         (e) Both parents are derived from minima: merge them.
         (f) One parent is a filler and the other is derived from a
             minima: merge the minima into the filler.
    (6) The output of the watershed operation consists of:
         - a pixa of the basins
         - a pta of the markers
         - a numa of the watershed levels

  Typical usage:
      L_WShed *wshed = wshedCreate(pixs, pixseed, mindepth, 0);

      wshedBasins(wshed, &pixa, &nalevels);
        ... do something with pixa, nalevels ...

      Pix *pixd = wshedRenderFill(wshed);




l_int32 wshedApply ( L_WSHED *wshed )


      Input:  wshed (generated from wshedCreate())
      Return: 0 if OK, 1 on error

  Iportant note:
      (1) This is buggy.  It seems to locate watersheds that are
          duplicates.  The watershed extraction after complete fill
          grabs some regions belonging to existing watersheds.
          See prog/watershedtest.c for testing.


l_int32 wshedBasins ( L_WSHED *wshed, PIXA **ppixa, NUMA **pnalevels )


      Input:  wshed
              &pixa  (<optional return> mask of watershed basins)
              &nalevels   (<optional return> watershed levels)
      Return: 0 if OK, 1 on error


L_WSHED * wshedCreate ( PIX *pixs, PIX *pixm, l_int32 mindepth, l_int32 debugflag )


      Input:  pixs  (8 bpp source)
              pixm  (1 bpp 'marker' seed)
              mindepth (minimum depth; anything less is not saved)
              debugflag (1 for debug output)
      Return: WShed, or null on error

      (1) It is not necessary for the fg pixels in the seed image
          be at minima, or that they be isolated.  We extract a
          single pixel from each connected component, and a seed
          anywhere in a watershed will eventually label the watershed
          when the filling level reaches it.
      (2) Set mindepth to some value to ignore noise in pixs that
          can create small local minima.  Any watershed shallower
          than mindepth, even if it has a seed, will not be saved;
          It will either be incorporated in another watershed or


void wshedDestroy ( L_WSHED **pwshed )


      Input:  &wshed (<will be set to null before returning>)
      Return: void


PIX * wshedRenderColors ( L_WSHED *wshed )


      Input:  wshed
      Return: pixd (initial image with all basins filled), or null on error


PIX * wshedRenderFill ( L_WSHED *wshed )


      Input:  wshed
      Return: pixd (initial image with all basins filled), or null on error


Zakariyya Mughal <>


This software is copyright (c) 2014 by Zakariyya Mughal.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.