Leptonica  1.83.1
Image processing and image analysis suite
conncomp.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 
91 #ifdef HAVE_CONFIG_H
92 #include <config_auto.h>
93 #endif /* HAVE_CONFIG_H */
94 
95 #include "allheaders.h"
96 #include "pix_internal.h"
97 
104 struct FillSeg
105 {
106  l_int32 xleft;
107  l_int32 xright;
108  l_int32 y;
109  l_int32 dy;
110 };
111 typedef struct FillSeg FILLSEG;
112 
113 static l_int32 nextOnPixelInRasterLow(l_uint32 *data, l_int32 w, l_int32 h,
114  l_int32 wpl, l_int32 xstart,
115  l_int32 ystart, l_int32 *px, l_int32 *py);
116 
117  /* Static accessors for FillSegs on a stack */
118 static void pushFillsegBB(L_STACK *stack, l_int32 xleft, l_int32 xright,
119  l_int32 y, l_int32 dy, l_int32 ymax,
120  l_int32 *pminx, l_int32 *pmaxx,
121  l_int32 *pminy, l_int32 *pmaxy);
122 static void pushFillseg(L_STACK *stack, l_int32 xleft, l_int32 xright,
123  l_int32 y, l_int32 dy, l_int32 ymax);
124 static void popFillseg(L_STACK *stack, l_int32 *pxleft, l_int32 *pxright,
125  l_int32 *py, l_int32 *pdy);
126 
127 
128 #ifndef NO_CONSOLE_IO
129 #define DEBUG 0
130 #endif /* ~NO_CONSOLE_IO */
131 
132 
133 /*-----------------------------------------------------------------------*
134  * Bounding boxes of 4 Connected Components *
135  *-----------------------------------------------------------------------*/
151 BOXA *
153  PIXA **ppixa,
154  l_int32 connectivity)
155 {
156 
157  if (ppixa) *ppixa = NULL;
158  if (!pixs || pixGetDepth(pixs) != 1)
159  return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
160  if (connectivity != 4 && connectivity != 8)
161  return (BOXA *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
162 
163  if (!ppixa)
164  return pixConnCompBB(pixs, connectivity);
165  else
166  return pixConnCompPixa(pixs, ppixa, connectivity);
167 }
168 
169 
193 BOXA *
195  PIXA **ppixa,
196  l_int32 connectivity)
197 {
198 l_int32 h, iszero;
199 l_int32 x, y, xstart, ystart;
200 PIX *pix1, *pix2, *pix3, *pix4;
201 PIXA *pixa;
202 BOX *box;
203 BOXA *boxa;
204 L_STACK *stack, *auxstack;
205 
206  if (!ppixa)
207  return (BOXA *)ERROR_PTR("&pixa not defined", __func__, NULL);
208  *ppixa = NULL;
209  if (!pixs || pixGetDepth(pixs) != 1)
210  return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
211  if (connectivity != 4 && connectivity != 8)
212  return (BOXA *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
213 
214  pix1 = pix2 = pix3 = pix4 = NULL;
215  stack = NULL;
216  pixa = pixaCreate(0);
217  boxa = NULL;
218  *ppixa = pixa;
219  pixZero(pixs, &iszero);
220  if (iszero)
221  return boxaCreate(1); /* return empty boxa and empty pixa */
222 
223  pixSetPadBits(pixs, 0);
224  pix1 = pixCopy(NULL, pixs);
225  pix2 = pixCopy(NULL, pixs);
226  if (!pix1 || !pix2) {
227  L_ERROR("pix1 or pix2 not made\n", __func__);
228  pixaDestroy(ppixa);
229  goto cleanup;
230  }
231 
232  h = pixGetHeight(pixs);
233  if ((stack = lstackCreate(h)) == NULL) {
234  L_ERROR("stack not made\n", __func__);
235  pixaDestroy(ppixa);
236  goto cleanup;
237  }
238  auxstack = lstackCreate(0);
239  stack->auxstack = auxstack;
240  boxa = boxaCreate(0);
241 
242  xstart = 0;
243  ystart = 0;
244  while (1) {
245  if (!nextOnPixelInRaster(pix1, xstart, ystart, &x, &y))
246  break;
247 
248  if ((box = pixSeedfillBB(pix1, stack, x, y, connectivity)) == NULL) {
249  boxaDestroy(&boxa);
250  pixaDestroy(ppixa);
251  L_ERROR("box not made\n", __func__);
252  goto cleanup;
253  }
254  boxaAddBox(boxa, box, L_INSERT);
255 
256  /* Save the c.c. and remove from pix2 as well */
257  pix3 = pixClipRectangle(pix1, box, NULL);
258  pix4 = pixClipRectangle(pix2, box, NULL);
259  pixXor(pix3, pix3, pix4);
260  pixRasterop(pix2, box->x, box->y, box->w, box->h, PIX_SRC ^ PIX_DST,
261  pix3, 0, 0);
262  pixaAddPix(pixa, pix3, L_INSERT);
263  pixDestroy(&pix4);
264 
265  xstart = x;
266  ystart = y;
267  }
268 
269 #if DEBUG
270  pixCountPixels(pix1, &iszero, NULL);
271  lept_stderr("Number of remaining pixels = %d\n", iszero);
272  lept_mkdir("lept/cc");
273  pixWriteDebug("/tmp/lept/cc/remain.png", pix1, IFF_PNG);
274 #endif /* DEBUG */
275 
276  /* Remove old boxa of pixa and replace with a copy */
277  boxaDestroy(&pixa->boxa);
278  pixa->boxa = boxaCopy(boxa, L_COPY);
279  *ppixa = pixa;
280 
281  /* Cleanup, freeing the fillsegs on each stack */
282 cleanup:
283  lstackDestroy(&stack, TRUE);
284  pixDestroy(&pix1);
285  pixDestroy(&pix2);
286  return boxa;
287 }
288 
289 
306 BOXA *
308  l_int32 connectivity)
309 {
310 l_int32 h, iszero;
311 l_int32 x, y, xstart, ystart;
312 PIX *pix1;
313 BOX *box;
314 BOXA *boxa;
315 L_STACK *stack, *auxstack;
316 
317  if (!pixs || pixGetDepth(pixs) != 1)
318  return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
319  if (connectivity != 4 && connectivity != 8)
320  return (BOXA *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
321 
322  boxa = NULL;
323  pix1 = NULL;
324  stack = NULL;
325  pixZero(pixs, &iszero);
326  if (iszero)
327  return boxaCreate(1); /* return empty boxa */
328 
329  pixSetPadBits(pixs, 0);
330  if ((pix1 = pixCopy(NULL, pixs)) == NULL)
331  return (BOXA *)ERROR_PTR("pix1 not made", __func__, NULL);
332 
333  h = pixGetHeight(pixs);
334  if ((stack = lstackCreate(h)) == NULL) {
335  L_ERROR("stack not made\n", __func__);
336  goto cleanup;
337  }
338  auxstack = lstackCreate(0);
339  stack->auxstack = auxstack;
340  boxa = boxaCreate(0);
341 
342  xstart = 0;
343  ystart = 0;
344  while (1) {
345  if (!nextOnPixelInRaster(pix1, xstart, ystart, &x, &y))
346  break;
347 
348  if ((box = pixSeedfillBB(pix1, stack, x, y, connectivity)) == NULL) {
349  L_ERROR("box not made\n", __func__);
350  boxaDestroy(&boxa);
351  goto cleanup;
352  }
353  boxaAddBox(boxa, box, L_INSERT);
354 
355  xstart = x;
356  ystart = y;
357  }
358 
359 #if DEBUG
360  pixCountPixels(pix1, &iszero, NULL);
361  lept_stderr("Number of remaining pixels = %d\n", iszero);
362  lept_mkdir("lept/cc");
363  pixWriteDebug("/tmp/lept/cc/remain.png", pix1, IFF_PNG);
364 #endif /* DEBUG */
365 
366  /* Cleanup, freeing the fillsegs on each stack */
367 cleanup:
368  lstackDestroy(&stack, TRUE);
369  pixDestroy(&pix1);
370  return boxa;
371 }
372 
373 
388 l_ok
390  l_int32 connectivity,
391  l_int32 *pcount)
392 {
393 l_int32 h, iszero;
394 l_int32 x, y, xstart, ystart;
395 PIX *pix1;
396 L_STACK *stack, *auxstack;
397 
398  if (!pcount)
399  return ERROR_INT("&count not defined", __func__, 1);
400  *pcount = 0; /* initialize the count to 0 */
401  if (!pixs || pixGetDepth(pixs) != 1)
402  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
403  if (connectivity != 4 && connectivity != 8)
404  return ERROR_INT("connectivity not 4 or 8", __func__, 1);
405 
406  stack = NULL;
407  pixZero(pixs, &iszero);
408  if (iszero)
409  return 0;
410 
411  pixSetPadBits(pixs, 0);
412  if ((pix1 = pixCopy(NULL, pixs)) == NULL)
413  return ERROR_INT("pix1 not made", __func__, 1);
414  h = pixGetHeight(pixs);
415  if ((stack = lstackCreate(h)) == NULL) {
416  pixDestroy(&pix1);
417  return ERROR_INT("stack not made\n", __func__, 1);
418  }
419  auxstack = lstackCreate(0);
420  stack->auxstack = auxstack;
421 
422  xstart = 0;
423  ystart = 0;
424  while (1) {
425  if (!nextOnPixelInRaster(pix1, xstart, ystart, &x, &y))
426  break;
427 
428  pixSeedfill(pix1, stack, x, y, connectivity);
429  (*pcount)++;
430  xstart = x;
431  ystart = y;
432  }
433 
434  /* Cleanup, freeing the fillsegs on each stack */
435  lstackDestroy(&stack, TRUE);
436  pixDestroy(&pix1);
437  return 0;
438 }
439 
440 
449 l_int32
451  l_int32 xstart,
452  l_int32 ystart,
453  l_int32 *px,
454  l_int32 *py)
455 {
456 l_int32 w, h, d, wpl;
457 l_uint32 *data;
458 
459  if (!pixs)
460  return ERROR_INT("pixs not defined", __func__, 0);
461  pixGetDimensions(pixs, &w, &h, &d);
462  if (d != 1)
463  return ERROR_INT("pixs not 1 bpp", __func__, 0);
464 
465  wpl = pixGetWpl(pixs);
466  data = pixGetData(pixs);
467  return nextOnPixelInRasterLow(data, w, h, wpl, xstart, ystart, px, py);
468 }
469 
470 
481 static l_int32
482 nextOnPixelInRasterLow(l_uint32 *data,
483  l_int32 w,
484  l_int32 h,
485  l_int32 wpl,
486  l_int32 xstart,
487  l_int32 ystart,
488  l_int32 *px,
489  l_int32 *py)
490 {
491 l_int32 i, x, y, xend, startword;
492 l_uint32 *line, *pword;
493 
494  /* Look at the first word */
495  line = data + ystart * wpl;
496  pword = line + (xstart / 32);
497  if (*pword) {
498  xend = xstart - (xstart % 32) + 31;
499  for (x = xstart; x <= xend && x < w; x++) {
500  if (GET_DATA_BIT(line, x)) {
501  *px = x;
502  *py = ystart;
503  return 1;
504  }
505  }
506  }
507 
508  /* Continue with the rest of the line */
509  startword = (xstart / 32) + 1;
510  x = 32 * startword;
511  for (pword = line + startword; x < w; pword++, x += 32) {
512  if (*pword) {
513  for (i = 0; i < 32 && x < w; i++, x++) {
514  if (GET_DATA_BIT(line, x)) {
515  *px = x;
516  *py = ystart;
517  return 1;
518  }
519  }
520  }
521  }
522 
523  /* Continue with following lines */
524  for (y = ystart + 1; y < h; y++) {
525  line = data + y * wpl;
526  for (pword = line, x = 0; x < w; pword++, x += 32) {
527  if (*pword) {
528  for (i = 0; i < 32 && x < w; i++, x++) {
529  if (GET_DATA_BIT(line, x)) {
530  *px = x;
531  *py = y;
532  return 1;
533  }
534  }
535  }
536  }
537  }
538 
539  return 0;
540 }
541 
542 
558 BOX *
560  L_STACK *stack,
561  l_int32 x,
562  l_int32 y,
563  l_int32 connectivity)
564 {
565 BOX *box;
566 
567  if (!pixs || pixGetDepth(pixs) != 1)
568  return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
569  if (!stack)
570  return (BOX *)ERROR_PTR("stack not defined", __func__, NULL);
571  if (connectivity != 4 && connectivity != 8)
572  return (BOX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
573 
574  if (connectivity == 4) {
575  if ((box = pixSeedfill4BB(pixs, stack, x, y)) == NULL)
576  return (BOX *)ERROR_PTR("box not made", __func__, NULL);
577  } else if (connectivity == 8) {
578  if ((box = pixSeedfill8BB(pixs, stack, x, y)) == NULL)
579  return (BOX *)ERROR_PTR("box not made", __func__, NULL);
580  } else {
581  return (BOX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
582  }
583 
584  return box;
585 }
586 
587 
619 BOX *
621  L_STACK *stack,
622  l_int32 x,
623  l_int32 y)
624 {
625 l_int32 w, h, xstart, wpl, x1, x2, dy;
626 l_int32 xmax, ymax;
627 l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
628 l_uint32 *data, *line;
629 BOX *box;
630 
631  if (!pixs || pixGetDepth(pixs) != 1)
632  return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
633  if (!stack)
634  return (BOX *)ERROR_PTR("stack not defined", __func__, NULL);
635  if (!stack->auxstack)
636  stack->auxstack = lstackCreate(0);
637 
638  pixGetDimensions(pixs, &w, &h, NULL);
639  xmax = w - 1;
640  ymax = h - 1;
641  data = pixGetData(pixs);
642  wpl = pixGetWpl(pixs);
643  line = data + y * wpl;
644 
645  /* Check pix value of seed; must be within the image and ON */
646  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
647  return NULL;
648 
649  /* Init stack to seed:
650  * Must first init b.b. values to prevent valgrind from complaining;
651  * then init b.b. boundaries correctly to seed. */
652  minx = miny = 100000;
653  maxx = maxy = 0;
654  pushFillsegBB(stack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
655  pushFillsegBB(stack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
656  minx = maxx = x;
657  miny = maxy = y;
658 
659  while (lstackGetCount(stack) > 0) {
660  /* Pop segment off stack and fill a neighboring scan line */
661  popFillseg(stack, &x1, &x2, &y, &dy);
662  line = data + y * wpl;
663 
664  /* A segment of scanline y - dy for x1 <= x <= x2 was
665  * previously filled. We now explore adjacent pixels
666  * in scan line y. There are three regions: to the
667  * left of x1 - 1, between x1 and x2, and to the right of x2.
668  * These regions are handled differently. Leaks are
669  * possible expansions beyond the previous segment and
670  * going back in the -dy direction. These can happen
671  * for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
672  * are plugged with a push in the -dy (opposite) direction.
673  * And any segments found anywhere are always extended
674  * in the +dy direction. */
675  for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
676  CLEAR_DATA_BIT(line,x);
677  if (x >= x1) /* pix at x1 was off and was not cleared */
678  goto skip;
679  xstart = x + 1;
680  if (xstart < x1 - 1) /* leak on left? */
681  pushFillsegBB(stack, xstart, x1 - 1, y, -dy,
682  ymax, &minx, &maxx, &miny, &maxy);
683 
684  x = x1 + 1;
685  do {
686  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
687  CLEAR_DATA_BIT(line, x);
688  pushFillsegBB(stack, xstart, x - 1, y, dy,
689  ymax, &minx, &maxx, &miny, &maxy);
690  if (x > x2 + 1) /* leak on right? */
691  pushFillsegBB(stack, x2 + 1, x - 1, y, -dy,
692  ymax, &minx, &maxx, &miny, &maxy);
693  skip: for (x++; x <= x2 &&
694  x <= xmax &&
695  (GET_DATA_BIT(line, x) == 0); x++)
696  ;
697  xstart = x;
698  } while (x <= x2 && x <= xmax);
699  }
700 
701  if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
702  == NULL)
703  return (BOX *)ERROR_PTR("box not made", __func__, NULL);
704  return box;
705 }
706 
707 
732 BOX *
734  L_STACK *stack,
735  l_int32 x,
736  l_int32 y)
737 {
738 l_int32 w, h, xstart, wpl, x1, x2, dy;
739 l_int32 xmax, ymax;
740 l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
741 l_uint32 *data, *line;
742 BOX *box;
743 
744  if (!pixs || pixGetDepth(pixs) != 1)
745  return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
746  if (!stack)
747  return (BOX *)ERROR_PTR("stack not defined", __func__, NULL);
748  if (!stack->auxstack)
749  stack->auxstack = lstackCreate(0);
750 
751  pixGetDimensions(pixs, &w, &h, NULL);
752  xmax = w - 1;
753  ymax = h - 1;
754  data = pixGetData(pixs);
755  wpl = pixGetWpl(pixs);
756  line = data + y * wpl;
757 
758  /* Check pix value of seed; must be ON */
759  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
760  return NULL;
761 
762  /* Init stack to seed:
763  * Must first init b.b. values to prevent valgrind from complaining;
764  * then init b.b. boundaries correctly to seed. */
765  minx = miny = 100000;
766  maxx = maxy = 0;
767  pushFillsegBB(stack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
768  pushFillsegBB(stack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
769  minx = maxx = x;
770  miny = maxy = y;
771 
772  while (lstackGetCount(stack) > 0) {
773  /* Pop segment off stack and fill a neighboring scan line */
774  popFillseg(stack, &x1, &x2, &y, &dy);
775  line = data + y * wpl;
776 
777  /* A segment of scanline y - dy for x1 <= x <= x2 was
778  * previously filled. We now explore adjacent pixels
779  * in scan line y. There are three regions: to the
780  * left of x1, between x1 and x2, and to the right of x2.
781  * These regions are handled differently. Leaks are
782  * possible expansions beyond the previous segment and
783  * going back in the -dy direction. These can happen
784  * for x < x1 and for x > x2. Any "leak" segments
785  * are plugged with a push in the -dy (opposite) direction.
786  * And any segments found anywhere are always extended
787  * in the +dy direction. */
788  for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
789  CLEAR_DATA_BIT(line,x);
790  if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
791  goto skip;
792  xstart = x + 1;
793  if (xstart < x1) /* leak on left? */
794  pushFillsegBB(stack, xstart, x1 - 1, y, -dy,
795  ymax, &minx, &maxx, &miny, &maxy);
796 
797  x = x1;
798  do {
799  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
800  CLEAR_DATA_BIT(line, x);
801  pushFillsegBB(stack, xstart, x - 1, y, dy,
802  ymax, &minx, &maxx, &miny, &maxy);
803  if (x > x2) /* leak on right? */
804  pushFillsegBB(stack, x2 + 1, x - 1, y, -dy,
805  ymax, &minx, &maxx, &miny, &maxy);
806  skip: for (x++; x <= x2 + 1 &&
807  x <= xmax &&
808  (GET_DATA_BIT(line, x) == 0); x++)
809  ;
810  xstart = x;
811  } while (x <= x2 + 1 && x <= xmax);
812  }
813 
814  if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
815  == NULL)
816  return (BOX *)ERROR_PTR("box not made", __func__, NULL);
817  return box;
818 }
819 
820 
836 l_ok
838  L_STACK *stack,
839  l_int32 x,
840  l_int32 y,
841  l_int32 connectivity)
842 {
843 l_int32 retval;
844 
845  if (!pixs || pixGetDepth(pixs) != 1)
846  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
847  if (!stack)
848  return ERROR_INT("stack not defined", __func__, 1);
849  if (connectivity != 4 && connectivity != 8)
850  return ERROR_INT("connectivity not 4 or 8", __func__, 1);
851 
852  if (connectivity == 4)
853  retval = pixSeedfill4(pixs, stack, x, y);
854  else /* connectivity == 8 */
855  retval = pixSeedfill8(pixs, stack, x, y);
856 
857  return retval;
858 }
859 
860 
878 l_ok
880  L_STACK *stack,
881  l_int32 x,
882  l_int32 y)
883 {
884 l_int32 w, h, xstart, wpl, x1, x2, dy;
885 l_int32 xmax, ymax;
886 l_uint32 *data, *line;
887 
888  if (!pixs || pixGetDepth(pixs) != 1)
889  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
890  if (!stack)
891  return ERROR_INT("stack not defined", __func__, 1);
892  if (!stack->auxstack)
893  stack->auxstack = lstackCreate(0);
894 
895  pixGetDimensions(pixs, &w, &h, NULL);
896  xmax = w - 1;
897  ymax = h - 1;
898  data = pixGetData(pixs);
899  wpl = pixGetWpl(pixs);
900  line = data + y * wpl;
901 
902  /* Check pix value of seed; must be within the image and ON */
903  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
904  return 0;
905 
906  /* Init stack to seed */
907  pushFillseg(stack, x, x, y, 1, ymax);
908  pushFillseg(stack, x, x, y + 1, -1, ymax);
909 
910  while (lstackGetCount(stack) > 0) {
911  /* Pop segment off stack and fill a neighboring scan line */
912  popFillseg(stack, &x1, &x2, &y, &dy);
913  line = data + y * wpl;
914 
915  /* A segment of scanline y - dy for x1 <= x <= x2 was
916  * previously filled. We now explore adjacent pixels
917  * in scan line y. There are three regions: to the
918  * left of x1 - 1, between x1 and x2, and to the right of x2.
919  * These regions are handled differently. Leaks are
920  * possible expansions beyond the previous segment and
921  * going back in the -dy direction. These can happen
922  * for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
923  * are plugged with a push in the -dy (opposite) direction.
924  * And any segments found anywhere are always extended
925  * in the +dy direction. */
926  for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
927  CLEAR_DATA_BIT(line,x);
928  if (x >= x1) /* pix at x1 was off and was not cleared */
929  goto skip;
930  xstart = x + 1;
931  if (xstart < x1 - 1) /* leak on left? */
932  pushFillseg(stack, xstart, x1 - 1, y, -dy, ymax);
933 
934  x = x1 + 1;
935  do {
936  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
937  CLEAR_DATA_BIT(line, x);
938  pushFillseg(stack, xstart, x - 1, y, dy, ymax);
939  if (x > x2 + 1) /* leak on right? */
940  pushFillseg(stack, x2 + 1, x - 1, y, -dy, ymax);
941  skip: for (x++; x <= x2 &&
942  x <= xmax &&
943  (GET_DATA_BIT(line, x) == 0); x++)
944  ;
945  xstart = x;
946  } while (x <= x2 && x <= xmax);
947  }
948 
949  return 0;
950 }
951 
952 
970 l_ok
972  L_STACK *stack,
973  l_int32 x,
974  l_int32 y)
975 {
976 l_int32 w, h, xstart, wpl, x1, x2, dy;
977 l_int32 xmax, ymax;
978 l_uint32 *data, *line;
979 
980  if (!pixs || pixGetDepth(pixs) != 1)
981  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
982  if (!stack)
983  return ERROR_INT("stack not defined", __func__, 1);
984  if (!stack->auxstack)
985  stack->auxstack = lstackCreate(0);
986 
987  pixGetDimensions(pixs, &w, &h, NULL);
988  xmax = w - 1;
989  ymax = h - 1;
990  data = pixGetData(pixs);
991  wpl = pixGetWpl(pixs);
992  line = data + y * wpl;
993 
994  /* Check pix value of seed; must be ON */
995  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
996  return 0;
997 
998  /* Init stack to seed */
999  pushFillseg(stack, x, x, y, 1, ymax);
1000  pushFillseg(stack, x, x, y + 1, -1, ymax);
1001 
1002  while (lstackGetCount(stack) > 0) {
1003  /* Pop segment off stack and fill a neighboring scan line */
1004  popFillseg(stack, &x1, &x2, &y, &dy);
1005  line = data + y * wpl;
1006 
1007  /* A segment of scanline y - dy for x1 <= x <= x2 was
1008  * previously filled. We now explore adjacent pixels
1009  * in scan line y. There are three regions: to the
1010  * left of x1, between x1 and x2, and to the right of x2.
1011  * These regions are handled differently. Leaks are
1012  * possible expansions beyond the previous segment and
1013  * going back in the -dy direction. These can happen
1014  * for x < x1 and for x > x2. Any "leak" segments
1015  * are plugged with a push in the -dy (opposite) direction.
1016  * And any segments found anywhere are always extended
1017  * in the +dy direction. */
1018  for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
1019  CLEAR_DATA_BIT(line,x);
1020  if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
1021  goto skip;
1022  xstart = x + 1;
1023  if (xstart < x1) /* leak on left? */
1024  pushFillseg(stack, xstart, x1 - 1, y, -dy, ymax);
1025 
1026  x = x1;
1027  do {
1028  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
1029  CLEAR_DATA_BIT(line, x);
1030  pushFillseg(stack, xstart, x - 1, y, dy, ymax);
1031  if (x > x2) /* leak on right? */
1032  pushFillseg(stack, x2 + 1, x - 1, y, -dy, ymax);
1033  skip: for (x++; x <= x2 + 1 &&
1034  x <= xmax &&
1035  (GET_DATA_BIT(line, x) == 0); x++)
1036  ;
1037  xstart = x;
1038  } while (x <= x2 + 1 && x <= xmax);
1039  }
1040 
1041  return 0;
1042 }
1043 
1044 
1045 
1046 /*-----------------------------------------------------------------------*
1047  * Static stack helper functions: push and pop fillsegs *
1048  *-----------------------------------------------------------------------*/
1071 static void
1073  l_int32 xleft,
1074  l_int32 xright,
1075  l_int32 y,
1076  l_int32 dy,
1077  l_int32 ymax,
1078  l_int32 *pminx,
1079  l_int32 *pmaxx,
1080  l_int32 *pminy,
1081  l_int32 *pmaxy)
1082 {
1083 FILLSEG *fseg;
1084 L_STACK *auxstack;
1085 
1086  if (!stack) {
1087  L_ERROR("stack not defined\n", __func__);
1088  return;
1089  }
1090 
1091  *pminx = L_MIN(*pminx, xleft);
1092  *pmaxx = L_MAX(*pmaxx, xright);
1093  *pminy = L_MIN(*pminy, y);
1094  *pmaxy = L_MAX(*pmaxy, y);
1095 
1096  if (y + dy >= 0 && y + dy <= ymax) {
1097  if ((auxstack = stack->auxstack) == NULL) {
1098  L_ERROR("auxstack not defined\n", __func__);
1099  return;
1100  }
1101 
1102  /* Get a fillseg to use */
1103  if (lstackGetCount(auxstack) > 0)
1104  fseg = (FILLSEG *)lstackRemove(auxstack);
1105  else
1106  fseg = (FILLSEG *)LEPT_CALLOC(1, sizeof(FILLSEG));
1107  fseg->xleft = xleft;
1108  fseg->xright = xright;
1109  fseg->y = y;
1110  fseg->dy = dy;
1111  lstackAdd(stack, fseg);
1112  }
1113 }
1114 
1115 
1134 static void
1136  l_int32 xleft,
1137  l_int32 xright,
1138  l_int32 y,
1139  l_int32 dy,
1140  l_int32 ymax)
1141 {
1142 FILLSEG *fseg;
1143 L_STACK *auxstack;
1144 
1145  if (!stack) {
1146  L_ERROR("stack not defined\n", __func__);
1147  return;
1148  }
1149 
1150  if (y + dy >= 0 && y + dy <= ymax) {
1151  if ((auxstack = stack->auxstack) == NULL) {
1152  L_ERROR("auxstack not defined\n", __func__);
1153  return;
1154  }
1155 
1156  /* Get a fillseg to use */
1157  if (lstackGetCount(auxstack) > 0)
1158  fseg = (FILLSEG *)lstackRemove(auxstack);
1159  else
1160  fseg = (FILLSEG *)LEPT_CALLOC(1, sizeof(FILLSEG));
1161  fseg->xleft = xleft;
1162  fseg->xright = xright;
1163  fseg->y = y;
1164  fseg->dy = dy;
1165  lstackAdd(stack, fseg);
1166  }
1167 }
1168 
1169 
1187 static void
1189  l_int32 *pxleft,
1190  l_int32 *pxright,
1191  l_int32 *py,
1192  l_int32 *pdy)
1193 {
1194 FILLSEG *fseg;
1195 L_STACK *auxstack;
1196 
1197  if (!stack) {
1198  L_ERROR("stack not defined\n", __func__);
1199  return;
1200  }
1201  if ((auxstack = stack->auxstack) == NULL) {
1202  L_ERROR("auxstack not defined\n", __func__);
1203  return;
1204  }
1205 
1206  if ((fseg = (FILLSEG *)lstackRemove(stack)) == NULL)
1207  return;
1208 
1209  *pxleft = fseg->xleft;
1210  *pxright = fseg->xright;
1211  *py = fseg->y + fseg->dy; /* this now points to the new line */
1212  *pdy = fseg->dy;
1213 
1214  /* Save it for re-use */
1215  lstackAdd(auxstack, fseg);
1216 }
#define CLEAR_DATA_BIT(pdata, n)
Definition: arrayaccess.h:131
#define GET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:123
BOXA * boxaCopy(BOXA *boxa, l_int32 copyflag)
boxaCopy()
Definition: boxbasic.c:475
l_ok boxaAddBox(BOXA *boxa, BOX *box, l_int32 copyflag)
boxaAddBox()
Definition: boxbasic.c:553
void boxaDestroy(BOXA **pboxa)
boxaDestroy()
Definition: boxbasic.c:519
BOX * boxCreate(l_int32 x, l_int32 y, l_int32 w, l_int32 h)
boxCreate()
Definition: boxbasic.c:171
BOXA * boxaCreate(l_int32 n)
boxaCreate()
Definition: boxbasic.c:442
BOXA * pixConnCompBB(PIX *pixs, l_int32 connectivity)
pixConnCompBB()
Definition: conncomp.c:307
l_ok pixSeedfill4(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill4()
Definition: conncomp.c:879
BOX * pixSeedfill4BB(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill4BB()
Definition: conncomp.c:620
BOXA * pixConnComp(PIX *pixs, PIXA **ppixa, l_int32 connectivity)
pixConnComp()
Definition: conncomp.c:152
static void pushFillsegBB(L_STACK *stack, l_int32 xleft, l_int32 xright, l_int32 y, l_int32 dy, l_int32 ymax, l_int32 *pminx, l_int32 *pmaxx, l_int32 *pminy, l_int32 *pmaxy)
pushFillsegBB()
Definition: conncomp.c:1072
static l_int32 nextOnPixelInRasterLow(l_uint32 *data, l_int32 w, l_int32 h, l_int32 wpl, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
nextOnPixelInRasterLow()
Definition: conncomp.c:482
static void pushFillseg(L_STACK *stack, l_int32 xleft, l_int32 xright, l_int32 y, l_int32 dy, l_int32 ymax)
pushFillseg()
Definition: conncomp.c:1135
BOX * pixSeedfill8BB(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill8BB()
Definition: conncomp.c:733
l_int32 nextOnPixelInRaster(PIX *pixs, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
nextOnPixelInRaster()
Definition: conncomp.c:450
l_ok pixCountConnComp(PIX *pixs, l_int32 connectivity, l_int32 *pcount)
pixCountConnComp()
Definition: conncomp.c:389
BOXA * pixConnCompPixa(PIX *pixs, PIXA **ppixa, l_int32 connectivity)
pixConnCompPixa()
Definition: conncomp.c:194
static void popFillseg(L_STACK *stack, l_int32 *pxleft, l_int32 *pxright, l_int32 *py, l_int32 *pdy)
popFillseg()
Definition: conncomp.c:1188
l_ok pixSeedfill(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity)
pixSeedfill()
Definition: conncomp.c:837
l_ok pixSeedfill8(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill8()
Definition: conncomp.c:971
BOX * pixSeedfillBB(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity)
pixSeedfillBB()
Definition: conncomp.c:559
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1642
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:608
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1074
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:689
l_ok pixSetPadBits(PIX *pix, l_int32 val)
pixSetPadBits()
Definition: pix2.c:1346
l_ok pixZero(PIX *pix, l_int32 *pempty)
pixZero()
Definition: pix3.c:1777
l_ok pixCountPixels(PIX *pixs, l_int32 *pcount, l_int32 *tab8)
pixCountPixels()
Definition: pix3.c:1893
PIX * pixXor(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixXor()
Definition: pix3.c:1654
PIX * pixClipRectangle(PIX *pixs, BOX *box, BOX **pboxc)
pixClipRectangle()
Definition: pix5.c:994
#define PIX_DST
Definition: pix.h:445
@ L_COPY
Definition: pix.h:505
@ L_INSERT
Definition: pix.h:504
#define PIX_SRC
Definition: pix.h:444
l_ok pixaAddPix(PIXA *pixa, PIX *pix, l_int32 copyflag)
pixaAddPix()
Definition: pixabasic.c:493
void pixaDestroy(PIXA **ppixa)
pixaDestroy()
Definition: pixabasic.c:404
PIXA * pixaCreate(l_int32 n)
pixaCreate()
Definition: pixabasic.c:167
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
l_int32 lstackGetCount(L_STACK *lstack)
lstackGetCount()
Definition: stack.c:242
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
Definition: stack.c:122
l_ok lstackAdd(L_STACK *lstack, void *item)
lstackAdd()
Definition: stack.c:166
void * lstackRemove(L_STACK *lstack)
lstackRemove()
Definition: stack.c:196
L_STACK * lstackCreate(l_int32 n)
lstackCreate()
Definition: stack.c:82
l_int32 y
Definition: pix_internal.h:258
l_int32 x
Definition: pix_internal.h:257
l_int32 w
Definition: pix_internal.h:259
l_int32 h
Definition: pix_internal.h:260
The struct FillSeg is used by the Heckbert seedfill algorithm to hold information about image segment...
Definition: conncomp.c:105
l_int32 y
Definition: conncomp.c:108
l_int32 dy
Definition: conncomp.c:109
l_int32 xleft
Definition: conncomp.c:106
l_int32 xright
Definition: conncomp.c:107
Definition: stack.h:60
struct L_Stack * auxstack
Definition: stack.h:64
struct Boxa * boxa
Definition: pix_internal.h:238
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306
l_int32 lept_mkdir(const char *subdir)
lept_mkdir()
Definition: utils2.c:2138