In the previous blogs, we discussed different segmentation algorithms. Now, let’s explore another important computer vision area known as object detection. This simply means identifying and locating objects, that is, where is this object present in the image. There are various algorithms available for object detection. In this blog, let’s discuss one such algorithm known as Template matching. So, let’s get started.
In the template matching, we have a template image and we need to find where is this in the input image. For this, the sliding window approach is used. In the sliding window approach, we simply slide the template image over the input image (similar to convolution) and compare the overlapping patch. For comparison, you can use any method such as cross-correlation, squared difference, etc. Below is the list of the comparison methods provided by OpenCV.
Here, I(x,y) denotes the input image, T(x,y) template image, R(x,y) result, and (w,h) as width and height of the template image.
This outputs a grayscale image, where each pixel represents how much does the neighborhood of that pixel match with the template (i.e. the comparison score). From this, we can either select the maximum/minimum (depending on the comparison method used) or use thresholding to select the probable region of interest. This is how the template matching works. Now, let’s see how to do this using OpenCV-Python.
OpenCV
OpenCV provides a built-in function cv2.matchTemplate() that implements the template matching algorithm. This takes as input the image, template and the comparison method and outputs the comparison result. The syntax is given below.
|
1 2 3 4 5 6 7 |
result = cv2.matchTemplate(image, template, method[, mask]]) # image: must be 8-bit or 32-bit floating-point # template: should have size less than input image and same data type # method: Comparison method to be used. See the table above # mask: Optional mask. must have same size as template. If data type is CV_32F, then values treated as weights otherwise treat it as the traditional mask. # result: comparison result. single-channel 32-bit floating-point. If image is W×H and templ is w×h , then result is (W−w+1)×(H−h+1) |
Let’s take the below input and template image and see how this works.
- Read both the input and the template image
- Apply the template matching using cv2.matchTemplate()
- If the method is cv2.TM_SQDIFF or cv2.TM_SQDIFF_NORMED, take the minimum, otherwise, take the maximum. This can be done using the cv2.minMaxLoc() function which finds the minimum and maximum element values and their positions.
- Once the min/max position is found, we can easily draw the rectangle by taking this position as the top-left corner and using (w,h) of the template.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import cv2 # read input and template image img = cv2.imread('D:/downloads/messi.jpg') img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) template = cv2.imread('D:/downloads/messi_temp10.jpg',0) w, h = template.shape[::-1] # Apply template Matching res = cv2.matchTemplate(img_gray,template,cv2.TM_SQDIFF) # Find min/max value and location min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res) # If the method is TM_SQDIFF or TM_SQDIFF_NORMED, # take minimum otherwise maximum bottom_right = (min_loc[0] + w, min_loc[1] + h) # draw the rectangle cv2.rectangle(img,min_loc, bottom_right, (0,0,255), 2) # Display the image cv2.imshow('a', img) cv2.waitKey(0) |
Template Matching with Multiple Objects
But what if we have multiple instances of the object present in an image. Clearly, the above approach will not work as this only finds a single instance of an object because we are finding max/min location. One plausible approach would be to use thresholding. Instead of taking out the max/min, we take out all the values greater/less than a certain threshold limit. This will not always work perfectly but still in some cases this approach can provide reasonable results.
Let’s take the below image and template to understand the multiple objects case.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import cv2 import numpy as np # Read the input and template image img = cv2.imread('D:/downloads/hearts_8.png') img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) template = cv2.imread('D:/downloads/hearts_8_temp.png',0) w, h = template.shape[::-1] # Apply template matching res = cv2.matchTemplate(img_gray,template,cv2.TM_CCOEFF_NORMED) # Threshold the result threshold = 0.95 loc = np.where(res >= threshold) # Draw the rectangle for pt in zip(*loc[::-1]): cv2.rectangle(img, pt, (pt[0] + w, pt[1] + h), (255,0,0), 1) # Display the result cv2.imshow('a',img) cv2.waitKey(0) |
Below is the resultant image.
Problems!!!
From the above result, you might have guessed the problems with this approach. Clearly, template matching is translation invariant. But as you can see from the above image, the hearts which are rotated and which have smaller size are not detected. Thus, this algorithm is not rotation and scale-invariant. Other potential problems include occlusion, illumination, and background changes, etc.
In the next blog, let’s improve this algorithm further and make it more robust against scale. For this, we will use the concept of image pyramids. See you in the next blog. Hope you enjoy reading.
If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.