Python / PIL template matching

[tillaart36]

Hello, im trying to implement a template matching algorithm with the use of Python + PIL and I'm trying to follow the code that wikipedia gives for template matching ->

http://en.wikipedia.org/wiki/Template_matching

Basically it loops through all pixels of a search image, and all pixels of a template. The sum of absolute differences in the wikipedia link i have substituted with a simple check if the pixel value at the positions is the same.

The program does more or less what i want. It finds the x and y position of where the template matches the image. I added some code to generate a new image (with the same sizes as the search image) and I paste the template in this new empty image on the found position so i can compare this generated image with the search image and they are indeed the same every time.

This is my "beginner" code:

from PIL import Image



def matchTemplate(searchImage, templateImage):
    minScore = -1000
    searchWidth = searchImage.size[0]
    searchHeight = searchImage.size[1]
    templateWidth = templateImage.size[0]
    templateHeight = templateImage.size[1]
    #loop over each pixel in the search image
    for xs in range(searchWidth):
        for ys in range(searchHeight):
            #set some kind of score variable to 0
            score = 0
            #loop over each pixel in the template image
            for xt in range(templateWidth):
                for yt in range(templateHeight):
                    if xs+xt < 0 or ys+yt < 0 or xs+xt >= searchWidth or ys+yt >= searchHeight:
                        score += 0
                    else:
                        pixel_searchImage = searchImage.getpixel(((xs+xt),(ys+yt)))
                        pixel_templateImage = templateImage.getpixel((xt, yt))
                        if pixel_searchImage == pixel_templateImage:
                            score += 1
                        else: score -= 1

            if minScore < score:
                minScore = score
                matching_xs = xs
                matching_ys = ys
                matching_xt = xt
                matching_yt = yt
                matching_score = score
                
    print matching_xs, matching_ys, matching_xt, matching_yt, matching_score
    im1 = Image.new('RGB', (searchWidth, searchHeight), (80, 147, 0))
    im1.paste(templateImage, ((matching_xs), (matching_ys)))
    searchImage.show()
    im1.show()
    im1.save('template_matched_in_search.jpg')


searchImage = Image.open("search_gray.jpg")
templateImage = Image.open("template_gray.jpg")

matchTemplate(searchImage, templateImage)
print "end"

The problem is the running time. When the search image is 60x60 pixels (yes this is a very small image) and the template is 10x10 pixels, the running time is about 1 minute. Offcourse when I go up with a search image of say 500x500 and a template of 80x80 pixels the running time was at least up to 1 hour (I cancelled the program because it took this long allready :D) and can be more. Are there any ways to speed things up because I want to do some more testing with this on different search images and templates.

Maybe if I make lists of the pixelvalues of each image, and compare them with eachother will be faster?

Anyways I'm just looking for some ideas to either improve the above code or another way to do such a template matching. Thanks for your help in advance :)

BTW here is a template, a search image, and a generated image with the template pasted on the found location:

[nezachem]

I don't think that this implementation can be radically optimized. The Wiki article gives some advices on the speedup (Fourier transforms and image pyramid). Try them.
I'd expect that convolution will yield the best results, however it implies a very good math background. A pyramid could be a fun to program.

[djidjadji]

To be able to see the improvement of an optimization timing the code is a good instrument.
If I time your original code with your example images using the following

import datetime
t1=datetime.datetime.now()
matchTemplate(searchImage, templateImage)
delta=datetime.datetime.now()-t1
print "Time=%d.%d"%(delta.seconds,delta.microseconds)

I get Time=4.625000 If we look at the code we see that xs+xt never will be negative, so also for ys+yt. And if we adjust the ranges for xs and ys then xs+xt and ys+yt will never go out of bounds. There is no need to save matched_xt and matched_yt, they are always the same and never used. The changed code is

from PIL import Image
import datetime

def matchTemplate(searchImage, templateImage):
    minScore = -1000
    searchWidth = searchImage.size[0]
    searchHeight = searchImage.size[1]
    templateWidth = templateImage.size[0]
    templateHeight = templateImage.size[1]
    #loop over each pixel in the search image
    for xs in range(searchWidth-templateWidth+1):
        for ys in range(searchHeight-templateHeight+1):
            #set some kind of score variable to 0
            score = 0
            #loop over each pixel in the template image
            for xt in range(templateWidth):
                for yt in range(templateHeight):
                    pixel_searchImage = searchImage.getpixel(((xs+xt),(ys+yt)))
                    pixel_templateImage = templateImage.getpixel((xt, yt))
                    score += 1 if pixel_searchImage == pixel_templateImage else -1

            if minScore < score:
                minScore = score
                matching_xs = xs
                matching_ys = ys
                matching_score = score
                
    print "Location=",(matching_xs, matching_ys), "Score=",matching_score
    im1 = Image.new('RGB', (searchWidth, searchHeight), (80, 147, 0))
    im1.paste(templateImage, ((matching_xs), (matching_ys)))
    #searchImage.show()
    #im1.show()
    im1.save('template_matched_in_search.png')


searchImage = Image.open("search_gray.jpg")
templateImage = Image.open("template_gray.jpg")

t1=datetime.datetime.now()
matchTemplate(searchImage, templateImage)
delta=datetime.datetime.now()-t1
print "Time=%d.%d"%(delta.seconds,delta.microseconds)
print "end"

I get Time=3.735000 If we read the manual of PIL we see that getpixel() is an expensive operation. Better is to use Image.getdata() or Image.load(). Here I use Image.load() because then we don't have to do the array index calculation. The changed code is

from PIL import Image
import datetime

def matchTemplate(searchImage, templateImage):
    minScore = -1000
    matching_xs = 0
    matching_ys = 0
    searchWidth = searchImage.size[0]
    searchHeight = searchImage.size[1]
    templateWidth = templateImage.size[0]
    templateHeight = templateImage.size[1]
    searchIm = searchImage.load()
    templateIm = templateImage.load()
    #loop over each pixel in the search image
    for xs in range(searchWidth-templateWidth+1):
        for ys in range(searchHeight-templateHeight+1):
        #for ys in range(10):
            #set some kind of score variable to 0
            score = 0
            #loop over each pixel in the template image
            for xt in range(templateWidth):
                for yt in range(templateHeight):
                    score += 1 if searchIm[xs+xt,ys+yt] == templateIm[xt, yt] else -1

            if minScore < score:
                minScore = score
                matching_xs = xs
                matching_ys = ys
                
    print "Location=",(matching_xs, matching_ys), "Score=",minScore
    im1 = Image.new('RGB', (searchWidth, searchHeight), (80, 147, 0))
    im1.paste(templateImage, ((matching_xs), (matching_ys)))
    #searchImage.show()
    #im1.show()
    im1.save('template_matched_in_search.png')


searchImage = Image.open("search_gray.jpg")
templateImage = Image.open("template_gray.jpg")

##searchImage = Image.open("search-500.png")
##templateImage = Image.open("template-80.png")

t1=datetime.datetime.now()
matchTemplate(searchImage, templateImage)
delta=datetime.datetime.now()-t1
print "Time=%d.%d"%(delta.seconds,delta.microseconds)
print "end"

I get Time=0.360000 That is fast enough for this little picture. But if I use it on a test set with source is 500x500 pixels and template 80x80. It will take some time. To estimate how long it will take I only timed testing the top 10 rows. Change the comment on the for ys lines and enable the loading of the large images.
For 10 rows it took Time=35.813000 .
If we extrapolate that to the complete image we get Time=35.813*(500-80)/10/60=1504.146=~25min A good python optimization rule: If there is a C/Library method that does the same job use it .
Looking at the PIL module we find the ImageChops module.
If we redesign the algorithm we can use the ImageChops.difference() method.

1. Use grey level images, only one band, to reduce computation if you don't do color
2. Create a Mask image the size of the template with the color=1
3. Crop from the source an image the size of the template, for every location we want to test
4. Take the ImageChops.difference() of the cropped image and the template
5. Find out which pixels are not equal by testing if they are 1 or larger using ImageChops.darker() with the difference image and the Mask
6. Count the number of NotEqual pixels using sum()
7. Adjust the score

from PIL import Image
from PIL import ImageChops

import datetime

def matchTemplate(searchImage, templateImage):
    minScore = -1000
    matching_xs = 0
    matching_ys = 0
    # convert images to "L" to reduce computation by factor 3 "RGB"->"L"
    searchImage = searchImage.convert(mode="L")
    templateImage = templateImage.convert(mode="L")
    searchWidth, searchHeight = searchImage.size
    templateWidth, templateHeight = templateImage.size
    # make a copy of templateImage and fill with color=1
    templateMask = Image.new(mode="L", size=templateImage.size, color=1)
    #loop over each pixel in the search image
    for xs in range(searchWidth-templateWidth+1):
        for ys in range(searchHeight-templateHeight+1):
        #for ys in range(10):
            #set some kind of score variable to "All equal"
            score = templateWidth*templateHeight
            # crop the part from searchImage
            searchCrop = searchImage.crop((xs,ys,xs+templateWidth,ys+templateHeight))
            diff = ImageChops.difference(templateImage, searchCrop)
            notequal = ImageChops.darker(diff,templateMask)
            countnotequal = sum(notequal.getdata())
            score -= countnotequal

            if minScore < score:
                minScore = score
                matching_xs = xs
                matching_ys = ys
                
    print "Location=",(matching_xs, matching_ys), "Score=",minScore
    im1 = Image.new('RGB', (searchWidth, searchHeight), (80, 147, 0))
    im1.paste(templateImage, ((matching_xs), (matching_ys)))
    #searchImage.show()
    #im1.show()
    im1.save('template_matched_in_search.png')


searchImage = Image.open("search_gray.jpg")
templateImage = Image.open("template_gray.jpg")

searchImage = Image.open("search-500.png")
templateImage = Image.open("template-80.png")

t1=datetime.datetime.now()
matchTemplate(searchImage, templateImage)
delta=datetime.datetime.now()-t1
print "Time=%d.%d"%(delta.seconds,delta.microseconds)
print "end"

I get Time=145.235000=~2.5min

[tillaart36]

Thanks for your replies....and thanks for taking the time to play with the code...I will look at it right now. BTW I also experimented with putting the image to an array with the help of numpy...this speeded things up also.

[vegaseat]

RE djidjadji
I test drove your final code and it works like a charm!
Thanks for the very nice contribution!

Would be great for a code snippet.