如何在基于 Hierarchical K-Means 的 Bag-of-Features 模型中实现全词数？

信息处理 计算机视觉 机器学习
2022-02-04 22:10:03

我正在实现一个使用词汇树的基线系统，即基于 HKM 的 BoF 模型，用于图像分类。目前，由于 HKM 导致的量化结构质量差，我正在获得低质量的识别。

我在深度为 6 和分支因子为 10 的树中的最终词汇表中获得了 100.000 个单词，其中理论单词数为 10^6 = 1'000.000

在几篇论文中，比如 Zisserman 的与大规模地标识别相关的论文，他们声称使用了 1'000.000 个单词的词汇，我发现这很难理解，因为这个数字是理论上的，而在实践中并不能保证获得它。

我理解错了吗？如果没有，尽管使用更多描述符来训练树，我应该怎么做才能增加词汇量？

PS：到目前为止，我唯一的提示是使用不同的播种算法进行集群初始化，例如 k-means++ 或 gonzales

谢谢，欢迎任何建议。

阅读@penelope 的回答后，我回来报告我的发现。我构建词汇树的实现配置是：深度 6，分支因子 10，最多 10 次迭代和随机播种。

解决一些问题：

  • 早期阶段人口严重不足的集群：我检查了第一层的集群，它们分布均匀，例如第一个集群通常占整个集群的 10%。

  • K-means 终止标准：我正在运行聚类过程，直到收敛或达到 10 次迭代。我从 Neister 2006 的实验中获取了这个参数，在该实验中，性能不会提高超过 12 次迭代，而这样做可能会影响整个算法的持续时间。

  • 特征空间的均匀覆盖：我正在使用随机选择播种中心，正如我在问题中所说，使用其他算法（如 k-means++ 或 gonzalez）将成为特征空间的更均匀覆盖。

  • 训练特征的数量应该比预期的集群数量大得多：“预期的集群数量”我理解“预期的词数”，既然如此，这很可能是我的问题的根本原因。我正在使用 300 万个描述符训练一个 100 万个单词的词汇表，而 Zisserman 的实验使用来自 Oxford Buildings 数据集的约 1700 万个描述符，而 Marc Pollefeys 团队的实验使用来自 San Francisco Landmark 数据集的约 1600 万个描述符。

  • 配对几个检测器和描述符：我有一个限制，就是将我使用二进制特征的方法与使用 DoG/MSER 和 SIFT 描述符的基线进行比较。在不久的将来，我计划使用其他检测器（如 AGAST）来评估性能，这些检测器会产生更多与 DoG 产生的质量相似的关键点。

  • HKM 终止条件：在@penelope 的回答中提到，获得预期大小的词汇树不是问题。我想知道这样的事情是否真的可能，并开始考虑 HKM 的终止条件。在我的实现中，它们是：

    • 达到最后一层。
    • 数据比集群少。
    • 在聚类初始化时获得彼此太近的中心，因此它们很有可能代表同一个词，因此不是很独特。

    前两个条件是足够和必要的，但第三个不是，我把它包括在内是因为词汇可能会导致更加独特，至少在理论上是这样。我从 OpenCV 中的分层 k-means 索引实现中借用了它。拆下来方便吗？

2个回答

不幸的是，我认为导致问题的原因很可能是您用于构建树的训练图像集。（或者，更一般地说，您正在处理的数据库）。由于无法检查具体图像，我只能给出一些模糊的猜测。

首先，我会通过简单地检查树并查看第一个分支来诊断它哪里出错了，这些分支变得严重不足，因此在较低级别不再分支。我会看看这些功能，然后……想想。但是，由于我没有你的数据集，所以我实际上不能这样做，让我进一步尝试。

如果你担心是 K-means 出了问题，不是因为特征不是（或多或少）均匀分布在特征空间上，而仅仅是因为算法的工作方式，在实现之前更高级的算法，您可能首先尝试为每个分支运行 K-means 多次并选择最佳结果（例如，将特征空间划分为最相等部分的结果）。这对于最终实现来说可能太慢了，但它可能是诊断问题的一种快速、省力的方法。

我想说，为了让 HKM 工作，您的初始特征数量应该比预期的集群数量大几个数量级。所以，如果不是这样，你就知道你做错了什么。我不知道多少就足够了，但我会说最低限度100次，但至少更好1000比预期集群多出几倍的特征。这可能是由两个（相关）问题引起的：

  • 也许您的训练集太小，或者它可能是数据库的错误表示，包含太相似的图像？尝试增加训练集的大小，也许（仅出于测试目的）通过选择非常不同的代表性图像来挑选训练集。

  • 也许您的特征检测器在您使用的图像集上表现不佳。对于某些图像，某些检测器无法检测到足够的特征。有问题的图像通常包含大的单色区域（例如白墙、蓝天）。尝试组合几个特征检测器。（例如，在我的论文中，我使用的是 DoG 和 MSER 功能）。您始终可以这样做，因为您最终可以使用相同的描述符描述来自多个检测器的所有特征。

不幸的是，基于这么少的信息，我想不出更多的想法。有时您可能只是有一个实现错误。我知道这并不容易，也不是最有帮助的诊断，但作为实际实施了这样一个 CBIR 系统的人，我必须告诉你，我在构建预期大小的词汇树时从来没有遇到任何问题。

如果您提供更多信息、更新或其他任何信息，我可以尝试考虑其他可能出错的方法。在那之前，我希望这会有所帮助。

经过长时间检查我的代码，我发现了我的问题的根本原因，对树深度的误解。我将节点的根计算为一个级别，因此当将深度设置为 6 时，我期望获得 1M 字，但我最多只能获得 100K。

到目前为止，在使用完整数据集的最佳运行中，我获得了 997.228 个单词，这是一个比之前更合理的数字，因为无法保证获得完整的词汇量。

作为旁注，我尝试删除太接近的描述符终止条件，但性能下降，表明它可能会导致更具辨别力的词汇表。

其它你可能感兴趣的问题
上一篇STFT 中的零填充 下一篇对于大量类，什么是好的分类算法？