图像哈希指纹碰撞（dHash）

Question

我在一组非常大的图像中使用 dHash ( http://www.hackerfactor.com/blog/index.php?url=archives/529-Kind-of-Like-That.html )。默认调整大小为 8 像素：

def dhash(image, hash_size=8):
    """
    Difference Hash computation.
    following http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html
    @image must be a PIL instance.
    """
    image = image.convert("L").resize((hash_size + 1, hash_size), Image.ANTIALIAS)
    pixels = numpy.array(image.getdata(), dtype=numpy.float).reshape((hash_size + 1, hash_size))
    # compute differences
    diff = pixels[1:, :] > pixels[:-1, :]
    return ImageHash(diff)

如果我们应用这个算法做大量的图像，我会不会因为短哈希指纹而发生冲突？

什么是最好的 hash_size？hash_size 越大不是越准确吗？是 8 是因为某些特定原因吗？

Answer 1

我最近看了几百万达西的统计。分布非常接近均匀性，即至少我的数据集没有任何模式，例如图像往往在上半部分更亮等。

这意味着冲突的概率接近二项式情况，并且每个位都是独立的。IIRC 正确，8x8 像素意味着您保存的哈希值是 64 位。有 2 64 = 1.8 x 10 19 种可能的哈希值，数量很多。生日悖论再次将我们击倒了平方根，所以你会期望看到你与第 40 亿张图像的第一次碰撞。