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);
215 PROCNAME(
"wshedCreate");
218 return (
L_WSHED *)ERROR_PTR(
"pixs is not defined", procName, NULL);
219 if (pixGetDepth(pixs) != 8)
220 return (
L_WSHED *)ERROR_PTR(
"pixs is not 8 bpp", procName, NULL);
222 return (
L_WSHED *)ERROR_PTR(
"pixm is not defined", procName, NULL);
223 if (pixGetDepth(pixm) != 1)
224 return (
L_WSHED *)ERROR_PTR(
"pixm is not 1 bpp", procName, NULL);
226 if (pixGetWidth(pixm) != w || pixGetHeight(pixm) != h)
227 return (
L_WSHED *)ERROR_PTR(
"pixs/m sizes are unequal", procName, NULL);
230 return (
L_WSHED *)ERROR_PTR(
"wshed not made", procName, NULL);
234 wshed->
mindepth = L_MAX(1, mindepth);
242 wshed->
debug = debugflag;
259 PROCNAME(
"wshedDestroy");
261 if (pwshed == NULL) {
262 L_WARNING(
"ptr address is null!\n", procName);
266 if ((wshed = *pwshed) == NULL)
284 LEPT_FREE(wshed->
lut);
288 LEPT_FREE(wshed->
links);
312 char two_new_watersheds[] =
"Two new watersheds";
313 char seed_absorbed_into_seeded_basin[] =
"Seed absorbed into seeded basin";
314 char one_new_watershed_label[] =
"One new watershed (label)";
315 char one_new_watershed_index[] =
"One new watershed (index)";
316 char minima_absorbed_into_seeded_basin[] =
317 "Minima absorbed into seeded basin";
318 char minima_absorbed_by_filler_or_another[] =
319 "Minima absorbed by filler or another";
320 l_int32 nseeds, nother, nboth, arraysize;
321 l_int32 i, j,
val,
x,
y, w, h,
index, mindepth;
322 l_int32 imin, imax, jmin, jmax, cindex, clabel, nindex;
323 l_int32 hindex, hlabel, hmin, hmax, minhindex, maxhindex;
325 l_uint32 ulabel, uval;
326 void **lines8, **linelab32;
327 NUMA *nalut, *nalevels, *nash, *namh, *nasi;
335 PROCNAME(
"wshedApply");
338 return ERROR_INT(
"wshed not defined", procName, 1);
354 for (i = 0; i < nseeds; i++) {
357 pushWSPixel(lh, rstack, (l_int32)uval,
x,
y, i);
376 for (i = 0; i < nother; i++) {
379 pushWSPixel(lh, rstack, (l_int32)uval,
x,
y, nseeds + i);
391 nboth = nseeds + nother;
392 arraysize = 2 * nboth;
397 links = (
NUMA **)LEPT_CALLOC(arraysize,
sizeof(
NUMA *));
398 wshed->
links = links;
399 nindex = nseeds + nother;
406 wshed->
pixad = pixad;
409 L_INFO(
"nseeds = %d, nother = %d\n", procName, nseeds, nother);
414 if (ulabel == MAX_LABEL_VALUE)
417 clabel = lut[ulabel];
419 if (clabel == cindex)
continue;
420 if (clabel == MAX_LABEL_VALUE) {
423 imin = L_MAX(0,
y - 1);
424 imax = L_MIN(h - 1,
y + 1);
425 jmin = L_MAX(0,
x - 1);
426 jmax = L_MIN(w - 1,
x + 1);
427 for (i = imin; i <= imax; i++) {
428 for (j = jmin; j <= jmax; j++) {
429 if (i ==
y && j ==
x)
continue;
431 pushWSPixel(lh, rstack, (l_int32)uval, j, i, cindex);
442 if (clabel < nseeds && cindex < nseeds) {
445 hmin = L_MIN(hlabel, hindex);
446 hmax = L_MAX(hlabel, hindex);
452 lept_stderr(
"clabel,hlabel = %d,%d\n", clabel, hlabel);
454 lept_stderr(
"cindex,hindex = %d,%d\n", cindex, hindex);
459 if (hmin >= mindepth) {
460 debugWshedMerge(wshed, two_new_watersheds,
461 x,
y, clabel, cindex);
468 debugPrintLUT(lut, nindex, wshed->
debug);
470 debugPrintLUT(lut, nindex, wshed->
debug);
472 debugPrintLUT(lut, nindex, wshed->
debug);
475 debugWshedMerge(wshed, seed_absorbed_into_seeded_basin,
476 x,
y, clabel, cindex);
480 if (hindex > hlabel) {
485 }
else if (clabel < nseeds && cindex >= nboth) {
488 debugWshedMerge(wshed, one_new_watershed_label,
489 x,
y, clabel, cindex);
493 }
else if (cindex < nseeds && clabel >= nboth) {
494 debugWshedMerge(wshed, one_new_watershed_index,
495 x,
y, clabel, cindex);
499 }
else if (clabel < nseeds) {
502 debugWshedMerge(wshed, minima_absorbed_into_seeded_basin,
503 x,
y, clabel, cindex);
505 }
else if (cindex < nseeds) {
506 debugWshedMerge(wshed, minima_absorbed_into_seeded_basin,
507 x,
y, clabel, cindex);
510 debugWshedMerge(wshed, minima_absorbed_by_filler_or_another,
511 x,
y, clabel, cindex);
520 for (i = 0; i < nseeds; i++) {
566 PROCNAME(
"wshedSaveBasin");
569 L_ERROR(
"wshed not defined\n", procName);
609 l_int32 imin, imax, jmin, jmax, minx, miny, maxx, maxy;
610 l_int32 bw, bh, i, j, w, h,
x,
y;
612 l_uint32 label, bval, lval;
613 void **lines8, **linelab32, **linet1;
615 PIX *pixs, *pixt, *pixd;
618 PROCNAME(
"identifyWatershedBasin");
621 return ERROR_INT(
"&box not defined", procName, 1);
624 return ERROR_INT(
"&pixd not defined", procName, 1);
627 return ERROR_INT(
"wshed not defined", procName, 1);
642 minx = miny = 1000000;
646 pushNewPixel(lq,
x,
y, &minx, &maxx, &miny, &maxy);
657 popNewPixel(lq, &
x, &
y);
658 imin = L_MAX(0,
y - 1);
659 imax = L_MIN(h - 1,
y + 1);
660 jmin = L_MAX(0,
x - 1);
661 jmax = L_MIN(w - 1,
x + 1);
662 for (i = imin; i <= imax; i++) {
663 for (j = jmin; j <= jmax; j++) {
664 if (j ==
x && i ==
y)
continue;
666 if (label == MAX_LABEL_VALUE || lut[label] !=
index)
continue;
668 if (bval == 1)
continue;
670 if (lval >= level)
continue;
672 pushNewPixel(lq, j, i, &minx, &maxx, &miny, &maxy);
678 bw = maxx - minx + 1;
679 bh = maxy - miny + 1;
720 l_int32 i, n, size,
index;
725 PROCNAME(
"mergeLookup");
728 return ERROR_INT(
"wshed not defined", procName, 1);
730 if (sindex < 0 || sindex >= size)
731 return ERROR_INT(
"invalid sindex", procName, 1);
732 if (dindex < 0 || dindex >= size)
733 return ERROR_INT(
"invalid dindex", procName, 1);
737 links = wshed->
links;
739 if ((na = links[sindex]) != NULL) {
741 for (i = 0; i < n; i++) {
746 lut[sindex] = dindex;
754 numaJoin(links[dindex], links[sindex], 0, -1);
787 PROCNAME(
"wshedGetHeight");
790 return ERROR_INT(
"&height not defined", procName, 1);
793 return ERROR_INT(
"wshed not defined", procName, 1);
795 if (label < wshed->nseeds)
797 else if (label < wshed->nseeds + wshed->
nother)
800 return ERROR_INT(
"finished watershed; should not call", procName, 1);
802 *pheight =
val - minval;
833 PROCNAME(
"pushNewPixel");
836 L_ERROR(
"queue not defined\n", procName);
841 *pminx = L_MIN(*pminx,
x);
842 *pmaxx = L_MAX(*pmaxx,
x);
843 *pminy = L_MIN(*pminy,
y);
844 *pmaxy = L_MAX(*pmaxy,
y);
879 PROCNAME(
"popNewPixel");
882 L_ERROR(
"lqueue not defined\n", procName);
920 PROCNAME(
"pushWSPixel");
923 L_ERROR(
"heap not defined\n", procName);
927 L_ERROR(
"stack not defined\n", procName);
937 wsp->
val = (l_float32)
val;
972 PROCNAME(
"popWSPixel");
975 L_ERROR(
"lheap not defined\n", procName);
979 L_ERROR(
"stack not defined\n", procName);
982 if (!pval || !px || !py || !pindex) {
983 L_ERROR(
"data can't be returned\n", procName);
989 *pval = (l_int32)wsp->
val;
992 *pindex = wsp->
index;
998 debugPrintLUT(l_int32 *lut,
1006 for (i = 0; i < size; i++)
1013 debugWshedMerge(
L_WSHED *wshed,
1020 if (!wshed || (wshed->
debug == 0))
1044 PROCNAME(
"wshedBasins");
1047 return ERROR_INT(
"wshed not defined", procName, 1);
1066 l_int32 i, n, level, bx, by;
1071 PROCNAME(
"wshedRenderFill");
1074 return (
PIX *)ERROR_PTR(
"wshed not defined", procName, NULL);
1079 for (i = 0; i < n; i++) {
1103 PIX *pixg, *pixt, *pixc, *pixm, *pixd;
1106 PROCNAME(
"wshedRenderColors");
1109 return (
PIX *)ERROR_PTR(
"wshed not defined", procName, NULL);
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
PIX * pixConvertTo32(PIX *pixs)
pixConvertTo32()
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
PIX * pixGenerateFromPta(PTA *pta, l_int32 w, l_int32 h)
pixGenerateFromPta()
PIX * pixRemoveSeededComponents(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
pixRemoveSeededComponents()
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
PIXA * pixaCreate(l_int32 n)
pixaCreate()
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
l_int32 lstackGetCount(L_STACK *lstack)
lstackGetCount()
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()
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
void wshedDestroy(L_WSHED **pwshed)
wshedDestroy()
void ** pixGetLinePtrs(PIX *pix, l_int32 *psize)
pixGetLinePtrs()
NUMA * numaMakeConstant(l_float32 val, l_int32 size)
numaMakeConstant()
void lept_stderr(const char *fmt,...)
lept_stderr()
#define GET_DATA_FOUR_BYTES(pdata, n)
l_ok pixLocalExtrema(PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
pixLocalExtrema()
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
NUMA * numaCreate(l_int32 n)
numaCreate()
l_int32 ptaGetCount(PTA *pta)
ptaGetCount()
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
PIX * pixaDisplay(PIXA *pixa, l_int32 w, l_int32 h)
pixaDisplay()
#define GET_DATA_BIT(pdata, n)
PIX * pixClipRectangle(PIX *pixs, BOX *box, BOX **pboxc)
pixClipRectangle()
l_ok numaSetValue(NUMA *na, l_int32 index, l_float32 val)
numaSetValue()
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
l_ok pixPaintThroughMask(PIX *pixd, PIX *pixm, l_int32 x, l_int32 y, l_uint32 val)
pixPaintThroughMask()
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
l_ok lstackAdd(L_STACK *lstack, void *item)
lstackAdd()
l_ok pixSetAllArbitrary(PIX *pix, l_uint32 val)
pixSetAllArbitrary()
l_ok pixCombineMasked(PIX *pixd, PIX *pixs, PIX *pixm)
pixCombineMasked()
PIXA * pixaCopy(PIXA *pixa, l_int32 copyflag)
pixaCopy()
l_int32 * numaGetIArray(NUMA *na)
numaGetIArray()
PIX * pixaDisplayRandomCmap(PIXA *pixa, l_int32 w, l_int32 h)
pixaDisplayRandomCmap()
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
l_ok pixaAddPix(PIXA *pixa, PIX *pix, l_int32 copyflag)
pixaAddPix()
PIX * wshedRenderColors(L_WSHED *wshed)
wshedRenderColors()
void * lstackRemove(L_STACK *lstack)
lstackRemove()
l_int32 numaGetCount(NUMA *na)
numaGetCount()
l_ok pixSetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 val)
pixSetPixel()
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
L_STACK * lstackCreate(l_int32 n)
lstackCreate()
static l_int32 mergeLookup(L_WSHED *wshed, l_int32 sindex, l_int32 dindex)
mergeLookup()
#define GET_DATA_BYTE(pdata, n)
void * lheapRemove(L_HEAP *lh)
lheapRemove()
l_ok pixaGetBoxGeometry(PIXA *pixa, l_int32 index, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
pixaGetBoxGeometry()
l_ok wshedApply(L_WSHED *wshed)
wshedApply()
PIX * wshedRenderFill(L_WSHED *wshed)
wshedRenderFill()
static void wshedSaveBasin(L_WSHED *wshed, l_int32 index, l_int32 level)
wshedSaveBasin()
PIX * pixClone(PIX *pixs)
pixClone()
void pixDestroy(PIX **ppix)
pixDestroy()
NUMA * numaMakeSequence(l_float32 startval, l_float32 increment, l_int32 size)
numaMakeSequence()
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
void numaDestroy(NUMA **pna)
numaDestroy()
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
L_WSHED * wshedCreate(PIX *pixs, PIX *pixm, l_int32 mindepth, l_int32 debugflag)
wshedCreate()
l_ok numaJoin(NUMA *nad, NUMA *nas, l_int32 istart, l_int32 iend)
numaJoin()
#define SET_DATA_FOUR_BYTES(pdata, n, val)
static l_int32 identifyWatershedBasin(L_WSHED *wshed, l_int32 index, l_int32 level, BOX **pbox, PIX **ppixd)
identifyWatershedBasin()
l_ok wshedBasins(L_WSHED *wshed, PIXA **ppixa, NUMA **pnalevels)
wshedBasins()
PIX * pixaGetPix(PIXA *pixa, l_int32 index, l_int32 accesstype)
pixaGetPix()
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
l_ok pixSelectMinInConnComp(PIX *pixs, PIX *pixm, PTA **ppta, NUMA **pnav)
pixSelectMinInConnComp()
void ptaDestroy(PTA **ppta)
ptaDestroy()
NUMA * numaClone(NUMA *na)
numaClone()
l_ok ptaGetIPt(PTA *pta, l_int32 index, l_int32 *px, l_int32 *py)
ptaGetIPt()
static l_int32 wshedGetHeight(L_WSHED *wshed, l_int32 val, l_int32 label, l_int32 *pheight)
wshedGetHeight()
l_ok pixaAddBox(PIXA *pixa, BOX *box, l_int32 copyflag)
pixaAddBox()
void pixaDestroy(PIXA **ppixa)
pixaDestroy()
BOX * boxCreate(l_int32 x, l_int32 y, l_int32 w, l_int32 h)
boxCreate()
l_int32 pixaGetCount(PIXA *pixa)
pixaGetCount()
#define SET_DATA_BIT(pdata, n)