Leptonica  1.82.0
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 
103 struct FillSeg
104 {
105  l_int32 xleft;
106  l_int32 xright;
107  l_int32 y;
108  l_int32 dy;
109 };
110 typedef struct FillSeg FILLSEG;
111 
112 static l_int32 nextOnPixelInRasterLow(l_uint32 *data, l_int32 w, l_int32 h,
113  l_int32 wpl, l_int32 xstart,
114  l_int32 ystart, l_int32 *px, l_int32 *py);
115 
116  /* Static accessors for FillSegs on a stack */
117 static void pushFillsegBB(L_STACK *stack, l_int32 xleft, l_int32 xright,
118  l_int32 y, l_int32 dy, l_int32 ymax,
119  l_int32 *pminx, l_int32 *pmaxx,
120  l_int32 *pminy, l_int32 *pmaxy);
121 static void pushFillseg(L_STACK *stack, l_int32 xleft, l_int32 xright,
122  l_int32 y, l_int32 dy, l_int32 ymax);
123 static void popFillseg(L_STACK *stack, l_int32 *pxleft, l_int32 *pxright,
124  l_int32 *py, l_int32 *pdy);
125 
126 
127 #ifndef NO_CONSOLE_IO
128 #define DEBUG 0
129 #endif /* ~NO_CONSOLE_IO */
130 
131 
132 /*-----------------------------------------------------------------------*
133  * Bounding boxes of 4 Connected Components *
134  *-----------------------------------------------------------------------*/
150 BOXA *
152  PIXA **ppixa,
153  l_int32 connectivity)
154 {
155 
156  PROCNAME("pixConnComp");
157 
158  if (ppixa) *ppixa = NULL;
159  if (!pixs || pixGetDepth(pixs) != 1)
160  return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
161  if (connectivity != 4 && connectivity != 8)
162  return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
163 
164  if (!ppixa)
165  return pixConnCompBB(pixs, connectivity);
166  else
167  return pixConnCompPixa(pixs, ppixa, connectivity);
168 }
169 
170 
194 BOXA *
196  PIXA **ppixa,
197  l_int32 connectivity)
198 {
199 l_int32 h, iszero;
200 l_int32 x, y, xstart, ystart;
201 PIX *pix1, *pix2, *pix3, *pix4;
202 PIXA *pixa;
203 BOX *box;
204 BOXA *boxa;
205 L_STACK *stack, *auxstack;
206 
207  PROCNAME("pixConnCompPixa");
208 
209  if (!ppixa)
210  return (BOXA *)ERROR_PTR("&pixa not defined", procName, NULL);
211  *ppixa = NULL;
212  if (!pixs || pixGetDepth(pixs) != 1)
213  return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
214  if (connectivity != 4 && connectivity != 8)
215  return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
216 
217  pix1 = pix2 = pix3 = pix4 = NULL;
218  stack = NULL;
219  pixa = pixaCreate(0);
220  boxa = NULL;
221  *ppixa = pixa;
222  pixZero(pixs, &iszero);
223  if (iszero)
224  return boxaCreate(1); /* return empty boxa and empty pixa */
225 
226  pixSetPadBits(pixs, 0);
227  pix1 = pixCopy(NULL, pixs);
228  pix2 = pixCopy(NULL, pixs);
229  if (!pix1 || !pix2) {
230  L_ERROR("pix1 or pix2 not made\n", procName);
231  pixaDestroy(ppixa);
232  goto cleanup;
233  }
234 
235  h = pixGetHeight(pixs);
236  if ((stack = lstackCreate(h)) == NULL) {
237  L_ERROR("stack not made\n", procName);
238  pixaDestroy(ppixa);
239  goto cleanup;
240  }
241  auxstack = lstackCreate(0);
242  stack->auxstack = auxstack;
243  boxa = boxaCreate(0);
244 
245  xstart = 0;
246  ystart = 0;
247  while (1) {
248  if (!nextOnPixelInRaster(pix1, xstart, ystart, &x, &y))
249  break;
250 
251  if ((box = pixSeedfillBB(pix1, stack, x, y, connectivity)) == NULL) {
252  boxaDestroy(&boxa);
253  pixaDestroy(ppixa);
254  L_ERROR("box not made\n", procName);
255  goto cleanup;
256  }
257  boxaAddBox(boxa, box, L_INSERT);
258 
259  /* Save the c.c. and remove from pix2 as well */
260  pix3 = pixClipRectangle(pix1, box, NULL);
261  pix4 = pixClipRectangle(pix2, box, NULL);
262  pixXor(pix3, pix3, pix4);
263  pixRasterop(pix2, box->x, box->y, box->w, box->h, PIX_SRC ^ PIX_DST,
264  pix3, 0, 0);
265  pixaAddPix(pixa, pix3, L_INSERT);
266  pixDestroy(&pix4);
267 
268  xstart = x;
269  ystart = y;
270  }
271 
272 #if DEBUG
273  pixCountPixels(pix1, &iszero, NULL);
274  lept_stderr("Number of remaining pixels = %d\n", iszero);
275  lept_mkdir("lept/cc");
276  pixWriteDebug("/tmp/lept/cc/remain.png", pix1, IFF_PNG);
277 #endif /* DEBUG */
278 
279  /* Remove old boxa of pixa and replace with a copy */
280  boxaDestroy(&pixa->boxa);
281  pixa->boxa = boxaCopy(boxa, L_COPY);
282  *ppixa = pixa;
283 
284  /* Cleanup, freeing the fillsegs on each stack */
285 cleanup:
286  lstackDestroy(&stack, TRUE);
287  pixDestroy(&pix1);
288  pixDestroy(&pix2);
289  return boxa;
290 }
291 
292 
309 BOXA *
311  l_int32 connectivity)
312 {
313 l_int32 h, iszero;
314 l_int32 x, y, xstart, ystart;
315 PIX *pix1;
316 BOX *box;
317 BOXA *boxa;
318 L_STACK *stack, *auxstack;
319 
320  PROCNAME("pixConnCompBB");
321 
322  if (!pixs || pixGetDepth(pixs) != 1)
323  return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
324  if (connectivity != 4 && connectivity != 8)
325  return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
326 
327  boxa = NULL;
328  pix1 = NULL;
329  stack = NULL;
330  pixZero(pixs, &iszero);
331  if (iszero)
332  return boxaCreate(1); /* return empty boxa */
333 
334  pixSetPadBits(pixs, 0);
335  if ((pix1 = pixCopy(NULL, pixs)) == NULL)
336  return (BOXA *)ERROR_PTR("pix1 not made", procName, NULL);
337 
338  h = pixGetHeight(pixs);
339  if ((stack = lstackCreate(h)) == NULL) {
340  L_ERROR("stack not made\n", procName);
341  goto cleanup;
342  }
343  auxstack = lstackCreate(0);
344  stack->auxstack = auxstack;
345  boxa = boxaCreate(0);
346 
347  xstart = 0;
348  ystart = 0;
349  while (1) {
350  if (!nextOnPixelInRaster(pix1, xstart, ystart, &x, &y))
351  break;
352 
353  if ((box = pixSeedfillBB(pix1, stack, x, y, connectivity)) == NULL) {
354  L_ERROR("box not made\n", procName);
355  boxaDestroy(&boxa);
356  goto cleanup;
357  }
358  boxaAddBox(boxa, box, L_INSERT);
359 
360  xstart = x;
361  ystart = y;
362  }
363 
364 #if DEBUG
365  pixCountPixels(pix1, &iszero, NULL);
366  lept_stderr("Number of remaining pixels = %d\n", iszero);
367  lept_mkdir("lept/cc");
368  pixWriteDebug("/tmp/lept/cc/remain.png", pix1, IFF_PNG);
369 #endif /* DEBUG */
370 
371  /* Cleanup, freeing the fillsegs on each stack */
372 cleanup:
373  lstackDestroy(&stack, TRUE);
374  pixDestroy(&pix1);
375  return boxa;
376 }
377 
378 
393 l_ok
395  l_int32 connectivity,
396  l_int32 *pcount)
397 {
398 l_int32 h, iszero;
399 l_int32 x, y, xstart, ystart;
400 PIX *pix1;
401 L_STACK *stack, *auxstack;
402 
403  PROCNAME("pixCountConnComp");
404 
405  if (!pcount)
406  return ERROR_INT("&count not defined", procName, 1);
407  *pcount = 0; /* initialize the count to 0 */
408  if (!pixs || pixGetDepth(pixs) != 1)
409  return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
410  if (connectivity != 4 && connectivity != 8)
411  return ERROR_INT("connectivity not 4 or 8", procName, 1);
412 
413  stack = NULL;
414  pixZero(pixs, &iszero);
415  if (iszero)
416  return 0;
417 
418  pixSetPadBits(pixs, 0);
419  if ((pix1 = pixCopy(NULL, pixs)) == NULL)
420  return ERROR_INT("pix1 not made", procName, 1);
421  h = pixGetHeight(pixs);
422  if ((stack = lstackCreate(h)) == NULL) {
423  pixDestroy(&pix1);
424  return ERROR_INT("stack not made\n", procName, 1);
425  }
426  auxstack = lstackCreate(0);
427  stack->auxstack = auxstack;
428 
429  xstart = 0;
430  ystart = 0;
431  while (1) {
432  if (!nextOnPixelInRaster(pix1, xstart, ystart, &x, &y))
433  break;
434 
435  pixSeedfill(pix1, stack, x, y, connectivity);
436  (*pcount)++;
437  xstart = x;
438  ystart = y;
439  }
440 
441  /* Cleanup, freeing the fillsegs on each stack */
442  lstackDestroy(&stack, TRUE);
443  pixDestroy(&pix1);
444  return 0;
445 }
446 
447 
456 l_int32
458  l_int32 xstart,
459  l_int32 ystart,
460  l_int32 *px,
461  l_int32 *py)
462 {
463 l_int32 w, h, d, wpl;
464 l_uint32 *data;
465 
466  PROCNAME("nextOnPixelInRaster");
467 
468  if (!pixs)
469  return ERROR_INT("pixs not defined", procName, 0);
470  pixGetDimensions(pixs, &w, &h, &d);
471  if (d != 1)
472  return ERROR_INT("pixs not 1 bpp", procName, 0);
473 
474  wpl = pixGetWpl(pixs);
475  data = pixGetData(pixs);
476  return nextOnPixelInRasterLow(data, w, h, wpl, xstart, ystart, px, py);
477 }
478 
479 
490 static l_int32
491 nextOnPixelInRasterLow(l_uint32 *data,
492  l_int32 w,
493  l_int32 h,
494  l_int32 wpl,
495  l_int32 xstart,
496  l_int32 ystart,
497  l_int32 *px,
498  l_int32 *py)
499 {
500 l_int32 i, x, y, xend, startword;
501 l_uint32 *line, *pword;
502 
503  /* Look at the first word */
504  line = data + ystart * wpl;
505  pword = line + (xstart / 32);
506  if (*pword) {
507  xend = xstart - (xstart % 32) + 31;
508  for (x = xstart; x <= xend && x < w; x++) {
509  if (GET_DATA_BIT(line, x)) {
510  *px = x;
511  *py = ystart;
512  return 1;
513  }
514  }
515  }
516 
517  /* Continue with the rest of the line */
518  startword = (xstart / 32) + 1;
519  x = 32 * startword;
520  for (pword = line + startword; x < w; pword++, x += 32) {
521  if (*pword) {
522  for (i = 0; i < 32 && x < w; i++, x++) {
523  if (GET_DATA_BIT(line, x)) {
524  *px = x;
525  *py = ystart;
526  return 1;
527  }
528  }
529  }
530  }
531 
532  /* Continue with following lines */
533  for (y = ystart + 1; y < h; y++) {
534  line = data + y * wpl;
535  for (pword = line, x = 0; x < w; pword++, x += 32) {
536  if (*pword) {
537  for (i = 0; i < 32 && x < w; i++, x++) {
538  if (GET_DATA_BIT(line, x)) {
539  *px = x;
540  *py = y;
541  return 1;
542  }
543  }
544  }
545  }
546  }
547 
548  return 0;
549 }
550 
551 
567 BOX *
569  L_STACK *stack,
570  l_int32 x,
571  l_int32 y,
572  l_int32 connectivity)
573 {
574 BOX *box;
575 
576  PROCNAME("pixSeedfillBB");
577 
578  if (!pixs || pixGetDepth(pixs) != 1)
579  return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
580  if (!stack)
581  return (BOX *)ERROR_PTR("stack not defined", procName, NULL);
582  if (connectivity != 4 && connectivity != 8)
583  return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
584 
585  if (connectivity == 4) {
586  if ((box = pixSeedfill4BB(pixs, stack, x, y)) == NULL)
587  return (BOX *)ERROR_PTR("box not made", procName, NULL);
588  } else if (connectivity == 8) {
589  if ((box = pixSeedfill8BB(pixs, stack, x, y)) == NULL)
590  return (BOX *)ERROR_PTR("box not made", procName, NULL);
591  } else {
592  return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
593  }
594 
595  return box;
596 }
597 
598 
630 BOX *
632  L_STACK *stack,
633  l_int32 x,
634  l_int32 y)
635 {
636 l_int32 w, h, xstart, wpl, x1, x2, dy;
637 l_int32 xmax, ymax;
638 l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
639 l_uint32 *data, *line;
640 BOX *box;
641 
642  PROCNAME("pixSeedfill4BB");
643 
644  if (!pixs || pixGetDepth(pixs) != 1)
645  return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
646  if (!stack)
647  return (BOX *)ERROR_PTR("stack not defined", procName, NULL);
648  if (!stack->auxstack)
649  stack->auxstack = lstackCreate(0);
650 
651  pixGetDimensions(pixs, &w, &h, NULL);
652  xmax = w - 1;
653  ymax = h - 1;
654  data = pixGetData(pixs);
655  wpl = pixGetWpl(pixs);
656  line = data + y * wpl;
657 
658  /* Check pix value of seed; must be within the image and ON */
659  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
660  return NULL;
661 
662  /* Init stack to seed:
663  * Must first init b.b. values to prevent valgrind from complaining;
664  * then init b.b. boundaries correctly to seed. */
665  minx = miny = 100000;
666  maxx = maxy = 0;
667  pushFillsegBB(stack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
668  pushFillsegBB(stack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
669  minx = maxx = x;
670  miny = maxy = y;
671 
672  while (lstackGetCount(stack) > 0) {
673  /* Pop segment off stack and fill a neighboring scan line */
674  popFillseg(stack, &x1, &x2, &y, &dy);
675  line = data + y * wpl;
676 
677  /* A segment of scanline y - dy for x1 <= x <= x2 was
678  * previously filled. We now explore adjacent pixels
679  * in scan line y. There are three regions: to the
680  * left of x1 - 1, between x1 and x2, and to the right of x2.
681  * These regions are handled differently. Leaks are
682  * possible expansions beyond the previous segment and
683  * going back in the -dy direction. These can happen
684  * for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
685  * are plugged with a push in the -dy (opposite) direction.
686  * And any segments found anywhere are always extended
687  * in the +dy direction. */
688  for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
689  CLEAR_DATA_BIT(line,x);
690  if (x >= x1) /* pix at x1 was off and was not cleared */
691  goto skip;
692  xstart = x + 1;
693  if (xstart < x1 - 1) /* leak on left? */
694  pushFillsegBB(stack, xstart, x1 - 1, y, -dy,
695  ymax, &minx, &maxx, &miny, &maxy);
696 
697  x = x1 + 1;
698  do {
699  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
700  CLEAR_DATA_BIT(line, x);
701  pushFillsegBB(stack, xstart, x - 1, y, dy,
702  ymax, &minx, &maxx, &miny, &maxy);
703  if (x > x2 + 1) /* leak on right? */
704  pushFillsegBB(stack, x2 + 1, x - 1, y, -dy,
705  ymax, &minx, &maxx, &miny, &maxy);
706  skip: for (x++; x <= x2 &&
707  x <= xmax &&
708  (GET_DATA_BIT(line, x) == 0); x++)
709  ;
710  xstart = x;
711  } while (x <= x2 && x <= xmax);
712  }
713 
714  if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
715  == NULL)
716  return (BOX *)ERROR_PTR("box not made", procName, NULL);
717  return box;
718 }
719 
720 
745 BOX *
747  L_STACK *stack,
748  l_int32 x,
749  l_int32 y)
750 {
751 l_int32 w, h, xstart, wpl, x1, x2, dy;
752 l_int32 xmax, ymax;
753 l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
754 l_uint32 *data, *line;
755 BOX *box;
756 
757  PROCNAME("pixSeedfill8BB");
758 
759  if (!pixs || pixGetDepth(pixs) != 1)
760  return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
761  if (!stack)
762  return (BOX *)ERROR_PTR("stack not defined", procName, NULL);
763  if (!stack->auxstack)
764  stack->auxstack = lstackCreate(0);
765 
766  pixGetDimensions(pixs, &w, &h, NULL);
767  xmax = w - 1;
768  ymax = h - 1;
769  data = pixGetData(pixs);
770  wpl = pixGetWpl(pixs);
771  line = data + y * wpl;
772 
773  /* Check pix value of seed; must be ON */
774  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
775  return NULL;
776 
777  /* Init stack to seed:
778  * Must first init b.b. values to prevent valgrind from complaining;
779  * then init b.b. boundaries correctly to seed. */
780  minx = miny = 100000;
781  maxx = maxy = 0;
782  pushFillsegBB(stack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
783  pushFillsegBB(stack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
784  minx = maxx = x;
785  miny = maxy = y;
786 
787  while (lstackGetCount(stack) > 0) {
788  /* Pop segment off stack and fill a neighboring scan line */
789  popFillseg(stack, &x1, &x2, &y, &dy);
790  line = data + y * wpl;
791 
792  /* A segment of scanline y - dy for x1 <= x <= x2 was
793  * previously filled. We now explore adjacent pixels
794  * in scan line y. There are three regions: to the
795  * left of x1, between x1 and x2, and to the right of x2.
796  * These regions are handled differently. Leaks are
797  * possible expansions beyond the previous segment and
798  * going back in the -dy direction. These can happen
799  * for x < x1 and for x > x2. Any "leak" segments
800  * are plugged with a push in the -dy (opposite) direction.
801  * And any segments found anywhere are always extended
802  * in the +dy direction. */
803  for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
804  CLEAR_DATA_BIT(line,x);
805  if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
806  goto skip;
807  xstart = x + 1;
808  if (xstart < x1) /* leak on left? */
809  pushFillsegBB(stack, xstart, x1 - 1, y, -dy,
810  ymax, &minx, &maxx, &miny, &maxy);
811 
812  x = x1;
813  do {
814  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
815  CLEAR_DATA_BIT(line, x);
816  pushFillsegBB(stack, xstart, x - 1, y, dy,
817  ymax, &minx, &maxx, &miny, &maxy);
818  if (x > x2) /* leak on right? */
819  pushFillsegBB(stack, x2 + 1, x - 1, y, -dy,
820  ymax, &minx, &maxx, &miny, &maxy);
821  skip: for (x++; x <= x2 + 1 &&
822  x <= xmax &&
823  (GET_DATA_BIT(line, x) == 0); x++)
824  ;
825  xstart = x;
826  } while (x <= x2 + 1 && x <= xmax);
827  }
828 
829  if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
830  == NULL)
831  return (BOX *)ERROR_PTR("box not made", procName, NULL);
832  return box;
833 }
834 
835 
851 l_ok
853  L_STACK *stack,
854  l_int32 x,
855  l_int32 y,
856  l_int32 connectivity)
857 {
858 l_int32 retval;
859 
860  PROCNAME("pixSeedfill");
861 
862  if (!pixs || pixGetDepth(pixs) != 1)
863  return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
864  if (!stack)
865  return ERROR_INT("stack not defined", procName, 1);
866  if (connectivity != 4 && connectivity != 8)
867  return ERROR_INT("connectivity not 4 or 8", procName, 1);
868 
869  if (connectivity == 4)
870  retval = pixSeedfill4(pixs, stack, x, y);
871  else /* connectivity == 8 */
872  retval = pixSeedfill8(pixs, stack, x, y);
873 
874  return retval;
875 }
876 
877 
895 l_ok
897  L_STACK *stack,
898  l_int32 x,
899  l_int32 y)
900 {
901 l_int32 w, h, xstart, wpl, x1, x2, dy;
902 l_int32 xmax, ymax;
903 l_uint32 *data, *line;
904 
905  PROCNAME("pixSeedfill4");
906 
907  if (!pixs || pixGetDepth(pixs) != 1)
908  return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
909  if (!stack)
910  return ERROR_INT("stack not defined", procName, 1);
911  if (!stack->auxstack)
912  stack->auxstack = lstackCreate(0);
913 
914  pixGetDimensions(pixs, &w, &h, NULL);
915  xmax = w - 1;
916  ymax = h - 1;
917  data = pixGetData(pixs);
918  wpl = pixGetWpl(pixs);
919  line = data + y * wpl;
920 
921  /* Check pix value of seed; must be within the image and ON */
922  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
923  return 0;
924 
925  /* Init stack to seed */
926  pushFillseg(stack, x, x, y, 1, ymax);
927  pushFillseg(stack, x, x, y + 1, -1, ymax);
928 
929  while (lstackGetCount(stack) > 0) {
930  /* Pop segment off stack and fill a neighboring scan line */
931  popFillseg(stack, &x1, &x2, &y, &dy);
932  line = data + y * wpl;
933 
934  /* A segment of scanline y - dy for x1 <= x <= x2 was
935  * previously filled. We now explore adjacent pixels
936  * in scan line y. There are three regions: to the
937  * left of x1 - 1, between x1 and x2, and to the right of x2.
938  * These regions are handled differently. Leaks are
939  * possible expansions beyond the previous segment and
940  * going back in the -dy direction. These can happen
941  * for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
942  * are plugged with a push in the -dy (opposite) direction.
943  * And any segments found anywhere are always extended
944  * in the +dy direction. */
945  for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
946  CLEAR_DATA_BIT(line,x);
947  if (x >= x1) /* pix at x1 was off and was not cleared */
948  goto skip;
949  xstart = x + 1;
950  if (xstart < x1 - 1) /* leak on left? */
951  pushFillseg(stack, xstart, x1 - 1, y, -dy, ymax);
952 
953  x = x1 + 1;
954  do {
955  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
956  CLEAR_DATA_BIT(line, x);
957  pushFillseg(stack, xstart, x - 1, y, dy, ymax);
958  if (x > x2 + 1) /* leak on right? */
959  pushFillseg(stack, x2 + 1, x - 1, y, -dy, ymax);
960  skip: for (x++; x <= x2 &&
961  x <= xmax &&
962  (GET_DATA_BIT(line, x) == 0); x++)
963  ;
964  xstart = x;
965  } while (x <= x2 && x <= xmax);
966  }
967 
968  return 0;
969 }
970 
971 
989 l_ok
991  L_STACK *stack,
992  l_int32 x,
993  l_int32 y)
994 {
995 l_int32 w, h, xstart, wpl, x1, x2, dy;
996 l_int32 xmax, ymax;
997 l_uint32 *data, *line;
998 
999  PROCNAME("pixSeedfill8");
1000 
1001  if (!pixs || pixGetDepth(pixs) != 1)
1002  return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
1003  if (!stack)
1004  return ERROR_INT("stack not defined", procName, 1);
1005  if (!stack->auxstack)
1006  stack->auxstack = lstackCreate(0);
1007 
1008  pixGetDimensions(pixs, &w, &h, NULL);
1009  xmax = w - 1;
1010  ymax = h - 1;
1011  data = pixGetData(pixs);
1012  wpl = pixGetWpl(pixs);
1013  line = data + y * wpl;
1014 
1015  /* Check pix value of seed; must be ON */
1016  if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
1017  return 0;
1018 
1019  /* Init stack to seed */
1020  pushFillseg(stack, x, x, y, 1, ymax);
1021  pushFillseg(stack, x, x, y + 1, -1, ymax);
1022 
1023  while (lstackGetCount(stack) > 0) {
1024  /* Pop segment off stack and fill a neighboring scan line */
1025  popFillseg(stack, &x1, &x2, &y, &dy);
1026  line = data + y * wpl;
1027 
1028  /* A segment of scanline y - dy for x1 <= x <= x2 was
1029  * previously filled. We now explore adjacent pixels
1030  * in scan line y. There are three regions: to the
1031  * left of x1, between x1 and x2, and to the right of x2.
1032  * These regions are handled differently. Leaks are
1033  * possible expansions beyond the previous segment and
1034  * going back in the -dy direction. These can happen
1035  * for x < x1 and for x > x2. Any "leak" segments
1036  * are plugged with a push in the -dy (opposite) direction.
1037  * And any segments found anywhere are always extended
1038  * in the +dy direction. */
1039  for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
1040  CLEAR_DATA_BIT(line,x);
1041  if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
1042  goto skip;
1043  xstart = x + 1;
1044  if (xstart < x1) /* leak on left? */
1045  pushFillseg(stack, xstart, x1 - 1, y, -dy, ymax);
1046 
1047  x = x1;
1048  do {
1049  for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
1050  CLEAR_DATA_BIT(line, x);
1051  pushFillseg(stack, xstart, x - 1, y, dy, ymax);
1052  if (x > x2) /* leak on right? */
1053  pushFillseg(stack, x2 + 1, x - 1, y, -dy, ymax);
1054  skip: for (x++; x <= x2 + 1 &&
1055  x <= xmax &&
1056  (GET_DATA_BIT(line, x) == 0); x++)
1057  ;
1058  xstart = x;
1059  } while (x <= x2 + 1 && x <= xmax);
1060  }
1061 
1062  return 0;
1063 }
1064 
1065 
1066 
1067 /*-----------------------------------------------------------------------*
1068  * Static stack helper functions: push and pop fillsegs *
1069  *-----------------------------------------------------------------------*/
1092 static void
1094  l_int32 xleft,
1095  l_int32 xright,
1096  l_int32 y,
1097  l_int32 dy,
1098  l_int32 ymax,
1099  l_int32 *pminx,
1100  l_int32 *pmaxx,
1101  l_int32 *pminy,
1102  l_int32 *pmaxy)
1103 {
1104 FILLSEG *fseg;
1105 L_STACK *auxstack;
1106 
1107  PROCNAME("pushFillsegBB");
1108 
1109  if (!stack) {
1110  L_ERROR("stack not defined\n", procName);
1111  return;
1112  }
1113 
1114  *pminx = L_MIN(*pminx, xleft);
1115  *pmaxx = L_MAX(*pmaxx, xright);
1116  *pminy = L_MIN(*pminy, y);
1117  *pmaxy = L_MAX(*pmaxy, y);
1118 
1119  if (y + dy >= 0 && y + dy <= ymax) {
1120  if ((auxstack = stack->auxstack) == NULL) {
1121  L_ERROR("auxstack not defined\n", procName);
1122  return;
1123  }
1124 
1125  /* Get a fillseg to use */
1126  if (lstackGetCount(auxstack) > 0)
1127  fseg = (FILLSEG *)lstackRemove(auxstack);
1128  else
1129  fseg = (FILLSEG *)LEPT_CALLOC(1, sizeof(FILLSEG));
1130  fseg->xleft = xleft;
1131  fseg->xright = xright;
1132  fseg->y = y;
1133  fseg->dy = dy;
1134  lstackAdd(stack, fseg);
1135  }
1136 }
1137 
1138 
1157 static void
1159  l_int32 xleft,
1160  l_int32 xright,
1161  l_int32 y,
1162  l_int32 dy,
1163  l_int32 ymax)
1164 {
1165 FILLSEG *fseg;
1166 L_STACK *auxstack;
1167 
1168  PROCNAME("pushFillseg");
1169 
1170  if (!stack) {
1171  L_ERROR("stack not defined\n", procName);
1172  return;
1173  }
1174 
1175  if (y + dy >= 0 && y + dy <= ymax) {
1176  if ((auxstack = stack->auxstack) == NULL) {
1177  L_ERROR("auxstack not defined\n", procName);
1178  return;
1179  }
1180 
1181  /* Get a fillseg to use */
1182  if (lstackGetCount(auxstack) > 0)
1183  fseg = (FILLSEG *)lstackRemove(auxstack);
1184  else
1185  fseg = (FILLSEG *)LEPT_CALLOC(1, sizeof(FILLSEG));
1186  fseg->xleft = xleft;
1187  fseg->xright = xright;
1188  fseg->y = y;
1189  fseg->dy = dy;
1190  lstackAdd(stack, fseg);
1191  }
1192 }
1193 
1194 
1212 static void
1214  l_int32 *pxleft,
1215  l_int32 *pxright,
1216  l_int32 *py,
1217  l_int32 *pdy)
1218 {
1219 FILLSEG *fseg;
1220 L_STACK *auxstack;
1221 
1222  PROCNAME("popFillseg");
1223 
1224  if (!stack) {
1225  L_ERROR("stack not defined\n", procName);
1226  return;
1227  }
1228  if ((auxstack = stack->auxstack) == NULL) {
1229  L_ERROR("auxstack not defined\n", procName);
1230  return;
1231  }
1232 
1233  if ((fseg = (FILLSEG *)lstackRemove(stack)) == NULL)
1234  return;
1235 
1236  *pxleft = fseg->xleft;
1237  *pxright = fseg->xright;
1238  *py = fseg->y + fseg->dy; /* this now points to the new line */
1239  *pdy = fseg->dy;
1240 
1241  /* Save it for re-use */
1242  lstackAdd(auxstack, fseg);
1243 }
BOX * pixSeedfill4BB(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill4BB()
Definition: conncomp.c:631
l_ok pixSeedfill4(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill4()
Definition: conncomp.c:896
l_int32 lept_mkdir(const char *subdir)
lept_mkdir()
Definition: utils2.c:2218
The struct FillSeg is used by the Heckbert seedfill algorithm to hold information about image segment...
Definition: conncomp.c:103
BOX * pixSeedfillBB(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity)
pixSeedfillBB()
Definition: conncomp.c:568
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
Definition: stack.c:124
struct Boxa * boxa
Definition: pix.h:461
l_int32 nextOnPixelInRaster(PIX *pixs, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
nextOnPixelInRaster()
Definition: conncomp.c:457
PIXA * pixaCreate(l_int32 n)
pixaCreate()
Definition: pixabasic.c:167
BOX * pixSeedfill8BB(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill8BB()
Definition: conncomp.c:746
l_int32 lstackGetCount(L_STACK *lstack)
lstackGetCount()
Definition: stack.c:252
Definition: pix.h:712
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
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
l_int32 y
Definition: pix.h:483
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306
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:1093
BOXA * boxaCopy(BOXA *boxa, l_int32 copyflag)
boxaCopy()
Definition: boxbasic.c:537
void boxaDestroy(BOXA **pboxa)
boxaDestroy()
Definition: boxbasic.c:583
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
l_int32 y
Definition: conncomp.c:107
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:491
#define GET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:123
PIX * pixClipRectangle(PIX *pixs, BOX *box, BOX **pboxc)
pixClipRectangle()
Definition: pix5.c:1026
Definition: pix.h:491
l_ok pixSeedfill(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity)
pixSeedfill()
Definition: conncomp.c:852
l_ok lstackAdd(L_STACK *lstack, void *item)
lstackAdd()
Definition: stack.c:170
#define CLEAR_DATA_BIT(pdata, n)
Definition: arrayaccess.h:131
BOXA * pixConnComp(PIX *pixs, PIXA **ppixa, l_int32 connectivity)
pixConnComp()
Definition: conncomp.c:151
l_ok pixaAddPix(PIXA *pixa, PIX *pix, l_int32 copyflag)
pixaAddPix()
Definition: pixabasic.c:506
PIX * pixXor(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixXor()
Definition: pix3.c:1688
void * lstackRemove(L_STACK *lstack)
lstackRemove()
Definition: stack.c:202
l_int32 w
Definition: pix.h:484
BOXA * pixConnCompBB(PIX *pixs, l_int32 connectivity)
pixConnCompBB()
Definition: conncomp.c:310
l_ok pixCountPixels(PIX *pixs, l_int32 *pcount, l_int32 *tab8)
pixCountPixels()
Definition: pix3.c:1937
l_ok boxaAddBox(BOXA *boxa, BOX *box, l_int32 copyflag)
boxaAddBox()
Definition: boxbasic.c:620
L_STACK * lstackCreate(l_int32 n)
lstackCreate()
Definition: stack.c:82
l_ok pixSetPadBits(PIX *pix, l_int32 val)
pixSetPadBits()
Definition: pix2.c:1382
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
Definition: pix.h:711
l_int32 x
Definition: pix.h:482
Definition: pix.h:455
l_int32 xright
Definition: conncomp.c:106
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
BOXA * pixConnCompPixa(PIX *pixs, PIXA **ppixa, l_int32 connectivity)
pixConnCompPixa()
Definition: conncomp.c:195
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:1158
struct L_Stack * auxstack
Definition: stack.h:64
l_int32 dy
Definition: conncomp.c:108
static void popFillseg(L_STACK *stack, l_int32 *pxleft, l_int32 *pxright, l_int32 *py, l_int32 *pdy)
popFillseg()
Definition: conncomp.c:1213
l_int32 h
Definition: pix.h:485
Definition: pix.h:138
l_ok pixZero(PIX *pix, l_int32 *pempty)
pixZero()
Definition: pix3.c:1815
BOXA * boxaCreate(l_int32 n)
boxaCreate()
Definition: boxbasic.c:502
#define PIX_SRC
Definition: pix.h:330
l_int32 xleft
Definition: conncomp.c:105
l_ok pixSeedfill8(PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
pixSeedfill8()
Definition: conncomp.c:990
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_ok pixCountConnComp(PIX *pixs, l_int32 connectivity, l_int32 *pcount)
pixCountConnComp()
Definition: conncomp.c:394
Definition: stack.h:59
#define PIX_DST
Definition: pix.h:331