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

发布于 2024-11-02 03:32:58 字数 307 浏览 7 评论 0原文

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

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

如果问题太愚蠢，请建议搜索材料或某些主题。

谢谢你！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

烟花肆意 2024-11-09 03:32:58

我建议首先了解慢速特征匹配，而不使用 kdtree。

输入：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
只是快速找到附近向量的一种方法；
它与匹配的内容关系不大
（代表...的数字向量），或如何（欧几里得距离）。
现在 kdtree 对于 2d、3d ... 可能达到 20d 非常快，
但可能不会比对 20d 以上的所有数据进行线性扫描更快。
那么 kdtree 如何处理 128d 中的特征呢？
主要技巧是尽早停止搜索。
Muja 和 Lowe 的论文，
具有自动算法配置的快速近似最近邻< /a>,
2009 年 10p，描述了用于匹配 128d SIFT 特征的多个随机 kdtree。
（Lowe 是 SIFT 的发明者。）

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

希望这会有所帮助。

I'd suggest first understanding slow feature matching, without kdtrees.

input: 1000 reference features, e.g. of faces or flowers; call these F1 .. F1000
a query feature Q: which face or flower feature is most like, nearest, Q ?

As you know,
SIFT
reduces an image feature to 128 8-bit numbers, scaled so that
similarity( feature F, feature Q ) =
Euclidean distance( SIFT(F), SIFT(Q) ).

The simplest way to find which of F1 .. F1000 is most like Q
is just to look at F1, F2 ... one by one:

# 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

(Of course one computes the SIFT numbers outside the loop.)

A Kdtree
is just a way of finding nearby vectors quickly;
it has little to do with what is being matched
(vectors of numbers representing ...), or how (Euclidean distance).
Now kdtrees are very fast for 2d, 3d ... up to perhaps 20d,
but may be no faster than a linear scan of all the data above 20d.
So how can a kdtree work for features in 128d ?
The main trick is to quit searching early.
The paper by Muja and Lowe,
Fast approximate nearest neighbors with automatic algorithm configuration,
2009, 10p, describes multiple randomized kdtrees for matching 128d SIFT features.
(Lowe is the inventor of SIFT.)

To compare two images I and Q, one finds a set of feature vectors --
several hundred up to a few thousand SIFT vectors -- for each,
and looks for near matches of these sets.
(One may think of images as molecules, features as atoms;
near-matching molecules is much harder than near-matching atoms,
but it helps to be able to match atoms quickly.)

Hope this helps.

回复收藏 0 原文

别低头，皇冠会掉 2024-11-09 03:32:58

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

回复收藏 0 原文

濫情▎り 2024-11-09 03:32:58

我建议您提取每个图像的颜色代码值并使用这些特征向量创建 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);

I suggest you to extract color code values of each image and create a KD tree using those features vectors.

You can use the following mat lab code to extract the color code features.

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 原文

~没有更多了~