问题快速简单的图像哈希算法

我需要一个（最好是简单快速）图像哈希算法。哈希值用于查找表，而不用于加密。

一些图像是“计算机图形” - 即纯色填充的光栅，光栅化文本等，而还有“摄影”图像 - 包含丰富的色谱，大多是光滑的，具有合理的噪声幅度。

我也希望哈希算法能够应用于特定的图像部分。我的意思是，图像可以分为网格单元格，每个单元格的哈希函数应该仅取决于该单元格的内容。因此，如果两个图像具有共同区域（如果它们被适当地对齐），则可以快速发现。

注意： 我只需要知道两个图像（或它们的部分）是否是相同。也就是说，我不需要匹配类似的图像，不需要特征识别，相关和其他DSP技术。

我想知道什么是首选的散列算法。

对于“摄影”图像，只需对网格单元内的所有像素进行异或运算即可。不同图像的相同散列值的概率非常低，特别是因为（几乎白色）噪声的存在破坏了所有潜在的对称性。此外，这种散列函数的频谱看起来很好（任何值都可能具有几乎相同的概率）。

但是这种天真的算法可能不会与“人工”图形一起使用。对于这样的图像，相同的像素，重复图案，几何偏移不变性是非常常见的。对于具有偶数个相同像素的任何图像，对所有像素进行异或将给出0。

使用像CRT-32这样的东西看起来很有希望，但我想更快地找出一些东西。我想到了迭代公式，每个新像素都会改变当前的哈希值，如下所示：

hashValue = (hashValue * /*something*/ | newPixelValue) % /* huge prime */

做模数素数应该可以很好地分散，所以我倾向于这个选项。但我想知道是否有更好的变种。

提前致谢。

13107

2017-07-04 23:02

起源

你为什么不使用像md5这样的普通哈希算法？ - Karoly Horvath

@Karoly Horvath：好问题。事实上，这正是我需要的或多或少。然而，MD5（可能）是CPU饥渴的，它被设计为单向散列函数。 OTOH我需要更简单的东西，因为我没有安全考虑。我虽然关于CRC-32。但我想找出更简单的东西 - valdo

如果你在很多图像上执行此操作，瓶颈将是你的磁盘速度。 - Karoly Horvath

@Karoly Horvath：谁说它会在磁盘上？确切地说，我将为您提供使用场景：内存中通常会存储多达100-200个图像（各种大小，对于台式计算机应用程序而言“典型”）。每当我“看到”一个新图像时 - 我想知道它是否与我之前看到的一致。 - valdo

答案:

如果你想让它非常快，你应该考虑采用像素的随机子集来避免读取整个图像。接下来，计算这些像素的值序列的散列函数。应该通过具有固定种子的确定性伪随机数生成器来选择随机子集，使得相同的图像产生相同的子集并因此产生相同的散列值。

即使对于人工图像，这也应该相当好。但是，如果您的图像彼此之间的差异很小，则会产生哈希冲突。更多迭代提供更好的可靠性。如果是这种情况，例如，如果您的图像集可能具有一个不同像素的对，则必须读取每个像素以计算哈希值。即使对于人工图像，采用具有伪随机系数的简单线性组合也是足够好的。

一个简单算法的伪代码

Random generator = new generator(2847)  // Initialized with fixed seed
int num_iterations = 100

int hash(Image image) {
    generator.reset()   //To ensure consistency on each evaluation
    int value = 0
    for num_iteration steps {
        int nextValue = image.getPixel(generator.nextInt()%image.getSize()).getValue()
        value = value + nextValue*generator.nextInt()
    }
    return value
}

2017-07-05 13:50

感谢你的回答。我没有问题阅读整个网格单元格。我的网格单元非常小（8x8或16x16）。此外，当两个图像的哈希值相等时 - 尽管如此我仍然确保图像相等。缺少的唯一参数是散列函数本身。它应该是什么？ - valdo

如果您不需要加密安全性，并且只担心人工图像，那么像我们所描述的那样，像素值与随机系数的简单线性组合就足够了。问题类似于找到整数数组的散列，例如v1 = [34,2,4,92,3]，v2 = [10,3,5,20,3]。你的目标是找到它们的哈希，看看哪些是平等的。最初选择随机选择的固定向量m = [72,37,1,4,34]。对于每个输入向量，v1的散列值是v1 * m = 34 * 72 + 2 * 37 + 4 * 1 + 92 * 4 + 3 * 34。如果你愿意的话，你也可以计算任何素数的模数。 - akashnil

看一下关于phash算法的本教程 http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html 用于找到紧密匹配的图像。

2017-07-05 14:00

感谢您的关注，但这不是我想要的恕我直言。所描述的算法适合于找到“相似”图像，它也是尺度不变的。我的问题更简单，我想要一个更有效的解决方案 - valdo

@valdo：我添加了更多信息。 - Bytemain

问题 快速简单的图像哈希算法

答案:

热门问题

问题快速简单的图像哈希算法