Introduction
Several days ago, I was trying to find a way to locate a small Bitmap
that I knew was contained in another, bigger Bitmap
. I found methods on the Internet used to transform a Bitmap
, to filter it, to resize/resample... but not what I needed.
After asking for some help here in CodeProject, I learnt how to go through a Bitmap
using LockBits()
(instead of the GetPixel()
and SetPixel()
methods, which are much slower), thanks to this article from Christian Graus, and finally, I could make my own (basic) algorithm to perform this search.
Comments, bug reports, and suggestions to improve performance will be highly appreciated since this is my first article here. Thanks to Basiuk for his bug report (the code is already updated to fix it), and to TF_Productions for his suggestions, all of which I hope I could implement in a future.
Background
Nothing special, I think.
Using the code
If you want to use it in your application, you only need the searchBitmap()
method:
private Rectangle searchBitmap(Bitmap smallBmp, Bitmap bigBmp, double tolerance)
{
BitmapData smallData =
smallBmp.LockBits(new Rectangle(0, 0, smallBmp.Width, smallBmp.Height),
System.Drawing.Imaging.ImageLockMode.ReadOnly,
System.Drawing.Imaging.PixelFormat.Format24bppRgb);
BitmapData bigData =
bigBmp.LockBits(new Rectangle(0, 0, bigBmp.Width, bigBmp.Height),
System.Drawing.Imaging.ImageLockMode.ReadOnly,
System.Drawing.Imaging.PixelFormat.Format24bppRgb);
int smallStride = smallData.Stride;
int bigStride = bigData.Stride;
int bigWidth = bigBmp.Width;
int bigHeight = bigBmp.Height - smallBmp.Height + 1;
int smallWidth = smallBmp.Width * 3;
int smallHeight = smallBmp.Height;
Rectangle location = Rectangle.Empty;
int margin = Convert.ToInt32(255.0 * tolerance);
unsafe
{
byte* pSmall = (byte*)(void*)smallData.Scan0;
byte* pBig = (byte*)(void*)bigData.Scan0;
int smallOffset = smallStride - smallBmp.Width * 3;
int bigOffset = bigStride - bigBmp.Width * 3;
bool matchFound = true;
for (int y = 0; y < bigHeight; y++)
{
for (int x = 0; x < bigWidth; x++)
{
byte* pBigBackup = pBig;
byte* pSmallBackup = pSmall;
for (int i = 0; i < smallHeight; i++)
{
int j = 0;
matchFound = true;
for (j = 0; j < smallWidth; j++)
{
int inf = pBig[0] - margin;
int sup = pBig[0] + margin;
if (sup < pSmall[0] || inf > pSmall[0])
{
matchFound = false;
break;
}
pBig++;
pSmall++;
}
if (!matchFound) break;
pSmall = pSmallBackup;
pBig = pBigBackup;
pSmall += smallStride * (1 + i);
pBig += bigStride * (1 + i);
}
if (matchFound)
{
location.X = x;
location.Y = y;
location.Width = smallBmp.Width;
location.Height = smallBmp.Height;
break;
}
else
{
pBig = pBigBackup;
pSmall = pSmallBackup;
pBig += 3;
}
}
if (matchFound) break;
pBig += bigOffset;
}
}
bigBmp.UnlockBits(bigData);
smallBmp.UnlockBits(smallData);
return location;
}
It receives two Bitmap
s (the smaller one and the bigger one), and the tolerance that should apply when searching (0.0 meaning exact match). It returns a Rectangle
with the location of the smaller image within the bigger one.
If no match is found, the width and the height of the Rectangle
will be zero:
Rectangle location = searchBitmap(bitmap1, bitmap2, tolerance);
if (location.Width != 0)
{
}
Understanding the code
First of all, you should read the above mentioned article from Christian Graus.
What a Bitmap is for us
The key is that you must understand that a Bitmap
is no longer an object with pixels ordered in columns and rows, but a series of bytes in your computer memory. A "row" of three pixels of a Bitmap
could be seen as, for example, these bytes:
255 0 0 | 0 255 0 | 0 0 255 | X ... X
What we have is:
- Three bytes per pixel, each one for one color component of the pixel. The order of the bytes is BGR (blue component, green component, red component), due to the fact that
PixelFormat.Format24bppRgb
shows BGR instead of RGB.
- The first pixel is BLUE in our example.
- The second pixel is GREEN in our example.
- And, the third and last pixel is RED in our example.
They are followed by a variable number of bytes "X ... X", which I have named "offset" in the code, and are used for padding. We are not interested in their contents. You can see how the offset is calculated in the famous article from Christian Graus.
If we had a bitmap with two rows, these would be seen as follows:
255 0 0 | 0 255 0 | 0 0 255 | X ... X | 192 0 192 | 128 128 0 | 0 0 128 | X ... X
So, if we are looking at one "pixel" and want to go to the next row, what we need to do is move forward 9 bytes (3 bytes per pixel, 3 pixels per row) plus the offset. It is done in the following line of code:
pBig += bigStride * (1 + i);
which is equivalent to:
pBig += (bigWidth * 3 + bigOffset) * (1 + i);
Of course, if you want to move to the next pixel, you must move forward 3 bytes (or the offset, if you are at the last pixel of a row):
pBig += 3;
pBig += bigOffset;
The algorithm
Once the previous point is understood, I think the rest is pretty self-explanatory:
- The method goes through the bigger
Bitmap
, "row" by "row", searching for "pixels" that match those of the first "row" of the smaller Bitmap
.
- When a match is found, we go to the next "row" of the bigger
Bitmap
and the next "row" of the smaller one (still staying at the same "columns"), and compare them.
- If they're not equal (considering the tolerance), we restore the pointers and continue searching from where we are.
- If they're equal (considering the tolerance), we repeat step 2 until we have compared all the "rows" of the smaller
Bitmap
. At that point, if we have a match, we return the corresponding Rectangle
.
Sample application
The application is very simple: you choose two bitmaps, choose the tolerance level, and press the "Search" button.
The output will be the Rectangle
in which the smaller Bitmap
is located inside the bigger one.
The "Auto" check can be useful: it starts searching with tolerance = 0 (exact match), and increases it in a loop, searching again and again until a match is found or the maximum tolerance is reached. Note that, with bigger tolerances, the time increases.
If you want to search only for an exact match, use tolerance = 0.0.
When to use and when not
The above method is useful for finding a small Bitmap
(like an icon or a button) inside a bigger one (like a window capture). If you look for exact matches or use low tolerances, you can get the output in a few milliseconds (15-30 ms.), which is much faster than using algorithms with the GetPixel()
and SetPixel()
methods.
The problem is when you want to look for a big Bitmap
contained in a huge Bitmap
. The time increases a lot with the size of the images, so be careful choosing the images and the tolerance.
History
- 31.07.2009 - Posted (first version).
- 10.03.2010 - Updated source code.