Hit-or-miss

In Mathematical morphology, the Hit-or-Miss operator is useful to describe the topology of a graph-like object. Even though this is not implemented − by default − in ImageJ, we can obtain a similar result...


The picture of Fig.1 is a classical example of what can do a Hit-or-Miss operator for describing the topology of the graph (leaves, nodes, corners, etc.).

Fig. 1: Test image

Note: This image is usually the result of a Skeletonize operation (another Mathematical Morphology operation, maybe the subject of another post).

1- Introduction

The Hit-or-Miss (also called Hit-and-Miss) operator is an erosion-like function that only works for a specific topology of TRUE and FALSE pixels in a 3x3 kernel (structuring element in the terminology of Mathematical Morphology).
If the combination of TRUE and FALSE pixels in the structuring element exactly match the pixels in the image, then the pixel underneath the origin of the structuring element is set to TRUE otherwise it is set to FALSE.

For example, if you want to detect the lower left corner of an object of interest, you can design the 3x3 kernel of Fig. 2A. The central pixel corresponds to the lower left corner. However, this first version is limited to filled rectangles and can be improved by removing the unnecessary pixels (Fig. 2B and 2C). The 'X' pixels are called 'Don't Care' pixels because whatever their value ​​(0 or 1), it does not change the topology of the feature detection.

0 1 1   0 1 X   X 1 X

0 1 1   0 1 1   0 1 0

0 0 0   0 0 0   0 0 X

Fig.2:  Designing a kernel to detect a 90° corner. A) First attempt. Only works with filled rectangles. B) We don't care of the inner pixel. C) If we are working in a 4-pixels connectivity, the diagonal pixels are irrelevant. They are set to 'Don't Care' pixels ('X').

As there is four different patterns of corners, you need four kernels (Fig. 3).

X 1 X   0 0 X   X 0 0   X 1 X

0 1 1   0 1 1   1 1 0   1 1 0

0 0 X   X 1 X   X 1 X   X 0 0

Fig.3: Four kernels required to detect corners. The '0' and '1' correspond to the FALSE and TRUE pixels, respectively. The 'X's are the 'Don't care' pixels (0 or 1).

Applying these four kernels to the image of Fig. 4A yields the image of Fig. 4B.

Fig.4: Detecting corners with a Hit-or-Miss operator. For sake of convenience, the corners were dilated.

Note: If you want to restrict corners detection to 90° corner in a 8-pixels connectivity, you have to use the following pattern:

0 1 X

0 1 1

0 0 0

2- Detecting ends (leaves) of a graph

Similarly, the detection of ends in the graph is possible with the eight following kernels (Fig. 5) which are based on the first (left in Fig. 5) kernel successively rotated by  45°.

0 0 0  0 0 0  0 0 0  1 0 0  0 1 0  0 0 1  0 0 0  0 0 0

0 1 0  0 1 0  1 1 0  0 1 0  0 1 0  0 1 0  0 1 1  0 1 0

0 1 0  1 0 0  0 0 0  0 0 0  0 0 0  0 0 0  0 0 0  0 0 1

Fig. 5: Eight structuring elements detecting ends (leaves) of a graph.

... and here is the result (Fig. 6) ...

Fig.6: Leaves detection (green) of the graph of Fig. 1 (red) calculated from the eight kernels of Fig. 5.

Now, it is time to see how we can use a Hit-or-Miss in ImageJ. To be continued ...

>> Next: Hit-and-Miss − In ImageJ

Further readings

Mathematical morphology [Link]
Image Processing [Link]