Find a bitmap within another bitmap

Question

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;
}

Answer 1

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 < 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;
}

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

Answer 2

The following solution does essentially the same as yours but maybe in a more clearer way, and it avoids the by many disliked goto-statement.

private static bool IsInnerImage(Bitmap searchBitmap, Bitmap withinBitmap, int left, int top)
{
  for (int y = top; y < top + withinBitmap.Height; y++)
  {
    for (int x = left; x < left + withinBitmap.Width; x++)
    {
      if (searchBitmap.GetPixel(x, y) != withinBitmap.GetPixel(x - left, y - top))
        return false;
    }
  }

  return true;
}

private static bool FindBitmap(Bitmap searchBitmap, Bitmap withinBitmap, out Point point)
{
  Color innerTopLeft = withinBitmap.GetPixel(0, 0);

  for (int y = 0; y < searchBitmap.Height - withinBitmap.Height; y++)
  {
    for (int x = 0; x < searchBitmap.Width - withinBitmap.Width; x++)
    {
      Color clr = searchBitmap.GetPixel(x, y);
      if (innerTopLeft == clr && IsInnerImage(searchBitmap, withinBitmap, x, y))
      {
        point = new Point(x, y); // Top left corner of the inner bitmap in searchBitmap - coordinates
        return true;
      }
    }
  }

  point = Point.Empty;
  return false;
}

Answer 3

Your code is using GetPixel() for accessing individual pixels in the bitmap. I find that this approach not suitable to image processing as it too slow.

c# allows to access the raw memory of bitmap data via pointers. My benchmarks shows that using this approach improve the speed by 80%. see Fast image processing in c# for more details.