Hit-Or-Miss And Skeleton
[Mathematical Morphology]
The Hit-or-miss and Skeleton category contains engines used to produce simplified representations of the objects in an image, while preserving their geometrical structure. More...
Detailed Description
The Hit-or-miss and Skeleton category contains engines used to produce simplified representations of the objects in an image, while preserving their geometrical structure.
The representations may then be used to calculate length, direction, etc. or to detect special topological structures such as end or triple points (number of crossings).
Morphological LUT
- A morphological LUT (Look Up Table) allows to move in a binary image some predefined configurations of neighborhood and apply a criteria when this configuration matches or not.
Creating a morphological LUT First a kernel has to be defined to test if a given pixel matches a criteria or not. The kernel is made of classical binary pixel values : 0, 1 and a specific one: 2 which means 'don't care'.
For example:
![\[ \begin{array}{ccc} 2 & 0 & 1\\ 2 & 1 & 0\\ 2 & 2 & 2 \end{array} ~~~\mbox{will match 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} \]](form_584.png)
A LUT to convert a binary image from an 8 neighbors connexity to 4 neighbors connexity can be defined testing if a given pixel has a neighbour in the north east, north west, south west and south east directions.
![\[ ~~~\mbox{north east}~~~ \begin{array}{ccc} 2 & 0 & 1\\ 2 & 1 & 0\\ 2 & 2 & 2 \end{array} ~~~\mbox{north west}~~~ \begin{array}{ccc} 1 & 0 & 2\\ 0 & 1 & 2\\ 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} \]](form_585.png)
These kernels have to be added one by one to build the LUT, using the addKernel method. The first kernel has to be inserted with the mode NEW, that indicates the LUT has to be reset before to add this kernel inside. Other kernels have to be ineserted with the mode OR to indicate to look for this kernels or one of the previous.
- 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 bits reduction is applied. The addKernel method function fills an array of 4194304 elements to build the LUT.
Applying a morphological LUT Once the 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: flagTrue if the pixel matches and flagFalse if it does not. There are 4 possible values :
- OUTPUT_ZERO : Force the output value to zero
- OUPUT_ONE : Force the output value to one
- OUTPUT_CHANGE : invert the output value
- OUPUT_UNCHANGE : let the output value unchanged.
For example : to change the connexity from 8 neighbors connexity to 4 , if the pixel matches the criteria the output value has to be forced to 0 and if it does not it has to be let unchanged. Therefore flagTrue = OUTPUT_ZERO and flagFalse = OUPUT_UNCHANGE.
Thinning, thickening and hit-or-miss operation with Morphological LUT As a consequence morphological LUT's can be used to perform classical neighborhood operations such as thinning, thickening and hit-or-miss :
![\[ \begin{tabular}{|c|c|c|} \hline \textbf{flagTrue} & \textbf{flagFalse} & \textbf{Operation}\\ \hline ZERO & UNCHANGE & Thinning\\ \hline ONE & UNCHANGE & Thickening\\ \hline ONE & ZERO & Hit-or-misss\\ \hline \end{tabular} \]](form_586.png)
Skeletonization
A 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 is:
![\[\begin{array}{ccc} 1 & 1 & 1\\ \times & \bullet & \times\\ 0 & 0 & 0 \end{array}\]](form_587.png)
where 
means "don't care".
Point detectors
Once a skeleton is computed it may be useful to detect specific configurations of points. The point detectors uses hit-or-miss transforms (HMT) to select target points. The following engines are point detectors : SoEndPointsProcessing2d, SoInteriorPointsProcessing2d, SoIsolatedPointsProcessing2d.
For example:
A LUT to convert a binary image from an 8 neighbors connexity to 4 neighbors connexity can be defined testing if a given pixel has a neighbour in the north east, north west, south west and south east directions.
These kernels have to be added one by one to build the LUT, using the addKernel method. The first kernel has to be inserted with the mode NEW, that indicates the LUT has to be reset before to add this kernel inside. Other kernels have to be ineserted with the mode OR to indicate to look for this kernels or one of the previous.
- 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 bits reduction is applied. The addKernel method function fills an array of 4194304 elements to build the LUT.
- Once the 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: flagTrue if the pixel matches and flagFalse if it does not. There are 4 possible values :
- OUTPUT_ZERO : Force the output value to zero
- OUPUT_ONE : Force the output value to one
- OUTPUT_CHANGE : invert the output value
- OUPUT_UNCHANGE : let the output value unchanged.
For example : to change the connexity from 8 neighbors connexity to 4 , if the pixel matches the criteria the output value has to be forced to 0 and if it does not it has to be let unchanged. Therefore flagTrue = OUTPUT_ZERO and flagFalse = OUPUT_UNCHANGE.
Thinning, thickening and hit-or-miss operation with Morphological LUT As a consequence morphological LUT's can be used to perform classical neighborhood operations such as thinning, thickening and hit-or-miss :
Skeletonization
A 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 is:
where means "don't care".
Point detectors
Once a skeleton is computed it may be useful to detect specific configurations of points. The point detectors uses hit-or-miss transforms (HMT) to select target points. The following engines are point detectors : SoEndPointsProcessing2d, SoInteriorPointsProcessing2d, SoIsolatedPointsProcessing2d.
where means "don't care".