比较两个图像的算法

Question

给定两个不同的图像文件（无论我选择什么格式），我需要编写一个程序来预测一个图像文件是另一个图像文件的非法副本的可能性。 文案的作者可能会做旋转、制作负片或添加琐碎细节（以及更改图像尺寸）等操作。

你知道有什么算法可以完成这种工作吗？

Answer 1

阅读论文：波里克利、法提赫、昂塞尔·图泽尔和彼得·米尔。 “使用基于模型更新的协方差跟踪
黎曼流形的均值”。 (2006) IEEE 计算机视觉和模式识别。

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

Answer 2

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

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

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

） 2比较容易解决。 第三，非常主观，仍然是一个研究课题。
我可以为 No1 和 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. 接近精确的重复项
   在这种情况下，您必须设置一个阈值并比较哈希值与每个哈希值的距离。
   其他。 这必须通过对图像内容进行反复试验来完成。

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 3

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

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

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

http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection =教程/色彩空间

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

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

Answer 4

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

开始之前

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

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

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和3400个像素之间、以及2和3200个像素之间。

在其他图像中搜索相似的感兴趣区域，标准化距离值并查看是否有潜在的匹配项。 该技术对于旋转和缩放的图像非常有效。 您感兴趣的区域越多，匹配的概率就会随着每次距离测量的匹配而增加。

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

变形

变形两个图像是将一张图像变成另一张图像的过程通过一组步骤：

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

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

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

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

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

Zipping

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

比较语料库时一个有趣的优化是，您可以删除被认为太常见的单词，例如“The”、“A”、“And”等。这些单词会稀释我们的结果，我们想要弄清楚两个语料库有多大差异所以这些可以在加工前去除。 也许图像中存在类似的常见信号可以在压缩之前去除？ 也许值得研究一下。

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

透明度

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

反转信号

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

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

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

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

_{（来源：mcburrz.com）}

反转其中之一它们，然后将其添加到另一个将不会产生中性画布，而这正是我们的目标。 然而，当比较两张原始图像的像素时，我们绝对可以看到两者之间的清晰关系。

我已经有几年没有研究颜色了，并且不确定色谱是否处于线性范围内，但是如果您确定了两张图片之间色差的平均因子，则可以在处理之前使用该值来标准化数据这项技术。

树数据结构

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

您可以考虑提取图像的某些属性（例如颜色箱）并生成霍夫曼树或类似的数据结构。 您也许可以比较两棵树的相似性。 这对于摄影数据（例如具有大范围颜色的照片数据）效果不佳，但对于卡通或其他减少颜色设置的图像，这可能有效。

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

FFFFFF|000000|FDFD44|FFFFFF

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

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

更多想法

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

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

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

其他需要考虑的事情

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

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

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

如果采用多种算法，正如本答案开头提到的，人们可能会找到所有阳性结果，但误报率为 20%，因此研究其他算法的属性/优点/缺点将会很有趣，因为另一种算法可能会有效消除从另一个返回的误报。

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

Answer 5

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

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

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

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

Answer 6

如果您运行的是 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 应该纠正任何偏移，以便比较命令实际上有机会检测到相同的像素。

Answer 7

如果您愿意考虑采用不同的方法来检测图像的非法副本，您可以考虑水印< /a>. （从1.4开始）

...将版权信息插入数字对象而不损失质量。 每当数字对象的版权受到质疑时，就会提取此信息以识别合法所有者。 还可以对原始购买者的身份以及版权所有者的身份进行编码，从而可以追踪任何未经授权的副本。

虽然这也是一个复杂的领域，但有一些技术可以允许水印信息通过总体图像更改而保留：（从 1.9 开始）

...任何合理强度的信号变换都无法去除水印。 因此，想要删除水印的盗版者不会成功，除非他们过度贬低文档而无法获得商业利益。

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

Answer 8

这只是一个建议，可能行不通，我已经准备好接受此事。

这会产生误报，但希望不会产生误报。

1. 调整两个图像的大小，使它们具有相同的大小（我假设两个图像的宽度与长度的比率相同）。

2. 使用无损压缩算法（例如gzip）压缩两个图像的位图。

   使用

3. 查找具有相似文件大小的文件对。 例如，您可以根据文件大小的相似程度对您拥有的每对文件进行排序，然后检索前 X 个。

正如我所说，这肯定会产生误报，但希望不会产生误报。 您可以在五分钟内完成此操作，而 Porikil 等人。 等人。 可能需要大量的工作。

Answer 9

一个想法：

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

第 2 步并非微不足道。 特别是，您可能需要使用智能算法来查找其他图像上最相似的关键点。 点描述符通常是非常高维的（比如一百个参数），并且有很多点需要查看。 kd 树在这里可能有用，哈希查找效果不佳。

变体：

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