LSH 是关于将向量转换为二进制向量以获得汉明距离吗?
Is LSH about transforming vectors to binary vectors for hamming distance?
我读了一些关于 LSH 的论文,我知道它用于解决近似 k-NN 问题。我们可以将算法分为两部分:
给定一个 D
维(其中 D
大)任意值的向量,用一组 N
(其中 N<<D
) 哈希函数到 N
维度的二进制向量。
使用汉明距离,对从阶段 1 获得的给定二进制代码集应用一些搜索技术以找到 k-NN。
关键是使用 XOR 可以快速计算 N
维向量的汉明距离。
无论如何,我有两个问题:
要点1.如果我们使用二进制描述符,比如ORB,还有必要吗?既然ORB的描述符已经是二进制的了,我们使用汉明距离来比较它们,为什么还要进行第一点呢?
如何对 SIFT 描述的图像进行转换?每个 SIFT 描述符为 128 位,每个图像由一组描述符描述。所以我们有矩阵 descX128
(其中 desc
是使用的描述符的数量),而 LSH 通常接受一个向量作为输入。
1) 你可以绕过它,但是 然后你将在 D
维度工作,而不是你说的 N
。其中 N << D
。这意味着该算法也必须适应 D
维度。
2) 否.
- 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*.
现在每个点,代表一个图像描述符。所以,我们有 n
图片
数据集.
查询,也是一个点(即向量d
坐标),表示另一个图像描述符。
我们正在寻求匹配(即找到最近的邻居)
使用我们数据集中的图像描述符查询图像描述符。
所以你所说的转换是在向量中应用的,不是矩阵。
编辑:
此外,根据我们的 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.
我读了一些关于 LSH 的论文,我知道它用于解决近似 k-NN 问题。我们可以将算法分为两部分:
给定一个
D
维(其中D
大)任意值的向量,用一组N
(其中N<<D
) 哈希函数到N
维度的二进制向量。使用汉明距离,对从阶段 1 获得的给定二进制代码集应用一些搜索技术以找到 k-NN。
关键是使用 XOR 可以快速计算 N
维向量的汉明距离。
无论如何,我有两个问题:
要点1.如果我们使用二进制描述符,比如ORB,还有必要吗?既然ORB的描述符已经是二进制的了,我们使用汉明距离来比较它们,为什么还要进行第一点呢?
如何对 SIFT 描述的图像进行转换?每个 SIFT 描述符为 128 位,每个图像由一组描述符描述。所以我们有矩阵
descX128
(其中desc
是使用的描述符的数量),而 LSH 通常接受一个向量作为输入。
1) 你可以绕过它,但是 然后你将在 D
维度工作,而不是你说的 N
。其中 N << D
。这意味着该算法也必须适应 D
维度。
2) 否.
- 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*.
现在每个点,代表一个图像描述符。所以,我们有
n
图片 数据集.查询,也是一个点(即向量
d
坐标),表示另一个图像描述符。我们正在寻求匹配(即找到最近的邻居) 使用我们数据集中的图像描述符查询图像描述符。
所以你所说的转换是在向量中应用的,不是矩阵。
编辑:
此外,根据我们的 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.