algorithm - 比较两个图像的算法

Question

给定两个不同的图像文件（以我选择的任何格式），我需要编写一个程序来预测一个是否是另一个的非法副本的机会。副本的作者可能会做一些事情，比如旋转、制作负片或添加琐碎的细节（以及更改图像的尺寸）。

你知道做这种工作的任何算法吗？

Answer 1

这些只是我对这个问题的想法，从未尝试过，但我喜欢思考这样的问题！

在你开始之前

考虑对图片进行归一化处理，如果一张图片的分辨率高于另一张图片，请考虑其中一张图片是另一张图片的压缩版本的选项，因此缩小分辨率可能会提供更准确的结果。

考虑扫描图像的各种预期区域，这些区域可以代表图像的缩放部分以及各种位置和旋转。如果其中一个图像是另一个图像的倾斜版本，它开始变得棘手，这些是您应该识别和妥协的限制。

Matlab是用于测试和评估图像的出色工具。

测试算法

您应该（至少）测试大量人工分析的测试数据集，其中预先知道匹配。例如，如果您的测试数据中有 1,000 张图像，其中 5% 匹配，那么您现在就有了一个相当可靠的基准。找到 10% 阳性的算法不如在我们的测试数据中找到 4% 阳性的算法好。但是，一种算法可能会找到所有匹配项，但也有 20% 的大误报率，因此有几种方法可以对您的算法进行评分。

测试数据应尝试设计为涵盖您希望在现实世界中找到的尽可能多的动态类型。

需要注意的是，每个有用的算法都必须比随机猜测执行得更好，否则对我们来说毫无用处！

然后，您可以以可控的方式将您的软件应用到现实世界中，并开始分析它产生的结果。这是一种可以无限进行的软件项目，总是可以进行调整和改进，在设计时要牢记这一点很重要，因为很容易陷入永无止境的项目的陷阱。

色桶

使用两张图片，扫描每个像素并计算颜色。例如，您可能有“桶”：

white
red
blue
green
black

（显然你会有更高的计数器分辨率）。每次找到“红色”像素时，都会增加红色计数器。每个桶都可以代表颜色光谱，分辨率越高越准确，但您应该尝试可接受的差异率。

获得总数后，将其与第二张图像的总数进行比较。您可能会发现每个图像都有一个相当独特的足迹，足以识别匹配。

边缘检测

如何使用边缘检测。 _{（来源：wikimedia.org）}

使用两张相似的图片，边缘检测应该为您提供可用且相当可靠的独特足迹。

拍摄两张照片，并应用边缘检测。也许测量边缘的平均厚度，然后计算图像可以缩放的概率，并在必要时重新缩放。下面是在各种旋转中应用的Gabor 滤波器（一种边缘检测）的示例。

逐像素比较图片，计算匹配项和不匹配项。如果它们在一定的误差阈值之内，那么您就有了匹配项。否则，您可以尝试将分辨率降低到某个点，看看匹配的概率是否会提高。

感兴趣的区域

一些图像可能具有不同的片段/感兴趣区域。这些区域可能与图像的其余部分形成鲜明对比，并且是在其他图像中搜索以查找匹配项的好项目。以这张图片为例：

_{（来源：meetthegimp.org）}

蓝色的建筑工人是感兴趣的区域，可以作为搜索对象。可能有几种方法可以从该感兴趣区域提取属性/数据并使用它们来搜索您的数据集。

如果您有超过 2 个感兴趣区域，则可以测量它们之间的距离。以这个简化的例子为例：

_{（来源：per2000.eu）}

我们有 3 个明确的感兴趣区域。区域 1 和 2 之间的距离可以是 200 像素、1 和 3 400 像素之间以及 2 和 3 200 像素之间的距离。

在其他图像中搜索相似的感兴趣区域，标准化距离值并查看是否有潜在的匹配项。这种技术可以很好地适用于旋转和缩放的图像。您拥有的感兴趣区域越多，匹配的概率随着每次距离测量匹配而增加。

考虑数据集的上下文很重要。例如，如果您的数据集是现代艺术，那么感兴趣的区域会很好地工作，因为感兴趣的区域可能被设计为最终图像的基本部分。但是，如果您处理的是建筑工地的图像，则感兴趣的区域可能会被非法复印机解释为丑陋的，并且可能会被随意裁剪/编辑掉。牢记数据集的共同特征，并尝试利用这些知识。

变形

变形两个图像是通过一组步骤将一个图像转换为另一个图像的过程：

请注意，这与将一张图像淡入另一张图像不同！

有许多软件包可以变形图像。它传统上用作过渡效果，两个图像通常不会半途变形，一个极端会变成另一个极端作为最终结果。

为什么这会有用？取决于您使用的变形算法，图像的相似性和变形算法的某些参数之间可能存在关系。

在一个非常简化的示例中，当需要进行的更改较少时，一种算法可能会执行得更快。然后我们知道这两个图像彼此共享属性的可能性更高。

这种技术可以很好地适用于旋转、扭曲、倾斜、缩放的所有类型的复制图像。同样，这只是我的一个想法，据我所知，它不是基于任何研究过的学术界（虽然我没有仔细研究），所以对你来说可能需要做很多工作，但结果有限/没有结果。

拉链

Ow 在这个问题上的回答非常好，我记得读过有关这些研究 AI 的技术。它在比较语料库词典方面非常有效。

比较语料库时一个有趣的优化是您可以删除被认为太常见的词，例如“The”、“A”、“And”等。这些词稀释了我们的结果，我们想弄清楚两个语料库的不同之处所以这些可以在处理之前删除。也许图像中有类似的常见信号可以在压缩之前被剥离？这可能值得研究。

压缩比是确定两组数据相似程度的一种非常快速且相当有效的方法。阅读有关压缩如何工作的内容将使您很好地了解为什么这会如此有效。对于快速发布的算法，这可能是一个很好的起点。

透明度

同样，我不确定如何为某些图像类型、gif png 等存储透明度数据，但这将是可提取的，并且可以作为有效的简化剪切来与您的数据集透明度进行比较。

反相信号

图像只是一个信号。如果您从扬声器播放噪音，而您在另一个扬声器中以完全相同的音量完美同步播放相反的噪音，它们会相互抵消。

_{（来源：themotorreport.com.au）}

反转图像，并将其添加到您的其他图像上。重复缩放它/循环位置，直到找到足够的像素为白色（或黑色？我将其称为中性画布）的结果图像，从而为您提供正匹配或部分匹配。

但是，考虑两个相同的图像，除了其中一个应用了增亮效果：

_{（来源：mcburrz.com）}

反转其中一个，然后将其添加到另一个不会产生我们想要的中性画布。然而，当比较两个原始图像的像素时，我们可以清楚地看到两者之间的关系。

我已经有几年没有研究颜色了，不确定色谱是否在线性比例上，但是如果您确定了两张图片之间色差的平均因子，您可以在处理之前使用此值对数据进行归一化处理这种技术。

树数据结构

起初这些似乎不适合这个问题，但我认为它们可以工作。

您可以考虑提取图像的某些属性（例如颜色箱）并生成霍夫曼树或类似的数据结构。您也许可以比较两棵树的相似性。这不适用于照片数据，例如具有大光谱的颜色，但卡通或其他减少颜色的图像可能会起作用。

这可能行不通，但这是一个想法。trie数据结构非常适合存储词典，例如字典。这是一个前缀树。也许可以构建一个相当于词典的图像（再次我只能想到颜色）来构建一个 trie。如果您将 300x300 的图像缩小为 5x5 的正方形，然后将每个 5x5 的正方形分解为一系列颜色，您可以从结果数据中构建一个 trie。如果一个 2x2 正方形包含：

FFFFFF|000000|FDFD44|FFFFFF

我们有一个相当独特的 trie 代码，它扩展了 24 个级别，增加/减少级别（IE 减少/增加我们的子方块的大小）可能会产生更准确的结果。

比较特里树应该相当容易，并且可能提供有效的结果。

更多创意

我偶然发现了一篇关于卫星图像分类的有趣论文，它概述了：

考虑的纹理测量是：共现矩阵、灰度级差异、纹理色调分析、从傅里叶光谱派生的特征和 Gabor 滤波器。一些傅里叶特征和一些 Gabor 滤波器被发现是不错的选择，特别是当使用单个频带进行分类时。

尽管其中一些可能与您的数据集无关，但可能值得更详细地研究这些测量。

其他需要考虑的事项

可能有很多关于这类事情的论文，所以阅读其中一些应该会有所帮助，尽管它们可能非常技术性。这是计算中一个极其困难的领域，许多人试图做类似的事情花费了许多徒劳无功的工作。保持简单并以这些想法为基础将是最好的方法。创建一个比随机匹配率更好的算法应该是一个相当困难的挑战，并且开始改进它确实开始变得相当难以实现。

每种方法都可能需要彻底测试和调整，如果您有任何关于您将要检查的图片类型的信息，这将很有用。例如广告，其中许多都包含文本，因此进行文本识别将是一种简单且可能非常可靠的查找匹配项的方法，尤其是与其他解决方案结合使用时。如前所述，尝试利用数据集的共同属性。

结合可以进行加权投票的替代测量和技术（取决于它们的有效性）将是您可以创建一个生成更准确结果的系统的一种方式。

如果采用多种算法，如本答案开头所述，可能会发现所有阳性结果但误报率为 20%，研究其他算法的属性/优势/劣势会很有趣，因为另一种算法可能有效地消除从另一个返回的误报。

小心不要试图完成永无止境的项目，祝你好运！

Answer 2

阅读论文：Porikli、Fatih、Oncel Tuzel 和 Peter Meer。“基于黎曼流形均值的模型更新协方差跟踪”。(2006) IEEE 计算机视觉和模式识别。

使用本文介绍的技术，我成功地检测到从相邻网络摄像头捕获的图像中的重叠区域。我的协方差矩阵由 Sobel、canny 和 SUSAN 方面/边缘检测输出以及原始灰度像素组成。

Answer 3

一个主意：

1. 使用关键点检测器来查找图像中某些点的尺度和变换不变描述符（例如 SIFT、SURF、GLOH 或 LESH）。
2. 尝试将关键点与两幅图像中的相似描述符对齐（如全景拼接），如有必要，允许进行一些图像变换（例如缩放和旋转，或弹性拉伸）。
3. 如果许多关键点对齐良好（存在这样的变换，关键点对齐误差很低；或者变换“能量”很低，等等），你可能有相似的图像。

第 2 步并非易事。特别是，您可能需要使用智能算法在另一张图像上找到最相似的关键点。点描述符通常是非常高维的（比如一百个参数），并且有很多点需要查看。kd-trees 在这里可能很有用，哈希查找不能很好地工作。

变体：

• 检测边缘或其他特征而不是点。

Answer 4

它确实没有看起来那么简单 :-) 尼克的建议是一个很好的建议。

首先，请记住，任何有价值的比较方法本质上都是通过将图像转换为不同的形式来工作的——这种形式可以更容易地挑选出相似的特征。通常，这些东西不会让阅读变得很轻松……


我能想到的最简单的例子之一就是简单地使用每个图像的色彩空间。如果两个图像具有高度相似的颜色分布，那么您可以合理地确定它们显示的是相同的东西。至少，你可以有足够的把握来标记它，或者做更多的测试。在色彩空间中比较图像也会抵抗诸如旋转、缩放和一些裁剪之类的事情。当然，它不会抵抗图像的大量修改或重新着色（即使是简单的色调变化也会有些棘手）。

http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace

另一个例子涉及一种叫做霍夫变换的东西。这种变换本质上是将图像分解为一组线条。然后，您可以在每张图像中选取一些“最强”的线条，看看它们是否排列整齐。您也可以做一些额外的工作来尝试补偿旋转和缩放 - 在这种情况下，由于比较几行比对整个图像执行相同的计算工作要少得多 - 它不会那么糟糕。

http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/霍夫变换

Answer 5

在您描述的形式中，问题很棘手。您是否考虑将图像的一部分复制、粘贴到另一个更大的图像中作为副本？等等

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

1. 精确重复
2. 近乎精确的重复。（图像等的小幅编辑）
3. 感知重复（相同的内容，但不同的视图、相机等）

No1 和 2 更容易解决。No 3. 非常主观，仍然是一个研究课题。我可以为 No1 和 2 提供一个解决方案。两种解决方案都使用了优秀的图像散列库：https ://github.com/JohannesBuchner/imagehash

1. 精确重复 可以使用感知散列测量找到精确重复。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

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

如果您退后一步，如果您对主图像加水印，则更容易解决。您将需要使用水印方案将代码嵌入到图像中。退一步说，与某些人建议的一些低级方法（边缘检测等）相反，水印方法更胜一筹，因为：

它可以抵抗信号处理攻击 ► 信号增强 - 锐化、对比度等。 ► 过滤 - 中值、低通、高通等 ► 加性噪声 - 高斯、均匀等 ► 有损压缩 - JPEG、MPEG 等。

它可以抵抗几何攻击 ► 仿射变换 ► 数据缩减 – 裁剪、剪裁等 ► 随机局部失真 ► 翘曲

对水印算法进行一些研究，您将走上解决问题的正确道路。( 注意：您可以使用STIRMARK数据集对您的方法进行基准测试。这是此类应用程序的公认标准。

Answer 6

This is just a suggestion, it might not work and I'm prepared to be called on this.

This will generate false positives, but hopefully not false negatives.

1. Resize both of the images so that they are the same size (I assume that the ratios of widths to lengths are the same in both images).

2. Compress a bitmap of both images with a lossless compression algorithm (e.g. gzip).

3. Find pairs of files that have similar file sizes. For instance, you could just sort every pair of files you have by how similar the file sizes are and retrieve the top X.

As I said, this will definitely generate false positives, but hopefully not false negatives. You can implement this in five minutes, whereas the Porikil et. al. would probably require extensive work.

Answer 7

我相信，如果您愿意将该方法应用于所有可能的方向和负面版本，图像识别（具有良好可靠性）的良好开端是使用特征脸：http ://en.wikipedia.org/wiki/Eigenface

另一个想法是将两个图像都转换为它们组件的向量。一个很好的方法是创建一个在 x*y 维度上运行的向量（x 是图像的宽度，y 是高度），每个维度的值都应用于 (x,y) 像素值。然后运行具有两个类别的 K-Nearest Neighbors 变体：匹配和不匹配。如果它与原始图像足够接近，它将适合匹配类别，如果不是，则不会。

K 最近邻（KNN）可以在这里找到，网上也有其他很好的解释：http ://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

KNN 的好处是与原始图像比较的变体越多，算法就越准确。缺点是您需要一个图像目录来首先训练系统​​。

Answer 8

如果您愿意考虑完全不同的方法来检测图像的非法副本，您可以考虑添加水印。（从 1.4 开始）

...在不损失质量的情况下将版权信息插入数字对象。每当涉及数字对象的版权时，都会提取此信息以识别合法所有者。还可以对原始购买者的身份以及版权所有者的身份进行编码，这样就可以追踪任何未经授权的复制品。

虽然它也是一个复杂的领域，但有一些技术可以让水印信息通过粗略的图像更改持续存在：（从 1.9 开始）

...任何合理强度的信号变换都无法去除水印。因此，愿意移除水印的盗版者将不会成功，除非他们将文档贬低到不符合商业利益的程度。

当然，常见问题解答呼吁实施这种方法：“......非常具有挑战性”，但如果你成功了，你就会对图像是否是副本有很高的信心，而不是百分比可能性。

Answer 9

如果您正在运行 Linux，我建议您使用两个工具：

来自包 hugin-tools 的 align_image_stack - 是一个命令行程序，可以自动校正旋转、缩放和其他扭曲（它主要用于合成 HDR 摄影，但也适用于视频帧和其他文档）。更多信息：http ://hugin.sourceforge.net/docs/manual/Align_image_stack.html

从包 imagemagick 进行比较- 一个可以查找和计算两个图像中不同像素数量的程序。这是一个简洁的教程：http : //www.imagemagick.org/Usage/compare/ 使用 -fuzz N% 可以增加容错。N 越高，仍然将两个像素计为相同的容错性就越高。

align_image_stack 应该更正任何偏移量，以便比较命令实际上有机会检测到相同的像素。