LSH 是关于将向量转换为二进制向量以获得汉明距离吗?

Is LSH about transforming vectors to binary vectors for hamming distance?

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

  1. 给定一个 D 维(其中 D 大)任意值的向量,用一组 N(其中 N<<D) 哈希函数到 N 维度的二进制向量。

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

关键是使用 XOR 可以快速计算 N 维向量的汉明距离。

无论如何,我有两个问题:

  1. 要点1.如果我们使用二进制描述符,比如ORB,还有必要吗?既然ORB的描述符已经是二进制的了,我们使用汉明距离来比较它们,为什么还要进行第一点呢?

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

1) 你可以绕过它,但是 然后你将在 D 维度工作,而不是你说的 N。其中 N << D。这意味着该算法也必须适应 D 维度。


2) .

阅读SIFT from openCV:

  1. Keypoint Descriptor

Now keypoint descriptor is created. A 16x16 neighbourhood around the keypoint is taken. It is devided into 16 sub-blocks of 4x4 size. For each sub-block, 8 bin orientation histogram is created. So a total of 128 bin values are available. It is represented as a vector to form keypoint descriptor. In addition to this, several measures are taken to achieve robustness against illumination changes, rotation etc.

我的想法是这样的,希望足够了:

LSH 以 n 点的点集作为输入,其中每个点都位于 d 维度中。

因此,查询是一个点,在 d 维度中,目标是找到它的 NN*.


  1. 现在每个点,代表一个图像描述符。所以,我们有 n 图片 数据集.

  2. 查询,也是一个点(即向量d 坐标),表示另一个图像描述符。

  3. 我们正在寻求匹配(即找到最近的邻居) 使用我们数据集中的图像描述符查询图像描述符。

所以你所说的转换是在向量中应用的,不是矩阵。


编辑:

此外,根据我们的 High-dimensional approximate nearest neighbor: k-d Generalized Randomized Forests 论文,请参阅 实验 部分:

SIFT is a 128-dimensional vector that describes a local image patch by histograms of local gradient orientations.


*Fixed-radius near neighbors问题