Leptonica  1.83.1
Image processing and image analysis suite
conncomp.c File Reference
#include "allheaders.h"
#include "pix_internal.h"

Go to the source code of this file.

Data Structures

struct  FillSeg
 

Macros

#define DEBUG   0
 

Typedefs

typedef struct FillSeg FILLSEG
 

Functions

static l_int32 nextOnPixelInRasterLow (l_uint32 *data, l_int32 w, l_int32 h, l_int32 wpl, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
 
static void pushFillsegBB (L_STACK *stack, l_int32 xleft, l_int32 xright, l_int32 y, l_int32 dy, l_int32 ymax, l_int32 *pminx, l_int32 *pmaxx, l_int32 *pminy, l_int32 *pmaxy)
 
static void pushFillseg (L_STACK *stack, l_int32 xleft, l_int32 xright, l_int32 y, l_int32 dy, l_int32 ymax)
 
static void popFillseg (L_STACK *stack, l_int32 *pxleft, l_int32 *pxright, l_int32 *py, l_int32 *pdy)
 
BOXApixConnComp (PIX *pixs, PIXA **ppixa, l_int32 connectivity)
 
BOXApixConnCompPixa (PIX *pixs, PIXA **ppixa, l_int32 connectivity)
 
BOXApixConnCompBB (PIX *pixs, l_int32 connectivity)
 
l_ok pixCountConnComp (PIX *pixs, l_int32 connectivity, l_int32 *pcount)
 
l_int32 nextOnPixelInRaster (PIX *pixs, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
 
BOXpixSeedfillBB (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity)
 
BOXpixSeedfill4BB (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
 
BOXpixSeedfill8BB (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
 
l_ok pixSeedfill (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity)
 
l_ok pixSeedfill4 (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
 
l_ok pixSeedfill8 (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y)
 

Detailed Description


   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()
   static  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.

Definition in file conncomp.c.

Function Documentation

◆ nextOnPixelInRaster()

l_int32 nextOnPixelInRaster ( PIX pixs,
l_int32  xstart,
l_int32  ystart,
l_int32 *  px,
l_int32 *  py 
)

nextOnPixelInRaster()

Parameters
[in]pixs1 bpp
[in]xstart,ystartstarting point for search
[out]px,pycoord value of next ON pixel
Returns
1 if a pixel is found; 0 otherwise or on error

Definition at line 450 of file conncomp.c.

References pixGetDimensions().

Referenced by findNextUnvisited(), and pixGetOuterBorder().

◆ nextOnPixelInRasterLow()

static l_int32 nextOnPixelInRasterLow ( l_uint32 *  data,
l_int32  w,
l_int32  h,
l_int32  wpl,
l_int32  xstart,
l_int32  ystart,
l_int32 *  px,
l_int32 *  py 
)
static

nextOnPixelInRasterLow()

Parameters
[in]datapix data
[in]w,hwidth and height
[in]wplwords per line
[in]xstart,ystartstarting point for search
[out]px,pycoord value of next ON pixel
Returns
1 if a pixel is found; 0 otherwise or on error

Definition at line 482 of file conncomp.c.

References GET_DATA_BIT, and FillSeg::y.

◆ pixConnComp()

BOXA* pixConnComp ( PIX pixs,
PIXA **  ppixa,
l_int32  connectivity 
)

pixConnComp()

Parameters
[in]pixs1 bpp
[out]ppixa[optional] pixa of each c.c.
[in]connectivity4 or 8
Returns
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.

Definition at line 152 of file conncomp.c.

Referenced by convertNumberedMasksToBoxaa(), evalColorfillData(), pixMorphSequenceByComponent(), pixSelectByArea(), pixSelectByAreaFraction(), pixSelectByPerimSizeRatio(), pixSelectByPerimToAreaRatio(), pixSelectBySize(), pixSelectByWidthHeightRatio(), and recogPreSplittingFilter().

◆ pixConnCompBB()

BOXA* pixConnCompBB ( PIX pixs,
l_int32  connectivity 
)

pixConnCompBB()

Parameters
[in]pixs1 bpp
[in]connectivity4 or 8
Returns
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.

Definition at line 307 of file conncomp.c.

References FillSeg::y.

Referenced by pixAutoPhotoinvert(), and pixSelectLargeULComp().

◆ pixConnCompPixa()

BOXA* pixConnCompPixa ( PIX pixs,
PIXA **  ppixa,
l_int32  connectivity 
)

pixConnCompPixa()

Parameters
[in]pixs1 bpp
[out]ppixapixa of each c.c.
[in]connectivity4 or 8
Returns
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.

Definition at line 194 of file conncomp.c.

References FillSeg::y.

◆ pixCountConnComp()

l_ok pixCountConnComp ( PIX pixs,
l_int32  connectivity,
l_int32 *  pcount 
)

pixCountConnComp()

Parameters
[in]pixs1 bpp
[in]connectivity4 or 8
[out]pcount
Returns
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.

Definition at line 389 of file conncomp.c.

References FillSeg::y.

Referenced by pixaSelectByNumConnComp(), and pixDecideIfTable().

◆ pixSeedfill()

l_ok pixSeedfill ( PIX pixs,
L_STACK stack,
l_int32  x,
l_int32  y,
l_int32  connectivity 
)

pixSeedfill()

Parameters
[in]pixs1 bpp
[in]stackfor holding fillsegs
[in]x,ylocation of seed pixel
[in]connectivity4 or 8
Returns
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.

Definition at line 837 of file conncomp.c.

◆ pixSeedfill4()

l_ok pixSeedfill4 ( PIX pixs,
L_STACK stack,
l_int32  x,
l_int32  y 
)

pixSeedfill4()

Parameters
[in]pixs1 bpp
[in]stackfor holding fillsegs
[in]x,ylocation of seed pixel
Returns
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()

Definition at line 879 of file conncomp.c.

References FillSeg::dy.

◆ pixSeedfill4BB()

BOX* pixSeedfill4BB ( PIX pixs,
L_STACK stack,
l_int32  x,
l_int32  y 
)

pixSeedfill4BB()

Parameters
[in]pixs1 bpp
[in]stackfor holding fillsegs
[in]x,ylocation of seed pixel
Returns
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.

Definition at line 620 of file conncomp.c.

References FillSeg::dy.

◆ pixSeedfill8()

l_ok pixSeedfill8 ( PIX pixs,
L_STACK stack,
l_int32  x,
l_int32  y 
)

pixSeedfill8()

Parameters
[in]pixs1 bpp
[in]stackfor holding fillsegs
[in]x,ylocation of seed pixel
Returns
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()

Definition at line 971 of file conncomp.c.

References FillSeg::dy.

◆ pixSeedfill8BB()

BOX* pixSeedfill8BB ( PIX pixs,
L_STACK stack,
l_int32  x,
l_int32  y 
)

pixSeedfill8BB()

Parameters
[in]pixs1 bpp
[in]stackfor holding fillsegs
[in]x,ylocation of seed pixel
Returns
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.

Definition at line 733 of file conncomp.c.

References FillSeg::dy.

◆ pixSeedfillBB()

BOX* pixSeedfillBB ( PIX pixs,
L_STACK stack,
l_int32  x,
l_int32  y,
l_int32  connectivity 
)

pixSeedfillBB()

Parameters
[in]pixs1 bpp
[in]stackfor holding fillsegs
[in]x,ylocation of seed pixel
[in]connectivity4 or 8
Returns
box or NULL on error
Notes:
     (1) This is the high-level interface to Paul Heckbert's
         stack-based seedfill algorithm.

Definition at line 559 of file conncomp.c.

◆ popFillseg()

static void popFillseg ( L_STACK stack,
l_int32 *  pxleft,
l_int32 *  pxright,
l_int32 *  py,
l_int32 *  pdy 
)
static

popFillseg()

Parameters
[in]stack
[out]pxleftleft x
[out]pxrightright x
[out]pyy coordinate
[out]pdydelta y
Returns
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.

Definition at line 1188 of file conncomp.c.

References L_Stack::auxstack, FillSeg::dy, lstackAdd(), lstackRemove(), FillSeg::xleft, FillSeg::xright, and FillSeg::y.

◆ pushFillseg()

static void pushFillseg ( L_STACK stack,
l_int32  xleft,
l_int32  xright,
l_int32  y,
l_int32  dy,
l_int32  ymax 
)
static

pushFillseg()

Parameters
[in]stack
[in]xleft,xright
[in]y
[in]dy
[in]ymax
Returns
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.

Definition at line 1135 of file conncomp.c.

References L_Stack::auxstack, FillSeg::dy, lstackAdd(), lstackGetCount(), lstackRemove(), FillSeg::xleft, FillSeg::xright, and FillSeg::y.

◆ pushFillsegBB()

static void pushFillsegBB ( L_STACK stack,
l_int32  xleft,
l_int32  xright,
l_int32  y,
l_int32  dy,
l_int32  ymax,
l_int32 *  pminx,
l_int32 *  pmaxx,
l_int32 *  pminy,
l_int32 *  pmaxy 
)
static

pushFillsegBB()

Parameters
[in]stack
[in]xleft,xright
[in]y
[in]dy
[in]ymax
[out]pminxminimum x
[out]pmaxxmaximum x
[out]pminyminimum y
[out]pmaxymaximum y
Returns
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.

Definition at line 1072 of file conncomp.c.

References L_Stack::auxstack, FillSeg::dy, lstackAdd(), lstackGetCount(), lstackRemove(), FillSeg::xleft, FillSeg::xright, and FillSeg::y.