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

我们知道执行这种工作的算法吗？

解决方案

回答

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

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

回答

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

首先，请记住，任何有价值的比较方法实际上都可以通过将图像转换为其他形式来工作-这种形式可以更轻松地挑选相似的特征。通常，这些东西并不能使阅读非常轻松...
我能想到的最简单的例子之一就是简单地使用每个图像的色彩空间。如果两个图像具有高度相似的颜色分布，则可以合理地确定它们显示的是相同的东西。至少，我们可以有足够的把握来对其进行标记，或者进行更多的测试。在色彩空间中比较图像还可以抵抗旋转，缩放和某些裁切等操作。当然，它不会抵抗图像的大量修改或者强烈的重新着色(甚至是简单的色相转换都会有些棘手)。

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

回答

如果我们愿意考虑采用其他方法来检测图像的非法副本，则可以考虑加水印。 (从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.

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

回答

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

这将产生假阳性，但希望不会产生假阴性。

• 调整两个图像的大小，以使其具有相同的大小(我假设两个图像的宽度与长度之比相同)。
• 使用无损压缩算法(例如gzip)压缩两个图像的位图。
• 查找具有相似文件大小的文件对。例如，我们可以按照文件大小的相似程度对每对文件进行排序，然后检索前X个。

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

回答

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

回答

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

在你开始之前

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

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

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

测试算法

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

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

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

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

色桶

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

white
red
blue
green
black

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

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

边缘检测

如何使用边缘检测。
替代文字http://upload.wikimedia.org/wikipedia/en/thumb/8/8e/EdgeDetectionMathematica.png/500px-EdgeDetectionMathematica.png

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

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

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

名胜古迹

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

替代文字http://meetthegimp.org/wp-content/uploads/2009/04/97.jpg

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

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

替代文字http://www.per2000.eu/assets/images/3_dots_black_03.jpg

我们有3个清晰的兴趣区域。区域1和2之间的距离可以是200像素，1和3 400像素之间以及2和3 200像素。

在其他图像中搜索相似的感兴趣区域，对距离值进行归一化，然后查看是否存在潜在的匹配项。该技术可以很好地用于旋转和缩放的图像。我们拥有的兴趣区域越多，匹配的可能性就随每次距离测量的匹配而增加。

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

变形

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

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

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

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

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

对于旋转，变形，偏斜，缩放，所有类型的复制图像，此技术都可以很好地工作。再说一次，这只是我的一个主意，据我所知，它并不是基于任何研究过的学术界(虽然我看起来并不难)，所以对我们来说可能是很多工作，但结果有限/没有结果。

压缩

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

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

压缩率是一种确定两组数据的相似程度的非常快速且合理有效的方法。阅读有关压缩如何工作的知识，将使我们很好地理解为何如此有效。对于快速发布的算法，这可能是一个很好的起点。

透明度

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

反相信号

图像只是一个信号。如果我们从某个扬声器播放噪声，并且以完全相同的音量在另一个扬声器中以完全同步的方式播放相反的噪声，则它们会相互抵消。

替代文字http://www.themotorreport.com.au/wp-content/uploads/2008/07/noise-cancellation.gif

反转图像，然后将其添加到其他图像上。重复缩放它/循环的位置，直到找到结果图像，其中足够多的像素为白色(或者黑色？我将其称为中性画布)以为我们提供正匹配或者部分匹配。

但是，请考虑两个相等的图像，只是其中一个图像具有加亮效果：

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

我已经好几年没有研究色彩了，并且不确定色谱是否在线性范围内，但是如果我们确定了两张图片之间色差的平均因子，则可以使用该值对数据进行归一化处理，然后再处理。这种技术。

树数据结构

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

我们可以考虑提取图像的某些属性(例如颜色容器)并生成霍夫曼树或者类似的数据结构。我们可能能够比较两棵树的相似性。例如，对于大范围的彩色图像，这不适用于摄影数据，但对于卡通或者其他缩小的彩色设置图像，这可能会起作用。

这可能行不通，但这是一个主意。 trie数据结构非常适合存储词典，例如字典。这是一个前缀树。也许可以构建与词典等效的图像(再次我只能想到颜色)来构建特里。如果将300x300的图像缩小为5x5的正方形，然后将每个5x5的正方形分解为一系列颜色，则可以根据结果数据构造特里。如果2x2正方形包含：

FFFFFF|000000|FDFD44|FFFFFF

我们有一个相当独特的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.

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

其他要考虑的事情

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

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

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

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

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

回答

我们将需要使用水印方案将代码嵌入图像中。与某些人建议的一些低级方法(边缘检测等)相比，退后一步，加水印方法是优越的，因为：

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

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

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

回答

一个主意：

• 使用关键点检测器查找图像中某些点(例如SIFT，SURF，GLOH或者LESH)的比例不变和变换不变的描述符。
• 尝试将两个图像的关键点与相似的描述符对齐(例如在全景拼接中)，并在必要时进行一些图像变换(例如缩放和旋转或者弹性拉伸)。
• 如果许多关键点对准得很好(存在这样的变换，则关键点对准误差很低；或者变换"能量"很低，等等)，我们可能拥有相似的图像。

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

变体：

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