# 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.

# 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)

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:

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

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.

• Your code looks great, do you happen to have a usage example with your code?
– Mast
May 27 at 16:49
• What version of .NET the project is targeting? May 27 at 22:02
• Currently it is targeting .NET 4.7.2. I will supply a usage example after the weekend. May 29 at 23:20
• 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. Jun 9 at 5:15
• 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. Jun 19 at 13:52