Leptonica 1.68
C Image Processing Library

conncomp.c

Go to the documentation of this file.
00001 /*====================================================================*
00002  -  Copyright (C) 2001 Leptonica.  All rights reserved.
00003  -  This software is distributed in the hope that it will be
00004  -  useful, but with NO WARRANTY OF ANY KIND.
00005  -  No author or distributor accepts responsibility to anyone for the
00006  -  consequences of using this software, or for whether it serves any
00007  -  particular purpose or works at all, unless he or she says so in
00008  -  writing.  Everyone is granted permission to copy, modify and
00009  -  redistribute this source code, for commercial or non-commercial
00010  -  purposes, with the following restrictions: (1) the origin of this
00011  -  source code must not be misrepresented; (2) modified versions must
00012  -  be plainly marked as such; and (3) this notice may not be removed
00013  -  or altered from any source or modified source distribution.
00014  *====================================================================*/
00015 
00016 /*
00017  *  conncomp.c
00018  *
00019  *    Connected component counting and extraction, using Heckbert's
00020  *    stack-based filling algorithm.
00021  *
00022  *      4- and 8-connected components: counts, bounding boxes and images
00023  *
00024  *      Top-level calls:
00025  *           BOXA     *pixConnComp()
00026  *           BOXA     *pixConnCompPixa()
00027  *           BOXA     *pixConnCompBB()
00028  *           l_int32   pixCountConnComp()
00029  *
00030  *      Identify the next c.c. to be erased:
00031  *           l_int32   nextOnPixelInRaster()
00032  *           l_int32   nextOnPixelInRasterLow()
00033  *
00034  *      Erase the c.c., saving the b.b.:
00035  *           BOX      *pixSeedfillBB()
00036  *           BOX      *pixSeedfill4BB()
00037  *           BOX      *pixSeedfill8BB()
00038  *
00039  *      Just erase the c.c.:
00040  *           l_int32   pixSeedfill()
00041  *           l_int32   pixSeedfill4()
00042  *           l_int32   pixSeedfill8()
00043  *
00044  *      Static stack helper functions for single raster line seedfill:
00045  *           static void    pushFillsegBB()
00046  *           static void    pushFillseg()
00047  *           static void    popFillseg()
00048  *
00049  *  The basic method in pixConnCompBB() is very simple.  We scan the
00050  *  image in raster order, looking for the next ON pixel.  When it
00051  *  is found, we erase it and every pixel of the 4- or 8-connected
00052  *  component to which it belongs, using Heckbert's seedfill
00053  *  algorithm.  As pixels are erased, we keep track of the
00054  *  minimum rectangle that encloses all erased pixels; after
00055  *  the connected component has been erased, we save its
00056  *  bounding box in an array of boxes.  When all pixels in the
00057  *  image have been erased, we have an array that describes every
00058  *  4- or 8-connected component in terms of its bounding box.
00059  *
00060  *  pixConnCompPixa() is a slight variation on pixConnCompBB(),
00061  *  where we additionally save an array of images (in a Pixa)
00062  *  of each of the 4- or 8-connected components.  This is done trivially
00063  *  by maintaining two temporary images.  We erase a component from one,
00064  *  and use the bounding box to extract the pixels within the b.b.
00065  *  from each of the two images.  An XOR between these subimages
00066  *  gives the erased component.  Then we erase the component from the
00067  *  second image using the XOR again, with the extracted component
00068  *  placed on the second image at the location of the bounding box.
00069  *  Rasterop does all the work.  At the end, we have an array
00070  *  of the 4- or 8-connected components, as well as an array of the
00071  *  bounding boxes that describe where they came from in the original image.
00072  *
00073  *  If you just want the number of connected components, pixCountConnComp()
00074  *  is a bit faster than pixConnCompBB(), because it doesn't have to
00075  *  keep track of the bounding rectangles for each c.c.
00076  */
00077 
00078 #include <stdio.h>
00079 #include <stdlib.h>
00080 #include "allheaders.h"
00081 
00082 
00083 /*
00084  *  The struct FillSeg is used by the Heckbert seedfill algorithm to
00085  *  hold information about image segments that are waiting to be
00086  *  investigated.  We use two Stacks, one to hold the FillSegs in use,
00087  *  and an auxiliary Stack as a reservoir to hold FillSegs for re-use.
00088  */
00089 struct FillSeg
00090 {
00091     l_int32    xleft;    /* left edge of run */
00092     l_int32    xright;   /* right edge of run */
00093     l_int32    y;        /* run y  */
00094     l_int32    dy;       /* parent segment direction: 1 above, -1 below) */
00095 };
00096 typedef struct FillSeg    FILLSEG;
00097 
00098 
00099     /* Static accessors for FillSegs on a stack */
00100 static void pushFillsegBB(L_STACK *lstack, l_int32 xleft, l_int32 xright,
00101                           l_int32 y, l_int32 dy, l_int32 ymax,
00102                           l_int32 *pminx, l_int32 *pmaxx,
00103                           l_int32 *pminy, l_int32 *pmaxy);
00104 static void pushFillseg(L_STACK *lstack, l_int32 xleft, l_int32 xright,
00105                         l_int32 y, l_int32 dy, l_int32 ymax);
00106 static void popFillseg(L_STACK *lstack, l_int32 *pxleft, l_int32 *pxright,
00107                        l_int32 *py, l_int32 *pdy);
00108 
00109 
00110 #ifndef  NO_CONSOLE_IO
00111 #define   DEBUG    0
00112 #endif  /* ~NO_CONSOLE_IO */
00113 
00114 
00115 /*-----------------------------------------------------------------------*
00116  *                Bounding boxes of 4 Connected Components               *
00117  *-----------------------------------------------------------------------*/
00118 /*!
00119  *  pixConnComp()
00120  *
00121  *      Input:  pixs (1 bpp)
00122  *              &pixa   (<optional return> pixa of each c.c.)
00123  *              connectivity (4 or 8)
00124  *      Return: boxa, or null on error
00125  *
00126  *  Notes:
00127  *      (1) This is the top-level call for getting bounding boxes or
00128  *          a pixa of the components, and it can be used instead
00129  *          of either pixConnCompBB() or pixConnCompPixa(), rsp.
00130  */
00131 BOXA *
00132 pixConnComp(PIX     *pixs,
00133             PIXA   **ppixa,
00134             l_int32  connectivity)
00135 {
00136 
00137     PROCNAME("pixConnComp");
00138 
00139     if (ppixa) *ppixa = NULL;
00140     if (!pixs)
00141         return (BOXA *)ERROR_PTR("pixs not defined", procName, NULL);
00142     if (pixGetDepth(pixs) != 1)
00143         return (BOXA *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
00144     if (connectivity != 4 && connectivity != 8)
00145         return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00146 
00147     if (!ppixa)
00148         return pixConnCompBB(pixs, connectivity);
00149     else
00150         return pixConnCompPixa(pixs, ppixa, connectivity);
00151 }
00152 
00153 
00154 /*!
00155  *  pixConnCompPixa()
00156  *
00157  *      Input:  pixs (1 bpp)
00158  *              &pixa (<return> pixa of each c.c.)
00159  *              connectivity (4 or 8)
00160  *      Return: boxa, or null on error
00161  *
00162  *  Notes:
00163  *      (1) This finds bounding boxes of 4- or 8-connected components
00164  *          in a binary image, and saves images of each c.c
00165  *          in a pixa array.
00166  *      (2) It sets up 2 temporary pix, and for each c.c. that is
00167  *          located in raster order, it erases the c.c. from one pix,
00168  *          then uses the b.b. to extract the c.c. from the two pix using
00169  *          an XOR, and finally erases the c.c. from the second pix.
00170  *      (3) A clone of the returned boxa (where all boxes in the array
00171  *          are clones) is inserted into the pixa.
00172  *      (4) If the input is valid, this always returns a boxa and a pixa.
00173  *          If pixs is empty, the boxa and pixa will be empty.
00174  */
00175 BOXA *
00176 pixConnCompPixa(PIX     *pixs,
00177                 PIXA   **ppixa,
00178                 l_int32  connectivity)
00179 {
00180 l_int32   h, iszero;
00181 l_int32   x, y, xstart, ystart;
00182 PIX      *pixt1, *pixt2, *pixt3, *pixt4;
00183 PIXA     *pixa;
00184 BOX      *box;
00185 BOXA     *boxa;
00186 L_STACK  *lstack, *auxstack;
00187 
00188     PROCNAME("pixConnCompPixa");
00189 
00190     if (!ppixa)
00191         return (BOXA *)ERROR_PTR("&pixa not defined", procName, NULL);
00192     *ppixa = NULL;
00193     if (!pixs || pixGetDepth(pixs) != 1)
00194         return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00195     if (connectivity != 4 && connectivity != 8)
00196         return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00197 
00198     pixa = pixaCreate(0);
00199     *ppixa = pixa;
00200     pixZero(pixs, &iszero);
00201     if (iszero)
00202         return boxaCreate(1);  /* return empty boxa */
00203 
00204     if ((pixt1 = pixCopy(NULL, pixs)) == NULL)
00205         return (BOXA *)ERROR_PTR("pixt1 not made", procName, NULL);
00206     if ((pixt2 = pixCopy(NULL, pixs)) == NULL)
00207         return (BOXA *)ERROR_PTR("pixt2 not made", procName, NULL);
00208 
00209     h = pixGetHeight(pixs);
00210     if ((lstack = lstackCreate(h)) == NULL)
00211         return (BOXA *)ERROR_PTR("lstack not made", procName, NULL);
00212     if ((auxstack = lstackCreate(0)) == NULL)
00213         return (BOXA *)ERROR_PTR("auxstack not made", procName, NULL);
00214     lstack->auxstack = auxstack;
00215     if ((boxa = boxaCreate(0)) == NULL)
00216         return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
00217 
00218     xstart = 0;
00219     ystart = 0;
00220     while (1)
00221     {
00222         if (!nextOnPixelInRaster(pixt1, xstart, ystart, &x, &y))
00223             break;
00224 
00225         if ((box = pixSeedfillBB(pixt1, lstack, x, y, connectivity)) == NULL)
00226             return (BOXA *)ERROR_PTR("box not made", procName, NULL);
00227         boxaAddBox(boxa, box, L_INSERT);
00228 
00229             /* Save the c.c. and remove from pixt2 as well */
00230         pixt3 = pixClipRectangle(pixt1, box, NULL);
00231         pixt4 = pixClipRectangle(pixt2, box, NULL);
00232         pixXor(pixt3, pixt3, pixt4);
00233         pixRasterop(pixt2, box->x, box->y, box->w, box->h, PIX_SRC ^ PIX_DST,
00234                     pixt3, 0, 0);
00235         pixaAddPix(pixa, pixt3, L_INSERT);
00236         pixDestroy(&pixt4);
00237 
00238         xstart = x;
00239         ystart = y;
00240     }
00241 
00242 #if  DEBUG
00243     pixCountPixels(pixt1, &iszero, NULL);
00244     fprintf(stderr, "Number of remaining pixels = %d\n", iszero);
00245     pixWrite("junkremain", pixt1, IFF_PNG);
00246 #endif  /* DEBUG */
00247 
00248         /* Remove old boxa of pixa and replace with a clone copy */
00249     boxaDestroy(&pixa->boxa);
00250     pixa->boxa = boxaCopy(boxa, L_CLONE);
00251 
00252         /* Cleanup, freeing the fillsegs on each stack */
00253     lstackDestroy(&lstack, TRUE);
00254     pixDestroy(&pixt1);
00255     pixDestroy(&pixt2);
00256 
00257     return boxa;
00258 }
00259 
00260 
00261 /*!
00262  *  pixConnCompBB()
00263  *
00264  *      Input:  pixs (1 bpp)
00265  *              connectivity (4 or 8)
00266  *      Return: boxa, or null on error
00267  *
00268  * Notes:
00269  *     (1) Finds bounding boxes of 4- or 8-connected components
00270  *         in a binary image.
00271  *     (2) This works on a copy of the input pix.  The c.c. are located
00272  *         in raster order and erased one at a time.  In the process,
00273  *         the b.b. is computed and saved.
00274  */
00275 BOXA *
00276 pixConnCompBB(PIX     *pixs,
00277               l_int32  connectivity)
00278 {
00279 l_int32   h, iszero;
00280 l_int32   x, y, xstart, ystart;
00281 PIX      *pixt;
00282 BOX      *box;
00283 BOXA     *boxa;
00284 L_STACK  *lstack, *auxstack;
00285 
00286     PROCNAME("pixConnCompBB");
00287 
00288     if (!pixs || pixGetDepth(pixs) != 1)
00289         return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00290     if (connectivity != 4 && connectivity != 8)
00291         return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00292 
00293     pixZero(pixs, &iszero);
00294     if (iszero)
00295         return boxaCreate(1);  /* return empty boxa */
00296 
00297     if ((pixt = pixCopy(NULL, pixs)) == NULL)
00298         return (BOXA *)ERROR_PTR("pixt not made", procName, NULL);
00299 
00300     h = pixGetHeight(pixs);
00301     if ((lstack = lstackCreate(h)) == NULL)
00302         return (BOXA *)ERROR_PTR("lstack not made", procName, NULL);
00303     if ((auxstack = lstackCreate(0)) == NULL)
00304         return (BOXA *)ERROR_PTR("auxstack not made", procName, NULL);
00305     lstack->auxstack = auxstack;
00306     if ((boxa = boxaCreate(0)) == NULL)
00307         return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
00308 
00309     xstart = 0;
00310     ystart = 0;
00311     while (1)
00312     {
00313         if (!nextOnPixelInRaster(pixt, xstart, ystart, &x, &y))
00314             break;
00315 
00316         if ((box = pixSeedfillBB(pixt, lstack, x, y, connectivity)) == NULL)
00317             return (BOXA *)ERROR_PTR("box not made", procName, NULL);
00318         boxaAddBox(boxa, box, L_INSERT);
00319 
00320         xstart = x;
00321         ystart = y;
00322     }
00323 
00324 #if  DEBUG
00325     pixCountPixels(pixt, &iszero, NULL);
00326     fprintf(stderr, "Number of remaining pixels = %d\n", iszero);
00327     pixWrite("junkremain", pixt1, IFF_PNG);
00328 #endif  /* DEBUG */
00329 
00330         /* Cleanup, freeing the fillsegs on each stack */
00331     lstackDestroy(&lstack, TRUE);
00332     pixDestroy(&pixt);
00333 
00334     return boxa;
00335 }
00336 
00337 
00338 /*!
00339  *  pixCountConnComp()
00340  *
00341  *      Input:  pixs (1 bpp)
00342  *              connectivity (4 or 8)
00343  *              &count (<return>
00344  *      Return: 0 if OK, 1 on error
00345  *
00346  * Notes:
00347  *     (1) This is the top-level call for getting the number of
00348  *         4- or 8-connected components in a 1 bpp image.
00349  *     (2) It works on a copy of the input pix.  The c.c. are located
00350  *         in raster order and erased one at a time.
00351  */
00352 l_int32
00353 pixCountConnComp(PIX      *pixs,
00354                  l_int32   connectivity,
00355                  l_int32  *pcount)
00356 {
00357 l_int32   h, iszero;
00358 l_int32   x, y, xstart, ystart;
00359 PIX      *pixt;
00360 L_STACK  *lstack, *auxstack;
00361 
00362     PROCNAME("pixCountConnComp");
00363 
00364     if (!pcount)
00365         return ERROR_INT("&count not defined", procName, 1);
00366     *pcount = 0;  /* initialize the count to 0 */
00367     if (!pixs || pixGetDepth(pixs) != 1)
00368         return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
00369     if (connectivity != 4 && connectivity != 8)
00370         return ERROR_INT("connectivity not 4 or 8", procName, 1);
00371 
00372     pixZero(pixs, &iszero);
00373     if (iszero)
00374         return 0;
00375 
00376     if ((pixt = pixCopy(NULL, pixs)) == NULL)
00377         return ERROR_INT("pixt not made", procName, 1);
00378 
00379     h = pixGetDepth(pixs);
00380     if ((lstack = lstackCreate(h)) == NULL)
00381         return ERROR_INT("lstack not made", procName, 1);
00382     if ((auxstack = lstackCreate(0)) == NULL)
00383         return ERROR_INT("auxstack not made", procName, 1);
00384     lstack->auxstack = auxstack;
00385 
00386     xstart = 0;
00387     ystart = 0;
00388     while (1)
00389     {
00390         if (!nextOnPixelInRaster(pixt, xstart, ystart, &x, &y))
00391             break;
00392 
00393         pixSeedfill(pixt, lstack, x, y, connectivity);
00394         (*pcount)++;
00395         xstart = x;
00396         ystart = y;
00397     }
00398 
00399         /* Cleanup, freeing the fillsegs on each stack */
00400     lstackDestroy(&lstack, TRUE);
00401     pixDestroy(&pixt);
00402 
00403     return 0;
00404 }
00405 
00406 
00407 /*!
00408  *  nextOnPixelInRaster()
00409  *
00410  *      Input:  pixs (1 bpp)
00411  *              xstart, ystart  (starting point for search)
00412  *              &x, &y  (<return> coord value of next ON pixel)
00413  *      Return: 1 if a pixel is found; 0 otherwise or on error
00414  */
00415 l_int32
00416 nextOnPixelInRaster(PIX      *pixs,
00417                     l_int32   xstart,
00418                     l_int32   ystart,
00419                     l_int32  *px,
00420                     l_int32  *py)
00421 {
00422 l_int32    w, h, d, wpl;
00423 l_uint32  *data;
00424 
00425     PROCNAME("nextOnPixelInRaster");
00426 
00427     if (!pixs)
00428         return ERROR_INT("pixs not defined", procName, 0);
00429     pixGetDimensions(pixs, &w, &h, &d);
00430     if (d != 1)
00431         return ERROR_INT("pixs not 1 bpp", procName, 0);
00432 
00433     wpl = pixGetWpl(pixs);
00434     data = pixGetData(pixs);
00435     return nextOnPixelInRasterLow(data, w, h, wpl, xstart, ystart, px, py);
00436 }
00437 
00438 
00439 l_int32
00440 nextOnPixelInRasterLow(l_uint32  *data,
00441                        l_int32    w,
00442                        l_int32    h,
00443                        l_int32    wpl,
00444                        l_int32    xstart,
00445                        l_int32    ystart,
00446                        l_int32   *px,
00447                        l_int32   *py)
00448 {
00449 l_int32    i, x, y, xend, startword;
00450 l_uint32  *line, *pword;
00451 
00452         /* Look at the first word */
00453     line = data + ystart * wpl;
00454     pword = line + (xstart / 32);
00455     if (*pword) {
00456         xend = xstart - (xstart % 32) + 31;
00457         for (x = xstart; x <= xend && x < w; x++) {
00458             if (GET_DATA_BIT(line, x)) {
00459                 *px = x;
00460                 *py = ystart;
00461                 return 1;
00462             }
00463         }
00464     }
00465 
00466         /* Continue with the rest of the line */
00467     startword = (xstart / 32) + 1;
00468     x = 32 * startword;
00469     for (pword = line + startword; x < w; pword++, x += 32) {
00470         if (*pword) {
00471             for (i = 0; i < 32 && x < w; i++, x++) {
00472                 if (GET_DATA_BIT(line, x)) {
00473                     *px = x;
00474                     *py = ystart;
00475                     return 1;
00476                 }
00477             }
00478         }
00479     }
00480 
00481         /* Continue with following lines */
00482     for (y = ystart + 1; y < h; y++) {
00483         line = data + y * wpl;
00484         for (pword = line, x = 0; x < w; pword++, x += 32) {
00485             if (*pword) {
00486                 for (i = 0; i < 32 && x < w; i++, x++) {
00487                     if (GET_DATA_BIT(line, x)) {
00488                         *px = x;
00489                         *py = y;
00490                         return 1;
00491                     }
00492                 }
00493             }
00494         }
00495     }
00496 
00497     return 0;
00498 }
00499 
00500 
00501 /*!
00502  *  pixSeedfillBB()
00503  *
00504  *      Input:  pixs (1 bpp)
00505  *              lstack (for holding fillsegs)
00506  *              x,y   (location of seed pixel)
00507  *              connectivity  (4 or 8)
00508  *      Return: box or null on error
00509  *
00510  *  Notes:
00511  *      (1) This is the high-level interface to Paul Heckbert's
00512  *          stack-based seedfill algorithm.
00513  */
00514 BOX *
00515 pixSeedfillBB(PIX      *pixs,
00516               L_STACK  *lstack,
00517               l_int32   x,
00518               l_int32   y,
00519               l_int32   connectivity)
00520 {
00521 BOX  *box;
00522 
00523     PROCNAME("pixSeedfillBB");
00524 
00525     if (!pixs || pixGetDepth(pixs) != 1)
00526         return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00527     if (!lstack)
00528         return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
00529     if (connectivity != 4 && connectivity != 8)
00530         return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00531 
00532     if (connectivity == 4) {
00533         if ((box = pixSeedfill4BB(pixs, lstack, x, y)) == NULL)
00534             return (BOX *)ERROR_PTR("box not made", procName, NULL);
00535     }
00536     else if (connectivity == 8) {
00537         if ((box = pixSeedfill8BB(pixs, lstack, x, y)) == NULL)
00538             return (BOX *)ERROR_PTR("box not made", procName, NULL);
00539     }
00540     else
00541         return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00542 
00543     return box;
00544 }
00545 
00546 
00547 /*!
00548  *  pixSeedfill4BB()
00549  *
00550  *      Input:  pixs (1 bpp)
00551  *              lstack (for holding fillsegs)
00552  *              x,y   (location of seed pixel)
00553  *      Return: box or null on error.
00554  *
00555  *  Notes:
00556  *      (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
00557  *      (2) This operates on the input 1 bpp pix to remove the fg seed
00558  *          pixel, at (x,y), and all pixels that are 4-connected to it.
00559  *          The seed pixel at (x,y) must initially be ON.
00560  *      (3) Returns the bounding box of the erased 4-cc component.
00561  *      (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
00562  *          in "Graphic Gems", ed. Andrew Glassner, Academic
00563  *          Press, 1990.  The algorithm description is given
00564  *          on pp. 275-277; working C code is on pp. 721-722.)
00565  *          The code here follows Heckbert's exactly, except
00566  *          we use function calls instead of macros for
00567  *          pushing data on and popping data off the stack.
00568  *          This makes sense to do because Heckbert's fixed-size
00569  *          stack with macros is dangerous: images exist that
00570  *          will overrun the stack and crash.   The stack utility
00571  *          here grows dynamically as needed, and the fillseg
00572  *          structures that are not in use are stored in another
00573  *          stack for reuse.  It should be noted that the 
00574  *          overhead in the function calls (vs. macros) is negligible.
00575  */
00576 BOX *
00577 pixSeedfill4BB(PIX      *pixs,
00578                L_STACK  *lstack,
00579                l_int32   x,
00580                l_int32   y)
00581 {
00582 l_int32    w, h, xstart, wpl, x1, x2, dy;
00583 l_int32    xmax, ymax;
00584 l_int32    minx, maxx, miny, maxy;  /* for bounding box of this c.c. */
00585 l_uint32  *data, *line;
00586 BOX       *box;
00587 
00588     PROCNAME("pixSeedfill4BB");
00589 
00590     if (!pixs || pixGetDepth(pixs) != 1)
00591         return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00592     if (!lstack)
00593         return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
00594 
00595     pixGetDimensions(pixs, &w, &h, NULL);
00596     xmax = w - 1;
00597     ymax = h - 1;
00598     data = pixGetData(pixs);
00599     wpl = pixGetWpl(pixs);
00600     line = data + y * wpl;
00601 
00602         /* Check pix value of seed; must be within the image and ON */
00603     if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
00604         return NULL;
00605 
00606         /* Init stack to seed:
00607          * Must first init b.b. values to prevent valgrind from complaining;
00608          * then init b.b. boundaries correctly to seed.  */
00609     minx = miny = 100000;
00610     maxx = maxy = 0;
00611     pushFillsegBB(lstack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
00612     pushFillsegBB(lstack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
00613     minx = maxx = x;
00614     miny = maxy = y;
00615 
00616     while (lstackGetCount(lstack) > 0)
00617     {
00618             /* Pop segment off stack and fill a neighboring scan line */
00619         popFillseg(lstack, &x1, &x2, &y, &dy);
00620         line = data + y * wpl;
00621 
00622             /* A segment of scanline y - dy for x1 <= x <= x2 was
00623              * previously filled.  We now explore adjacent pixels 
00624              * in scan line y.  There are three regions: to the
00625              * left of x1 - 1, between x1 and x2, and to the right of x2.
00626              * These regions are handled differently.  Leaks are
00627              * possible expansions beyond the previous segment and
00628              * going back in the -dy direction.  These can happen 
00629              * for x < x1 - 1 and for x > x2 + 1.  Any "leak" segments
00630              * are plugged with a push in the -dy (opposite) direction.
00631              * And any segments found anywhere are always extended
00632              * in the +dy direction.  */
00633         for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
00634             CLEAR_DATA_BIT(line,x);
00635         if (x >= x1)  /* pix at x1 was off and was not cleared */
00636             goto skip;
00637         xstart = x + 1;
00638         if (xstart < x1 - 1)   /* leak on left? */
00639             pushFillsegBB(lstack, xstart, x1 - 1, y, -dy,
00640                           ymax, &minx, &maxx, &miny, &maxy);
00641 
00642         x = x1 + 1;
00643         do {
00644             for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
00645                 CLEAR_DATA_BIT(line, x);
00646             pushFillsegBB(lstack, xstart, x - 1, y, dy,
00647                           ymax, &minx, &maxx, &miny, &maxy);
00648             if (x > x2 + 1)   /* leak on right? */
00649                 pushFillsegBB(lstack, x2 + 1, x - 1, y, -dy,
00650                               ymax, &minx, &maxx, &miny, &maxy);
00651     skip:   for (x++; x <= x2 &&
00652                       x <= xmax &&
00653                       (GET_DATA_BIT(line, x) == 0); x++)
00654                 ;
00655             xstart = x;
00656         } while (x <= x2 && x <= xmax);
00657     }
00658 
00659     if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
00660             == NULL)
00661         return (BOX *)ERROR_PTR("box not made", procName, NULL);
00662     return box;
00663 }
00664             
00665 
00666 /*!
00667  *  pixSeedfill8BB()
00668  *
00669  *      Input:  pixs (1 bpp)
00670  *              lstack (for holding fillsegs)
00671  *              x,y   (location of seed pixel)
00672  *      Return: box or null on error.
00673  *
00674  *  Notes:
00675  *      (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
00676  *      (2) This operates on the input 1 bpp pix to remove the fg seed
00677  *          pixel, at (x,y), and all pixels that are 8-connected to it.
00678  *          The seed pixel at (x,y) must initially be ON.
00679  *      (3) Returns the bounding box of the erased 8-cc component.
00680  *      (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
00681  *          in "Graphic Gems", ed. Andrew Glassner, Academic
00682  *          Press, 1990.  The algorithm description is given
00683  *          on pp. 275-277; working C code is on pp. 721-722.)
00684  *          The code here follows Heckbert's closely, except
00685  *          the leak checks are changed for 8 connectivity.
00686  *          See comments on pixSeedfill4BB() for more details.
00687  */
00688 BOX *
00689 pixSeedfill8BB(PIX      *pixs,
00690                L_STACK  *lstack,
00691                l_int32   x,
00692                l_int32   y)
00693 {
00694 l_int32    w, h, xstart, wpl, x1, x2, dy;
00695 l_int32    xmax, ymax;
00696 l_int32    minx, maxx, miny, maxy;  /* for bounding box of this c.c. */
00697 l_uint32  *data, *line;
00698 BOX       *box;
00699 
00700     PROCNAME("pixSeedfill8BB");
00701 
00702     if (!pixs || pixGetDepth(pixs) != 1)
00703         return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00704     if (!lstack)
00705         return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
00706 
00707     pixGetDimensions(pixs, &w, &h, NULL);
00708     xmax = w - 1;
00709     ymax = h - 1;
00710     data = pixGetData(pixs);
00711     wpl = pixGetWpl(pixs);
00712     line = data + y * wpl;
00713 
00714         /* Check pix value of seed; must be ON */
00715     if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
00716         return NULL;
00717 
00718         /* Init stack to seed:
00719          * Must first init b.b. values to prevent valgrind from complaining;
00720          * then init b.b. boundaries correctly to seed.  */
00721     minx = miny = 100000;
00722     maxx = maxy = 0;
00723     pushFillsegBB(lstack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
00724     pushFillsegBB(lstack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
00725     minx = maxx = x;
00726     miny = maxy = y;
00727 
00728     while (lstackGetCount(lstack) > 0)
00729     {
00730             /* Pop segment off stack and fill a neighboring scan line */
00731         popFillseg(lstack, &x1, &x2, &y, &dy);
00732         line = data + y * wpl;
00733 
00734             /* A segment of scanline y - dy for x1 <= x <= x2 was
00735              * previously filled.  We now explore adjacent pixels 
00736              * in scan line y.  There are three regions: to the
00737              * left of x1, between x1 and x2, and to the right of x2.
00738              * These regions are handled differently.  Leaks are
00739              * possible expansions beyond the previous segment and
00740              * going back in the -dy direction.  These can happen 
00741              * for x < x1 and for x > x2.  Any "leak" segments
00742              * are plugged with a push in the -dy (opposite) direction.
00743              * And any segments found anywhere are always extended
00744              * in the +dy direction.  */
00745         for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
00746             CLEAR_DATA_BIT(line,x);
00747         if (x >= x1 - 1)  /* pix at x1 - 1 was off and was not cleared */
00748             goto skip;
00749         xstart = x + 1;
00750         if (xstart < x1)   /* leak on left? */
00751             pushFillsegBB(lstack, xstart, x1 - 1, y, -dy,
00752                           ymax, &minx, &maxx, &miny, &maxy);
00753 
00754         x = x1;
00755         do {
00756             for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
00757                 CLEAR_DATA_BIT(line, x);
00758             pushFillsegBB(lstack, xstart, x - 1, y, dy,
00759                           ymax, &minx, &maxx, &miny, &maxy);
00760             if (x > x2)   /* leak on right? */
00761                 pushFillsegBB(lstack, x2 + 1, x - 1, y, -dy,
00762                               ymax, &minx, &maxx, &miny, &maxy);
00763     skip:   for (x++; x <= x2 + 1 && 
00764                       x <= xmax &&
00765                       (GET_DATA_BIT(line, x) == 0); x++)
00766                 ;
00767             xstart = x;
00768         } while (x <= x2 + 1 && x <= xmax);
00769     }
00770 
00771     if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
00772             == NULL)
00773         return (BOX *)ERROR_PTR("box not made", procName, NULL);
00774     return box;
00775 }
00776             
00777 
00778 /*!
00779  *  pixSeedfill()
00780  *
00781  *      Input:  pixs (1 bpp)
00782  *              lstack (for holding fillsegs)
00783  *              x,y   (location of seed pixel)
00784  *              connectivity  (4 or 8)
00785  *      Return: 0 if OK, 1 on error
00786  *
00787  *  Notes:
00788  *      (1) This removes the component from pixs with a fg pixel at (x,y).
00789  *      (2) See pixSeedfill4() and pixSeedfill8() for details.
00790  */
00791 l_int32
00792 pixSeedfill(PIX      *pixs,
00793             L_STACK  *lstack,
00794             l_int32   x,
00795             l_int32   y,
00796             l_int32   connectivity)
00797 {
00798 l_int32  retval;
00799 
00800     PROCNAME("pixSeedfill");
00801 
00802     if (!pixs || pixGetDepth(pixs) != 1)
00803         return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
00804     if (!lstack)
00805         return ERROR_INT("lstack not defined", procName, 1);
00806     if (connectivity != 4 && connectivity != 8)
00807         return ERROR_INT("connectivity not 4 or 8", procName, 1);
00808 
00809     if (connectivity == 4)
00810         retval = pixSeedfill4(pixs, lstack, x, y);
00811     else  /* connectivity == 8  */
00812         retval = pixSeedfill8(pixs, lstack, x, y);
00813 
00814     return retval;
00815 }
00816 
00817 
00818 /*!
00819  *  pixSeedfill4()
00820  *
00821  *      Input:  pixs (1 bpp)
00822  *              lstack (for holding fillsegs)
00823  *              x,y   (location of seed pixel)
00824  *      Return: 0 if OK, 1 on error
00825  *
00826  *  Notes:
00827  *      (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
00828  *      (2) This operates on the input 1 bpp pix to remove the fg seed
00829  *          pixel, at (x,y), and all pixels that are 4-connected to it.
00830  *          The seed pixel at (x,y) must initially be ON.
00831  *      (3) Reference: see pixSeedFill4BB()
00832  */
00833 l_int32
00834 pixSeedfill4(PIX      *pixs,
00835              L_STACK  *lstack,
00836              l_int32   x,
00837              l_int32   y)
00838 {
00839 l_int32    w, h, xstart, wpl, x1, x2, dy;
00840 l_int32    xmax, ymax;
00841 l_uint32  *data, *line;
00842 
00843     PROCNAME("pixSeedfill4");
00844 
00845     if (!pixs || pixGetDepth(pixs) != 1)
00846         return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
00847     if (!lstack)
00848         return ERROR_INT("lstack not defined", procName, 1);
00849 
00850     pixGetDimensions(pixs, &w, &h, NULL);
00851     xmax = w - 1;
00852     ymax = h - 1;
00853     data = pixGetData(pixs);
00854     wpl = pixGetWpl(pixs);
00855     line = data + y * wpl;
00856 
00857         /* Check pix value of seed; must be within the image and ON */
00858     if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
00859         return 0;
00860 
00861         /* Init stack to seed */
00862     pushFillseg(lstack, x, x, y, 1, ymax);
00863     pushFillseg(lstack, x, x, y + 1, -1, ymax);
00864 
00865     while (lstackGetCount(lstack) > 0)
00866     {
00867             /* Pop segment off stack and fill a neighboring scan line */
00868         popFillseg(lstack, &x1, &x2, &y, &dy);
00869         line = data + y * wpl;
00870 
00871             /* A segment of scanline y - dy for x1 <= x <= x2 was
00872              * previously filled.  We now explore adjacent pixels 
00873              * in scan line y.  There are three regions: to the
00874              * left of x1 - 1, between x1 and x2, and to the right of x2.
00875              * These regions are handled differently.  Leaks are
00876              * possible expansions beyond the previous segment and
00877              * going back in the -dy direction.  These can happen 
00878              * for x < x1 - 1 and for x > x2 + 1.  Any "leak" segments
00879              * are plugged with a push in the -dy (opposite) direction.
00880              * And any segments found anywhere are always extended
00881              * in the +dy direction.  */
00882         for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
00883             CLEAR_DATA_BIT(line,x);
00884         if (x >= x1)  /* pix at x1 was off and was not cleared */
00885             goto skip;
00886         xstart = x + 1;
00887         if (xstart < x1 - 1)   /* leak on left? */
00888             pushFillseg(lstack, xstart, x1 - 1, y, -dy, ymax);
00889 
00890         x = x1 + 1;
00891         do {
00892             for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
00893                 CLEAR_DATA_BIT(line, x);
00894             pushFillseg(lstack, xstart, x - 1, y, dy, ymax);
00895             if (x > x2 + 1)   /* leak on right? */
00896                 pushFillseg(lstack, x2 + 1, x - 1, y, -dy, ymax);
00897     skip:   for (x++; x <= x2 &&
00898                       x <= xmax &&
00899                       (GET_DATA_BIT(line, x) == 0); x++)
00900                 ;
00901             xstart = x;
00902         } while (x <= x2 && x <= xmax);
00903     }
00904 
00905     return 0;
00906 }
00907             
00908 
00909 /*!
00910  *  pixSeedfill8()
00911  *
00912  *      Input:  pixs (1 bpp)
00913  *              lstack (for holding fillsegs)
00914  *              x,y   (location of seed pixel)
00915  *      Return: 0 if OK, 1 on error
00916  *
00917  *  Notes:
00918  *      (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
00919  *      (2) This operates on the input 1 bpp pix to remove the fg seed
00920  *          pixel, at (x,y), and all pixels that are 8-connected to it.
00921  *          The seed pixel at (x,y) must initially be ON.
00922  *      (3) Reference: see pixSeedFill8BB()
00923  */
00924 l_int32
00925 pixSeedfill8(PIX      *pixs,
00926              L_STACK  *lstack,
00927              l_int32   x,
00928              l_int32   y)
00929 {
00930 l_int32    w, h, xstart, wpl, x1, x2, dy;
00931 l_int32    xmax, ymax;
00932 l_uint32  *data, *line;
00933 
00934     PROCNAME("pixSeedfill8");
00935 
00936     if (!pixs || pixGetDepth(pixs) != 1)
00937         return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
00938     if (!lstack)
00939         return ERROR_INT("lstack not defined", procName, 1);
00940 
00941     pixGetDimensions(pixs, &w, &h, NULL);
00942     xmax = w - 1;
00943     ymax = h - 1;
00944     data = pixGetData(pixs);
00945     wpl = pixGetWpl(pixs);
00946     line = data + y * wpl;
00947 
00948         /* Check pix value of seed; must be ON */
00949     if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
00950         return 0;
00951 
00952         /* Init stack to seed */
00953     pushFillseg(lstack, x, x, y, 1, ymax);
00954     pushFillseg(lstack, x, x, y + 1, -1, ymax);
00955 
00956     while (lstackGetCount(lstack) > 0)
00957     {
00958             /* Pop segment off stack and fill a neighboring scan line */
00959         popFillseg(lstack, &x1, &x2, &y, &dy);
00960         line = data + y * wpl;
00961 
00962             /* A segment of scanline y - dy for x1 <= x <= x2 was
00963              * previously filled.  We now explore adjacent pixels 
00964              * in scan line y.  There are three regions: to the
00965              * left of x1, between x1 and x2, and to the right of x2.
00966              * These regions are handled differently.  Leaks are
00967              * possible expansions beyond the previous segment and
00968              * going back in the -dy direction.  These can happen 
00969              * for x < x1 and for x > x2.  Any "leak" segments
00970              * are plugged with a push in the -dy (opposite) direction.
00971              * And any segments found anywhere are always extended
00972              * in the +dy direction.  */
00973         for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
00974             CLEAR_DATA_BIT(line,x);
00975         if (x >= x1 - 1)  /* pix at x1 - 1 was off and was not cleared */
00976             goto skip;
00977         xstart = x + 1;
00978         if (xstart < x1)   /* leak on left? */
00979             pushFillseg(lstack, xstart, x1 - 1, y, -dy, ymax);
00980 
00981         x = x1;
00982         do {
00983             for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
00984                 CLEAR_DATA_BIT(line, x);
00985             pushFillseg(lstack, xstart, x - 1, y, dy, ymax);
00986             if (x > x2)   /* leak on right? */
00987                 pushFillseg(lstack, x2 + 1, x - 1, y, -dy, ymax);
00988     skip:   for (x++; x <= x2 + 1 && 
00989                       x <= xmax &&
00990                       (GET_DATA_BIT(line, x) == 0); x++)
00991                 ;
00992             xstart = x;
00993         } while (x <= x2 + 1 && x <= xmax);
00994     }
00995 
00996     return 0;
00997 }
00998             
00999 
01000 
01001 /*-----------------------------------------------------------------------*
01002  *          Static stack helper functions: push and pop fillsegs         *
01003  *-----------------------------------------------------------------------*/
01004 /*!
01005  *  pushFillsegBB()
01006  *
01007  *      Input:  lstack
01008  *              xleft, xright
01009  *              y
01010  *              dy
01011  *              ymax,
01012  *              &minx (<return>)
01013  *              &maxx (<return>)
01014  *              &miny (<return>)
01015  *              &maxy (<return>)
01016  *      Return: void
01017  *
01018  *  Notes:
01019  *      (1) This adds a line segment to the stack, and returns its size.
01020  *      (2) The auxiliary stack is used as a storage area to recycle
01021  *          fillsegs that are no longer in use.  We only calloc new
01022  *          fillsegs if the auxiliary stack is empty.
01023  */
01024 static void
01025 pushFillsegBB(L_STACK  *lstack,
01026               l_int32   xleft,
01027               l_int32   xright,
01028               l_int32   y,
01029               l_int32   dy,
01030               l_int32   ymax,
01031               l_int32  *pminx,
01032               l_int32  *pmaxx,
01033               l_int32  *pminy,
01034               l_int32  *pmaxy)
01035 {
01036 FILLSEG  *fseg;
01037 L_STACK  *auxstack;
01038 
01039     PROCNAME("pushFillsegBB");
01040 
01041     if (!lstack) {
01042         L_ERROR(procName, "lstack not defined");
01043         return;
01044     }
01045 
01046     *pminx = L_MIN(*pminx, xleft);
01047     *pmaxx = L_MAX(*pmaxx, xright);
01048     *pminy = L_MIN(*pminy, y);
01049     *pmaxy = L_MAX(*pmaxy, y);
01050 
01051     if (y + dy >= 0 && y + dy <= ymax) {
01052         if ((auxstack = lstack->auxstack) == NULL) {
01053             L_ERROR("auxstack not defined", procName);
01054             return;
01055         }
01056 
01057             /* Get a fillseg to use */
01058         if (lstackGetCount(auxstack) > 0)
01059             fseg = (FILLSEG *)lstackRemove(auxstack);
01060         else {
01061             if ((fseg = (FILLSEG *)CALLOC(1, sizeof(FILLSEG))) == NULL) {
01062                 L_ERROR("fillseg not made", procName);
01063                 return;
01064             }
01065         }
01066 
01067         fseg->xleft = xleft;
01068         fseg->xright = xright;
01069         fseg->y = y;
01070         fseg->dy = dy;
01071         lstackAdd(lstack, fseg);
01072     }
01073     return;
01074 }
01075 
01076 
01077 /*!
01078  *  pushFillseg()
01079  *
01080  *      Input:  lstack
01081  *              xleft, xright
01082  *              y
01083  *              dy
01084  *              ymax
01085  *      Return: void
01086  *
01087  *  Notes:
01088  *      (1) This adds a line segment to the stack.
01089  *      (2) The auxiliary stack is used as a storage area to recycle
01090  *          fillsegs that are no longer in use.  We only calloc new
01091  *          fillsegs if the auxiliary stack is empty.
01092  */
01093 static void
01094 pushFillseg(L_STACK  *lstack,
01095             l_int32   xleft,
01096             l_int32   xright,
01097             l_int32   y,
01098             l_int32   dy,
01099             l_int32   ymax)
01100 {
01101 FILLSEG  *fseg;
01102 L_STACK  *auxstack;
01103 
01104     PROCNAME("pushFillseg");
01105 
01106     if (!lstack) {
01107         L_ERROR(procName, "lstack not defined");
01108         return;
01109     }
01110 
01111     if (y + dy >= 0 && y + dy <= ymax) {
01112         if ((auxstack = lstack->auxstack) == NULL) {
01113             L_ERROR("auxstack not defined", procName);
01114             return;
01115         }
01116 
01117             /* Get a fillseg to use */
01118         if (lstackGetCount(auxstack) > 0)
01119             fseg = (FILLSEG *)lstackRemove(auxstack);
01120         else {
01121             if ((fseg = (FILLSEG *)CALLOC(1, sizeof(FILLSEG))) == NULL) {
01122                 L_ERROR("fillseg not made", procName);
01123                 return;
01124             }
01125         }
01126 
01127         fseg->xleft = xleft;
01128         fseg->xright = xright;
01129         fseg->y = y;
01130         fseg->dy = dy;
01131         lstackAdd(lstack, fseg);
01132     }
01133     return;
01134 }
01135 
01136 
01137 /*!
01138  *  popFillseg()
01139  * 
01140  *      Input:  lstack
01141  *              &xleft (<return>)
01142  *              &xright (<return>)
01143  *              &y (<return>)
01144  *              &dy (<return>)
01145  *      Return: void
01146  *
01147  *  Notes:
01148  *      (1) This removes a line segment from the stack, and returns its size.
01149  *      (2) The surplussed fillseg is placed on the auxiliary stack
01150  *          for future use.
01151  */
01152 static void
01153 popFillseg(L_STACK  *lstack,
01154            l_int32  *pxleft,
01155            l_int32  *pxright,
01156            l_int32  *py,
01157            l_int32  *pdy)
01158 {
01159 FILLSEG  *fseg;
01160 L_STACK  *auxstack;
01161 
01162     PROCNAME("popFillseg");
01163 
01164     if (!lstack) {
01165         L_ERROR("lstack not defined", procName);
01166         return;
01167     }
01168     if ((auxstack = lstack->auxstack) == NULL) {
01169         L_ERROR("auxstack not defined", procName);
01170         return;
01171     }
01172 
01173     if ((fseg = (FILLSEG *)lstackRemove(lstack)) == NULL)
01174         return;
01175 
01176     *pxleft = fseg->xleft;
01177     *pxright = fseg->xright;
01178     *py = fseg->y + fseg->dy;  /* this now points to the new line */
01179     *pdy = fseg->dy;
01180 
01181         /* Save it for re-use */
01182     lstackAdd(auxstack, fseg);
01183     return;
01184 }
01185 
01186 
01187 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines