Leptonica  1.83.1
Image processing and image analysis suite
watershed.c File Reference
#include "allheaders.h"

Go to the source code of this file.

Data Structures

struct  L_NewPixel
 
struct  L_WSPixel
 

Macros

#define DEBUG_WATERSHED   0
 

Typedefs

typedef struct L_NewPixel L_NEWPIXEL
 
typedef struct L_WSPixel L_WSPIXEL
 

Functions

static void wshedSaveBasin (L_WSHED *wshed, l_int32 index, l_int32 level)
 
static l_int32 identifyWatershedBasin (L_WSHED *wshed, l_int32 index, l_int32 level, BOX **pbox, PIX **ppixd)
 
static l_int32 mergeLookup (L_WSHED *wshed, l_int32 sindex, l_int32 dindex)
 
static l_int32 wshedGetHeight (L_WSHED *wshed, l_int32 val, l_int32 label, l_int32 *pheight)
 
static void pushNewPixel (L_QUEUE *lq, l_int32 x, l_int32 y, l_int32 *pminx, l_int32 *pmaxx, l_int32 *pminy, l_int32 *pmaxy)
 
static void popNewPixel (L_QUEUE *lq, l_int32 *px, l_int32 *py)
 
static void pushWSPixel (L_HEAP *lh, L_STACK *stack, l_int32 val, l_int32 x, l_int32 y, l_int32 index)
 
static void popWSPixel (L_HEAP *lh, L_STACK *stack, l_int32 *pval, l_int32 *px, l_int32 *py, l_int32 *pindex)
 
static void debugPrintLUT (l_int32 *lut, l_int32 size, l_int32 debug)
 
static void debugWshedMerge (L_WSHED *wshed, char *descr, l_int32 x, l_int32 y, l_int32 label, l_int32 index)
 
L_WSHEDwshedCreate (PIX *pixs, PIX *pixm, l_int32 mindepth, l_int32 debugflag)
 
void wshedDestroy (L_WSHED **pwshed)
 
l_ok wshedApply (L_WSHED *wshed)
 
l_ok wshedBasins (L_WSHED *wshed, PIXA **ppixa, NUMA **pnalevels)
 
PIXwshedRenderFill (L_WSHED *wshed)
 
PIXwshedRenderColors (L_WSHED *wshed)
 

Variables

static const l_uint32 MAX_LABEL_VALUE = 0x7fffffff
 

Detailed Description


     Top-level
           L_WSHED         *wshedCreate()
           void             wshedDestroy()
           l_int32          wshedApply()

     Helpers
           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()

     Output
           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 labeled
       with the index value of its parent.
   (3) Each pixel is also labeled, 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 labeled 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);
     wshedApply(wshed);

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

     Pix *pixd = wshedRenderFill(wshed);

     wshedDestroy(&wshed);

Definition in file watershed.c.

Function Documentation

◆ identifyWatershedBasin()

static l_int32 identifyWatershedBasin ( L_WSHED wshed,
l_int32  index,
l_int32  level,
BOX **  pbox,
PIX **  ppixd 
)
static

identifyWatershedBasin()

Parameters
[in]wshed
[in]indexindex of basin to be located
[in]levelof basin at point at which the two basins met
[out]pboxbounding box of basin
[out]ppixdpix of basin, cropped to its bounding box
Returns
0 if OK, 1 on error
Notes:
     (1) This is a static function, so we assume pixlab, pixs and pixt
         exist and are the same size.
     (2) It selects all pixels that have the label index in pixlab
         and that have a value in pixs that is less than level.
     (3) It is used whenever two seeded basins meet (typically at a saddle),
         or when one seeded basin meets a 'filler'.  All identified
         basins are saved as a watershed.

Definition at line 595 of file watershed.c.

References L_WSPixel::index, L_WShed::linelab32, L_WShed::lines8, L_WShed::linet1, lqueueCreate(), lstackCreate(), L_WShed::lut, pixGetDimensions(), L_WShed::pixs, pixSetPixel(), L_WShed::pixt, ptaGetIPt(), L_WShed::ptas, L_Queue::stack, L_WSPixel::x, and L_WSPixel::y.

Referenced by wshedSaveBasin().

◆ mergeLookup()

static l_int32 mergeLookup ( L_WSHED wshed,
l_int32  sindex,
l_int32  dindex 
)
static

mergeLookup()

Parameters
[in]wshed
[in]sindexprimary index being changed in the merge
[in]dindexindex that sindex will point to after the merge
Returns
0 if OK, 1 on error
Notes:
     (1) The links are a sparse array of Numas showing current back-links.
         The lut gives the current index (of the seed or the minima
         for the wshed  in which it is located.
     (2) Think of each entry in the lut.  There are two types:
            owner:     lut[index] = index
            redirect:  lut[index] != index
     (3) This is called each time a merge occurs.  It puts the lut
         and backlinks in a canonical form after the merge, where
         all entries in the lut point to the current "owner", which
         has all backlinks.  That is, every "redirect" in the lut
         points to an "owner".  The lut always gives the index of
         the current owner.

Definition at line 706 of file watershed.c.

References L_WShed::arraysize, L_WSPixel::index, L_WShed::links, L_WShed::lut, numaAddNumber(), numaCreate(), numaDestroy(), numaGetCount(), numaGetIValue(), and numaJoin().

◆ wshedApply()

l_ok wshedApply ( L_WSHED wshed)

wshedApply()

Parameters
[in]wshedgenerated from wshedCreate()
Returns
0 if OK, 1 on error
Notes:
     (1) N.B. 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.

Definition at line 306 of file watershed.c.

References GET_DATA_BYTE, L_WSPixel::index, L_SORT_INCREASING, lheapCreate(), L_WShed::linelab32, L_WShed::lines8, lstackCreate(), pixGenerateFromPta(), pixGetDimensions(), L_WShed::pixm, L_WShed::pixs, pixSelectMinInConnComp(), ptaGetCount(), ptaGetIPt(), L_WSPixel::val, L_WSPixel::x, and L_WSPixel::y.

◆ wshedBasins()

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

wshedBasins()

Parameters
[in]wshed
[out]ppixa[optional] mask of watershed basins
[out]pnalevels[optional] watershed levels
Returns
0 if OK, 1 on error

Definition at line 1018 of file watershed.c.

References L_CLONE, L_WShed::nalevels, numaClone(), pixaCopy(), and L_WShed::pixad.

Referenced by wshedRenderColors(), and wshedRenderFill().

◆ wshedCreate()

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

wshedCreate()

Parameters
[in]pixs8 bpp source
[in]pixm1 bpp 'marker' seed
[in]mindepthminimum depth; anything less is not saved
[in]debugflag1 for debug output
Returns
WShed, or NULL on error
Notes:
     (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
         eliminated.

Definition at line 207 of file watershed.c.

◆ wshedDestroy()

◆ wshedGetHeight()

static l_int32 wshedGetHeight ( L_WSHED wshed,
l_int32  val,
l_int32  label,
l_int32 *  pheight 
)
static

wshedGetHeight()

Parameters
[in]wshedarray of current indices
[in]valvalue of current pixel popped off queue
[in]labelof pixel or 32 bpp label image
[out]pheightheight of current value from seed or minimum of watershed
Returns
0 if OK, 1 on error
Notes:
     (1) It is only necessary to find the height for a watershed
         that is indexed by a seed or a minima.  This function should
         not be called on a finished watershed (that continues to fill).

Definition at line 768 of file watershed.c.

References L_WShed::namh, L_WShed::nash, L_WShed::nother, numaGetIValue(), and L_WSPixel::val.

◆ wshedRenderColors()

PIX* wshedRenderColors ( L_WSHED wshed)

wshedRenderColors()

Parameters
[in]wshed
Returns
pixd initial image with all basins filled, or null on error

Definition at line 1074 of file watershed.c.

References pixaDestroy(), pixaDisplay(), pixaDisplayRandomCmap(), pixCombineMasked(), pixConvertTo32(), pixCopy(), pixDestroy(), pixGetDimensions(), L_WShed::pixs, and wshedBasins().

◆ wshedRenderFill()

PIX* wshedRenderFill ( L_WSHED wshed)

wshedRenderFill()

Parameters
[in]wshed
Returns
pixd initial image with all basins filled, or NULL on error

Definition at line 1040 of file watershed.c.

References L_CLONE, numaDestroy(), numaGetIValue(), pixaDestroy(), pixaGetBoxGeometry(), pixaGetCount(), pixaGetPix(), pixCopy(), pixDestroy(), pixPaintThroughMask(), L_WShed::pixs, and wshedBasins().

◆ wshedSaveBasin()

static void wshedSaveBasin ( L_WSHED wshed,
l_int32  index,
l_int32  level 
)
static

wshedSaveBasin()

Parameters
[in]wshed
[in]indexindex of basin to be located
[in]levelfilling level reached at the time this function is called
Returns
0 if OK, 1 on error
Notes:
     (1) This identifies a single watershed.  It does not change
         the LUT, which must be done subsequently.
     (2) The fill level of a basin is taken to be level - 1.

Definition at line 553 of file watershed.c.

References identifyWatershedBasin(), L_WSPixel::index, L_INSERT, L_WShed::nalevels, numaAddNumber(), pixaAddBox(), pixaAddPix(), and L_WShed::pixad.