Leptonica  1.82.0
Image processing and image analysis suite
seedfill.c File Reference
#include <math.h>
#include "allheaders.h"

Go to the source code of this file.

Data Structures

struct  L_Pixel
 

Macros

#define DEBUG_PRINT_ITERS   0
 

Typedefs

typedef struct L_Pixel L_PIXEL
 

Functions

static void seedfillBinaryLow (l_uint32 *datas, l_int32 hs, l_int32 wpls, l_uint32 *datam, l_int32 hm, l_int32 wplm, l_int32 connectivity)
 
static void seedfillGrayLow (l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
 
static void seedfillGrayInvLow (l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
 
static void seedfillGrayLowSimple (l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
 
static void seedfillGrayInvLowSimple (l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
 
static void distanceFunctionLow (l_uint32 *datad, l_int32 w, l_int32 h, l_int32 d, l_int32 wpld, l_int32 connectivity)
 
static void seedspreadLow (l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld, l_uint32 *datat, l_int32 wplt, l_int32 connectivity)
 
static l_int32 pixQualifyLocalMinima (PIX *pixs, PIX *pixm, l_int32 maxval)
 
PIXpixSeedfillBinary (PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity)
 
PIXpixSeedfillBinaryRestricted (PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 xmax, l_int32 ymax)
 
PIXpixHolesByFilling (PIX *pixs, l_int32 connectivity)
 
PIXpixFillClosedBorders (PIX *pixs, l_int32 connectivity)
 
PIXpixExtractBorderConnComps (PIX *pixs, l_int32 connectivity)
 
PIXpixRemoveBorderConnComps (PIX *pixs, l_int32 connectivity)
 
PIXpixFillBgFromBorder (PIX *pixs, l_int32 connectivity)
 
PIXpixFillHolesToBoundingRect (PIX *pixs, l_int32 minsize, l_float32 maxhfract, l_float32 minfgfract)
 
l_ok pixSeedfillGray (PIX *pixs, PIX *pixm, l_int32 connectivity)
 
l_ok pixSeedfillGrayInv (PIX *pixs, PIX *pixm, l_int32 connectivity)
 
l_ok pixSeedfillGraySimple (PIX *pixs, PIX *pixm, l_int32 connectivity)
 
l_ok pixSeedfillGrayInvSimple (PIX *pixs, PIX *pixm, l_int32 connectivity)
 
PIXpixSeedfillGrayBasin (PIX *pixb, PIX *pixm, l_int32 delta, l_int32 connectivity)
 
PIXpixDistanceFunction (PIX *pixs, l_int32 connectivity, l_int32 outdepth, l_int32 boundcond)
 
PIXpixSeedspread (PIX *pixs, l_int32 connectivity)
 
l_ok pixLocalExtrema (PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
 
l_ok pixSelectedLocalExtrema (PIX *pixs, l_int32 mindist, PIX **ppixmin, PIX **ppixmax)
 
PIXpixFindEqualValues (PIX *pixs1, PIX *pixs2)
 
l_ok pixSelectMinInConnComp (PIX *pixs, PIX *pixm, PTA **ppta, NUMA **pnav)
 
PIXpixRemoveSeededComponents (PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
 

Variables

static const l_int32 MaxIters = 40
 

Detailed Description


     Binary seedfill (source: Luc Vincent)
              PIX         *pixSeedfillBinary()
              PIX         *pixSeedfillBinaryRestricted()
              static void  seedfillBinaryLow()

     Applications of binary seedfill to find and fill holes,
     remove c.c. touching the border and fill bg from border:
              PIX         *pixHolesByFilling()
              PIX         *pixFillClosedBorders()
              PIX         *pixExtractBorderConnComps()
              PIX         *pixRemoveBorderConnComps()
              PIX         *pixFillBgFromBorder()

     Hole-filling of components to bounding rectangle
              PIX         *pixFillHolesToBoundingRect()

     Gray seedfill (source: Luc Vincent:fast-hybrid-grayscale-reconstruction)
              l_int32      pixSeedfillGray()
              l_int32      pixSeedfillGrayInv()
              static void  seedfillGrayLow()
              static void  seedfillGrayInvLow()


     Gray seedfill (source: Luc Vincent: sequential-reconstruction algorithm)
              l_int32      pixSeedfillGraySimple()
              l_int32      pixSeedfillGrayInvSimple()
              static void  seedfillGrayLowSimple()
              static void  seedfillGrayInvLowSimple()

     Gray seedfill variations
              PIX         *pixSeedfillGrayBasin()

     Distance function (source: Luc Vincent)
              PIX         *pixDistanceFunction()
              static void  distanceFunctionLow()

     Seed spread (based on distance function)
              PIX         *pixSeedspread()
              static void  seedspreadLow()

     Local extrema:
              l_int32      pixLocalExtrema()
           static l_int32  pixQualifyLocalMinima()
              l_int32      pixSelectedLocalExtrema()
              PIX         *pixFindEqualValues()

     Selection of minima in mask of connected components
              PTA         *pixSelectMinInConnComp()

     Removal of seeded connected components from a mask
              PIX         *pixRemoveSeededComponents()


          ITERATIVE RASTER-ORDER SEEDFILL

     The basic method in the Vincent seedfill (aka reconstruction)
     algorithm is simple.  We describe here the situation for
     binary seedfill.  Pixels are sampled in raster order in
     the seed image.  If they are 4-connected to ON pixels
     either directly above or to the left, and are not masked
     out by the mask image, they are turned on (or remain on).
     (Ditto for 8-connected, except you need to check 3 pixels
     on the previous line as well as the pixel to the left
     on the current line.  This is extra computational work
     for relatively little gain, so it is preferable
     in most situations to use the 4-connected version.)
     The algorithm proceeds from UR to LL of the image, and
     then reverses and sweeps up from LL to UR.
     These double sweeps are iterated until there is no change.
     At this point, the seed has entirely filled the region it
     is allowed to, as delimited by the mask image.

     The grayscale seedfill is a straightforward generalization
     of the binary seedfill, and is described in seedfillLowGray().

     For some applications, the filled seed will later be OR'd
     with the negative of the mask.   This is used, for example,
     when you flood fill into a 4-connected region of OFF pixels
     and you want the result after those pixels are turned ON.

     Note carefully that the mask we use delineates which pixels
     are allowed to be ON as the seed is filled.  We will call this
     a "filling mask".  As the seed expands, it is repeatedly
     ANDed with the filling mask: s & fm.  The process can equivalently
     be formulated using the inverse of the filling mask, which
     we will call a "blocking mask": bm = ~fm.   As the seed
     expands, the blocking mask is repeatedly used to prevent
     the seed from expanding into the blocking mask.  This is done
     by set subtracting the blocking mask from the expanded seed:
     s - bm.  Set subtraction of the blocking mask is equivalent
     to ANDing with the inverse of the blocking mask: s & (~bm).
     But from the inverse relation between blocking and filling
     masks, this is equal to s & fm, which proves the equivalence.

     For efficiency, the pixels can be taken in larger units
     for processing, but still in raster order.  It is natural
     to take them in 32-bit words.  The outline of the work
     to be done for 4-cc (not including special cases for boundary
     words, such as the first line or the last word in each line)
     is as follows.  Let the filling mask be m.  The
     seed is to fill "under" the mask; i.e., limited by an AND
     with the mask.  Let the current word be w, the word
     in the line above be wa, and the previous word in the
     current line be wp.   Let t be a temporary word that
     is used in computation.  Note that masking is performed by
     w & m.  (If we had instead used a "blocking" mask, we
     would perform masking by the set subtraction operation,
     w - m, which is defined to be w & ~m.)

     The entire operation can be implemented with shifts,
     logical operations and tests.  For each word in the seed image
     there are two steps.  The first step is to OR the word with
     the word above and with the rightmost pixel in wp (call it "x").
     Because wp is shifted one pixel to its right, "x" is ORed
     to the leftmost pixel of w.  We then clip to the ON pixels in
     the mask.  The result is
              t  <--  (w | wa | x000... ) & m
     We've now finished taking data from above and to the left.
     The second step is to allow filling to propagate horizontally
     in t, always making sure that it is properly masked at each
     step.  So if filling can be done (i.e., t is neither all 0s
     nor all 1s), iteratively take:
          t  <--  (t | (t >> 1) | (t << 1)) & m
     until t stops changing.  Then write t back into w.

     Finally, the boundary conditions require we note that in doing
     the above steps:
         (a) The words in the first row have no wa
         (b) The first word in each row has no wp in that row
         (c) The last word in each row must be masked so that
             pixels don't propagate beyond the right edge of the
             actual image.  (This is easily accomplished by
             setting the out-of-bound pixels in m to OFF.)

Definition in file seedfill.c.

Function Documentation

◆ pixDistanceFunction()

PIX* pixDistanceFunction ( PIX pixs,
l_int32  connectivity,
l_int32  outdepth,
l_int32  boundcond 
)

pixDistanceFunction()

Parameters
[in]pixs1 bpp
[in]connectivity4 or 8
[in]outdepth8 or 16 bits for pixd
[in]boundcondL_BOUNDARY_BG, L_BOUNDARY_FG
Returns
pixd, or NULL on error
Notes:
     (1) This computes the distance of each pixel from the nearest
         background pixel.  All bg pixels therefore have a distance of 0,
         and the fg pixel distances increase linearly from 1 at the
         boundary.  It can also be used to compute the distance of
         each pixel from the nearest fg pixel, by inverting the input
         image before calling this function.  Then all fg pixels have
         a distance 0 and the bg pixel distances increase linearly
         from 1 at the boundary.
     (2) The algorithm, described in Leptonica on the page on seed
         filling and connected components, is due to Luc Vincent.
         In brief, we generate an 8 or 16 bpp image, initialized
         with the fg pixels of the input pix set to 1 and the
         1-boundary pixels (i.e., the boundary pixels of width 1 on
         the four sides set as either:
           * L_BOUNDARY_BG: 0
           * L_BOUNDARY_FG:  max
         where max = 0xff for 8 bpp and 0xffff for 16 bpp.
         Then do raster/anti-raster sweeps over all pixels interior
         to the 1-boundary, where the value of each new pixel is
         taken to be 1 more than the minimum of the previously-seen
         connected pixels (using either 4 or 8 connectivity).
         Finally, set the 1-boundary pixels using the mirrored method;
         this removes the max values there.
     (3) Using L_BOUNDARY_BG clamps the distance to 0 at the
         boundary.  Using L_BOUNDARY_FG allows the distance
         at the image boundary to "float".
     (4) For 4-connected, one could initialize only the left and top
         1-boundary pixels, and go all the way to the right
         and bottom; then coming back reset left and top.  But we
         instead use a method that works for both 4- and 8-connected.

Definition at line 2535 of file seedfill.c.

Referenced by pixFindStrokeWidth().

◆ pixExtractBorderConnComps()

PIX* pixExtractBorderConnComps ( PIX pixs,
l_int32  connectivity 
)

pixExtractBorderConnComps()

Parameters
[in]pixs1 bpp
[in]connectivityfilling connectivity 4 or 8
Returns
pixd all pixels in the src that are in connected components touching the border, or NULL on error

Definition at line 698 of file seedfill.c.

◆ pixFillBgFromBorder()

PIX* pixFillBgFromBorder ( PIX pixs,
l_int32  connectivity 
)

pixFillBgFromBorder()

Parameters
[in]pixs1 bpp
[in]connectivityfilling connectivity 4 or 8
Returns
pixd with the background c.c. touching the border filled to foreground, or NULL on error
Notes:
     (1) This fills all bg components touching the border to fg.
         It is the photometric inverse of pixRemoveBorderConnComps().
     (2) Invert the result to get the "holes" left after this fill.
         This can be done multiple times, extracting holes within
         holes after each pair of fillings.  Specifically, this code
         peels away n successive embeddings of components:
pix1 = <initial image>
for (i = 0; i < 2 * n; i++) {
pix2 = pixFillBgFromBorder(pix1, 8);
pixInvert(pix2, pix2);
pixDestroy(&pix1);
pix1 = pix2;
}
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
PIX * pixInvert(PIX *pixd, PIX *pixs)
pixInvert()
Definition: pix3.c:1509
PIX * pixFillBgFromBorder(PIX *pixs, l_int32 connectivity)
pixFillBgFromBorder()
Definition: seedfill.c:787

Definition at line 787 of file seedfill.c.

◆ pixFillClosedBorders()

PIX* pixFillClosedBorders ( PIX pixs,
l_int32  connectivity 
)

pixFillClosedBorders()

Parameters
[in]pixs1 bpp
[in]connectivityfilling connectivity 4 or 8
Returns
pixd all topologically outer closed borders are filled as connected comonents, or NULL on error
Notes:
     (1) Start with 1-pixel black border on otherwise white pixd
     (2) Subtract input pixs to remove border pixels that were
         also on the closed border
     (3) Use the inverted pixs as the filling mask to fill in
         all the pixels from the outer border to the closed border
         on pixs
     (4) Invert the result to get the filled component, including
         the input border
     (5) If the borders are 4-c.c., use 8-c.c. filling, and v.v.
     (6) Closed borders within c.c. that represent holes, etc., are filled.

Definition at line 660 of file seedfill.c.

Referenced by ccbaDisplayImage1().

◆ pixFillHolesToBoundingRect()

PIX* pixFillHolesToBoundingRect ( PIX pixs,
l_int32  minsize,
l_float32  maxhfract,
l_float32  minfgfract 
)

pixFillHolesToBoundingRect()

Parameters
[in]pixs1 bpp
[in]minsizemin number of pixels in the hole
[in]maxhfractmax hole area as fraction of fg pixels in the cc
[in]minfgfractmin fg area as fraction of bounding rectangle
Returns
pixd with some holes possibly filled and some c.c. possibly expanded to their bounding rects, or NULL on error
Notes:
     (1) This does not fill holes that are smaller in area than 'minsize'.
         Use minsize = 0 and maxhfract = 1.0 to fill all holes.
     (2) This does not fill holes with an area larger than
         maxhfract times the fg area of the c.c.
         Use 1.0 to fill all holes.
     (3) This does not expand the fg of the c.c. to bounding rect if
         the fg area is less than minfgfract times the area of the
         bounding rect.  Use 1.0 to skip expanding to the bounding rect.
     (4) The decisions are made as follows:
          ~ Decide if we are filling the holes; if so, when using
            the fg area, include the filled holes.
          ~ Decide based on the fg area if we are filling to a bounding rect.
            If so, do it.
            If not, fill the holes if the condition is satisfied.
     (5) The choice of minsize depends on the resolution.
     (6) For solidifying image mask regions on printed materials,
         which tend to be rectangular, values for maxhfract
         and minfgfract around 0.5 are reasonable.

Definition at line 847 of file seedfill.c.

Referenced by pixAutoPhotoinvert().

◆ pixFindEqualValues()

PIX* pixFindEqualValues ( PIX pixs1,
PIX pixs2 
)

pixFindEqualValues()

Parameters
[in]pixs18 bpp
[in]pixs28 bpp
Returns
pixd 1 bpp mask, or NULL on error
Notes:
     (1) The two images are aligned at the UL corner, and the returned
         image has ON pixels where the pixels in pixs1 and pixs2
         have equal values.

Definition at line 3251 of file seedfill.c.

◆ pixHolesByFilling()

PIX* pixHolesByFilling ( PIX pixs,
l_int32  connectivity 
)

pixHolesByFilling()

Parameters
[in]pixs1 bpp
[in]connectivity4 or 8
Returns
pixd inverted image of all holes, or NULL on error

Action: 1 Start with 1-pixel black border on otherwise white pixd 2 Use the inverted pixs as the filling mask to fill in all the pixels from the border to the pixs foreground 3 OR the result with pixs to have an image with all ON pixels except for the holes. 4 Invert the result to get the holes as foreground

Notes:
    (1) To get 4-c.c. holes of the 8-c.c. as foreground, use
        4-connected filling; to get 8-c.c. holes of the 4-c.c.
        as foreground, use 8-connected filling.

Definition at line 609 of file seedfill.c.

◆ pixLocalExtrema()

l_ok pixLocalExtrema ( PIX pixs,
l_int32  maxmin,
l_int32  minmax,
PIX **  ppixmin,
PIX **  ppixmax 
)

pixLocalExtrema()

Parameters
[in]pixs8 bpp
[in]maxminmax allowed for the min in a 3x3 neighborhood; use 0 for default which is to have no upper bound
[in]minmaxmin allowed for the max in a 3x3 neighborhood; use 0 for default which is to have no lower bound
[out]ppixmin[optional] mask of local minima
[out]ppixmax[optional] mask of local maxima
Returns
0 if OK, 1 on error
Notes:
     (1) This gives the actual local minima and maxima.
         A local minimum is a pixel whose surrounding pixels all
         have values at least as large, and likewise for a local
         maximum.  For the local minima, maxmin is the upper
         bound for the value of pixs.  Likewise, for the local maxima,
         minmax is the lower bound for the value of pixs.
     (2) The minima are found by starting with the erosion-and-equality
         approach of pixSelectedLocalExtrema().  This is followed
         by a qualification step, where each c.c. in the resulting
         minimum mask is extracted, the pixels bordering it are
         located, and they are queried.  If all of those pixels
         are larger than the value of that minimum, it is a true
         minimum and its c.c. is saved; otherwise the c.c. is
         rejected.  Note that if a bordering pixel has the
         same value as the minimum, it must then have a
         neighbor that is smaller, so the component is not a
         true minimum.
     (3) The maxima are found by inverting the image and looking
         for the minima there.
     (4) The generated masks can be used as markers for
         further operations.

Definition at line 3019 of file seedfill.c.

◆ pixQualifyLocalMinima()

static l_int32 pixQualifyLocalMinima ( PIX pixs,
PIX pixm,
l_int32  maxval 
)
static

pixQualifyLocalMinima()

Parameters
[in]pixs8 bpp image from which pixm has been extracted
[in]pixm1 bpp mask of values equal to min in 3x3 neighborhood
[in]maxvalmax allowed for the min in a 3x3 neighborhood; use 0 for default which is to have no upper bound
Returns
0 if OK, 1 on error
Notes:
     (1) This function acts in-place to remove all c.c. in pixm
         that are not true local minima in pixs.  As seen in
         pixLocalExtrema(), the input pixm are found by selecting those
         pixels of pixs whose values do not change with a 3x3
         grayscale erosion.  Here, we require that for each c.c.
         in pixm, all pixels in pixs that correspond to the exterior
         boundary pixels of the c.c. have values that are greater
         than the value within the c.c.
     (2) The maximum allowed value for each local minimum can be
         bounded with maxval.  Use 0 for default, which is to have
         no upper bound (equivalent to maxval == 254).

Definition at line 3083 of file seedfill.c.

◆ pixRemoveBorderConnComps()

PIX* pixRemoveBorderConnComps ( PIX pixs,
l_int32  connectivity 
)

pixRemoveBorderConnComps()

Parameters
[in]pixs1 bpp
[in]connectivityfilling connectivity 4 or 8
Returns
pixd all pixels in the src that are not touching the border or NULL on error
Notes:
     (1) This removes all fg components touching the border.

Definition at line 737 of file seedfill.c.

◆ pixRemoveSeededComponents()

PIX* pixRemoveSeededComponents ( PIX pixd,
PIX pixs,
PIX pixm,
l_int32  connectivity,
l_int32  bordersize 
)

pixRemoveSeededComponents()

Parameters
[in]pixd[optional]; can be null or equal to pixm; 1 bpp
[in]pixs1 bpp seed
[in]pixm1 bpp filling mask
[in]connectivity4 or 8
[in]bordersizeamount of border clearing
Returns
pixd, or NULL on error
Notes:
     (1) This removes each component in pixm for which there is
         at least one seed in pixs.  If pixd == NULL, this returns
         the result in a new pixd.  Otherwise, it is an in-place
         operation on pixm.  In no situation is pixs altered,
         because we do the filling with a copy of pixs.
     (2) If bordersize > 0, it also clears all pixels within a
         distance bordersize of the edge of pixd.  This is here
         because pixLocalExtrema() typically finds local minima
         at the border.  Use bordersize >= 2 to remove these.

Definition at line 3431 of file seedfill.c.

◆ pixSeedfillBinary()

PIX* pixSeedfillBinary ( PIX pixd,
PIX pixs,
PIX pixm,
l_int32  connectivity 
)

pixSeedfillBinary()

Parameters
[in]pixd[optional]; can be null, equal to pixs, or different from pixs; 1 bpp
[in]pixs1 bpp seed
[in]pixm1 bpp filling mask
[in]connectivity4 or 8
Returns
pixd always
Notes:
     (1) This is for binary seedfill (aka "binary reconstruction").
     (2) There are 3 cases:
           (a) pixd == null (make a new pixd)
           (b) pixd == pixs (in-place)
           (c) pixd != pixs
     (3) If you know the case, use these patterns for clarity:
           (a) pixd = pixSeedfillBinary(NULL, pixs, ...);
           (b) pixSeedfillBinary(pixs, pixs, ...);
           (c) pixSeedfillBinary(pixd, pixs, ...);
     (4) The resulting pixd contains the filled seed.  For some
         applications you want to OR it with the inverse of
         the filling mask.
     (5) The input seed and mask images can be different sizes, but
         in typical use the difference, if any, would be only
         a few pixels in each direction.  If the sizes differ,
         the clipping is handled by the low-level function
         seedfillBinaryLow().

Definition at line 247 of file seedfill.c.

Referenced by ccbaDisplayImage1(), ccbaDisplayImage2(), and pixDecideIfTable().

◆ pixSeedfillBinaryRestricted()

PIX* pixSeedfillBinaryRestricted ( PIX pixd,
PIX pixs,
PIX pixm,
l_int32  connectivity,
l_int32  xmax,
l_int32  ymax 
)

pixSeedfillBinaryRestricted()

Parameters
[in]pixd[optional]; can be null, equal to pixs, or different from pixs; 1 bpp
[in]pixs1 bpp seed
[in]pixm1 bpp filling mask
[in]connectivity4 or 8
[in]xmaxmax distance in x direction of fill into mask
[in]ymaxmax distance in y direction of fill into mask
Returns
pixd always
Notes:
     (1) See usage for pixSeedfillBinary(), which has unrestricted fill.
         In pixSeedfillBinary(), the filling distance is unrestricted
         and can be larger than pixs, depending on the topology of
         th mask.
     (2) There are occasions where it is useful not to permit the
         fill to go more than a certain distance into the mask.
         xmax specifies the maximum horizontal distance allowed
         in the fill; ymax does likewise in the vertical direction.
     (3) Operationally, the max "distance" allowed for the fill
         is a linear distance from the original seed, independent
         of the actual mask topology.
     (4) Another formulation of this problem, not implemented,
         would use the manhattan distance from the seed, as
         determined by a breadth-first search starting at the seed
         boundaries and working outward where the mask fg allows.
         How this might use the constraints of separate xmax and ymax
         is not clear.

Definition at line 335 of file seedfill.c.

◆ pixSeedfillGray()

l_ok pixSeedfillGray ( PIX pixs,
PIX pixm,
l_int32  connectivity 
)

pixSeedfillGray()

Parameters
[in]pixs8 bpp seed; filled in place
[in]pixm8 bpp filling mask
[in]connectivity4 or 8
Returns
0 if OK, 1 on error
Notes:
     (1) This is an in-place filling operation on the seed, pixs,
         where the clipping mask is always above or at the level
         of the seed as it is filled.
     (2) For details of the operation, see the description in
         seedfillGrayLow() and the code there.
     (3) As an example of use, see the description in pixHDome().
         There, the seed is an image where each pixel is a fixed
         amount smaller than the corresponding mask pixel.
     (4) Reference paper :
           L. Vincent, Morphological grayscale reconstruction in image
           analysis: applications and efficient algorithms, IEEE Transactions
           on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

Definition at line 929 of file seedfill.c.

◆ pixSeedfillGrayBasin()

PIX* pixSeedfillGrayBasin ( PIX pixb,
PIX pixm,
l_int32  delta,
l_int32  connectivity 
)

pixSeedfillGrayBasin()

Parameters
[in]pixbbinary mask giving seed locations
[in]pixm8 bpp basin-type filling mask
[in]deltaamount of seed value above mask
[in]connectivity4 or 8
Returns
pixd filled seed if OK, NULL on error
Notes:
     (1) This fills from a seed within basins defined by a filling mask.
         The seed value(s) are greater than the corresponding
         filling mask value, and the result has the bottoms of
         the basins raised by the initial seed value.
     (2) The seed has value 255 except where pixb has fg (1), which
         are the seed 'locations'.  At the seed locations, the seed
         value is the corresponding value of the mask pixel in pixm
         plus delta.  If delta == 0, we return a copy of pixm.
     (3) The actual filling is done using the standard grayscale filling
         operation on the inverse of the mask and using the inverse
         of the seed image.  After filling, we return the inverse of
         the filled seed.
     (4) As an example of use: pixm can describe a grayscale image
         of text, where the (dark) text pixels are basins of
         low values; pixb can identify the local minima in pixm (say, at
         the bottom of the basins); and delta is the amount that we wish
         to raise (lighten) the basins.  We construct the seed
         (a.k.a marker) image from pixb, pixm and delta.

Definition at line 2444 of file seedfill.c.

◆ pixSeedfillGrayInv()

l_ok pixSeedfillGrayInv ( PIX pixs,
PIX pixm,
l_int32  connectivity 
)

pixSeedfillGrayInv()

Parameters
[in]pixs8 bpp seed; filled in place
[in]pixm8 bpp filling mask
[in]connectivity4 or 8
Returns
0 if OK, 1 on error
Notes:
     (1) This is an in-place filling operation on the seed, pixs,
         where the clipping mask is always below or at the level
         of the seed as it is filled.  Think of filling up a basin
         to a particular level, given by the maximum seed value
         in the basin.  Outside the filled region, the mask
         is above the filling level.
     (2) Contrast this with pixSeedfillGray(), where the clipping mask
         is always above or at the level of the fill.  An example
         of its use is the hdome fill, where the seed is an image
         where each pixel is a fixed amount smaller than the
         corresponding mask pixel.
     (3) The basin fill, pixSeedfillGrayBasin(), is a special case
         where the seed pixel values are generated from the mask,
         and where the implementation uses pixSeedfillGray() by
         inverting both the seed and mask.

Definition at line 988 of file seedfill.c.

◆ pixSeedfillGrayInvSimple()

l_ok pixSeedfillGrayInvSimple ( PIX pixs,
PIX pixm,
l_int32  connectivity 
)

pixSeedfillGrayInvSimple()

Parameters
[in]pixs8 bpp seed; filled in place
[in]pixm8 bpp filling mask
[in]connectivity4 or 8
Returns
0 if OK, 1 on error
Notes:
     (1) This is an in-place filling operation on the seed, pixs,
         where the clipping mask is always below or at the level
         of the seed as it is filled.  Think of filling up a basin
         to a particular level, given by the maximum seed value
         in the basin.  Outside the filled region, the mask
         is above the filling level.
     (2) Contrast this with pixSeedfillGraySimple(), where the clipping mask
         is always above or at the level of the fill.  An example
         of its use is the hdome fill, where the seed is an image
         where each pixel is a fixed amount smaller than the
         corresponding mask pixel.

Definition at line 2042 of file seedfill.c.

◆ pixSeedfillGraySimple()

l_ok pixSeedfillGraySimple ( PIX pixs,
PIX pixm,
l_int32  connectivity 
)

pixSeedfillGraySimple()

Parameters
[in]pixs8 bpp seed; filled in place
[in]pixm8 bpp filling mask
[in]connectivity4 or 8
Returns
0 if OK, 1 on error
Notes:
     (1) This is an in-place filling operation on the seed, pixs,
         where the clipping mask is always above or at the level
         of the seed as it is filled.
     (2) For details of the operation, see the description in
         seedfillGrayLowSimple() and the code there.
     (3) As an example of use, see the description in pixHDome().
         There, the seed is an image where each pixel is a fixed
         amount smaller than the corresponding mask pixel.
     (4) Reference paper :
           L. Vincent, Morphological grayscale reconstruction in image
           analysis: applications and efficient algorithms, IEEE Transactions
           on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

Definition at line 1971 of file seedfill.c.

◆ pixSeedspread()

PIX* pixSeedspread ( PIX pixs,
l_int32  connectivity 
)

pixSeedspread()

Parameters
[in]pixs8 bpp
[in]connectivity4 or 8
Returns
pixd, or NULL on error
Notes:
     (1) The raster/anti-raster method for implementing this filling
         operation was suggested by Ray Smith.
     (2) This takes an arbitrary set of nonzero pixels in pixs, which
         can be sparse, and spreads (extrapolates) the values to
         fill all the pixels in pixd with the nonzero value it is
         closest to in pixs.  This is similar (though not completely
         equivalent) to doing a Voronoi tiling of the image, with a
         tile surrounding each pixel that has a nonzero value.
         All pixels within a tile are then closer to its "central"
         pixel than to any others.  Then assign the value of the
         "central" pixel to each pixel in the tile.
     (3) This is implemented by computing a distance function in parallel
         with the fill.  The distance function uses free boundary
         conditions (assumed maxval outside), and it controls the
         propagation of the pixels in pixd away from the nonzero
         (seed) values.  This is done in 2 traversals (raster/antiraster).
         In the raster direction, whenever the distance function
         is nonzero, the spread pixel takes on the value of its
         predecessor that has the minimum distance value.  In the
         antiraster direction, whenever the distance function is nonzero
         and its value is replaced by a smaller value, the spread
         pixel takes the value of the predecessor with the minimum
         distance value.
     (4) At boundaries where a pixel is equidistant from two
         nearest nonzero (seed) pixels, the decision of which value
         to use is arbitrary (greedy in search for minimum distance).
         This can give rise to strange-looking results, particularly
         for 4-connectivity where the L1 distance is computed from
         steps in N,S,E and W directions (no diagonals).

Definition at line 2792 of file seedfill.c.

Referenced by makeColorfillTestData().

◆ pixSelectedLocalExtrema()

l_ok pixSelectedLocalExtrema ( PIX pixs,
l_int32  mindist,
PIX **  ppixmin,
PIX **  ppixmax 
)

pixSelectedLocalExtrema()

Parameters
[in]pixs8 bpp
[in]mindist-1 for keeping all pixels; >= 0 specifies distance
[out]ppixminmask of local minima
[out]ppixmaxmask of local maxima
Returns
0 if OK, 1 on error
Notes:
     (1) This selects those local 3x3 minima that are at least a
         specified distance from the nearest local 3x3 maxima, and v.v.
         for the selected set of local 3x3 maxima.
         The local 3x3 minima is the set of pixels whose value equals
         the value after a 3x3 brick erosion, and the local 3x3 maxima
         is the set of pixels whose value equals the value after
         a 3x3 brick dilation.
     (2) mindist is the minimum distance allowed between
         local 3x3 minima and local 3x3 maxima, in an 8-connected sense.
         mindist == 1 keeps all pixels found in step 1.
         mindist == 0 removes all pixels from each mask that are
         both a local 3x3 minimum and a local 3x3 maximum.
         mindist == 1 removes any local 3x3 minimum pixel that touches a
         local 3x3 maximum pixel, and likewise for the local maxima.
         To make the decision, visualize each local 3x3 minimum pixel
         as being surrounded by a square of size (2 * mindist + 1)
         on each side, such that no local 3x3 maximum pixel is within
         that square; and v.v.
     (3) The generated masks can be used as markers for further operations.

Definition at line 3191 of file seedfill.c.

◆ pixSelectMinInConnComp()

l_ok pixSelectMinInConnComp ( PIX pixs,
PIX pixm,
PTA **  ppta,
NUMA **  pnav 
)

pixSelectMinInConnComp()

Parameters
[in]pixs8 bpp
[in]pixm1 bpp
[out]pptapta of min pixel locations
[out]pnav[optional] numa of minima values
Returns
0 if OK, 1 on error.
Notes:
     (1) For each 8 connected component in pixm, this finds
         a pixel in pixs that has the lowest value, and saves
         it in a Pta.  If several pixels in pixs have the same
         minimum value, it picks the first one found.
     (2) For a mask pixm of true local minima, all pixels in each
         connected component have the same value in pixs, so it is
         fastest to select one of them using a special seedfill
         operation.  Not yet implemented.

Definition at line 3318 of file seedfill.c.

Referenced by wshedApply().

◆ seedfillBinaryLow()

static void seedfillBinaryLow ( l_uint32 *  datas,
l_int32  hs,
l_int32  wpls,
l_uint32 *  datam,
l_int32  hm,
l_int32  wplm,
l_int32  connectivity 
)
static

seedfillBinaryLow()

Notes: (1) This is an in-place fill, where the seed image is filled, clipping to the filling mask, in one full cycle of UL -> LR and LR -> UL raster scans. (2) Assume the mask is a filling mask, not a blocking mask. (3) Assume that the RHS pad bits of the mask are properly set to 0. (4) Clip to the smallest dimensions to avoid invalid reads.

Definition at line 403 of file seedfill.c.

◆ seedfillGrayInvLow()

static void seedfillGrayInvLow ( l_uint32 *  datas,
l_int32  w,
l_int32  h,
l_int32  wpls,
l_uint32 *  datam,
l_int32  wplm,
l_int32  connectivity 
)
static

seedfillGrayInvLow()

Notes: (1) The pixels are numbered as follows: 1 2 3 4 x 5 6 7 8 This low-level filling operation consists of two scans, raster and anti-raster, covering the entire seed image. During the anti-raster scan, every pixel p such that its current value could still be propagated during the next raster scanning is put into the FIFO-queue. Next step is the propagation step where where we update and propagate the values using FIFO structure created in anti-raster scan. (2) The "Inv" signifies the fact that in this case, filling of the seed only takes place when the seed value is greater than the mask value. The mask will act to stop the fill when it is higher than the seed level. (This is in contrast to conventional grayscale filling where the seed always fills below the mask.) (3) An example of use is a basin, described by the mask (pixm), where within the basin, the seed pix (pixs) gets filled to the height of the highest seed pixel that is above its corresponding max pixel. Filling occurs while the propagating seed pixels in pixs are larger than the corresponding mask values in pixm. (4) Reference paper : L. Vincent, Morphological grayscale reconstruction in image analysis: applications and efficient algorithms, IEEE Transactions on Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

Definition at line 1516 of file seedfill.c.

References GET_DATA_BYTE, lqueueAdd(), lqueueCreate(), lqueueDestroy(), lqueueGetCount(), lqueueRemove(), and SET_DATA_BYTE.

◆ seedfillGrayInvLowSimple()

static void seedfillGrayInvLowSimple ( l_uint32 *  datas,
l_int32  w,
l_int32  h,
l_int32  wpls,
l_uint32 *  datam,
l_int32  wplm,
l_int32  connectivity 
)
static

seedfillGrayInvLowSimple()

Notes: (1) The pixels are numbered as follows: 1 2 3 4 x 5 6 7 8 This low-level filling operation consists of two scans, raster and anti-raster, covering the entire seed image. The caller typically iterates until the filling is complete. (2) The "Inv" signifies the fact that in this case, filling of the seed only takes place when the seed value is greater than the mask value. The mask will act to stop the fill when it is higher than the seed level. (This is in contrast to conventional grayscale filling where the seed always fills below the mask.) (3) An example of use is a basin, described by the mask (pixm), where within the basin, the seed pix (pixs) gets filled to the height of the highest seed pixel that is above its corresponding max pixel. Filling occurs while the propagating seed pixels in pixs are larger than the corresponding mask values in pixm.

Definition at line 2279 of file seedfill.c.

References GET_DATA_BYTE, and SET_DATA_BYTE.

◆ seedfillGrayLow()

static void seedfillGrayLow ( l_uint32 *  datas,
l_int32  w,
l_int32  h,
l_int32  wpls,
l_uint32 *  datam,
l_int32  wplm,
l_int32  connectivity 
)
static

seedfillGrayLow()

Notes: (1) The pixels are numbered as follows: 1 2 3 4 x 5 6 7 8 This low-level filling operation consists of two scans, raster and anti-raster, covering the entire seed image. This is followed by a breadth-first propagation operation to complete the fill. During the anti-raster scan, every pixel p whose current value could still be propagated after the anti-raster scan is put into the FIFO queue. The propagation step is a breadth-first fill to completion. Unlike the simple grayscale seedfill pixSeedfillGraySimple(), where at least two full raster/anti-raster iterations are required for completion and verification, the hybrid method uses only a single raster/anti-raster set of scans. (2) The filling action can be visualized from the following example. Suppose the mask, which clips the fill, is a sombrero-shaped surface, where the highest point is 200 and the low pixels around the rim are 30. Beyond the rim, the mask goes up a bit. Suppose the seed, which is filled, consists of a single point of height 150, located below the max of the mask, with the rest 0. Then in the raster scan, nothing happens until the high seed point is encountered, and then this value is propagated right and down, until it hits the side of the sombrero. The seed can never exceed the mask, so it fills to the rim, going lower along the mask surface. When it passes the rim, the seed continues to fill at the rim height to the edge of the seed image. Then on the anti-raster scan, the seed fills flat inside the sombrero to the upper and left, and then out from the rim as before. The final result has a seed that is flat outside the rim, and inside it fills the sombrero but only up to 150. If the rim height varies, the filled seed outside the rim will be at the highest point on the rim, which is a saddle point on the rim. (3) Reference paper : L. Vincent, Morphological grayscale reconstruction in image analysis: applications and efficient algorithms, IEEE Transactions on Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

Definition at line 1065 of file seedfill.c.

References GET_DATA_BYTE, lqueueAdd(), lqueueCreate(), lqueueDestroy(), lqueueGetCount(), lqueueRemove(), and SET_DATA_BYTE.

◆ seedfillGrayLowSimple()

static void seedfillGrayLowSimple ( l_uint32 *  datas,
l_int32  w,
l_int32  h,
l_int32  wpls,
l_uint32 *  datam,
l_int32  wplm,
l_int32  connectivity 
)
static

seedfillGrayLowSimple()

Notes: (1) The pixels are numbered as follows: 1 2 3 4 x 5 6 7 8 This low-level filling operation consists of two scans, raster and anti-raster, covering the entire seed image. The caller typically iterates until the filling is complete. (2) The filling action can be visualized from the following example. Suppose the mask, which clips the fill, is a sombrero-shaped surface, where the highest point is 200 and the low pixels around the rim are 30. Beyond the rim, the mask goes up a bit. Suppose the seed, which is filled, consists of a single point of height 150, located below the max of the mask, with the rest 0. Then in the raster scan, nothing happens until the high seed point is encountered, and then this value is propagated right and down, until it hits the side of the sombrero. The seed can never exceed the mask, so it fills to the rim, going lower along the mask surface. When it passes the rim, the seed continues to fill at the rim height to the edge of the seed image. Then on the anti-raster scan, the seed fills flat inside the sombrero to the upper and left, and then out from the rim as before. The final result has a seed that is flat outside the rim, and inside it fills the sombrero but only up to 150. If the rim height varies, the filled seed outside the rim will be at the highest point on the rim, which is a saddle point on the rim.

Definition at line 2123 of file seedfill.c.

References GET_DATA_BYTE, and SET_DATA_BYTE.

◆ seedspreadLow()

static void seedspreadLow ( l_uint32 *  datad,
l_int32  w,
l_int32  h,
l_int32  wpld,
l_uint32 *  datat,
l_int32  wplt,
l_int32  connectivity 
)
static

seedspreadLow()

See pixSeedspread() for a brief description of the algorithm here.

Definition at line 2846 of file seedfill.c.

References GET_DATA_BYTE, GET_DATA_TWO_BYTES, SET_DATA_BYTE, and SET_DATA_TWO_BYTES.