here are some ideas, trying not to use much extra memory:
I will assume the small bitmap "bmSmall" indeed is an exact subset of the larger one, no rescales, no resampling, no color shifts; I will also assume lots of different colors are present, and there is exactly one match (so no checker board situations, and preferably real pictures, not synthetic ones)
if bmSmall had a single pixel in a very particular color C1, then all it would take is scan the large bitmap bmLarge for C1. If only one is found, that must be it. If multiple, each is a candidate, now check other pixels at some distance (dx,dy) from the matching one.
Q: how to find C1?
A: I don't recommend histogramming 32-bit colors, so I would suggest hashing the colors to a smaller number (I would prefer 12 bits, maybe 8 works well enough, say B bits) and then histogramming those, by counting their occurence in an array of size 2^B). This takes a single scan of the bmSmall.
Q: What hashing function?
A: A fast one; if going for 8-bit result XOR red,green,blue,alpha (or add ignoring overflow); if going for 12-bit, add red,green,blue,alpha (that's 10 bits actually). And not a real method, just one line of inline code!
Now scan the bmLarge, comparing each pixel with C1; on a match perform a full bitmap compare, don't do that in the classic order though, step through rows and columns in a smart way, say
x=(x+prime) modulo width, and
y=(y+prime) modulo height, so you aren't first checking all adjacent pixels and probability increases you don't get caught by a part of the bitmaps locally being identical.
[EDIT] Make sure the primes don't evenly divide width or height [/EDIT]
6a. a second special color
- while histogramming, build a second array of size 2^B, holding the last Point found with that color.
- choose a second color C2, the next most special color in bmSmall, and calculate the distance DIST from the last C1 pixel to the last C2 pixel
- now when a C1 match is found at pointLarge1, go check for C2 at pointLarge1+DIST
that reduces the probability of an accidental match
6b. ignore part of bmLarge while searching for C1
assuming one of the C1 pixels in bmSmall is at (x1,y1) there are four rectangles in bmLarge that you don't need to scan for C1: the regions where x<x1, or x>bmLargeWidth-(bmSmallWidth-x1), or similar for y.
instead of using a second color C2, use C1 again, however build two arrays, one for first location, the other for last location (same memory cost, lower probability of a false hit, and bigger effect of 6b!)
Alternative strategy, using more memory; less dependent on image reality, would work for synthetics too.
However expected to be a lot slower.
perform some transformation, both on bmSmall and bmLarge; the goal is to reduce their memory size so they become a smaller bmSmall2 and bmLarge2.
Example: replace 32-bit pixels by 8-bit pixels, using a hashing like before
with 1 byte/pixel, you can still address pixels easily, and either do a direct compare (nested loops), or apply the former strategy
Extreme case: hash to a single bit per pixel (just store the least significant bit of the earlier hash);
with less than 1 byte/pixel the problem is bmSmall2 and bmLarge2 may have different byte boundaries (say bmSmall is located at bmLarge offset 7, anything but a multiple of 8)
store 8 copies of bmSmall2, each shifted over 1 more pixel; now search for exact matches between those bmSmall2 and the one bmLarge2
minor problem: bmSmall2 and its shifted versions would have wrong boundary pixels (horizontally only), they would never match bmLarge2. Hence reduce width a bit so each bit is real pixel information.
That's it for now. Let us know what you decide and how it works out.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.