opencv - 在 OpenCV 中实现词汇树

Question

我正在尝试基于论文“Scalable Recognition with a Vocabulary Tree”实现图像搜索。我正在使用 SURF 来提取特征和关键点。例如，对于一张图像，我说有 300 个关键点，每个关键点有 128 个描述符值。我的问题是如何在数据上应用 K-Means 聚类算法。我的意思是我是否需要在所有点上应用聚类算法，即 300*128 值，或者我是否需要找到连续描述符值之间的距离并存储这些值并在其上应用聚类算法。我很困惑，我们将不胜感激。

谢谢，洛基。

Answer 1

从你的问题来看，我会说你很困惑。词汇树技术基于 k 均值层次聚类和叶节点 TF-IDF 加权方案的使用。

简而言之，用于构建词汇树的聚类算法对所有 d-dimensional 数据(对于 SIFT 的情况为 d=128)运行一次 k-means，然后对每个获得的集群再次运行 k-means 直到某个深度级别.因此，构建词汇树的两个主要参数是分支因子 k 和树深度 L。一些改进仅考虑分支因子，而深度是通过切割树自动确定的，以满足最小方差测量。

至于实现，来自 OpenCV 的 cv::BOWTrainer 是一个很好的起点，但对于分层 BoW 方案的情况不是很好地概括，因为它强制将中心存储在一个简单的 cv::Mat 中，而词汇树通常是不平衡的和映射当节点数远低于深度为 L 和分支因子为 k 的平衡树中的理论节点数时，从内存使用的角度来看，它以逐级方式转换为矩阵可能效率不高，即:

n << (1-k^L)/(1-k)