Feature Vector Partioning

Question

我在阅读关于图像搜索的内容，并且我已经到了对特征向量有基本理解的地方，并且对旋转不变和尺度不变特征有一个非常基本的（完全不完整的）理解。如何查看多采样图像的尺度不变性以及旋转不变性的角点。

要搜索十亿张图像，尽管您无法进行线性搜索。我读的大部分内容似乎都意味着K-d树被用作分区数据结构来改善查找时间。

K-d树分裂的是什么度量？如果使用SIFT，SURF或ORB等描述符，则不能保证类似的关键点在特征向量中排列，所以我很困惑如何确定'左'或'右'，因为使用这样的功能时，需要分割基于相似性。我的猜测是距离'标准'的欧式距离，然后你做一个可靠的最近邻居搜索，但是想知道如何在最近邻居搜索之前处理KD树中的初始查询。我认为KD树需要在每个维度上比较相似的特征，但我不知道在许多关键点上会发生什么。

我可以找到很多有关最近邻居搜索的论文，但大多数人似乎都假设你知道这是如何处理的，所以我在这里错过了一些东西。

Answer 1

这很简单。所有那些特征描述符都将图像作为多维空间中的一个点。只是为了简单起见，我们假设您的描述符维度为2.比您所有的图像将被映射到两个维度平面上。然后，kd-tree将这个平面分割成矩形区域。任何属于同一区域的图像都将被视为相似。

这意味着，顺便说一句，两个图像真的很接近，但在不同的区域（kd树的叶子）不会被认为是相似的。 为了克服这个问题，余弦相似性可以用来代替欧几里德距离。您可以在wiki中阅读有关该主题的更多信息。