c++ - 散列图像(一系列 rgb 字节)

Question

我正在使用 C/C++ 开发一个涉及屏幕捕获和散列的应用程序。我捕获的图像尺寸约为 250x250，我使用的是 winapi HashData 散列函数。

我的目标是比较 2 个哈希值(等 2 个 250x250 的图像)并立即判断它们是否相等。

我的代码:

           const int PIXEL_SIZE = (sc_part.height * sc_part.width)*3;
           BYTE* pixels = new BYTE[PIXEL_SIZE];
           for(UINT y=0,b=0;y<sc_part.height;y++) {
              for(UINT x=0;x<sc_part.width;x++) {
                 COLORREF rgb = sc_part.pixels[(y*sc_part.width)+x];
                 pixels[b++] = GetRValue(rgb);
                 pixels[b++] = GetGValue(rgb);
                 pixels[b++] = GetBValue(rgb);
              }
           }
           const int MAX_HASH_LEN = 64;
           BYTE Hash[MAX_HASH_LEN] = {0};
           HashData(pixels,PIXEL_SIZE,Hash,MAX_HASH_LEN);

           ... i have now my variable-size hash, above example uses 64 bytes

           delete[] pixels;

我测试了不同的散列大小及其完成时间，大致是:

           32 bytes  = ~30ms
           64 bytes  = ~47ms
           128 bytes = ~65ms
           256 bytes = ~125ms

我的问题是:

对于 250x250 的图像，哈希码应该有多长才能防止任何重复，比如从不？

我不喜欢 256 个字符的哈希码，因为它会导致我的应用运行缓慢(因为捕获非常频繁)。是否有用于比较的每个图像维度的“安全”哈希大小？

谢谢

Answer 1

假设，根据您的意见，您正在将“即时”计算的散列值添加到数据库中，因此数据库中每张图像的散列值最终都会与其他所有图像的散列值进行比较在数据库中然后你遇到了 birthday paradox .在一组随机选择的数字(例如，一群人的生日)中有两个相同数字的可能性比您凭直觉假设的要大。如果一个房间里有 23 个人，那么其中两人生日相同的概率为 50:50。

这意味着假设一个好的散列函数那么你可以预期会发生冲突，两张图像尽管不相同但具有相同的散列，在 2^(N/2) 次散列之后，其中 N 是散列中的位数。 1如果您的散列函数不是很好，您可以预期更早发生碰撞。不幸的是，只有 Microsoft 知道 HashData 到底有多好。

您的评论还提出了一些其他问题。一是 HashData 不会生成可变大小的哈希值。它生成一个字节数组，该数组的长度始终与您作为散列长度传递的值相同。您的问题是您将其视为一串字符。在 C++ 中，字符串以零终止，这意味着字符串的结尾标有零值字符 ('\0')。由于字节数组将在随机位置包含 0 值元素，因此在使用字符串时它会被截断。像这样处理哈希字符串将使您更有可能发生冲突。

另一个问题是您说您将正在比较的图像存储在您的数据库中，并且这些图像必须是唯一的。如果这种唯一性是由数据库强制执行的，那么在您自己的代码中检查唯一性是多余的。您的数据库很可能能够比您自己的代码更快地执行此操作。