algorithm - 如何使用 Opencv 存储大量图像的分层 K-Means 树？

Question

我正在尝试制作一个程序，从图像数据集中找到相似的图像。步骤是

• 为所有图像提取 SURF 描述符
• 存储描述符
• 在存储的描述符上应用 knn
• 使用 kNN 将存储的描述符与查询图像描述符匹配

现在每个图像 SURF 描述符都将存储为分层 k-means 树，现在我是将每棵树存储为单独的文件还是可以构建某种具有所有图像描述符的单一树并在添加图像时更新到数据集。

This is the paper I am basing the program on.

Answer 1

您确定要使用 SURF 描述符吗？我自己正在开发一个类似的应用程序，它基于 this论文(Nister、Stewenius)，他们发誓 SIFT 描述符是必经之路。但是，我想您也可以使用任何其他描述符来做到这一点。

查看您引用的论文，它比我链接到的作品更新，但它没有引用 Nister paper或 this work (Sivic, Zisserman)，据我所知，这是解决所有基于内容的图像检索问题的基础。

为了更好地理解问题，在开始实现之前，我先阅读了Sivic, Zisserman了解系统背后的总体思路。他们仅在从所有特征中提取所有 SIFT 描述符后应用简单的聚类。他们使用两种不同类型的特征来提高准确性，Shape Adapted(以角落为中心的特征)和 Maximally Stable(对应于高对比度的 Blob - 您可以在 this 论文(Matas 等人)中查找它们)。他们的系统的可扩展性不是很好，因为每个特征都是直接存储的，但他们引入了倒排文件的概念，一种来自文本分析的技术(你可以阅读它的基础知识 here)，它简化了查找过程显着。

征服那项工作后，我建议继续Nister, Stewenius他们在 L 级引入了分层 k 均值聚类的概念，用于存储特征，以及用于图像数据库的后期搜索。现在，除非我非常非常错误，否则您不会将每个 描述符存储为单独的树。相反，您根据现有特征制作树(每个级别的聚类中心实际上是每个聚类的代表性“中心”特征)。一旦树被构造到所需的深度(他们推荐 10 个聚类超过 6 个级别)，最后一级的聚类中心代表极少数特征 - 因此，您实际上可以忘记所有原始特征! (或者至少，他们的描述符)。每个原始特征都可以由相应的聚类中心表示，而不是描述符，对于每个图像，您只需要存储有关它包含哪些聚类中心(特征)的信息。这要容易得多，因为您只需要为每个特征存储一个或两个整数 - 对其通过树的路径进行编码。查看它的最简单方法是，如果您只编码该特征在每个级别所属的集群的数量 - 有 10 个(4 位) - 对于每个级别(其中 6 个，4 * 6 < 32 位，所以它适合一个整数)。您当然可以以您认为合适的任何方式实现实际编码。哦，他们还在 MSER 区域使用 SIFT 描述符。

此外，如果您用于构建词汇树的图像具有代表性(例如，您正在处理开放空间图片的数据集，并且您仅从图像的代表性部分构建树，但您知道没有数据集其余部分的工业工厂工作场所图片)，您可以非常快速地添加新图片。要在数据集中添加任何新图片，您唯一需要做的就是确定哪个计算出的聚类中心最能代表图像特征(如前所述，最后一级聚类中心非常精确)并存储有关的信息聚类中心(前面提到的整数)。查找聚类中心应该非常快 - 在 6 个级别中的每个级别只有 10 个比较。

希望有一天这对某些人有用，因为这个问题已经存在一年多了。 :)