JOURNEY INTO THE WORLD OF IMAGE PROCESSING (CHAPTER 9 OUT OF 9)
Template Matching using Python
In this part of the journey, we will discuss how to do template matching in an image. Using a template image, you will find where the template is most similar to the other image.
Throughout the discussion, we will use the following libraries.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from skimage.io import imread, imshow
from skimage.color import rgb2gray
from matplotlib.patches import Circle
from skimage import transformSingle Matching
The algorithm of template matching is simple. A template image is compared to a part of a larger image, sliding a window in the latter one pixel at a time. The similarity between the template and the sliding window of the larger image is determined. The most similar section of the larger image can be returned as the most matched part.
To do template matching, we need to grayscale our image first. Although this would still work for RGB images, it would simplify our analysis for now if we use grayscale.
# Load image
img = imread('img_wally.png')
img_gs = rgb2gray(img)
# Plot
fig, ax = plt.subplots(1, 2, figsize=(16, 8))
ax[0].imshow(img)
ax[0].set_title("Original Image of Where's Wally?")
ax[0].set_axis_off()
ax[1].imshow(img_gs, cmap='gray')
ax[1].set_title("Grayscale Image of Where's Wally?")
ax[1].set_axis_off()
plt.show()
Then we get a sample of the object we want to use as the template. For this case, we will get “Wally” in the image. Then we will apply template matching. This will be done using the `match_template` from the `skimage.feature`.
# Get a template image and match it with the grayscale image
img_template = img_gs[410:435, 600:625]
result = match_template(img_gs, img_template)
fig, ax = plt.subplots(1, 1, figsize=(8, 8))
ax.imshow(result, cmap='viridis')
ax.set_title("Result of Template Matching")
ax.set_axis_off()
plt.show()
This plot shows the peaks of the matching. The part in the middle with high intensity of yellow is the top match of the template. We will add a bounding box to our grayscale image to better visualize this.
# Getting the max
x, y = np.unravel_index(np.argmax(result), result.shape)
imshow(img_gs)
template_width, template_height = img_template.shape
rect = plt.Rectangle((y, x), template_height, template_width, color='red',
fc='none')
plt.gca().add_patch(rect)
plt.title('Grayscale Image with Bounding Box around Wally')
plt.axis('off')
plt.show()
This example seems trivial since we initially get the original template by manually searching for it then the algorithm searches it again in the image. To add more complexity, we will try to find multiple occurrences of the template in the image.
Multiple Matching
For this case, we will use the album tracklist of Fearless by Taylor Swift.
# Load image
img_ts = imread('TS_fearless.jpg')
tracks = imread('Fearless_Tracks.png')
# Plot
fig, ax = plt.subplots(1, 1, figsize=(5, 5))
ax.imshow(img_ts)
ax.set_title("Fearless (Taylor's Version) Album Cover")
ax.set_axis_off()
plt.show()
fig, ax = plt.subplots(1, 1, figsize=(5, 5))
ax.imshow(tracks)
ax.set_title("Fearless (Taylor's Version) Tracks")
ax.set_axis_off()
plt.show()
Similar to earlier, we will get the grayscale image and the sample template from the image. In our case, we want to find the new songs in the album, which is indicated by the tag `(FROM THE VAULT)`.
# Grayscale the image
img_tracks_gs = rgb2gray(tracks)
# Get a template image
ts_template = img_tracks_gs[499:513, 180:315]
# Plot
fig, ax = plt.subplots(1, 1, figsize=(8, 8))
ax.imshow(ts_template, cmap='gray')
ax.set_title("Template of the text '(FROM THE VAULT)'")
ax.set_axis_off()
plt.show()
We need to set the threshold as an additional parameter when finding multiple matches. This threshold will determine whether the similarity score between the template and the sliding window in the larger image matches the template.
For our case, let us try out different threshold values.
# Get the template matching results
result_ts = match_template(img_tracks_gs, ts_template)# Plot multiple results at different interval (threshold=0.40)
plt.imshow(img_tracks_gs, cmap='gray')
template_width, template_height = ts_template.shape
for x, y in peak_local_max(result_ts, threshold_abs=0.40):
rect = plt.Rectangle((y, x), template_height, template_width, color='red',
fc='none')
plt.gca().add_patch(rect)
plt.title('Template Matching at Threshold=0.40')
plt.axis('off')
plt.show()
Here we have set the threshold value too low, resulting in false matching by the algorithm. It returns a bounding box that doesn’t contain our template. To correct this, we need to increase our threshold.
# Plot multiple results at different interval (threshold=0.80)
plt.imshow(img_tracks_gs, cmap='gray')
template_width, template_height = ts_template.shape
for x, y in peak_local_max(result_ts, threshold_abs=0.99):
rect = plt.Rectangle((y, x), template_height, template_width, color='red',
fc='none')
plt.gca().add_patch(rect)
plt.title('Template Matching at Threshold=0.99')
plt.axis('off')
plt.show()
Here, the template matching results are just the original section of the image we used as the template. Similar results didn’t meet the too-high threshold set. We need to find the sweet spot to return all relevant matches but ensure no false match will be returned.
# Plot multiple results at different interval (threshold=0.99)
plt.imshow(img_tracks_gs, cmap='gray')
template_width, template_height = ts_template.shape
for x, y in peak_local_max(result_ts, threshold_abs=0.80):
rect = plt.Rectangle((y, x), template_height, template_width, color='red',
fc='none')
plt.gca().add_patch(rect)
plt.title('Template Matching at Threshold=0.80')
plt.axis('off')
plt.show()
We now have returned only those songs that are truly from the vault. It is trial and error to check which threshold would yield the best results.
This technique of template matching is scale and rotational variant. If the template can be found in the bigger image, only those with the same scale and rotation would output. The algorithm does not detect similar objects that are reduced, enlarged, or rotated. To solve this problem, several algorithms have been developed. An example is Scale Invariant Feature Transform or SIFT by D. Lowe.
Key Takeaways
Template matching is essential if we don’t have enough datasets for image detection using Deep Learning (CNN). It provides a much simple and scalable way to do object detection. It can be modified to return multiple results to provide more use-case, especially if the template can be found multiple times in the image.
End of Journey
This blog marks the end of our journey into the World of Image Processing. I hope you enjoy and learn a lot in this adventure. Huge thanks also to our Introduction in Image Processing professor, Mr. Benjur Emmanuel L. Borja. His lectures, notebooks, and dataset helped me make this blog.
