Find known sub image in larger image

Question

Does anyone know of an algorithm (or search terms / descriptions) to locate a known image within a larger image?

e.g.

I have an image of a single desktop window containing various buttons and areas (target). I also have code to capture a screen shot of the current desktop. I would like an algorithm that will help me find the target image within the larger desktop image (what exact x and y coordinates the window is located at). The target image may be located anywhere in the larger image and may not be 100% exactly the same (very similar but not exact possibly b/c of OS display differences)

Does anyone know of such an algorithm or class of algorithms?

I have found various image segmentation and computer vision algorithms but they seem geared to "fuzzy" classification of regions and not locating a specific image within another.

** My goal is to create a framework that, given some seed target images, can find "look" at the desktop, find the target area and "watch" it for changes. **

Answer 1

You said your image may not be exactly the same, but then say you don't want "fuzzy" algorithms. I'm not sure those are compatible. In general, though, I think you want to look at image registration algorithms. There's an open source C++ package called ITK that might provide some hints. Also ImageJ is a popular open source Java package. Both of these have at least some registration capabilities available if you poke around.

Answer 2

Here's the skeleton of code you'd want to use:

// look for all (x,y) positions where target appears in desktop
List<Loc> findMatches(Image desktop, Image target, float threshold) {
  List<Loc> locs;
  for (int y=0; y<desktop.height()-target.height(); y++) {
      for (int x=0; x<desktop.width()-target.width(); x++) {
          if (imageDistance(desktop, x, y, target) < threshold) {
              locs.append(Loc(x,y));
          }
      }
   }
   return locs;
}

// computes the root mean squared error between a rectangular window in 
// bigImg and target.
float imageDistance(Image bigImg, int bx, int by, Image target) {
    float dist = 0.0;
    for (int y=0; y<target.height(); y++) {
        for (int x=0; x<target.width(); x++) {
            // assume RGB images...
            for (int colorChannel=0; colorChannel<3; colorChannel++) {
                dist += Math.pow(target.getPixel(x,y) - bigImg.getPixel(x,y), 2);
            }
         }
    }
    return Math.sqrt(dist) / target.width() / target.height();
}

You could consider other image distances (see a similar question). For your application, the RMS error is probably a good choice.

There are probably various Java libraries that compute this distance for you efficiently.

Answer 3

Have a look at http://werner.yellowcouch.org/Papers/subimg/index.html. It's highly detailed and appears to be the only article discussing how to apply fourier transformation to the problem of subimage finding.