Leptonica  1.82.0
Image processing and image analysis suite
watershed.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
115 #ifdef HAVE_CONFIG_H
116 #include <config_auto.h>
117 #endif /* HAVE_CONFIG_H */
118 
119 #include "allheaders.h"
120 
121 #ifndef NO_CONSOLE_IO
122 #define DEBUG_WATERSHED 0
123 #endif /* ~NO_CONSOLE_IO */
124 
125 static const l_uint32 MAX_LABEL_VALUE = 0x7fffffff; /* largest l_int32 */
126 
129 {
130  l_int32 x;
131  l_int32 y;
132 };
133 typedef struct L_NewPixel L_NEWPIXEL;
134 
136 struct L_WSPixel
137 {
138  l_float32 val;
139  l_int32 x;
140  l_int32 y;
141  l_int32 index;
142 };
143 typedef struct L_WSPixel L_WSPIXEL;
144 
145 
146  /* Static functions for obtaining bitmap of watersheds */
147 static void wshedSaveBasin(L_WSHED *wshed, l_int32 index, l_int32 level);
148 
149 static l_int32 identifyWatershedBasin(L_WSHED *wshed,
150  l_int32 index, l_int32 level,
151  BOX **pbox, PIX **ppixd);
152 
153  /* Static function for merging lut and backlink arrays */
154 static l_int32 mergeLookup(L_WSHED *wshed, l_int32 sindex, l_int32 dindex);
155 
156  /* Static function for finding the height of the current pixel
157  above its seed or minima in the watershed. */
158 static l_int32 wshedGetHeight(L_WSHED *wshed, l_int32 val, l_int32 label,
159  l_int32 *pheight);
160 
161  /* Static accessors for NewPixel on a queue */
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);
166 
167  /* Static accessors for WSPixel on a heap */
168 static void pushWSPixel(L_HEAP *lh, L_STACK *stack, l_int32 val,
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);
172 
173  /* Static debug print output */
174 static void debugPrintLUT(l_int32 *lut, l_int32 size, l_int32 debug);
175 
176 static void debugWshedMerge(L_WSHED *wshed, char *descr, l_int32 x,
177  l_int32 y, l_int32 label, l_int32 index);
178 
179 
180 /*-----------------------------------------------------------------------*
181  * Top-level watershed *
182  *-----------------------------------------------------------------------*/
206 L_WSHED *
208  PIX *pixm,
209  l_int32 mindepth,
210  l_int32 debugflag)
211 {
212 l_int32 w, h;
213 L_WSHED *wshed;
214 
215  PROCNAME("wshedCreate");
216 
217  if (!pixs)
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);
221  if (!pixm)
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);
225  pixGetDimensions(pixs, &w, &h, NULL);
226  if (pixGetWidth(pixm) != w || pixGetHeight(pixm) != h)
227  return (L_WSHED *)ERROR_PTR("pixs/m sizes are unequal", procName, NULL);
228 
229  if ((wshed = (L_WSHED *)LEPT_CALLOC(1, sizeof(L_WSHED))) == NULL)
230  return (L_WSHED *)ERROR_PTR("wshed not made", procName, NULL);
231 
232  wshed->pixs = pixClone(pixs);
233  wshed->pixm = pixClone(pixm);
234  wshed->mindepth = L_MAX(1, mindepth);
235  wshed->pixlab = pixCreate(w, h, 32);
236  pixSetAllArbitrary(wshed->pixlab, MAX_LABEL_VALUE);
237  wshed->pixt = pixCreate(w, h, 1);
238  wshed->lines8 = pixGetLinePtrs(pixs, NULL);
239  wshed->linem1 = pixGetLinePtrs(pixm, NULL);
240  wshed->linelab32 = pixGetLinePtrs(wshed->pixlab, NULL);
241  wshed->linet1 = pixGetLinePtrs(wshed->pixt, NULL);
242  wshed->debug = debugflag;
243  return wshed;
244 }
245 
246 
253 void
255 {
256 l_int32 i;
257 L_WSHED *wshed;
258 
259  PROCNAME("wshedDestroy");
260 
261  if (pwshed == NULL) {
262  L_WARNING("ptr address is null!\n", procName);
263  return;
264  }
265 
266  if ((wshed = *pwshed) == NULL)
267  return;
268 
269  pixDestroy(&wshed->pixs);
270  pixDestroy(&wshed->pixm);
271  pixDestroy(&wshed->pixlab);
272  pixDestroy(&wshed->pixt);
273  if (wshed->lines8) LEPT_FREE(wshed->lines8);
274  if (wshed->linem1) LEPT_FREE(wshed->linem1);
275  if (wshed->linelab32) LEPT_FREE(wshed->linelab32);
276  if (wshed->linet1) LEPT_FREE(wshed->linet1);
277  pixaDestroy(&wshed->pixad);
278  ptaDestroy(&wshed->ptas);
279  numaDestroy(&wshed->nash);
280  numaDestroy(&wshed->nasi);
281  numaDestroy(&wshed->namh);
282  numaDestroy(&wshed->nalevels);
283  if (wshed->lut)
284  LEPT_FREE(wshed->lut);
285  if (wshed->links) {
286  for (i = 0; i < wshed->arraysize; i++)
287  numaDestroy(&wshed->links[i]);
288  LEPT_FREE(wshed->links);
289  }
290  LEPT_FREE(wshed);
291  *pwshed = NULL;
292 }
293 
294 
309 l_ok
311 {
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;
324 l_int32 *lut;
325 l_uint32 ulabel, uval;
326 void **lines8, **linelab32;
327 NUMA *nalut, *nalevels, *nash, *namh, *nasi;
328 NUMA **links;
329 L_HEAP *lh;
330 PIX *pixmin, *pixsd;
331 PIXA *pixad;
332 L_STACK *rstack;
333 PTA *ptas, *ptao;
334 
335  PROCNAME("wshedApply");
336 
337  if (!wshed)
338  return ERROR_INT("wshed not defined", procName, 1);
339 
340  /* ------------------------------------------------------------ *
341  * Initialize priority queue and pixlab with seeds and minima *
342  * ------------------------------------------------------------ */
343 
344  lh = lheapCreate(0, L_SORT_INCREASING); /* remove lowest values first */
345  rstack = lstackCreate(0); /* for reusing the WSPixels */
346  pixGetDimensions(wshed->pixs, &w, &h, NULL);
347  lines8 = wshed->lines8; /* wshed owns this */
348  linelab32 = wshed->linelab32; /* ditto */
349 
350  /* Identify seed (marker) pixels, 1 for each c.c. in pixm */
351  pixSelectMinInConnComp(wshed->pixs, wshed->pixm, &ptas, &nash);
352  pixsd = pixGenerateFromPta(ptas, w, h);
353  nseeds = ptaGetCount(ptas);
354  for (i = 0; i < nseeds; i++) {
355  ptaGetIPt(ptas, i, &x, &y);
356  uval = GET_DATA_BYTE(lines8[y], x);
357  pushWSPixel(lh, rstack, (l_int32)uval, x, y, i);
358  }
359  wshed->ptas = ptas;
360  nasi = numaMakeConstant(1, nseeds); /* indicator array */
361  wshed->nasi = nasi;
362  wshed->nash = nash;
363  wshed->nseeds = nseeds;
364 
365  /* Identify minima that are not seeds. Use these 4 steps:
366  * (1) Get the local minima, which can have components
367  * of arbitrary size. This will be a clipping mask.
368  * (2) Get the image of the actual seeds (pixsd)
369  * (3) Remove all elements of the clipping mask that have a seed.
370  * (4) Shrink each of the remaining elements of the minima mask
371  * to a single pixel. */
372  pixLocalExtrema(wshed->pixs, 200, 0, &pixmin, NULL);
373  pixRemoveSeededComponents(pixmin, pixsd, pixmin, 8, 2);
374  pixSelectMinInConnComp(wshed->pixs, pixmin, &ptao, &namh);
375  nother = ptaGetCount(ptao);
376  for (i = 0; i < nother; i++) {
377  ptaGetIPt(ptao, i, &x, &y);
378  uval = GET_DATA_BYTE(lines8[y], x);
379  pushWSPixel(lh, rstack, (l_int32)uval, x, y, nseeds + i);
380  }
381  wshed->namh = namh;
382 
383  /* ------------------------------------------------------------ *
384  * Initialize merging lookup tables *
385  * ------------------------------------------------------------ */
386 
387  /* nalut should always give the current after-merging index.
388  * links are effectively backpointers: they are numas associated with
389  * a dest index of all indices in nalut that point to that index. */
390  mindepth = wshed->mindepth;
391  nboth = nseeds + nother;
392  arraysize = 2 * nboth;
393  wshed->arraysize = arraysize;
394  nalut = numaMakeSequence(0, 1, arraysize);
395  lut = numaGetIArray(nalut);
396  wshed->lut = lut; /* wshed owns this */
397  links = (NUMA **)LEPT_CALLOC(arraysize, sizeof(NUMA *));
398  wshed->links = links; /* wshed owns this */
399  nindex = nseeds + nother; /* the next unused index value */
400 
401  /* ------------------------------------------------------------ *
402  * Fill the basins, using the priority queue *
403  * ------------------------------------------------------------ */
404 
405  pixad = pixaCreate(nseeds);
406  wshed->pixad = pixad; /* wshed owns this */
407  nalevels = numaCreate(nseeds);
408  wshed->nalevels = nalevels; /* wshed owns this */
409  L_INFO("nseeds = %d, nother = %d\n", procName, nseeds, nother);
410  while (lheapGetCount(lh) > 0) {
411  popWSPixel(lh, rstack, &val, &x, &y, &index);
412 /* lept_stderr("x = %d, y = %d, index = %d\n", x, y, index); */
413  ulabel = GET_DATA_FOUR_BYTES(linelab32[y], x);
414  if (ulabel == MAX_LABEL_VALUE)
415  clabel = ulabel;
416  else
417  clabel = lut[ulabel];
418  cindex = lut[index];
419  if (clabel == cindex) continue; /* have already seen this one */
420  if (clabel == MAX_LABEL_VALUE) { /* new one; assign index and try to
421  * propagate to all neighbors */
422  SET_DATA_FOUR_BYTES(linelab32[y], x, cindex);
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;
430  uval = GET_DATA_BYTE(lines8[i], j);
431  pushWSPixel(lh, rstack, (l_int32)uval, j, i, cindex);
432  }
433  }
434  } else { /* pixel is already labeled (differently); must resolve */
435 
436  /* If both indices are seeds, check if the min height is
437  * greater than mindepth. If so, we have two new watersheds;
438  * locate them and assign to both regions a new index
439  * for further waterfill. If not, absorb the shallower
440  * watershed into the deeper one and continue filling it. */
441  pixGetPixel(pixsd, x, y, &uval);
442  if (clabel < nseeds && cindex < nseeds) {
443  wshedGetHeight(wshed, val, clabel, &hlabel);
444  wshedGetHeight(wshed, val, cindex, &hindex);
445  hmin = L_MIN(hlabel, hindex);
446  hmax = L_MAX(hlabel, hindex);
447  if (hmin == hmax) {
448  hmin = hlabel;
449  hmax = hindex;
450  }
451  if (wshed->debug) {
452  lept_stderr("clabel,hlabel = %d,%d\n", clabel, hlabel);
453  lept_stderr("hmin = %d, hmax = %d\n", hmin, hmax);
454  lept_stderr("cindex,hindex = %d,%d\n", cindex, hindex);
455  if (hmin < mindepth)
456  lept_stderr("Too shallow!\n");
457  }
458 
459  if (hmin >= mindepth) {
460  debugWshedMerge(wshed, two_new_watersheds,
461  x, y, clabel, cindex);
462  wshedSaveBasin(wshed, cindex, val - 1);
463  wshedSaveBasin(wshed, clabel, val - 1);
464  numaSetValue(nasi, cindex, 0);
465  numaSetValue(nasi, clabel, 0);
466 
467  if (wshed->debug) lept_stderr("nindex = %d\n", nindex);
468  debugPrintLUT(lut, nindex, wshed->debug);
469  mergeLookup(wshed, clabel, nindex);
470  debugPrintLUT(lut, nindex, wshed->debug);
471  mergeLookup(wshed, cindex, nindex);
472  debugPrintLUT(lut, nindex, wshed->debug);
473  nindex++;
474  } else /* extraneous seed within seeded basin; absorb */ {
475  debugWshedMerge(wshed, seed_absorbed_into_seeded_basin,
476  x, y, clabel, cindex);
477  }
478  maxhindex = clabel; /* TODO: is this part of above 'else'? */
479  minhindex = cindex;
480  if (hindex > hlabel) {
481  maxhindex = cindex;
482  minhindex = clabel;
483  }
484  mergeLookup(wshed, minhindex, maxhindex);
485  } else if (clabel < nseeds && cindex >= nboth) {
486  /* If one index is a seed and the other is a merge of
487  * 2 watersheds, generate a single watershed. */
488  debugWshedMerge(wshed, one_new_watershed_label,
489  x, y, clabel, cindex);
490  wshedSaveBasin(wshed, clabel, val - 1);
491  numaSetValue(nasi, clabel, 0);
492  mergeLookup(wshed, clabel, cindex);
493  } else if (cindex < nseeds && clabel >= nboth) {
494  debugWshedMerge(wshed, one_new_watershed_index,
495  x, y, clabel, cindex);
496  wshedSaveBasin(wshed, cindex, val - 1);
497  numaSetValue(nasi, cindex, 0);
498  mergeLookup(wshed, cindex, clabel);
499  } else if (clabel < nseeds) { /* cindex from minima; absorb */
500  /* If one index is a seed and the other is from a minimum,
501  * merge the minimum wshed into the seed wshed. */
502  debugWshedMerge(wshed, minima_absorbed_into_seeded_basin,
503  x, y, clabel, cindex);
504  mergeLookup(wshed, cindex, clabel);
505  } else if (cindex < nseeds) { /* clabel from minima; absorb */
506  debugWshedMerge(wshed, minima_absorbed_into_seeded_basin,
507  x, y, clabel, cindex);
508  mergeLookup(wshed, clabel, cindex);
509  } else { /* If neither index is a seed, just merge */
510  debugWshedMerge(wshed, minima_absorbed_by_filler_or_another,
511  x, y, clabel, cindex);
512  mergeLookup(wshed, clabel, cindex);
513  }
514  }
515  }
516 
517 #if 0
518  /* Use the indicator array to save any watersheds that fill
519  * to the maximum value. This seems to screw things up! */
520  for (i = 0; i < nseeds; i++) {
521  numaGetIValue(nasi, i, &ival);
522  if (ival == 1) {
523  wshedSaveBasin(wshed, lut[i], val - 1);
524  numaSetValue(nasi, i, 0);
525  }
526  }
527 #endif
528 
529  numaDestroy(&nalut);
530  pixDestroy(&pixmin);
531  pixDestroy(&pixsd);
532  ptaDestroy(&ptao);
533  lheapDestroy(&lh, TRUE);
534  lstackDestroy(&rstack, TRUE);
535  return 0;
536 }
537 
538 
539 /*-----------------------------------------------------------------------*
540  * Helpers *
541  *-----------------------------------------------------------------------*/
558 static void
560  l_int32 index,
561  l_int32 level)
562 {
563 BOX *box;
564 PIX *pix;
565 
566  PROCNAME("wshedSaveBasin");
567 
568  if (!wshed) {
569  L_ERROR("wshed not defined\n", procName);
570  return;
571  }
572 
573  if (identifyWatershedBasin(wshed, index, level, &box, &pix) == 0) {
574  pixaAddPix(wshed->pixad, pix, L_INSERT);
575  pixaAddBox(wshed->pixad, box, L_INSERT);
576  numaAddNumber(wshed->nalevels, level - 1);
577  }
578 }
579 
580 
602 static l_int32
604  l_int32 index,
605  l_int32 level,
606  BOX **pbox,
607  PIX **ppixd)
608 {
609 l_int32 imin, imax, jmin, jmax, minx, miny, maxx, maxy;
610 l_int32 bw, bh, i, j, w, h, x, y;
611 l_int32 *lut;
612 l_uint32 label, bval, lval;
613 void **lines8, **linelab32, **linet1;
614 BOX *box;
615 PIX *pixs, *pixt, *pixd;
616 L_QUEUE *lq;
617 
618  PROCNAME("identifyWatershedBasin");
619 
620  if (!pbox)
621  return ERROR_INT("&box not defined", procName, 1);
622  *pbox = NULL;
623  if (!ppixd)
624  return ERROR_INT("&pixd not defined", procName, 1);
625  *ppixd = NULL;
626  if (!wshed)
627  return ERROR_INT("wshed not defined", procName, 1);
628 
629  /* Make a queue and an auxiliary stack */
630  lq = lqueueCreate(0);
631  lq->stack = lstackCreate(0);
632 
633  pixs = wshed->pixs;
634  pixt = wshed->pixt;
635  lines8 = wshed->lines8;
636  linelab32 = wshed->linelab32;
637  linet1 = wshed->linet1;
638  lut = wshed->lut;
639  pixGetDimensions(pixs, &w, &h, NULL);
640 
641  /* Prime the queue with the seed pixel for this watershed. */
642  minx = miny = 1000000;
643  maxx = maxy = 0;
644  ptaGetIPt(wshed->ptas, index, &x, &y);
645  pixSetPixel(pixt, x, y, 1);
646  pushNewPixel(lq, x, y, &minx, &maxx, &miny, &maxy);
647  if (wshed->debug) lept_stderr("prime: (x,y) = (%d, %d)\n", x, y);
648 
649  /* Each pixel in a spreading breadth-first search is inspected.
650  * It is accepted as part of this watershed, and pushed on
651  * the search queue, if:
652  * (1) It has a label value equal to %index
653  * (2) The pixel value is less than %level, the overflow
654  * height at which the two basins join.
655  * (3) It has not yet been seen in this search. */
656  while (lqueueGetCount(lq) > 0) {
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; /* parent */
665  label = GET_DATA_FOUR_BYTES(linelab32[i], j);
666  if (label == MAX_LABEL_VALUE || lut[label] != index) continue;
667  bval = GET_DATA_BIT(linet1[i], j);
668  if (bval == 1) continue; /* already seen */
669  lval = GET_DATA_BYTE(lines8[i], j);
670  if (lval >= level) continue; /* too high */
671  SET_DATA_BIT(linet1[i], j);
672  pushNewPixel(lq, j, i, &minx, &maxx, &miny, &maxy);
673  }
674  }
675  }
676 
677  /* Extract the box and pix, and clear pixt */
678  bw = maxx - minx + 1;
679  bh = maxy - miny + 1;
680  box = boxCreate(minx, miny, bw, bh);
681  pixd = pixClipRectangle(pixt, box, NULL);
682  pixRasterop(pixt, minx, miny, bw, bh, PIX_SRC ^ PIX_DST, pixd, 0, 0);
683  *pbox = box;
684  *ppixd = pixd;
685 
686  lqueueDestroy(&lq, 1);
687  return 0;
688 }
689 
690 
715 static l_int32
717  l_int32 sindex,
718  l_int32 dindex)
719 {
720 l_int32 i, n, size, index;
721 l_int32 *lut;
722 NUMA *na;
723 NUMA **links;
724 
725  PROCNAME("mergeLookup");
726 
727  if (!wshed)
728  return ERROR_INT("wshed not defined", procName, 1);
729  size = wshed->arraysize;
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);
734 
735  /* Redirect links in the lut */
736  n = 0;
737  links = wshed->links;
738  lut = wshed->lut;
739  if ((na = links[sindex]) != NULL) {
740  n = numaGetCount(na);
741  for (i = 0; i < n; i++) {
742  numaGetIValue(na, i, &index);
743  lut[index] = dindex;
744  }
745  }
746  lut[sindex] = dindex;
747 
748  /* Shift the backlink arrays from sindex to dindex.
749  * sindex should have no backlinks because all entries in the
750  * lut that were previously pointing to it have been redirected
751  * to dindex. */
752  if (!links[dindex])
753  links[dindex] = numaCreate(n);
754  numaJoin(links[dindex], links[sindex], 0, -1);
755  numaAddNumber(links[dindex], sindex);
756  numaDestroy(&links[sindex]);
757 
758  return 0;
759 }
760 
761 
779 static l_int32
781  l_int32 val,
782  l_int32 label,
783  l_int32 *pheight)
784 {
785 l_int32 minval;
786 
787  PROCNAME("wshedGetHeight");
788 
789  if (!pheight)
790  return ERROR_INT("&height not defined", procName, 1);
791  *pheight = 0;
792  if (!wshed)
793  return ERROR_INT("wshed not defined", procName, 1);
794 
795  if (label < wshed->nseeds)
796  numaGetIValue(wshed->nash, label, &minval);
797  else if (label < wshed->nseeds + wshed->nother)
798  numaGetIValue(wshed->namh, label, &minval);
799  else
800  return ERROR_INT("finished watershed; should not call", procName, 1);
801 
802  *pheight = val - minval;
803  return 0;
804 }
805 
806 
807 /*
808  * \brief pushNewPixel()
809  *
810  * \param[in] lqueue
811  * \param[in] x, y pixel coordinates
812  * \param[out] pminx, pmaxx, pminy, pmaxy bounding box update
813  * \return void
814  *
815  * <pre>
816  * Notes:
817  * (1) This is a wrapper for adding a NewPixel to a queue, which
818  * updates the bounding box for all pixels on that queue and
819  * uses the storage stack to retrieve a NewPixel.
820  * </pre>
821  */
822 static void
823 pushNewPixel(L_QUEUE *lq,
824  l_int32 x,
825  l_int32 y,
826  l_int32 *pminx,
827  l_int32 *pmaxx,
828  l_int32 *pminy,
829  l_int32 *pmaxy)
830 {
831 L_NEWPIXEL *np;
832 
833  PROCNAME("pushNewPixel");
834 
835  if (!lq) {
836  L_ERROR("queue not defined\n", procName);
837  return;
838  }
839 
840  /* Adjust bounding box */
841  *pminx = L_MIN(*pminx, x);
842  *pmaxx = L_MAX(*pmaxx, x);
843  *pminy = L_MIN(*pminy, y);
844  *pmaxy = L_MAX(*pmaxy, y);
845 
846  /* Get a newpixel to use */
847  if (lstackGetCount(lq->stack) > 0)
848  np = (L_NEWPIXEL *)lstackRemove(lq->stack);
849  else
850  np = (L_NEWPIXEL *)LEPT_CALLOC(1, sizeof(L_NEWPIXEL));
851 
852  np->x = x;
853  np->y = y;
854  lqueueAdd(lq, np);
855 }
856 
857 
858 /*
859  * \brief popNewPixel()
860  *
861  * \param[in] lqueue
862  * \param[out] px, py pixel coordinates
863  * \return void
864  *
865  * <pre>
866  * Notes:
867  * (1) This is a wrapper for removing a NewPixel from a queue,
868  * which returns the pixel coordinates and saves the NewPixel
869  * on the storage stack.
870  * </pre>
871  */
872 static void
873 popNewPixel(L_QUEUE *lq,
874  l_int32 *px,
875  l_int32 *py)
876 {
877 L_NEWPIXEL *np;
878 
879  PROCNAME("popNewPixel");
880 
881  if (!lq) {
882  L_ERROR("lqueue not defined\n", procName);
883  return;
884  }
885 
886  if ((np = (L_NEWPIXEL *)lqueueRemove(lq)) == NULL)
887  return;
888  *px = np->x;
889  *py = np->y;
890  lstackAdd(lq->stack, np); /* save for re-use */
891 }
892 
893 
894 /*
895  * \brief pushWSPixel()
896  *
897  * \param[in] lh priority queue
898  * \param[in] stack of reusable WSPixels
899  * \param[in] val pixel value: used for ordering the heap
900  * \param[in] x, y pixel coordinates
901  * \param[in] index label for set to which pixel belongs
902  * \return void
903  *
904  * <pre>
905  * Notes:
906  * (1) This is a wrapper for adding a WSPixel to a heap. It
907  * uses the storage stack to retrieve a WSPixel.
908  * </pre>
909  */
910 static void
911 pushWSPixel(L_HEAP *lh,
912  L_STACK *stack,
913  l_int32 val,
914  l_int32 x,
915  l_int32 y,
916  l_int32 index)
917 {
918 L_WSPIXEL *wsp;
919 
920  PROCNAME("pushWSPixel");
921 
922  if (!lh) {
923  L_ERROR("heap not defined\n", procName);
924  return;
925  }
926  if (!stack) {
927  L_ERROR("stack not defined\n", procName);
928  return;
929  }
930 
931  /* Get a wspixel to use */
932  if (lstackGetCount(stack) > 0)
933  wsp = (L_WSPIXEL *)lstackRemove(stack);
934  else
935  wsp = (L_WSPIXEL *)LEPT_CALLOC(1, sizeof(L_WSPIXEL));
936 
937  wsp->val = (l_float32)val;
938  wsp->x = x;
939  wsp->y = y;
940  wsp->index = index;
941  lheapAdd(lh, wsp);
942 }
943 
944 
945 /*
946  * \brief popWSPixel()
947  *
948  * \param[in] lh priority queue
949  * \param[in] stack of reusable WSPixels
950  * \param[out] pval pixel value
951  * \param[out] px, py pixel coordinates
952  * \param[out] pindex label for set to which pixel belongs
953  * \return void
954  *
955  * <pre>
956  * Notes:
957  * (1) This is a wrapper for removing a WSPixel from a heap,
958  * which returns the WSPixel data and saves the WSPixel
959  * on the storage stack.
960  * </pre>
961  */
962 static void
963 popWSPixel(L_HEAP *lh,
964  L_STACK *stack,
965  l_int32 *pval,
966  l_int32 *px,
967  l_int32 *py,
968  l_int32 *pindex)
969 {
970 L_WSPIXEL *wsp;
971 
972  PROCNAME("popWSPixel");
973 
974  if (!lh) {
975  L_ERROR("lheap not defined\n", procName);
976  return;
977  }
978  if (!stack) {
979  L_ERROR("stack not defined\n", procName);
980  return;
981  }
982  if (!pval || !px || !py || !pindex) {
983  L_ERROR("data can't be returned\n", procName);
984  return;
985  }
986 
987  if ((wsp = (L_WSPIXEL *)lheapRemove(lh)) == NULL)
988  return;
989  *pval = (l_int32)wsp->val;
990  *px = wsp->x;
991  *py = wsp->y;
992  *pindex = wsp->index;
993  lstackAdd(stack, wsp); /* save for re-use */
994 }
995 
996 
997 static void
998 debugPrintLUT(l_int32 *lut,
999  l_int32 size,
1000  l_int32 debug)
1001 {
1002 l_int32 i;
1003 
1004  if (!debug) return;
1005  lept_stderr("lut: ");
1006  for (i = 0; i < size; i++)
1007  lept_stderr( "%d ", lut[i]);
1008  lept_stderr("\n");
1009 }
1010 
1011 
1012 static void
1013 debugWshedMerge(L_WSHED *wshed,
1014  char *descr,
1015  l_int32 x,
1016  l_int32 y,
1017  l_int32 label,
1018  l_int32 index)
1019 {
1020  if (!wshed || (wshed->debug == 0))
1021  return;
1022  lept_stderr("%s:\n", descr);
1023  lept_stderr(" (x, y) = (%d, %d)\n", x, y);
1024  lept_stderr(" clabel = %d, cindex = %d\n", label, index);
1025 }
1026 
1027 
1028 /*-----------------------------------------------------------------------*
1029  * Output *
1030  *-----------------------------------------------------------------------*/
1039 l_ok
1041  PIXA **ppixa,
1042  NUMA **pnalevels)
1043 {
1044  PROCNAME("wshedBasins");
1045 
1046  if (!wshed)
1047  return ERROR_INT("wshed not defined", procName, 1);
1048 
1049  if (ppixa)
1050  *ppixa = pixaCopy(wshed->pixad, L_CLONE);
1051  if (pnalevels)
1052  *pnalevels = numaClone(wshed->nalevels);
1053  return 0;
1054 }
1055 
1056 
1063 PIX *
1065 {
1066 l_int32 i, n, level, bx, by;
1067 NUMA *na;
1068 PIX *pix, *pixd;
1069 PIXA *pixa;
1070 
1071  PROCNAME("wshedRenderFill");
1072 
1073  if (!wshed)
1074  return (PIX *)ERROR_PTR("wshed not defined", procName, NULL);
1075 
1076  wshedBasins(wshed, &pixa, &na);
1077  pixd = pixCopy(NULL, wshed->pixs);
1078  n = pixaGetCount(pixa);
1079  for (i = 0; i < n; i++) {
1080  pix = pixaGetPix(pixa, i, L_CLONE);
1081  pixaGetBoxGeometry(pixa, i, &bx, &by, NULL, NULL);
1082  numaGetIValue(na, i, &level);
1083  pixPaintThroughMask(pixd, pix, bx, by, level);
1084  pixDestroy(&pix);
1085  }
1086 
1087  pixaDestroy(&pixa);
1088  numaDestroy(&na);
1089  return pixd;
1090 }
1091 
1092 
1099 PIX *
1101 {
1102 l_int32 w, h;
1103 PIX *pixg, *pixt, *pixc, *pixm, *pixd;
1104 PIXA *pixa;
1105 
1106  PROCNAME("wshedRenderColors");
1107 
1108  if (!wshed)
1109  return (PIX *)ERROR_PTR("wshed not defined", procName, NULL);
1110 
1111  wshedBasins(wshed, &pixa, NULL);
1112  pixg = pixCopy(NULL, wshed->pixs);
1113  pixGetDimensions(wshed->pixs, &w, &h, NULL);
1114  pixd = pixConvertTo32(pixg);
1115  pixt = pixaDisplayRandomCmap(pixa, w, h);
1116  pixc = pixConvertTo32(pixt);
1117  pixm = pixaDisplay(pixa, w, h);
1118  pixCombineMasked(pixd, pixc, pixm);
1119 
1120  pixDestroy(&pixg);
1121  pixDestroy(&pixt);
1122  pixDestroy(&pixc);
1123  pixDestroy(&pixm);
1124  pixaDestroy(&pixa);
1125  return pixd;
1126 }
void ** lines8
Definition: watershed.h:45
l_int32 y
Definition: watershed.c:131
l_int32 * lut
Definition: watershed.h:57
l_int32 debug
Definition: watershed.h:60
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
PIX * pixConvertTo32(PIX *pixs)
pixConvertTo32()
Definition: pixconv.c:3332
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
Definition: stack.c:124
PIX * pixGenerateFromPta(PTA *pta, l_int32 w, l_int32 h)
pixGenerateFromPta()
Definition: ptafunc1.c:2023
struct Numa * nasi
Definition: watershed.h:51
PIX * pixRemoveSeededComponents(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
pixRemoveSeededComponents()
Definition: seedfill.c:3431
l_int32 nother
Definition: watershed.h:56
Definition: pix.h:713
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
PIXA * pixaCreate(l_int32 n)
pixaCreate()
Definition: pixabasic.c:167
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
l_int32 lstackGetCount(L_STACK *lstack)
lstackGetCount()
Definition: stack.c:252
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()
Definition: rop.c:204
struct Pix * pixt
Definition: watershed.h:44
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
void wshedDestroy(L_WSHED **pwshed)
wshedDestroy()
Definition: watershed.c:254
void ** pixGetLinePtrs(PIX *pix, l_int32 *psize)
pixGetLinePtrs()
Definition: pix1.c:1949
NUMA * numaMakeConstant(l_float32 val, l_int32 size)
numaMakeConstant()
Definition: numafunc1.c:851
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306
void ** linem1
Definition: watershed.h:46
#define GET_DATA_FOUR_BYTES(pdata, n)
Definition: arrayaccess.h:231
l_ok pixLocalExtrema(PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
pixLocalExtrema()
Definition: seedfill.c:3019
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
struct L_Stack * stack
Definition: queue.h:71
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
l_int32 ptaGetCount(PTA *pta)
ptaGetCount()
Definition: ptabasic.c:527
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:154
l_int32 x
Definition: watershed.c:139
PIX * pixaDisplay(PIXA *pixa, l_int32 w, l_int32 h)
pixaDisplay()
Definition: pixafunc2.c:191
struct Numa * namh
Definition: watershed.h:53
l_int32 index
Definition: watershed.c:141
#define GET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:123
struct Numa * nalevels
Definition: watershed.h:54
PIX * pixClipRectangle(PIX *pixs, BOX *box, BOX **pboxc)
pixClipRectangle()
Definition: pix5.c:1026
struct Pix * pixm
Definition: watershed.h:41
l_ok numaSetValue(NUMA *na, l_int32 index, l_float32 val)
numaSetValue()
Definition: numabasic.c:786
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:283
l_ok pixPaintThroughMask(PIX *pixd, PIX *pixm, l_int32 x, l_int32 y, l_uint32 val)
pixPaintThroughMask()
Definition: pix3.c:626
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:257
l_ok lstackAdd(L_STACK *lstack, void *item)
lstackAdd()
Definition: stack.c:170
l_ok pixSetAllArbitrary(PIX *pix, l_uint32 val)
pixSetAllArbitrary()
Definition: pix2.c:951
struct Pta * ptas
Definition: watershed.h:50
l_ok pixCombineMasked(PIX *pixd, PIX *pixs, PIX *pixm)
pixCombineMasked()
Definition: pix3.c:382
PIXA * pixaCopy(PIXA *pixa, l_int32 copyflag)
pixaCopy()
Definition: pixabasic.c:453
l_int32 * numaGetIArray(NUMA *na)
numaGetIArray()
Definition: numabasic.c:847
struct Pix * pixlab
Definition: watershed.h:43
PIX * pixaDisplayRandomCmap(PIXA *pixa, l_int32 w, l_int32 h)
pixaDisplayRandomCmap()
Definition: pixafunc2.c:269
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:754
l_ok pixaAddPix(PIXA *pixa, PIX *pix, l_int32 copyflag)
pixaAddPix()
Definition: pixabasic.c:506
Definition: array.h:70
PIX * wshedRenderColors(L_WSHED *wshed)
wshedRenderColors()
Definition: watershed.c:1100
void * lstackRemove(L_STACK *lstack)
lstackRemove()
Definition: stack.c:202
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:658
l_int32 mindepth
Definition: watershed.h:42
l_ok pixSetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 val)
pixSetPixel()
Definition: pix2.c:263
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:188
Definition: queue.h:64
L_STACK * lstackCreate(l_int32 n)
lstackCreate()
Definition: stack.c:82
void ** linet1
Definition: watershed.h:48
void ** linelab32
Definition: watershed.h:47
struct Numa ** links
Definition: watershed.h:58
static l_int32 mergeLookup(L_WSHED *wshed, l_int32 sindex, l_int32 dindex)
mergeLookup()
Definition: watershed.c:716
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
l_ok pixaGetBoxGeometry(PIXA *pixa, l_int32 index, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
pixaGetBoxGeometry()
Definition: pixabasic.c:854
l_ok wshedApply(L_WSHED *wshed)
wshedApply()
Definition: watershed.c:310
PIX * wshedRenderFill(L_WSHED *wshed)
wshedRenderFill()
Definition: watershed.c:1064
static void wshedSaveBasin(L_WSHED *wshed, l_int32 index, l_int32 level)
wshedSaveBasin()
Definition: watershed.c:559
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:593
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
NUMA * numaMakeSequence(l_float32 startval, l_float32 increment, l_int32 size)
numaMakeSequence()
Definition: numafunc1.c:821
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:286
l_int32 arraysize
Definition: watershed.h:59
struct Pix * pixs
Definition: watershed.h:40
Definition: pix.h:711
l_int32 nseeds
Definition: watershed.h:55
Definition: heap.h:77
Definition: pix.h:455
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
Definition: pix2.c:190
struct Pixa * pixad
Definition: watershed.h:49
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
L_WSHED * wshedCreate(PIX *pixs, PIX *pixm, l_int32 mindepth, l_int32 debugflag)
wshedCreate()
Definition: watershed.c:207
l_ok numaJoin(NUMA *nad, NUMA *nas, l_int32 istart, l_int32 iend)
numaJoin()
Definition: numafunc1.c:3640
l_int32 x
Definition: watershed.c:130
#define SET_DATA_FOUR_BYTES(pdata, n, val)
Definition: arrayaccess.h:235
static l_int32 identifyWatershedBasin(L_WSHED *wshed, l_int32 index, l_int32 level, BOX **pbox, PIX **ppixd)
identifyWatershedBasin()
Definition: watershed.c:603
l_ok wshedBasins(L_WSHED *wshed, PIXA **ppixa, NUMA **pnalevels)
wshedBasins()
Definition: watershed.c:1040
PIX * pixaGetPix(PIXA *pixa, l_int32 index, l_int32 accesstype)
pixaGetPix()
Definition: pixabasic.c:691
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:134
Definition: pix.h:138
l_ok pixSelectMinInConnComp(PIX *pixs, PIX *pixm, PTA **ppta, NUMA **pnav)
pixSelectMinInConnComp()
Definition: seedfill.c:3318
void ptaDestroy(PTA **ppta)
ptaDestroy()
Definition: ptabasic.c:195
#define PIX_SRC
Definition: pix.h:330
NUMA * numaClone(NUMA *na)
numaClone()
Definition: numabasic.c:428
l_ok ptaGetIPt(PTA *pta, l_int32 index, l_int32 *px, l_int32 *py)
ptaGetIPt()
Definition: ptabasic.c:578
static l_int32 wshedGetHeight(L_WSHED *wshed, l_int32 val, l_int32 label, l_int32 *pheight)
wshedGetHeight()
Definition: watershed.c:780
struct Numa * nash
Definition: watershed.h:52
l_float32 val
Definition: watershed.c:138
l_ok pixaAddBox(PIXA *pixa, BOX *box, l_int32 copyflag)
pixaAddBox()
Definition: pixabasic.c:555
l_int32 y
Definition: watershed.c:140
Definition: pix.h:480
void pixaDestroy(PIXA **ppixa)
pixaDestroy()
Definition: pixabasic.c:412
BOX * boxCreate(l_int32 x, l_int32 y, l_int32 w, l_int32 h)
boxCreate()
Definition: boxbasic.c:172
l_int32 pixaGetCount(PIXA *pixa)
pixaGetCount()
Definition: pixabasic.c:650
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
Definition: stack.h:59
Definition: pix.h:516
#define PIX_DST
Definition: pix.h:331