Find watershed basins from specified seeds in grayscale image. More...

#include <stdio.h>
#include <stdlib.h>
#include "allheaders.h"

Data Structures
struct	L_NewPixel
struct	L_WSPixel
Defines
#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_WSHED *	wshedCreate (PIX pixs, PIX pixm, l_int32 mindepth, l_int32 debugflag)
void	wshedDestroy (L_WSHED **pwshed)
l_int32	wshedApply (L_WSHED *wshed)
l_int32	wshedBasins (L_WSHED wshed, PIXA ppixa, NUMA *pnalevels)
PIX *	wshedRenderFill (L_WSHED *wshed)
PIX *	wshedRenderColors (L_WSHED *wshed)
Variables
static const l_uint32	MAX_LABEL_VALUE = 0x7fffffff

Detailed Description

Find watershed basins from specified seeds in grayscale image.

    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 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);
    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.

Define Documentation

#define DEBUG_WATERSHED 0

Definition at line 107 of file watershed.c.

Typedef Documentation

typedef struct L_NewPixel L_NEWPIXEL

Definition at line 117 of file watershed.c.

typedef struct L_WSPixel L_WSPIXEL

Definition at line 126 of file watershed.c.

Function Documentation

static void wshedSaveBasin	(	L_WSHED *	wshed,
		l_int32	index,
		l_int32	level
	)		`[static]`

wshedSaveBasin()

Input: wshed index (index of basin to be located) level (filling level reached at the time this function is called) Return: 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 - 1.

Definition at line 545 of file watershed.c.

References identifyWatershedBasin(), L_ERROR, L_INSERT, L_WShed::nalevels, numaAddNumber(), pixaAddBox(), pixaAddPix(), L_WShed::pixad, and PROCNAME.

Referenced by wshedApply().

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

identifyWatershedBasin()

Input: wshed index (index of basin to be located) level (of basin at point at which the two basins met) &box (<return> bounding box of basin) &pixd (<return> pix of basin, cropped to its bounding box) Return: 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 in pixlab and that have a value in pixs that is less than . (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 588 of file watershed.c.

References boxCreate(), L_WShed::debug, ERROR_INT, GET_DATA_BIT, GET_DATA_BYTE, GET_DATA_FOUR_BYTES, L_MAX, L_MIN, L_WShed::linelab32, L_WShed::lines8, L_WShed::linet1, lqueueCreate(), lqueueDestroy(), lqueueGetCount(), lstackCreate(), L_WShed::lut, MAX_LABEL_VALUE, NULL, PIX_DST, PIX_SRC, pixClipRectangle(), pixGetDimensions(), L_WShed::pixlab, pixRasterop(), L_WShed::pixs, pixSetPixel(), L_WShed::pixt, popNewPixel(), PROCNAME, ptaGetIPt(), L_WShed::ptas, pushNewPixel(), SET_DATA_BIT, L_Queue::stack, L_WSPixel::x, and L_WSPixel::y.

Referenced by wshedSaveBasin().

static l_int32 mergeLookup	(	L_WSHED *	wshed,
		l_int32	sindex,
		l_int32	dindex
	)		`[static]`

mergeLookup()

Input: wshed sindex (primary index being changed in the merge) dindex (index that will point to after the merge) Return: 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 700 of file watershed.c.

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

Referenced by wshedApply().

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

wshedGetHeight()

Input: wshed (array of current indices) val (value of current pixel popped off queue) label (of pixel or 32 bpp label image) &height (<return> height of current value from seed or minimum of watershed) Return: 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 762 of file watershed.c.

References ERROR_INT, L_WShed::namh, L_WShed::nash, L_WShed::nother, numaGetIValue(), and PROCNAME.

Referenced by wshedApply().

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]`

Definition at line 803 of file watershed.c.

References CALLOC, L_ERROR, L_MAX, L_MIN, lqueueAdd(), lstackGetCount(), lstackRemove(), PROCNAME, L_Queue::stack, L_WSPixel::x, L_NewPixel::x, L_WSPixel::y, and L_NewPixel::y.

Referenced by identifyWatershedBasin().

static void popNewPixel	(	L_QUEUE *	lq,
		l_int32 *	px,
		l_int32 *	py
	)		`[static]`

Definition at line 852 of file watershed.c.

References L_ERROR, lqueueRemove(), lstackAdd(), NULL, PROCNAME, L_Queue::stack, L_NewPixel::x, and L_NewPixel::y.

Referenced by identifyWatershedBasin().

static void pushWSPixel	(	L_HEAP *	lh,
		L_STACK *	stack,
		l_int32	val,
		l_int32	x,
		l_int32	y,
		l_int32	index
	)		`[static]`

Definition at line 889 of file watershed.c.

References CALLOC, L_WSPixel::index, L_ERROR, lheapAdd(), lstackGetCount(), lstackRemove(), PROCNAME, L_WSPixel::val, L_WSPixel::x, and L_WSPixel::y.

Referenced by wshedApply().

static void popWSPixel	(	L_HEAP *	lh,
		L_STACK *	stack,
		l_int32 *	pval,
		l_int32 *	px,
		l_int32 *	py,
		l_int32 *	pindex
	)		`[static]`

Definition at line 940 of file watershed.c.

References L_WSPixel::index, L_ERROR, lheapRemove(), lstackAdd(), NULL, PROCNAME, L_WSPixel::val, L_WSPixel::x, and L_WSPixel::y.

Referenced by wshedApply().

static void debugPrintLUT	(	l_int32 *	lut,
		l_int32	size,
		l_int32	debug
	)		`[static]`

Definition at line 976 of file watershed.c.

References size.

Referenced by wshedApply().

static void debugWshedMerge	(	L_WSHED *	wshed,
		char *	descr,
		l_int32	x,
		l_int32	y,
		l_int32	label,
		l_int32	index
	)		`[static]`

Definition at line 992 of file watershed.c.

References L_WShed::debug.

Referenced by wshedApply().

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

wshedCreate()

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

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 188 of file watershed.c.

References CALLOC, L_WShed::debug, ERROR_PTR, L_MAX, L_WShed::linelab32, L_WShed::linem1, L_WShed::lines8, L_WShed::linet1, MAX_LABEL_VALUE, L_WShed::mindepth, NULL, pixClone(), pixCreate(), pixGetDepth(), pixGetDimensions(), pixGetHeight(), pixGetLinePtrs(), pixGetWidth(), L_WShed::pixlab, L_WShed::pixm, L_WShed::pixs, pixSetAllArbitrary(), L_WShed::pixt, and PROCNAME.

Referenced by main().

void wshedDestroy ( L_WSHED ** pwshed )

wshedDestroy()

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

Definition at line 235 of file watershed.c.

References L_WShed::arraysize, FREE, L_WARNING, L_WShed::linelab32, L_WShed::linem1, L_WShed::lines8, L_WShed::linet1, L_WShed::links, L_WShed::lut, L_WShed::nalevels, L_WShed::namh, L_WShed::nash, L_WShed::nasi, NULL, numaDestroy(), L_WShed::pixad, pixaDestroy(), pixDestroy(), L_WShed::pixlab, L_WShed::pixm, L_WShed::pixs, L_WShed::pixt, PROCNAME, ptaDestroy(), and L_WShed::ptas.

Referenced by main().

l_int32 wshedApply ( L_WSHED * wshed )

wshedApply()

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.

Definition at line 290 of file watershed.c.

References L_WShed::arraysize, CALLOC, L_WShed::debug, debugPrintLUT(), debugWshedMerge(), ERROR_INT, GET_DATA_BYTE, GET_DATA_FOUR_BYTES, L_WSPixel::index, L_INFO_INT2, L_MAX, L_MIN, L_SORT_INCREASING, lheapCreate(), lheapDestroy(), lheapGetCount(), L_WShed::linelab32, L_WShed::lines8, L_WShed::links, lstackCreate(), lstackDestroy(), L_WShed::lut, MAX_LABEL_VALUE, mergeLookup(), L_WShed::mindepth, L_WShed::nalevels, L_WShed::namh, L_WShed::nash, L_WShed::nasi, L_WShed::nseeds, NULL, numaCreate(), numaDestroy(), numaGetIArray(), numaGetIValue(), numaMakeConstant(), numaMakeSequence(), numaSetValue(), pixaCreate(), L_WShed::pixad, pixDestroy(), pixGenerateFromPta(), pixGetDimensions(), pixGetPixel(), pixLocalExtrema(), L_WShed::pixm, pixRemoveSeededComponents(), L_WShed::pixs, pixSelectMinInConnComp(), popWSPixel(), PROCNAME, ptaDestroy(), ptaGetCount(), ptaGetIPt(), L_WShed::ptas, pushWSPixel(), SET_DATA_FOUR_BYTES, TRUE, L_WSPixel::val, wshedGetHeight(), wshedSaveBasin(), L_WSPixel::x, and L_WSPixel::y.