2

我读了一些关于 LSH 的论文，我知道它用于解决近似的 k-NN 问题。我们可以将算法分为两部分：

  1. 给定一个任意值的D维度（whereD很大）向量，用一组N（where N<<D）散列函数将其转换为N维度的二进制向量。

  2. 使用汉明距离，对从阶段 1 获得的给定二进制代码集应用一些搜索技术以找到 k-NN。

N关键是使用 XOR计算维度向量的汉明距离很快。

无论如何，我有两个问题：

  1. 如果我们使用像 ORB 这样的二进制描述符，第 1 点仍然是必要的吗？既然 ORB 的描述符已经是二进制的，我们使用汉明距离来比较它们，为什么我们要执行第一点呢？

  2. SIFT 描述的图像如何转换？每个 SIFT 描述符为 128 位，每个图像由一组描述符描述。所以我们有矩阵descX128（其中desc是使用的描述符的数量），而 LSH 通常接受向量作为输入。

4

1 回答 1

2

1）您可以绕过它，但是您将在D维度上工作，而不是N像您说的那样。哪里N << D。这意味着算法也必须适应D维度。

2)没有。

从 openCV读取SIFT ：

  1. 关键点描述符

现在创建了关键点描述符。取关键点周围的 16x16 邻域。它分为 16 个 4x4 大小的子块。对于每个子块，创建 8 个 bin 方向直方图。因此共有 128 个 bin 值可用。它被表示为一个向量以形成关键点描述符。除此之外，还采取了一些措施来实现对光照变化、旋转等的鲁棒性。

这是我的想法，希望这就足够了：

LSH 将一个n点集作为输入，其中每个点都位于d维度中。

因此，查询是一个点，在d维度上，目标是找到它的 NN *。

  1. 现在每个点都代表一个图像描述符。因此，我们n的数据集中有图像。

  2. 查询也是一个点（即带有d 坐标的向量），代表另一个图像描述符。

  3. 我们正在寻求将查询图像描述符与我们数据集中的图像描述符进行匹配（即找到最近邻）。

因此，您正在谈论的转换应用于向量，而不是矩阵。

编辑：

此外，来自我们的高维近似最近邻：kd Generalized Randomized Forests论文，请参见实验部分：

SIFT 是一个 128 维向量，通过局部梯度方向的直方图来描述局部图像块。

*或固定半径近邻问题

于 2016-05-25T06:34:15.917 回答