Hit-or-miss transform in OpenCV Posted on Jan 19, 2013 / 1 comment

Hit-or-miss transform is a very useful tool in binary image analysis. Too bad that as of OpenCV 2.4.3 this operation is not yet supported. In this tutorial I will show you how to perform hit-or-miss transform using OpenCV’s basic morphology functions and some sample applications.

When I was searching for algorithms for pruning, I couldn’t find any but only with image morphology as described in “Digital Image Processing” by Gonzalez and Woods. And the pruning requires the hit-or-miss transform. In Matlab, the transform is implemented in bwhitmiss.

This transform is useful in locating all pixels that match the shape of kernel B₁ and don’t match the shape of kernel B₂. The hit-or-miss transform of a given image A and kernel B=(B₁, B₂) is defined as:

That is, erode image A by kernel B₁ and erode the complement of A by kernel B₂ then AND-ing both results. Note that we can combine both B₁ and B₂ into a single structuring element which can contains 1, 0, or -1. The 1-valued elements make up the domain of B₁ and the -1-valued elements make up the domain of B₂, and the 0-valued elements are ignored.

Let’s see the code first.

#include <opencv2/imgproc/imgproc.hpp>

/**
 * Hit-or-miss transform function
 *
 * Parameters:
 *   src     The source image, 8 bit single-channel matrix
 *   dst     The destination image
 *   kernel  The kernel matrix. 1=foreground, -1=background, 0=don't care
 */
void hitmiss(cv::Mat& src, cv::Mat& dst, cv::Mat& kernel)
{
  CV_Assert(src.type() == CV_8U && src.channels() == 1);

  cv::Mat k1 = (kernel == 1) / 255;
  cv::Mat k2 = (kernel == -1) / 255;

  cv::normalize(src, src, 0, 1, cv::NORM_MINMAX);

  cv::Mat e1, e2;
  cv::erode(src, e1, k1, cv::Point(-1,-1), 1, cv::BORDER_CONSTANT, cv::Scalar(0));
  cv::erode(1-src, e2, k2, cv::Point(-1,-1), 1, cv::BORDER_CONSTANT, cv::Scalar(0));
  dst = e1 & e2;
}

Now we see how to use the function above for solving pattern-finding problem. Let’s say that we have a binary image like this:

Figure 1. A binary image with 1=foreground and 0=background.

And we want to detect zero-values pixels which have one-valued north, east, south, and west neighbors. First, we create the structuring element representing neighborhood we want to “hit”, shown in Fig 2a. Second we create the structuring element representing neighborhood we want to “miss”, shown if Fig 2b. Combining both structuring element results in Fig 2c.

Figure 2. (a) The kernel to 'hit'. (b) The kernel to 'miss'. (c) The combination of (a) and (b) where
1=foreground, -1=background, 0=don't care.

The C++ code:

cv::Mat a = (cv::Mat_<uchar>(8,8) << 0, 0, 0, 0, 0, 0, 0, 0,
                                     0, 1, 1, 1, 0, 0, 0, 0, 
                                     0, 1, 0, 1, 0, 0, 0, 1,
                                     0, 1, 1, 1, 0, 1, 0, 0,
                                     0, 0, 1, 0, 0, 0, 0, 0,
                                     0, 0, 1, 0, 0, 1, 1, 0,
                                     0, 1, 0, 1, 0, 0, 1, 0,
                                     0, 1, 1, 1, 0, 0, 0, 0 );

cv::Mat b = (cv::Mat_<char>(3,3) << 0, 1, 0, 1,-1, 1, 0, 1, 0 );

hitmiss(a, a, b);
std::cout << a << std::endl;

Which will result in:

[0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 1, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 1, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0]

You can see that the hit-or-miss transform successfully located the two points where a 0-values pixel had one-valued north, east, south, and west neighbors.

Let’s take another example. Suppose we want to find the top-right right-angle from the image in Figure 1. The kernels for detecting the top-right right-angle is shown in Figure 3.

Figure 3. The kernels for locating top-right right-angle.
(a) The kernel to 'hit'. (b) The kernel to 'miss'. (c) The combination of (a) and (b).

...
cv::Mat b = (cv::Mat_<char>(3,3) << 0,-1,-1, 1, 1,-1, 0, 1, 0);
hitmiss(a, a, b);
std::cout << a << std::endl;

The result:

[0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 1, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 1, 0;
 0, 0, 0, 0, 0, 0, 0, 0;
 0, 0, 0, 0, 0, 0, 0, 0]

Again, hit-or-miss transform successfully located the top-right right-angle. This transform rocks!

Given the examples above, it is clear that hit-or-miss transform is very useful in detecting a given configuration or pattern in a binary image. Another advanced uses of this transform is for thinning, thickening, and pruning.