比较两个图像的算法

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

您知道执行这种工作的任何算法吗？

---

这些只是我曾经考虑过的问题，从未尝试过，但我喜欢这样思考的问题！

好。

在你开始之前

好。

考虑对图片进行归一化，如果一个分辨率高于另一个分辨率，请考虑选择其中一个为另一种的压缩版本，因此按比例缩小分辨率可能会提供更准确的结果。

好。

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

好。

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

好。

测试算法

好。

您应该(至少)测试一组大型的人工分析的测试数据，这些数据事先已知。例如，如果在测试数据中有1,000张图像，其中有5％匹配，则您现在有了一个相当可靠的基准。在我们的测试数据中，找到10％阳性的算法不如发现4％阳性的算法好。但是，一种算法可能会找到所有匹配项，但误报率也很高，为20％，因此有几种方法可以对算法进行评分。

好。

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

好。

重要的是要注意，每个有用的算法都必须比随机猜测更好地执行，否则对我们没有用！

好。

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

好。

色桶

好。

对于两张图片，扫描每个像素并计算颜色。例如，您可能拥有"存储桶"：

好。

(显然，您将拥有更高的计数器分辨率)。每次找到"红色"像素，就增加红色计数器。每个存储桶都可以代表各种颜色，分辨率越高，精度越高，但是您应该以可接受的差异率进行实验。

好。

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

好。

边缘检测

好。

如何使用边缘检测。

_{(来源：wikimedia.org)}

好。

对于两张相似的图片，边缘检测将为您提供可用且相当可靠的独特封装。

好。

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

好。

好。

比较图片的像素，计算匹配和不匹配。如果它们在某个错误阈值之内，则您具有匹配项。否则，您可以尝试将分辨率降低到某个点，然后查看匹配概率是否提高。

好。

名胜古迹

好。

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

好。

_{(来源：Meetthegimp.org)}

好。

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

好。

如果您有两个以上的兴趣区域，则可以测量它们之间的距离。举这个简化的例子：

好。

_{(来源：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数据结构非常适合存储词典，例如字典。这是一个前缀树。也许可以构建与词典等效的图像(同样我只能想到颜色)来构建特里。如果将300x300的图像缩小为5x5的正方形，然后将每个5x5的正方形分解为一系列颜色，则可以根据结果数据构造特里。如果2x2正方形包含：

好。

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

好。

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

好。

更多想法

好。

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

好。

Texture measures considered are: cooccurrence matrices, gray-level differences, texture-tone analysis, features derived from the Fourier spectrum, and Gabor filters. Some Fourier features and some Gabor filters were found to be good choices, in particular when a single frequency band was used for classification.

Ok.

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

好。

其他要考虑的事情

好。

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

好。

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

好。

将可衡量的投票和技术(取决于其有效性)相结合的替代测量方法和技术，将是您创建可产生更准确结果的系统的一种方式。

好。

如果采用多种算法(如在此答案开头提到的那样)，则可能会发现所有阳性，但假阳性率仅为20％，因此研究另一种算法的特性/优势/弱点将是有趣的，因为另一种算法可能 有效消除从另一个人返回的误报。

好。

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

好。

好。

---

阅读本文：Porikli，Fatih，Afterl Tuzel和Peter Meer。"使用基于模型更新的协方差跟踪
在黎曼流形上"。 (2006)IEEE计算机视觉和模式识别。

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

---

一个主意：

使用关键点检测器查找图像中某些点(例如SIFT，SURF，GLOH或LESH)的比例不变和变换不变的描述符。

尝试将两个图像的关键点与相似的描述符对齐(例如在全景拼接中)，并在必要时进行一些图像变换(例如缩放和旋转或弹性拉伸)。

如果许多关键点对准得很好(存在这样的变换，则关键点对准误差很低；或者变换"能量"很低，等等)，您可能拥有相似的图像。

第2步并非易事。特别是，您可能需要使用智能算法在其他图像上找到最相似的关键点。点描述符通常是非常高维的(例如一百个参数)，并且有很多点需要浏览。 kd-trees在这里可能很有用，哈希查找效果不佳。

变体：

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

---

这确实比看起来简单得多：-)尼克的建议是一个好建议。

首先，请记住，任何有价值的比较方法实际上都可以通过将图像转换为其他形式来工作，这种形式可以更轻松地挑选出相似的特征。通常，这些东西并不能使阅读非常轻松...

我能想到的最简单的例子之一就是简单地使用每个图像的色彩空间。如果两个图像具有高度相似的颜色分布，则可以合理地确定它们显示的是相同的东西。至少，您可以有足够的把握来对其进行标记，或者进行更多的测试。在色彩空间中比较图像还可以抵抗旋转，缩放和某些裁切等操作。当然，它不会抵抗图像的大量修改或强烈的重新着色(甚至是简单的色相转换都会有些棘手)。

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/Hough_transform

---

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

如果您退后一步，则在对主图像进行水印处理时更容易解决。
您将需要使用水印方案将代码嵌入图像中。与某些人建议的一些低级方法(边缘检测等)相比，退后一步，加水印方法是优越的，因为：

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

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

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

---

这只是一个建议，可能不起作用，我准备就此提出呼吁。

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

调整两个图像的大小，以使它们具有相同的大小(我假设两个图像的宽度与长度之比相同)。

使用无损压缩算法(例如gzip)压缩两个图像的位图。

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

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

---

我相信，如果您愿意将该方法应用于所有可能的方向和否定版本，则使用特征脸可以很好地开始图像识别(具有良好的可靠性)：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的好处在于，与原始图像相比，变体越多，算法就越准确。不利的一面是您需要图像目录才能首先训练系统??。

---

如果您愿意考虑采用其他方法来检测图像的非法副本，则可以考虑加水印。 (从1.4开始)

...inserts copyright information into the digital object without the loss of quality. Whenever the copyright of a digital object is in question, this information is extracted to identify the rightful owner. It is also possible to encode the identity of the original buyer along with the identity of the copyright holder, which allows tracing of any unauthorized copies.

虽然它也是一个复杂的领域，但是有一些技术可以使水印信息通过总体图像更改而得以保留：(从1.9开始)

... any signal transform of reasonable strength cannot remove the watermark. Hence a pirate willing to remove the watermark will not succeed unless they debase the document too much to be of commercial interest.

当然，常见问题解答要求实施这种方法：" ...非常具有挑战性"，但是，如果成功实现，您将非常有信心确定图像是否是副本，而不是百分比可能性。

---

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

---