3

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

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

如果问题太愚蠢，请提出材料或一些搜索主题。

谢谢！

4

3 回答 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 只是一种快速查找附近向量的方法；它与匹配的内容（表示...的数字向量）或如何匹配（欧几里得距离）几乎没有关系。现在 kdtrees 对于 2d、3d ... 最多可能 20d 非常快，但可能不会比对 20d 以上所有数据的线性扫描快。那么 kdtree 如何为 128d 中的功能工作？主要技巧是尽早退出搜索。Muja 和 Lowe 的论文， 使用自动算法配置的快速近似最近邻， 2009，10p，描述了用于匹配 128d SIFT 特征的多个随机 kdtree。（Lowe 是 SIFT 的发明者。）

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

希望这可以帮助。

于 2011-04-19T15:16:43.740 回答
0

如果您计划使用 kd-trees 进行更高维度的近似 NN 搜索，您可能需要在此处查看实验：http: //zach.in.tu-clausthal.de/software/approximate_nn/

于 2011-07-13T15:57:15.107 回答
0

我建议您提取每个图像的颜色代码值并使用这些特征向量创建一个 KD 树。

您可以使用以下 mat lab 代码来提取颜色代码特征。

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);
于 2013-02-13T05:15:24.040 回答