比较存储在mysql数据库中的SIFT特征[英] Comparing SIFT features stored in a mysql database

本文是小编为大家收集整理的关于比较存储在mysql数据库中的SIFT特征的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。

问题描述

我目前正在扩展一个用于分类图像的图像库,我想查找重复的图像,转换的图像以及包含或包含在其他图像中的图像.
我已经测试了OPENCV的SIFT实现,它运行良好,但是对于多个图像来说,它的速度相当慢.我认为我可以提取这些功能并将其保存在数据库中,因为许多其他与图像相关的元数据已经保存在数据库中.

将新图像的功能与数据库中的功能进行比较的最快方法是什么?
通常进行比较,使用KD-Trees,Flann或使用金字塔匹配内核我在这里的另一个线程中发现,但还没有研究太多.

由于我不知道有效地保存和搜索KD-Tree的方法有效地,因此我目前只看到三个选项:
*让MySQL计算到数据库中的每个功能的欧几里得距离,尽管我敢肯定,这将花费不合理的时间用于几个图像.
*在开始时将整个数据集加载到内存中,并构建KD-Tree(S).这可能会很快,但记忆力很强.加上所有数据都需要从数据库传输.
*将生成的树保存到数据库中并加载所有这些树是最快的方法,但也会产生大量的流量,就像使用新图像一样,KD-Trees必须重建并发送到服务器.

.

我正在使用OpenCV的SIFT实现,但我还没有固定.如果有一个功能提取器更适合此任务(并且大致相同强大),我很高兴有人建议一个.

推荐答案

所以我基本上做了几年前与此相似的事情. 您想研究的算法是几年前由大卫·内斯特(David Nister)提出的,该论文是:"具有词汇树的可扩展识别".他们几乎对您的问题有一个精确的解决方案,可以扩展到数百万张图像.

这是指向摘要的链接,您可以通过谷歌标题找到下载链接.

基本思想是用层次k-means算法构建树木来建模功能,然后利用该树中特征的稀疏分布来快速找到您最近的邻居...或类似的东西,它是一个自从我工作以来几年.您可以在此处的作者网页上找到PowerPoint演示文稿: http://wwww. vis.uky.edu/~dnister/publications/publications.html

其他一些注释:

  • 我不会打扰金字塔匹配内核,它比重复/转换的图像检测实际上要改善对象识别.

  • 我不会将任何此功能的东西存储在SQL数据库中.根据您的应用程序,有时有时更有效地计算您的功能,因为它们的大小在密集计算时可能会超过原始图像大小.词汇树中的特征或指针的直方图更加有效.

  • SQL数据库不是为进行大规模浮点矢量计算而设计的. 您可以将内容存储在数据库中,但不要将其用作计算工具.我用SQLite尝试过一次,并且结束非常糟糕.

  • 如果您决定实施此功能,请详细阅读本文并在实施时方便地保持副本,因为有许多次要细节对于使算法有效工作非常重要.

其他推荐答案

我认为,这不是一个筛选问题.这是关于大约最近的邻居搜索的问题.像图像匹配的一样,也是一个开放的研究问题.您可以尝试谷歌搜索"近似最近的邻居搜索",并查看有哪些类型的方法可用.如果您需要确切的结果,请尝试:"确切的最近邻居搜索".

随着尺寸数量的增加,所有这些几何数据结构(例如KD-Trees)的性能降低了,因此我认为关键是您可能需要在较低的尺寸中表示您的SIFT描述符(例如10 -30而不是256-1024)具有真正有效的最近邻居搜索(例如使用PCA).

一旦您拥有这个数据,我认为如果数据存储在MySQL中.

其他推荐答案

我认为速度不是这里的主要问题.主要问题是如何使用功能获得所需的结果.

如果您想对图像进行分类(例如,人,汽车,房屋,猫),那么金字塔匹配内核绝对值得一看.它实际上是本地功能描述符的直方图,因此无需将单个功能彼此比较.还有一类称为"单词袋"的算法,它们试图聚集本地功能以形成"视觉词汇".同样,在这种情况下,一旦拥有"视觉单词",就无需计算所有对筛分描述符之间的距离,而是确定每个功能所属的群集.另一方面,如果要获得图像对之间的点对应关系,例如决定一个图像是否包含在另一个图像中,或计算图像之间的转换,那么您确实需要找到确切的最近邻居.<<<<<<<<<<<<<<<

此外,除了筛选外,还有其他本地功能.例如,冲浪是类似于SIFT的功能,但是它们的提取速度更快,并且已被证明可以在某些任务中表现更好.

如果您要做的就是找到重复项,则可以通过使用全局图像描述符(例如颜色直方图)来大大加快搜索的速度,以修剪明显不同的图像.比较两个颜色直方图的是比较两组包含数百个筛分特征的数量级.您可以使用颜色直方图创建一个简短的候选人列表,然后使用SIFT完善您的搜索.

本文地址:https://www.itbaoku.cn/post/597425.html

问题描述

I'm currently extending an image library used to categorize images and i want to find duplicate images, transformed images, and images that contain or are contained in other images.
I have tested the SIFT implementation from OpenCV and it works very well but would be rather slow for multiple images. Too speed it up I thought I could extract the features and save them in a database as a lot of other image related meta data is already being held there.

What would be the fastest way to compare the features of a new images to the features in the database?
Usually comparison is done calculating the euclidean distance using kd-trees, FLANN, or with the Pyramid Match Kernel that I found in another thread here on SO, but haven't looked much into yet.

Since I don't know of a way to save and search a kd-tree in a database efficiently, I'm currently only seeing three options:
* Let MySQL calculate the euclidean distance to every feature in the database, although I'm sure that that will take an unreasonable time for more than a few images.
* Load the entire dataset into memory at the beginning and build the kd-tree(s). This would probably be fast, but very memory intensive. Plus all the data would need to be transferred from the database.
* Saving the generated trees into the database and loading all of them, would be the fastest method but also generate high amounts of traffic as with new images the kd-trees would have to be rebuilt and send to the server.

I'm using the SIFT implementation of OpenCV, but I'm not dead set on it. If there is a feature extractor more suitable for this task (and roughly equally robust) I'm glad if someone could suggest one.

推荐答案

So I basically did something very similar to this a few years ago. The algorithm you want to look into was proposed a few years ago by David Nister, the paper is: "Scalable Recognition with a Vocabulary Tree". They pretty much have an exact solution to your problem that can scale to millions of images.

Here is a link to the abstract, you can find a download link by googleing the title. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

The basic idea is to build a tree with a hierarchical k-means algorithm to model the features and then leverage the sparse distribution of features in that tree to quickly find your nearest neighbors... or something like that, it's been a few years since I worked on it. You can find a powerpoint presentation on the authors webpage here: http://www.vis.uky.edu/~dnister/Publications/publications.html

A few other notes:

  • I wouldn't bother with the pyramid match kernel, it's really more for improving object recognition than duplicate/transformed image detection.

  • I would not store any of this feature stuff in an SQL database. Depending on your application it is sometimes more effective to compute your features on the fly since their size can exceed the original image size when computed densely. Histograms of features or pointers to nodes in a vocabulary tree are much more efficient.

  • SQL databases are not designed for doing massive floating point vector calculations. You can store things in your database, but don't use it as a tool for computation. I tried this once with SQLite and it ended very badly.

  • If you decide to implement this, read the paper in detail and keep a copy handy while implementing it, as there are many minor details that are very important to making the algorithm work efficiently.

其他推荐答案

The key, I think, is that is this isn't a SIFT question. It is a question about approximate nearest neighbor search. Like image matching this too is an open research problem. You can try googling "approximate nearest neighbor search" and see what type of methods are available. If you need exact results, try: "exact nearest neighbor search".

The performace of all these geometric data structures (such as kd-trees) degrade as the number of dimensions increase, so the key I think is that you may need to represent your SIFT descriptors in a lower number of dimensions (say 10-30 instead of 256-1024) to have really efficient nearest neighbor searches (use PCA for example).

Once you have this I think it will become secondary if the data is stored in MySQL or not.

其他推荐答案

I think speed is not the main issue here. The main issue is how to use the features to get the results you want.

If you want to categorize the images (e. g. person, car, house, cat), then the Pyramid Match kernel is definitely worth looking at. It is actually a histogram of the local feature descriptors, so there is no need to compare individual features to each other. There is also a class of algorithms known as the "bag of words", which try to cluster the local features to form a "visual vocabulary". Again, in this case once you have your "visual words" you do not need to compute distances between all pairs of SIFT descriptors, but instead determine which cluster each feature belongs to. On the other hand, if you want to get point correspondences between pairs of images, such as to decide whether one image is contained in another, or to compute the transformation between the images, then you do need to find the exact nearest neighbors.

Also, there are local features other than SIFT. For example SURF are features similar to SIFT, but they are faster to extract, and they have been shown to perform better for certain tasks.

If all you want to do is to find duplicates, you can speed up your search considerably by using a global image descriptor, such as a color histogram, to prune out images that are obviously different. Comparing two color histograms is orders of magnitude faster than comparing two sets each containing hundreds of SIFT features. You can create a short list of candidates using color histograms, and then refine your search using SIFT.