图像比较 - 快速算法

Question

图像比较 - 快速算法

imagealgorithmcomparisoncomputer-vision

446

我希望创建一个图像基础表，然后将任何新图像与此进行比较，以确定新图像是否是基础图像的完全副本或近似副本。

例如：如果您想减少存储同一图像数百次的情况，您可以只存储一份，并提供其引用链接。当输入新图像时，您希望将其与现有图像进行比较，以确保它不是重复的...有什么建议吗？

我的一个想法是缩小成小缩略图，然后随机选择100个像素位置进行比较。

- meade

12个回答

99

我所知道的最好方法是使用感知哈希(Perceptual Hash)。这里有一个良好的开源实现可供使用:

http://phash.org/

主要思想是通过识别原始图像文件中的显著特征，并对这些特征的紧凑表示进行哈希（而不是直接哈希图像数据），将每个图像缩小到一个小的哈希码或“指纹”。这意味着与将图像缩小为微小的缩略图并比较缩略图等简单方法相比，误报率大大降低。

phash提供了几种类型的哈希，并可用于图像、音频或视频。

- redcalx

有兴趣的人可以通过以下链接找到Objective-C感知哈希实现：https://github.com/ameingast/cocoaimagehashing - Alexey Voitenko

@AlexeyVoitenko 这个是否与phash.org在其默认配置下生成的哈希兼容？ - Michael

5

依照我的经验，pHash 对于查找同一图像的不同尺寸效果良好，但对于查找相似图像则不是很适用。例如，同一物体的两张不同照片可能具有非常不同的哈希值。 - Rena

44

这篇文章是我解决问题的起点，其中有很多好的想法，所以我想分享一下我的结果。重要的一点是，我找到了一种利用phash速度来避免基于关键点图像匹配缓慢性的方法。

为了得到通用解决方案，最好采用多个策略。每个算法最适合某些类型的图像变换，你可以利用这一点。

在顶部是最快的算法；在底部是最慢的（但更准确）。如果在更快的级别上找到了好的匹配，那么可能会跳过较慢的选项。

基于文件哈希（md5，sha1等）用于完全重复的图像
感知哈希（phash）用于缩放后的图像
基于特征的（SIFT）用于修改后的图像

对于phash，我得到了非常好的结果。对于大小调整后的图像，准确率很高。但对于（感知上）修改后的图像（裁剪，旋转，镜像等），效果不好。为了处理哈希速度，我们必须使用磁盘缓存/数据库来维护干草堆的哈希。

phash真正好的地方在于，一旦构建了哈希数据库（对我来说，每秒约1000张图像），搜索速度就可以非常快，特别是当你可以将整个哈希数据库保留在内存中时。这相当实用，因为哈希只有8字节。

例如，如果你有100万张图像，它将需要一个包含100万个64位哈希值的数组（8 MB）。对于某些CPU而言，这适合于L2/L3缓存！在实际使用中，我看到的一个Corei7比较速度超过1千兆哈姆/秒，这只是与CPU的内存带宽有关。在64位CPU上，10亿图像数据库是实用的（需要8GB RAM），并且搜索不会超过1秒！

对于修改/裁剪的图像，似乎使用SIFT这样的转换不变特征点检测器是正确的选择。SIFT将产生良好的关键点，可以检测到裁剪/旋转/镜像等操作。然而，与phash使用的海明距离相比，描述符比较速度非常慢。这是一个重大限制。由于最多需要IxJxK个描述符比较来查找一个图像（I=数字干草堆图像，J=每个干草堆图像的目标关键点，K=每个针图像的目标关键点），所以需要进行大量的比较。

为了解决速度问题，我尝试在每个找到的关键点周围使用phash，使用特征大小/半径来确定子矩形。使其良好工作的技巧是增加/减小半径以生成不同的子矩形级别（在针图像上）。通常，第一级（未缩放）将匹配，但有时需要更多级别。我不100％确定为什么会有效，但我可以想象它能够启用对于phash无法处理的太小的特征。

另一个问题是，SIFT将不能优化地分配关键点。如果图像中有很多边缘部分，关键点将聚集在那里，而另一个区域则没有关键点。我正在使用OpenCV中的GridAdaptedFeatureDetector来改善分布。不确定最佳网格大小是多少，我使用了一个小网格（1x3或3x1，取决于图像方向）。

您可能希望将所有干草堆图像（和针）缩小到较小的尺寸以进行特征检测（我使用最大尺寸为210px）。这将减少图像中的噪声（计算机视觉算法总是存在问题），还将使检测器更专注于突出特征。

对于人物图像，您可以尝试面部检测，并使用它来确定要缩放的图像大小和网格大小（例如将最大的脸缩放为100px）。特征检测器考虑多个比例级别（使用金字塔），但使用的级别有限制（当然可以调整）。

当关键点检测器返回的特征数量少于您需要的数量时，它可能会表现最佳。例如，如果您要求400个并得到300个，那就很好。如果每次都得到400个，那么可能有一些好的特征被忽略了。

针图像的关键点可以比堆栈图像少，仍然能获得良好的结果。添加更多的关键点并不一定会带来巨大的收益，例如J=400和K=40时，我的命中率约为92%。使用J=400和K=400时，命中率只增加到96%。

我们可以利用汉明函数的极速来解决缩放、旋转、镜像等问题。可以使用多通道技术。在每次迭代中，变换子矩形，重新哈希，再次运行搜索函数。

- wally

14

我的公司每个月从制造商那里接收大约2400万张图片。我正在寻找一种快速解决方案，以确保我们上传到目录中的图片是新的图片。

我想说我已经在互联网上广泛搜索，试图找到一个理想的解决方案。我甚至开发了自己的边缘检测算法。
我评估了多个模型的速度和准确性。我的图片有白色背景，使用phashing非常有效。就像redcalx所说，我建议使用phash或ahash。不要使用MD5哈希或任何其他加密哈希。除非你只想获取完全相同的图片匹配。在图像之间进行任何调整或操作都会产生不同的哈希值。

关于phash/ahash，请查看：imagehash

我想通过发布我的代码和准确性来扩展*redcalx*的帖子。

我的做法：

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

这是我的一些结果:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

希望这能帮到您！

- Tanner Clark

MD5哈希比图像哈希更快吗？我只是在想一个情况，你有很多相同的图像，并且如果你首先进行MD5哈希比较，是否会获得速度增益。 - Pepsi-Joe

8

正如卡特曼指出的那样，您可以使用任何类型的哈希值来查找精确的重复项。

寻找相似图像的一个起点可能是这里。这是CG公司用来检查翻新后的图像是否仍然显示基本相同场景的工具。

- Tobiesque

7

我有一个想法，可以运行并且很可能非常快速。你可以将图像子采样到80x60或相似的分辨率，并转换为灰度（在子采样之后会更快）。处理要比较的两个图像。然后运行两个图像（查询图像和每个来自数据库的图像）之间的标准化平方差之和，甚至更好的是使用标准化交叉相关性，如果两个图像相似，则结果接近1。然后，如果图像相似，您可以继续使用更复杂的技术验证它们是否是相同的图像。显然，这个算法在数据库中的图像数量方面是线性的，因此即使在现代硬件上每秒处理10000张图像也会非常快速。如果需要旋转不变性，则可以为该小图像计算主导梯度，然后将整个坐标系旋转到规范方向，但这会更慢。不，这里没有尺度不变性。

如果您需要更通用或使用大型数据库（数百万张图像），则需要研究图像检索理论（最近5年出现了许多论文）。其他答案中有一些指针。但这可能过于复杂，建议直接使用直方图方法即可完成任务。虽然我认为结合许多不同的快速方法会更好。

- Denis C

6

我认为将图像大小缩小到接近于图标的尺寸，例如48x48，然后转换成灰度，并取像素之间的差异或Delta，应该能够很好地工作。因为我们比较的是像素颜色的变化而不是实际像素颜色，所以图像略微变亮或变暗并不重要。大的变化会很重要，因为像素变得太亮或太暗会被忽略。您可以在一行上应用此方法，或者应用多行以增加准确性。最多可能需要进行47x47=2,209次减法运算，以形成可比较的密钥。

- Tanoshimi

4

我们通常所说的重复可能很难让算法分辨。

你的重复可以是以下几种情况：

完全重复
几乎完全重复（图片等进行了微小的编辑）
感知重复（相同内容，但是不同视角、相机等）

1和2更容易解决。3很主观，并且仍然是一个研究课题。

我可以提供第1和第2个问题的解决方案。这两个方案都使用了出色的图像哈希计算库：https://github.com/JohannesBuchner/imagehash

完全重复我们可以使用感知哈希测量来找到完全重复的内容。 phash库在此方面表现很好。我经常使用它来清理培训数据。如下是使用方式（来自github站点）：

from PIL import Image
import imagehash

# image_fns : List of training image files
img_hashes = {}

for img_fn in sorted(image_fns):
    hash = imagehash.average_hash(Image.open(image_fn))
    if hash in img_hashes:
        print( '{} duplicate of {}'.format(image_fn, img_hashes[hash]) )
    else:
        img_hashes[hash] = image_fn

几乎相同的重复内容在这种情况下，您需要设置一个阈值，并比较它们的哈希值之间的距离。对于您的图片内容，这必须通过试错来完成。

from PIL import Image
import imagehash

# image_fns : List of training image files
img_hashes = {}
epsilon = 50

for img_fn1, img_fn2 in zip(image_fns, image_fns[::-1]):
    if image_fn1 == image_fn2:
        continue

    hash1 = imagehash.average_hash(Image.open(image_fn1))
    hash2 = imagehash.average_hash(Image.open(image_fn2))
    if hash1 - hash2 < epsilon:
        print( '{} is near duplicate of {}'.format(image_fn1, image_fn2) )

- navneeth

谢谢。以下是一个可能的使用案例，您认为如何？https://www.edaboard.com/threads/machine-learning-algorithms-for-identifying-electronic-components-in-pcb.398134/ 谢谢和问候。 - Prashant Akerkar

3

选择100个随机点可能意味着相似（甚至有时是不相似）的图像会被标记为相同，这显然不是您想要的。如果图像格式不同（png、jpeg等）、大小不同或元数据不同，则MD5哈希将无法使用。将所有图像缩小到较小的尺寸是一个好选择，进行像素对比只要使用良好的图像库/快速语言且大小足够小即可。您可以尝试将它们变得微小，然后如果它们相同，请在较大的大小上执行另一次比较-这可能是速度和准确性的良好组合...

- HarryM

1

如果您正在寻找具有不同格式/元数据的完全重复项，则可以对实际像素值进行哈希（例如MD5）。Imagemagick将其称为签名（与加密签名无关）。您还可以首先将其缩小，例如将每个像素截断为4位，以减少JPEG伪影的影响，或者将其转换为灰度以匹配略微重新着色的图像。 - Rena

2

如果您有大量的图像，请考虑使用Bloom过滤器，它使用多个哈希进行概率但高效的结果。如果图像数量不是很大，则像md5这样的加密哈希应该足够了。

- jdigital

那么（试图理解布隆过滤器）-这是否意味着您在基础图像上选择随机像素点，随机获取像素的红/绿/蓝值-然后与新图像进行比较？然后使用概率水平（90％匹配）来确定两个图像的相似程度？ - meade

6

这不是相似性检查，而是等价性检查。如果您需要相似性检查，则哈希不是正确的方法。Bloom 的想法是使用多个哈希算法来增加唯一标识的可能性。对于哈希算法来说，选择随机点不是最佳方法，因为它每次都会产生不同的结果。 - jdigital

@jdigital OP问到如何检查两个图像是否“完全相同（或接近）”，哈希算法（如MD5或SHA1）无法判断两个图像是否接近但不完全一样。 - skeetastax

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kyle Simek · Accepted Answer

以下是解决这个问题的三种方法（还有很多其他方法）：

1. 第一种是计算机视觉中的标准方法，关键点匹配。需要一些背景知识才能实现，可能速度较慢。

2. 第二种方法仅使用基本图像处理，可能比第一种方法更快，并且易于实现。但是，它在可靠性方面不如第一种方法——匹配失败会发生在缩放、旋转或变色的图像上。

3. 第三种方法既快速又可靠，但可能是最难实现的。

关键点匹配

比选择100个随机点更好的是选择100个重要点。图像的某些部分比其他部分具有更多信息（特别是在边缘和角落处），这些部分是智能图像匹配所需的部分。搜索 "keypoint extraction" 和 "keypoint matching" 就可以找到很多学术论文。如今，SIFT keypoints 可能是最流行的，因为它们可以匹配不同比例、旋转和光照下的图像。一些 SIFT 实现可以在 here 找到。

关键点匹配的一个缺点是朴素实现的运行时间复杂度为O(n^2m)，其中n是每个图像中关键点的数量，m是数据库中图像的数量。一些聪明的算法可以更快地找到最接近的匹配，例如四叉树或二进制空间分割。

替代方案：直方图方法

另一个不太健壮但潜在更快的解决方案是为每个图像构建特征直方图，并选择与输入图像直方图最接近的图像。我在本科时实现了这个方法，我们使用了3种颜色直方图（红色、绿色和蓝色）和两种纹理直方图，方向和比例尺寸。我将在下面详细介绍，但我应该指出，这仅适用于非常类似于数据库图像的匹配图像。重新缩放、旋转或变色的图像可能无法使用此方法，但像裁剪这样的小变化不会破坏算法

计算颜色直方图很简单——只需选择直方图桶的范围，并对每个范围中具有该颜色的像素数量进行统计。例如，考虑“绿色”直方图，并假设我们为直方图选择了4个桶：0-63、64-127、128-191和192-255。然后对于每个像素，我们查看其绿色值，并将计数添加到相应的桶中。当我们完成计数时，我们将每个桶总数除以整个图像中的像素数，以获得绿色通道的归一化直方图。

对于纹理方向直方图，我们首先对图像执行边缘检测。每个边缘点都有一个法向量，指向垂直于边缘的方向。我们将法向量的角度量化为0到PI之间的6个桶之一（由于边缘具有180度的对称性，因此我们将-PI到0之间的角度转换为0到PI之间）。在统计每个方向的边缘点数后，我们得到了一个表示纹理方向的非归一化直方图，通过将每个桶除以图像中边缘点的总数进行归一化。

为了计算纹理比例直方图，对于每个边缘点，我们测量到与相同方向的下一个最近的边缘点的距离。例如，如果边缘点A的方向为45度，算法将在该方向上行走，直到找到另一个方向为45度（或在合理偏差范围内）的边缘点。计算每个边缘点的这个距离后，我们将这些值倾倒到一个直方图中，并通过除以边缘点的总数来进行归一化。

现在你有每张图片的5个直方图。要比较两张图片，你需要取每个直方图桶之间的差的绝对值，然后将这些值相加。例如，要比较图片A和B，我们会计算

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1|

对于绿色直方图中的每个桶，以及其他直方图，重复此过程，然后将所有结果相加。结果越小，匹配越好。对于数据库中的所有图像重复此过程，并获得最小结果的匹配。您可能希望设置一个阈值，在该阈值之上，算法会得出未找到匹配项的结论。

第三选择 - 关键点 + 决策树

第三种方法可能比其他两种方法快得多，它使用语义文本森林（PDF）来提取简单的关键点，并使用一组决策树来对图像进行分类。这比简单的SIFT关键点匹配更快，因为它避免了昂贵的匹配过程，并且关键点比SIFT简单得多，因此关键点提取速度更快。然而，它保留了SIFT方法对旋转、缩放和照明的不变性，这是直方图方法所缺乏的一个重要特征。

更新：

我犯了错误 - 《语义文本森林》论文并非专门讨论图像匹配，而是区域标记。最初进行匹配的论文是：使用随机化树进行关键点识别。此外，以下论文继续发展这些想法并代表了当时的最新技术（约为2010年）：

使用随机蕨分类器进行快速关键点识别 - 比Lepetit 06更快且更可扩展
~~BRIEF：二进制稳健独立元素特征~~ - 不太稳健但非常快速--我认为这里的目标是在智能手机和其他手持设备上进行实时匹配