如何将图像与kd-trees和最近邻搜索进行比较/匹配？

Question

我一直在向google查询有关kd-trees和图像比较的一些材料,但我无法在使用kd-trees进行图像比较的技术之间建立"链接".首先,我发现一些文章谈论随机kd树的速度提升,然后我被介绍给SIFT.在基本了解了SIFT如何工作之后,我读到了最近邻搜索.

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

如果问题太愚蠢,请提供材料或搜索​​主题.

谢谢!

Answer 1

我建议首先理解缓慢的特征匹配,没有kdtrees.

• 输入:1000个参考特征,例如面部或花朵; 叫这些F1 .. F1000
• 查询特征问:哪个面部或花卉特征最像,最近,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数.)

一个Kdtree 仅仅是一个快速查找附近的载体的方法; 它几乎没有做什么正在匹配(占...数字载体),或如何(欧氏距离).现在kdtree非常快2d,3d ......可能大约20d,但可能不比20d以上所有数据的线性扫描快.那么kdtree如何在128d中运行功能呢？主要技巧是尽早退出搜索.Muja和Lowe的文章, 具有自动算法配置的快速近似最近邻, 2009,10p,描述了用于匹配128d SIFT特征的多个随机化kdtrees.(Lowe是SIFT的发明者.)

为了比较两个图像I和Q,人们为每个图像找到一组特征向量 - 几百到几千个SIFT向量 - 并寻找这些集合的近似匹配.(人们可能认为图像作为分子,特征原子;近匹配分子是多比接近匹配原子困难,但它有助于能够快速匹配原子.)

希望这可以帮助.