查找包含裁剪图像的图像

Question

我有一个很大的图片数据库（例如，100 万张 512x512px 图像），我想快速执行以下查询：

\n

给定裁剪后的图像，从包含该图像的数据库中查找图像。

\n

（我在 StackOverflow 中能找到的最接近的问题是这个，我将在本文后面讨论这个问题）

\n

下图说明了我正在尝试做的事情。

\n

\n

我有以下限制：

\n

\n

• (I) \xe2\x80\x93查询必须快。10\xe2\x81\xb6 很多，所以我认为我无法将查询中的每个图像与其他每个图像单独进行比较。

  \n
\n

• (II) \xe2\x80\x93我需要处理裁剪后的图像，因此简单图像散列之类的解决方案无法做到这一点（当然，这不适用于抗裁剪散列）

  \n
\n

• (III) \xe2\x80\x93我不知道查询的图像和包含它的图像的面积之间的比例。在上面的示例中，制冷剂只是原始图像的一小部分，但猫在包含它的图像中占据了很大的空间。虽然我估计该比例始终在 10%~100% 之间，但我事先不知道确切的数量（例如，假设查询中的图像始终为 512x512px）

  \n
\n

\n

我在研究中收集了一些信息：

\n

\n

• 由于(II)（我正在处理裁剪部分），简单的图像哈希匹配是不可能的

  \n
\n

• Reddit 的 RepostSleuthBot（可在GitHub上找到）对我来说是一个很好的起点：它可以识别图像是否已经以有效的方式发布。它似乎不是简单地匹配哈希值，而是使用ANNOY 算法来查找相似的图像（因此它可以匹配文本或亮度稍有修改的图像）。这种方法的唯一问题是它不太适合裁剪图像。因此，这涉及(I)但不涉及(II)和(III)。

  \n
\n

• 在我的 StackOverflow 搜索中，我发现对解决这个问题最有帮助的是，如果我知道裁剪图像和原始图像之间的比例，我可以使用相位相关性来匹配它，就像这个答案所说的那样。
  \n这解决了(II)，这很棒，但是我会遇到(I)的问题，因为我必须尝试与数据库的每个图像进行匹配，而且它也是不可行的，因为(三）。
  \n

  \n
\n

• 一个有前途的功能是抗裁剪图像散列 - 论文《高效裁剪抗鲁棒图像散列》，10.1109/ares.2014.85描述了一个功能，但似乎性能不是那么好，特别是考虑到我的目标适合小作物（原始图像的 10%~100%）和大量图像。

  \n
\n

\n

在这之后我陷入了困境。还有其他我应该注意的算法或方法吗？任何事情都会非常感激。

\n