比较两张图片的算法

Question

比较两张图片的算法

algorithmimageimage-processingimage-recognition

165

给定两个不同的图像文件（以我选择的任何格式），我需要编写一个程序来预测其中一个是另一个非法拷贝的机会。副本的作者可能会做一些事情，例如旋转、取反或添加微不足道的细节（以及更改图像的尺寸）。

您是否知道任何算法可以完成这种工作？

- Lam Luu

12

怎么确定哪一个是原始版本？ - jfs

1

我猜他手头有原始文件，需要验证一个外部文件是否是经过转换的副本，还是与原始文件无关。 - unfa

基于机器学习的图像特征向量可以具有鲁棒性，并且可以通过余弦相似度进行轻松比较。您可以搜索img2vec项目或类似latentvector.space的内容，以便更轻松地集成API（免责声明：我运营该服务）。 - Christian Safka

9个回答

36

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

我成功地利用本文中介绍的技术，通过对Sobel、Canny、SUSAN特征/边缘检测输出以及原始灰度像素组成的协方差矩阵，能够检测出从相邻网络摄像头捕捉的图像中的重叠区域。

- Nick

1

@Satoru Logic：谷歌搜索显示了这篇论文的相关结果： http://www.google.com/search?q=Porikli,+Fatih,+Oncel+Tuzel,+and+Peter+Meer.+%E2%80%9CCovariance+Tracking+Using+Model+Update+Based+on+Means+on+Riemannian+Manifolds%E2%80%9D.+(2006)+IEEE+Computer+Vision+and+Pattern+Recognition。 - Nick

34

一个想法：

使用关键点检测器来找到图像中某些点的尺度和变换不变性描述符（例如SIFT、SURF、GLOH或LESH）。
尝试将来自两幅图像的具有相似描述符的关键点对齐（例如在全景拼接中），如果需要，允许一些图像变换（例如缩放和旋转或弹性拉伸）。
如果许多关键点对齐得好（存在这样的变换，使得关键点对准误差低；或者变换“能量”低等），则您可能拥有相似的图像。

第二步并不简单。特别是，您可能需要使用智能算法在另一幅图像中找到最相似的关键点。点描述符通常是非常高维的（如百个参数），而且要查找很多点。kd树在这里可能很有用，哈希查找效果不佳。

变体：

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

- sastanin

2

我认为这也是正确的方法。只是一个细节：SIFT、SURF和GLOH不是关键点检测器，它们是关键点描述符。常见的关键点检测器有（尺度不变的）DoG、Harris或特征值检测器。 - Niki

对于第二步，您可以使用最近邻居算法，该算法使用描述符之间的欧几里得距离。 - MobileCushion

16

这个问题实际上比看起来的要复杂得多 :-) Nick的建议很不错。

首先要知道，任何有价值的比较方法都基本上是通过将图像转换为另一种形式来工作--一种使其更容易选择相似特征的形式。通常，这些东西并不适合轻松阅读...

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

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

霍夫变换是一种在计算机视觉和图像处理中使用的技术，用于检测数学形状的存在。它可以检测出直线、圆或其他形状，并在图像中提取这些形状的参数。具体而言，霍夫变换将图像空间中的点映射到一个参数空间中，使得在图像空间中共线的点，在参数空间中对应的曲线相交。

霍夫变换最早用于检测图像中的直线，但现在已经广泛应用于检测圆、椭圆、直线段等形状。此外，霍夫变换还被用于边缘检测、形态分析和目标跟踪等领域。

- shea241

8

在您描述的表单中，问题很棘手。您是否认为将图像的一部分复制、粘贴到另一个较大的图像中算作复制？等等。

我们通常所说的重复可能对算法来说很难区分。您的重复可以是以下几种情况：

1. 精确重复 2. 几乎完全相同的重复（图像的小修改等） 3. 感知上的重复（内容相同，但视角、摄像机等不同）

第1和第2种情况比较容易解决，第3种情况非常主观，仍然是研究课题。我可以提供第1和第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

在这种情况下，您需要设置一个阈值，并比较它们的哈希值之间的距离，以确定是否是几乎完全相同。对于您的图像内容，必须通过试错来完成此操作。

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数据集来测试你的方法。它是这类应用的公认标准。）

- navneeth

5

这只是一些建议，可能不会起作用，我已经做好被批评的准备。

这样做会产生虚警，但希望不会漏检。

将两个图像的大小调整为相同的大小（假设宽高比在两个图像中是相同的）。
使用无损压缩算法（例如gzip）压缩两个图像的位图。
查找文件大小相似的文件对。例如，您可以通过文件大小的相似程度对每对文件进行排序，并检索前X个。

正如我所说，这肯定会产生虚警，但希望不会漏检。您可以在五分钟内实现此操作，而Porikil等人可能需要进行大量工作。

- Owen

我非常喜欢这个解决方案，易于实现，我相信它将产生比随机识别率更好的效果。 - Tom Gullen

这是一个问题：如果复制品保存在不同的分辨率下，它是否有效？ - Dr. belisarius

4

我认为，如果你愿意将该方法应用于每种可能的方向和负版本，那么使用特征脸是开始进行图像识别（具有良好的可靠性）的良好选择：http://en.wikipedia.org/wiki/Eigenface 另一个想法是将两个图像转换为它们各自组成的向量。这样做的好方法是创建一个在x*y维度上运作的向量（x为您的图像的宽度，y为高度），每个维度的值都适用于（x，y）像素值。然后使用两个类别：“匹配”和“不匹配”的K最近邻变体运行。如果它与原始图像非常接近，则适合于“匹配”类别；否则，它不适合。

K最近邻算法可以在此处找到，网络上还有其他很好的解释：http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm KNN的好处是，您比较的变量越多，算法就越准确。缺点是首先需要训练系统的图像目录。

- Nick Udell

1

这是一个好主意，但只有在数据中存在面部时才有效。此外，它只能识别人，而不能识别情境。因此，一个在多个出版物中出现的专业演员会产生很多误报。 - Tom Gullen

除非我误解你的使用意图。 - Tom Gullen

Eigenfaces在人脸上表现良好，因为不同面部表情的照片非常相似，并且可以近似为图片空间的低维线性子空间。我无法看出这种近似如何适用于任何类型的图片的一般仿射变换。 - Niki

我的错误，我一定是误解了特征脸的工作方式。我仍然认为，应用高维映射和K-最近邻算法可能会有所帮助，具体取决于他的特定应用。 - Nick Udell

1

我怀疑直接将KNN应用于原始像素值可能不会有太大帮助。小的转换/旋转通常会导致原始像素值巨大的差异，特别是如果图片包含锐利的对比度或细线条。因此，同一张图片的任意变换版本在该空间中并不真正接近彼此（它们不会聚集成簇），因此KNN效果不佳。虽然我猜它在图像直方图或某些其他变换不变表示上可能效果很好。 - Niki

显示剩余2条评论

2

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

来自hugin-tools包的align_image_stack

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

来自imagemagick包的compare

这是一个可以查找并计算两个图像中不同像素数量的程序。这里有一个不错的教程: http://www.imagemagick.org/Usage/compare/ ，使用-fuzz N％，您可以增加误差容忍度。 N越高，则将两个像素视为相同的误差容忍度越高。

align_image_stack应该会纠正任何偏移，因此compare命令实际上有机会检测到相同的像素。

- unfa

1

如果你愿意考虑另一种方式来检测你的图像是否存在非法副本，你可以考虑数字水印。（来自 1.4）

它能够在不丢失质量的情况下将版权信息嵌入到数字对象中。每当数字对象的版权受到质疑时，该信息都会被提取出来以确定合法所有者。还可以将原始买家的身份和版权持有者的身份编码，从而追踪任何未经授权的副本。

尽管这也是一个复杂的领域，但有一些技术可以使水印信息在粗略的图像变化中保持不变：（来自 1.9）

任何具有合理强度的信号变换都无法移除水印。因此，除非他们过度降低文档的商业价值，否则盗版者将无法成功地删除水印。

当然，常见问题解答称：“实施这种方法非常具有挑战性”，但如果你成功了，你就能够高度确认图像是否为副本，而不仅仅是一个百分比的可能性。

- JeffH

有没有更多关于水印如何在大量编辑后持久存在的信息？听起来非常有趣。 - Tom Gullen

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

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

- Tom Gullen · Accepted Answer

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

开始之前

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

考虑扫描图像的各个潜在区域，这些区域可以代表图像的缩放部分和不同的位置和旋转。如果其中一个图像是另一个图像的倾斜版本，则开始变得棘手，这就是您应该确定并妥协的限制条件。

Matlab是测试和评估图像的优秀工具。

测试算法

您应该测试（至少）一个大型人工分析的测试数据集，其中匹配已经预先知道。例如，在您的测试数据中，有1,000个图像，其中5％的图像匹配，那么您现在有了一个相当可靠的基准。找到10％正面结果的算法不如在我们的测试数据中找到4％正面结果的算法好。然而，一种算法可能会找到所有匹配项，但也可能有20％的误报率，因此有多种方法可以评估您的算法。

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

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

你可以控制软件并开始分析其产生的结果，将软件应用于现实世界。这是一种可以无限制进行的软件项目，总有调整和改进的空间，设计时要牢记这一点，因为很容易陷入永无止境的项目陷阱。 颜色桶 使用两张图片，扫描每个像素并计算颜色数量。例如，你可能会有“桶”：

white
red
blue
green
black

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

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

边缘检测

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

对于两张相似的图片，边缘检测应该会提供一个可用且相当可靠的独特足迹。

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

将图片逐像素进行比较，计算匹配和不匹配的数量。如果它们在一定误差范围内，则匹配。否则，您可以尝试减小分辨率到一定程度，看看匹配概率是否提高。 感兴趣的区域 某些图像可能具有独特的感兴趣部分/区域。这些区域可能与图像的其余部分形成高对比度，并且是在其他图像中搜索匹配项的好对象。以这张照片为例：

_{(来源: meetthegimp.org)} 蓝色的建筑工人是一个感兴趣的区域，可以用作搜索对象。您可能有几种方法从这个感兴趣的区域中提取属性/数据，并将它们用于搜索数据集。

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

_{(来源: per2000.eu)} 我们有三个明确的兴趣区域。区域1和2之间的距离可能为200个像素，1和3之间为400个像素，2和3之间为200个像素。

搜索其他图片以寻找类似的兴趣区域，规范化距离值并查看是否有潜在匹配项。这种技术对于旋转和缩放的图像效果很好。您拥有的兴趣区域越多，每个距离测量匹配的概率就越大。

重要的是要考虑数据集的上下文。例如，如果您的数据集是现代艺术，则兴趣区域将非常有效，因为兴趣区域可能被设计为最终图像的基本部分。但是，如果您正在处理建筑工地的图像，则非法复制者可能会将兴趣区域解释为丑陋，并可能会自由裁剪/编辑。请记住数据集的共同特征，并尝试利用这些知识。

变形变形两张图片是将一张图片通过一系列步骤变成另一张图片的过程：

alt text

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

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

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

在一个非常简单的例子中，当需要进行较少更改时，一个算法可能会执行得更快。然后我们知道，这两个图像彼此具有更高的共性的概率更大。

这种技术对于旋转、扭曲、倾斜、缩放、所有类型的复制图像都可能很有效。再次强调，这只是我想到的一个想法，据我所知，它并没有基于任何研究学术（我还没有认真看过），因此你可能会付出很多工作但收效甚微或没有成果。

压缩

这个问题中 Ow 的回答非常好，我记得在学习 AI 时读到过这些技术。它在比较语料库词汇表方面非常有效。

在比较语料库时，一个有趣的优化是，您可以删除被认为太常见的单词，例如“the”、“a”、“and”等。这些单词会稀释我们的结果，我们想要计算出两个语料库之间的差异，因此在处理之前可以将它们删除。也许在压缩之前可以去除图像中类似的常见信号？值得研究。

压缩比是一种非常快速且相对有效的确定两组数据相似性的方法。了解压缩如何工作将让您对为什么这可能非常有效有一个好的想法。对于一个快速发布的算法，这可能是一个很好的起点。

透明度

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

信号反转

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

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

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

然而，请考虑两个图像，它们相等，除了其中一个应用了明亮的效果：

_{(来源: mcburrz.com)}

将其中一个图片反转，然后加到另一个图片上，并不能得到我们想要的中性画布。但是，当比较两个原始图像的像素时，我们可以明显看到两者之间存在着明显的关系。

我已经好几年没有学习颜色了，不确定颜色光谱是否在线性刻度上，但如果您确定了两张图片之间的平均颜色差异因子，则可以使用此值来规范化数据，然后再使用此技术进行处理。

树形数据结构

起初，这些似乎与问题不符，但我认为它们可能有效。

您可以考虑提取图像的某些属性（例如颜色箱）并生成huffman tree或类似的数据结构。您可能能够比较两棵树的相似性。这对于具有大量颜色光谱的摄影数据（例如卡通或其他减少颜色集的图像）效果不佳，但对于其他减少颜色集的图像则可能有效。

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

FFFFFF|000000|FDFD44|FFFFFF

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

比较trie树应该相对容易，并且可能提供有效的结果。 更多想法 我偶然发现了一篇关于卫星图像分类的有趣论文，其中概述了以下内容：

纹理测量考虑因素包括：共生矩阵、灰度差异、纹理-色调分析、从傅里叶谱中导出的特征以及Gabor滤波器。在分类时，一些傅里叶特征和一些Gabor滤波器被认为是不错的选择，特别是当单一频带用于分类时。

值得进一步研究这些测量方法，尽管其中一些可能与您的数据集无关。 其他需要考虑的事情 可能有很多关于这种事情的论文，所以阅读其中一些应该会有所帮助，尽管它们可能非常技术性。这是计算机领域中极其困难的领域，许多人花费了很多徒劳无功的时间来尝试做类似的事情。保持简单并建立在这些想法之上是最好的方法。创建一个具有优于随机匹配率的算法应该是一个相当困难的挑战，并且开始改进那真的很难实现。

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

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

如本答案开头所提到的，如果使用多个算法，则可能会发现所有积极因素，但误报率为20％，因此研究其他算法的属性/优点/缺点可能会很有趣，因为另一个算法可能会有效地消除从另一个算法返回的误报。

注意不要陷入完成永无止境的项目的陷阱，祝你好运！