Hit Or Miss And Skeleton
Algorithms computing morphological skeleton and applying post-processing on it.
- Skeleton: Computes the morphological skeleton of objects contained in a binary image.
- Centerline3d: Extracts the centerline of a binary three-dimensional image.
- InfluenceZones: Computes the Skeleton by Influence Zone (SKIZ).
- Centroid2d: Computes the centroid of objects in two-dimensional binary image.
- EndPoints2d: Point detector selecting end points of a two-dimensional binary image.
- EndPoints3d: Point detector selecting end points of a three-dimensional binary image.
- Pruning2d: Point detector removing spurs from a two-dimensional binary image.
- Pruning3d: Point detector removing spurs from a three-dimensional binary image.
- IsolatedPoints2d: Point detector selecting object made up of a single point in a two-dimensional binary image.
- IsolatedPoints3d: Point detector selecting object made up of a single point in a three-dimensional binary image.
- TriplePoints2d: Point detector selecting triple points of a skeleton in a two-dimensional binary image.
- InteriorPoints2d: Point detector retaining interior points of object in a two-dimensional binary image.
- ApplyMorphologicalLut2d: Applies a predefined morphological lookup table (LUT) on a two-dimensional binary image.
- ApplyMorphologicalLut3d: Applies a predefined morphological lookup table (LUT) on a three-dimensional binary image.
The Hit-or-miss and Skeleton category contains algorithms used to produce simplified representations of image
objects, while preserving their geometrical structure. The representations then can be used to calculate length,
direction, etc., or to detect special topological structures such as end or triple points (number of crossings).
For example: $$ \begin{array}{ccc} 2 & 0 & 1\\ 2 & 1 & 0\\ 2 & 2 & 2 \end{array} ~~~\mbox{matches with}~~~ \begin{array}{ccc} 1 & 0 & 1\\ 1 & 1 & 0\\ 0 & 0 & 0 \end{array} ~~~\mbox{and}~~~ \begin{array}{ccc} 1 & 0 & 1\\ 1 & 1 & 0\\ 1 & 1 & 0 \end{array} ~~~\mbox{but not}~~~ \begin{array}{ccc} 0 & 1 & 1\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{array} $$
A LUT to convert a binary image from an 8 neighbors connectivity to 4 neighbors connectivity can be defined, testing whether a given pixel has a neighbour in the north-east, north-west, south-west and south-east directions.
$$ \mbox{north-west:}~~~ \begin{array}{ccc} 1 & 0 & 2\\ 0 & 1 & 2\\ 2 & 2 & 2 \end{array} ~~~~~~~~~~~~\mbox{north-east:}~~~ \begin{array}{ccc} 2 & 0 & 1\\ 2 & 1 & 0\\ 2 & 2 & 2 \end{array} $$ $$ \mbox{south-west:}~~~ \begin{array}{ccc} 2 & 2 & 2\\ 0 & 1 & 2\\ 1 & 0 & 2 \end{array} ~~~~~~~~~~~~\mbox{south-east:}~~~ \begin{array}{ccc} 2 & 2 & 2\\ 2 & 1 & 0\\ 2 & 0 & 1 \end{array} $$
These kernels have to be added one by one to build the LUT by using the addKernel method. The kernelRotation parameter indicates whether the kernel must be rotated before being inserted. A value of zero inserts the kernel as is; a value of 2 transforms the north-west configuration above into the south-west configuration.
The LUT can be reinitialized with the reset, which removes all existing kernels from the LUT.
Applying a morphological LUT on a binary image can be performed with the ApplyMorphologicalLut2d and ApplyMorphologicalLut3d algorithms.
Skeletonization is a transformation based on the thinning of connected components until a line is achieved. A skeleton is obtained by successive thinnings until convergence, using the L configuration and rotating it. The structuring element associated with the L configuration is: $$ \begin{array}{ccc} 1 & 1 & 1\\ \times & \bullet & \times\\ 0 & 0 & 0 \end{array} $$ where $\times$ means "don't care".
The following algorithms are some point detectors:
Morphological LUT
Using a morphological LUT (Look Up Table) consists of moving some predefined configurations of neighborhood in a binary image and applying a decision when this configuration matches or not.Creating a morphological LUT
First a kernel has to be defined to test whether a given pixel matches a criterion or not. The kernel is made of classical binary pixel values : 0, 1 and a specific one, 2, which means 'do not care'.For example: $$ \begin{array}{ccc} 2 & 0 & 1\\ 2 & 1 & 0\\ 2 & 2 & 2 \end{array} ~~~\mbox{matches with}~~~ \begin{array}{ccc} 1 & 0 & 1\\ 1 & 1 & 0\\ 0 & 0 & 0 \end{array} ~~~\mbox{and}~~~ \begin{array}{ccc} 1 & 0 & 1\\ 1 & 1 & 0\\ 1 & 1 & 0 \end{array} ~~~\mbox{but not}~~~ \begin{array}{ccc} 0 & 1 & 1\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{array} $$
A LUT to convert a binary image from an 8 neighbors connectivity to 4 neighbors connectivity can be defined, testing whether a given pixel has a neighbour in the north-east, north-west, south-west and south-east directions.
$$ \mbox{north-west:}~~~ \begin{array}{ccc} 1 & 0 & 2\\ 0 & 1 & 2\\ 2 & 2 & 2 \end{array} ~~~~~~~~~~~~\mbox{north-east:}~~~ \begin{array}{ccc} 2 & 0 & 1\\ 2 & 1 & 0\\ 2 & 2 & 2 \end{array} $$ $$ \mbox{south-west:}~~~ \begin{array}{ccc} 2 & 2 & 2\\ 0 & 1 & 2\\ 1 & 0 & 2 \end{array} ~~~~~~~~~~~~\mbox{south-east:}~~~ \begin{array}{ccc} 2 & 2 & 2\\ 2 & 1 & 0\\ 2 & 0 & 1 \end{array} $$
These kernels have to be added one by one to build the LUT by using the addKernel method. The kernelRotation parameter indicates whether the kernel must be rotated before being inserted. A value of zero inserts the kernel as is; a value of 2 transforms the north-west configuration above into the south-west configuration.
The LUT can be reinitialized with the reset, which removes all existing kernels from the LUT.
- In the 2D case, 2 power 9 configurations of neighborhood are possible. The addKernel method function fills an array of 512 elements to build the LUT.
- In the 3D case, 2 power 27 configurations of neighborhood are theorically possible. A 5 bit reduction is applied. The addKernel method function fills an array of 4194304 elements to build the LUT.
Applying a morphological LUT
Once a LUT is created, it has to be specified what has to be done with the pixels that match the LUT and those that do not. Two flag fields are available to specify the different actions: matchingFlag if the pixel matches and unmatchingFlag if it does not. There are 4 possible values:- SET_ZERO: forces the output value to zero.
- SET_ONE: forces the output value to one.
- CHANGE: inverts the output value.
- PRESERVE: lets the output value unchanged.
Applying a morphological LUT on a binary image can be performed with the ApplyMorphologicalLut2d and ApplyMorphologicalLut3d algorithms.
Thinning, thickening, and hit-or-miss operation with Morphological LUT
Morphological LUT's can be used to perform classical neighborhood operations such as thinning, thickening, and hit-or-miss: $$ \begin{array}{|c|c|c|} \hline \textbf{matchingFlag} & \textbf{unmatchingFlag} & \textbf{Operation}\\ \hline \mbox{SET_ZERO} & \mbox{PRESERVE} & \mbox{Thinning}\\ \hline \mbox{SET_ONE} & \mbox{PRESERVE} & \mbox{Thickening}\\ \hline \mbox{SET_ONE} & \mbox{SET_ZERO} & \mbox{Hit-or-miss}\\ \hline \end{array} $$Skeletonization
Skeletonization is used to produce a simplified representation of the objects in an image, while preserving their geometrical structure. The representation then can be used to calculate length, direction, etc., or to detect special topological structures such as end or triple points (number of crossings).Skeletonization is a transformation based on the thinning of connected components until a line is achieved. A skeleton is obtained by successive thinnings until convergence, using the L configuration and rotating it. The structuring element associated with the L configuration is: $$ \begin{array}{ccc} 1 & 1 & 1\\ \times & \bullet & \times\\ 0 & 0 & 0 \end{array} $$ where $\times$ means "don't care".
Point detectors
Once a skeleton is computed it may be useful to detect specific configurations of points. The point detectors use hit-or-miss transforms (HMT) to select target points.The following algorithms are some point detectors: