Definition

Introduction

A morphological structuring element (SE) is a binary shape used by morphological operators (such as erosion, dilation, ...) to specialize operator behavior.

See also: http://en.wikipedia.org/wiki/Structuring_element

2d structuring elements

In 2d case, a morphological structuring element (associated to class ipsdk::StructuringElementXYInfo) is represented by a collection of offsets (associated to class ipsdk::OffsetXY) defining its shape.

Rectangular structuring elements

Rectangular structuring elements are defined by their half size along X and Y axis ( $ halfSizeX $ and $ halfSizeY $ ) and aggregate all offsets such as :

$SE[halfSizeX, halfSizeY] = \left \{ (o_x, o_y) / \left | o_x \right | \leqslant halfSizeX \& \left | o_y \right | \leqslant halfSizeY \right \}$

Full size of structuring element is then defined by :

$\left \{ \begin{matrix} sizeX = 2 \times halfSizeX + 1 \\ sizeY = 2 \times halfSizeY + 1 \end{matrix} \right .$

The following C++ example illustrates the definition of a rectangular morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testRectangularSE()
{
    const ipUInt32 halfSizeX = 3;
    const ipUInt32 halfSizeY = 2;
    StructuringElementXYInfoConstPtr pSE = rectangularSEXYInfo(halfSizeX, halfSizeY);
}

The following C++ example illustrates the definition of a square morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testSquareSE()
{
    const ipUInt32 halfSize = 3;
    StructuringElementXYInfoConstPtr pSE = squareSEXYInfo(halfSize);
}

Circular structuring elements

Circular structuring elements are defined by their radius and aggregate all offsets enclosed in associated circle :

$SE[radius] = \left \{ (o_x, o_y) / o_x^2 + o_y^2 <= radius^2 \right \}$

The following C++ example illustrates the definition of a circular morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testCircularSE()
{
    const ipReal64 radius = 3.5;
    StructuringElementXYInfoConstPtr pSE = circularSEXYInfo(radius);
}

Half Linear structuring elements

Half linear structuring elements are defined by an orientation and a radius and aggregate offsets at the intersection of associated direction and circle :

$SE[\theta, radius] = \left \{ (o_x, o_y) / \exists \lambda \in \mathbb{N}^+ / o_x=\lambda \cos{\theta}, o_y=\lambda \sin{\theta} \& o_x^2 + o_y^2 <= radius^2 \right \}$

The following C++ example illustrates the definition of a half linear morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testHalfLinearSE()
{
    const ipReal64 theta = M_PI / 6;
    const ipReal64 radius = 6;
    StructuringElementXYInfoConstPtr pSE = halfLinearSEXYInfo(theta, radius);
}

Note: See Points and vectors 2d representation for more informations on 2d orientation conventions.

Linear structuring elements

Linear structuring elements are defined by an orientation and a radius and aggregate offsets at the intersection of associated direction and circle :

$SE[\theta, radius] = \left \{ (o_x, o_y) / \exists \lambda \in \mathbb{N} / o_x=\lambda \cos{\theta}, o_y=\lambda \sin{\theta} \& o_x^2 + o_y^2 <= radius^2 \right \}$

The following C++ example illustrates the definition of a linear morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testLinearSE()
{
    const ipReal64 theta = M_PI / 6;
    const ipReal64 radius = 6;
    StructuringElementXYInfoConstPtr pSE = linearSEXYInfo(theta, radius);
}

Note: See Points and vectors 2d representation for more informations on 2d orientation conventions.

3d structuring elements

In 3d case, a morphological structuring element (associated to class ipsdk::StructuringElementXYZInfo) is represented by a collection of offsets (associated to class ipsdk::OffsetXYZ) defining its shape.

Rectangular structuring elements

Rectangular structuring elements are defined by their half size along X, Y and Z axis ( $ halfSizeX $ , $ halfSizeY $ and $ halfSizeZ $ ) and aggregate all offsets such as :

$SE[halfSizeX, halfSizeY, halfSizeZ] = \left \{ (o_x, o_y, o_z) / \left | o_x \right | \leqslant halfSizeX \& \left | o_y \right | \leqslant halfSizeY \& \left | o_z \right | \leqslant halfSizeZ \right \}$

Full size of structuring element is then defined by :

$\left \{ \begin{matrix} sizeX = 2 \times halfSizeX + 1 \\ sizeY = 2 \times halfSizeY + 1 \\ sizeZ = 2 \times halfSizeZ + 1 \end{matrix} \right .$

The following C++ example illustrates the definition of a rectangular morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testRectangularSE()
{
    const ipUInt32 halfSizeX = 4;
    const ipUInt32 halfSizeY = 1;
    const ipUInt32 halfSizeZ = 2;
    StructuringElementXYZInfoConstPtr pSE = rectangularSEXYZInfo(halfSizeX, halfSizeY, halfSizeZ);
}

The following C++ example illustrates the definition of a cubic morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testCubicSE()
{
    const ipUInt32 halfSize = 3;
    StructuringElementXYZInfoConstPtr pSE = cubicSEXYZInfo(halfSize);
}

Spherical structuring elements

Spherical structuring elements are defined by their radius and aggregate all offsets enclosed in associated sphere :

$SE[radius] = \left \{ (o_x, o_y, o_z) / o_x^2 + o_y^2 + o_z^2 <= radius^2 \right \}$

The following C++ example illustrates the definition of a spherical morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testSphericalSE()
{
    const ipReal64 radius = 4;
    StructuringElementXYZInfoConstPtr pSE = sphericalSEXYZInfo(radius);
}

Half Linear structuring elements

Half linear structuring elements are defined by an orientation and a radius and aggregate offsets at the intersection of associated direction and sphere :

$SE[\theta, \phi, radius] = \left \{ (o_x, o_y) / \exists \lambda \in \mathbb{N}^+ / o_x=\lambda \sin{\theta} \cos{\phi}, o_y=\lambda \sin{\theta} \sin{\phi}, o_z=\lambda \cos{\theta} \& o_x^2 + o_y^2 + o_z^2 <= radius^2 \right \}$

The following C++ example illustrates the definition of a half linear morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testHalfLinearSE()
{
    const ipReal64 theta = M_PI / 6;
    const ipReal64 phi = M_PI / 4;
    const ipReal64 radius = 6;
    StructuringElementXYZInfoConstPtr pSE = halfLinearSEXYZInfo(theta, phi, radius);
}

Note: See Points and vectors 3d representation for more informations on 3d orientation conventions.

Linear structuring elements

Linear structuring elements are defined by an orientation and a radius and aggregate offsets at the intersection of associated direction and sphere :

$SE[\theta, \phi, radius] = \left \{ (o_x, o_y) / \exists \lambda \in \mathbb{N} / o_x=\lambda \sin{\theta} \cos{\phi}, o_y=\lambda \sin{\theta} \sin{\phi}, o_z=\lambda \cos{\theta} \& o_x^2 + o_y^2 + o_z^2 <= radius^2 \right \}$

The following C++ example illustrates the definition of a linear morphological structuring element :

#include <IPSDKBaseData/Pattern/StructuringElement/StructuringElementInfoUtils.h>
using namespace ipsdk;
void testLinearSE()
{
    const ipReal64 theta = M_PI / 6;
    const ipReal64 phi = M_PI / 4;
    const ipReal64 radius = 6;
    StructuringElementXYZInfoConstPtr pSE = linearSEXYZInfo(theta, phi, radius);
}

Note: See Points and vectors 3d representation for more informations on 3d orientation conventions.

Usage

Introduction

Erosion and dilation are the two fundamental morphological operations.

These operations use a flat (with values in [0, 1]) structuring element combined to a Minkowski sum (in case of dilation) or subtraction (in case of erosion). Formula associated to each of these operations are given by :

For dilation :
$A \oplus B = \left \{ x / B_x \cap A \neq \varnothing \right \}$

See also
See http://en.wikipedia.org/wiki/Dilation_%28morphology%29 for more informations.
For erosion :
$A \ominus B = \left \{ x / B_x \subseteq A \right \}$

See also
See http://en.wikipedia.org/wiki/Erosion_%28morphology%29 for more informations.
Several algorithm are decline above these two fundamental operations :
closing operation :
$A \odot B = (A \oplus B) \ominus B$

See also
See http://en.wikipedia.org/wiki/Closing_%28morphology%29 for more informations.
opening operation :
$A \circledcirc B = (A \ominus B) \oplus B$

See also
See http://en.wikipedia.org/wiki/Opening_%28morphology%29 for more informations.
morphological gradient computation :
$G(A)_B = A \oplus B - A \ominus B$

See also
See http://en.wikipedia.org/wiki/Morphological_gradient for more informations.
Dark (black) top hat transform :
$T^D(A)_B = A \odot B - A$
This transformation is generally associated to a thresholding operation to obtain a binary image.
See also
See http://en.wikipedia.org/wiki/Top-hat_transform for more informations.
Light (white) top hat transform :
$T^L(A)_B = A - A \circledcirc B$
This transformation is generally associated to a thresholding operation to obtain a binary image.
See also
See http://en.wikipedia.org/wiki/Top-hat_transform for more informations.

Structuring elements typology

Structuring elements specific typology (shape) are detailed into :

2d structuring elements for 2d structuring elements
3d structuring elements for 3d structuring elements

These different typologies include rectangle, circle, sphere, lines, ...

Each of this shape can be used to respond to a specific need. We will try to illustrate this concept in the following section.

Detailed samples :

The following examples illustrates usage of different structuring element types for dilation 2d algorithm. A dilation 2d operation has been chosen for this use case but all these considerations could be extended to 3d case as well as other morphological operators.

operation applied with a binary input image with a rectangular structuring element with following parameters and :

In this case we can see that a input rectangular shapes (without respect to their aspect ratio) are preserved whereas curved one are not.
operation applied with a binary input image with a square structuring element with half kernel size set to 7 :

In this case we can see that a input rectangular shapes are preserved whereas curved one are not.
operation applied with a binary input image with a circular structuring element with radius 7 :

In this case we can see that a input rectangular shapes corners are rounded whereas circular ones are preserved.
operation applied with a binary input image with a half linear structuring element with following parameters $\theta = \frac{\pi}{3}$ and :

This kind of structuring element can be used to extract oriented directional shapes. We can see that in this case, shapes are half dilated with respect to the provided direction.
operation applied with a binary input image with a linear structuring element with following parameters $\theta = \frac{\pi}{3}$ and :

This kind of structuring element can be used to extract oriented directional shapes. We can see that in this case, shapes are dilated with respect to the provided direction.

Specific case of circular and spherical shapes

Circular 2d and spherical 3d structuring elements morphological operations can be optimised using a multi-level decomposition algorithm described in :
Multi-level decomposition of Euclidean spheres, Michael S. Vaz, Atilla P. Kiraly and Russell M. Mersereau, Proceedings of the 8 th International Symposium on Mathematical Morphology, Rio de Janeiro, Brazil, Oct. 10–13, 2007, MCT/INPE, v. 1, p. 461–472

This method allows to decompose convex and symmetric (with respect to x, y and z axis) structuring elements into a combination of elementary structuring elements.

The following graph shows processing time comportment of a standard implementation of a morphological operation using a circular 2d structuring element versus its multi-level decomposition form :

The following graph shows processing time comportment of a standard implementation of a morphological operation using a spherical 3d structuring element versus its multi-level decomposition form :

Morphological 2d and 3d operations are optimized to swap between a standard and a multi-level decomposition implementation in function of these graphs.

Note: In special case of binary input images, an additional optimization is applied (based on a distance map algorithm) which ensure constant processing times for high structuring element radiuss.