image - 在 Elasticsearch 中通过 pHash 距离搜索相似图像

Question

相似图片搜索问题

数百万张图片 pHash 'ed 并存储在 Elasticsearch 中。

格式为“11001101...11”(长度为 64)，但可以更改(最好不要)。

给定主题图像的哈希“100111..10”，我们希望在 Elasticsearch 索引 中找到所有相似的图像哈希。在 8 的汉明距离内 .

当然，query 可以返回距离大于 8 的图像，并且 Elasticsearch 中或外部的脚本可以过滤结果集。但总搜索时间必须在 1 秒左右。

我们当前的映射

每个文档都嵌套了 images包含图像哈希的字段:

{
  "images": {
    "type": "nested", 
    "properties": {
      "pHashFingerprint": {"index": "not_analysed", "type": "string"}
    }
  }
}

我们糟糕的解决方案

事实: Elasticsearch 模糊查询仅支持最大 2 的 Levenshtein 距离。

我们使用自定义标记器将 64 位字符串分成 4 组 16 位，并使用四个模糊查询进行 4 组搜索。

分析器:

{
   "analysis": {
      "analyzer": {
         "split4_fingerprint_analyzer": {
            "type": "custom",
            "tokenizer": "split4_fingerprint_tokenizer"
         }
      },
      "tokenizer": {
         "split4_fingerprint_tokenizer": {
            "type": "pattern",
            "group": 0,
            "pattern": "([01]{16})"
         }
      }
   }
}

然后新建字段映射:

"index_analyzer": "split4_fingerprint_analyzer",

然后查询:

{
   "query": {
      "filtered": {
         "query": {
            "nested": {
               "path": "images",
               "query": {
                  "bool": {
                     "minimum_should_match": 2,
                     "should": [
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "0010100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "1010100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "0110100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "1110100100111001",
                                 "fuzziness": 2
                              }
                           }
                        }
                     ]
                  }
               }
            }
         },
         "filter": {}
      }
   }
}

请注意，我们返回具有匹配图像的文档，而不是图像本身，但这不应有太大变化。

问题是这个查询返回 数十万条结果 即使在添加其他特定于域的过滤器以减少初始设置之后。脚本有太多工作需要再次计算汉明距离，因此查询可能需要几分钟。

正如预期的那样，如果增加 minimum_should_match对于 3 和 4，只返回必须找到的图像子集，但结果集小而快。低于 95% 的所需图像返回 minimum_should_match == 3 但我们需要 100%(或 99.9%)，就像 minimum_should_match == 2。

我们用 n-gram 尝试了类似的方法，但在结果太多的类似方式中仍然没有取得太大的成功。

其他数据结构和查询的任何解决方案？

编辑 :

我们注意到，在我们的评估过程中存在一个错误，并且 minimum_should_match == 2 返回 100% 的结果。但是，之后的处理时间平均需要 5 秒。我们将看看脚本是否值得优化。

Answer 1

我已经模拟并实现了一个可能的解决方案，它避免了所有昂贵的“模糊”查询。取而代之的是在索引时取 N M的随机样本这些 64 位中的位。我猜这是 Locality-sensitive hashing 的一个例子.因此对于每个文档(以及查询时)样本编号 x总是取自相同的位位置以在文档之间具有一致的散列。

查询使用 term过滤器在 bool query的 should条款相对较低minimum_should_match临界点。较低的阈值对应较高的“模糊性”。不幸的是，您需要重新索引所有图像以测试这种方法。

我想 { "term": { "phash.0": true } }查询表现不佳，因为平均每个过滤器匹配 50%的文件。每个样本匹配 16 位/样本 2^-16 = 0.0015%的文件。

我使用以下设置运行我的测试:

1024 个样本/哈希(存储到文档字段 "0" - "ff")

16 位/样本(存储到 short 类型，doc_values = true)

4 个分片和 100 万个哈希/索引，大约 17.6 GB 的存储空间(可以通过不存储 _source 和样本来最小化，仅存储原始二进制哈希)

minimum_should_match = 150(共 1024 个)

以 400 万个文档(4 个索引)为基准

您可以通过更少的样本获得更快的速度和更低的磁盘使用率，但是汉明距离为 8 和 9 之间的文档没有很好地分离(根据我的模拟)。 1024似乎是 should的最大数目条款。

测试在单个 Core i5 3570K、24 GB RAM、8 GB ES 版本 1.7.1 上运行。 500 条查询的结果 (见下方注释，结果过于乐观) :

Mean time: 221.330 ms
Mean docs: 197

Percentiles:
   1st = 140.51ms
   5th = 150.17ms
  25th = 172.29ms
  50th = 207.92ms
  75th = 233.25ms
  95th = 296.27ms
  99th = 533.88ms

我将测试它如何扩展到 1500 万个文档，但是生成 100 万个文档并将其存储到每个索引需要 3 个小时。

您应该测试或计算应该设置多低 minimum_should_match要在错过的匹配和不正确的匹配之间获得所需的权衡，这取决于散列的分布。

示例查询(显示 1024 个字段中的 3 个):

{
  "bool": {
    "should": [
      {
        "filtered": {
          "filter": {
            "term": {
              "0": -12094,
              "_cache": false
            }
          }
        }
      },
      {
        "filtered": {
          "filter": {
            "term": {
              "_cache": false,
              "1": -20275
            }
          }
        }
      },
      {
        "filtered": {
          "filter": {
            "term": {
              "ff": 15724,
              "_cache": false
            }
          }
        }
      }
    ],
    "minimum_should_match": 150
  }
}

编辑:当我开始做进一步的基准测试时，我注意到我为不同的索引生成了太不同的哈希值，因此从这些索引中搜索导致零匹配。新生成的文档会产生大约 150 - 250 个匹配/索引/查询，应该更真实。

新结果显示在之前的图表中，我有 4 GB 的内存用于 ES，其余 20 GB 用于操作系统。搜索 1 - 3 个索引具有良好的性能(中值时间为 0.1 - 0.2 秒)，但搜索更多会导致大量磁盘 IO，查询开始需要 9 - 11 秒!这可以通过减少散列样本来规避，但召回率和准确率不会那么好，或者你可以拥有一台具有 64 GB RAM 的机器，看看你能得到多远。



编辑 2:我用 _source: false 重新生成了数据并且不存储哈希样本(仅原始哈希)，这将存储空间减少了 60% 到大约 6.7 GB/索引(100 万个文档)。这不会影响较小数据集的查询速度，但是当 RAM 不足且必须使用磁盘时，查询速度提高了约 40%。



编辑 3:我测试了 fuzzy在一组 3000 万个文档上以编辑距离 2 进行搜索，并将其与 256 个随机哈希样本进行比较以获得近似结果。在这些条件下，方法的速度大致相同，但 fuzzy给出准确的结果并且不需要额外的磁盘空间。我认为这种方法只对“非常模糊”的查询有用，比如大于 3 的汉明距离。