val*_*ldo 12 algorithm hash image
我需要一个(最好是简单快速)的图像散列算法.散列值用于查找表,而不用于加密.
一些图像是"计算机图形" - 即纯色填充的光栅,光栅化文本等,而还有"摄影"图像 - 包含丰富的色谱,大多是光滑的,具有合理的噪声幅度.
我也希望哈希算法能够应用于特定的图像部分.我的意思是,图像可以分为网格单元格,每个单元格的哈希函数应该仅取决于该单元格的内容.因此,如果两个图像具有共同区域(如果它们被适当地对齐),则可以快速发现.
注意:我只需要知道两个图像(或它们的部分)是否相同.也就是说,我不需要匹配类似的图像,不需要特征识别,相关和其他DSP技术.
我想知道什么是首选的散列算法.
对于"摄影"图像,只需对网格单元格内的所有像素进行异或运算即可.不同图像的相同散列值的概率非常低,特别是因为(几乎白色)噪声的存在打破了所有潜在的对称性.此外,这种散列函数的频谱看起来很好(任何值都可能以几乎相同的概率).
但是这种天真的算法可能不会与"人工"图形一起使用.对于这样的图像,相同的像素,重复图案,几何偏移不变性是非常常见的.对于具有偶数个相同像素的任何图像,对所有像素进行异或将给出0.
使用像CRT-32这样的东西看起来很有希望,但我想更快地找出一些东西.我想到了迭代公式,每个新像素都会改变当前的哈希值,如下所示:
hashValue = (hashValue * /*something*/ | newPixelValue) % /* huge prime */
做模数素数应该可以很好地分散,所以我倾向于这个选项.但我想知道是否有更好的变种.
提前致谢.
如果你想要非常快,你应该考虑采用像素的随机子集来避免读取整个图像.接下来,计算这些像素的值序列的散列函数.应该通过具有固定种子的确定性伪随机数生成器来选择随机子集,使得相同的图像产生相同的子集并因此产生相同的散列值.
即使对于人工图像,这也应该相当好.但是,如果您的图像通过少量像素彼此不同,则会产生哈希冲突.更多迭代提供更好的可靠性.如果是这种情况,例如,如果您的图像集可能具有一个不同像素的对,则必须读取每个像素以计算哈希值.即使对于人工图像,采用具有伪随机系数的简单线性组合也是足够好的.
一个简单算法的伪代码
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
}
看一下关于phash算法的本教程http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html用于查找紧密匹配的图像.