logo标签列表

使用kd树和最近邻搜索比较/匹配图像的工作原理是什么？

computational-geometrynearest-neighborsiftkdtree
3
我一直在搜索关于kd-trees和图像比较的材料，但我无法将使用kd-trees进行图像比较的技术联系起来。首先，我找到了一些关于使用随机kd-trees提高速度的文章，然后介绍了SIFT。在基本理解SIFT的工作原理之后，我阅读了最近邻搜索的相关内容。
我的真正问题是：如果我有一个由SIFT中的点组成的网格，然后为每个图像创建kd-tree，最近邻搜索如何帮助我比较图像？起初，我认为使用树进行图像比较会使用某种算法检查树结构，以及同一节点中从图像A到图像B的每个点的距离有多近。
如果这个问题太愚蠢，请建议一些搜索材料或主题。
谢谢！
我和你一样对于kdtree、sift、surf等方面感到困惑，我认为我们可以通过Google Talk或其他方式联系并讨论。请在http://codepad.org/TmazIhsY与我联系 :) - Wiliam
3个回答
8

我建议首先理解缓慢的特征匹配，不需要使用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数字。） Kdtree是一种快速查找附近向量的方法；它与匹配的内容（表示数字的向量）以及如何匹配（欧几里得距离）无关。现在，对于2d、3d...可能高达20d的数据，kdtrees非常快，但在超过20d的数据上，可能不比线性扫描更快。那么如何使kdtree适用于128d的特征？主要的技巧是尽早停止搜索。Muja和Lowe在2009年的论文Fast approximate nearest neighbors with automatic algorithm configuration中描述了多个随机的kdtrees，用于匹配128d的SIFT特征。（Lowe是SIFT的发明者。）
为了比较两张图片I和Q，需要为每一张找到一组特征向量--几百到几千个SIFT向量--并寻找这些集合的近似匹配。 （可以将图像视为分子，特征视为原子；近似匹配分子比近似匹配原子要困难得多，但快速匹配原子是有帮助的。）希望这可以帮到你。
0
我建议您提取每个图像的颜色代码值，并使用这些特征向量创建KD树。
您可以使用以下Matlab代码提取颜色代码特征。
im = imread('image.jpg');

len = size(im,3);
if(len == 1)
    im = ind2rgb(im, colourMap);
    im = uint8(im.*255);
end

im(logical(  0 <= im & im <=  63)) = 0;
im(logical( 64 <= im & im <= 127)) = 1;
im(logical(128 <= im & im <= 191)) = 2;
im(logical(192 <= im & im <= 255)) = 3;
im = im(:,:,1) * 16 + im(:,:,2) * 4 + im(:,:,3);

imHist = histc(im(:),0:63);
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接