Template Matching

Robert Washbourne - 5 years ago - programming

I will be using correlation code from Correlation, so check that out.
For the imaging, we will use Scipy to load images, Numpy to edit the arrays, and Pyplot to show the images. This first part is image correlation code, the second part is matching templates.

from scipy.misc import imread import numpy as np from matplotlib import pyplot as plt

If you import just scipy, then misc will not work.

>> import scipy 
>>> scipy.misc.imread 
Traceback (most recent call last): File "<pyshell#1>", line 1, in <module> scipy.misc.imread AttributeError: 'module' object has no attribute 'misc' 
>>> import scipy.misc 
>>> scipy.misc.imread 
<function imread at 0x000000000CB9DF98>

So now we need to find correlation in images.

When we read an image with scikit, it saves it as a two dimensional array with each member an RGB value, like the image on the right. To compute the correlation in an image, we can take advantage of the element wise multiplication for numpy arrays. In numpy, if we have to lists, we can just do list1*list2 and get a list with each element
multiplied with its respective element.

>>> import numpy as np 
>>> list1 = np.array([1,2,3]) 
>>> list2 = np.array([3,2,6]) 
>>> list1*list2 array([ 3, 4, 18])

So in our correlation function, we can just use the array multiplication provided.
Since this is an 2D array with three RGB value, we must sum three times, like this:

def corr(img1,img2): return (sum(sum(sum(img1*img2)))/ (sum(sum(sum(img1*img1)))*sum(sum(sum((img2*img2)))))**0.5)

To test if this works, we input two images that are the same:

>>>img2 = scipy.misc.imread('image.png') >>>print corr(img1,img1) 1.0

It’s working! Of course, to do this with your own images, you must change the filename.

Part two: Template Matching

Now that we have this image correlation code, we will search the whole image for correlation. If the images are just shifted horizontally, like in stereo images, then adjust the code to just search x. What we are going to do is test correlation between the template and the image at every point, and add that correlation to a list. Then we find the highest correlation and find the index of that location and return it. We need a list to add each correlation to, so we make a list of zeros the size of the image that we can append to. We can do this with this: list  =  [[0 for i in range(X)] for j in range(Y)]. This is the same as iteration over x and y in a loop, but more compact. Python Wiki Topic

def tempMatch(template, img, blockSize):
    correl = [
        [0
            for i in range(img.shape[1] + blockSize)
        ]
        for j in range(img.shape[1])
    ]

for x in range(img.shape[0] - blockSize):
    for y in range(img.shape[1] - blockSize):
    window = img[x: (x + blockSize), y: (y + blockSize)]
correl[x][y] = corr(window, template)
correl = np.array(correl)
return np.unravel_index(np.argmax(correl), correl.shape)

This reads:
Create a list full of zeros.
Loop through every template possible in image.
Check correlation and add to a list.
Convert the list to a numpy array.
Return the coefficients of the template found.

>>> img1 = plt.imread('v1.png') 
>>> temp = img1[100:110,30:40] 
>>> tempMatch(temp,img1,10) [100, 30]

Full Code

Download Correlation.py

import scipy.misc
import numpy as np from matplotlib
import pyplot as plt def corr(img1, img2): return (sum(sum(sum(img1 * img2))) / (sum(sum(sum(img1 * img1))) * sum(sum(sum((img2 * img2))))) * * 0.5) def tempMatch(template, img, blockSize): correl = [
    [0
        for i in range(img.shape[1] + blockSize)
    ]
    for j in range(img.shape[1])
]
for x in range(img.shape[0] - blockSize): for y in range(img.shape[1] - blockSize): window = img[x: (x + blockSize), y: (y + blockSize)] correl[x][y] = corr(window, template) correl = np.array(correl) return np.unravel_index(np.argmax(correl), correl.shape) img1 = plt.imread('v1.png') temp = img1[100: 110, 30: 40] a = tempMatch(temp, img1, 10)