图像比较 - 快速算法

以下是解决此问题的三种方法（还有许多其他方法）。

第一种是计算机视觉中的标准方法，即关键点匹配。这可能需要一些背景知识来实现，并且可能很慢。

第二种方法仅使用基本图像处理，并且可能比第一种方法更快，并且易于实现。然而，它在可理解性方面获得了什么，但它缺乏鲁棒性——在缩放、旋转或变色的图像上匹配失败。

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

关键点匹配

比选择 100 个随机点更好的是选择 100 个 important 点。图像的某些部分比其他部分具有更多信息（特别是在边缘和角落），这些是您想要用于智能图像匹配的部分。谷歌“keypoint extraction”和“keypoint matching”，你会发现很多关于这个主题的学术论文。如今，SIFT keypoints 可以说是最受欢迎的，因为它们可以匹配不同比例、旋转和光照下的图像。可以在 here 中找到一些 SIFT 实现。

关键点匹配的一个缺点是简单实现的运行时间：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| 

对于绿色直方图中的每个桶，对其他直方图重复，然后总结所有结果。结果越小，匹配越好。对数据库中的所有图像重复，结果最小的匹配获胜。您可能希望有一个阈值，超过该阈值算法得出未找到匹配的结论。

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

第三种可能比其他两种快得多的方法是使用 semantic texton forests (PDF)。这涉及提取简单的关键点并使用集合决策树对图像进行分类。这比简单的 SIFT 关键点匹配要快，因为它避免了昂贵的匹配过程，而且关键点比 SIFT 简单得多，因此关键点提取要快得多。但是，它保留了 SIFT 方法对旋转、缩放和光照的不变性，这是直方图方法所缺乏的一个重要特征。

更新：

我的错误——Semantic Texton Forests 论文不是专门关于图像匹配，而是区域标签。进行匹配的原始论文是：Keypoint Recognition using Randomized Trees。此外，以下论文继续发展这些想法并代表最先进的技术（c. 2010）：

使用 Random Ferns 进行快速关键点识别 - 比 Lepetit 06 更快且更具可扩展性

简介：二进制鲁棒独立基本特征 - 不太健壮但非常快 - 我认为这里的目标是在智能手机和其他手持设备上进行实时匹配

---

我知道的最好的方法是使用感知哈希。这种散列似乎有一个很好的开源实现，可在以下位置获得：

http://phash.org/

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

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

---

这篇文章是我解决方案的起点，这里有很多好主意，所以我想分享我的结果。主要的见解是，我找到了一种通过利用 phash 的速度来解决基于关键点的图像匹配缓慢的方法。

对于一般解决方案，最好采用多种策略。每种算法都最适合某些类型的图像转换，您可以利用它。

在顶部，最快的算法；在底部最慢（虽然更准确）。如果在较快的级别上找到了良好的匹配，您可能会跳过较慢的级别。

基于文件哈希（md5、sha1 等）的精确重复项

重新缩放图像的感知散列（phash）

修改图像的基于特征 (SIFT)

我在使用 phash 时取得了很好的效果。对于重新缩放的图像，精度很好。它不适用于（感知）修改的图像（裁剪、旋转、镜像等）。为了处理散列速度，我们必须使用磁盘缓存/数据库来维护干草堆的散列。

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

例如，如果您有 100 万张图像，则需要一个包含 100 万个 64 位哈希值 (8 MB) 的数组。在某些 CPU 上，这适合 L2/L3 缓存！在实际使用中，我看到 corei7 的比较速度超过 1 Giga-hamm/sec，这只是 CPU 的内存带宽问题。 10 亿张图像数据库在 64 位 CPU（需要 8GB RAM）上是实用的，搜索不会超过 1 秒！

对于修改/裁剪的图像，看起来像 SIFT 这样的变换不变特征/关键点检测器是可行的方法。 SIFT 会产生很好的关键点来检测裁剪/旋转/镜像等。但是与 phash 使用的汉明距离相比，描述符比较非常慢。这是一个主要限制。有很多比较要做，因为有最大的 IxJxK 描述符比较查找一个图像（I=num haystack 图像，J=每个 haystack 图像的目标关键点，K=每个针图像的目标关键点）。

为了解决速度问题，我尝试在每个找到的关键点周围使用 phash，使用特征大小/半径来确定子矩形。使这项工作顺利进行的技巧是增大/缩小半径以生成不同的子矩形级别（在针图像上）。通常第一级（未缩放）会匹配，但通常需要更多。我不是 100% 确定为什么会这样，但我可以想象它启用了太小而无法使用 phash 的功能（phash 将图像缩小到 32x32）。

另一个问题是 SIFT 不会最优地分布关键点。如果图像的某个部分有很多边缘，则关键点将聚集在那里，而您将不会在其他区域得到任何边缘。我在 OpenCV 中使用 GridAdaptedFeatureDetector 来改进分布。不确定哪种网格尺寸最好，我使用的是小网格（1x3 或 3x1，具体取决于图像方向）。

在特征检测之前，您可能希望将所有干草堆图像（和针）缩放到更小的尺寸（我沿最大尺寸使用 210 像素）。这将减少图像中的噪声（对于计算机视觉算法来说总是一个问题），还将检测器集中在更突出的特征上。

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

当关键点检测器返回的特征数量少于您想要的数量时，它可能工作得最好。例如，如果您要求 400 并获得 300 回来，那很好。如果您每次都返回 400，则可能必须忽略一些好的功能。

针图像的关键点可以比干草堆图像少，并且仍然可以获得良好的结果。添加更多并不一定会给您带来巨大的收益，例如在 J=400 和 K=40 的情况下，我的命中率约为 92%。在 J=400 和 K=400 的情况下，命中率仅上升到 96%。

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

---

我的公司每月有大约 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

希望这可以帮助！

---

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

寻找近距离图像的一个起点可以是 here。这是 CG 公司用来检查修改后的图像是否仍然显示基本相同的场景的工具。

---

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

如果您想要更通用的东西或使用大型数据库（数百万张图像），那么您需要研究图像检索理论（过去 5 年出现了大量论文）。其他答案中有一些指示。但这可能是矫枉过正，建议直方图方法可以完成这项工作。虽然我认为许多不同的快速方法的组合会更好。

---

我相信将图像的大小降低到几乎是图标大小，比如 48x48，然后转换为灰度，然后获取像素之间的差异或 Delta，应该可以很好地工作。因为我们比较的是像素颜色的变化，而不是实际的像素颜色，所以图像稍微亮一点还是暗一点都没有关系。大的变化很重要，因为太亮/太暗的像素会丢失。您可以将其应用于一行，或任意数量以提高准确性。最多你需要做 47x47=2,209 次减法来形成一个可比较的 Key。

---

选择 100 个随机点可能意味着相似（或偶尔甚至不相似）的图像将被标记为相同，我认为这不是您想要的。如果图像格式不同（png、jpeg 等）、大小不同或元数据不同，则 MD5 哈希将不起作用。将所有图像缩小到较小的尺寸是一个不错的选择，只要您使用良好的图像库/快速语言并且尺寸足够小，进行逐像素比较不应该花费太长时间。

您可以尝试使它们变小，然后如果它们相同，则在更大的尺寸上进行另一次比较-可能是速度和准确性的良好结合...

---

我们松散地称为重复的东西对于算法来说很难辨别。您的重复项可以是：

精确重复 近乎精确的重复。 （图像等的微小编辑）感知重复（相同的内容，但不同的视图，相机等）

1号& 2更容易解决。 No 3. 非常主观，仍然是一个研究课题。我可以为 No1 & 提供解决方案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

Near-Exact Duplicates 在这种情况下，您必须设置一个阈值并比较散列值之间的距离。这必须通过对图像内容的反复试验来完成。

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) )

---

如果您有大量图像，请查看 Bloom filter，它使用多个散列以获得概率但有效的结果。如果图像的数量不是很大，那么像 md5 这样的加密哈希就足够了。

---