Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/conncomp.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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
27 /*!
28 * \file conncomp.c
29 * <pre>
30 *
31 * Connected component counting and extraction, using Heckbert's
32 * stack-based filling algorithm.
33 *
34 * 4- and 8-connected components: counts, bounding boxes and images
35 *
36 * Top-level calls:
37 * BOXA *pixConnComp()
38 * BOXA *pixConnCompPixa()
39 * BOXA *pixConnCompBB()
40 * l_int32 pixCountConnComp()
41 *
42 * Identify the next c.c. to be erased:
43 * l_int32 nextOnPixelInRaster()
44 * static l_int32 nextOnPixelInRasterLow()
45 *
46 * Erase the c.c., saving the b.b.:
47 * BOX *pixSeedfillBB()
48 * BOX *pixSeedfill4BB()
49 * BOX *pixSeedfill8BB()
50 *
51 * Just erase the c.c.:
52 * l_int32 pixSeedfill()
53 * l_int32 pixSeedfill4()
54 * l_int32 pixSeedfill8()
55 *
56 * Static stack helper functions for single raster line seedfill:
57 * static void pushFillsegBB()
58 * static void pushFillseg()
59 * static void popFillseg()
60 *
61 * The basic method in pixConnCompBB() is very simple. We scan the
62 * image in raster order, looking for the next ON pixel. When it
63 * is found, we erase it and every pixel of the 4- or 8-connected
64 * component to which it belongs, using Heckbert's seedfill
65 * algorithm. As pixels are erased, we keep track of the
66 * minimum rectangle that encloses all erased pixels; after
67 * the connected component has been erased, we save its
68 * bounding box in an array of boxes. When all pixels in the
69 * image have been erased, we have an array that describes every
70 * 4- or 8-connected component in terms of its bounding box.
71 *
72 * pixConnCompPixa() is a slight variation on pixConnCompBB(),
73 * where we additionally save an array of images (in a Pixa)
74 * of each of the 4- or 8-connected components. This is done trivially
75 * by maintaining two temporary images. We erase a component from one,
76 * and use the bounding box to extract the pixels within the b.b.
77 * from each of the two images. An XOR between these subimages
78 * gives the erased component. Then we erase the component from the
79 * second image using the XOR again, with the extracted component
80 * placed on the second image at the location of the bounding box.
81 * Rasterop does all the work. At the end, we have an array
82 * of the 4- or 8-connected components, as well as an array of the
83 * bounding boxes that describe where they came from in the original image.
84 *
85 * If you just want the number of connected components, pixCountConnComp()
86 * is a bit faster than pixConnCompBB(), because it doesn't have to
87 * keep track of the bounding rectangles for each c.c.
88 * </pre>
89 */
90
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
98 /*!
99 * \brief The struct FillSeg is used by the Heckbert seedfill algorithm to
100 * hold information about image segments that are waiting to be
101 * investigated. We use two Stacks, one to hold the FillSegs in use,
102 * and an auxiliary Stack as a reservoir to hold FillSegs for re-use.
103 */
104 struct FillSeg
105 {
106 l_int32 xleft; /*!< left edge of run */
107 l_int32 xright; /*!< right edge of run */
108 l_int32 y; /*!< run y */
109 l_int32 dy; /*!< parent segment direction: 1 above, -1 below) */
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 *-----------------------------------------------------------------------*/
136 /*!
137 * \brief pixConnComp()
138 *
139 * \param[in] pixs 1 bpp
140 * \param[out] ppixa [optional] pixa of each c.c.
141 * \param[in] connectivity 4 or 8
142 * \return boxa, or NULL on error
143 *
144 * <pre>
145 * Notes:
146 * (1) This is the top-level call for getting bounding boxes or
147 * a pixa of the components, and it can be used instead
148 * of either pixConnCompBB() or pixConnCompPixa(), rsp.
149 * </pre>
150 */
151 BOXA *
152 pixConnComp(PIX *pixs,
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
170 /*!
171 * \brief pixConnCompPixa()
172 *
173 * \param[in] pixs 1 bpp
174 * \param[out] ppixa pixa of each c.c.
175 * \param[in] connectivity 4 or 8
176 * \return boxa, or NULL on error
177 *
178 * <pre>
179 * Notes:
180 * (1) This finds bounding boxes of 4- or 8-connected components
181 * in a binary image, and saves images of each c.c
182 * in a pixa array.
183 * (2) It sets up 2 temporary pix, and for each c.c. that is
184 * located in raster order, it erases the c.c. from one pix,
185 * then uses the b.b. to extract the c.c. from the two pix using
186 * an XOR, and finally erases the c.c. from the second pix.
187 * (3) A clone of the returned boxa (where all boxes in the array
188 * are clones) is inserted into the pixa.
189 * (4) If the input is valid, this always returns a boxa and a pixa.
190 * If pixs is empty, the boxa and pixa will be empty.
191 * </pre>
192 */
193 BOXA *
194 pixConnCompPixa(PIX *pixs,
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
290 /*!
291 * \brief pixConnCompBB()
292 *
293 * \param[in] pixs 1 bpp
294 * \param[in] connectivity 4 or 8
295 * \return boxa, or NULL on error
296 *
297 * <pre>
298 * Notes:
299 * (1) Finds bounding boxes of 4- or 8-connected components
300 * in a binary image.
301 * (2) This works on a copy of the input pix. The c.c. are located
302 * in raster order and erased one at a time. In the process,
303 * the b.b. is computed and saved.
304 * </pre>
305 */
306 BOXA *
307 pixConnCompBB(PIX *pixs,
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
374 /*!
375 * \brief pixCountConnComp()
376 *
377 * \param[in] pixs 1 bpp
378 * \param[in] connectivity 4 or 8
379 * \param[out] pcount
380 * \return 0 if OK, 1 on error
381 *
382 * Notes:
383 * (1 This is the top-level call for getting the number of
384 * 4- or 8-connected components in a 1 bpp image.
385 * 2 It works on a copy of the input pix. The c.c. are located
386 * in raster order and erased one at a time.
387 */
388 l_ok
389 pixCountConnComp(PIX *pixs,
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
441 /*!
442 * \brief nextOnPixelInRaster()
443 *
444 * \param[in] pixs 1 bpp
445 * \param[in] xstart, ystart starting point for search
446 * \param[out] px, py coord value of next ON pixel
447 * \return 1 if a pixel is found; 0 otherwise or on error
448 */
449 l_int32
450 nextOnPixelInRaster(PIX *pixs,
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
471 /*!
472 * \brief nextOnPixelInRasterLow()
473 *
474 * \param[in] data pix data
475 * \param[in] w, h width and height
476 * \param[in] wpl words per line
477 * \param[in] xstart, ystart starting point for search
478 * \param[out] px, py coord value of next ON pixel
479 * \return 1 if a pixel is found; 0 otherwise or on error
480 */
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
543 /*!
544 * \brief pixSeedfillBB()
545 *
546 * \param[in] pixs 1 bpp
547 * \param[in] stack for holding fillsegs
548 * \param[in] x,y location of seed pixel
549 * \param[in] connectivity 4 or 8
550 * \return box or NULL on error
551 *
552 * <pre>
553 * Notes:
554 * (1) This is the high-level interface to Paul Heckbert's
555 * stack-based seedfill algorithm.
556 * </pre>
557 */
558 BOX *
559 pixSeedfillBB(PIX *pixs,
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
588 /*!
589 * \brief pixSeedfill4BB()
590 *
591 * \param[in] pixs 1 bpp
592 * \param[in] stack for holding fillsegs
593 * \param[in] x,y location of seed pixel
594 * \return box or NULL on error.
595 *
596 * <pre>
597 * Notes:
598 * (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
599 * (2) This operates on the input 1 bpp pix to remove the fg seed
600 * pixel, at (x,y), and all pixels that are 4-connected to it.
601 * The seed pixel at (x,y) must initially be ON.
602 * (3) Returns the bounding box of the erased 4-cc component.
603 * (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
604 * in "Graphic Gems", ed. Andrew Glassner, Academic
605 * Press, 1990. The algorithm description is given
606 * on pp. 275-277; working C code is on pp. 721-722.)
607 * The code here follows Heckbert's exactly, except
608 * we use function calls instead of macros for
609 * pushing data on and popping data off the stack.
610 * This makes sense to do because Heckbert's fixed-size
611 * stack with macros is dangerous: images exist that
612 * will overrun the stack and crash. The stack utility
613 * here grows dynamically as needed, and the fillseg
614 * structures that are not in use are stored in another
615 * stack for reuse. It should be noted that the
616 * overhead in the function calls (vs. macros) is negligible.
617 * </pre>
618 */
619 BOX *
620 pixSeedfill4BB(PIX *pixs,
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
708 /*!
709 * \brief pixSeedfill8BB()
710 *
711 * \param[in] pixs 1 bpp
712 * \param[in] stack for holding fillsegs
713 * \param[in] x,y location of seed pixel
714 * \return box or NULL on error.
715 *
716 * <pre>
717 * Notes:
718 * (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
719 * (2) This operates on the input 1 bpp pix to remove the fg seed
720 * pixel, at (x,y), and all pixels that are 8-connected to it.
721 * The seed pixel at (x,y) must initially be ON.
722 * (3) Returns the bounding box of the erased 8-cc component.
723 * (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
724 * in "Graphic Gems", ed. Andrew Glassner, Academic
725 * Press, 1990. The algorithm description is given
726 * on pp. 275-277; working C code is on pp. 721-722.)
727 * The code here follows Heckbert's closely, except
728 * the leak checks are changed for 8 connectivity.
729 * See comments on pixSeedfill4BB() for more details.
730 * </pre>
731 */
732 BOX *
733 pixSeedfill8BB(PIX *pixs,
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
821 /*!
822 * \brief pixSeedfill()
823 *
824 * \param[in] pixs 1 bpp
825 * \param[in] stack for holding fillsegs
826 * \param[in] x,y location of seed pixel
827 * \param[in] connectivity 4 or 8
828 * \return 0 if OK, 1 on error
829 *
830 * <pre>
831 * Notes:
832 * (1) This removes the component from pixs with a fg pixel at (x,y).
833 * (2) See pixSeedfill4() and pixSeedfill8() for details.
834 * </pre>
835 */
836 l_ok
837 pixSeedfill(PIX *pixs,
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
861 /*!
862 * \brief pixSeedfill4()
863 *
864 * \param[in] pixs 1 bpp
865 * \param[in] stack for holding fillsegs
866 * \param[in] x,y location of seed pixel
867 * \return 0 if OK, 1 on error
868 *
869 * <pre>
870 * Notes:
871 * (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
872 * (2) This operates on the input 1 bpp pix to remove the fg seed
873 * pixel, at (x,y), and all pixels that are 4-connected to it.
874 * The seed pixel at (x,y) must initially be ON.
875 * (3) Reference: see pixSeedFill4BB()
876 * </pre>
877 */
878 l_ok
879 pixSeedfill4(PIX *pixs,
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
953 /*!
954 * \brief pixSeedfill8()
955 *
956 * \param[in] pixs 1 bpp
957 * \param[in] stack for holding fillsegs
958 * \param[in] x,y location of seed pixel
959 * \return 0 if OK, 1 on error
960 *
961 * <pre>
962 * Notes:
963 * (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
964 * (2) This operates on the input 1 bpp pix to remove the fg seed
965 * pixel, at (x,y), and all pixels that are 8-connected to it.
966 * The seed pixel at (x,y) must initially be ON.
967 * (3) Reference: see pixSeedFill8BB()
968 * </pre>
969 */
970 l_ok
971 pixSeedfill8(PIX *pixs,
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 *-----------------------------------------------------------------------*/
1049 /*!
1050 * \brief pushFillsegBB()
1051 *
1052 * \param[in] stack
1053 * \param[in] xleft, xright
1054 * \param[in] y
1055 * \param[in] dy
1056 * \param[in] ymax
1057 * \param[out] pminx minimum x
1058 * \param[out] pmaxx maximum x
1059 * \param[out] pminy minimum y
1060 * \param[out] pmaxy maximum y
1061 * \return void
1062 *
1063 * <pre>
1064 * Notes:
1065 * (1) This adds a line segment to the stack, and returns its size.
1066 * (2) The auxiliary stack is used as a storage area to recycle
1067 * fillsegs that are no longer in use. We only calloc new
1068 * fillsegs if the auxiliary stack is empty.
1069 * </pre>
1070 */
1071 static void
1072 pushFillsegBB(L_STACK *stack,
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
1116 /*!
1117 * \brief pushFillseg()
1118 *
1119 * \param[in] stack
1120 * \param[in] xleft, xright
1121 * \param[in] y
1122 * \param[in] dy
1123 * \param[in] ymax
1124 * \return void
1125 *
1126 * <pre>
1127 * Notes:
1128 * (1) This adds a line segment to the stack.
1129 * (2) The auxiliary stack is used as a storage area to recycle
1130 * fillsegs that are no longer in use. We only calloc new
1131 * fillsegs if the auxiliary stack is empty.
1132 * </pre>
1133 */
1134 static void
1135 pushFillseg(L_STACK *stack,
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
1170 /*!
1171 * \brief popFillseg()
1172 *
1173 * \param[in] stack
1174 * \param[out] pxleft left x
1175 * \param[out] pxright right x
1176 * \param[out] py y coordinate
1177 * \param[out] pdy delta y
1178 * \return void
1179 *
1180 * <pre>
1181 * Notes:
1182 * (1) This removes a line segment from the stack, and returns its size.
1183 * (2) The surplussed fillseg is placed on the auxiliary stack
1184 * for future use.
1185 * </pre>
1186 */
1187 static void
1188 popFillseg(L_STACK *stack,
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 }