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

Go to the source code of this file.

Functions

static PIXpixErodeGray3h (PIX *pixs)
 
static PIXpixErodeGray3v (PIX *pixs)
 
static PIXpixDilateGray3h (PIX *pixs)
 
static PIXpixDilateGray3v (PIX *pixs)
 
static void dilateGrayLow (l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld, l_uint32 *datas, l_int32 wpls, l_int32 size, l_int32 direction, l_uint8 *buffer, l_uint8 *maxarray)
 
static void erodeGrayLow (l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld, l_uint32 *datas, l_int32 wpls, l_int32 size, l_int32 direction, l_uint8 *buffer, l_uint8 *minarray)
 
PIXpixErodeGray (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixDilateGray (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixOpenGray (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixCloseGray (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixErodeGray3 (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixDilateGray3 (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixOpenGray3 (PIX *pixs, l_int32 hsize, l_int32 vsize)
 
PIXpixCloseGray3 (PIX *pixs, l_int32 hsize, l_int32 vsize)
 

Detailed Description

 Top-level grayscale morphological operations (van Herk / Gil-Werman)
       PIX           *pixErodeGray()
       PIX           *pixDilateGray()
       PIX           *pixOpenGray()
       PIX           *pixCloseGray()

 Special operations for 1x3, 3x1 and 3x3 Sels  (direct)
       PIX           *pixErodeGray3()
       static PIX    *pixErodeGray3h()
       static PIX    *pixErodeGray3v()
       PIX           *pixDilateGray3()
       static PIX    *pixDilateGray3h()
       static PIX    *pixDilateGray3v()
       PIX           *pixOpenGray3()
       PIX           *pixCloseGray3()

 Low-level grayscale morphological operations
       static void    dilateGrayLow()
       static void    erodeGrayLow()


 Method: Algorithm by van Herk and Gil and Werman, 1992

 Measured speed of the vH/G-W implementation is about 1 output
 pixel per 120 PIII clock cycles, for a horizontal or vertical
 erosion or dilation.  The computation time doubles for opening
 or closing, or for a square SE, as expected, and is independent
 of the size of the SE.

 A faster implementation can be made directly for brick Sels
 of maximum size 3.  We unroll the computation for sets of 8 bytes.
 It needs to be called explicitly; the general functions do not
 default for the size 3 brick Sels.

 We use the van Herk/Gil-Werman (vHGW) algorithm, [van Herk,
 Patt. Recog. Let. 13, pp. 517-521, 1992; Gil and Werman,
 IEEE Trans PAMI 15(5), pp. 504-507, 1993.]
 This was the first grayscale morphology
 algorithm to compute dilation and erosion with
 complexity independent of the size of the structuring
 element.  It is simple and elegant, and surprising that
 it was discovered as recently as 1992.  It works for
 SEs composed of horizontal and/or vertical lines.  The
 general case requires finding the Min or Max over an
 arbitrary set of pixels, and this requires a number of
 pixel comparisons equal to the SE "size" at each pixel
 in the image.  The vHGW algorithm requires not
 more than 3 comparisons at each point.  The algorithm has been
 recently refined by Gil and Kimmel ("Efficient Dilation
 Erosion, Opening and Closing Algorithms", in "Mathematical
 Morphology and its Applications to Image and Signal Processing",
 the proceedings of the International Symposium on Mathematical
 Morphology, Palo Alto, CA, June 2000, Kluwer Academic
 Publishers, pp. 301-310).  They bring this number down below
 1.5 comparisons per output pixel but at a cost of significantly
 increased complexity, so I don't bother with that here.

 In brief, the method is as follows.  We evaluate the dilation
 in groups of "size" pixels, equal to the size of the SE.
 For horizontal, we start at x = "size"/2 and go
 (w - 2 * ("size"/2))/"size" steps.  This means that
 we don't evaluate the first 0.5 * "size" pixels and, worst
 case, the last 1.5 * "size" pixels.  Thus we embed the
 image in a larger image with these augmented dimensions, where
 the new border pixels are appropriately initialized (0 for
 dilation; 255 for erosion), and remove the boundary at the end.
 (For vertical, use h instead of w.)   Then for each group
 of "size" pixels, we form an array of length 2 * "size" + 1,
 consisting of backward and forward partial maxima (for
 dilation) or minima (for erosion).  This represents a
 jumping window computed from the source image, over which
 the SE will slide.  The center of the array gets the source
 pixel at the center of the SE.  Call this the center pixel
 of the window.  Array values to left of center get
 the maxima(minima) of the pixels from the center
 one and going to the left an equal distance.  Array
 values to the right of center get the maxima(minima) to
 the pixels from the center one and going to the right
 an equal distance.  These are computed sequentially starting
 from the center one.  The SE (of length "size") can slide over this
 window (of length 2 * "size + 1) at "size" different places.
 At each place, the maxima(minima) of the values in the window
 that correspond to the end points of the SE give the extremal
 values over that interval, and these are stored at the dest
 pixel corresponding to the SE center.  A picture is worth
 at least this many words, so if this isn't clear, see the
 leptonica documentation on grayscale morphology.

Definition in file graymorph.c.

Function Documentation

◆ dilateGrayLow()

static void dilateGrayLow ( l_uint32 *  datad,
l_int32  w,
l_int32  h,
l_int32  wpld,
l_uint32 *  datas,
l_int32  wpls,
l_int32  size,
l_int32  direction,
l_uint8 *  buffer,
l_uint8 *  maxarray 
)
static

dilateGrayLow()

Parameters
[in]datad8 bpp dsst image
[in]w,hdimensions of src and dest
[in]wpldwords/line of dest
[in]datas8 bpp src image
[in]wplswords/line of src
[in]sizefull length of SEL; restricted to odd numbers
[in]directionL_HORIZ or L_VERT
[in]bufferholds full line or column of src image pixels
[in]maxarrayarray of dimension 2*size+1
Returns
void
Notes:
       (1) To eliminate border effects on the actual image, these images
           are prepared with an additional border of dimensions:
              leftpix = 0.5 * size
              rightpix = 1.5 * size
              toppix = 0.5 * size
              bottompix = 1.5 * size
           and we initialize the src border pixels to 0.
           This allows full processing over the actual image; at
           the end the border is removed.
       (2) Uses algorithm of van Herk, Gil and Werman

Definition at line 1161 of file graymorph.c.

◆ erodeGrayLow()

static void erodeGrayLow ( l_uint32 *  datad,
l_int32  w,
l_int32  h,
l_int32  wpld,
l_uint32 *  datas,
l_int32  wpls,
l_int32  size,
l_int32  direction,
l_uint8 *  buffer,
l_uint8 *  minarray 
)
static

erodeGrayLow()

Parameters
[in]datad8 bpp dsst image
[in]w,hdimensions of src and dest
[in]wpldwords/line of dest
[in]datas8 bpp src image
[in]wplswords/line of src
[in]sizefull length of SEL; restricted to odd numbers
[in]directionL_HORIZ or L_VERT
[in]bufferholds full line or column of src image pixels
[in]minarrayarray of dimension 2*size+1
Returns
void
Notes:
       (1) See notes in dilateGrayLow()

Definition at line 1268 of file graymorph.c.

◆ pixCloseGray()

PIX* pixCloseGray ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixCloseGray()

Parameters
[in]pixs
[in]hsizeof Sel; must be odd; origin implicitly in center
[in]vsizeditto
Returns
pixd
Notes:
     (1) Sel is a brick with all elements being hits
     (2) If hsize = vsize = 1, just returns a copy.

Definition at line 520 of file graymorph.c.

◆ pixCloseGray3()

PIX* pixCloseGray3 ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixCloseGray3()

Parameters
[in]pixs8 bpp, not cmapped
[in]hsize1 or 3
[in]vsize1 or 3
Returns
pixd, or NULL on error
Notes:
     (1) Special case for 1x3, 3x1 or 3x3 brick sel (all hits)
     (2) If hsize = vsize = 1, just returns a copy.

Definition at line 1080 of file graymorph.c.

◆ pixDilateGray()

PIX* pixDilateGray ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixDilateGray()

Parameters
[in]pixs
[in]hsizeof Sel; must be odd; origin implicitly in center
[in]vsizeditto
Returns
pixd
Notes:
     (1) Sel is a brick with all elements being hits
     (2) If hsize = vsize = 1, just returns a copy.

Definition at line 276 of file graymorph.c.

◆ pixDilateGray3()

PIX* pixDilateGray3 ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixDilateGray3()

Parameters
[in]pixs8 bpp, not cmapped
[in]hsize1 or 3
[in]vsize1 or 3
Returns
pixd, or NULL on error
Notes:
     (1) Special case for 1x3, 3x1 or 3x3 brick sel (all hits)
     (2) If hsize = vsize = 1, just returns a copy.

Definition at line 837 of file graymorph.c.

◆ pixDilateGray3h()

static PIX * pixDilateGray3h ( PIX pixs)
static

pixDilateGray3h()

Parameters
[in]pixs8 bpp, not cmapped
Returns
pixd, or NULL on error
Notes:
     (1) Special case for horizontal 3x1 brick Sel;
         also used as the first step for the 3x3 brick Sel.

Definition at line 888 of file graymorph.c.

◆ pixDilateGray3v()

static PIX * pixDilateGray3v ( PIX pixs)
static

pixDilateGray3v()

Parameters
[in]pixs8 bpp, not cmapped
Returns
pixd, or NULL on error
Notes:
     (1) Special case for vertical 1x3 brick Sel;
         also used as the second step for the 3x3 brick Sel.

Definition at line 950 of file graymorph.c.

◆ pixErodeGray()

PIX* pixErodeGray ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixErodeGray()

Parameters
[in]pixs
[in]hsizeof Sel; must be odd; origin implicitly in center
[in]vsizeditto
Returns
pixd
Notes:
     (1) Sel is a brick with all elements being hits
     (2) If hsize = vsize = 1, just returns a copy.

Definition at line 162 of file graymorph.c.

◆ pixErodeGray3()

PIX* pixErodeGray3 ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixErodeGray3()

Parameters
[in]pixs8 bpp, not cmapped
[in]hsize1 or 3
[in]vsize1 or 3
Returns
pixd, or NULL on error
Notes:
     (1) Special case for 1x3, 3x1 or 3x3 brick sel (all hits)
     (2) If hsize = vsize = 1, just returns a copy.
     (3) It would be nice not to add a border, but it is required
         if we want the same results as from the general case.
         We add 4 bytes on the left to speed up the copying, and
         8 bytes at the right and bottom to allow unrolling of
         the computation of 8 pixels.

Definition at line 657 of file graymorph.c.

◆ pixErodeGray3h()

static PIX * pixErodeGray3h ( PIX pixs)
static

pixErodeGray3h()

Parameters
[in]pixs8 bpp, not cmapped
Returns
pixd, or NULL on error
Notes:
     (1) Special case for horizontal 3x1 brick Sel;
         also used as the first step for the 3x3 brick Sel.

Definition at line 708 of file graymorph.c.

◆ pixErodeGray3v()

static PIX * pixErodeGray3v ( PIX pixs)
static

pixErodeGray3v()

Parameters
[in]pixs8 bpp, not cmapped
Returns
pixd, or NULL on error
Notes:
     (1) Special case for vertical 1x3 brick Sel;
         also used as the second step for the 3x3 brick Sel.
     (2) Surprisingly, this is faster than setting up the
         lineptrs array and accessing into it; e.g.,
             val4 = GET_DATA_BYTE(lines8[i + 3], j);

Definition at line 773 of file graymorph.c.

◆ pixOpenGray()

PIX* pixOpenGray ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixOpenGray()

Parameters
[in]pixs
[in]hsizeof Sel; must be odd; origin implicitly in center
[in]vsizeditto
Returns
pixd
Notes:
     (1) Sel is a brick with all elements being hits
     (2) If hsize = vsize = 1, just returns a copy.

Definition at line 390 of file graymorph.c.

◆ pixOpenGray3()

PIX* pixOpenGray3 ( PIX pixs,
l_int32  hsize,
l_int32  vsize 
)

pixOpenGray3()

Parameters
[in]pixs8 bpp, not cmapped
[in]hsize1 or 3
[in]vsize1 or 3
Returns
pixd, or NULL on error
Notes:
     (1) Special case for 1x3, 3x1 or 3x3 brick sel (all hits)
     (2) If hsize = vsize = 1, just returns a copy.
     (3) It would be nice not to add a border, but it is required
         to get the same results as for the general case.

Definition at line 1016 of file graymorph.c.