Hit or miss transform is a basic technique for shape detection in image processing. Furthermore, this technique is useful for finding locations of specific shapes or objects in binary images.

This tool belongs among basic algorithms in morphological processing. There are posts about other morphological operations on this blog already. However, this process is an upgrade to all other, since it transforms input image and displays only the origins of the shapes we seek.

We base it on erosion process, which is one of the fundamental operations in morphological processing. But what makes hit or miss transform process special is that, we need to use two structuring elements to extract the origins of the shapes.

What is the origin of a shape or structuring element?

Origin is basically the center of the shape or structuring element. Therefore, we need to use structuring elements that are the same size as the shape we’re looking for.

How does hit or miss transform work?

As we mentioned already, we need to use erosion. But because we have two different structuring elements, we will need to apply transformation on the input image itself.

What kind of transformation am I talking about?

We need to invert values of the binary image, which means that we will turn white pixels black and vise versa. But that isn’t the end of it. Once we have these two images, we apply erosion to each one, using these two different structuring elements we spoke of earlier.

Firstly, applying erosion to the input image is pretty straight forward, there’s no special tricks we need here. As you can imagine, if we use structuring element the same size as the shape we want to detect, it’s going to erode all around leaving only one pixel in the center.

This image data will be useful later on, now let’s get to the more important part of this operation. By that I mean the erosion of the inverted image. The trick here lies in the structuring element, which is not just packed with all ones to detect where the edge is.

Structuring element for detecting background pixels (for inverted image data)

Structuring element for inverted image is all zeros, except at its border. While we can set this border of arbitrary thickness, we need to put it on the ouside edge. This means it’s slightly bigger than the first structuring element.

Special thing about this structuring element is that it will cause to set a center pixel of the inverted shape white once it lines up perfectly with it.

And lastly, the final step to this transform is to get the intersection of these two resulting erosions. This will result in an image which will only display origins of the shapes we want to detect.

Code for hit or miss transform

public static Bitmap HitOrMiss(this Bitmap image, int se_dim)
     {
         int w = image.Width;
         int h = image.Height;

         BitmapData image_data = image.LockBits(
             new Rectangle(0, 0, w, h),
             ImageLockMode.ReadOnly,
             PixelFormat.Format24bppRgb);

         int bytes = image_data.Stride * image_data.Height;
         byte[] buffer = new byte[bytes];
         byte[] result = new byte[bytes];
         byte[] inv_result = new byte[bytes];

         Marshal.Copy(image_data.Scan0, buffer, 0, bytes);
         image.UnlockBits(image_data);

         int o_left = (int)Math.Floor(((double)se_dim - 1) / 2);
         int o_right = (int)Math.Ceiling(((double)se_dim - 1) / 2);
         for (int i = o_left + 1; i < w - o_right - 1; i++)
         {
             for (int j = o_left + 1; j < h - o_right - 1; j++)
             {
                 int position = i * 3 + j * image_data.Stride;
                 byte val = 255;
                 byte ival = 255;

                 for (int k = -o_left - 1; k <= o_right + 1; k++)
                 {
                     for (int l = -o_left - 1; l <= o_right + 1; l++)
                     {
                         int se_pos = position + k * 3 + l * image_data.Stride;

                         if (k == -o_left - 1 || k == o_right + 1 || l == -o_left - 1 || l == o_right + 1)
                         {
                             byte inv_buffered = (byte)((buffer[se_pos] == 255) ? 0 : 255);
                             ival = Math.Min(ival, inv_buffered);
                         }
                         else
                         {
                             val = Math.Min(val, buffer[se_pos]);
                         }
                     }
                 }

                 for (int c = 0; c < 3; c++)
                 {
                     result[position + c] = val;
                     inv_result[position + c] = ival;
                 }
             }
         }

         for (int i = 0; i < bytes; i++)
         {
             result[i] = (byte)(result[i] == inv_result[i] ? result[i] : 0);
         }

         Bitmap res_img = new Bitmap(w, h);
         BitmapData res_data = res_img.LockBits(
             new Rectangle(0, 0, w, h),
             ImageLockMode.WriteOnly,
             PixelFormat.Format24bppRgb);
         Marshal.Copy(result, 0, res_data.Scan0, bytes);
         res_img.UnlockBits(res_data);

         return res_img;
     }

Conclusion

The code I wrote demonstrates how to apply these two erosions simultaniously, but I’m sure it can be better optimized. However, for the demonstration purpose it’ll be just fine. I hope this tutorial made things about hit or miss transform a little clearer.

You can also download the demo project and try it out yourself.