1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * conncomp.c
18 *
19 * Connected component counting and extraction, using Heckbert's
20 * stack-based filling algorithm.
21 *
22 * 4- and 8-connected components: counts, bounding boxes and images
23 *
24 * Top-level calls:
25 * BOXA *pixConnComp()
26 * BOXA *pixConnCompPixa()
27 * BOXA *pixConnCompBB()
28 * l_int32 pixCountConnComp()
29 *
30 * Identify the next c.c. to be erased:
31 * l_int32 nextOnPixelInRaster()
32 * l_int32 nextOnPixelInRasterLow()
33 *
34 * Erase the c.c., saving the b.b.:
35 * BOX *pixSeedfillBB()
36 * BOX *pixSeedfill4BB()
37 * BOX *pixSeedfill8BB()
38 *
39 * Just erase the c.c.:
40 * l_int32 pixSeedfill()
41 * l_int32 pixSeedfill4()
42 * l_int32 pixSeedfill8()
43 *
44 * Static stack helper functions for single raster line seedfill:
45 * static void pushFillsegBB()
46 * static void pushFillseg()
47 * static void popFillseg()
48 *
49 * The basic method in pixConnCompBB() is very simple. We scan the
50 * image in raster order, looking for the next ON pixel. When it
51 * is found, we erase it and every pixel of the 4- or 8-connected
52 * component to which it belongs, using Heckbert's seedfill
53 * algorithm. As pixels are erased, we keep track of the
54 * minimum rectangle that encloses all erased pixels; after
55 * the connected component has been erased, we save its
56 * bounding box in an array of boxes. When all pixels in the
57 * image have been erased, we have an array that describes every
58 * 4- or 8-connected component in terms of its bounding box.
59 *
60 * pixConnCompPixa() is a slight variation on pixConnCompBB(),
61 * where we additionally save an array of images (in a Pixa)
62 * of each of the 4- or 8-connected components. This is done trivially
63 * by maintaining two temporary images. We erase a component from one,
64 * and use the bounding box to extract the pixels within the b.b.
65 * from each of the two images. An XOR between these subimages
66 * gives the erased component. Then we erase the component from the
67 * second image using the XOR again, with the extracted component
68 * placed on the second image at the location of the bounding box.
69 * Rasterop does all the work. At the end, we have an array
70 * of the 4- or 8-connected components, as well as an array of the
71 * bounding boxes that describe where they came from in the original image.
72 *
73 * If you just want the number of connected components, pixCountConnComp()
74 * is a bit faster than pixConnCompBB(), because it doesn't have to
75 * keep track of the bounding rectangles for each c.c.
76 */
77
78 #include <stdio.h>
79 #include <stdlib.h>
80 #include "allheaders.h"
81
82
83 /*
84 * The struct FillSeg is used by the Heckbert seedfill algorithm to
85 * hold information about image segments that are waiting to be
86 * investigated. We use two Stacks, one to hold the FillSegs in use,
87 * and an auxiliary Stack as a reservoir to hold FillSegs for re-use.
88 */
89 struct FillSeg
90 {
91 l_int32 xleft; /* left edge of run */
92 l_int32 xright; /* right edge of run */
93 l_int32 y; /* run y */
94 l_int32 dy; /* parent segment direction: 1 above, -1 below) */
95 };
96 typedef struct FillSeg FILLSEG;
97
98
99 /* Static accessors for FillSegs on a stack */
100 static void pushFillsegBB(L_STACK *lstack, l_int32 xleft, l_int32 xright,
101 l_int32 y, l_int32 dy, l_int32 ymax,
102 l_int32 *pminx, l_int32 *pmaxx,
103 l_int32 *pminy, l_int32 *pmaxy);
104 static void pushFillseg(L_STACK *lstack, l_int32 xleft, l_int32 xright,
105 l_int32 y, l_int32 dy, l_int32 ymax);
106 static void popFillseg(L_STACK *lstack, l_int32 *pxleft, l_int32 *pxright,
107 l_int32 *py, l_int32 *pdy);
108
109
110 #ifndef NO_CONSOLE_IO
111 #define DEBUG 0
112 #endif /* ~NO_CONSOLE_IO */
113
114
115 /*-----------------------------------------------------------------------*
116 * Bounding boxes of 4 Connected Components *
117 *-----------------------------------------------------------------------*/
118 /*!
119 * pixConnComp()
120 *
121 * Input: pixs (1 bpp)
122 * &pixa (<optional return> pixa of each c.c.)
123 * connectivity (4 or 8)
124 * Return: boxa, or null on error
125 *
126 * Notes:
127 * (1) This is the top-level call for getting bounding boxes or
128 * a pixa of the components, and it can be used instead
129 * of either pixConnCompBB() or pixConnCompPixa(), rsp.
130 */
131 BOXA *
pixConnComp(PIX * pixs,PIXA ** ppixa,l_int32 connectivity)132 pixConnComp(PIX *pixs,
133 PIXA **ppixa,
134 l_int32 connectivity)
135 {
136
137 PROCNAME("pixConnComp");
138
139 if (ppixa) *ppixa = NULL;
140 if (!pixs)
141 return (BOXA *)ERROR_PTR("pixs not defined", procName, NULL);
142 if (pixGetDepth(pixs) != 1)
143 return (BOXA *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
144 if (connectivity != 4 && connectivity != 8)
145 return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
146
147 if (!ppixa)
148 return pixConnCompBB(pixs, connectivity);
149 else
150 return pixConnCompPixa(pixs, ppixa, connectivity);
151 }
152
153
154 /*!
155 * pixConnCompPixa()
156 *
157 * Input: pixs (1 bpp)
158 * &pixa (<return> pixa of each c.c.)
159 * connectivity (4 or 8)
160 * Return: boxa, or null on error
161 *
162 * Notes:
163 * (1) This finds bounding boxes of 4- or 8-connected components
164 * in a binary image, and saves images of each c.c
165 * in a pixa array.
166 * (2) It sets up 2 temporary pix, and for each c.c. that is
167 * located in raster order, it erases the c.c. from one pix,
168 * then uses the b.b. to extract the c.c. from the two pix using
169 * an XOR, and finally erases the c.c. from the second pix.
170 * (3) A clone of the returned boxa (where all boxes in the array
171 * are clones) is inserted into the pixa.
172 * (4) If the input is valid, this always returns a boxa and a pixa.
173 * If pixs is empty, the boxa and pixa will be empty.
174 */
175 BOXA *
pixConnCompPixa(PIX * pixs,PIXA ** ppixa,l_int32 connectivity)176 pixConnCompPixa(PIX *pixs,
177 PIXA **ppixa,
178 l_int32 connectivity)
179 {
180 l_int32 h, iszero;
181 l_int32 x, y, xstart, ystart;
182 PIX *pixt1, *pixt2, *pixt3, *pixt4;
183 PIXA *pixa;
184 BOX *box;
185 BOXA *boxa;
186 L_STACK *lstack, *auxstack;
187
188 PROCNAME("pixConnCompPixa");
189
190 if (!ppixa)
191 return (BOXA *)ERROR_PTR("&pixa not defined", procName, NULL);
192 *ppixa = NULL;
193 if (!pixs || pixGetDepth(pixs) != 1)
194 return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
195 if (connectivity != 4 && connectivity != 8)
196 return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
197
198 pixa = pixaCreate(0);
199 *ppixa = pixa;
200 pixZero(pixs, &iszero);
201 if (iszero)
202 return boxaCreate(1); /* return empty boxa */
203
204 if ((pixt1 = pixCopy(NULL, pixs)) == NULL)
205 return (BOXA *)ERROR_PTR("pixt1 not made", procName, NULL);
206 if ((pixt2 = pixCopy(NULL, pixs)) == NULL)
207 return (BOXA *)ERROR_PTR("pixt2 not made", procName, NULL);
208
209 h = pixGetHeight(pixs);
210 if ((lstack = lstackCreate(h)) == NULL)
211 return (BOXA *)ERROR_PTR("lstack not made", procName, NULL);
212 if ((auxstack = lstackCreate(0)) == NULL)
213 return (BOXA *)ERROR_PTR("auxstack not made", procName, NULL);
214 lstack->auxstack = auxstack;
215 if ((boxa = boxaCreate(0)) == NULL)
216 return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
217
218 xstart = 0;
219 ystart = 0;
220 while (1)
221 {
222 if (!nextOnPixelInRaster(pixt1, xstart, ystart, &x, &y))
223 break;
224
225 if ((box = pixSeedfillBB(pixt1, lstack, x, y, connectivity)) == NULL)
226 return (BOXA *)ERROR_PTR("box not made", procName, NULL);
227 boxaAddBox(boxa, box, L_INSERT);
228
229 /* Save the c.c. and remove from pixt2 as well */
230 pixt3 = pixClipRectangle(pixt1, box, NULL);
231 pixt4 = pixClipRectangle(pixt2, box, NULL);
232 pixXor(pixt3, pixt3, pixt4);
233 pixRasterop(pixt2, box->x, box->y, box->w, box->h, PIX_SRC ^ PIX_DST,
234 pixt3, 0, 0);
235 pixaAddPix(pixa, pixt3, L_INSERT);
236 pixDestroy(&pixt4);
237
238 xstart = x;
239 ystart = y;
240 }
241
242 #if DEBUG
243 pixCountPixels(pixt1, &iszero, NULL);
244 fprintf(stderr, "Number of remaining pixels = %d\n", iszero);
245 pixWrite("junkremain", pixt1, IFF_PNG);
246 #endif /* DEBUG */
247
248 /* Remove old boxa of pixa and replace with a clone copy */
249 boxaDestroy(&pixa->boxa);
250 pixa->boxa = boxaCopy(boxa, L_CLONE);
251
252 /* Cleanup, freeing the fillsegs on each stack */
253 lstackDestroy(&lstack, TRUE);
254 pixDestroy(&pixt1);
255 pixDestroy(&pixt2);
256
257 return boxa;
258 }
259
260
261 /*!
262 * pixConnCompBB()
263 *
264 * Input: pixs (1 bpp)
265 * connectivity (4 or 8)
266 * Return: boxa, or null on error
267 *
268 * Notes:
269 * (1) Finds bounding boxes of 4- or 8-connected components
270 * in a binary image.
271 * (2) This works on a copy of the input pix. The c.c. are located
272 * in raster order and erased one at a time. In the process,
273 * the b.b. is computed and saved.
274 */
275 BOXA *
pixConnCompBB(PIX * pixs,l_int32 connectivity)276 pixConnCompBB(PIX *pixs,
277 l_int32 connectivity)
278 {
279 l_int32 h, iszero;
280 l_int32 x, y, xstart, ystart;
281 PIX *pixt;
282 BOX *box;
283 BOXA *boxa;
284 L_STACK *lstack, *auxstack;
285
286 PROCNAME("pixConnCompBB");
287
288 if (!pixs || pixGetDepth(pixs) != 1)
289 return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
290 if (connectivity != 4 && connectivity != 8)
291 return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
292
293 pixZero(pixs, &iszero);
294 if (iszero)
295 return boxaCreate(1); /* return empty boxa */
296
297 if ((pixt = pixCopy(NULL, pixs)) == NULL)
298 return (BOXA *)ERROR_PTR("pixt not made", procName, NULL);
299
300 h = pixGetHeight(pixs);
301 if ((lstack = lstackCreate(h)) == NULL)
302 return (BOXA *)ERROR_PTR("lstack not made", procName, NULL);
303 if ((auxstack = lstackCreate(0)) == NULL)
304 return (BOXA *)ERROR_PTR("auxstack not made", procName, NULL);
305 lstack->auxstack = auxstack;
306 if ((boxa = boxaCreate(0)) == NULL)
307 return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
308
309 xstart = 0;
310 ystart = 0;
311 while (1)
312 {
313 if (!nextOnPixelInRaster(pixt, xstart, ystart, &x, &y))
314 break;
315
316 if ((box = pixSeedfillBB(pixt, lstack, x, y, connectivity)) == NULL)
317 return (BOXA *)ERROR_PTR("box not made", procName, NULL);
318 boxaAddBox(boxa, box, L_INSERT);
319
320 xstart = x;
321 ystart = y;
322 }
323
324 #if DEBUG
325 pixCountPixels(pixt, &iszero, NULL);
326 fprintf(stderr, "Number of remaining pixels = %d\n", iszero);
327 pixWrite("junkremain", pixt1, IFF_PNG);
328 #endif /* DEBUG */
329
330 /* Cleanup, freeing the fillsegs on each stack */
331 lstackDestroy(&lstack, TRUE);
332 pixDestroy(&pixt);
333
334 return boxa;
335 }
336
337
338 /*!
339 * pixCountConnComp()
340 *
341 * Input: pixs (1 bpp)
342 * connectivity (4 or 8)
343 * &count (<return>
344 * Return: 0 if OK, 1 on error
345 *
346 * Notes:
347 * (1) This is the top-level call for getting the number of
348 * 4- or 8-connected components in a 1 bpp image.
349 * (2) It works on a copy of the input pix. The c.c. are located
350 * in raster order and erased one at a time.
351 */
352 l_int32
pixCountConnComp(PIX * pixs,l_int32 connectivity,l_int32 * pcount)353 pixCountConnComp(PIX *pixs,
354 l_int32 connectivity,
355 l_int32 *pcount)
356 {
357 l_int32 h, iszero;
358 l_int32 x, y, xstart, ystart;
359 PIX *pixt;
360 L_STACK *lstack, *auxstack;
361
362 PROCNAME("pixCountConnComp");
363
364 if (!pcount)
365 return ERROR_INT("&count not defined", procName, 1);
366 *pcount = 0; /* initialize the count to 0 */
367 if (!pixs || pixGetDepth(pixs) != 1)
368 return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
369 if (connectivity != 4 && connectivity != 8)
370 return ERROR_INT("connectivity not 4 or 8", procName, 1);
371
372 pixZero(pixs, &iszero);
373 if (iszero)
374 return 0;
375
376 if ((pixt = pixCopy(NULL, pixs)) == NULL)
377 return ERROR_INT("pixt not made", procName, 1);
378
379 h = pixGetDepth(pixs);
380 if ((lstack = lstackCreate(h)) == NULL)
381 return ERROR_INT("lstack not made", procName, 1);
382 if ((auxstack = lstackCreate(0)) == NULL)
383 return ERROR_INT("auxstack not made", procName, 1);
384 lstack->auxstack = auxstack;
385
386 xstart = 0;
387 ystart = 0;
388 while (1)
389 {
390 if (!nextOnPixelInRaster(pixt, xstart, ystart, &x, &y))
391 break;
392
393 pixSeedfill(pixt, lstack, x, y, connectivity);
394 (*pcount)++;
395 xstart = x;
396 ystart = y;
397 }
398
399 /* Cleanup, freeing the fillsegs on each stack */
400 lstackDestroy(&lstack, TRUE);
401 pixDestroy(&pixt);
402
403 return 0;
404 }
405
406
407 /*!
408 * nextOnPixelInRaster()
409 *
410 * Input: pixs (1 bpp)
411 * xstart, ystart (starting point for search)
412 * &x, &y (<return> coord value of next ON pixel)
413 * Return: 1 if a pixel is found; 0 otherwise or on error
414 */
415 l_int32
nextOnPixelInRaster(PIX * pixs,l_int32 xstart,l_int32 ystart,l_int32 * px,l_int32 * py)416 nextOnPixelInRaster(PIX *pixs,
417 l_int32 xstart,
418 l_int32 ystart,
419 l_int32 *px,
420 l_int32 *py)
421 {
422 l_int32 w, h, d, wpl;
423 l_uint32 *data;
424
425 PROCNAME("nextOnPixelInRaster");
426
427 if (!pixs)
428 return ERROR_INT("pixs not defined", procName, 0);
429 pixGetDimensions(pixs, &w, &h, &d);
430 if (d != 1)
431 return ERROR_INT("pixs not 1 bpp", procName, 0);
432
433 wpl = pixGetWpl(pixs);
434 data = pixGetData(pixs);
435 return nextOnPixelInRasterLow(data, w, h, wpl, xstart, ystart, px, py);
436 }
437
438
439 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)440 nextOnPixelInRasterLow(l_uint32 *data,
441 l_int32 w,
442 l_int32 h,
443 l_int32 wpl,
444 l_int32 xstart,
445 l_int32 ystart,
446 l_int32 *px,
447 l_int32 *py)
448 {
449 l_int32 i, x, y, xend, startword;
450 l_uint32 *line, *pword;
451
452 /* Look at the first word */
453 line = data + ystart * wpl;
454 pword = line + (xstart / 32);
455 if (*pword) {
456 xend = xstart - (xstart % 32) + 31;
457 for (x = xstart; x <= xend && x < w; x++) {
458 if (GET_DATA_BIT(line, x)) {
459 *px = x;
460 *py = ystart;
461 return 1;
462 }
463 }
464 }
465
466 /* Continue with the rest of the line */
467 startword = (xstart / 32) + 1;
468 x = 32 * startword;
469 for (pword = line + startword; x < w; pword++, x += 32) {
470 if (*pword) {
471 for (i = 0; i < 32 && x < w; i++, x++) {
472 if (GET_DATA_BIT(line, x)) {
473 *px = x;
474 *py = ystart;
475 return 1;
476 }
477 }
478 }
479 }
480
481 /* Continue with following lines */
482 for (y = ystart + 1; y < h; y++) {
483 line = data + y * wpl;
484 for (pword = line, x = 0; x < w; pword++, x += 32) {
485 if (*pword) {
486 for (i = 0; i < 32 && x < w; i++, x++) {
487 if (GET_DATA_BIT(line, x)) {
488 *px = x;
489 *py = y;
490 return 1;
491 }
492 }
493 }
494 }
495 }
496
497 return 0;
498 }
499
500
501 /*!
502 * pixSeedfillBB()
503 *
504 * Input: pixs (1 bpp)
505 * lstack (for holding fillsegs)
506 * x,y (location of seed pixel)
507 * connectivity (4 or 8)
508 * Return: box or null on error
509 *
510 * Notes:
511 * (1) This is the high-level interface to Paul Heckbert's
512 * stack-based seedfill algorithm.
513 */
514 BOX *
pixSeedfillBB(PIX * pixs,L_STACK * lstack,l_int32 x,l_int32 y,l_int32 connectivity)515 pixSeedfillBB(PIX *pixs,
516 L_STACK *lstack,
517 l_int32 x,
518 l_int32 y,
519 l_int32 connectivity)
520 {
521 BOX *box;
522
523 PROCNAME("pixSeedfillBB");
524
525 if (!pixs || pixGetDepth(pixs) != 1)
526 return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
527 if (!lstack)
528 return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
529 if (connectivity != 4 && connectivity != 8)
530 return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
531
532 if (connectivity == 4) {
533 if ((box = pixSeedfill4BB(pixs, lstack, x, y)) == NULL)
534 return (BOX *)ERROR_PTR("box not made", procName, NULL);
535 }
536 else if (connectivity == 8) {
537 if ((box = pixSeedfill8BB(pixs, lstack, x, y)) == NULL)
538 return (BOX *)ERROR_PTR("box not made", procName, NULL);
539 }
540 else
541 return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
542
543 return box;
544 }
545
546
547 /*!
548 * pixSeedfill4BB()
549 *
550 * Input: pixs (1 bpp)
551 * lstack (for holding fillsegs)
552 * x,y (location of seed pixel)
553 * Return: box or null on error.
554 *
555 * Notes:
556 * (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
557 * (2) This operates on the input 1 bpp pix to remove the fg seed
558 * pixel, at (x,y), and all pixels that are 4-connected to it.
559 * The seed pixel at (x,y) must initially be ON.
560 * (3) Returns the bounding box of the erased 4-cc component.
561 * (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
562 * in "Graphic Gems", ed. Andrew Glassner, Academic
563 * Press, 1990. The algorithm description is given
564 * on pp. 275-277; working C code is on pp. 721-722.)
565 * The code here follows Heckbert's exactly, except
566 * we use function calls instead of macros for
567 * pushing data on and popping data off the stack.
568 * This makes sense to do because Heckbert's fixed-size
569 * stack with macros is dangerous: images exist that
570 * will overrun the stack and crash. The stack utility
571 * here grows dynamically as needed, and the fillseg
572 * structures that are not in use are stored in another
573 * stack for reuse. It should be noted that the
574 * overhead in the function calls (vs. macros) is negligible.
575 */
576 BOX *
pixSeedfill4BB(PIX * pixs,L_STACK * lstack,l_int32 x,l_int32 y)577 pixSeedfill4BB(PIX *pixs,
578 L_STACK *lstack,
579 l_int32 x,
580 l_int32 y)
581 {
582 l_int32 w, h, xstart, wpl, x1, x2, dy;
583 l_int32 xmax, ymax;
584 l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
585 l_uint32 *data, *line;
586 BOX *box;
587
588 PROCNAME("pixSeedfill4BB");
589
590 if (!pixs || pixGetDepth(pixs) != 1)
591 return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
592 if (!lstack)
593 return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
594
595 pixGetDimensions(pixs, &w, &h, NULL);
596 xmax = w - 1;
597 ymax = h - 1;
598 data = pixGetData(pixs);
599 wpl = pixGetWpl(pixs);
600 line = data + y * wpl;
601
602 /* Check pix value of seed; must be within the image and ON */
603 if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
604 return NULL;
605
606 /* Init stack to seed:
607 * Must first init b.b. values to prevent valgrind from complaining;
608 * then init b.b. boundaries correctly to seed. */
609 minx = miny = 100000;
610 maxx = maxy = 0;
611 pushFillsegBB(lstack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
612 pushFillsegBB(lstack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
613 minx = maxx = x;
614 miny = maxy = y;
615
616 while (lstackGetCount(lstack) > 0)
617 {
618 /* Pop segment off stack and fill a neighboring scan line */
619 popFillseg(lstack, &x1, &x2, &y, &dy);
620 line = data + y * wpl;
621
622 /* A segment of scanline y - dy for x1 <= x <= x2 was
623 * previously filled. We now explore adjacent pixels
624 * in scan line y. There are three regions: to the
625 * left of x1 - 1, between x1 and x2, and to the right of x2.
626 * These regions are handled differently. Leaks are
627 * possible expansions beyond the previous segment and
628 * going back in the -dy direction. These can happen
629 * for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
630 * are plugged with a push in the -dy (opposite) direction.
631 * And any segments found anywhere are always extended
632 * in the +dy direction. */
633 for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
634 CLEAR_DATA_BIT(line,x);
635 if (x >= x1) /* pix at x1 was off and was not cleared */
636 goto skip;
637 xstart = x + 1;
638 if (xstart < x1 - 1) /* leak on left? */
639 pushFillsegBB(lstack, xstart, x1 - 1, y, -dy,
640 ymax, &minx, &maxx, &miny, &maxy);
641
642 x = x1 + 1;
643 do {
644 for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
645 CLEAR_DATA_BIT(line, x);
646 pushFillsegBB(lstack, xstart, x - 1, y, dy,
647 ymax, &minx, &maxx, &miny, &maxy);
648 if (x > x2 + 1) /* leak on right? */
649 pushFillsegBB(lstack, x2 + 1, x - 1, y, -dy,
650 ymax, &minx, &maxx, &miny, &maxy);
651 skip: for (x++; x <= x2 &&
652 x <= xmax &&
653 (GET_DATA_BIT(line, x) == 0); x++)
654 ;
655 xstart = x;
656 } while (x <= x2 && x <= xmax);
657 }
658
659 if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
660 == NULL)
661 return (BOX *)ERROR_PTR("box not made", procName, NULL);
662 return box;
663 }
664
665
666 /*!
667 * pixSeedfill8BB()
668 *
669 * Input: pixs (1 bpp)
670 * lstack (for holding fillsegs)
671 * x,y (location of seed pixel)
672 * Return: box or null on error.
673 *
674 * Notes:
675 * (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
676 * (2) This operates on the input 1 bpp pix to remove the fg seed
677 * pixel, at (x,y), and all pixels that are 8-connected to it.
678 * The seed pixel at (x,y) must initially be ON.
679 * (3) Returns the bounding box of the erased 8-cc component.
680 * (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
681 * in "Graphic Gems", ed. Andrew Glassner, Academic
682 * Press, 1990. The algorithm description is given
683 * on pp. 275-277; working C code is on pp. 721-722.)
684 * The code here follows Heckbert's closely, except
685 * the leak checks are changed for 8 connectivity.
686 * See comments on pixSeedfill4BB() for more details.
687 */
688 BOX *
pixSeedfill8BB(PIX * pixs,L_STACK * lstack,l_int32 x,l_int32 y)689 pixSeedfill8BB(PIX *pixs,
690 L_STACK *lstack,
691 l_int32 x,
692 l_int32 y)
693 {
694 l_int32 w, h, xstart, wpl, x1, x2, dy;
695 l_int32 xmax, ymax;
696 l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
697 l_uint32 *data, *line;
698 BOX *box;
699
700 PROCNAME("pixSeedfill8BB");
701
702 if (!pixs || pixGetDepth(pixs) != 1)
703 return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
704 if (!lstack)
705 return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
706
707 pixGetDimensions(pixs, &w, &h, NULL);
708 xmax = w - 1;
709 ymax = h - 1;
710 data = pixGetData(pixs);
711 wpl = pixGetWpl(pixs);
712 line = data + y * wpl;
713
714 /* Check pix value of seed; must be ON */
715 if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
716 return NULL;
717
718 /* Init stack to seed:
719 * Must first init b.b. values to prevent valgrind from complaining;
720 * then init b.b. boundaries correctly to seed. */
721 minx = miny = 100000;
722 maxx = maxy = 0;
723 pushFillsegBB(lstack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
724 pushFillsegBB(lstack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
725 minx = maxx = x;
726 miny = maxy = y;
727
728 while (lstackGetCount(lstack) > 0)
729 {
730 /* Pop segment off stack and fill a neighboring scan line */
731 popFillseg(lstack, &x1, &x2, &y, &dy);
732 line = data + y * wpl;
733
734 /* A segment of scanline y - dy for x1 <= x <= x2 was
735 * previously filled. We now explore adjacent pixels
736 * in scan line y. There are three regions: to the
737 * left of x1, between x1 and x2, and to the right of x2.
738 * These regions are handled differently. Leaks are
739 * possible expansions beyond the previous segment and
740 * going back in the -dy direction. These can happen
741 * for x < x1 and for x > x2. Any "leak" segments
742 * are plugged with a push in the -dy (opposite) direction.
743 * And any segments found anywhere are always extended
744 * in the +dy direction. */
745 for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
746 CLEAR_DATA_BIT(line,x);
747 if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
748 goto skip;
749 xstart = x + 1;
750 if (xstart < x1) /* leak on left? */
751 pushFillsegBB(lstack, xstart, x1 - 1, y, -dy,
752 ymax, &minx, &maxx, &miny, &maxy);
753
754 x = x1;
755 do {
756 for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
757 CLEAR_DATA_BIT(line, x);
758 pushFillsegBB(lstack, xstart, x - 1, y, dy,
759 ymax, &minx, &maxx, &miny, &maxy);
760 if (x > x2) /* leak on right? */
761 pushFillsegBB(lstack, x2 + 1, x - 1, y, -dy,
762 ymax, &minx, &maxx, &miny, &maxy);
763 skip: for (x++; x <= x2 + 1 &&
764 x <= xmax &&
765 (GET_DATA_BIT(line, x) == 0); x++)
766 ;
767 xstart = x;
768 } while (x <= x2 + 1 && x <= xmax);
769 }
770
771 if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
772 == NULL)
773 return (BOX *)ERROR_PTR("box not made", procName, NULL);
774 return box;
775 }
776
777
778 /*!
779 * pixSeedfill()
780 *
781 * Input: pixs (1 bpp)
782 * lstack (for holding fillsegs)
783 * x,y (location of seed pixel)
784 * connectivity (4 or 8)
785 * Return: 0 if OK, 1 on error
786 *
787 * Notes:
788 * (1) This removes the component from pixs with a fg pixel at (x,y).
789 * (2) See pixSeedfill4() and pixSeedfill8() for details.
790 */
791 l_int32
pixSeedfill(PIX * pixs,L_STACK * lstack,l_int32 x,l_int32 y,l_int32 connectivity)792 pixSeedfill(PIX *pixs,
793 L_STACK *lstack,
794 l_int32 x,
795 l_int32 y,
796 l_int32 connectivity)
797 {
798 l_int32 retval;
799
800 PROCNAME("pixSeedfill");
801
802 if (!pixs || pixGetDepth(pixs) != 1)
803 return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
804 if (!lstack)
805 return ERROR_INT("lstack not defined", procName, 1);
806 if (connectivity != 4 && connectivity != 8)
807 return ERROR_INT("connectivity not 4 or 8", procName, 1);
808
809 if (connectivity == 4)
810 retval = pixSeedfill4(pixs, lstack, x, y);
811 else /* connectivity == 8 */
812 retval = pixSeedfill8(pixs, lstack, x, y);
813
814 return retval;
815 }
816
817
818 /*!
819 * pixSeedfill4()
820 *
821 * Input: pixs (1 bpp)
822 * lstack (for holding fillsegs)
823 * x,y (location of seed pixel)
824 * Return: 0 if OK, 1 on error
825 *
826 * Notes:
827 * (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
828 * (2) This operates on the input 1 bpp pix to remove the fg seed
829 * pixel, at (x,y), and all pixels that are 4-connected to it.
830 * The seed pixel at (x,y) must initially be ON.
831 * (3) Reference: see pixSeedFill4BB()
832 */
833 l_int32
pixSeedfill4(PIX * pixs,L_STACK * lstack,l_int32 x,l_int32 y)834 pixSeedfill4(PIX *pixs,
835 L_STACK *lstack,
836 l_int32 x,
837 l_int32 y)
838 {
839 l_int32 w, h, xstart, wpl, x1, x2, dy;
840 l_int32 xmax, ymax;
841 l_uint32 *data, *line;
842
843 PROCNAME("pixSeedfill4");
844
845 if (!pixs || pixGetDepth(pixs) != 1)
846 return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
847 if (!lstack)
848 return ERROR_INT("lstack not defined", procName, 1);
849
850 pixGetDimensions(pixs, &w, &h, NULL);
851 xmax = w - 1;
852 ymax = h - 1;
853 data = pixGetData(pixs);
854 wpl = pixGetWpl(pixs);
855 line = data + y * wpl;
856
857 /* Check pix value of seed; must be within the image and ON */
858 if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
859 return 0;
860
861 /* Init stack to seed */
862 pushFillseg(lstack, x, x, y, 1, ymax);
863 pushFillseg(lstack, x, x, y + 1, -1, ymax);
864
865 while (lstackGetCount(lstack) > 0)
866 {
867 /* Pop segment off stack and fill a neighboring scan line */
868 popFillseg(lstack, &x1, &x2, &y, &dy);
869 line = data + y * wpl;
870
871 /* A segment of scanline y - dy for x1 <= x <= x2 was
872 * previously filled. We now explore adjacent pixels
873 * in scan line y. There are three regions: to the
874 * left of x1 - 1, between x1 and x2, and to the right of x2.
875 * These regions are handled differently. Leaks are
876 * possible expansions beyond the previous segment and
877 * going back in the -dy direction. These can happen
878 * for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
879 * are plugged with a push in the -dy (opposite) direction.
880 * And any segments found anywhere are always extended
881 * in the +dy direction. */
882 for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
883 CLEAR_DATA_BIT(line,x);
884 if (x >= x1) /* pix at x1 was off and was not cleared */
885 goto skip;
886 xstart = x + 1;
887 if (xstart < x1 - 1) /* leak on left? */
888 pushFillseg(lstack, xstart, x1 - 1, y, -dy, ymax);
889
890 x = x1 + 1;
891 do {
892 for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
893 CLEAR_DATA_BIT(line, x);
894 pushFillseg(lstack, xstart, x - 1, y, dy, ymax);
895 if (x > x2 + 1) /* leak on right? */
896 pushFillseg(lstack, x2 + 1, x - 1, y, -dy, ymax);
897 skip: for (x++; x <= x2 &&
898 x <= xmax &&
899 (GET_DATA_BIT(line, x) == 0); x++)
900 ;
901 xstart = x;
902 } while (x <= x2 && x <= xmax);
903 }
904
905 return 0;
906 }
907
908
909 /*!
910 * pixSeedfill8()
911 *
912 * Input: pixs (1 bpp)
913 * lstack (for holding fillsegs)
914 * x,y (location of seed pixel)
915 * Return: 0 if OK, 1 on error
916 *
917 * Notes:
918 * (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
919 * (2) This operates on the input 1 bpp pix to remove the fg seed
920 * pixel, at (x,y), and all pixels that are 8-connected to it.
921 * The seed pixel at (x,y) must initially be ON.
922 * (3) Reference: see pixSeedFill8BB()
923 */
924 l_int32
pixSeedfill8(PIX * pixs,L_STACK * lstack,l_int32 x,l_int32 y)925 pixSeedfill8(PIX *pixs,
926 L_STACK *lstack,
927 l_int32 x,
928 l_int32 y)
929 {
930 l_int32 w, h, xstart, wpl, x1, x2, dy;
931 l_int32 xmax, ymax;
932 l_uint32 *data, *line;
933
934 PROCNAME("pixSeedfill8");
935
936 if (!pixs || pixGetDepth(pixs) != 1)
937 return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
938 if (!lstack)
939 return ERROR_INT("lstack not defined", procName, 1);
940
941 pixGetDimensions(pixs, &w, &h, NULL);
942 xmax = w - 1;
943 ymax = h - 1;
944 data = pixGetData(pixs);
945 wpl = pixGetWpl(pixs);
946 line = data + y * wpl;
947
948 /* Check pix value of seed; must be ON */
949 if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
950 return 0;
951
952 /* Init stack to seed */
953 pushFillseg(lstack, x, x, y, 1, ymax);
954 pushFillseg(lstack, x, x, y + 1, -1, ymax);
955
956 while (lstackGetCount(lstack) > 0)
957 {
958 /* Pop segment off stack and fill a neighboring scan line */
959 popFillseg(lstack, &x1, &x2, &y, &dy);
960 line = data + y * wpl;
961
962 /* A segment of scanline y - dy for x1 <= x <= x2 was
963 * previously filled. We now explore adjacent pixels
964 * in scan line y. There are three regions: to the
965 * left of x1, between x1 and x2, and to the right of x2.
966 * These regions are handled differently. Leaks are
967 * possible expansions beyond the previous segment and
968 * going back in the -dy direction. These can happen
969 * for x < x1 and for x > x2. Any "leak" segments
970 * are plugged with a push in the -dy (opposite) direction.
971 * And any segments found anywhere are always extended
972 * in the +dy direction. */
973 for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
974 CLEAR_DATA_BIT(line,x);
975 if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
976 goto skip;
977 xstart = x + 1;
978 if (xstart < x1) /* leak on left? */
979 pushFillseg(lstack, xstart, x1 - 1, y, -dy, ymax);
980
981 x = x1;
982 do {
983 for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
984 CLEAR_DATA_BIT(line, x);
985 pushFillseg(lstack, xstart, x - 1, y, dy, ymax);
986 if (x > x2) /* leak on right? */
987 pushFillseg(lstack, x2 + 1, x - 1, y, -dy, ymax);
988 skip: for (x++; x <= x2 + 1 &&
989 x <= xmax &&
990 (GET_DATA_BIT(line, x) == 0); x++)
991 ;
992 xstart = x;
993 } while (x <= x2 + 1 && x <= xmax);
994 }
995
996 return 0;
997 }
998
999
1000
1001 /*-----------------------------------------------------------------------*
1002 * Static stack helper functions: push and pop fillsegs *
1003 *-----------------------------------------------------------------------*/
1004 /*!
1005 * pushFillsegBB()
1006 *
1007 * Input: lstack
1008 * xleft, xright
1009 * y
1010 * dy
1011 * ymax,
1012 * &minx (<return>)
1013 * &maxx (<return>)
1014 * &miny (<return>)
1015 * &maxy (<return>)
1016 * Return: void
1017 *
1018 * Notes:
1019 * (1) This adds a line segment to the stack, and returns its size.
1020 * (2) The auxiliary stack is used as a storage area to recycle
1021 * fillsegs that are no longer in use. We only calloc new
1022 * fillsegs if the auxiliary stack is empty.
1023 */
1024 static void
pushFillsegBB(L_STACK * lstack,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)1025 pushFillsegBB(L_STACK *lstack,
1026 l_int32 xleft,
1027 l_int32 xright,
1028 l_int32 y,
1029 l_int32 dy,
1030 l_int32 ymax,
1031 l_int32 *pminx,
1032 l_int32 *pmaxx,
1033 l_int32 *pminy,
1034 l_int32 *pmaxy)
1035 {
1036 FILLSEG *fseg;
1037 L_STACK *auxstack;
1038
1039 PROCNAME("pushFillsegBB");
1040
1041 if (!lstack)
1042 return ERROR_VOID(procName, "lstack not defined");
1043
1044 *pminx = L_MIN(*pminx, xleft);
1045 *pmaxx = L_MAX(*pmaxx, xright);
1046 *pminy = L_MIN(*pminy, y);
1047 *pmaxy = L_MAX(*pmaxy, y);
1048
1049 if (y + dy >= 0 && y + dy <= ymax) {
1050 if ((auxstack = lstack->auxstack) == NULL)
1051 return ERROR_VOID("auxstack not defined", procName);
1052
1053 /* Get a fillseg to use */
1054 if (lstackGetCount(auxstack) > 0)
1055 fseg = (FILLSEG *)lstackRemove(auxstack);
1056 else {
1057 if ((fseg = (FILLSEG *)CALLOC(1, sizeof(FILLSEG))) == NULL)
1058 return ERROR_VOID("fillseg not made", procName);
1059 }
1060
1061 fseg->xleft = xleft;
1062 fseg->xright = xright;
1063 fseg->y = y;
1064 fseg->dy = dy;
1065 lstackAdd(lstack, fseg);
1066 }
1067 return;
1068 }
1069
1070
1071 /*!
1072 * pushFillseg()
1073 *
1074 * Input: lstack
1075 * xleft, xright
1076 * y
1077 * dy
1078 * ymax
1079 * Return: void
1080 *
1081 * Notes:
1082 * (1) This adds a line segment to the stack.
1083 * (2) The auxiliary stack is used as a storage area to recycle
1084 * fillsegs that are no longer in use. We only calloc new
1085 * fillsegs if the auxiliary stack is empty.
1086 */
1087 static void
pushFillseg(L_STACK * lstack,l_int32 xleft,l_int32 xright,l_int32 y,l_int32 dy,l_int32 ymax)1088 pushFillseg(L_STACK *lstack,
1089 l_int32 xleft,
1090 l_int32 xright,
1091 l_int32 y,
1092 l_int32 dy,
1093 l_int32 ymax)
1094 {
1095 FILLSEG *fseg;
1096 L_STACK *auxstack;
1097
1098 PROCNAME("pushFillseg");
1099
1100 if (!lstack)
1101 return ERROR_VOID(procName, "lstack not defined");
1102
1103 if (y + dy >= 0 && y + dy <= ymax) {
1104 if ((auxstack = lstack->auxstack) == NULL)
1105 return ERROR_VOID("auxstack not defined", procName);
1106
1107 /* Get a fillseg to use */
1108 if (lstackGetCount(auxstack) > 0)
1109 fseg = (FILLSEG *)lstackRemove(auxstack);
1110 else {
1111 if ((fseg = (FILLSEG *)CALLOC(1, sizeof(FILLSEG))) == NULL)
1112 return ERROR_VOID("fillseg not made", procName);
1113 }
1114
1115 fseg->xleft = xleft;
1116 fseg->xright = xright;
1117 fseg->y = y;
1118 fseg->dy = dy;
1119 lstackAdd(lstack, fseg);
1120 }
1121 return;
1122 }
1123
1124
1125 /*!
1126 * popFillseg()
1127 *
1128 * Input: lstack
1129 * &xleft (<return>)
1130 * &xright (<return>)
1131 * &y (<return>)
1132 * &dy (<return>)
1133 * Return: void
1134 *
1135 * Notes:
1136 * (1) This removes a line segment from the stack, and returns its size.
1137 * (2) The surplussed fillseg is placed on the auxiliary stack
1138 * for future use.
1139 */
1140 static void
popFillseg(L_STACK * lstack,l_int32 * pxleft,l_int32 * pxright,l_int32 * py,l_int32 * pdy)1141 popFillseg(L_STACK *lstack,
1142 l_int32 *pxleft,
1143 l_int32 *pxright,
1144 l_int32 *py,
1145 l_int32 *pdy)
1146 {
1147 FILLSEG *fseg;
1148 L_STACK *auxstack;
1149
1150 PROCNAME("popFillseg");
1151
1152 if (!lstack)
1153 return ERROR_VOID("lstack not defined", procName);
1154 if ((auxstack = lstack->auxstack) == NULL)
1155 return ERROR_VOID("auxstack not defined", procName);
1156
1157 if ((fseg = (FILLSEG *)lstackRemove(lstack)) == NULL)
1158 return;
1159
1160 *pxleft = fseg->xleft;
1161 *pxright = fseg->xright;
1162 *py = fseg->y + fseg->dy; /* this now points to the new line */
1163 *pdy = fseg->dy;
1164
1165 /* Save it for re-use */
1166 lstackAdd(auxstack, fseg);
1167 return;
1168 }
1169
1170
1171
1172