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

Question

Hi,

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

You can do this via Image Registration, though I don't know of a (good) .NET library usable directly for this.

If you're willing to use C++, the Insight Toolkit has many tools that will help you do this, including the ability for your "haystack" to not precisely match the "needle" (ie: "fuzzy" searching/matching).

Answer 2

I'm by no means an expert in image processing. Just toying around with an idea out of my head here :)

Say you look at a line of pixels in your needle. This line could provide a base for calculating a checksum for the given line, so let's call it a fingerprint. Now you could search all horizontal lines in the haystack for subsets of the same length with the same checksum. Once you've found your horizontal candidates, you can check each for a vertical match.

Problem with this algorithm is clearly the speed of it. It's O(Scary) in cases where you'll have a lot of matches on your horizontal fingerprint (for example, if you chose the top line, it would be all blacks - A pattern that's shown a lot in the haystack), so somehow you have to choose a fingerprint with a nice, distinct behavior.

I'm sure there's a lot of better ways to do it, but I thought I'd share my thoughts :)

Good luck

Answer 3

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.

Answer 4

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.