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 ->
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 searchHeight = searchImage.size templateWidth = templateImage.size templateHeight = templateImage.size #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: