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

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

虽然这个工作,并且对于小的位图效果很好,但是在制作过程中,我将会在一个紧密的循环和更大的图像中使用它,所以我需要一个更好的方法。 有没有人有任何build议?

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

编辑 :我已经编写了一些build议的实现,这里是基准。 设置:两个相同的(最坏的情况下)位图,大小100×100,每个10,000次迭代。 结果如下:

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

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

感谢大家。 =)

编辑2 :忘了closures优化 – 这样做可以使GrayWizardX的答案更具有提升性:

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

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

编辑3 :张贴我的答案(MemCmp)其他方法吹出来的水。 OO

编辑8-31-12:每个乔伊的评论下面,请注意您比较的位图的格式。 他们可能会包含填充的步伐,使位图不等,尽pipe是等效的像素。 看到这个问题的更多细节。


阅读这个答案有关比较字节数组的问题已经产生了更快的方法:在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); } } 

如果你试图确定它们是否是100%相等的,你可以倒置一个,如果它们相同则把它加到另一个。 使用不安全的代码进行扩展,一次取64位,并以这种方式进行math计算,任何差异都可能导致立即失败。

如果图像不是100%相同的(比较PNG到JPEG),或者如果你不是100%匹配,那么你有更多的工作在你面前。

祝你好运。

那么,你正在使用.LockBits ,所以大概你使用的是不安全的代码。 不要把每一行的起始位置( Scan0 + y * Stride )视为一个byte* ,而应该把它看作一个int* ; int算术很快,你只需要做1/4的工作。 而对于ARGB中的图像,你可能仍然在用像素进行交谈,使得math变得简单。

你可以把每一个哈希和比较? 这将是略有概率的,但实际上不是。

由于Ram,这是这种技术的一个示例实现 。

如果原始问题只是在两个位图之间find确切的重复,那么只需要进行比特级比较就可以了。 我不知道C#但在CI会使用以下function:

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

我会开始在中间看,因为我怀疑在图像中间附近find比开始时不平等的位更好的机会; 当然,这真的取决于你正在扣除的图像,select一个随机的地方开始可能是最好的。

如果您试图在数百张图片中find完全相同的重复图片,则比较所有图片对是不必要的。 首先计算每个图像的MD5哈希,并将其放在一个对列表中(md5Hash,imageId); 然后通过m5Hash对列表进行sorting。 接下来,只对具有相同md5Hash的图像进行两两比较。

如果这些位图已经在您的显卡上,那么您可以使用CUDA或OpenCL等语言在显卡上进行并行化检查。

我会用CUDA来解释,因为那是我所知道的。 基本上CUDA允许您编写通用代码在您的graphics卡的每个节点上并行运行。 您可以访问共享内存中的位图。 该函数的每个调用在并行运行集中也被赋予一个索引。 因此,对于这样的问题,您只需要对位图的某个子集运行上述比较函数之一 – 使用并行化来覆盖整个位图。 然后,如果比较失败,只写1到某个内存位置(如果成功,则不写任何内容)。

如果你的graphics卡上没有位图,这可能不是一个好办法,因为在你的显卡上加载两个位图的代价很容易超过平行化所带来的成本。

这里有一些(非常糟糕的)示例代码(自从我编程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”,然后使用数据库引擎来比较它们的二进制文件。 这只会给你一个是或否的二进制数据是否相同的答案。 制作2张图片的图片非常容易,但是却有不同的二进制图片。

你也可以select一些随机像素并进行比较,如果它们相同,则继续更多,直到检查完所有像素。 这只会返回一个更快的否定匹配,但它仍然需要很长时间才能find100%的正面匹配

基于比较散列而不是比较每个像素的方法,这是我使用的:

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