c++ - OpenCV 中用于图像处理的局部敏感哈希

Question

这是我的第一个图像处理应用程序，所以请善待这个肮脏的农民。

应用程序:

我想实现一个快速的应用程序(性能至关重要，甚至高于准确性)，其中给定一张包含电影海报的照片(由手机拍摄)，在给定数据集中找到最相似的照片并返回相似度得分。该数据集由相似的图片组成(手机拍摄，包含电影海报)。图像可以具有不同的尺寸、分辨率，并且可以从不同的角度拍摄(但没有旋转，因为海报应该始终是向右的)。

任何有关如何实现此类应用程序的建议都会被广泛接受。

OPENCV 中的功能描述:

我从未使用过 OpenCV，但我读过 this tutorial about Feature Detection and Description通过 OpenCV。

根据我的理解，这些算法应该找到关键点(通常是角点)并最终定义描述符(描述每个关键点并用于匹配两个不同的图像)。我使用“最终”，因为其中一些(例如 FAST)仅提供关键点。

最相似图像问题和 LSH:

上述问题并没有解决“给定一张图像，如何快速找到数据集中最相似的图像”的问题。为此，我们可以使用之前任何算法获得的关键点和描述符。上述问题看起来像nearest neighbor problem和 Locality Sensitive Hashing是在高维空间中找到此问题的近似解的快速且流行的解决方案。

问题:

我不明白的是如何在 LSH 中使用任何先前算法的结果(即关键点和描述符)。

有没有办法解决这个问题？

Answer 1

我将提供一个一般性答案，超出 OpenCV 库的范围。

---

引用此answer :

descriptors: they are the way to compare the keypoints. They summarize, in vector format (of constant length) some characteristics about the keypoints.

话虽如此，我们可以将描述符想象/视为(几何)D 维空间中的点。所以总的来说，所有描述符都是 D 维空间中的点。例如，对于 GIST ，D = 960。

所以实际上描述符描述图像，使用比整个图像更少的信息(因为当你有 10 亿张图像时，大小很重要)。它们充当图像的代表，因此我们代表图像处理它们(因为它们更容易/更小处理)。

---

您提到的问题是Nearest Neighbor问题。请注意，当 D 较大时，此问题的近似版本可能会导致显着的加速(因为维数灾难将使传统方法，例如 kd-tree 非常慢，几乎是线性的) N(点数))。

解决神经网络问题(这是一个优化问题)的算法通常是通用的。他们可能不关心数据是否是图像、分子等，例如我使用了我的kd-GeRaF对彼此而言。因此，算法期望 D 维空间中有 N 个点，因此您可能想说 N 个描述符。

查看我对 LSH 的回答 here (这表明这是一个很好的实现)。

---

编辑:

LSH 期望输入 N 个 D 维度 vector ，并给出查询 vector (在 D 中)和范围 R，将从查询 vector 中找到位于此范围内的 vector 。

因此，我们可以说每个图像仅由一个 vector 表示，如 SIFT例如格式。

你看，LSH 实际上并没有直接解决 k-NN 问题，但它在一个范围内搜索(并且可以为你提供 k-NN，如果它们在该范围内)。在实验部分了解有关 R 的更多信息，High-dimensional approximate nearest neighbo 。 kd-GeRaF和 FLANN直接求解k-NN问题。