The hit-and-miss transform is a general binary morphological operation that can be used to look for particular patterns of foreground and background pixels in an image. It is actually the basic operation of binary morphology since almost all the other binary morphological operators can be derived from it. As with other binary morphological operators it takes as input a binary image and a structuring element, and produces another binary image as output.
The structuring element used in the hit-and-miss is a slight extension to the type that has been introduced for erosion and dilation, in that it can contain both foreground and background pixels, rather than just foreground pixels, i.e. both ones and zeros. Note that the simpler type of structuring element used with erosion and dilation is often depicted containing both ones and zeros as well, but in that case the zeros really stand for `don't care's', and are just used to fill out the structuring element to a convenient shaped kernel, usually a square. In all our illustrations, these `don't care's' are shown as blanks in the kernel in order to avoid confusion. An example of the extended kind of structuring element is shown in Figure 1. As usual we denote foreground pixels using ones, and background pixels using zeros.
Figure 1 Example of the extended type of structuring element used in hit-and-miss operations. This particular element can be used to find corner points, as explained below.
The hit-and-miss operation is performed in much the same way as other morphological operators, by translating the origin of the structuring element to all points in the image, and then comparing the structuring element with the underlying image pixels. If the foreground and background pixels in the structuring element exactly match foreground and background pixels in the image, then the pixel underneath the origin of the structuring element is set to the foreground color. If it doesn't match, then that pixel is set to the background color.
For instance, the structuring element shown in Figure 1 can be used to find right angle convex corner points in images. Notice that the pixels in the element form the shape of a bottom-left convex corner. We assume that the origin of the element is at the center of the 3×3 element. In order to find all the corners in a binary image we need to run the hit-and-miss transform four times with four different elements representing the four kinds of right angle corners found in binary images. Figure 2 shows the four different elements used in this operation.
Figure 2 Four structuring elements used for corner finding in binary images using the hit-and-miss transform. Note that they are really all the same element, but rotated by different amounts.
After obtaining the locations of corners in each orientation, We can
then simply OR all these images together to get the final
result showing the locations of all right angle convex corners in any
orientation. Figure 3 shows the effect of this corner detection
on a simple binary image.
Figure 3 Effect of the hit-and-miss based right angle convex corner detector on a simple binary image. Note that the `detector' is rather sensitive.
Implementations vary as to how they handle the hit-and-miss transform at the edges of images where the structuring element overlaps the edge of the image. A simple solution is to simply assume that any structuring element that overlaps the image does not match underlying pixels, and hence the corresponding pixel in the output should be set to zero.
The hit-and-miss transform has many applications in more complex morphological operations. It is being used to construct the thinning and thickening operators, and hence for all applications explained in these worksheets.
The hit-and-miss transform is used to look for occurrences of particular binary patterns in fixed orientations. It can be used to look for several patterns (or alternatively, for the same pattern in several orientations as above) simply by running successive transforms using different structuring elements, and then ORing the results together.
The operations of erosion, dilation, opening, closing, thinning and thickening can all be derived from the hit-and-miss transform in conjunction with simple set operations.
Figure 4 illustrates some structuring elements that can be used for locating various binary features.
Figure 4 Some applications of the hit-and-miss transform. 1 is used to locate isolated points in a binary image. 2 is used to locate the end points on a binary skeleton Note that this structuring element must be used in all its rotations so four hit-and-miss passes are required. 3a, 3b, and 3c are the kernels used to locate the triple points (junctions) on a skeleton. All three structuring elements must be run in all orientations so twelve hit-and-miss passes are required.
We illustrate two of these applications on an image skeleton.
We start with
which is the skeleton of
The image
shows the triple points (i.e. points where three lines meet) of the skeleton. Note that the hit-and-miss transform itself merely outputs single foreground pixels at each triple point (the rest of the output image being black). To produce our example here, this image was then dilated once using a cross-shaped structuring element in order to mark these isolated points clearly, and this was then ORed with the original skeleton in order to produce the overlay.
The image
shows the end points of the skeleton. This image was produced in a similar way to the triple point image above, except of course that a different structuring element was used for the hit-and-miss operation. In addition, the isolated points produced by the transform were dilated with a square in order to mark them, rather than with a cross.
The successful use of the hit-and-miss transform relies on being able to think of a relatively small set of binary patterns that capture all the possible variations and orientations of a feature that is to be located. For features larger than a few pixels across this is often not feasible.
You can interactively experiment with this operator by clicking here.
R. Gonzalez and R. Woods Digital Image Processing, Addison-Wesley Publishing Company, 1992, p 528.
R. Haralick and L. Shapiro Computer and Robot Vision, Vol. 1, Addison-Wesley Publishing Company, 1992, Chap 5, pp 168 - 173.
A. Jain Fundamentals of Digital Image Processing, Prentice-Hall, 1989, Chap. 9.
D. Vernon Machine Vision, Prentice-Hall, 1991, p 75.
Specific information about this operator may be found here.
More general advice about the local HIPR installation is available in the Local Information introductory section.
©2003 R. Fisher, S. Perkins,
A. Walker and E. Wolfart.
