快速简单的图像哈希算法

Question

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

其中一些图像是“计算机图形” - 即填充的实色矩形、栅格化文本等，而也有“摄影”图像 - 包含丰富的颜色谱，大多数平滑，噪声幅度合理。

我还希望哈希算法能够应用于特定的图像部分。我的意思是，可以将图像分成网格单元，并且每个单元的哈希函数应仅取决于该单元的内容。这样，如果两个图像的公共区域对齐，则可以快速发现。

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

我想知道首选的哈希算法是什么。

对于“摄影”图像，仅对网格单元内的所有像素进行XOR运算就足够了。不同图像具有相同哈希值的概率非常低，尤其是因为（几乎白色的）噪声存在破坏所有潜在对称性。此外，这种哈希函数的频谱看起来很好（几乎具有相同的可能性）。

但是，这样的简单算法可能无法处理“人工”图形。对于这种图像，相同像素、重复的模式、几何偏移不变性非常普遍。对所有像素进行XOR运算将为任何具有相同像素数量的图像提供0。

使用类似CRT-32的东西似乎有一定的希望，但我想找出更快的方法。我考虑过迭代公式，每个新像素都会改变当前哈希值，就像这样：

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

对质数取模可能会得到更好的分散效果，因此我倾向于这个选项。但我想知道是否有更好的变体。

提前感谢。

- valdo

---

为什么不使用一些简单的哈希算法，比如MD5？ - Karoly Horvath

@Karoly Horvath：好问题。确实这差不多是我需要的。然而MD5（可能）需要大量CPU，它被设计成单向哈希函数。另一方面，我需要更简单的东西，因为我没有安全考虑。我想到了CRC-32。但我想找出更简单的东西。 - valdo

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

@Karoly Horvath：谁说它会在磁盘上？更准确地说，我将为您提供使用场景：通常会在内存中存储100-200个图像（大小各异，适用于桌面计算机应用程序的“典型”）。每当我“看到”一张新图片时，我想知道它是否与我之前看到的某张图片相同。 - valdo

Answer 1

请看一下这篇关于phash算法的教程http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html，该算法用于查找相似的图片。

- Micromega

---

谢谢关注，但这不是我想要的。所描述的算法适用于查找“相似”的图像，而且它也具有尺度不变性。我的问题要简单得多，我需要一个更高效的解决方案。 - valdo

Answer 2

如果您想让它运行得非常快，您应该考虑随机选择像素的子集以避免读取整个图像。然后，在这些像素值的序列上计算哈希函数。应该使用固定种子的确定性伪随机数生成器选择随机子集，以便相同的图像产生相同的子集和相同的哈希值。

即使对于人工图像，这也应该能够正常工作。但是，如果您有仅有少量像素不同的图像，这将导致哈希冲突。进行更多迭代可以提高可靠性。如果是这种情况，例如，如果您的图像集可能具有一个不同像素的成对图像，则必须读取每个像素以计算哈希值。即使对于人工图像，采用伪随机系数的简单线性组合也足够好。

下面是一个简单算法的伪代码。

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
}

- akashnil

---

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

如果您不需要加密安全性，只担心人工图像的话，那么使用带随机系数的简单线性组合应该就足够了，就如我所描述的。这个问题类似于查找整数数组的哈希值，例如v1=[34,2,4,92,3]，v2=[10,3,5,20,3]。您的目标是找到它们的哈希值以查看哪些相等。最初选一个随机选择的固定向量m=[72,37,1,4,34]。对于每个输入向量，v1的哈希值为v1m= 3472 + 237 + 41 + 924 + 334。如果您愿意，您也可以对此数字进行任何质数取模运算。 - akashnil