18

我目前正在扩展一个用于对图像进行分类的图像库，并且我想查找重复图像、转换图像以及包含或包含在其他图像中的图像。
我已经测试了 OpenCV 的 SIFT 实现，它工作得很好，但对于多个图像来说会相当慢。太快了，我想我可以提取特征并将它们保存在数据库中，因为许多其他与图像相关的元数据已经保存在那里。

将新图像的特征与数据库中的特征进行比较的最快方法是什么？
通常比较是使用 kd-trees、FLANN 或我在 SO 上的另一个线程中找到的Pyramid Match Kernel来计算欧几里得距离，但还没有深入研究。

由于我不知道如何有效地在数据库中保存和搜索 kd-tree，因此我目前只看到三个选项：
* 让 MySQL 计算到数据库中每个特征的欧几里德距离，尽管我很确定这将花费不合理的时间来处理多个图像。
* 在开始时将整个数据集加载到内存中并构建 kd-tree(s)。这可能会很快，但非常占用内存。另外，所有数据都需要从数据库中传输。
* 将生成的树保存到数据库中并加载所有这些树，这将是最快的方法，但也会产生大量流量，因为对于新图像，kd-trees 必须重建并发送到服务器。

我正在使用 OpenCV 的 SIFT 实现，但我并没有死心塌地。如果有一个更适合这项任务的特征提取器（并且大致同样健壮），我很高兴有人能推荐一个。

4

4 回答 4

15

所以几年前我基本上做了一些与此非常相似的事情。 您想要研究的算法是几年前由 David Nister 提出的，论文是：“Scalable Recognition with a Vocabulary Tree”。他们几乎可以为您的问题提供精确的解决方案，可以扩展到数百万张图像。

这是摘要的链接，您可以通过谷歌搜索标题找到下载链接。 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

基本思想是用分层k-means算法构建一棵树来对特征进行建模，然后利用该树中特征的稀疏分布来快速找到你最近的邻居......或者类似的东西，已经有几年了我正在研究它。您可以在此处的作者网页上找到 powerpoint 演示文稿：http: //www.vis.uky.edu/~dnister/Publications/publications.html

其他一些注意事项：

  • 我不会为金字塔匹配内核而烦恼，它实际上更多的是用于改进对象识别而不是重复/转换图像检测。

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

  • SQL 数据库不是为进行大规模浮点向量计算而设计的。 您可以将事物存储在数据库中，但不要将其用作计算工具。 我用 SQLite 试过一次，结果很糟糕。

  • 如果您决定实现这一点，请详细阅读论文并在实现时保留一份副本，因为有许多小细节对于使算法有效工作非常重要。

于 2010-08-19T17:53:55.970 回答
2

我认为，关键在于这不是一个 SIFT 问题。这是一个关于近似最近邻搜索的问题。就像图像匹配一样，这也是一个开放的研究问题。您可以尝试使用谷歌搜索“近似最近邻搜索”并查看可用的方法类型。如果您需要精确的结果，请尝试：“精确最近邻搜索”。

所有这些几何数据结构（例如 kd-trees）的性能随着维度数量的增加而下降，所以我认为关键是您可能需要以较少的维度表示您的 SIFT 描述符（例如 10-30 256-1024) 进行真正有效的最近邻搜索（例如使用 PCA）。

一旦你有了这个，我认为无论数据是否存储在 MySQL 中，它都会成为次要的。

于 2010-08-18T13:29:12.037 回答
1

我认为速度不是这里的主要问题。主要问题是如何使用这些功能来获得您想要的结果。

如果你想对图像进行分类（例如人、车、房子、猫），那么 Pyramid Match 内核绝对值得一看。它实际上是局部特征描述符的直方图，因此无需将各个特征相互比较。还有一类算法被称为“词袋”，它试图将局部特征聚类，形成“视觉词汇表”。同样，在这种情况下，一旦有了“视觉词”，您就不需要计算所有 SIFT 描述符对之间的距离，而是确定每个特征属于哪个集群。另一方面，如果你想获得图像对之间的点对应关系，例如决定一个图像是否包含在另一个图像中，或者计算图像之间的变换，

此外，还有除 SIFT 之外的本地特征。例如，SURF 是类似于 SIFT 的特征，但提取速度更快，并且已被证明在某些任务中表现更好。

如果您只想查找重复项，则可以通过使用全局图像描述符（例如颜色直方图）来删除明显不同的图像，从而大大加快搜索速度。比较两个颜色直方图比比较两个包含数百个 SIFT 特征的集合快几个数量级。您可以使用颜色直方图创建一个简短的候选列表，然后使用 SIFT 优化您的搜索。

于 2010-08-18T15:56:39.513 回答
1

I have some tools in python you can play with here . Basically its a package that uses SIFT transformed vectors, and then computes a nearest lattice hashing of each 128d sift vector. The hashing is the important part, as it is locality sensitive, simply meaning that vectors near in R^n space result in equivalent hash collision probabilities. The work I provide is an extension of Andoni that provides a query adaptive heuristic for pruning the LSH exact search lists, as well as an optimized CUDA implementation of the hashing function. I also have a small app that does image database search with nice visual feedback, all under bsd (exception is SIFT which has some additional restrictions).

于 2011-12-20T19:23:14.990 回答