12

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

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

我还希望散列算法能够应用于特定的图像部分。我的意思是，图像可以划分为一个网格单元格，每个单元格的哈希函数应该只取决于这个单元格的内容。因此，如果两个图像具有共同区域（以防它们正确对齐），则可以快速发现。

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

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

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

但这种幼稚的算法可能不适用于“人造”图形。相同像素、重复图案、几何偏移不变性对于此类图像非常常见。对于具有偶数个相同像素的任何图像，对所有像素进行异或运算将为 0。

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

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

做模素数可能会产生良好的分散性，所以我倾向于这个选项。但我想知道是否有更好的变体。

提前致谢。

4

2 回答 2

7

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

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

一个简单算法的伪代码

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
}
于 2012-07-05T13:50:43.930 回答
7

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

于 2012-07-05T14:00:54.257 回答