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

编辑8-31-12:根据 Joey's 请注意下面比较的位图的格式。它们可能包含使位图不相等的步幅填充,尽管它们的像素方向相同。见 this question 了解更多详细信息。

阅读 this answer 关于比较字节数组的问题产生了一个更快的方法:在msvcrt中使用p/invoke和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);
    }
}

好吧,你在用 .LockBits ,所以假设您使用的是不安全的代码。而不是处理每一行的起源( Scan0 + y * Stride 作为一个 byte* ,考虑将其视为 int* ; int 算术很快,你只需要做四分之一的工作量。对于argb中的图像,您可能仍在谈论像素,使数学变得简单。

如果您试图确定它们是否100%相等,则可以反转其中一个,如果其为零,则将其添加到另一个。使用不安全的代码扩展这个函数,每次使用64位作为一个长度,然后这样做,任何差异都可能导致立即失败。

如果图像不是100%完全相同(将png与jpeg进行比较),或者如果您没有寻找100%匹配,那么您将面临更多的工作。

祝你好运。

你能把每一个都拿出来比较一下吗?这可能有点概率,但实际上并非如此。

多亏了拉姆,这是 sample implementation 这项技术。

如果最初的问题只是在两个位图中找到精确的重复,那么只需要进行位级比较。我不知道C,但在C中,我将使用以下功能:

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的图像进行成对比较。

如果这些位图已经在图形卡上了,那么您可以使用类似的语言在图形卡上进行并行检查。 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;
}

如果你能实现 Duff's Device 在你的语言中,这可能会在一个简单的循环中给你一个显著的速度提升。通常用于复制数据,但没有理由不能将其用于比较数据。

或者,对于这一点,您可能只想使用一些等价于memcmp()。

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

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

基于比较哈希而不是比较每个像素的方法,我使用的是:

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