比较两个图像的算法

Question

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

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

Answer 1

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

开始之前

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

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

Matlab是测试和评估图像的绝佳工具。

测试算法

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

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

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

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

色桶

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

white
red
blue
green
black

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

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

边缘检测

如何使用 Edge Detection .

(来源: wikimedia.org)

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

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



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

感兴趣的区域

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


(来源: meetthegimp.org)

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

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


(来源: per2000.eu)

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

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

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

变形

Morphing两个图像是通过一组步骤将一个图像转换为另一个图像的过程:



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

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

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

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

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

zipper

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

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

压缩比是确定两组数据的相似程度的一种非常快速且合理有效的方法。阅读关于 how compression works会给你一个很好的想法，为什么这会如此有效。对于快速发布算法，这可能是一个很好的起点。

透明度

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

反相信号

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


(来源: themotorreport.com.au)

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

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


(来源: mcburrz.com)

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

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

树数据结构

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

您可以考虑提取图像的某些属性(例如颜色箱)并生成 huffman tree或类似的数据结构。您也许可以比较两棵树的相似性。这不适用于例如具有大范围颜色的摄影数据，但是这可能适用于卡通或其他减少颜色集的图像。

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

FFFFFF|000000|FDFD44|FFFFFF

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

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

更多创意

我偶然发现了一篇关于 classification of satellite imagery 的有趣论文。 ，它概述了:

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%，那么研究其他算法的属性/优势/劣势会很有趣，因为另一种算法可能会有效地消除从另一个返回的误报。

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