问题标签 [locality-sensitive-hash]

This is my first image processing application, so please be kind with this filthy peasant.

THE APPLICATION:

I want to implement a fast application (performance are crucial even over accuracy) where given a photo (taken by mobile phone) containing a movie poster finds the most similar photo in a given dataset and return a similarity score. The dataset is composed by similar pictures (taken by mobile phone, containing a movie poster). The images can be of different size, resolutions and can be taken from different viewpoints (but there is no rotation, since the posters are supposed to always be right-oriented).

Any suggestion on how to implement such an application is well accepted.

FEATURE DESCRIPTIONS IN OPENCV:

I've never used OpenCV and I've read this tutorial about Feature Detection and Description by OpenCV.

From what I've understood, these algorithms are supposed to find keypoints (usually corners) and eventually define descriptors (which describe each keypoint and are used for matching two different images). I used "eventually" since some of them (eg FAST) provides only keypoints.

MOST SIMILAR IMAGE PROBLEM AND LSH:

The problems above doesn't solve the problem "given an image, how to find the most similar one in a dataset in a fast way". In order to do that, we can both use the keypoints and descriptors obtained by any of the previous algorithms. The problem stated above seems like a nearest neighbor problem and Locality Sensitive Hashing is a fast and popular solution for find an approximate solution for this problem in high-dimensionality spaces.

THE QUESTION:

What I don't understand is how to use the result of any of the previous algorithms (i.e. keypoints and descriptors) in LSH.

Is there any implementation for this problem?

我正在阅读Kernelized Locality-Sensitive Hashing，这显然是基于应用于空间、函数和数据的内核概念。

我对数学和图像处理中的这个概念也没有信心（因为它不是我的领域，如果我很天真，对不起），所以请有人帮我理解它吗？

我已经阅读了关于 Locality Sensitive Hashing的原始论文。

复杂性是参数 ε 的函数，但我不明白它是什么。

你能解释一下它的含义吗？

我试图理解本文关于 LSH 的第 5 节，特别是如何存储生成的哈希。引用链接的论文：

给定每个由 d 位组成的位向量，我们选择 N = O(n 1/(1+epsilon) ) 位的随机排列。对于每个随机排列 σ，我们维护位向量的排序顺序 O σ，按照由 σ 排列的位的字典顺序。给定一个查询位向量 q，我们通过执行以下操作找到近似最近邻： 对于每个排列 σ，我们对 O σ 执行二进制搜索，以定位最接近 q 的两个位向量（按获得的字典顺序）由 σ 置换的位）。我们现在按照与 q 匹配的最长前缀的长度的顺序在每个排序顺序 O σ 中搜索由二分搜索返回的位置上方和下方的元素。这可以通过为每个排序顺序 O σ 维护两个指针来完成（一个向上移动，另一个向下移动）。在每一步中，我们向上或向下移动与具有最长匹配前缀的元素相对应的指针之一。（这里 O σ 中最长匹配前缀的长度是相对于 q 计算的，其位由 σ 置换）。我们以这种方式检查 2N = O(n 1/(1+epsilon) ) 位向量。在检查的所有位向量中，我们将具有最小汉明距离的位向量返回到 q。

我对这个算法感到困惑，我认为我不明白它是如何工作的。

我已经在该主题上找到了这个问题，但我不明白评论中的答案。同样在第 2 点的这个问题中，描述了相同的算法，但同样，我不明白它是如何工作的。

你能试着向我解释它是如何工作的，并尽可能地简单吗？

我什至试着把我看不懂的东西列个清单，但实际上写得太糟糕了，我看不懂大部分句子！

在 gsamaras 回答后编辑：

我基本上明白了答案，但我仍然有一些疑问：

1. 是否正确地说执行N排列的总成本是O(Nnlogn)，因为我们必须对它们中的每一个进行排序？

2. 上述排列+排序过程在预处理期间或每个查询中只执行一次q？O(Nnlogn)即使在预处理中，它似乎已经相当昂贵，如果我们必须在查询时这样做，那将是一场灾难：D

3. 在最后一点，我们比较v0和v4，q我们比较它们的置换版本还是原始版本（在它们置换之前）？

我读了一些关于 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 通常接受向量作为输入。

局部敏感哈希 (LSH) 的关键思想是相邻点v更有可能映射到同一个桶，但彼此相距较远的点更有可能映射到不同的桶。在使用随机投影时，如果数据库包含 N 个样本，每个样本都具有较高的维度 d，那么理论上我们必须创建 k 个随机生成的哈希函数，其中 k 是目标缩减维度，表示为g(**v**) = (h_1(v),h_2(v),...,h_k(v))。因此，对于任何向量点v，该点都映射到具有 g 函数的 k 维向量。那么哈希码就是长度/维度为k的缩减向量，被视为一个桶。现在，为了增加碰撞概率，理论说我们应该g_1, g_2,...,g_L随机拥有 L 个这样的 g 函数。这是我不明白的部分。

问题：如何创建多个哈希表？一个哈希表中包含多少个桶？

我正在遵循Sparse Projections for High-Dimensional Binary CodesYan Xia 等人在论文中给出的代码。al 代码链接

在文件中Coding.m

X_query是每个维度为 d 的查询数据集，有 1000 个查询样本；R是随机投影，位是目标降维。B_query和的输出B_base是N长度k为 0/1 值的字符串。这种方式是否会创建多个哈希表，即哈希表N的数量？我很困惑如何。详细的解释将非常有帮助。

通常，SIFT、SURF和许多其他算法提供一组k关键点和相关的d维度描述符（例如，在 SIFT 中，每个描述符都有d=128维度）。

因此，为了描述图像，我们需要一个矩阵kxd（k描述符向量，每个d维度都有一个）。到目前为止，一切都很好。

我的问题是：我们如何通过单个向量来描述图像？

这可能非常有用，因为我们可以节省大量空间，并且某些算法（如LSH）需要向量作为输入/查询。

在一些论文中（例如this，第 6.5 节），这种方法被描述为“全局描述符”。

据了解，我只找到了这篇论文，但它似乎不太准确（它是 2009 年的，不是那么新）。

更新： 其他可能的解决方案（评论中提出了一些建议）：

• 视觉词袋

• 主旨描述符

前提：

我对计算机视觉/图像处理和机器学习真的很陌生（幸运的是，我更擅长信息检索），所以请善待这个肮脏的农民！:D

我的应用程序：

我们有一个移动应用程序，用户在其中拍照（查询），系统返回与其他用户先前拍摄的最相似的照片（数据集元素）。时间性能至关重要，其次是精度，最后是内存使用。

我的方法：

首先，很明显这是一个 1-Nearest Neighbor 问题 (1-NN)。LSH是解决此问题的一种流行、快速且相对精确的解决方案。特别是，我的 LSH impelementation 是关于使用Kernalized Locality Sensitive Hashing来实现良好的精度，将-dimensiond向量转换为 -dimension sbinary vector (where s<<d)，然后使用Fast Exact Search in Hamming Space with Multi-Index Hashing快速找到数据集中所有向量之间的精确最近邻（转置到汉明空间）。

此外，我将使用SIFT，因为我想为我的应用程序使用强大的关键点检测器和描述符。

在这个过程中遗漏了什么？

好吧，看来我已经决定了一切，对吧？实际上没有：在我的链接问题中，我面临如何将单个图像的集合描述符向量表示为向量的问题。为什么我需要它？因为 LSH 中的查询/数据集元素是向量，而不是矩阵（而 SIFT 关键点描述符集是矩阵）。正如评论中有人建议的那样，最常见（也是最有效）的解决方案是使用Bag of Features (BoF) 模型，我对此仍然没有信心。

所以，我读了这篇文章，但我还有一些问题（见下面的问题）！

问题：

第一个也是最重要的问题：您认为这是一种合理的方法吗？

1. BoF 算法中使用的 k-means 是此类应用的最佳选择吗？什么是替代聚类算法？
2. BoF得到的码字向量的维数等于簇的个数（所以-means方法k中的参数k）？
3. 如果 2. 是正确的，那么 k 越大，那么得到的 BoF 向量是否更精确？
4. 有任何“动态”k-means吗？由于计算完成后必须将查询图像添加到数据集中（请记住：数据集是由所有提交的查询的图像形成的）集群可以及时更改。
5. 给定一张查询图像，获取码本向量的过程是否与获取数据集图像的过程相同，例如，我们将每个描述符分配给一个集群，i-th结果向量的维度等于分配给i-th集群的描述符数量？

flannIndex在 openCV 中旨在通过二进制描述符匹配 2 个图像。

无论如何，LSH 在 CBIR 中被大量使用，不是为了“比较两个图像”而是“在数据集中找到最相似的图像”，这显然是不同的。

我们如何在 OpenCV 中实现这样的事情？

引用 E2LSH 手册（关于这个特定库并不重要，这句话对于一般的 NN 问题应该是正确的）：

E 2LSH 也可用于解决最近邻问题，其中，给定查询 q，数据结构需要报告 P 中最接近 q 的点。这可以通过创建几个 R 近邻数据结构来完成，对于 R = R1, R2, 。. . Rt ，其中 Rt 应大于从任何查询点到其最近邻居的最大距离。然后可以通过按半径的递增顺序查询数据结构来恢复最近的邻居，只要找到第一个点就停止

有人可以改写吗？我没有这个程序来使用 R 近邻方法找到最近的邻居。