/*====================================================================*
- Copyright (C) 2001 Leptonica. All rights reserved.
- This software is distributed in the hope that it will be
- useful, but with NO WARRANTY OF ANY KIND.
- No author or distributor accepts responsibility to anyone for the
- consequences of using this software, or for whether it serves any
- particular purpose or works at all, unless he or she says so in
- writing. Everyone is granted permission to copy, modify and
- redistribute this source code, for commercial or non-commercial
- purposes, with the following restrictions: (1) the origin of this
- source code must not be misrepresented; (2) modified versions must
- be plainly marked as such; and (3) this notice may not be removed
- or altered from any source or modified source distribution.
*====================================================================*/
/*
* conncomp.c
*
* Connected component counting and extraction, using Heckbert's
* stack-based filling algorithm.
*
* 4- and 8-connected components: counts, bounding boxes and images
*
* Top-level calls:
* BOXA *pixConnComp()
* BOXA *pixConnCompPixa()
* BOXA *pixConnCompBB()
* l_int32 pixCountConnComp()
*
* Identify the next c.c. to be erased:
* l_int32 nextOnPixelInRaster()
* l_int32 nextOnPixelInRasterLow()
*
* Erase the c.c., saving the b.b.:
* BOX *pixSeedfillBB()
* BOX *pixSeedfill4BB()
* BOX *pixSeedfill8BB()
*
* Just erase the c.c.:
* l_int32 pixSeedfill()
* l_int32 pixSeedfill4()
* l_int32 pixSeedfill8()
*
* Static stack helper functions for single raster line seedfill:
* static void pushFillsegBB()
* static void pushFillseg()
* static void popFillseg()
*
* The basic method in pixConnCompBB() is very simple. We scan the
* image in raster order, looking for the next ON pixel. When it
* is found, we erase it and every pixel of the 4- or 8-connected
* component to which it belongs, using Heckbert's seedfill
* algorithm. As pixels are erased, we keep track of the
* minimum rectangle that encloses all erased pixels; after
* the connected component has been erased, we save its
* bounding box in an array of boxes. When all pixels in the
* image have been erased, we have an array that describes every
* 4- or 8-connected component in terms of its bounding box.
*
* pixConnCompPixa() is a slight variation on pixConnCompBB(),
* where we additionally save an array of images (in a Pixa)
* of each of the 4- or 8-connected components. This is done trivially
* by maintaining two temporary images. We erase a component from one,
* and use the bounding box to extract the pixels within the b.b.
* from each of the two images. An XOR between these subimages
* gives the erased component. Then we erase the component from the
* second image using the XOR again, with the extracted component
* placed on the second image at the location of the bounding box.
* Rasterop does all the work. At the end, we have an array
* of the 4- or 8-connected components, as well as an array of the
* bounding boxes that describe where they came from in the original image.
*
* If you just want the number of connected components, pixCountConnComp()
* is a bit faster than pixConnCompBB(), because it doesn't have to
* keep track of the bounding rectangles for each c.c.
*/
#include <stdio.h>
#include <stdlib.h>
#include "allheaders.h"
/*
* The struct FillSeg is used by the Heckbert seedfill algorithm to
* hold information about image segments that are waiting to be
* investigated. We use two Stacks, one to hold the FillSegs in use,
* and an auxiliary Stack as a reservoir to hold FillSegs for re-use.
*/
struct FillSeg
{
l_int32 xleft; /* left edge of run */
l_int32 xright; /* right edge of run */
l_int32 y; /* run y */
l_int32 dy; /* parent segment direction: 1 above, -1 below) */
};
typedef struct FillSeg FILLSEG;
/* Static accessors for FillSegs on a stack */
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);
static void pushFillseg(L_STACK *lstack, l_int32 xleft, l_int32 xright,
l_int32 y, l_int32 dy, l_int32 ymax);
static void popFillseg(L_STACK *lstack, l_int32 *pxleft, l_int32 *pxright,
l_int32 *py, l_int32 *pdy);
#ifndef NO_CONSOLE_IO
#define DEBUG 0
#endif /* ~NO_CONSOLE_IO */
/*-----------------------------------------------------------------------*
* Bounding boxes of 4 Connected Components *
*-----------------------------------------------------------------------*/
/*!
* pixConnComp()
*
* Input: pixs (1 bpp)
* &pixa (<optional return> pixa of each c.c.)
* connectivity (4 or 8)
* Return: boxa, or null on error
*
* Notes:
* (1) This is the top-level call for getting bounding boxes or
* a pixa of the components, and it can be used instead
* of either pixConnCompBB() or pixConnCompPixa(), rsp.
*/
BOXA *
pixConnComp(PIX *pixs,
PIXA **ppixa,
l_int32 connectivity)
{
PROCNAME("pixConnComp");
if (ppixa) *ppixa = NULL;
if (!pixs)
return (BOXA *)ERROR_PTR("pixs not defined", procName, NULL);
if (pixGetDepth(pixs) != 1)
return (BOXA *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
if (connectivity != 4 && connectivity != 8)
return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
if (!ppixa)
return pixConnCompBB(pixs, connectivity);
else
return pixConnCompPixa(pixs, ppixa, connectivity);
}
/*!
* pixConnCompPixa()
*
* Input: pixs (1 bpp)
* &pixa (<return> pixa of each c.c.)
* connectivity (4 or 8)
* Return: boxa, or null on error
*
* Notes:
* (1) This finds bounding boxes of 4- or 8-connected components
* in a binary image, and saves images of each c.c
* in a pixa array.
* (2) It sets up 2 temporary pix, and for each c.c. that is
* located in raster order, it erases the c.c. from one pix,
* then uses the b.b. to extract the c.c. from the two pix using
* an XOR, and finally erases the c.c. from the second pix.
* (3) A clone of the returned boxa (where all boxes in the array
* are clones) is inserted into the pixa.
* (4) If the input is valid, this always returns a boxa and a pixa.
* If pixs is empty, the boxa and pixa will be empty.
*/
BOXA *
pixConnCompPixa(PIX *pixs,
PIXA **ppixa,
l_int32 connectivity)
{
l_int32 h, iszero;
l_int32 x, y, xstart, ystart;
PIX *pixt1, *pixt2, *pixt3, *pixt4;
PIXA *pixa;
BOX *box;
BOXA *boxa;
L_STACK *lstack, *auxstack;
PROCNAME("pixConnCompPixa");
if (!ppixa)
return (BOXA *)ERROR_PTR("&pixa not defined", procName, NULL);
*ppixa = NULL;
if (!pixs || pixGetDepth(pixs) != 1)
return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
if (connectivity != 4 && connectivity != 8)
return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
pixa = pixaCreate(0);
*ppixa = pixa;
pixZero(pixs, &iszero);
if (iszero)
return boxaCreate(1); /* return empty boxa */
if ((pixt1 = pixCopy(NULL, pixs)) == NULL)
return (BOXA *)ERROR_PTR("pixt1 not made", procName, NULL);
if ((pixt2 = pixCopy(NULL, pixs)) == NULL)
return (BOXA *)ERROR_PTR("pixt2 not made", procName, NULL);
h = pixGetHeight(pixs);
if ((lstack = lstackCreate(h)) == NULL)
return (BOXA *)ERROR_PTR("lstack not made", procName, NULL);
if ((auxstack = lstackCreate(0)) == NULL)
return (BOXA *)ERROR_PTR("auxstack not made", procName, NULL);
lstack->auxstack = auxstack;
if ((boxa = boxaCreate(0)) == NULL)
return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
xstart = 0;
ystart = 0;
while (1)
{
if (!nextOnPixelInRaster(pixt1, xstart, ystart, &x, &y))
break;
if ((box = pixSeedfillBB(pixt1, lstack, x, y, connectivity)) == NULL)
return (BOXA *)ERROR_PTR("box not made", procName, NULL);
boxaAddBox(boxa, box, L_INSERT);
/* Save the c.c. and remove from pixt2 as well */
pixt3 = pixClipRectangle(pixt1, box, NULL);
pixt4 = pixClipRectangle(pixt2, box, NULL);
pixXor(pixt3, pixt3, pixt4);
pixRasterop(pixt2, box->x, box->y, box->w, box->h, PIX_SRC ^ PIX_DST,
pixt3, 0, 0);
pixaAddPix(pixa, pixt3, L_INSERT);
pixDestroy(&pixt4);
xstart = x;
ystart = y;
}
#if DEBUG
pixCountPixels(pixt1, &iszero, NULL);
fprintf(stderr, "Number of remaining pixels = %d\n", iszero);
pixWrite("junkremain", pixt1, IFF_PNG);
#endif /* DEBUG */
/* Remove old boxa of pixa and replace with a clone copy */
boxaDestroy(&pixa->boxa);
pixa->boxa = boxaCopy(boxa, L_CLONE);
/* Cleanup, freeing the fillsegs on each stack */
lstackDestroy(&lstack, TRUE);
pixDestroy(&pixt1);
pixDestroy(&pixt2);
return boxa;
}
/*!
* pixConnCompBB()
*
* Input: pixs (1 bpp)
* connectivity (4 or 8)
* Return: boxa, or null on error
*
* Notes:
* (1) Finds bounding boxes of 4- or 8-connected components
* in a binary image.
* (2) This works on a copy of the input pix. The c.c. are located
* in raster order and erased one at a time. In the process,
* the b.b. is computed and saved.
*/
BOXA *
pixConnCompBB(PIX *pixs,
l_int32 connectivity)
{
l_int32 h, iszero;
l_int32 x, y, xstart, ystart;
PIX *pixt;
BOX *box;
BOXA *boxa;
L_STACK *lstack, *auxstack;
PROCNAME("pixConnCompBB");
if (!pixs || pixGetDepth(pixs) != 1)
return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
if (connectivity != 4 && connectivity != 8)
return (BOXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
pixZero(pixs, &iszero);
if (iszero)
return boxaCreate(1); /* return empty boxa */
if ((pixt = pixCopy(NULL, pixs)) == NULL)
return (BOXA *)ERROR_PTR("pixt not made", procName, NULL);
h = pixGetHeight(pixs);
if ((lstack = lstackCreate(h)) == NULL)
return (BOXA *)ERROR_PTR("lstack not made", procName, NULL);
if ((auxstack = lstackCreate(0)) == NULL)
return (BOXA *)ERROR_PTR("auxstack not made", procName, NULL);
lstack->auxstack = auxstack;
if ((boxa = boxaCreate(0)) == NULL)
return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
xstart = 0;
ystart = 0;
while (1)
{
if (!nextOnPixelInRaster(pixt, xstart, ystart, &x, &y))
break;
if ((box = pixSeedfillBB(pixt, lstack, x, y, connectivity)) == NULL)
return (BOXA *)ERROR_PTR("box not made", procName, NULL);
boxaAddBox(boxa, box, L_INSERT);
xstart = x;
ystart = y;
}
#if DEBUG
pixCountPixels(pixt, &iszero, NULL);
fprintf(stderr, "Number of remaining pixels = %d\n", iszero);
pixWrite("junkremain", pixt1, IFF_PNG);
#endif /* DEBUG */
/* Cleanup, freeing the fillsegs on each stack */
lstackDestroy(&lstack, TRUE);
pixDestroy(&pixt);
return boxa;
}
/*!
* pixCountConnComp()
*
* Input: pixs (1 bpp)
* connectivity (4 or 8)
* &count (<return>
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This is the top-level call for getting the number of
* 4- or 8-connected components in a 1 bpp image.
* (2) It works on a copy of the input pix. The c.c. are located
* in raster order and erased one at a time.
*/
l_int32
pixCountConnComp(PIX *pixs,
l_int32 connectivity,
l_int32 *pcount)
{
l_int32 h, iszero;
l_int32 x, y, xstart, ystart;
PIX *pixt;
L_STACK *lstack, *auxstack;
PROCNAME("pixCountConnComp");
if (!pcount)
return ERROR_INT("&count not defined", procName, 1);
*pcount = 0; /* initialize the count to 0 */
if (!pixs || pixGetDepth(pixs) != 1)
return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
if (connectivity != 4 && connectivity != 8)
return ERROR_INT("connectivity not 4 or 8", procName, 1);
pixZero(pixs, &iszero);
if (iszero)
return 0;
if ((pixt = pixCopy(NULL, pixs)) == NULL)
return ERROR_INT("pixt not made", procName, 1);
h = pixGetDepth(pixs);
if ((lstack = lstackCreate(h)) == NULL)
return ERROR_INT("lstack not made", procName, 1);
if ((auxstack = lstackCreate(0)) == NULL)
return ERROR_INT("auxstack not made", procName, 1);
lstack->auxstack = auxstack;
xstart = 0;
ystart = 0;
while (1)
{
if (!nextOnPixelInRaster(pixt, xstart, ystart, &x, &y))
break;
pixSeedfill(pixt, lstack, x, y, connectivity);
(*pcount)++;
xstart = x;
ystart = y;
}
/* Cleanup, freeing the fillsegs on each stack */
lstackDestroy(&lstack, TRUE);
pixDestroy(&pixt);
return 0;
}
/*!
* nextOnPixelInRaster()
*
* Input: pixs (1 bpp)
* xstart, ystart (starting point for search)
* &x, &y (<return> coord value of next ON pixel)
* Return: 1 if a pixel is found; 0 otherwise or on error
*/
l_int32
nextOnPixelInRaster(PIX *pixs,
l_int32 xstart,
l_int32 ystart,
l_int32 *px,
l_int32 *py)
{
l_int32 w, h, d, wpl;
l_uint32 *data;
PROCNAME("nextOnPixelInRaster");
if (!pixs)
return ERROR_INT("pixs not defined", procName, 0);
pixGetDimensions(pixs, &w, &h, &d);
if (d != 1)
return ERROR_INT("pixs not 1 bpp", procName, 0);
wpl = pixGetWpl(pixs);
data = pixGetData(pixs);
return nextOnPixelInRasterLow(data, w, h, wpl, xstart, ystart, px, py);
}
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)
{
l_int32 i, x, y, xend, startword;
l_uint32 *line, *pword;
/* Look at the first word */
line = data + ystart * wpl;
pword = line + (xstart / 32);
if (*pword) {
xend = xstart - (xstart % 32) + 31;
for (x = xstart; x <= xend && x < w; x++) {
if (GET_DATA_BIT(line, x)) {
*px = x;
*py = ystart;
return 1;
}
}
}
/* Continue with the rest of the line */
startword = (xstart / 32) + 1;
x = 32 * startword;
for (pword = line + startword; x < w; pword++, x += 32) {
if (*pword) {
for (i = 0; i < 32 && x < w; i++, x++) {
if (GET_DATA_BIT(line, x)) {
*px = x;
*py = ystart;
return 1;
}
}
}
}
/* Continue with following lines */
for (y = ystart + 1; y < h; y++) {
line = data + y * wpl;
for (pword = line, x = 0; x < w; pword++, x += 32) {
if (*pword) {
for (i = 0; i < 32 && x < w; i++, x++) {
if (GET_DATA_BIT(line, x)) {
*px = x;
*py = y;
return 1;
}
}
}
}
}
return 0;
}
/*!
* pixSeedfillBB()
*
* Input: pixs (1 bpp)
* lstack (for holding fillsegs)
* x,y (location of seed pixel)
* connectivity (4 or 8)
* Return: box or null on error
*
* Notes:
* (1) This is the high-level interface to Paul Heckbert's
* stack-based seedfill algorithm.
*/
BOX *
pixSeedfillBB(PIX *pixs,
L_STACK *lstack,
l_int32 x,
l_int32 y,
l_int32 connectivity)
{
BOX *box;
PROCNAME("pixSeedfillBB");
if (!pixs || pixGetDepth(pixs) != 1)
return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
if (!lstack)
return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
if (connectivity != 4 && connectivity != 8)
return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
if (connectivity == 4) {
if ((box = pixSeedfill4BB(pixs, lstack, x, y)) == NULL)
return (BOX *)ERROR_PTR("box not made", procName, NULL);
}
else if (connectivity == 8) {
if ((box = pixSeedfill8BB(pixs, lstack, x, y)) == NULL)
return (BOX *)ERROR_PTR("box not made", procName, NULL);
}
else
return (BOX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
return box;
}
/*!
* pixSeedfill4BB()
*
* Input: pixs (1 bpp)
* lstack (for holding fillsegs)
* x,y (location of seed pixel)
* Return: box or null on error.
*
* Notes:
* (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
* (2) This operates on the input 1 bpp pix to remove the fg seed
* pixel, at (x,y), and all pixels that are 4-connected to it.
* The seed pixel at (x,y) must initially be ON.
* (3) Returns the bounding box of the erased 4-cc component.
* (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
* in "Graphic Gems", ed. Andrew Glassner, Academic
* Press, 1990. The algorithm description is given
* on pp. 275-277; working C code is on pp. 721-722.)
* The code here follows Heckbert's exactly, except
* we use function calls instead of macros for
* pushing data on and popping data off the stack.
* This makes sense to do because Heckbert's fixed-size
* stack with macros is dangerous: images exist that
* will overrun the stack and crash. The stack utility
* here grows dynamically as needed, and the fillseg
* structures that are not in use are stored in another
* stack for reuse. It should be noted that the
* overhead in the function calls (vs. macros) is negligible.
*/
BOX *
pixSeedfill4BB(PIX *pixs,
L_STACK *lstack,
l_int32 x,
l_int32 y)
{
l_int32 w, h, xstart, wpl, x1, x2, dy;
l_int32 xmax, ymax;
l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
l_uint32 *data, *line;
BOX *box;
PROCNAME("pixSeedfill4BB");
if (!pixs || pixGetDepth(pixs) != 1)
return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
if (!lstack)
return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
pixGetDimensions(pixs, &w, &h, NULL);
xmax = w - 1;
ymax = h - 1;
data = pixGetData(pixs);
wpl = pixGetWpl(pixs);
line = data + y * wpl;
/* Check pix value of seed; must be within the image and ON */
if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
return NULL;
/* Init stack to seed:
* Must first init b.b. values to prevent valgrind from complaining;
* then init b.b. boundaries correctly to seed. */
minx = miny = 100000;
maxx = maxy = 0;
pushFillsegBB(lstack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
pushFillsegBB(lstack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
minx = maxx = x;
miny = maxy = y;
while (lstackGetCount(lstack) > 0)
{
/* Pop segment off stack and fill a neighboring scan line */
popFillseg(lstack, &x1, &x2, &y, &dy);
line = data + y * wpl;
/* A segment of scanline y - dy for x1 <= x <= x2 was
* previously filled. We now explore adjacent pixels
* in scan line y. There are three regions: to the
* left of x1 - 1, between x1 and x2, and to the right of x2.
* These regions are handled differently. Leaks are
* possible expansions beyond the previous segment and
* going back in the -dy direction. These can happen
* for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
* are plugged with a push in the -dy (opposite) direction.
* And any segments found anywhere are always extended
* in the +dy direction. */
for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
CLEAR_DATA_BIT(line,x);
if (x >= x1) /* pix at x1 was off and was not cleared */
goto skip;
xstart = x + 1;
if (xstart < x1 - 1) /* leak on left? */
pushFillsegBB(lstack, xstart, x1 - 1, y, -dy,
ymax, &minx, &maxx, &miny, &maxy);
x = x1 + 1;
do {
for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
CLEAR_DATA_BIT(line, x);
pushFillsegBB(lstack, xstart, x - 1, y, dy,
ymax, &minx, &maxx, &miny, &maxy);
if (x > x2 + 1) /* leak on right? */
pushFillsegBB(lstack, x2 + 1, x - 1, y, -dy,
ymax, &minx, &maxx, &miny, &maxy);
skip: for (x++; x <= x2 &&
x <= xmax &&
(GET_DATA_BIT(line, x) == 0); x++)
;
xstart = x;
} while (x <= x2 && x <= xmax);
}
if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
== NULL)
return (BOX *)ERROR_PTR("box not made", procName, NULL);
return box;
}
/*!
* pixSeedfill8BB()
*
* Input: pixs (1 bpp)
* lstack (for holding fillsegs)
* x,y (location of seed pixel)
* Return: box or null on error.
*
* Notes:
* (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
* (2) This operates on the input 1 bpp pix to remove the fg seed
* pixel, at (x,y), and all pixels that are 8-connected to it.
* The seed pixel at (x,y) must initially be ON.
* (3) Returns the bounding box of the erased 8-cc component.
* (4) Reference: see Paul Heckbert's stack-based seed fill algorithm
* in "Graphic Gems", ed. Andrew Glassner, Academic
* Press, 1990. The algorithm description is given
* on pp. 275-277; working C code is on pp. 721-722.)
* The code here follows Heckbert's closely, except
* the leak checks are changed for 8 connectivity.
* See comments on pixSeedfill4BB() for more details.
*/
BOX *
pixSeedfill8BB(PIX *pixs,
L_STACK *lstack,
l_int32 x,
l_int32 y)
{
l_int32 w, h, xstart, wpl, x1, x2, dy;
l_int32 xmax, ymax;
l_int32 minx, maxx, miny, maxy; /* for bounding box of this c.c. */
l_uint32 *data, *line;
BOX *box;
PROCNAME("pixSeedfill8BB");
if (!pixs || pixGetDepth(pixs) != 1)
return (BOX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
if (!lstack)
return (BOX *)ERROR_PTR("lstack not defined", procName, NULL);
pixGetDimensions(pixs, &w, &h, NULL);
xmax = w - 1;
ymax = h - 1;
data = pixGetData(pixs);
wpl = pixGetWpl(pixs);
line = data + y * wpl;
/* Check pix value of seed; must be ON */
if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
return NULL;
/* Init stack to seed:
* Must first init b.b. values to prevent valgrind from complaining;
* then init b.b. boundaries correctly to seed. */
minx = miny = 100000;
maxx = maxy = 0;
pushFillsegBB(lstack, x, x, y, 1, ymax, &minx, &maxx, &miny, &maxy);
pushFillsegBB(lstack, x, x, y + 1, -1, ymax, &minx, &maxx, &miny, &maxy);
minx = maxx = x;
miny = maxy = y;
while (lstackGetCount(lstack) > 0)
{
/* Pop segment off stack and fill a neighboring scan line */
popFillseg(lstack, &x1, &x2, &y, &dy);
line = data + y * wpl;
/* A segment of scanline y - dy for x1 <= x <= x2 was
* previously filled. We now explore adjacent pixels
* in scan line y. There are three regions: to the
* left of x1, between x1 and x2, and to the right of x2.
* These regions are handled differently. Leaks are
* possible expansions beyond the previous segment and
* going back in the -dy direction. These can happen
* for x < x1 and for x > x2. Any "leak" segments
* are plugged with a push in the -dy (opposite) direction.
* And any segments found anywhere are always extended
* in the +dy direction. */
for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
CLEAR_DATA_BIT(line,x);
if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
goto skip;
xstart = x + 1;
if (xstart < x1) /* leak on left? */
pushFillsegBB(lstack, xstart, x1 - 1, y, -dy,
ymax, &minx, &maxx, &miny, &maxy);
x = x1;
do {
for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
CLEAR_DATA_BIT(line, x);
pushFillsegBB(lstack, xstart, x - 1, y, dy,
ymax, &minx, &maxx, &miny, &maxy);
if (x > x2) /* leak on right? */
pushFillsegBB(lstack, x2 + 1, x - 1, y, -dy,
ymax, &minx, &maxx, &miny, &maxy);
skip: for (x++; x <= x2 + 1 &&
x <= xmax &&
(GET_DATA_BIT(line, x) == 0); x++)
;
xstart = x;
} while (x <= x2 + 1 && x <= xmax);
}
if ((box = boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1))
== NULL)
return (BOX *)ERROR_PTR("box not made", procName, NULL);
return box;
}
/*!
* pixSeedfill()
*
* Input: pixs (1 bpp)
* lstack (for holding fillsegs)
* x,y (location of seed pixel)
* connectivity (4 or 8)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This removes the component from pixs with a fg pixel at (x,y).
* (2) See pixSeedfill4() and pixSeedfill8() for details.
*/
l_int32
pixSeedfill(PIX *pixs,
L_STACK *lstack,
l_int32 x,
l_int32 y,
l_int32 connectivity)
{
l_int32 retval;
PROCNAME("pixSeedfill");
if (!pixs || pixGetDepth(pixs) != 1)
return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
if (!lstack)
return ERROR_INT("lstack not defined", procName, 1);
if (connectivity != 4 && connectivity != 8)
return ERROR_INT("connectivity not 4 or 8", procName, 1);
if (connectivity == 4)
retval = pixSeedfill4(pixs, lstack, x, y);
else /* connectivity == 8 */
retval = pixSeedfill8(pixs, lstack, x, y);
return retval;
}
/*!
* pixSeedfill4()
*
* Input: pixs (1 bpp)
* lstack (for holding fillsegs)
* x,y (location of seed pixel)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This is Paul Heckbert's stack-based 4-cc seedfill algorithm.
* (2) This operates on the input 1 bpp pix to remove the fg seed
* pixel, at (x,y), and all pixels that are 4-connected to it.
* The seed pixel at (x,y) must initially be ON.
* (3) Reference: see pixSeedFill4BB()
*/
l_int32
pixSeedfill4(PIX *pixs,
L_STACK *lstack,
l_int32 x,
l_int32 y)
{
l_int32 w, h, xstart, wpl, x1, x2, dy;
l_int32 xmax, ymax;
l_uint32 *data, *line;
PROCNAME("pixSeedfill4");
if (!pixs || pixGetDepth(pixs) != 1)
return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
if (!lstack)
return ERROR_INT("lstack not defined", procName, 1);
pixGetDimensions(pixs, &w, &h, NULL);
xmax = w - 1;
ymax = h - 1;
data = pixGetData(pixs);
wpl = pixGetWpl(pixs);
line = data + y * wpl;
/* Check pix value of seed; must be within the image and ON */
if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
return 0;
/* Init stack to seed */
pushFillseg(lstack, x, x, y, 1, ymax);
pushFillseg(lstack, x, x, y + 1, -1, ymax);
while (lstackGetCount(lstack) > 0)
{
/* Pop segment off stack and fill a neighboring scan line */
popFillseg(lstack, &x1, &x2, &y, &dy);
line = data + y * wpl;
/* A segment of scanline y - dy for x1 <= x <= x2 was
* previously filled. We now explore adjacent pixels
* in scan line y. There are three regions: to the
* left of x1 - 1, between x1 and x2, and to the right of x2.
* These regions are handled differently. Leaks are
* possible expansions beyond the previous segment and
* going back in the -dy direction. These can happen
* for x < x1 - 1 and for x > x2 + 1. Any "leak" segments
* are plugged with a push in the -dy (opposite) direction.
* And any segments found anywhere are always extended
* in the +dy direction. */
for (x = x1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
CLEAR_DATA_BIT(line,x);
if (x >= x1) /* pix at x1 was off and was not cleared */
goto skip;
xstart = x + 1;
if (xstart < x1 - 1) /* leak on left? */
pushFillseg(lstack, xstart, x1 - 1, y, -dy, ymax);
x = x1 + 1;
do {
for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
CLEAR_DATA_BIT(line, x);
pushFillseg(lstack, xstart, x - 1, y, dy, ymax);
if (x > x2 + 1) /* leak on right? */
pushFillseg(lstack, x2 + 1, x - 1, y, -dy, ymax);
skip: for (x++; x <= x2 &&
x <= xmax &&
(GET_DATA_BIT(line, x) == 0); x++)
;
xstart = x;
} while (x <= x2 && x <= xmax);
}
return 0;
}
/*!
* pixSeedfill8()
*
* Input: pixs (1 bpp)
* lstack (for holding fillsegs)
* x,y (location of seed pixel)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This is Paul Heckbert's stack-based 8-cc seedfill algorithm.
* (2) This operates on the input 1 bpp pix to remove the fg seed
* pixel, at (x,y), and all pixels that are 8-connected to it.
* The seed pixel at (x,y) must initially be ON.
* (3) Reference: see pixSeedFill8BB()
*/
l_int32
pixSeedfill8(PIX *pixs,
L_STACK *lstack,
l_int32 x,
l_int32 y)
{
l_int32 w, h, xstart, wpl, x1, x2, dy;
l_int32 xmax, ymax;
l_uint32 *data, *line;
PROCNAME("pixSeedfill8");
if (!pixs || pixGetDepth(pixs) != 1)
return ERROR_INT("pixs not defined or not 1 bpp", procName, 1);
if (!lstack)
return ERROR_INT("lstack not defined", procName, 1);
pixGetDimensions(pixs, &w, &h, NULL);
xmax = w - 1;
ymax = h - 1;
data = pixGetData(pixs);
wpl = pixGetWpl(pixs);
line = data + y * wpl;
/* Check pix value of seed; must be ON */
if (x < 0 || x > xmax || y < 0 || y > ymax || (GET_DATA_BIT(line, x) == 0))
return 0;
/* Init stack to seed */
pushFillseg(lstack, x, x, y, 1, ymax);
pushFillseg(lstack, x, x, y + 1, -1, ymax);
while (lstackGetCount(lstack) > 0)
{
/* Pop segment off stack and fill a neighboring scan line */
popFillseg(lstack, &x1, &x2, &y, &dy);
line = data + y * wpl;
/* A segment of scanline y - dy for x1 <= x <= x2 was
* previously filled. We now explore adjacent pixels
* in scan line y. There are three regions: to the
* left of x1, between x1 and x2, and to the right of x2.
* These regions are handled differently. Leaks are
* possible expansions beyond the previous segment and
* going back in the -dy direction. These can happen
* for x < x1 and for x > x2. Any "leak" segments
* are plugged with a push in the -dy (opposite) direction.
* And any segments found anywhere are always extended
* in the +dy direction. */
for (x = x1 - 1; x >= 0 && (GET_DATA_BIT(line, x) == 1); x--)
CLEAR_DATA_BIT(line,x);
if (x >= x1 - 1) /* pix at x1 - 1 was off and was not cleared */
goto skip;
xstart = x + 1;
if (xstart < x1) /* leak on left? */
pushFillseg(lstack, xstart, x1 - 1, y, -dy, ymax);
x = x1;
do {
for (; x <= xmax && (GET_DATA_BIT(line, x) == 1); x++)
CLEAR_DATA_BIT(line, x);
pushFillseg(lstack, xstart, x - 1, y, dy, ymax);
if (x > x2) /* leak on right? */
pushFillseg(lstack, x2 + 1, x - 1, y, -dy, ymax);
skip: for (x++; x <= x2 + 1 &&
x <= xmax &&
(GET_DATA_BIT(line, x) == 0); x++)
;
xstart = x;
} while (x <= x2 + 1 && x <= xmax);
}
return 0;
}
/*-----------------------------------------------------------------------*
* Static stack helper functions: push and pop fillsegs *
*-----------------------------------------------------------------------*/
/*!
* pushFillsegBB()
*
* Input: lstack
* xleft, xright
* y
* dy
* ymax,
* &minx (<return>)
* &maxx (<return>)
* &miny (<return>)
* &maxy (<return>)
* Return: void
*
* Notes:
* (1) This adds a line segment to the stack, and returns its size.
* (2) The auxiliary stack is used as a storage area to recycle
* fillsegs that are no longer in use. We only calloc new
* fillsegs if the auxiliary stack is empty.
*/
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)
{
FILLSEG *fseg;
L_STACK *auxstack;
PROCNAME("pushFillsegBB");
if (!lstack)
return ERROR_VOID(procName, "lstack not defined");
*pminx = L_MIN(*pminx, xleft);
*pmaxx = L_MAX(*pmaxx, xright);
*pminy = L_MIN(*pminy, y);
*pmaxy = L_MAX(*pmaxy, y);
if (y + dy >= 0 && y + dy <= ymax) {
if ((auxstack = lstack->auxstack) == NULL)
return ERROR_VOID("auxstack not defined", procName);
/* Get a fillseg to use */
if (lstackGetCount(auxstack) > 0)
fseg = (FILLSEG *)lstackRemove(auxstack);
else {
if ((fseg = (FILLSEG *)CALLOC(1, sizeof(FILLSEG))) == NULL)
return ERROR_VOID("fillseg not made", procName);
}
fseg->xleft = xleft;
fseg->xright = xright;
fseg->y = y;
fseg->dy = dy;
lstackAdd(lstack, fseg);
}
return;
}
/*!
* pushFillseg()
*
* Input: lstack
* xleft, xright
* y
* dy
* ymax
* Return: void
*
* Notes:
* (1) This adds a line segment to the stack.
* (2) The auxiliary stack is used as a storage area to recycle
* fillsegs that are no longer in use. We only calloc new
* fillsegs if the auxiliary stack is empty.
*/
static void
pushFillseg(L_STACK *lstack,
l_int32 xleft,
l_int32 xright,
l_int32 y,
l_int32 dy,
l_int32 ymax)
{
FILLSEG *fseg;
L_STACK *auxstack;
PROCNAME("pushFillseg");
if (!lstack)
return ERROR_VOID(procName, "lstack not defined");
if (y + dy >= 0 && y + dy <= ymax) {
if ((auxstack = lstack->auxstack) == NULL)
return ERROR_VOID("auxstack not defined", procName);
/* Get a fillseg to use */
if (lstackGetCount(auxstack) > 0)
fseg = (FILLSEG *)lstackRemove(auxstack);
else {
if ((fseg = (FILLSEG *)CALLOC(1, sizeof(FILLSEG))) == NULL)
return ERROR_VOID("fillseg not made", procName);
}
fseg->xleft = xleft;
fseg->xright = xright;
fseg->y = y;
fseg->dy = dy;
lstackAdd(lstack, fseg);
}
return;
}
/*!
* popFillseg()
*
* Input: lstack
* &xleft (<return>)
* &xright (<return>)
* &y (<return>)
* &dy (<return>)
* Return: void
*
* Notes:
* (1) This removes a line segment from the stack, and returns its size.
* (2) The surplussed fillseg is placed on the auxiliary stack
* for future use.
*/
static void
popFillseg(L_STACK *lstack,
l_int32 *pxleft,
l_int32 *pxright,
l_int32 *py,
l_int32 *pdy)
{
FILLSEG *fseg;
L_STACK *auxstack;
PROCNAME("popFillseg");
if (!lstack)
return ERROR_VOID("lstack not defined", procName);
if ((auxstack = lstack->auxstack) == NULL)
return ERROR_VOID("auxstack not defined", procName);
if ((fseg = (FILLSEG *)lstackRemove(lstack)) == NULL)
return;
*pxleft = fseg->xleft;
*pxright = fseg->xright;
*py = fseg->y + fseg->dy; /* this now points to the new line */
*pdy = fseg->dy;
/* Save it for re-use */
lstackAdd(auxstack, fseg);
return;
}