3

我们使用 libpuzzle ( http://www.pureftpd.org/project/libpuzzle/doc ) 来比较 400 万张图像的相似性。

它工作得很好。

但不是使用 libpuzzle 函数进行图像与图像比较，还有另一种比较图像的方法。

这是一些快速背景：

Libpuzzle 为任何给定图像创建一个相当小的（544 字节）散列。这个散列又可以用来与使用 libpuzzles 函数的其他散列进行比较。有一些 API……PHP、C 等等……我们正在使用 PHP API。

比较图像的另一种方法是从给定的哈希创建向量，这是来自文档的粘贴：

将向量切割成固定长度的单词。例如，让我们考虑以下向量：

[ abcdefghijklmnopqrstu vwxyz ]

词长（K）为10，可以得到以下词：

[ abcdefghij ] 在位置 0 找到 [ bcdefghijk ] 在位置 1 找到 [ cdefghijkl ] 在位置 2 找到，依此类推，直到位置 N-1

然后，使用（单词+位置）的复合索引索引您的向量。

即使有数百万张图像，K = 10 和 N = 100 也应该足以让很少的条目共享相同的索引。

所以，我们有矢量方法工作。它实际上比图像与图像比较好一点，因为当我们进行图像与图像比较时，我们使用其他数据来减少我们的样本量。它有点无关紧要，并且特定于应用程序我们使用什么其他数据来减少样本量，但是使用向量方法......我们不必这样做，我们可以对 400 万个哈希中的每一个进行真正的测试.

我们遇到的问题如下：

有 400 万张图像，每张图像有 100 个向量，这变成了 4 亿行。我们发现 MySQL 在大约 60000 张图像（60000 x 100 = 600 万行）之后往往会阻塞。

我们使用的查询如下：

SELECT isw.itemid, COUNT(isw.word) as strength
FROM vectors isw
JOIN vectors isw_search ON isw.word = isw_search.word
WHERE isw_search.itemid = {ITEM ID TO COMPARE AGAINST ALL OTHER ENTRIES}
GROUP BY isw.itemid;

如前所述，即使有适当的索引，当涉及到 4 亿行时，上面的速度也相当慢。

那么，任何人都可以建议任何其他技术/算法来测试这些相似性吗？

我们愿意试一试。

一些值得一提的事情：

  1. 哈希是二进制的。
  2. 哈希总是相同的长度，544 字节。

我们能想到的最好的是：

  1. 将图像哈希从二进制转换为 ascii。
  2. 创建向量。
  3. 如下创建一个字符串：VECTOR1 VECTOR2 VECTOR3 等。
  4. 使用狮身人面像搜索。

我们还没有尝试上述方法，但这可能会比执行 mysql 查询产生更好的结果。

有任何想法吗？如前所述，我们愿意安装任何新服务（postgresql？hadoop？）。

最后一点，这个向量+比较方法的工作原理可以在问题Libpuzzle索引数百万张图片中找到？. 我们本质上是使用 Jason 提供的精确方法（目前是最后一个答案，获得了 200+ 分）。

4

2 回答 2

0

我选择“回答我自己的”问题，因为我们找到了一个非常有效的解决方案。

在最初的问题中，我提到我们正在考虑通过 sphinx 搜索来做到这一点。

好吧，我们继续做了，结果比通过 mysql 做的要好得多。

所以，本质上这个过程是这样的：

a) 从图像生成哈希。

b) 将此哈希“向量化”为 100 个部分。

c) binhex（二进制到十六进制）这些向量中的每一个，因为它们是二进制格式。

d）像这样存储在狮身人面像搜索中：

项目编号 | 0_vector0 1_vector1 2_vec...等

e) 使用 sphinx 搜索进行搜索。

最初……一旦我们有了这个包含 400 万条记录的 sphinxbase，每次搜索仍然需要大约 1 秒。

然后，我们在 8 个内核上为这个 sphinxbase 启用了分布式索引，现在每秒将查询大约 10 次以上的搜索。这对我们来说已经足够了。

最后一步是在我们拥有的多台服务器上进一步分发这个 sphinxbase，进一步利用我们可用的未使用的 cpu 周期。

但就目前而言，已经足够好了。我们每天添加大约 1000-2000 个“项目”，因此通过“只是新的”搜索会很快发生......在我们进行初始扫描之后。

于 2013-03-31T15:03:36.747 回答
0

不要在数据库中这样做，只需使用一个简单的文件。下面我展示了一个文件，其中包含两个向量[abcdefghijklmnopqrst]（图 1）和[xxcdefghijklxxxxxxxx]（图 2）中的一些单词

 <index>       <image>
0abcdefghij      1
1bcdefghijk      1
2cdefghijkl      1
3defghijklm      1
4efghijklmn      1
...
...
0xxcdefghij      2
1xcdefghijk      2
2cdefghijkl      2
3defghijklx      2
4efghijklxx      2
...

现在对文件进行排序：

  <index>       <image>
0abcdefghij      1
0xxcdefghij      2
1bcdefghijk      1
1xcdefghijk      2
2cdefghijkl      1       
2cdefghijkl      2       <= the index is repeated, those we have a match
3defghijklm      1
3defghijklx      2
4efghijklmn      1
4efghijklxx      2

对文件进行排序后，很容易找到具有相同索引的记录。编写一个小程序或可以在排序列表中运行并找到重复项的东西。

于 2013-03-30T13:58:58.440 回答