Hit-and-Miss Algorithm

The purpose of the hit-and-miss algorithm is to detect certain patterns in a binary image, using a structuring element containing 1's, 0's and blanks for don't cares. The structuring element is used as a template that slides over the binary image (similar to a convolution kernel) and the pixel corresponding to the center of the template is set to 1 if the template matches the image, or 0 otherwise. For example, the following four structuring elements can detect corners of four different orientations. The final result is an OR of four images each obtained by one of the four structuring elements.

Hit-and-miss algorithm can be used to thin and skeletonize a shape in a binary image. This is an iterative process containing repeated steps to thin the shape by hit-and-miss method. In each iteration, some different structuring elements are used to identify the edge pixels to be removed, followed by the actual removal of them:

$$I'_k=O_i(I_k),\;\;\;\;\;I_{k+1}=I_k -I'_k, \;\;\;\;k=k+1$$

where $I_k$ is the image after k iterations, $O_i(I_k)$ is the application of a structuring element $O_i$ to $I_k$, and $I_k-I'_k$ is a set subtraction $A-B=A\cap \bar{B}$. After each such iteration, the elements are rotated to identify and remove other edge pixels in different orientations. The process continues until no further edge pixels can be identified, and the shape has been thinned to a skeleton.