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 回答