文章/答案/技术大牛

发布

社区首页 >问答首页 >为数以百万计的图片做索引？

问为数以百万计的图片做索引？
EN

Stack Overflow用户

提问于 2012-03-14 06:19:32

回答 4查看 7.8K关注 0票数 23

这是来自Frank的lib谜libray ( http://libpuzzle.pureftpd.org/project/libpuzzle )。我试图了解如何在mysql数据库中索引和存储数据。矢量的生成是绝对没有问题的。

示例：

# Compute signatures for two images
$cvec1 = puzzle_fill_cvec_from_file('img1.jpg');
$cvec2 = puzzle_fill_cvec_from_file('img2.jpg');

# Compute the distance between both signatures
$d = puzzle_vector_normalized_distance($cvec1, $cvec2);

# Are pictures similar?
if ($d < PUZZLE_CVEC_SIMILARITY_LOWER_THRESHOLD) {
  echo "Pictures are looking similar\n";
} else {
  echo "Pictures are different, distance=$d\n";
}

这一切对我来说都很清楚--但是现在当我有大量的图片>1.000.000时，我该如何工作呢？我计算向量并将其存储在数据库中的文件名中？现在怎样才能找到类似的图片？如果我将每个向量存储在mysql中，则必须打开每条记录并使用puzzle_vector_normalized_distance函数计算距离。该过程花费大量时间(打开每个数据库条目-将其抛出函数，.)

我从libaray的lib益智中阅读了自述文件，并发现了以下内容：

它能与拥有数百万张图片的数据库一起工作吗？一个典型的图像签名只需要182个字节，使用内置的压缩/解压缩功能。类似的签名有相同的“单词”。相同位置的相同值序列。通过使用复合索引(word + position)，极大地减少了可能的相似向量集，而且在大多数情况下，实际上不需要计算向量距离。通过单词和位置进行索引还可以轻松地将数据拆分为多个表和服务器。所以是的，谜团库当然不是与需要索引数百万张图片的项目不兼容的。

此外，我还找到了关于索引的描述：

如何快速找到类似的图片，如果他们是数百万的记录？原来的论文有一个简单而有效的答案。把向量切成固定长度的字。例如，让我们考虑以下向量： A b，c，d，f，g，h，i，k，l，n，p，q，r，s，t，v，w，x，y，z 如果单词长度(K)为10，则可以得到以下单词： A b、c d e f g h h i j在位置0 b c d e f h h j j k处发现，在位置1 c d f g h i j k找到位置2等，直到N-1位置。然后，用复合索引(word + position)索引向量。即使有数以百万计的图像，K= 10和N= 100也足以使很少的条目共享相同的索引。下面是一个非常基本的示例数据库模式：

+-----------------------------+
| signatures |
+-----------------------------+
| sig_id | signature | pic_id |
+--------+-----------+--------+

+--------------------------+
| words |
+--------------------------+
| pos_and_word | fk_sig_id |
+--------------+-----------+

我建议至少将“word”表拆分为多个表和/或服务器。默认情况下(lambas=9)签名长度为544字节。为了节省存储空间，可以通过puzzle_compress_cvec()函数将它们压缩到原来大小的三分之一。在使用之前，必须用puzzle_uncompress_cvec()对它们进行解压缩。

我认为压缩是错误的，因为在比较之前，我必须先解压缩每个向量。

我现在的问题是，如何处理数百万张图片，以及如何快速、高效地比较它们。我不明白“向量的切割”如何帮助我解决我的问题。

非常感谢--也许我能在这里找到一个人，它正在和lib谜libaray合作。

干杯。

php

mysql

compare

similarity

image

回答 4

Stack Overflow用户

发布于 2012-03-19 17:34:38

那么，让我们来看看他们给出的例子，并尝试展开。

假设您有一个存储与每个图像(路径、名称、描述等)相关的信息的表。在该表中，您将包含一个用于压缩签名的字段，在初始填充数据库时计算和存储该字段。让我们这样定义该表：

CREATE TABLE images (
    image_id INTEGER NOT NULL PRIMARY KEY,
    name TEXT,
    description TEXT,
    file_path TEXT NOT NULL,
    url_path TEXT NOT NULL,
    signature TEXT NOT NULL
);

在最初计算签名时，还需要计算签名中的一些单词：

// this will be run once for each image:
$cvec = puzzle_fill_cvec_from_file('img1.jpg');
$words = array();
$wordlen = 10; // this is $k from the example
$wordcnt = 100; // this is $n from the example
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) {
    $words[] = substr($cvec, $i, $wordlen);
}

现在，您可以将这些单词放入表中，定义如下：

CREATE TABLE img_sig_words (
    image_id INTEGER NOT NULL,
    sig_word TEXT NOT NULL,
    FOREIGN KEY (image_id) REFERENCES images (image_id),
    INDEX (image_id, sig_word)
);

现在，在该表中插入单词所在位置的位置索引，以便您知道某个单词何时匹配它在签名中的相同位置：

// the signature, along with all other data, has already been inserted into the images
// table, and $image_id has been populated with the resulting primary key
foreach ($words as $index => $word) {
    $sig_word = $index.'__'.$word;
    $dbobj->query("INSERT INTO img_sig_words (image_id, sig_word) VALUES ($image_id,
        '$sig_word')"); // figure a suitably defined db abstraction layer...
}

因此，您的数据初始化后，可以相对轻松地获取具有匹配单词的图像：

// $image_id is set to the base image that you are trying to find matches to
$dbobj->query("SELECT i.*, COUNT(isw.sig_word) as strength FROM images i JOIN img_sig_words
    isw ON i.image_id = isw.image_id JOIN img_sig_words isw_search ON isw.sig_word =
    isw_search.sig_word AND isw.image_id != isw_search.image_id WHERE
    isw_search.image_id = $image_id GROUP BY i.image_id, i.name, i.description,
    i.file_path, i.url_path, i.signature ORDER BY strength DESC");

您可以通过添加一个需要最小HAVING的strength子句来改进查询，从而进一步减少匹配集。

我不保证这是最有效的设置，但它应该是大致功能，以完成您正在寻找的东西。

基本上，以这种方式拆分和存储单词允许您进行粗略的距离检查，而不必对签名运行专门的函数。

票数 14

Stack Overflow用户

发布于 2012-03-14 07:28:17

我以前试过玩益智游戏-就像你一样。并没有真正开始一个适当的实施。也不清楚该怎么做。(由于缺乏时间，他放弃了这个项目-所以没有真正坚持下去)

无论如何，看看现在，我会尽力提供我的理解-也许我们之间可以解决它:)

查询使用两个阶段的进程-

首先使用words表。
1. 拿出“参考”的图像并计算出它的签名。
2. 想出它的组成词，
3. 请参阅words表，以查找所有可能的匹配。这可以使用数据库引擎的索引来进行高效的查询。
4. 编译所有sig_ids的列表。(将在3中得到一些副本。)

然后查阅签名表
1. 退出并解压缩所有可能的签名(因为您有一个预先筛选的列表，数量应该相对较少)
2. 使用puzzle_vector_normalized_distance计算出实际的距离。
3. 根据需要对结果进行排序和排序

(仅对签名表进行压缩)。字词仍未压缩，因此可以在其上快速查询)

词表是倒排索引的一种形式。实际上，我考虑使用https://stackoverflow.com/questions/tagged/sphinx代替words数据库表，因为这是专门设计为一个非常快速的倒排索引。

..。理论上说无论如何..。

票数 3

Stack Overflow用户

发布于 2014-11-02 00:46:51

我还在php中做lib谜的工作，并且对如何从图像签名生成单词有一些疑问。贾森上面的回答似乎是对的，但我对这部分有一个问题：

// this will be run once for each image:
$cvec = puzzle_fill_cvec_from_file('img1.jpg');
$words = array();
$wordlen = 10; // this is $k from the example
$wordcnt = 100; // this is $n from the example
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) {
    $words[] = substr($cvec, $i, $wordlen);
}