给定两个不同的图像文件(我选择的任何格式),我需要编写一个程序来预测如果一个文件是另一个文件的非法复制的机会。该副本的作者可能会做诸如旋转,制作负片或添加琐碎细节(以及更改图像尺寸)之类的事情。
您知道执行这种工作的算法吗?
最佳答案
这些只是我曾经考虑过的问题,从未尝试过,但我喜欢这样思考的想法!
开始之前
考虑对图片进行归一化,如果一个图片的分辨率高于另一个图片,请考虑以下选项:其中一个是另一张图片的压缩版本,因此降低分辨率可能会提供更准确的结果。
考虑扫描图像的各个预期区域,这些区域可能代表图像的缩放部分以及各种位置和旋转。如果其中一幅图像是另一幅图像的歪斜版本,它将开始变得棘手,这些是您应该确定并妥协的限制。
Matlab是用于测试和评估图像的出色工具。
测试算法
您应该(至少)测试一组大型的人工分析的测试数据,这些数据事先已知。例如,如果在测试数据中有1,000张图像,其中有5%匹配,则您现在有了一个相当可靠的基准。在我们的测试数据中,找到10%阳性的算法不如发现4%阳性的算法。但是,一种算法可能会找到所有匹配项,但误报率也很高,为20%,因此有几种方法可以对算法进行评分。
应将测试数据设计为涵盖您希望在现实世界中找到的尽可能多的动态类型。
重要的是要注意,每个有用的算法都必须比随机猜测更好地执行,否则对我们没有用!
然后,您可以以受控方式将软件应用于现实世界,并开始分析其产生的结果。这是可以无限进行的软件项目,您总是可以进行调整和改进,在设计它时要记住这一点,因为很容易陷入永无止境的项目陷阱,这一点很重要。
颜色桶
使用两张图片,扫描每个像素并计算颜色。例如,您可能拥有“存储桶”:
white
red
blue
green
black
(显然,您将拥有更高的计数器分辨率)。每次找到“红色”像素,就增加红色计数器。每个存储桶都可以代表各种颜色,分辨率越高,精度越高,但是您应该以可接受的差异率进行实验。
获得总计后,将其与第二张图像的总计进行比较。您可能会发现每个图像都有一个相当独特的足迹,足以识别匹配项。
边缘检测
如何使用Edge Detection。
(来源:wikimedia.org)
对于两张相似的图片,边缘检测将为您提供可用且相当可靠的独特封装。
拍摄两张照片,然后应用边缘检测。也许测量边缘的平均厚度,然后计算图像可以缩放的可能性,并在必要时重新缩放。以下是在各种旋转中应用的Gabor Filter(一种边缘检测)的示例。
比较图片的像素,计算匹配和不匹配。如果它们在某个错误阈值之内,则您具有匹配项。否则,您可以尝试将分辨率降低到某个点,然后查看匹配可能性是否提高。
名胜古迹
一些图像可能具有独特的感兴趣的片段/区域。这些区域可能与图像的其余部分形成强烈对比,并且是在其他图像中进行搜索以找到匹配项的好项目。以这张图片为例:
(来源:meetthegimp.org)
蓝色的建筑 worker 是关注的区域,可以用作搜索对象。您可能有几种方法可以从此感兴趣的区域提取属性/数据,然后使用它们来搜索数据集。
如果您有两个以上的兴趣区域,则可以测量它们之间的距离。举这个简化的例子:
(来源:per2000.eu)
我们有3个明确的兴趣区域。区域1和2之间的距离可以是200像素,1和3 400像素之间以及2和3 200像素。
在其他图像中搜索感兴趣的相似区域,对距离值进行归一化,然后查看是否存在潜在的匹配项。该技术可以很好地用于旋转和缩放的图像。您拥有的兴趣区域越多,匹配的可能性就随每次距离测量值的匹配而增加。
考虑数据集的上下文非常重要。例如,如果您的数据集是现代艺术,那么感兴趣的区域就可以很好地工作,因为感兴趣的区域可能被设计为最终图像的基本部分。但是,如果您正在处理建筑工地的图像,则非法复印机可能会将感兴趣的区域解释为丑陋的,并且可能会对其进行自由裁剪/编辑。请记住数据集的共同特征,并尝试利用这些知识。
变形
Morphing两个图像是通过一组步骤将一个图像转换为另一个图像的过程:
请注意,这与将一个图像淡入另一个图像不同!
有许多可以使图像变形的软件包。传统上,它用作过渡效果,两张图像通常不会变半成最终的结果,一个极端变到另一个极端。
为什么这会有用?取决于您使用的变形算法,图像的相似性与变形算法的某些参数之间可能存在关系。
在完全简化的示例中,当要进行的更改较少时,一种算法的执行速度可能会更快。然后我们知道这两个图像彼此共享属性的可能性更高。
对于旋转,扭曲,倾斜,缩放的所有类型的复制图像,此技术都可以很好地工作。再说一次,这只是我的一个想法,据我所知,它并不是基于任何研究过的学术界(虽然我看起来并不难),所以对您来说可能是很多工作,但结果有限/没有结果。
压缩
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
我们有一个相当独特的trie代码,它扩展了24个级别,增加/减少级别(IE减小/增加子正方形的大小)可能会产生更准确的结果。
比较特里树应该相当容易,并且有可能提供有效的结果。
更多想法
我偶然发现了有关classification of satellite imagery的有趣的纸制字母,它概述了:
尽管其中一些可能与您的数据集无关,但值得更详细地研究这些度量。
需要考虑的其他事项
可能有很多关于这种事情的论文,因此尽管其中一些技术性很强,但阅读其中一些内容应该会有所帮助。这是计算 Realm 中极为困难的 Realm ,许多人试图做类似的事情花费了很多无用的时间。保持简单并以这些想法为基础将是最好的方法。创建一个比随机匹配率更好的算法,并开始对其进行改进,确实确实变得非常困难,这是一个相当困难的挑战。
每种方法可能都需要进行彻底的测试和调整,如果您还具有要检查的图片类型的任何信息,这将很有用。例如,广告中很多都包含文本,因此进行文本识别将是一种简单且可能非常可靠的找到匹配项的方法,尤其是与其他解决方案结合使用时。如前所述,尝试利用数据集的通用属性。
将可衡量的投票和替代技术(取决于其有效性)相结合,将是您创建可产生更准确结果的系统的一种方式。
如果采用多种算法(如在此答案开头提到的那样),则可能会找到所有阳性,但假阳性率仅为20%,因此研究另一种算法的特性/优势/弱点将是有趣的,因为另一种算法可能有效消除从其他人返回的误报。
小心不要陷入试图完成永无止境的项目的过程中,祝您好运!