局部敏感哈希还是 pHash？

Question

我正在尝试实现一个通用的指纹记忆器：我们有一个可以通过智能指纹表达的文件（如图像的pHash或音频的色度图），如果我们想要的（昂贵的）函数已经在类似的文件上计算过，然后我们返回相同的结果（避免昂贵的计算）。

局部敏感哈希(LSH) 是一种流行且性能良好的解决方案，用于解决昂贵的多维空间中的近似最近邻问题。

pHash是一个很好的库，它实现了图像的感知散列。

因此，pHash 将多维输入（图像）转换为一维对象（哈希码），这与 LSH（再次，LSH 中的多维对象）有所不同。

所以我想知道我们如何为 pHash 哈希值实现单维 LSH？或者简单地说：我们如何将类似的 pHash 值分组到 bin 中？它可以替代经典的 LSH 方法吗（如果不是为什么）？

Answer 1

您可以使用n 随机投影将 pHash 空间分成2^n多个桶，然后很可能从同一个桶中找到相似的图像。您甚至可以将哈希与汉明权重为 1 的所有 64 个可能的整数进行异或，以方便地检查相邻的存储桶，并确保您找到所有近似匹配。

仅当您对具有几乎相同哈希值（小汉明距离）的图像感兴趣时，这才有效。如果您想容忍更大的汉明距离（例如 8），那么高效准确地找到所有匹配项就会变得很棘手。我通过 GPU扫描整个表获得了非常好的性能，即使是我 3 年的笔记本电脑 GT 650M 也可以检查 7 亿个哈希/秒！

编辑 1：您可以将 64 位哈希视为 64 维立方体上的单个角，如果将角坐标标准化为-1和1（这样它的中心位于原点），数学会更容易。您可以将m图像表示为M大小矩阵m x 64（一行/图像，一位散列/列）。

将其分成2^n不同组的最简单方法是生成n64 维向量v_0, v_1, ..., v_n（从正态分布 N(0,1) 中选取每个向量元素），这可以表示为V大小矩阵64 x n（一列/向量）。正如随机投影中提到的，可能存在正交性强制，但我将在这里跳过它。

现在通过计算A = (M * V) > 0得到m x n矩阵（一张图像/行，一个投影/列）。接下来将每行的二进制表示形式转换为数字，您会得到2^n不同的可能性，并且相似的哈希最有可能最终到达同一个存储桶。

该算法适用于数据的任何正交表示（例如SURF特征），而不仅仅是二进制字符串。我确信二进制哈希有更简单（并且计算上更有效）的算法，但这是实现随机投影的一种方法。

我建议使用异或环，因为如果图像没有相同的哈希值，那么它们不能保证最终位于同一个存储桶中。通过检查与原始哈希值的所有可能的小偏差，您可以了解哪些其他 bin 可能用于可能的匹配。

在某种程度上，这类似于计算机游戏引擎将 2D 地图分割成大小为 的单元格的网格x，然后要查找以点为中心的半径内的所有单位，x您只需要检查 9 个单元格（包含点 + 8 的单元格）周围的细胞）以获得 100% 准确的答案。