116 #include <config_auto.h>
119 #include "allheaders.h"
121 #ifndef NO_CONSOLE_IO
122 #define DEBUG_WATERSHED 0
125 static const l_uint32 MAX_LABEL_VALUE = 0x7fffffff;
150 l_int32
index, l_int32 level,
162 static void pushNewPixel(
L_QUEUE *lq, l_int32
x, l_int32
y,
163 l_int32 *pminx, l_int32 *pmaxx,
164 l_int32 *pminy, l_int32 *pmaxy);
165 static void popNewPixel(
L_QUEUE *lq, l_int32 *px, l_int32 *py);
169 l_int32
x, l_int32
y, l_int32
index);
170 static void popWSPixel(
L_HEAP *lh,
L_STACK *stack, l_int32 *pval,
171 l_int32 *px, l_int32 *py, l_int32 *pindex);
174 static void debugPrintLUT(l_int32 *lut, l_int32 size, l_int32 debug);
176 static void debugWshedMerge(
L_WSHED *wshed,
char *descr, l_int32
x,
177 l_int32
y, l_int32 label, l_int32
index);
216 return (
L_WSHED *)ERROR_PTR(
"pixs is not defined", __func__, NULL);
217 if (pixGetDepth(pixs) != 8)
218 return (
L_WSHED *)ERROR_PTR(
"pixs is not 8 bpp", __func__, NULL);
220 return (
L_WSHED *)ERROR_PTR(
"pixm is not defined", __func__, NULL);
221 if (pixGetDepth(pixm) != 1)
222 return (
L_WSHED *)ERROR_PTR(
"pixm is not 1 bpp", __func__, NULL);
224 if (pixGetWidth(pixm) != w || pixGetHeight(pixm) != h)
225 return (
L_WSHED *)ERROR_PTR(
"pixs/m sizes are unequal", __func__, NULL);
228 return (
L_WSHED *)ERROR_PTR(
"wshed not made", __func__, NULL);
232 wshed->
mindepth = L_MAX(1, mindepth);
240 wshed->
debug = debugflag;
257 if (pwshed == NULL) {
258 L_WARNING(
"ptr address is null!\n", __func__);
262 if ((wshed = *pwshed) == NULL)
280 LEPT_FREE(wshed->
lut);
284 LEPT_FREE(wshed->
links);
308 char two_new_watersheds[] =
"Two new watersheds";
309 char seed_absorbed_into_seeded_basin[] =
"Seed absorbed into seeded basin";
310 char one_new_watershed_label[] =
"One new watershed (label)";
311 char one_new_watershed_index[] =
"One new watershed (index)";
312 char minima_absorbed_into_seeded_basin[] =
313 "Minima absorbed into seeded basin";
314 char minima_absorbed_by_filler_or_another[] =
315 "Minima absorbed by filler or another";
316 l_int32 nseeds, nother, nboth, arraysize;
317 l_int32 i, j,
val,
x,
y, w, h,
index, mindepth;
318 l_int32 imin, imax, jmin, jmax, cindex, clabel, nindex;
319 l_int32 hindex, hlabel, hmin, hmax, minhindex, maxhindex;
321 l_uint32 ulabel, uval;
322 void **lines8, **linelab32;
323 NUMA *nalut, *nalevels, *nash, *namh, *nasi;
332 return ERROR_INT(
"wshed not defined", __func__, 1);
348 for (i = 0; i < nseeds; i++) {
351 pushWSPixel(lh, rstack, (l_int32)uval,
x,
y, i);
370 for (i = 0; i < nother; i++) {
373 pushWSPixel(lh, rstack, (l_int32)uval,
x,
y, nseeds + i);
385 nboth = nseeds + nother;
386 arraysize = 2 * nboth;
391 links = (
NUMA **)LEPT_CALLOC(arraysize,
sizeof(
NUMA *));
392 wshed->
links = links;
393 nindex = nseeds + nother;
400 wshed->
pixad = pixad;
403 L_INFO(
"nseeds = %d, nother = %d\n", __func__, nseeds, nother);
408 if (ulabel == MAX_LABEL_VALUE)
411 clabel = lut[ulabel];
413 if (clabel == cindex)
continue;
414 if (clabel == MAX_LABEL_VALUE) {
417 imin = L_MAX(0,
y - 1);
418 imax = L_MIN(h - 1,
y + 1);
419 jmin = L_MAX(0,
x - 1);
420 jmax = L_MIN(w - 1,
x + 1);
421 for (i = imin; i <= imax; i++) {
422 for (j = jmin; j <= jmax; j++) {
423 if (i ==
y && j ==
x)
continue;
425 pushWSPixel(lh, rstack, (l_int32)uval, j, i, cindex);
436 if (clabel < nseeds && cindex < nseeds) {
439 hmin = L_MIN(hlabel, hindex);
440 hmax = L_MAX(hlabel, hindex);
446 lept_stderr(
"clabel,hlabel = %d,%d\n", clabel, hlabel);
448 lept_stderr(
"cindex,hindex = %d,%d\n", cindex, hindex);
453 if (hmin >= mindepth) {
454 debugWshedMerge(wshed, two_new_watersheds,
455 x,
y, clabel, cindex);
462 debugPrintLUT(lut, nindex, wshed->
debug);
464 debugPrintLUT(lut, nindex, wshed->
debug);
466 debugPrintLUT(lut, nindex, wshed->
debug);
469 debugWshedMerge(wshed, seed_absorbed_into_seeded_basin,
470 x,
y, clabel, cindex);
474 if (hindex > hlabel) {
479 }
else if (clabel < nseeds && cindex >= nboth) {
482 debugWshedMerge(wshed, one_new_watershed_label,
483 x,
y, clabel, cindex);
487 }
else if (cindex < nseeds && clabel >= nboth) {
488 debugWshedMerge(wshed, one_new_watershed_index,
489 x,
y, clabel, cindex);
493 }
else if (clabel < nseeds) {
496 debugWshedMerge(wshed, minima_absorbed_into_seeded_basin,
497 x,
y, clabel, cindex);
499 }
else if (cindex < nseeds) {
500 debugWshedMerge(wshed, minima_absorbed_into_seeded_basin,
501 x,
y, clabel, cindex);
504 debugWshedMerge(wshed, minima_absorbed_by_filler_or_another,
505 x,
y, clabel, cindex);
514 for (i = 0; i < nseeds; i++) {
561 L_ERROR(
"wshed not defined\n", __func__);
601 l_int32 imin, imax, jmin, jmax, minx, miny, maxx, maxy;
602 l_int32 bw, bh, i, j, w, h,
x,
y;
604 l_uint32 label, bval, lval;
605 void **lines8, **linelab32, **linet1;
607 PIX *pixs, *pixt, *pixd;
611 return ERROR_INT(
"&box not defined", __func__, 1);
614 return ERROR_INT(
"&pixd not defined", __func__, 1);
617 return ERROR_INT(
"wshed not defined", __func__, 1);
632 minx = miny = 1000000;
636 pushNewPixel(lq,
x,
y, &minx, &maxx, &miny, &maxy);
647 popNewPixel(lq, &
x, &
y);
648 imin = L_MAX(0,
y - 1);
649 imax = L_MIN(h - 1,
y + 1);
650 jmin = L_MAX(0,
x - 1);
651 jmax = L_MIN(w - 1,
x + 1);
652 for (i = imin; i <= imax; i++) {
653 for (j = jmin; j <= jmax; j++) {
654 if (j ==
x && i ==
y)
continue;
656 if (label == MAX_LABEL_VALUE || lut[label] !=
index)
continue;
658 if (bval == 1)
continue;
660 if (lval >= level)
continue;
662 pushNewPixel(lq, j, i, &minx, &maxx, &miny, &maxy);
668 bw = maxx - minx + 1;
669 bh = maxy - miny + 1;
710 l_int32 i, n, size,
index;
716 return ERROR_INT(
"wshed not defined", __func__, 1);
718 if (sindex < 0 || sindex >= size)
719 return ERROR_INT(
"invalid sindex", __func__, 1);
720 if (dindex < 0 || dindex >= size)
721 return ERROR_INT(
"invalid dindex", __func__, 1);
725 links = wshed->
links;
727 if ((na = links[sindex]) != NULL) {
729 for (i = 0; i < n; i++) {
734 lut[sindex] = dindex;
742 numaJoin(links[dindex], links[sindex], 0, -1);
776 return ERROR_INT(
"&height not defined", __func__, 1);
779 return ERROR_INT(
"wshed not defined", __func__, 1);
781 if (label < wshed->nseeds)
783 else if (label < wshed->nseeds + wshed->
nother)
786 return ERROR_INT(
"finished watershed; should not call", __func__, 1);
788 *pheight =
val - minval;
820 L_ERROR(
"queue not defined\n", __func__);
825 *pminx = L_MIN(*pminx,
x);
826 *pmaxx = L_MAX(*pmaxx,
x);
827 *pminy = L_MIN(*pminy,
y);
828 *pmaxy = L_MAX(*pmaxy,
y);
864 L_ERROR(
"lqueue not defined\n", __func__);
903 L_ERROR(
"heap not defined\n", __func__);
907 L_ERROR(
"stack not defined\n", __func__);
917 wsp->
val = (l_float32)
val;
953 L_ERROR(
"lheap not defined\n", __func__);
957 L_ERROR(
"stack not defined\n", __func__);
960 if (!pval || !px || !py || !pindex) {
961 L_ERROR(
"data can't be returned\n", __func__);
967 *pval = (l_int32)wsp->
val;
970 *pindex = wsp->
index;
976 debugPrintLUT(l_int32 *lut,
984 for (i = 0; i < size; i++)
991 debugWshedMerge(
L_WSHED *wshed,
998 if (!wshed || (wshed->
debug == 0))
1023 return ERROR_INT(
"wshed not defined", __func__, 1);
1042 l_int32 i, n, level, bx, by;
1048 return (
PIX *)ERROR_PTR(
"wshed not defined", __func__, NULL);
1053 for (i = 0; i < n; i++) {
1077 PIX *pixg, *pixt, *pixc, *pixm, *pixd;
1081 return (
PIX *)ERROR_PTR(
"wshed not defined", __func__, NULL);
#define SET_DATA_BIT(pdata, n)
#define SET_DATA_FOUR_BYTES(pdata, n, val)
#define GET_DATA_BYTE(pdata, n)
#define GET_DATA_FOUR_BYTES(pdata, n)
#define GET_DATA_BIT(pdata, n)
BOX * boxCreate(l_int32 x, l_int32 y, l_int32 w, l_int32 h)
boxCreate()
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
void * lheapRemove(L_HEAP *lh)
lheapRemove()
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
NUMA * numaCreate(l_int32 n)
numaCreate()
NUMA * numaClone(NUMA *na)
numaClone()
void numaDestroy(NUMA **pna)
numaDestroy()
l_ok numaSetValue(NUMA *na, l_int32 index, l_float32 val)
numaSetValue()
l_int32 numaGetCount(NUMA *na)
numaGetCount()
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
l_int32 * numaGetIArray(NUMA *na)
numaGetIArray()
l_ok numaJoin(NUMA *nad, NUMA *nas, l_int32 istart, l_int32 iend)
numaJoin()
NUMA * numaMakeConstant(l_float32 val, l_int32 size)
numaMakeConstant()
NUMA * numaMakeSequence(l_float32 startval, l_float32 increment, l_int32 size)
numaMakeSequence()
void pixDestroy(PIX **ppix)
pixDestroy()
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
PIX * pixClone(PIX *pixs)
pixClone()
void ** pixGetLinePtrs(PIX *pix, l_int32 *psize)
pixGetLinePtrs()
l_ok pixSetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 val)
pixSetPixel()
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
l_ok pixSetAllArbitrary(PIX *pix, l_uint32 val)
pixSetAllArbitrary()
l_ok pixPaintThroughMask(PIX *pixd, PIX *pixm, l_int32 x, l_int32 y, l_uint32 val)
pixPaintThroughMask()
l_ok pixCombineMasked(PIX *pixd, PIX *pixs, PIX *pixm)
pixCombineMasked()
PIX * pixClipRectangle(PIX *pixs, BOX *box, BOX **pboxc)
pixClipRectangle()
l_ok pixaAddPix(PIXA *pixa, PIX *pix, l_int32 copyflag)
pixaAddPix()
void pixaDestroy(PIXA **ppixa)
pixaDestroy()
PIXA * pixaCreate(l_int32 n)
pixaCreate()
PIXA * pixaCopy(PIXA *pixa, l_int32 copyflag)
pixaCopy()
l_int32 pixaGetCount(PIXA *pixa)
pixaGetCount()
l_ok pixaAddBox(PIXA *pixa, BOX *box, l_int32 copyflag)
pixaAddBox()
l_ok pixaGetBoxGeometry(PIXA *pixa, l_int32 index, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
pixaGetBoxGeometry()
PIX * pixaGetPix(PIXA *pixa, l_int32 index, l_int32 accesstype)
pixaGetPix()
PIX * pixaDisplay(PIXA *pixa, l_int32 w, l_int32 h)
pixaDisplay()
PIX * pixaDisplayRandomCmap(PIXA *pixa, l_int32 w, l_int32 h)
pixaDisplayRandomCmap()
PIX * pixConvertTo32(PIX *pixs)
pixConvertTo32()
l_ok ptaGetIPt(PTA *pta, l_int32 index, l_int32 *px, l_int32 *py)
ptaGetIPt()
l_int32 ptaGetCount(PTA *pta)
ptaGetCount()
void ptaDestroy(PTA **ppta)
ptaDestroy()
PIX * pixGenerateFromPta(PTA *pta, l_int32 w, l_int32 h)
pixGenerateFromPta()
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
l_ok pixRasterop(PIX *pixd, l_int32 dx, l_int32 dy, l_int32 dw, l_int32 dh, l_int32 op, PIX *pixs, l_int32 sx, l_int32 sy)
pixRasterop()
l_ok pixSelectMinInConnComp(PIX *pixs, PIX *pixm, PTA **ppta, NUMA **pnav)
pixSelectMinInConnComp()
l_ok pixLocalExtrema(PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
pixLocalExtrema()
PIX * pixRemoveSeededComponents(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
pixRemoveSeededComponents()
l_int32 lstackGetCount(L_STACK *lstack)
lstackGetCount()
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
l_ok lstackAdd(L_STACK *lstack, void *item)
lstackAdd()
void * lstackRemove(L_STACK *lstack)
lstackRemove()
L_STACK * lstackCreate(l_int32 n)
lstackCreate()
void lept_stderr(const char *fmt,...)
lept_stderr()
PIX * wshedRenderFill(L_WSHED *wshed)
wshedRenderFill()
static l_int32 wshedGetHeight(L_WSHED *wshed, l_int32 val, l_int32 label, l_int32 *pheight)
wshedGetHeight()
static l_int32 identifyWatershedBasin(L_WSHED *wshed, l_int32 index, l_int32 level, BOX **pbox, PIX **ppixd)
identifyWatershedBasin()
L_WSHED * wshedCreate(PIX *pixs, PIX *pixm, l_int32 mindepth, l_int32 debugflag)
wshedCreate()
void wshedDestroy(L_WSHED **pwshed)
wshedDestroy()
static l_int32 mergeLookup(L_WSHED *wshed, l_int32 sindex, l_int32 dindex)
mergeLookup()
l_ok wshedBasins(L_WSHED *wshed, PIXA **ppixa, NUMA **pnalevels)
wshedBasins()
static void wshedSaveBasin(L_WSHED *wshed, l_int32 index, l_int32 level)
wshedSaveBasin()
l_ok wshedApply(L_WSHED *wshed)
wshedApply()
PIX * wshedRenderColors(L_WSHED *wshed)
wshedRenderColors()