98

我需要创建许多图像的指纹（大约 100.000 个现有图像，每天 1000 个新图像，RGB，JPEG，最大尺寸 800x800）以非常快速地将每个图像与其他图像进行比较。我不能使用二进制比较方法，因为也应该识别几乎相似的图像。

最好的将是一个现有的库，但对现有算法的一些提示也会对我有很大帮助。

4

11 回答 11

59

普通散列或 CRC 计算算法不适用于图像数据。必须考虑信息的维度性质。

如果您需要极其强大的指纹识别，例如考虑仿射变换（缩放、旋转、平移、翻转），您可以在图像源上使用 Radon 变换来生成图像数据的规范映射 - 将其存储在每个图像中并然后只比较指纹。这是一个复杂的算法，不适合胆小的人。

一些简单的解决方案是可能的：

  1. 为图像创建亮度直方图作为指纹
  2. 创建每个图像的缩小版本作为指纹
  3. 将技术 (1) 和 (2) 组合成一种混合方法，以提高比较质量

亮度直方图（尤其是分离为 RGB 分量的直方图）是图像的合理指纹 - 并且可以非常有效地实现。从另一个中减去一个直方图将产生一个新的直方图，您可以对其进行处理以确定两个图像的相似程度。直方图，因为唯一评估亮度/颜色信息的分布和出现可以很好地处理仿射变换。如果将每个颜色分量的亮度信息量化为 8 位值，则 768 字节的存储空间足以存储几乎任何合理大小的图像的指纹。当图像中的颜色信息被操纵时，亮度直方图会产生假阴性。如果您应用对比度/亮度、色调分离、颜色偏移等转换，亮度信息会发生变化。

使用缩放图像是将图像的信息密度降低到更容易比较的水平的另一种方法。缩小到原始图像大小的 10% 以下通常会丢失太多无法使用的信息 - 因此，可以将 800x800 像素的图像缩小到 80x80，并且仍然提供足够的信息来执行体面的指纹识别。与直方图数据不同，当源分辨率具有不同的纵横比时，您必须对图像数据执行各向异性缩放。换句话说，将 300x800 的图像缩小为 80x80 的缩略图会导致图像变形，因此与 300x500 的图像（非常相似）相比会导致误报。当涉及仿射变换时，缩略图指纹也经常产生假阴性。如果您翻转或旋转图像，

结合这两种技术是一种合理的方式来对冲您的赌注并减少误报和误报的发生。

于 2009-07-02T18:19:41.080 回答
34

与此处提出的按比例缩小的图像变体相比，有一种更不特别的方法，它保留了它们的一般风格，但它为正在发生的事情提供了更严格的数学基础。

取图像的Haar 小波。基本上，Haar 小波是从较低分辨率图像到每个较高分辨率图像的连续差异，但根据您在 mipmap 的“树”中的深度加权。计算很简单。然后，一旦对 Haar 小波进行了适当加权，就丢弃除 k 个最大系数之外的所有系数（就绝对值而言），对向量进行归一化并保存它。

如果你取其中两个标准化向量的点积，它会给你一个相似度的度量，其中 1 几乎相同。我在这里发布了更多信息。

于 2009-07-02T20:56:05.830 回答
21

你绝对应该看看phash。

对于图像比较，有这个php项目： https ://github.com/kennethrapp/phasher

还有我的小javascript克隆： https ://redaktor.me/phasher/demo_js/index.html

不幸的是，这是基于“位计数”的，但会识别旋转的图像。javascript 中的另一种方法是借助画布从图像中构建亮度直方图。您可以在画布上可视化多边形直方图并比较数据库中的多边形（例如 mySQL 空间...）

于 2013-06-14T08:38:09.070 回答
12

很久以前，我在一个具有一些相似特征的系统上工作，这是我们遵循的算法的近似值：

  1. 将图片划分为多个区域。在我们的例子中，我们处理的是 4:3 分辨率的视频，所以我们使用了 12 个区域。这样做会使源图像的分辨率脱离图片。
  2. 对于每个区域，计算一个整体颜色 - 区域中所有像素的平均值
  3. 对于整个图像，计算整体颜色 - 所有区域的平均值

因此，对于每张图像，您都在存储n + 1整数值，其中n是您要跟踪的区域数。

为了进行比较，您还需要单独查看每个颜色通道。

  1. 对于整体图像，比较整体颜色的颜色通道，看看它们是否在某个阈值内——比如 10%
  2. 如果图像在阈值内，接下来比较每个区域。如果所有区域也在阈值范围内，则图像的匹配度足够高，您至少可以标记它们以进行进一步比较。

这使您可以快速丢弃不匹配的图像；您还可以使用更多区域和/或递归应用算法以获得更强的匹配置信度。

于 2009-07-02T18:51:20.217 回答
6

与 Ic 的答案类似 - 您可以尝试以多种分辨率比较图像。因此，每个图像都保存为 1x1、2x2、4x4 .. 800x800。如果最低分辨率不匹配（受阈值限制），您可以立即拒绝它。如果匹配，您可以在下一个更高分辨率下比较它们，依此类推..

此外 - 如果图像共享任何相似的结构，例如医学图像，您可能能够将该结构提取到更容易/更快比较的描述中。

于 2009-02-27T20:07:06.057 回答
3

截至 2015 年（回到未来……关于这个 2009 年的问题，现在在 Google 中排名靠前），可以使用深度学习技术计算图像相似度。称为自动编码器的算法系列可以创建可搜索相似性的向量表示。这里有一个演示。

于 2015-12-24T23:05:26.220 回答
2

对于 iPhone 图像比较和图像相似度开发，请查看： http ://sites.google.com/site/imagecomparison/

要查看它的实际效果，请查看 iTunes AppStore 上的 eyeBuy Visual Search。

于 2010-02-17T19:54:53.140 回答
2

您可以做到这一点的一种方法是调整图像大小并显着降低分辨率（可能是 200x200？），存储一个较小的（像素平均）版本进行比较。然后定义一个容差阈值并比较每个像素。如果所有像素的 RGB 都在容差范围内，则表示匹配。

您的初始运行时间为 O(n^2)，但如果您对所有匹配项进行编目，则每个新图像只是一个 O(n) 算法进行比较（您只需将其与每个先前插入的图像进行比较）。然而，随着要比较的图像列表变大，它最终会崩溃，但我认为你暂时是安全的。

运行 400 天后，您将拥有 500,000 张图像，这意味着（扣除缩小图像大小的时间）200(H)*200(W)*500,000(images)*3(RGB)= 60,000,000,000 次比较。如果每张图片都完全匹配，那么您将落后，但情况可能并非如此，对吧？请记住，只要单个比较超出您的阈值，您就可以将图像视为匹配项。

于 2009-02-27T19:47:23.780 回答
2

您是否真的想将每张图片与其他图片进行比较？应用程序是什么？也许您只需要某种基于某些描述符的图像索引和检索？然后，例如，您可以查看多媒体内容描述接口的 MPEG-7 标准。然后你可以比较不同的图像描述符，这不会那么准确，但要快得多。

于 2009-02-27T19:56:16.613 回答
2

所以你想做与“图像匹配”完全不同的“指纹匹配”。指纹分析在过去 20 年中得到了深入研究，并且开发了几种有趣的算法来确保正确的检测率（关于FAR和FRR测量 -错误接受率和错误拒绝率）。

我建议您更好地查看LFA（局部特征分析）类检测技术，主要基于细节检查。细节是任何指纹的特定特征，并已分为几类。将光栅图像映射到细节图实际上是大多数公共当局为提交罪犯或恐怖分子所做的事情。

请参阅此处以获取更多参考

于 2009-09-30T10:49:33.993 回答
-1

似乎专门的图像散列算法是一个积极研究的领域，但也许图像字节的正常散列计算可以解决问题。

您是否正在寻找字节相同的图像，而不是寻找源自相同来源但可能具有不同格式或分辨率的图像（这让我觉得这是一个相当困难的问题）。

于 2009-02-28T07:15:13.283 回答