c++ - 局部敏感哈希或 pHash？

Question

我正在尝试实现通用指纹 memoizator :我们有一个可以通过智能指纹表示的文件(例如图像的 pHash 或音频的 chromaprint)，如果我们想要的(昂贵的)函数已经在类似文件上计算出来，那么我们返回相同的结果(避免昂贵的计算)。

Locality Sensitive Hash (LSH) 是 Approximate nearest neighbor 的流行且性能良好的解决方案昂贵的多维空间中的问题。

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

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

所以我想知道我们如何为 pHash 哈希值实现一维 LSH？或者简而言之:我们如何将相似的 pHash 值分组到 bin 中？它可以替代经典的 LSH 方法吗(如果不是为什么)？

Answer 1

你可以使用n random projections将 pHash 空间分成 2^n 个桶，那么很可能从同一个桶中找到相似的图像。您甚至可以将散列与所有 64 个可能的整数(汉明权重为 1)进行异或，以方便地检查相邻的桶并确保找到所有近似匹配项。

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

编辑 1:您可以将 64 位哈希视为 64 维立方体上的单个角，如果将角坐标标准化为 -1 并且1(这样它的中心在原点)。您可以将 m 图像表示为大小为 m x 64 的矩阵 M(一行/图像，一位散列/列)。

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

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

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

我建议使用 XORring，因为如果图像不具有相同的哈希值，则不能保证它们最终会出现在同一个存储桶中。通过检查与原始哈希的所有可能的小偏差，您可以看到哪些其他 bin 可能用于可能的匹配。

在某种程度上，这类似于计算机游戏引擎如何将 2D map 拆分为大小为 x 的单元格网格，然后找到半径 x 内的所有单元> 从一个点出发，您只需检查 9 个单元格(包含该点的单元格 + 周围的 8 个单元格)即可获得 100% 准确的答案。