Locality Sensitivy Hashing在OpenCV中进行图像处理 [英] Locality Sensitivy Hashing in OpenCV for image processing

问题描述

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

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

应用程序：

我想实现一个快速的应用程序（性能至关重要甚至超过准确性），其中包含电影海报的照片（手机拍摄）发现最相似给定数据集中的照片并返回相似性分数。数据集由类似的图片组成（由手机拍摄，包含电影海报）。图像可以具有不同的大小，分辨率，并且可以从不同的视点拍摄（但是没有旋转，因为海报应该始终是右向的）。

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).

有关如何实施此类申请的任何建议都被广泛接受。

OPENCV中的功能说明：

我从未使用过OpenCV，而且我读过本教程关于功能检测和描述。

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

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

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.

最相似的图像问题和LSH：

上面的问题并没有解决问题给定图像，如何快速找到数据集中最相似的图像。为了做到这一点，我们都可以使用任何先前算法获得的关键点和描述符。上述问题似乎是最近邻居问题和 Locality Sensitive Hashing 是一种快速而流行的解决方案，可以在高维空间中找到此问题的近似解决方案。

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.

问题：

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

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?

推荐答案

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

I will provide a general answer, going beyond the scope of OpenCV library.

引用此回答：

describeors ：他们是通往的方式比较关键点。它们以b $ b总结，以矢量格式（恒定长度）关于关键点的一些特征
。

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。

With that said, we can imagine/treat (geometrically) a descriptor as point in a D dimensional space. So in total, all the descriptors are points in a D dimensional space. For example, for GIST, D = 960.

所以实际描述符描述图像，使用较少的整个图像信息（因为当你有10亿个图像时，尺寸很重要）。它们作为图像的代表，因此我们代表图像处理它们（因为它们更容易/更小待处理）。

So actually descriptors describe the image, using less information that the whole image (because when you have 1 billion images, the size matters). They serve as the image's representatives, so we are processing them on behalf of the image (since they are easier/smaller to treat).

您提到的问题是最近邻居 问题。请注意，当D很大时（ kd-tree 非常慢，N（点数）几乎是线性的。）

The problem you are mentioning is the Nearest Neighbor problem. Notice that an approximate version of this problem can lead to significant speed ups, when D is big (since the curse of dimensionality will make the traditional approaches, such as a kd-tree very slow, almost linear in N (number of points)).

解决NN问题的算法通常是通用的，这是一个优化问题。他们可能不在乎数据是图像，分子等，例如我使用了我的 kd-两者都是GeRaF 。因此，算法期望D维空间中的N个点，因此您可能想要说N个描述符。

Algorithms that solve the NN problem, which is a problem of optimization, are usually generic. They may not care if the data are images, molecules, etc., I for example have used my kd-GeRaF for both. As a result, the algorithms expect N points in a D dimensional space, so N descriptors you might want to say.

检查我的答案LSH 此处（指向一个很好的实现）。

Check my answer for LSH here (which points to a nice implementation).

编辑：

LSH期望输入 D 维度的 N 向量并给出查询向量（在 D 中）并且范围 R ，将从查询向量中找到位于此范围内的向量。

LSH expects as input N vectors of D dimension and given a query vector (in D) and a range R, will find the vectors that lie within this range from the query vector.

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

As a result, we can say that every image is represented by just one vector, in SIFT format for example.

你看，LSH实际上并没有直接解决k-NN问题，而是在一个范围内进行搜索（ d可以给你k-NN，如果他们在范围内）。有关R的更多信息，请参阅实验部分，高维近似最近的邻居。 kd-GeRaF 和 FLANN 直接解决了k-NN问题。

You see, LSH doesn't actually solve the k-NN problem directly, but it searches within a range (and can give you the k-NNs, if they are withing the range). Read more about R, in the Experiments section, High-dimensional approximate nearest neighbo. kd-GeRaF and FLANN solve directly the k-NN problem.

这篇关于Locality Sensitivy Hashing在OpenCV中进行图像处理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！