比较两个相同大小的位图以确定它们是否相同的最快方法是什么？

Question

我正在尝试编写一个函数来确定两个相同大小的位图是否相同。我现在拥有的函数只是一次比较每个位图中的一个像素，在第一个不相等的像素处返回 false。

虽然这很有效，并且适用于小位图，但在生产中我将在紧密循环中和更大的图像上使用它，所以我需要一种更好的方法。有人有什么建议吗？

顺便说一句，我使用的语言是 C# - 是的，我已经在使用 .LockBits 方法。 =)

编辑：我已经对给出的一些建议的实现进行了编码，下面是基准。设置：两个相同的（最坏情况）位图，大小为 100x100，每个位图迭代 10,000 次。结果如下：

CompareByInts (Marc Gravell) :   1107ms
CompareByMD5  (Skilldrick)   :   4222ms
CompareByMask (GrayWizardX)  :    949ms

在 CompareByInts 和 CompareByMask 中，我使用指针直接访问内存；在 MD5 方法中，我使用 Marshal.Copy 检索字节数组并将其作为参数传递给 MD5.ComputeHash。 CompareByMask 只是稍微快一点，但考虑到上下文，我认为任何改进都是有用的。

谢谢大家。 =)

编辑 2：忘记打开优化 - 这样做会给 GrayWizardX 的答案带来更多的提升：

CompareByInts   (Marc Gravell) :    944ms
CompareByMD5    (Skilldrick)   :   4275ms
CompareByMask   (GrayWizardX)  :    630ms
CompareByMemCmp (Erik)         :    105ms

有趣的是 MD5 方法根本没有改进。

编辑3：发布了我的答案（MemCmp），它让其他方法大吃一惊。 oO

Answer 1

12 年 8 月 31 日编辑：根据下面的 Joey 的 评论，请注意您比较的位图的格式。它们可能在步幅上包含填充，导致位图不相等，尽管在像素方面是等效的。有关更多详细信息，请参阅此问题。

---

阅读关于比较字节数组的问题的这个答案已经产生了结果更快的方法：使用 P/Invoke 和 msvcrt 中的 memcmp API 调用。这是代码：

[DllImport("msvcrt.dll")]
private static extern int memcmp(IntPtr b1, IntPtr b2, long count);

public static bool CompareMemCmp(Bitmap b1, Bitmap b2)
{
    if ((b1 == null) != (b2 == null)) return false;
    if (b1.Size != b2.Size) return false;

    var bd1 = b1.LockBits(new Rectangle(new Point(0, 0), b1.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
    var bd2 = b2.LockBits(new Rectangle(new Point(0, 0), b2.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

    try
    {
        IntPtr bd1scan0 = bd1.Scan0;
        IntPtr bd2scan0 = bd2.Scan0;

        int stride = bd1.Stride;
        int len = stride * b1.Height;

        return memcmp(bd1scan0, bd2scan0, len) == 0;
    }
    finally
    {
        b1.UnlockBits(bd1);
        b2.UnlockBits(bd2);
    }
}

Answer 2

如果您试图确定它们是否 100% 相等，则可以将其中之一反转，然后将其与另一个相加（如果其为零，则它们相同）。使用不安全代码对此进行扩展，一次取 64 位作为 long，并以这种方式进行数学计算，任何差异都可能导致立即失败。

如果图像不是 100% 相同（比较 png 和 jpeg），或者如果您不是在寻找 100% 匹配，那么您还有更多工作要做。

祝你好运。

Answer 3

好吧，您正在使用 .LockBits，所以大概您正在使用不安全的代码。不要将每行原点 (Scan0 + y * Stride) 视为 byte*，而是考虑将其视为 int*； int 算术非常快，您只需要做 1/4 的工作。对于 ARGB 格式的图像，您可能仍然以像素为单位进行讨论，从而使数学变得简单。

Answer 4

你能计算每个的哈希值并进行比较吗？这有点概率性，但实际上不是。

感谢 Ram，这里提供了此技术的示例实现。

Answer 5

如果最初的问题只是找到两个位图之间的精确重复项，那么只需进行位级比较即可。我不懂 C#，但在 CI 中会使用以下函数：

int areEqual (long size, long *a, long *b)
{
    long start = size / 2;
    long i;
    for (i = start; i != size; i++) { if (a[i] != b[i]) return 0 }
    for (i = 0; i != start; i++) { if (a[i] != b[i]) return 0 }
    return 1;
}

我会开始在中间查找，因为我怀疑在图像中间附近找到不相等位的机会比在开头处要好得多；当然，这实际上取决于您要删除重复的图像，选择随机位置开始可能是最好的。

如果您试图在数百张图像中找到精确的重复项，则无需比较所有图像对。首先计算每个图像的 MD5 哈希值并将其放入 (md5Hash, imageId) 对的列表中；然后按 m5Hash 对列表进行排序。接下来，仅对具有相同 md5Hash 的图像进行两两比较。

Answer 6

如果这些位图已经在您的显卡上，那么您可以通过使用诸如 CUDA 或 OpenCL。

我会用 CUDA 来解释，因为这是我所知道的。基本上，CUDA 允许您编写通用代码以在显卡的每个节点上并行运行。您可以访问共享内存中的位图。该函数的每次调用还会在并行运行集中给出一个索引。因此，对于这样的问题，您只需对位图的某些子集运行上述比较函数之一 - 使用并行化来覆盖整个位图。然后，如果比较失败，则将 1 写入某个内存位置（如果成功，则不写入任何内容）。

如果您的显卡上还没有位图，这可能不是正确的方法，因为在卡上加载两个位图的成本很容易超过并行化为您带来的节省。

这是一些（非常糟糕的）示例代码（自从我编写 CUDA 以来已经有一段时间了）。有更好的方法来访问已经作为纹理加载的位图，但我在这里没有打扰。

// kernel to run on GPU, once per thread
__global__ void compare_bitmaps(long const * const A, long const * const B, char * const retValue, size_t const len)
{
 // divide the work equally among the threads (each thread is in a block, each block is in a grid)
 size_t const threads_per_block = blockDim.x * blockDim.y * blockDim.z;
 size_t const len_to_compare = len / (gridDim.x * gridDim.y * gridDim.z * threads_per_block);
# define offset3(idx3,dim3)  (idx3.x + dim3.x * (idx3.y + dim3.y * idx3.z))
 size_t const start_offset = len_to_compare * (offset3(threadIdx,blockDim) + threads_per_block * offset3(blockIdx,gridDim));
 size_t const stop_offset = start_offset + len_to_compare;
# undef offset3

 size_t i;
 for (i = start_offset; i < stop_offset; i++)
 {
  if (A[i] != B[i]) 
  {
   *retValue = 1;
   break;
  }
 }
 return;
}

Answer 7

如果您可以用您的语言实现类似 Duff's Device 的功能，这可能会给您带来重大帮助比简单循环速度提升。通常它用于复制数据，但没有理由不能用于比较数据。

或者，就此而言，您可能只想使用与 memcmp() 等效的东西。

Answer 8

您可以尝试将它们添加到数据库“blob”中，然后使用数据库引擎来比较它们的二进制文件。对于二进制数据是否相同，这只会给出是或否的答案。制作两个产生相同图形但具有不同二进制的图像是非常容易的。

您还可以选择一些随机像素并比较它们，如果它们相同，则继续更多，直到检查完所有像素为止。这只会返回更快的负匹配，但仍然需要很长时间才能找到 100% 正匹配

Answer 9

基于比较哈希值而不是比较每个像素的方法，这就是我使用的方法：

public static class Utils
{
    public static byte[] ShaHash(this Image image)
    {
        var bytes = new byte[1];
        bytes = (byte[])(new ImageConverter()).ConvertTo(image, bytes.GetType());

        return (new SHA256Managed()).ComputeHash(bytes);
    }

    public static bool AreEqual(Image imageA, Image imageB)
    {
        if (imageA.Width != imageB.Width) return false;
        if (imageA.Height != imageB.Height) return false;

        var hashA = imageA.ShaHash();
        var hashB = imageB.ShaHash();

        return !hashA
            .Where((nextByte, index) => nextByte != hashB[index])
            .Any();
    }
]

用法很简单：

bool isMatch = Utils.AreEqual(bitmapOne, bitmapTwo);