4
\$\begingroup\$

Background

I am creating a tool to locate a small bitmap in a large bitmap by comparing each pixel. Since I am by far no professional programmer, I was searching for some code snippets and found this. The code from the link uses pointers and requires therefor the “unsafe” keyword and is working perfectly. With the usage of the “unsafe” keyword some virus scanners (incl. Windows Defender) is ringing all alarm bells. While this is no problem when executing the program on my computer since I can trust myself, it is a big issue when sending out the program to friends etc.

Report from VirusTotal.com

My solution, step by step (if anyone like me is looking for a detailed How-To)

I decided to write my own method for that without using “unsafe” content. Trying to explain my logic:

The following image is only for visualization and for better understanding. My method should return the upper left corner of the found "smallBitmap" within the "largeBitmap" (5,5)

Simplified images

The bitmaps are located on local storage, so handling and loading them is no issue.

At first I am converting each bitmap to a byte[] that contains the RGB values for each pixel. I also got pretty confused about the fact that the values are stored in BGR order.

private byte[] GetPixelData(Bitmap bitmap)
{
    BitmapData bitmapData = bitmap.LockBits(new Rectangle(0, 0, bitmap.Width, bitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);
    byte[] bytes = new byte[bitmap.Width * bitmap.Height * 3];
    for (int y = 0; y < bitmap.Height; ++y)
    {
        IntPtr mem = (IntPtr)((long)bitmapData.Scan0 + y * bitmapData.Stride);
        Marshal.Copy(mem, bytes, y * bitmapData.Width * 3, bitmapData.Width * 3);
    }
    bitmap.UnlockBits(bitmapData);
    return bytes;
}

I learned pretty quick, that you have to write the bytes for each line of the bitmap, otherwise you end up writing all the padding values, since: "The size of each row is rounded up to a multiple of 4 bytes (a 32-bit DWORD) by padding." (Thanks Wikipedia!)

The resulting byte[] for the small bitmap looks like this: Small Bitmap

The resulting byte[] for the large bitmap looks like this (only the relevant part): Large Bitmap

The following code is the method itself.

public void LocateBitmap(Bitmap smallBmp, Bitmap largeBmp, byte tol)
{
    byte[] small = GetPixelData(smallBmp);
    byte[] large = GetPixelData(largeBmp);

    for (int i = 0; i < large.Length; i += 3)
    {
        if (large[i] == small[0] && large[i + 1] == small[1] && large[i + 2] == small[2])
        {
            // The first similar pixel has been found, now iterate through all pixels of the small bitmap and compare them to the large bitmap
            int ii = 0;
            bool found = true;

            for (int j = 0; j < small.Length; j += 3)
            {
                // Calculate 2d position for the calculation of the relative position in the large bitmap
                int row = j / 3 / smallBmp.Width;
                int column = j / 3 % smallBmp.Width;

                // Offset the index accordingly
                ii = i + largeBmp.Width * 3 * row + column * 3;

                // Read each RGB value for easier debugging
                byte largeR = large[ii + 2];
                byte largeG = large[ii + 1];
                byte largeB = large[ii + 0];
                byte smallR = small[j  + 2]; 
                byte smallG = small[j  + 1];
                byte smallB = small[j  + 0];

                if (!IsInRange(largeR, smallR, tol) || !IsInRange(largeG, smallG, tol) || !IsInRange(largeB, smallB, tol))
                {
                    // If they are not equal, break the loop since it cannot be the small image
                    found = false;
                    break;
                }
            }

            if (found)
            {
                int coordsX = i / 3 % largeBmp.Width;
                int coordsY = i / 3 / largeBmp.Width;
                Console.WriteLine($"Bitmap found at {ii} --> {coordsX}|{coordsY}");
            }
        }
    }
}

private bool IsInRange(byte a, byte b, byte tol)
{
    if (a >= b - tol && a <= b + tol)
        return true;

    return false;
}

How would you optimize the method?

I know that you can get rid of some variables like largeR, but I would like to know how you would optimize these methods performance / execution time wise.

\$\endgroup\$
5
  • \$\begingroup\$ Your code looks great, do you happen to have a usage example with your code? \$\endgroup\$
    – Mast
    May 27 at 16:49
  • \$\begingroup\$ What version of .NET the project is targeting? \$\endgroup\$
    – aepot
    May 27 at 22:02
  • \$\begingroup\$ Currently it is targeting .NET 4.7.2. I will supply a usage example after the weekend. \$\endgroup\$
    – Hanebu
    May 29 at 23:20
  • \$\begingroup\$ I made a small page on GitHub that explain the usage of the code above. This tool is a small helper for the Ultima Online Freeshard called UO Outlands. \$\endgroup\$
    – Hanebu
    Jun 9 at 5:15
  • \$\begingroup\$ In 4.7.2 you have no such cool apis as Span<T> or ReadOnlySpan<T>. Then only unsafe code can help to speed up the code. Btw, here's some code for example. \$\endgroup\$
    – aepot
    Jun 19 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.