Search for a bitmap in another bitmap with indentation and return coordinates

Question

i found a perfectly working function but can't figure out how to add search indentation:

        public static bool FindBitmap(Bitmap bmpNeedle, Bitmap bmpHaystack, out Point location)
        {
            if (bmpNeedle == null || bmpHaystack == null)
            {
                location = new Point();
                return false;
            }
            for (int outerX = 0; outerX < bmpHaystack.Width - bmpNeedle.Width; outerX++)
            {
                for (int outerY = 0; outerY < bmpHaystack.Height - bmpNeedle.Height; outerY++)
                {
                    for (int innerX = 0; innerX < bmpNeedle.Width; innerX++)
                    {
                        for (int innerY = 0; innerY < bmpNeedle.Height; innerY++)
                        {
                            Color cNeedle = bmpNeedle.GetPixel(innerX, innerY);
                            Color cHaystack = bmpHaystack.GetPixel(innerX + outerX, innerY + outerY);

                            if (cNeedle.R != cHaystack.R || cNeedle.G != cHaystack.G || cNeedle.B != cHaystack.B)
                            {
                                goto notFound;
                            }
                        }
                    }
                    location = new Point(outerX, outerY);
                    return true;
                notFound:
                continue;
                }
            }
            location = Point.Empty;
            return false;
        }

I modified the function by adding the variables xFrom and yFrom public static bool FindBitmap(Bitmap bmpNeedle, Bitmap bmpHaystack, out Point location, int xFrom, int yFrom)

And set the initial values of the counters: outerX and outerY

But it doesn't work. I don’t understand how I can modify the function.

Answer 1

I have modified your code so that you can have search indentation:

public static bool FindBitmap(Bitmap bmpNeedle, Bitmap bmpHaystack, out Point location, int startX, int startY)
    {
        if (bmpNeedle == null || bmpHaystack == null)
        {
            location = new Point();
            return false;
        }
        for (int outerX = startX; outerX < bmpHaystack.Width - bmpNeedle.Width; outerX++)
        {
            for (int outerY = startY; outerY < bmpHaystack.Height - bmpNeedle.Height; outerY++)
            {
                for (int innerX = 0; innerX < bmpNeedle.Width; innerX++)
                {
                    for (int innerY = 0; innerY < bmpNeedle.Height; innerY++)
                    {
                        Color cNeedle = bmpNeedle.GetPixel(innerX, innerY);
                        Color cHaystack = bmpHaystack.GetPixel(innerX + outerX, innerY + outerY);

                        if (cNeedle.R != cHaystack.R || cNeedle.G != cHaystack.G || cNeedle.B != cHaystack.B)
                        {
                            goto notFound;
                        }
                    }
                }
                location = new Point(outerX, outerY);
                return true;
            notFound:;
            }
        }
        location = Point.Empty;
        return false;
    }

Answer 2

Let's start with a fully working solution, which uses your function that you provided as-is:

Bitmap fullImage = (Bitmap)Bitmap.FromFile(@"G:\large.png");
Bitmap smallImage = (Bitmap)Bitmap.FromFile(@"G:\small.png");

if (FindBitmap(smallImage, fullImage, out Point location))
{
    Console.WriteLine($"Found small image embedded at {location}");
}
else
{
    Console.WriteLine("Couldn't find small image embedded in larger image.");
}

I ran this with some sample data and was able to find the embedded image. In my sample my embedded image is at {X=88,Y=74}, and it takes about 330k ticks on my CPU to find this location. Now, the question is how to modify your original function to supply bounds on the search space. As you suggested, you could set an initial x and y position, provided as a guess or indentation, to your function.

public static bool FindBitmap(Bitmap bmpNeedle, Bitmap bmpHaystack, out Point location, int xFrom = 0, int yFrom = 0)
{
    if (bmpNeedle == null || bmpHaystack == null)
    {
        location = new Point();
        return false;
    }
    for (int outerX = xFrom; outerX < bmpHaystack.Width - bmpNeedle.Width; outerX++)
    {
        for (int outerY = yFrom; outerY < bmpHaystack.Height - bmpNeedle.Height; outerY++)
        {
            for (int innerX = 0; innerX < bmpNeedle.Width; innerX++)
            {
                for (int innerY = 0; innerY < bmpNeedle.Height; innerY++)
                {
                    Color cNeedle = bmpNeedle.GetPixel(innerX, innerY);
                    Color cHaystack = bmpHaystack.GetPixel(innerX + outerX, innerY + outerY);

                    if (cNeedle.R != cHaystack.R || cNeedle.G != cHaystack.G || cNeedle.B != cHaystack.B)
                    {
                        goto notFound;
                    }
                }
            }
            location = new Point(outerX, outerY);
            return true;
        notFound:
            continue;
        }
    }
    location = Point.Empty;
    return false;
}

Now we can call with with a better guess: if (FindBitmap(smallImage, fullImage, out Point location, 80, 70)) which returns the same value. Since the search space is reduced this now only takes 45k ticks on my machine. You could similarly add xTo and yTo values to further constraint the search space.

However, we can do better! Right now you are using GetPixel, which is notoriously non-performant. You can lock your bitmap image and get access to the pixel data directly:

public static int[] GetPixels(Bitmap image)
{
    var imageLock = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
    int[] pixels = new int[image.Width * image.Height];
    Marshal.Copy(imageLock.Scan0, pixels, 0, pixels.Length);
    image.UnlockBits(imageLock);
    return pixels;
}

Now you can grab the pixel data at the start of your search and access it directly:

public static bool FindBitmap(Bitmap bmpNeedle, Bitmap bmpHaystack, out Point location, int xFrom = 0, int yFrom = 0)
{
    if (bmpNeedle == null || bmpHaystack == null)
    {
        location = new Point();
        return false;
    }

    var needlePixels = GetPixels(bmpNeedle);
    var haystackPixels = GetPixels(bmpHaystack);

    for (int outerX = xFrom; outerX < bmpHaystack.Width - bmpNeedle.Width; outerX++)
    {
        for (int outerY = yFrom; outerY < bmpHaystack.Height - bmpNeedle.Height; outerY++)
        {
            for (int innerX = 0; innerX < bmpNeedle.Width; innerX++)
            {
                for (int innerY = 0; innerY < bmpNeedle.Height; innerY++)
                {
                    var cNeedle = needlePixels[innerX + innerY * bmpNeedle.Width];
                    var cHaystack = haystackPixels[innerX + outerX + (innerY + outerY) * bmpHaystack.Width];

                    if (cNeedle != cHaystack)
                    {
                        goto notFound;
                    }
                }
            }
            location = new Point(outerX, outerY);
            return true;
        notFound:
            continue;
        }
    }
    location = Point.Empty;
    return false;
}

This reduces the search time to 25k ticks on my hardware, and will likely pay dividends on larger searches. Lastly, you can reformat this code a bit to be (I hope) a bit more clean. Here is my suggested final method, which only takes around 15k ticks on my machine:

public static bool FindBitmap(Bitmap bmpNeedle, Bitmap bmpHaystack, out Point location, int xFrom = 0, int yFrom = 0)
{
    location = Point.Empty;

    if (bmpNeedle == null || bmpHaystack == null)
    {
        return false;
    }

    var needlePixels = GetPixels(bmpNeedle);
    var haystackPixels = GetPixels(bmpHaystack);

    for (int outerX = xFrom; outerX < bmpHaystack.Width - bmpNeedle.Width; outerX++)
    {
        for (int outerY = yFrom; outerY < bmpHaystack.Height - bmpNeedle.Height; outerY++)
        {
            if (IsMatch(needlePixels, haystackPixels, outerX, outerY, bmpNeedle.Width, bmpHaystack.Width))
            {
                location = new Point(outerX, outerY);
                return true;
            }
        }
    }

    return false;
}

public static bool IsMatch(int[] needle, int[] haystack, int x, int y, int needleWidth, int haystackWidth)
{
    for (int i = 0; i < needle.Length; i++)
    {
        var innerX = i % needleWidth;
        var innerY = i / needleWidth;
        var cNeedle = needle[i];
        var cHaystack = haystack[innerX + x + (innerY + y) * haystackWidth];
        if (cNeedle != cHaystack) return false;
    }
    return true;
}