SIFT描述子匹配的高效方法

Question

有两张图片A和B，我从中提取了关键点（a[i]和b[i]）。

我想知道如何高效地确定a[i]和b[j]之间的匹配？显而易见的方法是将A中的每个点与B中的每个点进行比较。但对于大型图像数据库来说，这样做太耗时了。我应该如何仅将点a[i]与范围较小的b[k]进行比较？

我听说kd-tree可能是一个不错的选择，是吗？有没有关于kd-tree的好例子？

还有其他建议吗？

- vancexu

---

kd-tree本身对于像SIFT这样高维度的描述符并不高效（这被称为维数灾难）。然而，在高维空间中存在其他逼近最近邻搜索的索引策略。其中之一是OpenCV中包含的FLANN。还有一种使用FLANN进行关键点匹配的实现，可以查看我的回答中的链接。 - remi

Answer 1

KD树以一种快速的方式存储了训练好的描述符，这使得在执行匹配时查找最相似的描述符变得更加高效。

使用OpenCV很容易使用kd-tree，我将为您提供flann匹配器的示例：

flann::GenericIndex< cvflann::L2<int> >  *tree; // the flann searching tree
tree = new flann::GenericIndex< cvflann::L2<int> >(descriptors, cvflann::KDTreeIndexParams(4)); // a 4 k-d tree

然后，当你进行匹配时：

const cvflann::SearchParams params(32);
tree.knnSearch(queryDescriptors, indices, dists, 2, cvflann::SearchParams(8));

- Jav_Rock

---

当您标记应该是评论或仅为链接的答案时，请将它们标记为“不是答案”，而不是“非常低质量”，这有助于我们从工作流程的角度进行处理。但请继续标记，我们非常感谢！ - casperOne

Answer 2

问题是你是否想要在两张图片之间确定关键点匹配，还是计算相似性度量。

如果你想要确定匹配，那么恐怕你需要通过暴力搜索来查找两张图片之间所有可能的描述符对（还有一些更高级的方法，比如FLANN - 快速近似最近邻搜索，但如果每张图片只有不到或大约2000个关键点，速度提升并不显著--至少在我的经验中）。为了获得更准确的匹配（不是更快，而是更好的匹配），我可以建议你看看：

• D.G. Lowe. 不变尺度特征转换的独特图像特征--与第二个最接近匹配的比较
• J. Sivic和A. Zisserman。Video Google:一种文本检索方法用于视频对象匹配--关于空间一致性的部分

如果您只需要在一个大型数据库中进行相似度比较，那么开始的适当位置应该是：

• D. Nistér和H. Stewénius。使用一种称为vocabulary tree的结构的分层方法，以计算查询图像与来自大型数据库中的图像之间的相似度量。
• J. Sivic和A. Zisserman。视频Google：一种文本检索方法用于视频中的对象匹配 -- 与上述论文相同，但对于理解Nistér，Stewénius的方法非常有帮助。

- penelope

Answer 3

在OpenCV中，有几种策略用于匹配关键点集。请查看有关描述符匹配器的常见接口的文档。

- remi