6

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.

Improve this question
5
  • I doubt language is the issue here. Whether you have the right image processing toolbox is the key.
    – PolyThinker
    Commented Jan 18, 2009 at 2:11
  • Does it have to match "exactly" pixel-by-pixel? What about rotation and scaling issues?
    – chakrit
    Commented Jan 18, 2009 at 2:25
  • @PolyThinker: True, I'll drop that specific qualifier for the question.
    – dmanxiii
    Commented Jan 18, 2009 at 2:35
  • Duplicate? stackoverflow.com/questions/297762/…
    – RexE
    Commented Jan 18, 2009 at 5:37
  • Duplicate? stackoverflow.com/questions/876142
    – endolith
    Commented Oct 14, 2009 at 22:40

3 Answers 3

Reset to default
6

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)

Improve this answer
2
1

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

Improve this answer
0

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.

Improve this answer
4
  • If the images are JPEGs you are going to have a headache :-)
    – PolyThinker
    Commented Jan 18, 2009 at 2:20
  • Yes. That is a very, very good point. If you cannot assume a perfect match, then the notion of 'best' because difficult and 'efficient/quick' become hard. You would need to do something based on energy minimization / dynamic programming
    – Owen
    Commented Jan 18, 2009 at 2:22
  • Voted down because methods like this will not work at all on images.
    – endolith
    Commented Oct 14, 2009 at 22:37
  • @Owen Can you give me some hints on how to handle the linebreaks? I'm currently doing a pixel by pixel search similar to the example code in the wikipedia Template Match link in the first answer, and its taking forever. Someone suggested I look into the Horspool algorithm which looks to do the same string search as your KMP algo. Also, whats wrong with JPEGs?
    – mikew
    Commented Feb 16, 2013 at 7:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.