computational-geometry - 它如何使用 kd 树和最近邻搜索来比较/匹配图像？

Question

我一直在向谷歌查询有关 kd-trees 和图像比较的一些 Material ，但我无法在使用 kd-trees 的图像比较技术之间建立“链接”。
首先，我发现了一些关于使用随机 kd 树提高速度的文章，然后我被介绍了 SIFT。在基本了解 SIFT 的工作原理后，我阅读了最近邻搜索。

我真正的问题是:如果我有来自 SIFT 的点网格，那么我会为每个图像创建 kd 树。最近邻搜索如何帮助我比较图像？起初，我认为将图像与树进行比较可以使用一些算法来检查树结构以及每个点与图像 A 和图像 B 中同一节点中的点的距离。

如果问题太愚蠢，请建议 Material 或一些搜索主题。

谢谢!

Answer 1

我建议先了解慢速特征匹配，没有 kdtrees。

输入:1000 个引用特征，例如脸或花；调用这些 F1 .. F1000

查询特征 Q:哪个脸或花特征最像，最近，Q？

如你所知，
SIFT
将图像特征减少到 128 个 8 位数字，缩放以便
相似度(特征 F，特征 Q)=
欧氏距离(SIFT(F), SIFT(Q))。

找出 F1 .. F1000 中哪个最像 Q 的最简单方法
就是看F1、F2……一个一个:

# find the feature of F1 .. F1000 nearest Q
nearestdistance = infinity
nearestindex = 0
for j in 1 .. 1000:
    distance = Euclideandistance( SIFT(Fj), SIFT(Q) )  # 128 numbers vs. 128 numbers
    if distance < nearestdistance:
        nearestdistance = distance
        nearestindex = j

(当然可以在循环外计算 SIFT 数。)

A Kdtree
只是一种快速查找附近向量的方法；
它与匹配的内容无关
(代表...的数字向量)，或如何(欧几里得距离)。
现在 kdtrees 对于 2d、3d 来说非常快......最多可能是 20d，
但可能不会比对 20d 以上的所有数据进行线性扫描快。
那么 kdtree 如何处理 128d 中的功能呢？
主要技巧是尽早停止搜索。
Muja 和 Lowe 的论文，
Fast approximate nearest neighbors with automatic algorithm configuration ,
2009, 10p，描述了用于匹配 128d SIFT 特征的多个随机 kdtree。
(Lowe 是 SIFT 的发明者。)

为了比较两个图像 I 和 Q，找到一组特征向量——
几百到几千个 SIFT 向量——对于每个向量，
并寻找这些集合的接近匹配。
(人们可能将图像视为分子，将特征视为原子；
接近匹配的分子比接近匹配的原子更难，
但它有助于快速匹配原子。)

希望这可以帮助。