查找包含在另一个位图中的位图

• 下载源代码 - 12.6 KB

引言

几天前，我正在尝试寻找一种方法来定位一个我已知的包含在另一个较大 Bitmap 中的较小 Bitmap。我在网上找到了一些用于转换 Bitmap、过滤它、调整大小/重新采样的方法……但不是我需要的。

在 CodeProject 这里寻求帮助后，我学会了如何使用 LockBits()（而不是慢得多的 GetPixel() 和 SetPixel() 方法）遍历 Bitmap，这要归功于 Christian Graus 的这篇文章，最终，我能够编写自己的（基本的）算法来执行此搜索。

非常感谢您的评论、错误报告和提高性能的建议，因为这是我在这里的第一篇文章。感谢 Basiuk 的 错误报告（代码已更新以修复它），以及 TF_Productions 的 建议，我希望我能在未来实现它们。

背景

我认为没有什么特别的。

使用代码

如果您想在您的应用程序中使用它，您只需要 searchBitmap() 方法

private Rectangle searchBitmap(Bitmap smallBmp, Bitmap bigBmp, double tolerance)
{
    BitmapData smallData = 
      smallBmp.LockBits(new Rectangle(0, 0, smallBmp.Width, smallBmp.Height), 
               System.Drawing.Imaging.ImageLockMode.ReadOnly, 
               System.Drawing.Imaging.PixelFormat.Format24bppRgb);
    BitmapData bigData = 
      bigBmp.LockBits(new Rectangle(0, 0, bigBmp.Width, bigBmp.Height), 
               System.Drawing.Imaging.ImageLockMode.ReadOnly, 
               System.Drawing.Imaging.PixelFormat.Format24bppRgb);

    int smallStride = smallData.Stride;
    int bigStride = bigData.Stride;

    int bigWidth = bigBmp.Width;
    int bigHeight = bigBmp.Height - smallBmp.Height + 1;
    int smallWidth = smallBmp.Width * 3;
    int smallHeight = smallBmp.Height;

    Rectangle location = Rectangle.Empty;
    int margin = Convert.ToInt32(255.0 * tolerance);

    unsafe
    {
        byte* pSmall = (byte*)(void*)smallData.Scan0;
        byte* pBig = (byte*)(void*)bigData.Scan0;

        int smallOffset = smallStride - smallBmp.Width * 3;
        int bigOffset = bigStride - bigBmp.Width * 3;

        bool matchFound = true;

        for (int y = 0; y < bigHeight; y++)
        {
            for (int x = 0; x < bigWidth; x++)
            {
                byte* pBigBackup = pBig;
                byte* pSmallBackup = pSmall;

                //Look for the small picture.
                for (int i = 0; i < smallHeight; i++)
                {
                    int j = 0;
                    matchFound = true;
                    for (j = 0; j < smallWidth; j++)
                    {
                        //With tolerance: pSmall value should be between margins.
                        int inf = pBig[0] - margin;
                        int sup = pBig[0] + margin;
                        if (sup < pSmall[0] || inf > pSmall[0])
                        {
                            matchFound = false;
                            break;
                        }

                        pBig++;
                        pSmall++;
                    }

                    if (!matchFound) break;

                    //We restore the pointers.
                    pSmall = pSmallBackup;
                    pBig = pBigBackup;

                    //Next rows of the small and big pictures.
                    pSmall += smallStride * (1 + i);
                    pBig += bigStride * (1 + i);
                }

                //If match found, we return.
                if (matchFound)
                {
                    location.X = x;
                    location.Y = y;
                    location.Width = smallBmp.Width;
                    location.Height = smallBmp.Height;
                    break;
                }
                //If no match found, we restore the pointers and continue.
                else
                {
                    pBig = pBigBackup;
                    pSmall = pSmallBackup;
                    pBig += 3;
                }
            }

            if (matchFound) break;

            pBig += bigOffset;
        }
    }

    bigBmp.UnlockBits(bigData);
    smallBmp.UnlockBits(smallData);

    return location;
}

它接收两个 Bitmap（较小的一个和较大的一个），以及搜索时应应用的容差（0.0 表示精确匹配）。它返回一个 Rectangle，其中包含较小图像在较大图像中的位置。

如果未找到匹配项，Rectangle 的宽度和高度将为零

Rectangle location = searchBitmap(bitmap1, bitmap2, tolerance);
if (location.Width != 0)
{
     //Do something.
}

理解代码

首先，您应该阅读上面提到的 Christian Graus 的文章。

Bitmap 对我们来说意味着什么

关键在于您必须明白，Bitmap 不再是一个像素按列和行排序的对象，而是计算机内存中的一系列字节。Bitmap 的一个“行”三个像素可能被看作是，例如，这些字节

255 0 0 | 0 255 0 | 0 0 255 | X ... X

我们拥有的是

• 每个像素三个字节，每个字节代表像素的一个颜色分量。字节的顺序是 BGR（蓝色分量、绿色分量、红色分量），因为 PixelFormat.Format24bppRgb 显示的是 BGR 而不是 RGB。
• 在我们的例子中，第一个像素是蓝色。
• 在我们的例子中，第二个像素是绿色。
• 在我们的例子中，第三个也是最后一个像素是红色。

它们后面跟着可变数量的字节“X ... X”，我在代码中将其命名为“offset”（偏移量），用于填充。我们不关心它们的内容。您可以在 Christian Graus 的著名文章 中看到偏移量的计算方法。

如果我们有一个包含两行的位图，它们将被视为如下：

255 0 0 | 0 255 0 | 0 0 255 | X ... X | 192 0 192 | 128 128 0 | 0 0 128 | X ... X

所以，如果我们查看一个“像素”并想转到下一行，我们需要做的是向前移动 9 个字节（每个像素 3 个字节，每行 3 个像素）加上偏移量。这在以下代码行中完成：

pBig += bigStride * (1 + i);

这相当于

pBig += (bigWidth * 3 + bigOffset) * (1 + i);

当然，如果您想移动到下一个像素，您必须向前移动 3 个字节（或者偏移量，如果您处于一行的最后一个像素）。

pBig += 3;
pBig += bigOffset;

算法

一旦前面的点被理解，我认为其余的就很容易理解了。

1. 该方法遍历较大的 Bitmap，“逐行”搜索与较小 Bitmap 第一“行”像素匹配的“像素”。
2. 当找到匹配项时，我们转到较大 Bitmap 的下一“行”和较小 Bitmap 的下一“行”（仍然保持在相同的“列”），然后进行比较。
3. 如果它们不相等（考虑到容差），我们会恢复指针并从当前位置继续搜索。
4. 如果它们相等（考虑到容差），我们会重复步骤 2，直到比较完较小 Bitmap 的所有“行”。此时，如果找到匹配项，我们将返回相应的 Rectangle。

示例应用程序

应用程序非常简单：您选择两个位图，选择容差级别，然后按“搜索”按钮。

输出将是较小的 Bitmap 在较大的 Bitmap 中找到的 Rectangle。

“自动”复选框可能很有用：它从容差 = 0（精确匹配）开始搜索，然后在一个循环中递增容差，反复搜索，直到找到匹配项或达到最大容差。请注意，随着容差增大，时间也会增加。

如果您只想搜索精确匹配，请使用容差 = 0.0。

何时使用和何时不使用

上述方法对于在较大的位图（如窗口捕获）中查找较小的位图（如图标或按钮）很有用。如果您搜索精确匹配或使用低容差，您可以在几毫秒内（15-30 毫秒）获得输出，这比使用具有 GetPixel() 和 SetPixel() 方法的算法快得多。

问题在于，当您想在巨大的 Bitmap 中查找较大的 Bitmap 时。时间会随着图像大小而大大增加，因此请谨慎选择图像和容差。

历史

• 2009 年 7 月 31 日 - 发布（第一版）。
• 2010 年 3 月 10 日 - 更新源代码。