局部性敏感散列还是pHash？

Question

我正在尝试实现一个通用指纹回忆录：我们有一个可以通过智能指纹来表示的文件(比如用于图像的pHash或用于音频的铬蛋白 )，如果我们需要的(昂贵的)函数已经在相似的文件上计算过了，那么我们返回相同的结果(避免昂贵的计算)。

局部性敏感散列 (LSH)是一种在昂贵的多维空间中求解近似近邻问题的有效方法.

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

因此，pHash将多维输入(图像)转换为一维对象(哈希码)，这与LSH (也是LSH中的多维对象)不同。

所以我想知道我们如何为pHash哈希值实现一个一维LSH？或者用几句话来说:我们如何分组到类似的pHash值中？它是否可以替代经典的LSH方法(如果不是，为什么)？

Answer 1

您可以使用n 随机投影将pHash空间分割成2^n桶，然后很可能从同一个桶中找到类似的图像。您甚至可以使用带有Hamming重量1的所有64个可能整数的散列来方便地检查相邻的桶，并确保找到所有的近似匹配。

这是有效的，只有当你感兴趣的图像与几乎相同的散列(小汉明距离)。如果你想容忍更大的汉明距离(如8)，那么很难找到所有的匹配有效和准确。我通过扫描通过获得了很好的性能-- GPU的整个表，即使是我3岁的笔记本电脑的GT650m，每秒也可以检查7亿个散列！

编辑1：您可以将64位哈希看作64维立方体上的一个角，如果您将角坐标归一化为-1和1 (这样它的中心在原点)，数学就更容易了。您可以将m图像表示为大小为m x 64的矩阵M (一行/图像，一位哈希/列)。

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

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

该算法适用于任何数据的正交表示(如浪花特性)，而不仅仅是二进制字符串。我确信对于二进制哈希有更简单(计算效率更高)的算法，但这是实现随机投影的一种方法。

我建议使用XORring，因为如果图像没有相同的散列，那么它们就不能保证在同一个桶中结束。通过检查与原始散列的所有可能的小偏差，您可以看到可能匹配的其他回收箱。

在某种程度上，这类似于计算机游戏引擎可能将2D地图分割成一个大小为x的单元格，然后从一个点查找半径x中的所有单元，只需检查9个单元(包含点+8个周围单元)即可得到100%的准确答案。