|
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_ok | wshedApply (L_WSHED *wshed) |
|
l_ok | wshedBasins (L_WSHED *wshed, PIXA **ppixa, NUMA **pnalevels) |
|
PIX * | wshedRenderFill (L_WSHED *wshed) |
|
PIX * | wshedRenderColors (L_WSHED *wshed) |
|
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.
static l_int32 identifyWatershedBasin |
( |
L_WSHED * |
wshed, |
|
|
l_int32 |
index, |
|
|
l_int32 |
level, |
|
|
BOX ** |
pbox, |
|
|
PIX ** |
ppixd |
|
) |
| |
|
static |
identifyWatershedBasin()
- Parameters
-
[in] | wshed | |
[in] | index | index of basin to be located |
[in] | level | of basin at point at which the two basins met |
[out] | pbox | bounding box of basin |
[out] | ppixd | pix 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().
static l_int32 mergeLookup |
( |
L_WSHED * |
wshed, |
|
|
l_int32 |
sindex, |
|
|
l_int32 |
dindex |
|
) |
| |
|
static |
mergeLookup()
- Parameters
-
[in] | wshed | |
[in] | sindex | primary index being changed in the merge |
[in] | dindex | index 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().