patterncsharpModerate

Find a bitmap within another bitmap

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

withinbitmapanotherfind

Problem

I have a function that will try to find a bitmap within another bitmap.

If it successfully finds it, then it will return the center point of bitmap #1.

I've only seen negativity towards goto which is what this function relies on.

I would like some help optimizing my function and possibly having it work without the need of goto.

private static bool FindBitmap(Bitmap searchBitmap, Bitmap withinBitmap, out Point point)
{
    for (var outerX = 0; outerX < withinBitmap.Width - searchBitmap.Width; outerX++)
    {
        for (var outerY = 0; outerY < withinBitmap.Height - searchBitmap.Height; outerY++)
        {
            for (var innerX = 0; innerX < searchBitmap.Width; innerX++)
            {
                for (var innerY = 0; innerY < searchBitmap.Height; innerY++)
                {
                    var searchColor = searchBitmap.GetPixel(innerX, innerY);
                    var withinColor = withinBitmap.GetPixel(outerX + innerX, outerY + innerY);

                    if (searchColor.R != withinColor.R || searchColor.G != withinColor.G ||
                        searchColor.B != withinColor.B)
                    {
                        goto NotFound;
                    }
                }
            }
            point = new Point(outerX, outerY);
            point.X += searchBitmap.Width / 2; // Set X to the middle of the bitmap.
            point.Y += searchBitmap.Height / 2; // Set Y to the center of the bitmap.
            return true;

            NotFound:
            continue;
        }
    }
    point = Point.Empty;
    return false;
}

Solution

Accessing the Pixels

GetPixel() is notoriously slow for iterating through the whole bitmap. Consider using LockBits for accessing the pixels directly in memory. After making sure the alpha channel is the same on both bitmaps (should be automatically unless one of the images is transparent), simply compare integer values for each pixel instead of manually comparing R then G then B.

Improving the Search

I would also adopt a faster algorithm for doing the search: Take the first line of the second bitmap (needle) and check on which lines of the first bitmap (haystack) that line is matching. Afterwards, simply check if all the other lines of the needle are placed immediately below the first one => much less comparisons to perform.

Return value

Returning a bool only to request another value be passed as an out parameter is troublesome. Simply return the Point you found wrapped inside Nullable<> or null if the search returned nothing. Also, I would rather have the function return the top of bottom left corner of where the second image was found so that I can perform some operation using that coordinate instead of getting the center point with which I do little without extracting the corner anyway.

Sample Code

Here is an example code of the idea presented:

public Point? Find(Bitmap haystack, Bitmap needle)
{
    if (null == haystack || null == needle)
    {
        return null;
    }
    if (haystack.Width  FindMatch(IEnumerable haystackLines, int[] needleLine)
{
    var y = 0;
    foreach (var haystackLine in haystackLines)
    {
        for (int x = 0, n = haystackLine.Length - needleLine.Length; x < n; ++x)
        {
            if (ContainSameElements(haystackLine, x, needleLine, 0, needleLine.Length))
            {
                yield return new Point(x, y);
            }
        }
        y += 1;
    }
}

private bool ContainSameElements(int[] first, int firstStart, int[] second, int secondStart, int length)
{
    for (int i = 0; i < length; ++i)
    {
        if (first[i + firstStart] != second[i + secondStart])
        {
            return false;
        }
    }
    return true;
}

private bool IsNeedlePresentAtLocation(int[][] haystack, int[][] needle, Point point, int alreadyVerified)
{
    //we already know that "alreadyVerified" lines already match, so skip them
    for (int y = alreadyVerified; y < needle.Length; ++y)
    {
        if ( ! ContainSameElements(haystack[y + point.Y], point.X, needle[y], 0, needle.Length))
        {
            return false;
        }
    }
    return true;
}

I've also done a benchmark for finding a 246x228 pixel needle located at (169, 281) in an 800x600 pixel haystack:

Optimized method: ~ 11 ms

Initial method: ~ 261 ms

Code Snippets

public Point? Find(Bitmap haystack, Bitmap needle)
{
    if (null == haystack || null == needle)
    {
        return null;
    }
    if (haystack.Width < needle.Width || haystack.Height < needle.Height)
    {
        return null;
    }

    var haystackArray = GetPixelArray(haystack);
    var needleArray = GetPixelArray(needle);

    foreach (var firstLineMatchPoint in FindMatch(haystackArray.Take(haystack.Height - needle.Height), needleArray[0]))
    {
        if (IsNeedlePresentAtLocation(haystackArray, needleArray, firstLineMatchPoint, 1))
        {
            return firstLineMatchPoint;
        }
    }

    return null;
}

private int[][] GetPixelArray(Bitmap bitmap)
{
    var result = new int[bitmap.Height][];
    var bitmapData = bitmap.LockBits(new Rectangle(0, 0, bitmap.Width, bitmap.Height), ImageLockMode.ReadOnly,
        PixelFormat.Format32bppArgb);

    for (int y = 0; y < bitmap.Height; ++y)
    {
        result[y] = new int[bitmap.Width];
        Marshal.Copy(bitmapData.Scan0 + y*bitmapData.Stride, result[y], 0, result[y].Length);
    }

    bitmap.UnlockBits(bitmapData);

    return result;
}

private IEnumerable<Point> FindMatch(IEnumerable<int[]> haystackLines, int[] needleLine)
{
    var y = 0;
    foreach (var haystackLine in haystackLines)
    {
        for (int x = 0, n = haystackLine.Length - needleLine.Length; x < n; ++x)
        {
            if (ContainSameElements(haystackLine, x, needleLine, 0, needleLine.Length))
            {
                yield return new Point(x, y);
            }
        }
        y += 1;
    }
}

private bool ContainSameElements(int[] first, int firstStart, int[] second, int secondStart, int length)
{
    for (int i = 0; i < length; ++i)
    {
        if (first[i + firstStart] != second[i + secondStart])
        {
            return false;
        }
    }
    return true;
}

private bool IsNeedlePresentAtLocation(int[][] haystack, int[][] needle, Point point, int alreadyVerified)
{
    //we already know that "alreadyVerified" lines already match, so skip them
    for (int y = alreadyVerified; y < needle.Length; ++y)
    {
        if ( ! ContainSameElements(haystack[y + point.Y], point.X, needle[y], 0, needle.Length))
        {
            return false;
        }
    }
    return true;
}

Context

StackExchange Code Review Q#138011, answer score: 16

Revisions (0)

No revisions yet.