Match a pattern/needle (preferrably bitmap) in a haystack bitmap?

Question

i have two bitmaps in code (.NET). I'd like to search for the small pattern (needle) in the big image (haystack). How can this be done?

Answer 1

It depends if you are doing an "exact" match with bitwise patterns or just an approximate (fuzzy) image match. If you are doing an exact match simply treat the bitmaps as a generic 2D data array search.

A naive but very easy implementation for the exact match can be made in N*M time where N is the number of pixels in the haystack and M is the number of pixels in the Needle.

Given the Haystack is size (S,T) and the Needle Bitmap is size (U,V), you can iterate over Haystack with X=[0,S-U) & Y=[0,T-V). For each location, you can look at a 2D sub-array the same size as the Needle [{X,Y},{X+U,Y+V}) and compare it to the Needle [{0,0},{U,V}) coordinates.

Answer 2

You might want to look at "edge detection" the generic term for what you are trying to do.

These two links look useful, but deal more with the color registration than the image processing:

1. Codeproject: Edge Detection
2. Edge Detection in C#

the gist of what you want to do is:

1. Cut the "find" image down to the minimal size
2. Invert the "find" image and ensure that the edges are as clean (have high gradients) as possible
3. Scan the "target" image and detect all edges
4. Subdivide the "target" image into sections of "find" size (plus some error) and only take the regions where there are a high number of edges
5. Foreach section in the "target" XOR the "find" image on the section (incrementing as needed) and see if the resulting threshold is lower than your detected threshold

So the basics are you clip your "find" image, invert it (for the XOR later), find all the edges in your target image then apply the XOR map to those regions and find the highest match percentage.

Alternatively if the images are small enough, you can "slide" apply the same technique, invert the find image, and slide it across the "target" image looking for the match.

The main problem with these techniques is what constitutes a "match", it usually wont be a 100% match and you have to have some code to deal with when that happens.

If you need to do this, I do recommend finding a library that already does this, such as what Reed suggested. If you want to roll your own, spend some time on Wikipedia and Codeproject looking at image manipulation libraries.