![]() |
Leptonica
1.82.0
Image processing and image analysis suite
|
#include "allheaders.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) |
BOXA * | pixConnComp (PIX *pixs, PIXA **ppixa, l_int32 connectivity) |
BOXA * | pixConnCompPixa (PIX *pixs, PIXA **ppixa, l_int32 connectivity) |
BOXA * | pixConnCompBB (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) |
BOX * | pixSeedfillBB (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y, l_int32 connectivity) |
BOX * | pixSeedfill4BB (PIX *pixs, L_STACK *stack, l_int32 x, l_int32 y) |
BOX * | pixSeedfill8BB (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) |
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.
l_int32 nextOnPixelInRaster | ( | PIX * | pixs, |
l_int32 | xstart, | ||
l_int32 | ystart, | ||
l_int32 * | px, | ||
l_int32 * | py | ||
) |
[in] | pixs | 1 bpp |
[in] | xstart,ystart | starting point for search |
[out] | px,py | coord value of next ON pixel |
Definition at line 457 of file conncomp.c.
References pixGetDimensions().
Referenced by findNextUnvisited(), and pixGetOuterBorder().
|
static |
[in] | data | pix data |
[in] | w,h | width and height |
[in] | wpl | words per line |
[in] | xstart,ystart | starting point for search |
[out] | px,py | coord value of next ON pixel |
Definition at line 491 of file conncomp.c.
References GET_DATA_BIT, and FillSeg::y.
[in] | pixs | 1 bpp |
[out] | ppixa | [optional] pixa of each c.c. |
[in] | connectivity | 4 or 8 |
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 151 of file conncomp.c.
Referenced by convertNumberedMasksToBoxaa(), evalColorfillData(), pixMorphSequenceByComponent(), pixSelectByArea(), pixSelectByAreaFraction(), pixSelectByPerimSizeRatio(), pixSelectByPerimToAreaRatio(), pixSelectBySize(), pixSelectByWidthHeightRatio(), and recogPreSplittingFilter().
[in] | pixs | 1 bpp |
[in] | connectivity | 4 or 8 |
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 310 of file conncomp.c.
References FillSeg::y.
Referenced by pixAutoPhotoinvert(), and pixSelectLargeULComp().
[in] | pixs | 1 bpp |
[out] | ppixa | pixa of each c.c. |
[in] | connectivity | 4 or 8 |
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 195 of file conncomp.c.
References FillSeg::y.
l_ok pixCountConnComp | ( | PIX * | pixs, |
l_int32 | connectivity, | ||
l_int32 * | pcount | ||
) |
[in] | pixs | 1 bpp |
[in] | connectivity | 4 or 8 |
[out] | pcount |
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 394 of file conncomp.c.
References FillSeg::y.
Referenced by pixaSelectByNumConnComp(), and pixDecideIfTable().
[in] | pixs | 1 bpp |
[in] | stack | for holding fillsegs |
[in] | x,y | location of seed pixel |
[in] | connectivity | 4 or 8 |
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 852 of file conncomp.c.
[in] | pixs | 1 bpp |
[in] | stack | for holding fillsegs |
[in] | x,y | location of seed pixel |
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 896 of file conncomp.c.
References FillSeg::dy.
[in] | pixs | 1 bpp |
[in] | stack | for holding fillsegs |
[in] | x,y | location of seed pixel |
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 631 of file conncomp.c.
References FillSeg::dy.
[in] | pixs | 1 bpp |
[in] | stack | for holding fillsegs |
[in] | x,y | location of seed pixel |
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 990 of file conncomp.c.
References FillSeg::dy.
[in] | pixs | 1 bpp |
[in] | stack | for holding fillsegs |
[in] | x,y | location of seed pixel |
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 746 of file conncomp.c.
References FillSeg::dy.
[in] | pixs | 1 bpp |
[in] | stack | for holding fillsegs |
[in] | x,y | location of seed pixel |
[in] | connectivity | 4 or 8 |
Notes: (1) This is the high-level interface to Paul Heckbert's stack-based seedfill algorithm.
Definition at line 568 of file conncomp.c.
|
static |
[in] | stack | |
[out] | pxleft | left x |
[out] | pxright | right x |
[out] | py | y coordinate |
[out] | pdy | delta y |
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 1213 of file conncomp.c.
References L_Stack::auxstack, FillSeg::dy, lstackAdd(), lstackRemove(), FillSeg::xleft, FillSeg::xright, and FillSeg::y.
|
static |
[in] | stack | |
[in] | xleft,xright | |
[in] | y | |
[in] | dy | |
[in] | ymax |
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 1158 of file conncomp.c.
References L_Stack::auxstack, FillSeg::dy, lstackAdd(), lstackGetCount(), lstackRemove(), FillSeg::xleft, FillSeg::xright, and FillSeg::y.
|
static |
[in] | stack | |
[in] | xleft,xright | |
[in] | y | |
[in] | dy | |
[in] | ymax | |
[out] | pminx | minimum x |
[out] | pmaxx | maximum x |
[out] | pminy | minimum y |
[out] | pmaxy | maximum y |
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 1093 of file conncomp.c.
References L_Stack::auxstack, FillSeg::dy, lstackAdd(), lstackGetCount(), lstackRemove(), FillSeg::xleft, FillSeg::xright, and FillSeg::y.