7

I'm not sure where to start with this so some guidance would be good. What I need to achieve is, examine a large image (say 1280x1024) and check to see if another smaller image exists within it or not (maybe a 50x50 pixel image).

I tried doing this by comparing every pixel which is really slow and I may need to do it 100+ times so it doesn't seem suitable. I'm just wondering if there is a better way?

Thanks

Tset
  • 73
  • 1
  • 1
  • 3
  • How exact does it have to be? Could you resize the images to half the size and compare? – jestro Dec 15 '09 at 22:42
  • Can you tell us anything about the content of the images? Are they random static bitmaps, or is there some structure that you could take advantage of? Also, can you tell us about what the likelihood is of the query being "junk"? That is, what is the likelihood that the small image is NOT found in the large image? If the query has high likelihood of being junk then what you want to optimize for is quickly determining junk status. What are the consequences of getting the answer wrong, either false positive or false negative? Does it have to be exact for all images? – Eric Lippert Dec 15 '09 at 23:15
  • Oh, and do you have to determine *where* the match is, or just whether or not a match exists? – Eric Lippert Dec 15 '09 at 23:17

1 Answers1

4

I was just working on something similar and the quick and dirty result I came up with is to use AForge.Net's implementation of "ExhaustiveTemplateMatching" with images 1/4 of their size. 720p images at full size took a couple minutes but at 1/4 size it's about a second on my puny computer.

public static class BitmapExtensions
{
    /// <summary>
    /// See if bmp is contained in template with a small margin of error.
    /// </summary>
    /// <param name="template">The Bitmap that might contain.</param>
    /// <param name="bmp">The Bitmap that might be contained in.</param>        
    /// <returns>You guess!</returns>
    public static bool Contains(this Bitmap template, Bitmap bmp)
    {
        const Int32 divisor = 4;
        const Int32 epsilon = 10;

        ExhaustiveTemplateMatching etm = new ExhaustiveTemplateMatching(0.9f);                      

        TemplateMatch[] tm = etm.ProcessImage(
            new ResizeNearestNeighbor(template.Width / divisor, template.Height / divisor).Apply(template),
            new ResizeNearestNeighbor(bmp.Width / divisor, bmp.Height / divisor).Apply(bmp)
            );

        if (tm.Length == 1)
        {
            Rectangle tempRect = tm[0].Rectangle;

            if (Math.Abs(bmp.Width / divisor - tempRect.Width) < epsilon
                &&
                Math.Abs(bmp.Height / divisor - tempRect.Height) < epsilon)
            {
                return true;
            }                
        }

        return false;
    }
}

You could also of course just check for tm.length > 0 and yes there are some unnecessary divides in there :P

jestro
  • 2,524
  • 4
  • 27
  • 46
  • Thanks a lot :) from the quick test I did that seems ideal, I'll test it properly tomorrow – Tset Dec 15 '09 at 23:24