Find an Image within an Image

Question

I am looking for the best way to detect an image within another image. I have a small image and would like to find the location that it appears within a larger image - which will actually be screen captures. Conceptually, it is like a 'Where's Waldo?' sort of search in the larger image.

Are there any efficient/quick ways to accomplish this? Speed is more important than memory.

Edit:

The 'inner' image may not always have the same scale but will have the same rotation.

It is not safe to assume that the image will be perfectly contained within the other, pixel for pixel.

Answer 1

You can treat this as a substring problem, where characters in the alphabet are pixels and your string is the image. You would need also to use a special character in a similar vein to a linebreak, to denote the image boundary.

The algorithm you want is on wikipedia: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Update: If you cannot assume that the image is perfectly contained within the other, pixel for pixel, then this approach will not work.

There are other, more complicated algorithms based on the same dynamic programming concept as the above, but I won't go into them unless it's necessary.

Answer 2

Wikipedia has an article on Template Matching, with sample code.

(While that page doesn't handle changed scales, it has links to other styles of matching, for example Scale invariant feature transform)

Answer 3

If rotation also had to be catered for, the Generalised Hough Transform can be used.