Morphological filtering module
#include "diplib/morphology.h"

dip::StructuringElement class

Represents the shape and size of a structuring element.

Many functions in the Mathematical Morphology module require a structuring element definition. There are two ways to define a structuring element: the user can specify the shape name and the size of a structuring element, and the user can pass an image containing the structuring element.

Objects of type dip::Image, dip::FloatArray and dip::String implicitly convert to a dip::StructuringElement, so it should be convenient to use these various representations in your code.

To define a structuring element by shape and size, pass a string defining the shape, and a floating-point array with the size along each dimension. These are the valid shape strings, and the corresponding meaning of the size array:

• "elliptic": the isotropic flat structuring element, and the default shape. The size array gives the diameter along each dimension. It is always symmetric. That is, the origin is centered on a pixel. The pixels included in the disk or ellipse are those less than half of the diameter away from the origin. It is implemented through a relatively efficient algorithm that scales with the diameter, not the number of pixels covered. Rectangular, elliptic and octagonal structuring elements are much faster, especially for larger sizes. Any size array element that is smaller than 2 causes that dimension to not be processed.

• "rectangular": the unit circle in a chessboard metric. The size array gives the diameter (or rather the side lengths). The rectangle can have even sizes, in which case it is not symmetric around the origin pixel. This structuring element is implemented with a one-dimensional pass along each image dimension. This decomposition makes this a highly efficient structuring element, with computation times that are independent of the size. Any size array element that is smaller or equal to 1 causes that dimension to not be processed.

• "diamond": the unit circles in a city-block metric. The size array gives the diameter (the extent along each image axis). Like the ellipse, it is always symmetric. That is, the origin is centered on a pixel. If all sizes are equal, then this structuring element is decomposed into a unit diamond and 2 diagonal lines, for a 2D diamond. In this case, computation times that are independent of the size, like for the rectangle. However, for smaller diamonds, the decomposition is different: a unit diamond is applied repeatedly; this yielding faster computation times. If any size is different from the others, or if the diamond has more than two dimensions, then the same algorithm as for the elliptic structuring element is used. Any size array element that is smaller than 2 causes that dimension to not be processed.

• "octagonal": a fast approximation to the ellipse. Octagons (in 2D) are decomposed into a rectangle and a diamond, each one implemented as described above. This makes the octagonal structuring element more expensive than either the diamond or rectangle, but still computable in constant time independent of the diameter. We generalize this structuring element to arbitrary number of dimensions simply by applying those two smaller structuring elements in succession. In 3D this leads to a rhombicuboctahedron. Any size array element that is smaller than 2 causes that dimension to not be processed.

• "parabolic": the parabolic structuring element is the morphological equivalent to the Gaussian kernel in linear filtering. It is separable and perfectly isotropic. The size array corresponds to the scaling of the parabola (i.e. the in ). A value equal or smaller to 0 causes that dimension to not be processed. The boundary condition is ignored for operators with this structuring element, and the output image is always a floating-point type.

• "line", "fast line", "periodic line", "discrete line", "interpolated line": these are straight lines, using different implementations. The size array corresponds to the size of the bounding box of the line, with signs indicating the direction. Thus, if the size array is {2,2}, the line goes right and down two pixels, meaning that the line is formed by two pixels at an angle of 45 degrees down. If the size array is {-2,2}, then the line is again two pixels, but at an angle of 135 degrees. (Note that in images, angles increase clockwise from the x-axis, as the y-axis is inverted). For a description of the meaning of these various line implementations, see Line morphology.

To define a structuring element through an image, provide either a binary or grey-value image. If the image is binary, the set pixels form the structuring element. If the image is a grey-value image, those grey values are directly used as structuring element values. Set pixels to negative infinity to exclude them from the structuring element (the result would be the same by setting them to a value lower than the range of the input image, but the algorithm should be more efficient if those pixels are excluded).

Note that the image is directly used as neighborhood (i.e. no mirroring is applied). That is, dip::Dilation and dip::Erosion will use the same neighborhood. Their composition only leads to an opening or a closing if the structuring element is symmetric. For non-symmetric structuring element images, you need to mirror it in one of the two function calls:

dip::Image se = ...;
dip::Image out = dip::Erosion( in, se );
out = dip::Dilation( out, se.Mirror() );

(Do note that, in the code above, se itself is modified! use se.QuickCopy().Mirror() to prevent that.)

As elsewhere, the origin of the structuring element is in the middle of the image, on the pixel to the right of the center in case of an even-sized image.

Line morphology

There are various different ways of applying dilations, erosions, openings and closings with line structuring elements. The dip::StructuringElement class accepts five different strings each providing a different definition of the line structuring element. Further, there is also the dip::PathOpening function, which provides path openings and closings. Here we describe the five different line structuring elements implemented in DIPlib.

• "line": This is an efficient implementation that yields the same results as the traditional line structuring element ("discrete line"). It is implemented as a combination of "periodic line" and "discrete line", and is called recursive line in the literature (see Soille, 1996). If the line parameters are such that the periodic line has a short period, this implementation saves a lot of time. In this case, for a given line angle, the cost of the operation is independent of the length of the line. If the line parameters are such that the periodic line has only one point, this is identical to "discrete line".

• "fast line": This is a faster algorithm that applies a 1D operation along Bresenham lines, yielding a non-translation-invariant result. The cost of this operation is always independent of the length of the line.

• "periodic line": This is a line formed of only a subset of the pixels along the Bresenham line, such that it can be computed as a 1D operation along Bresenham lines, but still yields a translation-invariant result (Soille, 1996). It might not be very useful on its own, but when combined with the "discrete line", it provides a more efficient implementation of the traditional line structuring element (see "line" above).

• "discrete line": This is the traditional line structuring element, drawn using the Bresenham algorithm and applied brute-force.

• "interpolated line": This operation skews the image, using interpolation, such that the line operation can be applied along an image axis; the result of the operation is then skewed back. The result is an operation with a line that uses interpolation to read image intensities in between pixels. This greatly improves the results in e.g. a granulometry when the input image is band limited (Luengo Hendriks, 2005). However, the result of morphological operations is not band limited, and so the second, reverse skew operation will lose some precision. Note that the result of morphological operations with this SE do not strictly satisfy the corresponding properties (only by approximation) because of the interpolated values. Setting the boundary condition to "periodic" allows the operation to occur completely in place; other boundary conditions lead to a larger intermediate image, and thus will always require additional, temporary storage.

For all these lines, if they are an even number of pixels in length, then the origin is placed at the result of the integer division length/2. That is, on the pixel that comes just after the true middle of the line. This means that the line {8,3} will have the origin on pixel number 4 (when starting counting at 0), as will the line {-8,-3}. The difference between these two is that the latter starts on the bottom right and goes left and up, whereas the former starts on the top left and goes right and down. Note that the drawn Bresenham line might have a slightly different configuration also.

The SE "line" is different from the others in that these two lines will be normalized to the exact same line: If the first size component is negative, all size components will be negated, turning {-8,-3} into {8,3}. This makes it easier to decompose the SE into the two components. Do note that, because of this normalization, there could be a 1 pixel shift for even-sized lines as compared to "discrete line" or "fast line".

A few quick experiments have shown that, depending on the angle and the direction of the line w.r.t. the image storage order, "discrete line" can be much faster than "line" (or "fast line") for shorter lines (times were equal with around 50px length), or they can be much slower for even the shortest of lines. Predicting which implementation of the line will be faster for a given situation is not trivial.