Locating a template in an image

I have an image, and a template. I'm trying to find out if the template exists in the image, and if it does, where its instances within the image are. Something like these images:

http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/ex1-model-bit.gif http://开发者_如何学Pythonwww-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/ex1-image-bit.gif

This would be the result: http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/sc1-match.gif

These images come from this page: http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html There is a reference to Rucklidge's algorithm, but I have found no information on that algorithm.

I do not need rotation more than 15 degrees or scaling more than 20% (either larger or smaller). What would be the best way to do this?

*Edit: * I have a list of black pixels that form the edges of the image, and another list of pixels that form the template. I'm just looking for a simple way to find the best (x,y) offset of the list of the template image's pixels such that they're as close as possible to the pixels that form the image. Some tolerance would be nice, to allow for a few percent of scaling or a few degrees of rotation, but nothing radical.

A bit of link-chasing from the page you cite leads to http://www.cs.cornell.edu/vision/hausdorff/hausmatch.html which has, among other things, some code for what looks like the same problem as you have.

Rucklidge published versions of his algorithm in, e.g., "Efficiently Locating Objects Using the Hausdorff Distance" (International Journal of Computer Vision, vol 24 issue 3, Sept./Oct. 1997) and in a book "Efficient visual recognition using the Hausdorff distance", Springer LNCS no 1173). I haven't read any of this other than the snippets of the book you can get via Google. It sounds as if Rucklidge has effective ways of pruning the search space, ruling out large regions of (position,transformation) by proving that they can't contain a good copy of the thing being searched for.

I think your question as it stands -- "What would be the best way to do this?" -- calls for a substantial research programme rather than a Stack Overflow answer. So far as I know (I am not an expert in the field) this is still an active and challenging area of research.

The keyword here is Hausdorff distance. Your original links has a good explanation of Hausdorff metrics. So once you learn that algorithm is pretty simple-

1. Convert image and template to binary mode.
2. Find region in image with lowest Hausdorff_distance(region, your_template)