Finding a Bitmap contained inside another Bitmap

• Download source code - 12.6 KB

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;

                //Look for the small picture.
                for (int i = 0; i < smallHeight; i++)
                {
                    int j = 0;
                    matchFound = true;
                    for (j = 0; j < smallWidth; j++)
                    {
                        //With tolerance: pSmall value should be between margins.
                        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;

                    //We restore the pointers.
                    pSmall = pSmallBackup;
                    pBig = pBigBackup;

                    //Next rows of the small and big pictures.
                    pSmall += smallStride * (1 + i);
                    pBig += bigStride * (1 + i);
                }

                //If match found, we return.
                if (matchFound)
                {
                    location.X = x;
                    location.Y = y;
                    location.Width = smallBmp.Width;
                    location.Height = smallBmp.Height;
                    break;
                }
                //If no match found, we restore the pointers and continue.
                else
                {
                    pBig = pBigBackup;
                    pSmall = pSmallBackup;
                    pBig += 3;
                }
            }

            if (matchFound) break;

            pBig += bigOffset;
        }
    }

    bigBmp.UnlockBits(bigData);
    smallBmp.UnlockBits(smallData);

    return location;
}

It receives two Bitmaps (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)
{
     //Do something.
}

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:

1. The method goes through the bigger Bitmap, "row" by "row", searching for "pixels" that match those of the first "row" of the smaller Bitmap.
2. 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.
3. If they're not equal (considering the tolerance), we restore the pointers and continue searching from where we are.
4. 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.